Combinatorics: n people moving between three queues.

Question

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 ?

Answer 1

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):
          nxt.add(nn)
  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.