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

Question

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}$.

Answer 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)$.

Answer 2

For a calculation answer, I get about $1.21131 \cdot 10^{92}$ I just made an Excel sheet with rows labeled -9 through 100 and columns 1 through 100. The rows represent the number of ways to make that sum with the number of numbers $1$ through $10$ in the column heading. Under column 1,put $1$ in each row $1$ through $10$. Then in subsequent columns each cell is the sum of ten entries in the column to the left, from one above to ten above. The rows with negative numbers in them are there so I didn't have to cut off the early sums, like for a sum of $3$ from two numbers.

Here is the top corner of the sheet:
$$ \begin {array} {l l l l l } tot&1&2&3&4\\ \hline 1&1&&&\\2&1&1&0&0\\3&1&2&1&0\\4&1&3&3&1\\5&1&4&6&4\\6&1&5&10&10\\7&1&6&15&20\\8&1&7&21&35\\9&1&8&28&56\\10&1&9&36&84\\11&&10&45&120\\12&&9&55&165\\13&&8&63&220\\14&&7&69&282\\15&&6&73&348\\16&&5&75&415\\17&&4&75&480\\18&&3&73&540\\19&&2&69&592\\20&&1&63&633\\21&&0&55&660\\22&&0&45&670\\23&&0&36&660\\24&&0&28&633\\25&&0&21&592\\26&&0&15&540\\27&&0&10&480\\28&&0&6&415\\29&&0&3&348\\30&&0&1&282\\31&&0&0&220\\32&&0&0&165\\33&&0&0&120\\34&&0&0&84\\35&&0&0&56\\36&&0&0&35\\37&&0&0&20\\38&&0&0&10\\39&&0&0&4\\40&&0&0&1\\ \end {array} $$

Answer 3

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.

Answer 4

As this seems to be a programmer's problem, I will give you a sketch of the solution. For sake of completeness, I should advise you that this kind of problems should be posted in the correct stack exchange forum.

You certainly have been familiar with DP. So this problem should be solved in that manner. You should look to a certain function, namely $f(n, m)$ that gives you the number of ordered sequences of $n$ integers in $A = \{1, \cdots, 10\} $ that sum $m$. You want $f(100, 700)$.

You should know a recursive way of computing this, as any sequence $a_1, \cdots , a_n$ that sums $m$ leads bijectively to a smaller sequence $a_1, \cdots , a_{n-1}$ that sum $m-a_n$ So $$f(n, m) = \sum_{k \in A}^{ m - k \geq 0} f(n-1, m-k)$$

You should initialize your function in $f(n, n) = 1$ and $f(1, m) = 1$ for $m\in A$, $f(1, m)=0 $ for $ m> 10 $. And now is just a question of programming.

Answer 5

Note that the numbers being added together have mean $\mu_0=11/2$ and standard deviation $\sigma_0=\sqrt{33}/2$; by the central limit theorem, the distribution of the sum of $100$ such numbers is approximately a Gaussian with mean $\mu=100\mu_0 = 550$ and standard deviation $\sigma=10\sigma_0=5\sqrt{33}$. The continuous Gaussian distribution is $$ f(x,\mu,\sigma)=\frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right); $$ and to a first approximation you can ignore the correction from discreteness. So the number you want is roughly $$ N\approx 10^{100} \cdot f(700,550,5\sqrt{33})=\frac{10^{100}}{5\sqrt{33}\sqrt{2\pi}}\exp\left(-\frac{150^2}{1650}\right)\\ = \frac{10^{100}}{5\sqrt{66\pi}}e^{-150/11}\approx 1.66\times 10^{92}. $$ It is helpful to compare this to the computational result. A simple Python implementation is the following:

def N(x, n, cache={(0,0):1}):
   if x<0 or (n==0 and x>0): return 0
   if not cache.has_key((x,n)):
      cache[(x,n)] = sum([N(x-i, n-1) for i in xrange(1,11)])
   return cache[(x,n)]

Then N(700, 100) * 1.0 yields 1.2113063910758377e+92.

Answer 6

A066099 features a nice visual generation pattern for compositions of $n$ (listing them in reverse lexical order):

From Omar E. Pol, Sep 03 2013:       

-----------------------------------  ----------
n  j       Diagram   Composition j   Row length
-----------------------------------  ----------
.               _
1  1           |_|   1;              1
.             _ _
2  1         |  _|   2,              1
2  2         |_|_|   1, 1;           2
.           _ _ _
3  1       |    _|   3,              1
3  2       |  _|_|   2, 1,           2
3  3       | |  _|   1, 2,           2 
3  4       |_|_|_|   1, 1, 1;        3
.         _ _ _ _
4  1     |      _|   4,              1
4  2     |    _|_|   3, 1,           2
4  3     |   |  _|   2, 2,           2
4  4     |  _|_|_|   2, 1, 1,        3
4  5     | |    _|   1, 3,           2
4  6     | |  _|_|   1, 2, 1,        3
4  7     | | |  _|   1, 1, 2,        3
4  8     |_|_|_|_|   1, 1, 1, 1;     4
.

So we would need that diagramm for $n = 700$ and only those rows with $100$ summands and all summands from $\{1, \ldots, 10 \}$.

Pragmatic problem: There are $N = 2.63 \times 10^{210}$ compositions of $700$, according to WolframAlpha link.

Looking at the diagram one notices that $N(n)$ is resulting from the doubling (see step 3 of the algorithm below) and is thus simply $N(n) = 2^{N-1}$ (A000225) and in this case: $N(700) = 2^{699}$.

About the recursion involved:

1. The list of compositions for $n+1$ can be obtained, by using a copy of the list for $n$ first.
2. Then we put a column of $1$ elements to the left of that list.
3. Finally we put another copy of the list for $n$ on top, shifted one position left, aligning with the column of $1$ elements, and adding $1$ to each entry in the first column of the copy.

Side note: It is already interesting to see how the row lengths develop:

1
1 2
1 2 2 3
1 2 2 3 2 3 3 4
1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5

If we have $2^n$ terms, we find the next $2^n$ terms by copying the first $2^n$ terms plus $1$ each.

This leads to A063787 and is related to A000120 (binary weight of $n$). They are described as fractal sequences - deleting every other term gives the original series.

Answer 7

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ With $\ds{0 < a < 1}$:

\begin{align} &\color{#66f}{\large\sum_{k_{1}=1}^{10}\ldots\sum_{k_{100}=1}^{10} \delta_{k_{1}\ +\ \cdots\ +\ x_{100},700}} =\sum_{k_{1}=1}^{10}\ldots\sum_{k_{100}=1}^{10}\oint_{\verts{z}\ =\ a} {1 \over z^{-k_{1}\ -\ \cdots\ -\ k_{100}\ +\ 701}}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ a} {1 \over z^{701}}\,\pars{\sum_{k =1}^{10}z^{k}}^{100}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a}{1 \over z^{701}}\,\pars{z\,{z^{10} - 1 \over z - 1}}^{100} \,\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ a}{1 \over z^{601}}\, {\pars{1 - z^{10}}^{100} \over \pars{1 - z}^{100}}\,\,{\dd z \over 2\pi\ic} \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\pars{1} \\[3mm]&=\sum_{n = 0}^{100}\sum_{k = 0}^{\infty}\pars{-1}^{n + k}{100 \choose n} {-100 \choose k}\oint_{\verts{z}\ =\ a}{1 \over z^{601 - 10n - k}} \,{\dd z \over 2\pi\ic} \\[3mm]&=\sum_{n = 0}^{100}\sum_{k = 0}^{\infty}\pars{-1}^{n + k}{100 \choose n} \pars{-1}^{k}{k + 99 \choose 99}\delta_{10n + k,600} =\sum_{n = 0}^{100}\pars{-1}^{n}{100 \choose n}{699 - 10n \choose 99} \end{align}

Contributions to the sum are limited by $\quad\ds{0 \leq n \leq 100}\quad$ and $\quad\ds{99 \leq 699 - 10n}\quad$ which yield $\quad\ds{0 \leq n \leq 60}$:

$$ \color{#66f}{\large\sum_{k_{1}=1}^{10}\ldots\sum_{k_{100}=1}^{10} \delta_{k_{1}\ +\ \cdots\ +\ x_{100},700} =\sum_{n = 0}^{60}\pars{-1}^{n}{100 \choose n}{699 - 10n \choose 99}} $$ which is $\ds{\pars{~\mbox{see expression}\ \pars{1}~}}$ equal to $\ds{\bracks{z^{600}}\pars{1 - z^{10} \over 1 - z}^{100}}$.

It leads to the value \begin{align}& {\tt 1.211306391075837746814517416259229640857139892912601984348493171327624} \\ &{\tt 03014516376282321342995 \times 10^{92}} \end{align}

It is found with W & A.