# How to get number of combinations from given set of numbers to result a given sum?

Eg:

sum = 10
Num of given nos: 1
Given nos: 1
Num of Combination: 1

sum = 13
Num of given nos: 3
Given nos: 1, 2, 8
Num of Combination: 415

sum = 15
Num of given nos: 5
Given nos: 1, 2, 3, 4, 5
Num of Combination: 13624


Case 1 explain: Only one combination is possible: $$1+1+1+1+1+1+1+1+1+1$$

I want to know how to get $415$ combinations for case $2$ as well as for case $3$.

I came to know this has to be solved by Frobenius theorem $$N = \sum_{i=1}^n a_i \times x_i$$

but here what will $N,a_i, x_i =?$

• A suggestion: use ''num'' to abbreviate ''number''. Even better, don't use abbreviations... Nov 9 '11 at 11:44
• Compositions sure are turning up a lot lately here in math.SE... Nov 9 '11 at 11:50
• Like, in here... Nov 9 '11 at 12:07
• 1. That's probably Frobenius. 2. What theorem? You've written down an equation full of undefined symbols - that's not a theorem. 3. I suppose you are interested in all solutions of that equation where $N$ is your sum, $n$ is arbitrary, $x_i$ come from your given numbers, and the $a_i$ are all 1. E.g., in your 2nd case, $N=13$; $x_i$ take values from 1, 2, 8; $a_i$ are all 1; and $n$ takes all values from 4 to 13. Nov 10 '11 at 6:11
• P.S.: You asked how to get 415, and I told you in my answer. Did you not find that helpful? Nov 10 '11 at 6:12

This can be solved with dynamic programming:

Denote the set of given numbers as $S$ and the number of required combinations for some number $n$ as $f(n)$. Then the following recurrent equation holds:

$$f(n)=\left\{ \begin{array}{ll} \sum\limits_{k \in S }f(n-k) & \textrm{if }n\not\in S, n > 0\\ \sum\limits_{k \in S }f(n-k) + 1 & \textrm{if }n\in S \\ 0 &\textrm{if } n < 0 \end{array}\right.$$

The main formula is given in line 1, the recurrence base - in line 2, and the impossible cases are cut out in line 3.

Thus $f(n)$ can be calculated in $O(n*|S|)$.

• Right answer, wrong question. I don't think this gives 415 for OP's 2nd example. OP seems to be counting $8+2+2+1$, $2+1+2+8$, $1+2+8+2$, etc., etc., as different. Nov 10 '11 at 0:00
• So, I think it should be a permutation rather than combination as it counts order of combination too. Nov 10 '11 at 4:06
• The usual word, as noted in the comments on the original question, is "composition". Nov 10 '11 at 6:06

Here's how you get 415 for Case 2. I'll leave case 3 (and the general case) to you.

Not counting order, there are 10 ways to make up 13 using 1s, 2s, and 8s:

$8+2+2+1$
$8+2+1+1+1$
$8+1+\cdots+1$
six 2s and one 1
five 2s and three 1s
four 2s and five 1s
three 2s and seven 1s
two 2s and nine 1s
one 2 and eleven 1s
thirteen 1s.

But order (evidently) counts. So, how many ways can you order 8, 2, 2, 1? You could order 4 distinct numbers 24 ways, but the 2s are indistinguishable, so we get 12.

How many ways to order 8, 2, 1, 1, 1? The 8 can go in any of 5 locations, the 2, in any of the reamaining 4 locations, so, 20.

For one 8 and five 1s, there are 6 places to put the 8, so, 6.

For the 2s and 1s, if there are $m$ 2s and $n$ 1s, then there are $(m+n)$-choose-$m$ orderings.

Putting it all together you get $$12+20+6+7+56+126+120+55+12+1=415$$

• It was useful & Iam finding how to get the series expansion? Nov 10 '11 at 7:39
• Do you know how to compute the series ? Nov 10 '11 at 10:27
• @Angelin If you don't have a computer, the best way to solve such problems is outlined in Gerry's answer. There is no easy way to compute the series.
– user940
Nov 10 '11 at 14:42
• Its not about easy way but to automate it. Nov 10 '11 at 16:49

The three tasks are interesting. Unfortunately, Euler in “Observationes analyticae variae de combinationibus”, Commentarii academiae scientiarum Petropolitanae, 13, 1751, pp. 64–93. (https://arxiv.org/pdf/0711.3656.pdf is an English translation of E158) and his later works, Caley, Sylvester, Macmahon, Hardi, Ramanujan, Rademacher, … did not leave an opportunity to make a discovery in these three and a few related problems (but not all of this kind).

Terminology: a partition of a positive integer is its representation as a sum of positive integers not considering the order of the summands - parts; compositions are partitions in which the order of occurrences of parts is essential. In general, the number $n$, and $r$ parts are involved. A multiset is a set with possibly repeated elements. Numbers of repetitions are multiplicities. We shall write the multiset $\{1,2,2,8\}$ as $\{1^1,2^2,8^1\}$, where “powers” are multiplicities.

The number of partitions of 13 in any numbers of parts $\{1, 2, 8\}$ can be obtained as a coefficient at $x^{13}$ in the expansion of $\frac{1}{(1-x)(1-x^2)(1-x^8)}$. If this looks strange, then recollect that $\frac{1}{1-x}$ is the infinite geometric series $1+x+x^2+x^3+x^4+\cdots$. Similarly, $\frac{1}{1-x^2}$ is $1+x^2+x^4+x^6+x^8+\cdots$, and $\frac{1}{1-x^8}$ is $1+x^8+x^{16}+x^{24}+x^{32}+\cdots$. When three infinite series are multiplied, the coefficients at the lower powers of $x$ are not affected by the higher powers – stabilize. Our product is $1+x+2x^2+2x^3+3x^4+3x^5+4x^6+4x^7+6x^8+6x^9+8x^{10}+8x^{11}+10x^{12}+10x^{13}+12x^{14}+\dots$

So, $3=1+1+1=1+2$ yields two partitions using allowed parts 1, 2, 8. This is the coefficient 2 at the term of $x^3$. But $5=1+1+1+1+1=1+1+1+2=1+2+2$ yields three partitions, notice $3x^5$. 13 yields 10 partitions, notice $10x^{13}$, written for briefness as multisets $\{1^{13}\}$, $\{1^{11},2^1\}$, $\{1^9,2^2\}$, $\{1^7,2^3\}$, $\{1^5,2^4\}$, $\{1^3,2^5\}$, $\{1^1,2^6\}$, $\{1^{5},8^1\}$, $\{1^3,2^1,8^1\}$, $\{1^1,2^2,8^1\}$. The number of unique permutations of multiset $\{p_1^{m_1},\dots,p_k^{m_k}\}$ elements is $\frac{(m_1+\cdots+m_k)!}{m_1!\cdots m_k!}$.

We get the sum of 10 numbers $1+12+55+120+[\frac{(5+4)!}{5!4!}=7\cdot 2 \cdot 9=126]+56+7+6+20+12=415$. This coincides with Gerry's evaluation and supports original result. Euler discusses that sometimes expansions become rather complex and for a few important cases derives recurrent relationships between the coefficients in front of powers. Asymptotic formulas from Hardi, Ramanujan, Rademacher evaluate the number of unrestricted partitions of $n$. Best Regards, Valerii Salov.

Focusing on the interpretation of Gerry's method and mainly illustrating its relationship to the Euler's 1751 paper, I have "overlooked" the answer of user940. That one "bypasses" the three step process: 1) get restricted partitions, 2) evaluate numbers of their unique permutations, 3) sum the obtained quantities. However, user940 does not explain, where his generating functions come from. Here, I only fill that gap. The following result is well known (for instance, Proposition I.1 on page 42 of Flajolet, Philippe, Sedgewick, Robert. Analytic Combinatorics. Cambridge: Cambridge University Press, 2009). Let $T$ is a subset of positive integers, $n$ is a positive integer, and we need the number of compositions on any number of parts from this subset, then the generating function is $C^T(z)=\frac{1}{1-\sum_{k \in T}z^k}$.

For compositions of 13 represented by $\{1,2,8\}$, we write

$\frac{1}{1-x-x^2-x^8}=1+x+2x^2+3x^3+5x^4+8x^5+13x^6+21x^7+35x^8+57x^9+94x^{10}+154x^{11}+253x^{12}+415x^{13}+681x^{14}+1117x^{15}+1833x^{16}+3007x^{17}+\cdots$

and find 415 at the term $x^{13}$.

For compositions of 15 represented by $\{1,2,3,4,5\}=$ we write

$\frac{1}{1-x-x^2-x^3-x^4-x^5}=1+x+2x^2+4x^3+8x^4+16x^5+31x^6+61x^7+120x^8+236x^9+464x^{10}+912x^{11}+1793x^{12}+3525x^{13}+6930x^{14}+13624x^{15}+26784x^{16}+52656x^{17}+\cdots$

and find 13624 at the term $x^{15}$.

As a compensation for overlooking the user940's "bypass", I am referencing MacMahon, Percy, Alexander. Memoir on the Theory of the Compositions of Numbers. Philosophical Transactions of the Royal Society of London, Series A, Volume 184, 1893, pp. 835 - 901. Best Regards, Valerii Salov