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.
We'll count the number of ways of choosing the smaller number of integers to go on one side, except in the case where the smaller number is the same as the larger number (N is odd so N-1 is even), we divide by 2 so that, for example, we don't count both 1,2,5,3,4 and 4,3,5,2,1.
clearvars
for N=3:20
ways=0;
rest=N-1;
for low=1:floor(rest/2)
high=rest-low;
if low~=high
ways=ways+nchoosek(rest,low);
else
ways=ways+nchoosek(rest,low)/2;
end
end
wayCt(N)=ways;
fprintf('%3d %15d\n',N,ways)
end
fprintf('%d,',wayCt)
fprintf('\n')
finds
3 1
4 3
5 7
6 15
7 31
8 63
9 127
10 255
11 511
12 1023
13 2047
14 4095
15 8191
16 16383
17 32767
18 65535
19 131071
20 262143
which are 2^(N-2)-1
|
|
Posted by Charlie
on 2025-01-11 08:20:25 |
Matlab version
