32
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Order doesnt matter does it? $\endgroup$ – Asimov Sep 10 '14 at 15:43
  • 1
    $\begingroup$ You can derive a simple recurrence formula in the case without order, that if $f(r,s,n)$ is the number of ways of writing $n$ as a sum of $s$ integers between $1$ and $r$, then $f(r,s,n)=f(r-1,s,n)+f(r,s-1,n-r)$ - the first case being those sums which don't involve the number $r$, and the second being the case where there is at least one $r$. $\endgroup$ – Mark Bennet Sep 10 '14 at 15:51
  • 3
    $\begingroup$ By the way, as a programmer, I see this as a difficult variation of a typical "fencepole" problem. If you want 100 numbers that add to 700, all you do is randomly position 99 "fenceposts" on the run from 0 to 700 .. right? It's trivial. This is much harder, as you have to sort of pull them along like venetian blind slats, with a max and minimum gap. $\endgroup$ – Fattie Sep 10 '14 at 16:19
  • $\begingroup$ Using the language of compositions, what you want is the number of $A$-restricted compositions of 700 into 100 parts with $A=\{1,2,\ldots,10\}$. $\endgroup$ – Semiclassical Sep 10 '14 at 16:23
  • $\begingroup$ @semiclassical - magnificent! Do you know, what is the count of the A-restricted compositions of 700 into 100 parts with A=1..10?? :) $\endgroup$ – Fattie Sep 10 '14 at 16:24
46
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Great answer. Just two minor remarks: personally I would not omit parentheses in expressions of the form $\left(\sum_ja_jx^{cj}\right)\left(\sum_kb_kx^k\right)$ (or alternatively write them $\sum_j\sum_ka_jb_kx^{cj+k}$), and I would rewrite $\binom{k+99}k$ as $\binom{k+99}{99}$. But things are correct as written. $\endgroup$ – Marc van Leeuwen Sep 11 '14 at 9:54
  • $\begingroup$ @MarcvanLeeuwen: the parentheses seems to be a stylistic preference since I don't think there is much confusion and I was thinking of combining the sums. As for $\binom{k+99}{k}$ vs $\binom{k+99}{99}$, it is true that for non-negative, integer $k$ they are the same (so who cares?), however, for integer $k\lt-99$, they are different: $\binom{k+99}{k}=0$ whereas $\binom{k+99}{99}=-\binom{-k-1}{99}$ which is not $0$. It is sometimes useful to use, $$\sum_{j=0}^{60}(-1)^j\binom{100}{j}\binom{699-10j}{600-10j}=\sum_{j\in\mathbb{Z}}(-1)^j\binom{100}{j}\binom{699-10j}{600-10j}$$ $\endgroup$ – robjohn Sep 11 '14 at 21:46
22
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ oeis.org/A037306 seems to have some pointers. $\endgroup$ – mvw Sep 10 '14 at 16:48
  • $\begingroup$ If someone can provide a better way to format that 92-digit number, please do! $\endgroup$ – Semiclassical Sep 10 '14 at 16:54
  • $\begingroup$ What does the zero in $\{x,0,700\}$ (Wolfram Alpha notation) show? $\endgroup$ – user26486 Sep 10 '14 at 18:12
  • $\begingroup$ @mathh: It means that we're expanding about $x=0$ (rather than, say, $x=1$). $\endgroup$ – Semiclassical Sep 10 '14 at 18:17
  • $\begingroup$ @Semiclassical I have no knowledge about Taylor series (or anything similar) so far (I assume the zero is related to them). Is it true that when working with generating functions we can always simply write it as $\{x,0,k\}$ after the generating function, where $k$ is the coefficient we're searching for? $\endgroup$ – user26486 Sep 10 '14 at 19:09
16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for this cute alternative estimation. $\endgroup$ – mvw Sep 10 '14 at 17:06
  • $\begingroup$ @Semiclassical: Thanks, I was using the wrong standard deviation. I think it's fixed now. $\endgroup$ – mjqxxxx Sep 10 '14 at 17:43
  • $\begingroup$ @mvw: By $\mu_0$ I'm referring to the mean of the candidate values, not the mean of the actually selected values. $\endgroup$ – mjqxxxx Sep 10 '14 at 18:01
  • $\begingroup$ That's nice insight. $\endgroup$ – Felix Marin Sep 10 '14 at 22:02
  • $\begingroup$ Note: $\mu_0 = \left(\sum_{i=1}^{10}i\right)/ 10$, $\sigma_0 =\sqrt{\left(\sum_{i=1}^{10}(i-\mu_0)^2\right)/10}$. $\endgroup$ – mvw Sep 10 '14 at 23:26
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ hell - I'd have to really think about that! $\endgroup$ – Fattie Sep 10 '14 at 16:40
  • $\begingroup$ WolframAlpha gives a result of roughly $1.2\times 10^{92}$. Not sure whether that's a matter of Excel/WA breaking down or a typo in one of our implementations. $\endgroup$ – Semiclassical Sep 10 '14 at 16:49
  • $\begingroup$ @Semiclassical: I would guess it is Excel numerics, but am surprised the discrepancy is that large. $\endgroup$ – Ross Millikan Sep 10 '14 at 16:54
  • $\begingroup$ Aye. A 20% discrepancy would make sense for an approximation, but not for a direct count. $\endgroup$ – Semiclassical Sep 10 '14 at 16:56
  • 2
    $\begingroup$ I think you may just be looking in the wrong place… your result is the correct number of ways to make $701$ from a list of one hundred numbers in $\{1,2,\ldots,10\}$. $\endgroup$ – mjqxxxx Sep 10 '14 at 19:53
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Wow. I bet, this would help generalise the problem, too. $\endgroup$ – Fattie Sep 11 '14 at 8:09
  • $\begingroup$ Compared to the approach by robjohn, I'm don't see any insight that is gained by the use of contour integrals (rather the contrary). $\endgroup$ – Marc van Leeuwen Sep 11 '14 at 9:58
  • $\begingroup$ Marc ... uh, obviously! :-) Thanks for that; I'm trying to make sense of what is different, natty, solid, etc! $\endgroup$ – Fattie Sep 11 '14 at 14:10
  • $\begingroup$ @JoeBlow It's true. It lets you to set a general formula if you want. It avoids 'intermediate steps' that involve "counting" which is the most difficult situation. It's straightforward. Maybe, it takes a little bit to realize that. Thanks. $\endgroup$ – Felix Marin Sep 11 '14 at 18:08
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ It is a valid combinatorics problem. $\endgroup$ – mvw Sep 10 '14 at 16:46
  • $\begingroup$ I wont deny it. I just though that the OP wouldn't be interested in the generating function solution. My bad if it is not the case. $\endgroup$ – PenasRaul Sep 10 '14 at 16:53
  • $\begingroup$ +1 Have you tried just entering the recurrence and conditions into Mathematica. That probably gives the answer and the programming is minimal. Too pressed for time right now to try it! $\endgroup$ – almagest Sep 11 '14 at 4:23
  • 1
    $\begingroup$ I can absolutely assure you that very few top software engineers, can do, the math on this page :-) $\endgroup$ – Fattie Sep 11 '14 at 8:10

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.