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.

How many ways there are to group 27 same cookies into 3 same groups, where each group contains at least 1?

If the groups are distinct, then I can use the technique to calculate how many vectors(x1,x2,x3) there are such that x1 + x2 + x3 = 27. However, the groups are actually same, how can I solve that? Thanks.

share|improve this question
    
shouldnt we change group to set? –  Bananarama Jan 8 '13 at 3:13

2 Answers 2

up vote 3 down vote accepted

You want the number of partitions of $27$ into at most $3$ parts; this is given by the partition function $q(n,k)$, which gives the number of partitions of $n$ into at most $k$ parts. Specifically, you want $q(27,3)$. The partition function satisfies a simple recurrence, so it’s possible to calculate small values fairly easily. However, the numbers $q(n,3)$ are OEIS A001399, where you can read off the value $75$. You can also find the formula

$$q(n,3)=\left\lfloor\frac{(n+3)^2}{12}+\frac12\right\rfloor\;.$$

Added: The recurrence $$q(n,k)=q(n,k-1)+q(n-k,k)$$ can be justified as follows. Partitions of $n$ into at most $k$ parts are of two kinds: those that have fewer than $k$ parts, and those that have exactly $k$ parts. There are $q(n,k-1)$ that have fewer than $k$ parts. Now take a partition with exactly $k$ parts; if you remove $1$ from each part, you have a partition of $n-k$ into at most $k$ parts. Conversely, if you start with a partition of $n-k$ into at most $k$ parts and add $1$ to each part, you get a partition of $n-k$ into exactly $k$ parts. Since there are $q(n-k,k)$ partitions of $n-k$ into at most $k$ parts, there must be $q(n-k,k)$ partitions of $n$ into exactly $k$ parts. And this justifies the recurrence: the $q(n,k)$ partitions of $n$ into at most $k$ parts include $q(n,k-1)$ that have fewer than $k$ parts and $q(n-k,k)$ with exactly $k$ parts.

share|improve this answer
    
what about exact 3 groups? that being said, each group has at least 1. –  Frank Xu Jan 8 '13 at 0:02
5  
@Frank: If each group has at least $1$, then you are in effect distributing $24$ arbitrarily, so just use $q(24,3)=61$ instead. –  Brian M. Scott Jan 8 '13 at 0:04
    
could u explain more about q(n,k) = q(n,k-1) + q(n-k,k)? I don't quite understand the q(n-k,k) part, thank you –  Frank Xu Jan 8 '13 at 0:26
    
@Frank: It comes from the same reasoning as my previous comment; I’ve expanded on that in an addition to my answer. –  Brian M. Scott Jan 8 '13 at 0:34

The size $x_1$ of the largest group ranges from $9$ to $25$. From $x_1=9$ up to $x_1=13$ there are $1,2,4,5,7$ options, respectively, for splitting up the rest. From $x_1=14$ up to $x_1=25$ there are $6,6,5,5,4,4,3,3,2,2,1,1$ options, respectively, for splitting up the rest. Thus the total is $1+2+4+5+7+2\cdot6(6+1)/2=19+42=61$, in agreement with Brian's more elegant answer.

share|improve this answer

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.