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

63 Views Asked by At

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.

1

There are 1 best solutions below

0
On

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]].}$$