I was going through Bouton's paper on Nim and its solution. In section 3, he calculates the probability that a random initial position is a winning position for the first player. There, he first counts the total number of positions:
... if each pile contains less than $2^n$ counters and if no pile is zero (i.e. if there are three piles), the possible number of different piles is $$\frac{2^{n-1}(2^{2n} - 1)}{3}$$
How did he get that expression? In my opinion, you have $2^n - 1$ choices for the number of counters in any pile ($1$ to $2^n$), and you have three piles with different numbers of counters, so the number of choices should be $$\binom{2^n - 1}{3} = \frac{(2^n - 1)(2^n - 2)(2^n - 3)}{3!}$$
Where am I going wrong?
When Bouton says "different piles," what he means is "different ways to choose the pile sizes." He is not implying that all the pile sizes are distinct. His wording is misleading.
To arrive at the answer he gave, you have to add in the possibilities of repeats: $$ \binom{2^n-1}3+ 2\binom{2^n-1}2+\binom{2^n-1}{1} $$ The middle summand counts where there are two distinct sizes (the factor of 2 is the choice for which size is repeated), and the right summand is when all sizes are the same. This simplifies to Bouton's answer.
There is a more direct way to arrive at Bouton's answer, which we will write in the form
$$ \frac{2^{2n-1}(2^{2n}-1)}{3}=\frac{(2^n+1)(2^n)(2^n-1)}{6}=\binom{2^n+1}3 $$
This is the number of ways to choose three distinct numbers $1\le n_1<n_2<n_3\le 2^n+1$. Given such a choice, consider the sequence of numbers $$ n_1,n_2-1,n_3-2 $$ Wheras the sequence $n_1,n_2,n_3$ is strictly increasing, so repeats aren't possible, the above sequence is only weakly increasing, so repeats are possible. Thus, applying the displayed transformation yields a list of three integers, each between $1$ and $2^{n-1}-1$, with repeats allowed, which exactly describes the nim positions Bouton is trying to count.
This transformation can be used more generally to show that size $k$ multi-subsets of an $n$-element set are in bijection with size $k$ subsets of an $(n+k-1)$-element set. Assuming that the two sets we are choosing from are respectively $\{1,2,\dots,n\}$ and $\{1,2,\dots,n+k-1\}$, the bijection is $$ \{x_1,x_2,\dots,x_k\}\mapsto \{x_1,x_2+1,\dots,x_k+k-1\}, $$ where $x_1,x_2,\dots,x_k$, is in weakly increasing order.