Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given an integer $N ≥ 0$ and an integer $K ≥ 0$, how many tuples $(n_1,\ldots,n_k)$ are there such that $n_i ≥0$ and $\Sigma n_i = N$? In other words, how many way can you "partition" $N$ into $K$ sets such that the sum of the sets adds up to $N$.

For example, $n = 5$, $k =2$ gives 6 tuples: $(5,0) , (4,1) \ldots (0,5)$.

I've come up with this recursive definition:

$P(n,k) =$ # of tuples $(n_1,..,n_k)$ such that $n_i ≥ 0$ and $\Sigma n_i = N$
$P(n,k) = \Sigma_{i=0}^n{P(i,k-1)}$
$P(0,k)=1 $
$P(n,1)=1$

A suggested answer below is that this problem is the Stirling #'s of 2nd kind but I am not sure how to reduce this problem to it. See my response below.

My question is if there's a closed form solution for $P(n,k)$?

share|improve this question
    
I would be very unsurprised if this is a duplicate. If someone less busy than me would be happy to have a check for that, that would be great! –  Tara B May 15 '12 at 15:15
    
@Tara: You’re right: it’s about the umpty-third question involving this problem or a variant. –  Brian M. Scott May 16 '12 at 4:06
    
@BrianM.Scott: Are there enough of them to make one of those 'generalisations of common questions'? –  Tara B May 16 '12 at 8:11
    
@Tara: It would be a chore, because while some are very straightforward, like this one, some have fairly ugly boundary conditions. You can get a pretty good idea if you use the site search on stars and bars. –  Brian M. Scott May 16 '12 at 8:16
    
@BrianM.Scott: Okay, yes, probably too much work. –  Tara B May 16 '12 at 8:25
add comment

1 Answer

up vote 1 down vote accepted

This is a standard stars-and-bars problem; the answer is that $$p(n,k)=\binom{n+k-1}{k-1}=\binom{n+k-1}n=\frac{(n+k-1)!}{(k-1)!\,n!}\;.$$ The explanation in the Wikipedia article cited above is pretty clear. What you’re counting are called compositions of $n$ into $k$ parts; you’ll find more information on them here. (A search of this site for stars and bars will turn up many variations on this type of problem, some with quite detailed answers, but the Wikipedia stars-and-bars article is your best starting point.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.