Number of ways to move 1 or more elements from one list to the previous list until one list remains

Question

Given N elements, divided into at most N groups, which are then labeled 1 thru N, move all of the elements into the group labeled 1. By moving 1 to all of the elements, in group i to i-1. This means that no elements from group 1 may be moved, although it will always have at least 1 marble.

A key thing to note is that once a group is "empty", it is removed from the list of groups. That is, a elements will never be moved into an empty group.

Edit #2: I should have clarified that I have an algorithm that determines which exactly elements will be moved. Which I'm thinking is enough to bring it down from exponential to polynomial.

Here are examples:

Example from worst case of N = 5 and groups = [1,1,1,1,1]
move 1 from 4, result: [1,1,2,1]
move 2 from 3, result: [1,3,1]
move 3 from 2, result: [4,1]
move 1 from 2, result: [5], finished

All ways for N = 3 (total = 3):
[1,1,1] -> [2,1] -> [3]
[1,1,1] -> [1,2] -> [3]
[1,1,1] -> [1,2] -> [2,1] -> [3]

All ways for N = 4:
[1,1,1,1] -> [2,1,1] -> [3,1]   -> [4]
[1,1,1,1] -> [2,1,1] -> [2,2]   -> [4]
[1,1,1,1] -> [2,1,1] -> [2,2]   -> [3,1]   -> [4]

[1,1,1,1] -> [1,2,1] -> [3,1]   -> [4]
[1,1,1,1] -> [1,2,1] -> [2,1,1] -> [3,1]   -> [4]
[1,1,1,1] -> [1,2,1] -> [2,1,1] -> [2,2]   -> [4]
[1,1,1,1] -> [1,2,1] -> [2,1,1] -> [2,2]   -> [3,1] -> [4]
[1,1,1,1] -> [1,2,1] -> [1,3]   -> [4]
[1,1,1,1] -> [1,2,1] -> [1,3]   -> [2,2]   -> [4]
[1,1,1,1] -> [1,2,1] -> [1,3]   -> [2,2]   -> [3,1] -> [4]

[1,1,1,1] -> [1,1,2] -> [2,2]   -> [4]
[1,1,1,1] -> [1,1,2] -> [2,2]   -> [3,1]   -> [4]
[1,1,1,1] -> [1,1,2] -> [1,2,1] -> [3,1]   -> [4]
[1,1,1,1] -> [1,1,2] -> [1,2,1] -> [2,1,1] -> [3,1] -> [4]
[1,1,1,1] -> [1,1,2] -> [1,2,1] -> [2,1,1] -> [2,2] -> [4]
[1,1,1,1] -> [1,1,2] -> [1,2,1] -> [2,1,1] -> [2,2] -> [3,1] -> [4]
[1,1,1,1] -> [1,1,2] -> [1,2,1] -> [1,3]   -> [2,2] -> [4]
[1,1,1,1] -> [1,1,2] -> [1,2,1] -> [1,3]   -> [2,2] -> [3,1] -> [4]
[1,1,1,1] -> [1,1,2] -> [1,2,1] -> [1,3]   -> [3,1] -> [4]
[1,1,1,1] -> [1,1,2] -> [1,2,1] -> [1,3]   -> [4]
[1,1,1,1] -> [1,1,2] -> [1,3]   -> [3,1]   -> [4]
[1,1,1,1] -> [1,1,2] -> [1,3]   -> [2,2]   -> [4]
[1,1,1,1] -> [1,1,2] -> [1,3]   -> [2,2]   -> [3,1] -> [4]

I'm trying to figure out if a brute force implementation of this, that tries all possible ways grows polynomially or exponentially in N.

I'm thinking it's polynomial, since the number of ways seems like it cannot exceed the sum of the squares from 1 to N. However, I can't say for sure that I didn't miss something.

I would appreciate independent confirmation of this, an equation showing exactly how the number of ways grows with N would be an ideal answer.

Edit: I've added all ways for N = 3 and N = 4. I'm thinking I got all of them for N = 4.

Edit #3: Replaced all instances of "marbles" with elements, which is easier to associate with being able to determine which ones to move. Also to clarify, when for example 5 elements are moved, which 5 doesn't matter, as for a given group of elements, the same 5 will always be picked.

Answer 1

Given $n \ge 2$ piles of which all but the first have size $1$, there are at least $n-1$ ways to reduce this to $n-1$ piles of which all but the first have size $1$: move a single marble from pile $i \in \{2,3,\ldots,n\}$ to pile $i-1$, then to pile $i-2$, and so on until it reaches pile $1$. Recursing on this gives $f(n)\ge (n-1)!$, or $\log f(n) \in \Omega(n \log n)$.

A better lower bound is obtained by restricting attention to moves from the last pile. If all moves are from the last pile, then there are $2^{k−1}$ ways to empty the last pile, given that it initially contains $k$ elements. The last pile will contain $1$ element, then $2$, then $3$, etc., up to $n−1$. The total number of ways must therefore satisfy $\log_2 f(n) \ge 0 + 1 + \cdots + (n−3) + (n−2) = \frac{1}{2}(n−1)(n−2)$. This proves that $\log f(n) \in \Omega(n^2)$.

This is the best lower bound that seems obvious; it's interesting to wonder whether combining these two approaches gives another increase. But in any case, $f(n)$ is certainly (super-)exponential, not polynomial.

An exact enumeration for $f(n)$ gives the sequence $$1,1,3,25,643,61193,26460895,63090093973,\ldots$$ Computing the sequence as far as $f(22)\approx1.21\times 10^{164}$, it appears to be growing as $e^{\alpha n^2 \log n}$, where $\alpha$ is in the neighborhood of $0.25$.

Answer 2

Note that each configuration of piles is a composition of the number $N$, so there will be exactly $2^{N-1}$ such configurations. Consider a directed graph with each configuration as a vertex and an edge from vertex $p$ to vertex $q$ if we can move from configuration $p$ to configuration $q$ in one step. The question now is to find the number of directed paths between two given vertices (note that the graph is acyclic as with each movement, the composition moves to a lexicographically higher composition).

If there are $k_i$ elements in pile $i$, then the number of possible ways to move elements from pile $i$ to pile $i-1$ is $k_i$. So total number of movements possible is $\sum_{i=2}^n k_i = N-k_1$. So, if a configuration has $k_1$ elements in its first pile, then the degree of corresponding vertex in the graph is $N-k_1 \leq N-1$. So a good upper bound for the problem would be number of paths in a (regular) directed acyclic graph where degree of each vertex is $N-1$.

We can get a rough upper bound by observing that the maximum path length is $N(N-1)/2$ (can show this in multiple ways, in particular, we can use the lexicographic argument mentioned above). At each vertex we have a choice of going to at most $N-1$ adjacent vertices and we can repeat this process at most $N(N-1)/2$ times before we reach the target vertex. This gives an upper bound, $f(N) \leq (N-1)^{N(N-1)/2}$ or $log f(N) \in O(N^2 log N)$.