2
$\begingroup$

Assume we have set $A$ with $n$ elements and we want to choose $k$ items with the maximal number of repetitions $r$.

If $r = 1$ then repetitions are not allowed. Then this number can be computed as $n \choose k$.

I also know that the number of all allowed combinations with any number of repetitions equals $n+k-1 \choose k$

But how can I compute the number of combinations with at most $r$ repetitions, and some item chosen exactly $r$ times?

Example: take $A = \{a,b,c\}$ and $k = 3$:

  • $r=1$: {(a,b,c)} 1 choice
  • $r=2$: {(a,a,b),(a,a,c),(b,b,a),(b,b,c),(c,c,a),(c,c,b)} 6 choices
  • $r=3$: {(a,a,a),(b,b,b),(c,c,c)} 3 choices
Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ The generating function for the number $a_k$ of ways to choose $k$ items from $n$ with at most $r$ choices of each item is $(1+x+\cdots + x^r)^n$. Taking $r=1$ gives $(1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k$ and letting $r$ tend to infinity one gets $1/(1-x)^n = \sum_{k=0}^\infty \binom{-n}{k}(-x)^k = \sum_{k=0}^\infty \binom{k+n-1}{k}x^k$, the two formulae in the question. As far as I know there are no very convenient formulae for $r$ in between. And then one would need some form of inclusion/exclusion to count those choices where some item is chosen exactly $r$ times. $\endgroup$
    – Mark Wildon
    Nov 6, 2020 at 10:50
  • 1
    $\begingroup$ @MarkWildon I/E isn't needed. The choices with some item chosen $r$ times equals the number with all items chosen at most $r$ times minus the number with all items chosen at most $r-1$ times. $\endgroup$
    – Brendan McKay
    Nov 6, 2020 at 11:48
  • $\begingroup$ Of course. Thank you. $\endgroup$
    – Mark Wildon
    Nov 6, 2020 at 12:25

0

Reset to default