What is the "standard balls-in-boxes" argument?

Question

I came across a question recently that I did not know how to do. It included a solution, and basically the question boiled down to how many positive integers are there with 10 or less digits such that the sum of its digits is equal to 9? The solution then finished by saying the answer with simply a combination with n=18 and r=9 (=48620) by "a standard balls-in-boxes argument."

I looked up arguments that sounded like this one, and did not understand them or how they related to this problem.

What I have come to ask you guys is, generally, what does that argument entail and how does it relate to the specific type of problem?

Answer 1

This is what is often called a Stars and Bars argument. Please see the linked Wikipedia article. You will also find many hits on MSE.

The argument applies only in a limited way to sums of digits problems. But it works with this one.

The Stars and Bars technique counts the number of ways $n$ indistinguishable balls can be put into $k$ distinguishable boxes. Equivalently, it counts the number of solutions of the equation $x_1+x_2+\cdots+x_k=n$ in non-negative integers.

The Stars and Bars technique shows that the number of solutions is given by $\binom{n+k-1}{k-1}$, or equivalently $\binom{n+k-1}{n}$.

To construct a $10$ or fewer digit number with digit sum $9$, let the digits from left to right be $x_1$ to $x_{10}$. Then our number has digit sum $9$ if and only if $x_1+\cdots+x_{10}=9$. So we have a Stars and Bars problem with $n=9$ and $k=10$.

Unfortunately, this simple technique does not work for, say, digit sum $29$. True, Stars and Bars lets us count the number of solutions of $x_1+x_2+\cdots+x_{10}=29$ in non-negative integers. But many of these solutions involve some $x_i\gt 9$, and these do not give us decimal digits.

Answer 2

This is the problem of finding the number of weak compositions of size $k$ of a positive integer $n$. When $n = 9$ (the sum of digits) and $k = 10$, it is $\binom{n + k - 1}{k - 1} = \binom{9 + 10 - 1}{10 - 1}$.

Let me now explain the idea of (1) partition, (2) composition and (3) weak composition of a positive integer. A partition of a positive integer $n$ is a way of writing it as a sum of positive integers, where the order of the summands does not matter. If the order matters then we have a composition. A weak composition is the one in which we can use a zero as a summand. If there is no restriction on the number of summands then the number of weak compositions is infinity.

Let us now consider the number of weak compositions of a positive integer $n$. Represent $n$ as a sequence of 1s with a gap between them. Each gap can be filled with either a plus sign or a comma. A comma means "1,1,1" is $3$ while a plus is the usual addition. Since there are $n - 1$ gaps between $n$ 1s, with each gap having a two choices, there are $2^{n-1}$ compositions of $n$.

If we have to count the number of compositions in $k$ parts, only plus signs are allowed in the gaps and that too only $k - 1$ of them. An empty gap is interpreted as a comma in the sense of the above paragraph. Therefore, the number of compositions of $n$ into $k$ parts is \begin{equation} \binom{n - 1}{k - 1} \end{equation}

Now comes the trick for a weak composition. Consider a composition of the number $n + k$ into $k$ parts. Let it be expressed as \begin{equation} d_1 + d_2 + \cdots + d_k = n + k \end{equation} where $1 \le d_i \le 9$ for all $i$. We can write it as \begin{equation} (d_1 - 1) + (d_2 - 1) + \cdots + (d_k - 1) = n \end{equation} If $e_i = d_i - 1$ then \begin{equation} e_1 + e_2 + \cdots + e_k = n \end{equation} where $0 \le e_1 \le 9$. Thus, the number of weak compositions of $n$ of size $k$ is equal to the number of compositions of $n + k$ of size $k$, which is, \begin{equation} \binom{n + k - 1}{k - 1} \end{equation}