How many combination of $3$ integers reach given number?

Question

I have 3 numbers

$M=10$

$N=5$

$I=2$

Suppose I have been given number $R$ as input that is equal to $40$

so in how many ways these $3$ numbers arrange them selves to reach $40$

e.g.

$$10+10+10+10$$

$$10+5+5+5+5+10$$

$$5+5+5+5+5+5+5+5$$

etc.

Kow can you give me formulae supposing I pass any number e.g. $30$ etc.

What are formulae to calculate the number of these $3$ integers combinations to given number?

1 MORE EXAMPLE?

suppose number is 7

combinationare 2 these are

5+2

2+5

Answer 1

Here is a slightly different way to calculate the number of compositions of $40$ generated from $2,5$ and $10$.

Since a selection of $2,5$ or $10$ can be represented as \begin{align*} x^2+x^5+x^{10} \end{align*} we start with the ordinary generating function \begin{align*} \frac{1}{1-\left(x^2+x^5+x^{10}\right)}=\sum_{j=0}^\infty\left(x^2+x^5+x^{10}\right)^j \end{align*} providing the number of occurrences of zero or more selections of $2,5$ or $10$.

We are interested in the coefficient of $x^{40}$ and expand the series accordingly. It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.

We obtain \begin{align*} [x^{40}]&\frac{1}{1-\left(x^2+x^5+x^{10}\right)}\\ &=[x^{40}]\sum_{j=0}^\infty\left(x^2+x^5+x^{10}\right)^j\\ &=[x^{40}]\sum_{j=0}^\infty x^{2j}\left(1+x^3+x^7\right)^j\\ &=\sum_{j=0}^{20}[x^{40-2j}]\sum_{k=0}^{j}\binom{j}{k}\left(x^3+x^8\right)^k\tag{1}\\ &=\sum_{j=0}^{20}[x^{40-2j}]\sum_{k=0}^{j}\binom{j}{k}x^{3k}\left(1+x^5\right)^k\\ &=\sum_{0\leq k\leq j\leq 20}\binom{j}{k}[x^{40-2j-3k}]\sum_{l=0}^{k}\binom{k}{l}x^{5l}\qquad\qquad 2j+3k\leq 40\tag{2}\\ &=\sum_{0\leq l\leq k\leq j\leq 20}\binom{j}{k}\binom{k}{l}\quad\qquad\qquad\qquad\qquad2j+3k+5l=40\tag{3} \end{align*}

Comment:

• In (1) we use the linearity of the coefficient of operator and the rule \begin{align*} [x^{n-m}]A(x)=[x^n]x^mA(x) \end{align*}

• In (2) we use another notation for summation and respect that the power $40-2j-3k$ is non-negative. In order to get a coefficient with a contribution $>0$ we have to choose $40-2j-3k=5l$. This is done in the next step.

In (3) we see that for each triple $(j,k,l)$ which fulfills

\begin{align*} &0\leq l\leq k\leq j\leq 20\\ &2j+3k+5l=40 \end{align*}

we have a contribution of $\binom{j}{k}\binom{k}{l}$.

These triples are

\begin{array}{rrrrr} j&k&l&\binom{j}{k}\binom{k}{l}&\sum\\ \hline 4&4&4&1&1\\ 5&5&3&10&11\\ 6&6&2&15&26\\ 7&7&1&7&33\\ 8&3&3&56&89\\ 8&8&0&1&90\\ 9&4&2&756&846\\ 10&5&1&1260&2106\\ 11&6&0&462&2568\\ 12&2&2&66&2634\\ 13&3&1&858&3492\\ 14&4&0&1001&4493\\ 16&1&1&16&4509\\ 17&2&0&36&4645\\ 20&0&0&1&\color{blue}{4646}\\ \end{array}

resulting finally in

\begin{align*} [x^{40}]&\frac{1}{1-\left(x^2+x^5+x^{10}\right)}=4646 \end{align*}

in accordance with the result of @WillOrrick.

Answer 2

This is not a formula, but it does provide a way to compute the number you want. Let $f(n,k)$ denote the number $k$-term sums of the numbers $2$, $5$, and $10$ whose value is $n$. Using the exponential generating function, $f(n,k)$ is the coefficient of $\frac{x^ny^k}{k!}$ in the expansion of $$ G(x,y)=\exp(y(x^2+x^5+x^{10})). $$ So the coefficient of $x^{40}$ in $G(x,y)$ is $$ P_{40}(y)=\frac{y^4}{24}+\frac{y^5}{12}+\frac{y^6}{48}+\frac{y^7}{720}+\frac{19 y^8}{13440}+\frac{y^9}{480}+\frac{y^{10}}{2880}+\frac{y^{11}}{86400}+\frac{y^{12}}{7257600}+\frac{y^{1 3}}{7257600}+\frac{y^{14}}{87091200}+\frac{y^{16}}{1307674368000}+\frac{y^{17}}{2615348736000}+\frac{y^{20}}{2432902008176640000}. $$ The number of four-term sums with value $40$ is the coefficient of $\frac{y^4}{4!}$ in this sum, which is $1$; the number of five-term sums is the coefficient of $\frac{y^5}{5!}$, which is $10$; the number of six-term sums is the coefficient of $\frac{y^6}{6!}$, which is $15$; and so on.

Added: A systematic way to extract the answer to the question in the original post is to define the differential operator $$ \mathcal{D}=1+\frac{\partial}{\partial y}+\frac{\partial^2}{\partial^2 y}+\frac{\partial^3}{\partial^3 y}+\ldots. $$ Then $$ \left.\mathcal{D}P_{40}(y)\right\rvert_{y=0}=4646. $$ Applying this operator to $G(x,y)$ gives the single-variable generating function $$ \left.\mathcal{D}G(x,y)\right\rvert_{y=0}=\sum_{j=0}^\infty(x^2+x^5+x^{10})^j=\frac{1}{1-x^2-x^5-x^{10}}. $$ One root of the denominator is $-1$. If one can find all ten roots, then one can perform partial fraction decomposition and get a closed form for all of the coefficients. Carrying this out numerically gives the formula $$ (0.142857) (-1.)^n+(0.13495\, -0.118936 i) (-0.977224-0.533462 i)^n+(0.13495\, +0.118936 i) (-0.977224+0.533462 i)^n+(0.0325019\, -0.00923824 i) (-0.28946-0.81605 i)^n+(0.0325019\, +0.00923824 i) (-0.28946+0.81605 i)^n+(0.078652\, +0.0284466 i) (0.357796\, -0.943739 i)^n+(0.078652\, -0.0284466 i) (0.357796\, +0.943739 i)^n+(0.0433843\, -0.0370765 i) (0.771384\, +0.483182 i)^n+(0.0433843\, +0.0370765 i) (0.771384\, -0.483182 i)^n+(0.278166) (1.27501)^n, $$ which gives accurate results for $n=40$. The leading large $n$ asymptotic behavior is given by the last term in this expression, $$ 0.2781662298364124\times (1.2750078449285394)^n. $$