Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Quoting:

We define $f(d, n)$ to be the number of integers of up to $d$ decimal digits with digit sum less than or equal to $n$. It can be seen that this function is given by the formula $$f(d,n)=\sum_{i=0}^d(-1)^i\binom{d}i\binom{n+d-10i}d\;.$$

How is this derived? And surely the function requires binomials with negative arguments?

share|improve this question
    
Please edit your question to make it self-contained, and please edit the title to make it more informative. –  Gerry Myerson Apr 25 '12 at 13:03
    
Edited to reflect this –  sam keays Apr 25 '12 at 14:57

1 Answer 1

The number of solutions of $x_1+x_2+\ldots+x_d=m$ in non-negative integers is $\binom{m+d-1}m$. (If this is not familiar, see this article.) If we could use arbitrarily large digits, not just $0,\dots,9$, this would be the number of non-negative integers of at most $d$ digits with digit sum $m$. Since we want to allow all digits sums from $0$ through $n$, we want $$\sum_{m=0}^n\binom{m+d-1}m=\sum_{m=0}^n\binom{m+d-1}{d-1}=\binom{n+d}d\tag{1}$$ by a standard binomial coefficient identity; and since $\binom{d}0=1$, $(1)$ is the $i=0$ term of the sum

$$f(d,n)=\sum_{i=0}^d(-1)^i\binom{d}i\binom{n+d-10i}d\;.\tag{2}$$

The other terms of $(2)$ correct for the inclusion in $(1)$ of numerals using digits greater than $9$, i.e., for the inclusion of solutions to $x_1+\ldots+x_d=m$ with some $x_k>9$. This is a standard inclusion-exclusion argument, but I’ve included some of the details below.

To start, fix $k$ with $1\le k\le d$. There is a natural bijection between solutions in non-negative integers to $x_1+\ldots+x_d=m$ with $x_k\ge 10$ and solutions in non-negative integers to $x_1+\ldots+x_d=m-10$. Arguing as before, and ignoring the possibility that some $x_i$ may exceed $9$, we get $\binom{(m-10)+d-1}{m-10}$ such solutions, and summing over $m\le n$ yields a total of $\binom{n+d-10}d$ solutions counted in $(1)$ but having $x_k\ge 10$. Moreover, there are $\binom{d}1=d$ possible values of $k$, each of which provides $\binom{n+d-10}d$ ‘bad’ solutions, so we must subtract $\binom{d}1\binom{n+d-10}d$ from the first approximation in $(1)$. Our second approximation to the desired number is therefore $$\binom{d}0\binom{n+d}d-\binom{d}1\binom{n+d-10}d\;.\tag{3}$$

Unfortunately, $(3)$ overcorrects: some of the ‘bad’ solutions counted in $(1)$ exceed $9$ in two terms and have been removed twice in $(2)$, so they have to be added back in. The reasoning is as before. For any pair of indices $i,k$ with $i\ne k$ and any sum $m$, there is a natural bijection between solutions in non-negative integers to $x_1+\ldots+x_d=m$ with $x_i,x_k\ge 10$ and solutions in non-negative integers to $x_1+\ldots+x_d=m-2\cdot10$. The total correction for this pair of indices is therefore $\binom{n+d-2\cdot10}d$, and there are $\binom{d}2$ such pairs of indices, so the overall correction is $\binom{d}2\binom{n+d-2\cdot 10}d$, giving a third approximation of $$\binom{d}0\binom{n+d}d-\binom{d}1\binom{n+d-10}d+\binom{d}2\binom{n+d-2\cdot 10}d\;.\tag{4}$$

This again overcorrects, because some of the original solutions are ‘bad’ in three places and got added back into $(4)$ for two pairs of indices, so we have to subtract another correction. When all of the corrections have been made, we’re left with $(2)$, as desired.

The binomial coefficients with negative upper number are evidently defined to be $0$ for purposes of this calculation, so they cause no trouble.

Added: This is not the usual definition, so the notation is a bit sloppy: the usual definition, good for arbitrary complex $z$ and non-negative integer $k$, is $$\binom{z}k=\frac{z^{\underline k}}{k!}\;,$$ where $z^{\underline k}$ is the falling $k$ power of $z$, $z(z-1)(z-2)\dots(z-k+1)$.

share|improve this answer
    
But the usual definition of $x\choose n$ is the quotient of $x(x-1)(x-2)\cdots(x-n+1)$ and $n!$, whether $x$ is positive, negative, integer, decimal, real, complex, whatever. –  Gerry Myerson Apr 25 '12 at 22:37
    
Thanks, that's actually not so difficult to understand. For some reason I just find it often hard to visualise the binomial coefficient and what it does, there often feels something algebraically counter-intuitive about it. –  sam keays Apr 26 '12 at 12:19
    
@Gerry: Yes, and I really should make more of a point of that. Done now. –  Brian M. Scott Apr 26 '12 at 13:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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