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?

• It smells like induction. Not an easy problem! Nov 19, 2021 at 8:05
• I think the first stack and the output make the problem a bit unclear. It is easier for me to think of the first stack as an ordered input stream and so the output should be a permutated output of the process. Then the number of stacks serving a purpose will be one less. Nov 19, 2021 at 8:12
• And the output stream simply pops from the last stack at strategic points in the process. Nov 19, 2021 at 8:13

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!