The number of ways in which $n$ distinct items can be divided among $r$ groups such that no group contains less than $m$ and not more than $k$ items $(m<k)$ is

Please solve this question.I am having no idea how to solve this question because I hadn't started Binomial Chapter ,I was wondering if there is any way to solve this question using Permutation and Combination.

Edit:-I tried but to solve this question but I couldn't reach anywhere.Please answer this question and try to understand I am not trying to be lazy to ask homework question.

  • $\begingroup$ What are your thoughts? What have you tried? $\endgroup$ – Zestylemonzi Sep 11 '18 at 13:36
  • $\begingroup$ I don't think you will get a nice compact formula. You can define $N(n,r,m,k)$ as the answer and get a recurrence by taking a number of items for the first group and distributing the rest of the items among the other groups. The restrictions of $m$ and $k$ complicate things for a compact formula. $\endgroup$ – Ross Millikan Sep 11 '18 at 15:40
  • $\begingroup$ @RossMillikan I got a result but problem is it's used for identical items "Coefficient of $x^n$ in the expansion of($ (x^m + x^m+1 +........+x^k)^r )$) $\endgroup$ – Rafael Nadal Sep 11 '18 at 16:16

Duplicating the construction for Stirling numbers we get the combinatorial class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}_{=r}(\textsc{SET}_{m\le\cdot\le k} (\mathcal{Z})).$$

The corresponding EGF is

$$\frac{1}{r!} \left(\sum_{q=m}^k \frac{z^q}{q!} \right)^r.$$

The desired quantity is then given by

$$a_{n,r} = n! [z^n] \frac{1}{r!} \left(\sum_{q=m}^k \frac{z^q}{q!} \right)^r.$$

If a recurrence is wanted with memoization we write

$$a_{n,r} = \frac{1}{r} n! [z^n] \sum_{p=m}^k \frac{z^p}{p!} \frac{1}{(r-1)!} \left(\sum_{q=m}^k \frac{z^q}{q!} \right)^{r-1} \\ = \frac{1}{r} n! \sum_{p=m}^k \frac{1}{p!} [z^{n-p}] \frac{1}{(r-1)!} \left(\sum_{q=m}^k \frac{z^q}{q!} \right)^{r-1} \\ = \frac{1}{r} n! \sum_{p=m}^k \frac{1}{p!} \frac{1}{(n-p)!} a_{n-p, r-1} \\ = \frac{1}{r} \sum_{p=m}^k {n\choose p} a_{n-p, r-1}.$$

This yields

$$\bbox[5px,border:2px solid #00A000]{ a_{n,r} = \frac{1}{r} \sum_{p=m}^{\min(n,k)} {n\choose p} a_{n-p, r-1} \quad\text{where}\quad a_{n,1} = [[m\le n\le k]].}$$


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.