Number of permutations generated by using $k$ serial stacks Suppose given $k\geq 2$ stacks $S_1,S_2,\dots,S_k$, and we have $n$ numbers that we can push a number to $S_1$ and pop and push it into $S_2$ and finally we can pop from $S_k$. How many permutations can generated by this method of using $k$ stacks?
Also I read this post but i can't figured out how many stacks we need to generate $n!$ permutation or how many permutation generated by using $k$ stacks?
 A: DISCLAIMER: This is not (by far) a complete solution, only some thoughts and partial analysis!
Here is my initial model of the problem. I wrote a backtracking algorithm in C# which can be summarized as:
Function BacktrackingAlgorithm(system of stacks)
{
  for each non-empty stack:
  {
    Perform: pop(i) -> push(i + 1) // i + 1 = k is output stack
    BacktrackingAlgorithm(system of stacks) // recursive
    Revert: pop(i + 1) -> push(i)
  }

  if (all stacks are empty) record stats for permutation
}

Now my stacks are $0$-indexed $S_0,...,S_{k-1}$ and $S_0=[1,2,...,n]$ is loaded with $n$ on top. Then for $(n,k)=(3,2)$ I got the following output, where x>y>z denotes the sequence of stacks to pop from.
0>0>0>1>1>1 gives 1 2 3
0>0>1>0>1>1 gives 2 1 3
0>0>1>1>0>1 gives 2 3 1
0>1>0>0>1>1 gives 3 1 2
0>1>0>1>0>1 gives 3 2 1

Which is $5$ of the desired $3!=6$ permutations (missing 1 3 2). But when I set $(n,k)=(4,2)$ I only get $14$ of $24$ permutations whereas $(n,k)=(4,3)$ produces all $4!=24$ BUT of course has multiple ways of producing many of them. This leads me to the obvious question:
Number of valid pop-sequences?
Each number $1,...,n$ must be popped once from every stack to reach the output. Hence stack $i$ has had $n$ pop-operations. A total of $n\cdot k$ pops in total. How many pop-sequences x>y>z>... can we form for the case $(n,k)$ based on this? An upper bound is:
$$
\operatorname{popsequences}(n,k)\leq\binom {nk}n\cdot\binom{n(k-1)}{n}\cdots\binom {n\cdot2}n
$$
so for the case $(n,k)=(4,3)$ we must have:
$$
\operatorname{popsequences}(4,3)\leq\binom {12}4\cdot\binom{8}{4}=34650
$$
My program tells me the actual figure is $462$ valid pop-sequences. This is because it is not valid to pop from the last stack to begin with for instance. A stack need to contain an element before one can start popping. So many sequences in the upper bound are invalid. And the number does not resemble a value directly related to the $n!$ permutations we want to produce. This is quite a messy problem!
