How many lists of 100 numbers (1 to 10 only) add to 700?

Each number is from one to ten inclusive only. There are $100$ numbers in the ordered list. The total must be $700$.

How many such lists?

Note: if, as it happens, this is one of those math problems where only an approximation is known, that would be great. (My guess is it's not "that" big, around $10^{20}$ maybe?)

Thank you!!

So, to be clear say you have a dice with sides labelled $1$-$10$. You roll it $100$ times, once every $10$ seconds in order. The result is, if you will, a specific array of $100$ numbers (each being $1$-$10$), each position labelled $1$ to $100$. The array must then add to $700$; how many such arrays??

Just to be absolutely clear, I believe the total of "all" such lists (so, there is no requirement to add to $700$; it can add to anything), is indeed, simply $1$ googol, ie, $10^{100}$.

Solution 1:

Generating Function Approach

The coefficient of $x^{700}$ in $(x+x^2+x^3+\dots+x^{10})^{100}$ is the number you are looking for. This is because each choice of one of the summands in each term gives a unique choice for one of the $100$ numbers.

We can get an easier form by first noticing that the coefficient of $x^{700}$ above is the coefficient of $x^{600}$ in $(1+x+x^2+\dots+x^9)^{100}$ and that $$ \begin{align} (1+x+x^2+\dots+x^9)^{100} &=\left(\frac{1-x^{10}}{1-x}\right)^{100}\\ &=\sum_{j=0}^{100}\binom{100}{j}\left(-x^{10}\right)^j\sum_{k=0}^\infty\binom{-100}{k}(-x)^k\\ &=\sum_{j=0}^{100}\binom{100}{j}\left(-x^{10}\right)^j\sum_{k=0}^\infty\binom{k+99}{k}x^k\tag{1} \end{align} $$ Now we just need to add up the contributions to $x^{600}$ in $(1)$ which comes from the terms where $k=600-10j$. Thus, the coefficient of $x^{600}$ in $(1)$ is $$ \sum_{j=0}^{60}(-1)^j\binom{100}{j}\binom{699-10j}{600-10j}\tag{2} $$ which comes to $$ 12113063910758377468145174162592296408571398929\\1260198434849317132762403014516376282321342995 $$ or approximately $1.2113063910758377468\times10^{92}$

Inclusion-Exclusion Approach

To compute the number of ways for $100$ non-negative numbers to sum to $600$ we can use the usual stars and bars approach which gives $$ \binom{699}{600} $$ How many of these ways include a number $10$ or bigger? We can try to count this by sticking a chunk of $10$ stars into one of the $100$ places and counting how many ways to sum $100$ numbers to $600-10$. This gives $$ \binom{100}{1}\binom{689}{590} $$ but this counts twice the ways that include two numbers $10$ or bigger. To count these, we stick $2$ chunks of $10$ stars into two of the $100$ plaes and count how many ways to sum $100$ numbers to $600-20$. This gives $$ \binom{100}{2}\binom{679}{580} $$ We can apply Inclusion-Exclusion to get the number of ways for $100$ non-negative numbers less than $10$ to sum to $700$ to be $$ \sum_{j=0}^{60}(-1)^j\binom{100}{j}\binom{699-10j}{600-10j} $$ which is the same as gotten in $(2)$.

Solution 2:

In the language of compositions, what you want are the number of $A$-restricted compositions of $n=700$ into $k=100$ parts where $A=\{1,2,\ldots,a\}$ with $a=10$. While I don't know a closed-form for this number, one can express such counting succinctly using formal power series. To represent our set $A$ of allowed terms, we use the formal polynomial $f_{a}(x)=\sum\limits_{j=1}^{a} x^j = \dfrac{x-x^{a+1}}{1-x}$. If we square this, then the coefficient of a term $x^n$ will represent the number of ways in which two integers in $A$ can add to a total of $n$. This gives us the following result:

The number of $A$-restricted compositions, with $A=\{1,2,\ldots a\}$, of $n$ into $k$ parts is the $n$th coefficient of $f_{10}(x)^k$, which we can express as $[x^n]\left(\dfrac{x-x^{a+1}}{1-x}\right)^k.$

Thus in the case at hand what we want to find (or at least estimate) is $\boxed{\displaystyle\left[x^{700}\right]\left(\dfrac{x-x^{11}}{1-x}\right)^{100}}$. Amazingly, this can be pulled off rather easily by WolframAlpha, yielding the rather impressive result of $$ \boxed{ \begin{align} 12113063910758377468145174162592296408571398929 &\\ 1260198434849317132762403014516376282321342995 &\approx 1.2 \times 10^{92} \end{align} } $$ For approximations, I suggest perusing Sedgwick and Flajolet's Analytic Combinatorics which is available for download on the book site. I may dig into there myself to see if anything is known or can be estimated about such numbers.