2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – coffeemath May 13 '16 at 0:09
  • $\begingroup$ @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? $\endgroup$ – Axoren May 13 '16 at 1:15
  • $\begingroup$ 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, $\endgroup$ – coffeemath May 13 '16 at 2:54
2
$\begingroup$

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".]

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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