# Combinatorics: n people moving between three queues.

We have 3 queues; at first n people are in first queue, numbered from 1 to n. One of the following three things happens every minute :

1. first person from first queue moves behind the last person in second queue .
2. first person from second queue moves behind the last person in third queue .
3. first person from first queue moves behind the last person in third queue .

The second queue has a capacity of "k" people .

A) if n=100 and k=1 what is the number of different ways that the given n people can stand in the third queue ?

B) if n=11 and k=4 what is the number of different ways that the given n people can stand in the third queue ?

I solved part A and answer is $$2^{99}$$ .

can you help me with part B ?

• There appears to be a bijection between permutations that can be made by this process and those where there are two moves instead - move the first person in the first queue to the end of the second queue, and move the last person in the second queue to the end of the third queue. If you can prove this it is possible to construct a recurrence relation for general k. Jul 16, 2022 at 6:55

I'm not sure how tractable part B is analytically. When the numbers are small enough, we can enumerate the possible results with a simple Python script. To get the states that can be reached in a single move,

def reachable(st, k):
(q1, q2, q3) = st
ret = []
if q1:
ret.append((q1[1:], q2, q3 + (q1[0],))) # 1->3
if len(q2) < k:
ret.append((q1[1:], q2 + (q1[0],), q3)) # 1->2
if q2:
ret.append((q1, q2[1:], q3 + (q2[0],))) # 2->3
return ret


Then, to get all the possible final states of the third queue, starting with $$n$$ people in the first:

def allFinalThirdQueueStates(n, k):
nxt = [(tuple(range(1, n+1)), (), ())]
ret = set([])
while nxt:
curr = nxt
nxt = set([])
for (q1, q2, q3) in curr:
if not q1 and not q2: ret.add(q3)
else:
for nn in reachable((q1, q2, q3), k):
return ret


At this point, you can easily reproduce the form of your correct result for part A (i.e., that the number of final states with $$n$$ people and capacity $$k=1$$ is $$2^{n-1}$$):

>>> for n in range(1, 14): print(n, len(allFinalThirdQueueStates(n, k=1)), 2**(n-1))
...
1 1 1
2 2 2
3 4 4
4 8 8
5 16 16
6 32 32
7 64 64
8 128 128
9 256 256
10 512 512
11 1024 1024
12 2048 2048
13 4096 4096


And you can also find an empirical result for part B:

>>> for n in range(1, 14): print(n, len(allFinalThirdQueueStates(n, k=4)))
...
1 1
2 2
3 5
4 14
5 42
6 131
7 417
8 1341
9 4334
10 14041
11 45542
12 147798
13 479779


Note that this sequence is in the OEIS (as A080937), and there are a number of related results in the notes.