0
$\begingroup$

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

Addition:

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 =?$

$\endgroup$
8
  • 1
    $\begingroup$ A suggestion: use ''num'' to abbreviate ''number''. Even better, don't use abbreviations... $\endgroup$ Nov 9 '11 at 11:44
  • 3
    $\begingroup$ Compositions sure are turning up a lot lately here in math.SE... $\endgroup$ Nov 9 '11 at 11:50
  • 1
    $\begingroup$ Like, in here... $\endgroup$ Nov 9 '11 at 12:07
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 10 '11 at 6:11
  • 1
    $\begingroup$ P.S.: You asked how to get 415, and I told you in my answer. Did you not find that helpful? $\endgroup$ Nov 10 '11 at 6:12
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Nov 10 '11 at 0:00
  • $\begingroup$ So, I think it should be a permutation rather than combination as it counts order of combination too. $\endgroup$ Nov 10 '11 at 4:06
  • 1
    $\begingroup$ The usual word, as noted in the comments on the original question, is "composition". $\endgroup$ Nov 10 '11 at 6:06
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

Your 415 and your 13624.

$\endgroup$
4
  • $\begingroup$ It was useful & Iam finding how to get the series expansion? $\endgroup$ Nov 10 '11 at 7:39
  • $\begingroup$ Do you know how to compute the series ? $\endgroup$ Nov 10 '11 at 10:27
  • $\begingroup$ @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. $\endgroup$
    – user940
    Nov 10 '11 at 14:42
  • $\begingroup$ Its not about easy way but to automate it. $\endgroup$ Nov 10 '11 at 16:49
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.