0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The answer is 280. $\endgroup$ – TorsionSquid Dec 2 '16 at 14:46
  • $\begingroup$ Oh ! How you got this number ? $\endgroup$ – S.H.W Dec 2 '16 at 14:49
  • 1
    $\begingroup$ Hint: first find how many combinations add up to less than 40. $\endgroup$ – TorsionSquid Dec 2 '16 at 14:51
  • $\begingroup$ I can't do anything with your help. If you can write on paper and take photo. $\endgroup$ – S.H.W Dec 2 '16 at 14:55
  • $\begingroup$ @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. $\endgroup$ – bat_of_doom Dec 2 '16 at 15:32
2
+50
$\begingroup$

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

\begin{align*} [t^5]&A(z,t)=[t^5]\prod_{i=1}^{13}(1+tz^i)\\ &s=[t^5]\sum_{i=0}^{13}A_i(z) t^i =A_5(z)\\ &=t^5z^{15}\left(z^{40}+z^{39}+2z^{38}+3z^{37}+5z^{36}+7z^{35}+10z^{34}+13z^{33}\right.\\ &\qquad\qquad\qquad+18z^{32}+22z^{31}+28z^{30}+33z^{29}+40z^{28}+45z^{27}+52z^{26}\\ &\qquad\qquad\qquad+\cdots\\ &\qquad\qquad\qquad+18z^8+13z^7+10z^6+7z^5+5z^4+3z^3+2z^2+z+1)\tag{3} \end{align*}

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – S.H.W Dec 7 '16 at 12:18
  • $\begingroup$ @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) $\endgroup$ – Markus Scheuer Dec 7 '16 at 12:37
  • $\begingroup$ @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. $\endgroup$ – Markus Scheuer Dec 7 '16 at 12:40
1
$\begingroup$

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á!

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

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.