integer-partitionsset-partition
I spent all afternoon looking for this but I wasn't able to find anything, so…
Is there a formula to know the NUMBER of partitions with a constraint on the integer domain ?
E.g.: Find the number of partitions of 5 only using integers belonging to S = {1,2,3}
p(5) -> 13
Since p(5):
[1,1,1,1,1]
[1,1,1,2]
[1,1,2,1]
[1,2,1,1]
[2,1,1,1]
[2,2,1]
[2,1,2]
[1,2,2]
[1,1,3]
[1,3,1]
[3,1,1]
[3,2]
[2,3]
To complete the conversation, here is a rather concise java program to generate the sequence up to $a(200)$
import java.lang.Math;
public class PartitionCounter
{
public static void main(String[] args)
{
int F[] = new int[201];
F[0]=1;
F[1]=1;
for(int n=2; n<201; n++){
for(int k=200; k>n-1; k--){
F[k] = F[k]+F[k-n];
}
}
System.out.print("[");
for(int k=0; k<200; k++){
System.out.print((F[k]-1) + ", ");
}
System.out.print("]");
}
}
What is going on mathematically is again, we are approaching via generating functions. In this case, the generating function is:
$$\frac{1}{x-1}+\prod\limits_{k=1}^\infty (1+x^k)$$
For our purposes however, we do not need infinitely many terms, we only need the first $201$ terms of the polynomial, so the following will suffice
$$(1+x)(1+x^2)(1+x^3)\cdots (1+x^{199})(1+x^{200}) - (1+x+x^2+\dots+x^{200})$$
The coefficient of $x^n$ in the expansion of the above corresponds to the number of partitions of $n$ matching your requirements (all parts distinct and at least two parts). To see why this is, recognize that if we were to avoid adding anything together, there will be a term associated with each sequence of choosing $x^i$ vs $1$ in the product such that the powers add up to $n$.
For example, one of the contributions to the coefficient of $x^5$ comes from the sequence of choices (in red) as $(\color{red}{1}+x)(1+\color{red}{x^2})(1+\color{red}{x^3})(\color{red}{1}+x^4)\cdots$ corresponding to the partition (2,3). This is just like the "foil" method for computing $(a+b)(c+d)$ except taken to the extreme having used "infinitely many" (though only finitely many matter) parenthetical expressions being multiplied.
The code above quite literally computes the coefficients of $x^k$ in the expansion of $(1+x)(1+x^2)(1+x^3)\cdots (1+x^{200})$ and stores them in an integer array for each partial product. It only bothers to remember the coefficients for those terms up to the power $x^{200}$ because anything of higher power is irrelevant. We finally recognize that if we have a polynomial, $f(x)$ and we multiply by $(1+x^k)$, the coefficient of $x^n$ in $(1+x^k)f(x)$ will be the coefficient of $x^n$ in $f(x)$ plus the coefficient of $x^{n-k}$ in $f(x)$. The above code will update the values of $F[n]$ from back to front so as to avoid having the newly modified values disrupting further calculations without the need to create a temporary array.
Finally, we subtract one from the above because you are interested only in those partitions which have at least two parts. (this is also where the $\frac{1}{x-1}$ comes into play in the generating function, as the expansion of $\frac{1}{x-1}$ is $-1-x-x^2-x^3-x^4-\dots$)
The output for the first two hundred and one terms in the sequence is then: (note: starts at $n=0$ instead of $n=3$)
[0, 0, 0, 1, 1, 2, 3, 4, 5, 7, 9, 11, 14, 17, 21, 26, 31, 37, 45, 53, 63, 75, 88, 103, 121, 141, 164, 191, 221, 255, 295, 339, 389, 447, 511, 584, 667, 759, 863, 981, 1112, 1259, 1425, 1609, 1815, 2047, 2303, 2589, 2909, 3263, 3657, 4096, 4581, 5119, 5717, 6377, 7107, 7916, 8807, 9791, 10879, 12075, 13393, 14847, 16443, 18199, 20131, 22249, 24575, 27129, 29926, 32991, 36351, 40025, 44045, 48445, 53249, 58498, 64233, 70487, 77311, 84755, 92863, 101697, 111321, 121791, 133183, 145577, 159045, 173681, 189585, 206847, 225584, 245919, 267967, 291873, 317787, 345855, 376255, 409173, 444792, 483329, 525015, 570077, 618783, 671417, 728259, 789639, 855905, 927405, 1004543, 1087743, 1177437, 1274117, 1378303, 1490527, 1611387, 1741520, 1881577, 2032289, 2194431, 2368799, 2556283, 2757825, 2974399, 3207085, 3457026, 3725409, 4013543, 4322815, 4654669, 5010687, 5392549, 5802007, 6240973, 6711479, 7215643, 7755775, 8334325, 8953855, 9617149, 10327155, 11086967, 11899933, 12769601, 13699698, 14694243, 15757501, 16893951, 18108417, 19406015, 20792119, 22272511, 23853317, 25540981, 27342420, 29264959, 31316313, 33504745, 35839007, 38328319, 40982539, 43812109, 46828031, 50042055, 53466623, 57114843, 61000703, 65139007, 69545357, 74236383, 79229675, 84543781, 90198445, 96214549, 102614113, 109420548, 116658615, 124354421, 132535701, 141231779, 150473567, 160293887, 170727423, 181810743, 193582641, 206084095, 219358314, 233451097, 248410815, 264288461, 281138047, 299016607, 317984255, 338104629, 359444903, 382075867, 406072421, 431513601, 458482687, ]
A pretty easy way is to use generating functions. Let's denote the number of solutions $(n_1,\ldots,n_d)\in\mathbb{Z}^d$ of $|n_1|+|n_2|+\ldots+|n_d|=k$ by $N(k,d)$, and similarly use $N_{\geqslant 0}(k,d)$ for $\mathbb{Z}_{\geqslant 0}$, etc. Then $$\sum_{k\geqslant 0}N_{\geqslant 0}(k,d)z^k=(1+z+z^2+z^3+\ldots)^d=\frac{1}{(1-z)^d};\\\sum_{k\geqslant 0}N_{>0}(k,d)z^k=(z+z^2+z^3+\ldots)^d=\frac{z^d}{(1-z)^d};\\\sum_{k\geqslant 0}N(k,d)z^k=(1+2z+2z^2+2z^3+\ldots)^d=\frac{(1+z)^d}{(1-z)^d}.$$ Now the binomial series gives the well-known formula $N_{\geqslant 0}(k,d)=\binom{k+d-1}{d-1}$ (which also has a well-known combinatorial interpretation). Yet another way to get it is to use Cauchy's integral formula $$N_{\geqslant 0}(k,d)=\frac{1}{2\pi i}\oint_{|z|=r}\frac{dz}{z^{k+1}(1-z)^d},$$ say, where $0<r<1$; the substitution $z=1/w$ gives $$N_{\geqslant 0}(k,d)=\frac{1}{2\pi i}\oint_{|w|=1/r}\frac{w^{k+1}}{(1-1/w)^d}\frac{dw}{w^2}=\frac{1}{2\pi i}\oint_{|w|=1/r}\frac{w^{k+d-1}~dw}{(w-1)^d},$$ and the same formula tells now that $N_{\geqslant 0}(k,d)$ is the coefficient of $z^{d-1}$ in $(z+1)^{k+d-1}$, as expected.
For $N(k,d)$, these approaches are not that fruitful. The generating function gives the formula $$N(k,d)=\sum_{r=0}^{d}\binom{d}{r}\binom{k+r-1}{d-1}$$ (obtained by expanding $(1+z)^d$ and [re]using the expansion of $(1-z)^{-d}$). And Cauchy tells $$N(k,d)=[z^{d-1}](z+1)^{k-1}(z+2)^d=\sum_{r=1}^{d}2^r\binom{d}{r}\binom{k-1}{r-1}.$$ While both formulae do have combinatorial interpretations (which ones?..), these don't give a closed-form expression for $N(k,d)$. And I believe there's none (in a well-defined sense; one may try to state it properly, and even prove it, looking at the methods developed here). There is another book you may find interesting; the present question is dealt with in section 2.5 (essentially the same way, but the book gives a far broader view).
Best Answer
Ok, the problem can be solved using a recurrence equation.
If we suppose $ n > m $ the number of ordered partitions of $n$ will be: $$ P_{k}(n) = \sum_{i=1}^{k} P_{k}(n-i) $$
Where $P_{3}(1) = 1$ , $P_{3}(2) = 2$ and $P_{3}(3) = 4$.
If we think about it the first number in our partition can be any number up to $m$.
So e.g. $n = 5$ and $m = 3$
Start = 3
$[3, 1, 1]$ , $[3, 2]$
$->$ 2 partitions {$P_{3}(5-3) = P_{3}(2)$}
Start = 2
$[2, 1, 1, 1]$ , $[2, 2, 1]$ , $[2, 1, 2]$ , $[2, 3]$
$->$ 4 partitions {$P_{3}(5-2) = P_{3}(3)$}
Start = 1
$[1, 1, 1, 1, 1]$ , $[1, 1, 1, 2]$ , $[1, 1, 2, 1]$ , $[1, 2, 1, 1]$ , $[1, 1, 3]$ , $[1, 3, 1]$ , $[1, 2, 2]$
$->$ 7 partitions {$P_{3}(5-1) = P_{3}(4)$}
Finally:
$P_{3}(5) = P_{3}(4) + P_{3}(3) + P_{3}(2) = 7 + 4 + 2 = 13$