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

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.

-
From 1,1,1 I count 3 ways: 2,1 3; 1,2 2,1 3; 1,2 3. From 1,1,1,1 there's 2,1,1 and then 3 ways; 1,2,1 2,1,1 and 3 ways; 1,2,1 3,1 4; 1,2,1 1,3 then 4 ways; 1,1,2 2,2 then 2 ways; 1,1,2 1,2,1 then 8 ways; 1,1,2 1,3 then 4 ways; I count 25 ways. Looks very exponential to me. I wonder if it's oeis.org/A003024 –  Gerry Myerson Dec 31 '12 at 14:54
I've added all solutions for n = 3 and n = 4, and only left one full example. –  Nuclearman Dec 31 '12 at 15:29
@GerryMyerson: but that series doesn't have a term $8$. –  Ross Millikan Dec 31 '12 at 15:32
If you want the exact number of paths, you need to specify whether "move one from pile 3 to pile 1" and "move one from pile 2 to pile 1" (starting from $[1,1,1]$) count as two choices (since they're different choices) or just one (since they both lead to $[2,1]$). –  mjqxxxx Dec 31 '12 at 15:52
@mjqxxxx You cannot move from pile 3 to 1 since they're not consecutive –  barto Dec 31 '12 at 15:58

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$.

-
The thing is that I have a polynomial algorithm that determines exactly which marble(s) to move. So in the case of "[1,1,1] -> [1,2] -> [2,1] -> [3]", there is exactly 1 way this specific pattern of movement can be done, instead of 2 * 1. Perhaps I shouldn't have used marbles to illustrate the example. –  Nuclearman Dec 31 '12 at 15:55
@MC: Marbles are fine, just make sure they're "unlabeled" (I'm treating them that way here). Alternately, you could use chips or playing cards and stipulate that when $n$ cards are moved from a pile, it's the top $n$. This gives another way to see the factorial bound: starting with $n$ cards in $n$ piles, you can wind up with the cards in any of $(n-1)!$ orders on the first pile, implying at least $(n-1)!$ ways to get them piled up. –  mjqxxxx Dec 31 '12 at 16:23
Very true, however, order doesn't matter in this case, as both where the elements are removed from and where they are inserted to is calculated using a polynomial algorithm. Basically the "way" is described simply as the unique set of instructions required to move them. Using the remaining example, the way can be described as simply "[move 1 from 4, move 2 from 3, move 3 from 2, move 1 from 2]". So perhaps my terminology is bad. –  Nuclearman Dec 31 '12 at 16:40
@MC: You're missing the point here, I think. Your terminology is fine. There are at least factorially many ways to migrate all the (indistinguishable) marbles into the first pile. –  mjqxxxx Dec 31 '12 at 18:34
Hmmm, I suppose your right (upvoted), and that's basically what my concern was, that tosses out that possibility. –  Nuclearman Dec 31 '12 at 19:23

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)$.

-
That sounds a lot like the logic I used to determine that it was polynomial, and the bound of O(N^2 log n), was one of the possible bounds I came up with experimentally although it might have been for another aspect of the code. Neglecting the bit about composition, which is new. I'll wait a bit to see if anyone contests this answer before I set as the accepted one. Upvoted though. –  Nuclearman Dec 31 '12 at 18:18
@MC: This answer says it's not polynomial. –  mjqxxxx Dec 31 '12 at 18:33
Combining this upper bound with my lower bound gives $\log f(n)\in \Omega(n\log n) \cap O(n^2 \log n)$. –  mjqxxxx Dec 31 '12 at 18:46
... I was wondering about that exponent, probably should have asked. Well, that removes that possibility, although that was only intended to be a starting point for the algorithm. –  Nuclearman Dec 31 '12 at 19:25
You two with your bounds makes it rather difficult to pick a "best answer"... –  Nuclearman Dec 31 '12 at 19:28