# The number of ways in which $n$ distinct items can be divided among $r$ groups

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.

• What are your thoughts? What have you tried? – Zestylemonzi Sep 11 '18 at 13:36
• 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. – Ross Millikan Sep 11 '18 at 15:40
• @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 )$) – 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]].}$$