# Count the number of possible solutions

We want to choose 5 natural numbers from 1 to 13. (Non-repetitive numbers) And also sum of these numbers must be greater than 40 . How many solutions we have ? (using combination or any other operator that can help)

$x_1 + x_2 + x_3 + x_4 + x_5 \gt 40$ and $x_1,x_2,x_3,x_4,x_5\in\{1,2,3,\dots , 13\}$

• The answer is 280. – TorsionSquid Dec 2 '16 at 14:46
• Oh ! How you got this number ? – S.H.W Dec 2 '16 at 14:49
• Hint: first find how many combinations add up to less than 40. – TorsionSquid Dec 2 '16 at 14:51
• I can't do anything with your help. If you can write on paper and take photo. – S.H.W Dec 2 '16 at 14:55
• @S.H.W For finding out the number of solutions of $x_1+x_2+x_3+x_4+x_5 <= 40$, let $x_6>0$, then observe that $x_1+x_2+x_3+x_4+x_5 <= 40$ has solutions same as $x_1+x_2+x_3+x_4+x_5 +x_6= 40, x_6>0$. Now, since since you know the no. of solutions of <=40, you can deduce those of >40, since $x_is$ take only a limited range of values. – bat_of_doom Dec 2 '16 at 15:32

Here is an interpretation of @TorsionSquid's answer according to OPs comment.

We use the technique of generating functions to encode the number of ordered five-tuples $(x_1,x_2,x_3,x_4,x_5)$ of integer values with the constraints \begin{align*} 1\leq x_1<x_2<x_3<x_4<x_5\leq 13\qquad \text{and}\qquad x_1+x_2+x_3+x_4+x_5>40 \end{align*}

The integer values $i\in\{1,2,3,\ldots,13\}$ are encoded as power of a formal variable $z$ and the number of occurrences of $i$ is given as the coefficient of $z^i$.

The expression \begin{align*} 1+z^i \end{align*} represents the integer value $i$ which occurs either zero or one times. Whenever we select a five-tuple $(x_1,x_2,x_3,x_4,x_5)$ we select $5$ different values between $1$ and $13$ inclusively. This corresponds to five factors from the product \begin{align*} (1+z^1)(1+z^2)(1+z^3)\cdots(1+z^{13})=\prod_{i=1}^{13}(1+z^i) \end{align*}

We now introduce a new variable $t$ to mark the factors we choose. If we write \begin{align*} (1+tz^1)(1+tz^2)(1+tz^3)\cdots(1+tz^{13})=\prod_{i=1}^{13}(1+tz^i) \end{align*} we obtain a generating function $A(z,t)$ which can be expanded in powers of $t$ \begin{align*} A(z,t)=\sum_{i=0}^{13}A_i(z) t^i \end{align*} with $A_i(z)$ being polynomials in $z$.

It is convenient to use the coefficient of operator $[t^n]$ to denote the coefficient of $t^n$ in a series. Since we have to consider all five-tuples $(x_1,x_2,x_3,x_4,x_5)$ we take the coefficient of $t^5$ from $A(z,t)$.

We obtain \begin{align*} [t^5]A(z,t)=[t^5]\prod_{i=1}^{13}(1+tz^i)\tag{1} \end{align*} If we evaluate the RHS of (1) at $z=1$ we have all solutions of \begin{align*} x_1+x_2+x_3+x_4+x_5\qquad\text{with}\qquad 1\leq x_1<x_2<x_3<x_4<x_5\leq 13\tag{2} \end{align*} But we need only those solutions with $x_1+x_2+x_3+x_4+x_5>40$. This corresponds to the summands of $A(z,t)$ with powers of $z$ greater then $40$.

Here is a somewhat closer look at the situation with the help of Wolfram Alpha

Since we need $x_1+x_2+x_3+x_4+x_5>40$ we consider the coefficients of $z^n$ with $n>40$ only. The term $z^{15}$ is factored out in (3). So we need all summands in (3) starting with $52x^{26}$ up to $z^{40}$. In order to isolate these summands we can divide the polynomial (3) by $z^{41}$ and focus on the summands with non-negative powers. This means we subtract the principal part, which is the part with negative powers.

We obtain this way \begin{align*} z^{14}&+z^{13}+2z^{12}+3z^{11}+5z^{10}+7z^{9}+10z^{8}+13z^{7}\\ &\qquad+18z^{6}+22z^{5}+28z^{4}+33z^{3}+40z^{2}+45z^{1}+52 \end{align*} Finally evaluating this expression at $z=1$ counts the number of occurrences of (2) and gives \begin{align*} 1&+1+2+3+5+7+10+13\\ &\qquad+18+22+28+33+40+45+52=280 \end{align*}

• Thank you so much for your time. Your answer is complete and also complex! Can you provide some references for better understanding ? Because I'm a high school student. – S.H.W Dec 7 '16 at 12:18
• @S.H.W: I recommend Lectures on Integer Partitions which is a good starter for studying integer partitions based upon generating functions. Another accessible starter is Integer Partitions, by G. E. Andrews. (t.b.c) – Markus Scheuer Dec 7 '16 at 12:37
• @S.H.W: This is the little brother of his classic The Theory of Partitions. A great starter with respect to generating functions is Wilf's Generatingfunctionology. You might also find this answer useful. – Markus Scheuer Dec 7 '16 at 12:40

Take the coefficient of $t^5$ in

$$\prod_{i=1}^{13} (1+tx^i);$$

call it $p(x)$. Take $p(z)/z^{41}$, subtract the principal part, and plug in $z=1$. Voilá!

• Can you explain more ? What do you mean by $t$ and $z$ ? – S.H.W Dec 6 '16 at 19:09
• They're formal variables. – TorsionSquid Dec 6 '16 at 19:11
• Is it related to specific theory ? – S.H.W Dec 6 '16 at 19:14
• Frankly , I don't understand your answer. – S.H.W Dec 6 '16 at 19:15