# Stars and Bars with an odd constraint.

Stars and bars is a classic combinatorics question, but I've run into a variant I've never seen before.

I have $n$ stars. Rather than group them into piles using $k - 1$ bars, I want to group them up by any number of bars, such that no pile of stars contains less than $c$ stars. Order of piles doesn't matter. Order of stars doesn't matter.

In this case, I don't know how many bars there are in general.

I know that there can be $0$ and I know that there can be $\frac n c - 1$ bars (for nice values of $n,c$).

The issue here is that the minimum number of stars per pile is throwing a wrench into how I know to approach the problem. I could sum over $k = 0 \text{ to } \frac n c - 1$ and solve this sub-problem.

I have $n$ stars and $k$ bars. How many combinations have no pile with less than $c$ stars?

This problem, I'm also not familiar with how to solve. How do I approach either of these?

• Since the orded of the summands doesn't matter, this sounds more like partitions of $n$ in which each part is $c$ or more. [In partitions there may be any number of parts, and the usual version has only each part $1$ or more. So I think your problem is related to that one, only since you don't know in avance how many piles, there isn't an immediate way to reduce to usual partitions. – coffeemath May 13 '16 at 0:09
• @coffeemath Is there a known pattern for partitions of $n$ elements whose slices are of $c$ or more? I wouldn't know how to search that. Stars and bars is a canon title for a common problem. Is there such a title for this? – Axoren May 13 '16 at 1:15
• Axoren Just put up an "answer" about the second question, relating it to standard partition functions, but have no idea how to do the first one, – coffeemath May 13 '16 at 2:54

I don't know about the first count in which the number of bars is not specified. However if there are $k$ bars then there are $k+1$ summands, and since each one has size at least $c$ the least $n$ one can make is $c(k+1).$ That can be made in only one way (one star in each pile). For $n>c(k+1)$ we could let $m=n-c(k+1)$ and then partition $m$ into $k+1$ or fewer parts using the usual partition function.

For example there are various partitions of $6$ into three or fewer parts $1+1+4,1+2+3,2+2+2,1+5,2+4,3+3,6$ One notation for partitions of $n$ into $k$ parts used is $p(n,k),$ and this function has been studied (and there are recursive ways to compute it. It would then be summed for an initial segment of $k$ values to apply to your situation. [Sorry about the notation clash here, using $k$ for number of bars, and also in the $p(n,k)$ function...]

So to apply this to your situation, if you had $k=2$ bars, and therefore three summands, and your required $c$ was say $4,$ one could not make any $n$ less than 12. $12$ itself could be made in only 1 way as $4+4+4,$ but after subtracting $c(k+1)=12$ one would be "partitioning" zero (which usually isn't defined). However to use the above partitions of $6$ into 3 or fewer parts, it would be applied to $n=18$ given the above $k,c.$ and give for example $4+4+10$ from the partition $6=6$ of 6, and $5+6+7$ from the partition $1+2+3$ of $6.$

So I believe in case the number of bars is known, the count can be found as outlined using the information about the partition function $p(n,k)$ [Maybe look up "partitions of n into k parts".]

• There is much information about $p(n,k)$ starting just after formula $(58)$ at MathWorld. – Brian M. Scott May 13 '16 at 16:36
• @BrianM.Scott Thanks for mentioning that link, maybe OP will find it useful. – coffeemath May 13 '16 at 17:48