How many permutations of the
integers 1 through N consist of a
strictly ascending sequence followed
by a strictly descending sequence?
For example, for N = 9, one such
permutation is (1-4-5-7-9-8-6-3-2).
There must be at least two integers in
a sequence, and N is considered to be a
member of both sequences.
Reversals
are not considered to be different
permutations, i.e. (2-3-6-8-9-7-5-4-1) is
the same as the above example.
A sequence meets the criteria if in contains one "peak" and zero "valleys".
n #
3 1
4 3
5 7
6 15
7 31
8 63
9 127
10 255
11 511
Observing a pattern, the solution appears to be 2^(n-2) - 1
------------
from itertools import permutations
def f(n):
nlist = [i for i in range(1,n+1)]
mylist = []
for p in permutations(nlist):
peak_count = 0
valley_count = 0
for ind, val in enumerate(p):
if ind < 2:
continue
if p[ind] < p[ind-1] and p[ind-2] < p[ind-1]:
peak_count += 1
if p[ind] > p[ind-1] and p[ind-2] > p[ind-1]:
valley_count += 1
if peak_count == 1 and valley_count == 0 and p not in mylist:
mylist.append(p)
mylist.append(p[::-1])
print(mylist, sep='\n')
return int(len(mylist)/2)
for n in range(3,10):
nlist = [i for i in range(1,n+1)]
solutions_list = []
for p in permutations(nlist):
peak_count = 0
valley_count = 0
for ind, val in enumerate(p):
if ind < 2:
continue
if p[ind] < p[ind-1] and p[ind-2] < p[ind-1]:
peak_count += 1
if p[ind] > p[ind-1] and p[ind-2] > p[ind-1]:
valley_count += 1
if peak_count == 1 and valley_count == 0 and p not in solutions_list:
solutions_list.append(p)
solutions_list.append(p[::-1])
print(n, int(len(solutions_list)/2))
|
|
Posted by Larry
on 2025-01-11 07:54:26 |
Computer solution
