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.
It is unclear whether the largest number can be on one of the ends. For any N>1 there are only 2 additional permutation if it is.
I'll derive the formula with N on the end allowed.
For a given N, there are N possible positions for the largest number N.
Consider each position in turn:
N _ _ _ ... _
There is 1 possibility here since the remaining (N-1) numbers must be in descending order. C(N-1,0)=1
_ N _ _ _ ... _
There are (N-1) possibilities since there are (N-1) choices for that first number. The numbers after the N can only go in one order. C(N-1,1)=(N-1)
_ _ N _ _ ... _
There are C(N-1,2) choices now. Whichever numbers ore chosen to go in from of the N can only go in one order. The other numbers can only go in one order.
and so on
So we just have all the C(N-1,i), the whole row of Pascal's triangle which is the well known sum 2^(N-1)
The is an overcount by a factor of 2 so the answer is half of this or
2^(N-2).
If we don't allow N on the end we remove these two and get the formula suggested by the previous computer solvers:
2(N-2)-2
|
|
Posted by Jer
on 2025-01-11 13:56:07 |
Derivation of formula
