Slightly different combinatorics question?

This is an interesting and unusual problem. As with all unfamiliar problems, a good way of starting is to explore possible solutions, especially when the number of variables is small, to gain familiarity and look for patterns or insight. We also need to find a convenient way of representing the problem mathematically.

Label the five people 1 to 5, with 1 the shortest and 5 the tallest. Assume they are lined up left to right, facing right. There are 5! = 120 ways in which they can be arranged (permutations). For example 12354 and 51234 meet the condition whereas 12345 and 12543 do not.

Starting with all (n-1)! permutations of numbers 1 to n-1, for n=3, 4, 5, I shall enumerate the permutations which can be formed by addition of one extra person. N permutations can be formed having exactly one person taller than the one immediately in front (to the right) and M which have two such persons.

For n = 3 (3! = 6 permutations) :

12 --> 312 132 and [123]

21 --> 231 213 and 321

N = 4. M = 1. p = 4/6 = 2/3.

For n = 4 (4! = 24 permutations) :

123 --> 4123 1423 1243 and [1234]

132 --> 1342 1324 and 4132 1432

213 --> 2413 2134 and 4213 2143

231 --> 2341 2314 and 4231 2431

312 --> 3412 3124 and 4312 3142

321 --> [4321] and 3421 3241 3214

N = 11, M = 11. p = 11/24.

For n = 5 (5! = 120 permutations) :

1234 --> 51234 15234 12534 12354 and [12345]

1243 --> 12453 12435 and 51243 15243 12543

1324 --> 13524 13245 and 51324 15324 13254

1342 --> 13452 13425 and 51342 15342 13542

1423 --> 14523 14235 and 51423 15423 14253

1432 --> xxx and 14532 14352 14325

2134 --> 25134 21345 and 52134 21534 21354

2143 --> xxx and 25143 21453 21435

2314 --> 23514 23145 and 52314 25314 23154

2341 --> 23451 23415 and 52341 25341 23541

2413 --> 24513 24135 and 52413 25413 24153

2431 --> xxx and 24531 24351 24315

3124 --> 35124 31245 and 53124 31524 31254

3142 --> xxx and 35142 31452 31425

3214 --> xxx and 35214 32514 32145

3241 --> xxx and 35214 32451 32415

3412 --> 34512 34125 and 53412 35412 34152

3421 --> xxx and 34521 34251 34215

4123 ---> 45123 41235 and 54123 41523 41253

4132 --> xxx and 45132 41352 41325

4213 --> xxx and 45213 42513 42135

4231 --> xxx and 45231 42351 42315

4312 --> xxx and 45312 43512 43125

4321 --> [54321]

N = 26, M = 66. p = 26/120.

When the person/number to the right is smaller, I shall call this a 'dip'. Generally, for n people in the queue, there is only one permutation with no dips (the n integers in increasing order). If there are m 'dips' these split the permutation into m+1 monotonically increasing sub-sequences, which I shall call 'rises'.

Let N(n) be the number of permutations of length n containing exactly one dip (two rises) and M(n) be the number containing exactly two dips (three rises). Without loss of generality, we can increase the queue size by adding another person of greater height ranked (n+1). From the single permutation containing no dips (one rise) we can form n permutations containing one dip (two rises) by inserting the next number n+1 into any of the n positions which don't include the last. For each of the N(n) permutations containing exactly one dip (two rises) we can form 2 permutations, each still containing only one dip, by inserting the next number at the end of each rise. If we insert at any of the other (n+1)-2 = n-1 positions, we will form n-1 permutations each containing two dips. Finally, for each of the M(n) permutations already containing two dips (three rises) we can insert the new person/number at the end of each rise to retain 3 permutations which still have two dips (three rises), whereas if we insert at any of the other (n+1)-3 = n-2 positions we will introduce third dip.

So after adding the n+1th person/number, the numbers N(n) and M(n) become :

N(n+1) = n + 2N(n) and

M(n+1) = (n-1)N(n)+3M(n).

We could extend the same analysis to any number of dips in the queue. For 3 dips I would expect :

L(n+1) = (n-2)M(n)+4L(n).

Using these recursion formulas, we get :

N(1) = 0+2*0 = 0, M(1) = 0

N(2) = 1+2*0 = 1, M(2) = 0*0+3*0 = 0

N(3) = 2+2*1 = 4, M(3) = 1*1+3*0 = 1

N(4) = 3+2*4 = 11, M(4) = 2*4+3*1 = 11

N(5) = 4+2*11 = 26, M(5) = 3*11+3*11 = 66

N(6) = 5+2*26 = 57, M(6) = 4*26+3*66 = 302.

These numbers agree with my enumerations above.

When there are 5 people in the queue, the probabilities of one and two dips are p1 = 26/120 and p2 = 66/120.

When there are 6 people in the queue (6! = 720) then p1 = 57/720 and p2 = 302/720.

It is possible to solve the recursion (difference) formulas above to get closed formulas.

First solve the associated homogeneous eqn N(n+1) - 2N(n) = 0. The auxiliary eqn is m - 2 = 0, m = 2, so the general solution to the homogeneous eqn is A(2^n). Next look for a particular solution : try Bn+C. Then B(n+1)+C = n+2(Bn+C) so B = 2B+1, B = -1, and B+C = 2C, C = B = -1. So the general solution is N(n) = A(2^n)-(n+1). When n=1 then N=0 so 0=2A-2, A=1.

The solution is N(n) = 2^n - (n+1).

Check : N(5) = 2^5 - 6 = 32-6 = 26. Correct.

Check : N(6) = 2^6 - 7 = 64-7 = 57. Correct.

Using this expression for N(n), Wolfram Alpha gives the solution to the 2nd recurrence relation as

M(n) = A*3^(n-1) - (1/2)(n+1)(2^(n+1) - n).

Substitute for M(2)=0 to get A=3. Therefore

M(n) = 3^n - (1/2)(n+1)(2^(n+1) - n).

Check :

M(3) = 3^3 - (1/2)(4)(2^4 - 3) = 27 - 26 = 1. Correct.

M(4) = 3^4 - (1/2)(5)(2^5 - 4) = 81 - 70 = 11. Correct.

M(5) = 3^5 - (1/2)(6)(2^6 - 5) = 243 - 177 = 66. Correct.

M(6) = 3^6 - (1/2)(7)(2^7 - 6) = 729 - 427 = 302. Correct.