I was learning integer partition of a number n into k parts.
My initial solution was $\frac{\binom{n-1}{k-1}}{k}$ and later found out the actual formula is $p(n,k)=p(n-k,k) + p(n-1,k-1)$
Is my solution correct? $\binom{n-1}{k-1}$ is from the stars and bars problem – the number of k-tuples of positive integers whose sum is n and I divide by k because we are counting some more than we should. Here is an example.
$p(5,3)=2$
$x_1+x_2+x_3=5$ where $x\in \mathbb{N}\setminus\{0\}$
$\binom{5-1}{3-1}=6$ because we count 1+1+3,1+3+1,3+1+1 as three different and same as 2+2+1,2+1+2,1+2+2
So that's why I divide by k, which brings us to $\frac{6}{3}=2=p(5,3)$
Of course this is only one example and not a proof and that's why I want to hear your opinion if it's a solution.
Can I get the number of integer partitions into k parts using the stars and bars technique
combinatoricsdiscrete mathematics
Best Answer
No, you cannot. The number of orders depends on how many of the pieces are equal. For example, $10=1+2+3+4$ is counted $4!=24$ times. Your counts of $k$ times applies when one part is distinct but all the rest are equal. Counting partitions is harder than counting combinations for this reason. The Wikipedia page shows how to count them.