How many numbers in an interval given a rule

Question

The question is:

How many numbers can we make from 0-9 that are between 100,000 and 999,999 and also the sum of there digits is 27, given that repetition is allowed.

What I understood is that given this interval [100000,999999], how many numbers in this interval such that the sum of there digits is exactly 27.

Answer 1

Generating Functions

Overview

I find the analytical method to solving this still probably requires the use of a computer, but I think it is still nice to demonstrate, especially if it's a new concept to you.

The idea is that you create a function such that its power series (its polynomial form, Taylor expansion, etc.) gives you the sequence you want in its coefficients. For instance, suppose you wanted to find the number of ways to pick $k$ out of $4$ objects, commonly known as $\binom{4}{k}$. The sequence for $k=0$, $1$, etc. gives ${1,4,6,4,1}$, which can be found by doing

$$ (x+1)^4 = \color{blue}1x^4 + \color{blue}4x^3 + \color{blue}6x^2 + \color{blue}4x^2 + \color{blue}1 $$

To see why this works, think about how you distribute each factor of $(x+1)^4$. For each factor, you have to make a selection for either the $x$ term or the $1$ term, and all four of your selections are multiplied together. The power of $x$ tells you how many $x$'s you've chosen. The coefficient is the number of ways this can be done!

See how $6x^2$ is obtained: $$ (\color{red}x+1) \qquad (\color{red}x+1) \qquad (\color{red}x+1) \qquad (x+\color{red}1) \qquad (x+\color{red}1) \qquad (x+\color{red}1)\\ (\color{red}x+1) \qquad (x+\color{red}1) \qquad (x+\color{red}1) \qquad (\color{red}x+1) \qquad (\color{red}x+1) \qquad (x+\color{red}1)\\ (x+\color{red}1) \qquad (\color{red}x+1) \qquad (x+\color{red}1) \qquad (\color{red}x+1) \qquad (x+\color{red}1) \qquad (\color{red}x+1)\\ (x+\color{red}1) \qquad (x+\color{red}1) \qquad (\color{red}x+1) \qquad (x+\color{red}1) \qquad (\color{red}x+1) \qquad (\color{red}x+1) $$

Notice that while you could substitute a value for $x$, you don't have to. The variable here serves no purpose aside from keeping track of the number of times it is multiplied. A very strange concept, as people are generally taught that variables always represented something!

So this $(x+1)^4$ is called the generating function of that ${1,4,6,4,1}$ sequence. This is a very powerful tool in the field of combinatorics and intimately connects it to algebra, calculus, and analysis, which you typically don't imagine as being related in any way when you first dabble in the field.

Application

Now let's tackle the problem at hand. Each digit can be from $0$ to $9$, so we build our first term to represent all of those choices:

$$ x^9 + x^8 + x^7 + x^6 + \cdots + x^2 + x^1 + x^0 = \frac{x^{10}-1}{x-1} $$

Notice that we always have $6$ digits. Therefore, we need to make this choice $6$ times. We raise this expression to a power of $6$.

$$ \left(\frac{x^{10}-1}{x-1}\right)^6 $$

Since the sum of our digits is $27$, we need to find the coefficient of $x^{27}$. (Think about why this works!)

Here is the full series and here is the value of just the coefficient of $x^{27}$.

But wait a minute, you may notice that the answer is larger than what you obtained! This is because we also counted numbers like $000999$, which violates your rule of the number being between $100000$ and $999999$. That's okay, it's very easy to fix the overcounting. Just subtract the coefficient of $x^{27}$ of $$ \left(\frac{x^{10}-1}{x-1}\right)^\color{red}5 $$ Once again, try to see how this accounts for all of the overcounted cases!

$$ [x^{27}]\left(\frac{x^{10}-1}{x-1}\right)^6 - [x^{27}]\left(\frac{x^{10}-1}{x-1}\right)^5 = 55252 - 4840 = 50412 $$

Answer 2

You’re looking for the number of ways to distribute $27$ balls into $6$ bins, where there must be at least one ball in the first bin and at most $9$ balls in any bin. Instead of enforcing the condition that there’s at least one ball in the first bin, let’s calculate the number $a_n$ of ways to distribute $27$ balls into $n$ bins and then form $a_6-a_5$ (since the arrangements that don’t have a ball in the first bin have $27$ balls distributed over the remaining $5$ bins).

There are $\binom{27+n-1}{n-1}$ ways to distribute $27$ balls over $n$ bins (see stars and bars). We have $n$ capacity constraints. There are $\binom n1=n$ ways to choose $1$ constraint to violate. Put $10$ balls in the chosen bin to violate the constraint, and then you can distribute the remaining $17$ balls into the $n$ bins in $\binom{17+n-1}{n-1}$ ways. So we need to subtract $n\binom{17+n-1}{n-1}$ distributions that violate a constraint. But that double-counts the distributions that violate two constraints, so we need to add those again. There are $\binom n2=\frac{n(n-1)}2$ ways to choose two constraints to violate. Put $10$ balls in each of the two chosen bins to violate the constraints, and then you can distribute the remaining $7$ balls into the $n$ bins in $\binom{7+n-1}{n-1}$ ways. It’s impossible to violate $3$ or more of the capacity constraints with $27$ balls, so there’s no more overcounting to correct. Thus in total we have

$$ a_n=\binom{27+n-1}{n-1}-n\binom{17+n-1}{n-1}+\frac{n(n-1)}2\binom{7+n-1}{n-1}\;, $$

and the desired count is

\begin{eqnarray}a_6-a_5 &=& \binom{27+6-1}{6-1}-6\binom{17+6-1}{6-1}+\frac{6(6-1)}2\binom{7+6-1}{6-1} \\ && -\left(\binom{27+5-1}{5-1}-5\binom{17+5-1}{5-1}+\frac{5(5-1)}2\binom{7+5-1}{5-1}\right) \\ &=&\binom{32}5-6\binom{22}5+15\binom{12}5-\binom{31}4+5\binom{21}4-10\binom{11}4 \\[5pt] &=& 201376-158004+11880-31465+29925-3300 \\[5pt] &=& 50412\;, \end{eqnarray}

in agreement with your result.

A more general and systematic form of this way of counting the nunber of ways to fulfill conditions by correcting for overcounting is known as inclusion–exclusion.