1
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So can we say in general that it doesnt work for $x>=29$ as $9.3=27+1$ $\endgroup$ – Archis Welankar Jan 4 '16 at 4:42
  • $\begingroup$ It already does not work for sum of digits equal to $10$, for among the solutions of $x_1+\cdots+x_{10}=10$ in non-negative integers, we have the solutions $(10,0,0,\dots,0)$, $(0,10,0,\dots,0)$ and so on. These are counted by the Stars and Bars formula, but do not correspond to $10$-digit numbers. For this example we can "fix" the answer given to us by Stars and Bars by just subtracting the $10$ "bad" solutions. With digit sum $29$, the "fix" is a lot more complicated. $\endgroup$ – André Nicolas Jan 4 '16 at 4:47
  • $\begingroup$ No but whats confusing me is that we can have like this $a+b+c+d...+g=30$ and you have solutions so why it doesnt work after $29$ sorry for being unaware uf theee exists such fact $\endgroup$ – Archis Welankar Jan 4 '16 at 5:09
  • 1
    $\begingroup$ I used digit sum $29$ as an example of a situation where simple Stars and Bars does not work. In a comment I mentioned it already does not work for digit sum $10$. In fact it only works with no modification for digit sum $k$, where $k\le 9$. This is because if we look at any solution of $x_1+\cdots+x_{10}=k\le 9$ in non-negative integers, then the $x_i$ must all be $\le k\le 9$, that is, the $x_i$ must be digits. However, if $k\gt 9$, some of the solutions to $x_1+\cdots +x_{10}=k$ can involve numbers $\gt 9$, that is, non-digits. (More) $\endgroup$ – André Nicolas Jan 4 '16 at 5:17
  • 1
    $\begingroup$ (More) So there is no longer the simple relationship between $10$ or fewer digit numbers with digit sum $k$ and solutions of the equation $x_1+\cdots+x_{10}=k$. $\endgroup$ – André Nicolas Jan 4 '16 at 5:19
2
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.