4
$\begingroup$

Stirling number of the second kind is the number of ways to partition a set of n objects into k non-empty subsets - S(n,k). I want to restrict/constrain this partition so I can count the ways to partition a set of n objects into k non-empty subsets while at least p subsets out of k will have size r. When p=k the answer is the associated Stirling of the second kind Sr(n,k) , but I was wondering whether there is a general expression for any p. In case there isn't I will be glad to find an expression for p=1 and r=1. Thank you.

An example: the number of partitions of 4 objects into 2 subsets is S(4,2)=7. I want to count only the partitions that contain at least p=1 subset in the size of r=1. So in this case the answer is 4 because I don't want to count {1 2 | 3 4}, {1 3 | 3 2} and {1 4 | 2 4}.

$\endgroup$
3
$\begingroup$

Here is an approach based upon generating functions. The following can be found in section II.3.1 in Analytic combinatorics by P. Flajolet and R. Sedgewick:

The class $S^{(A,B)}$ of set partitions with block sizes in $A\subseteq \mathbb{Z}_{\geq 1}$ and with a number of blocks that belongs to $B$ has exponential generating function

\begin{align*} S^{(A,B)}(z)=\beta(\alpha(z))\qquad\text{where}\qquad \alpha(z)=\sum_{a\in A}\frac{z^a}{a!},\quad \beta(z)=\sum_{b\in B}\frac{z^b}{b!}\tag{1} \end{align*}

We decompose the problem into two parts and use (1) to derive generating functions for each part.

First part: We consider $p$ partitions with size $r$.

\begin{align*} A_1=\{r\}, B_1=\{p\}\qquad\text{where}\qquad\alpha_1(z)=\frac{z^r}{r!},\beta_1(z)=\frac{z^p}{p!} \end{align*}

We obtain a generating function \begin{align*} \beta_1\left(\alpha_1\left(z\right)\right)=\frac{1}{p!}\left(\frac{z^r}{r!}\right)^p=\frac{z^{rp}}{p!\left(r!\right)^p}\tag{2} \end{align*}

Second part: We consider $k-p$ partitions with size $\geq 1$.

\begin{align*} A_2={\mathbb{Z}}_{\geq 1}, B_2=\{k-p\}\qquad\text{where}\qquad \alpha_2(z)=\sum_{n=1}^\infty \frac{z^n}{n!},\beta_2(z)=\frac{z^{k-p}}{(k-p)!} \end{align*}

We obtain a generating function \begin{align*} \beta_2\left(\alpha_2\left(z\right)\right)&=\frac{1}{(k-p)!}\left(e^z-1\right)^{k-p} =\sum_{n=k-p}^\infty {n\brace k-p}\frac{z^n}{n!}\tag{3} \end{align*} Note the coefficients of (3) are the Stirling numbers of the second kind.

Since the original problem is the cross product of the two parts, the resulting generating functions is the product of the generating functions in (2) and (3). We denote with \begin{align*} a_{r,p}(n,k) \end{align*} the number of distributions of $n$ elements into $k$ partitions with at least $p$ partitions having exactly $r$ elements.

We obtain for $1\leq p\leq k\leq n, 1\leq r\leq \left\lfloor\frac{n}{r}\right\rfloor$ \begin{align*} \beta_1\left(\alpha_1\left(z\right)\right)\beta_2\left(\alpha_2\left(z\right)\right) &=\sum_{n=k-p}^\infty {n\brace k-p}\frac{z^n}{n!}\cdot\frac{z^{rp}}{p!\left(r!\right)^p}\\ &=\frac{1}{p!\left(r!\right)^p}\sum_{n=k-p+rp}{n-rp\brace k-p}\frac{z^n}{(n-rp)!}\\ &=\frac{(rp)!}{p!(r!)^p}\binom{n}{rp}\sum_{n=k+(r-1)p}{n-rp\brace k-p}\frac{z^n}{n!}\\ &=\sum_{n=k+(r-1)p}a_{r,p}(n,k) \end{align*}

We conclude: \begin{align*} \color{blue}{a_{r,p}(n,k)=\frac{(rp)!}{p!(r!)^p}\binom{n}{rp}{n-rp\brace k-p}}\tag{4} \end{align*}

Example: Calculating OPs example with $n=4,k=2,p=1$ and $r=1$ using (4) results in \begin{align*} a_{1,1}(4,2)=\binom{4}{1}{3\brace 1}=4 \end{align*} in accordance with OPs calculation.

$\endgroup$
2
$\begingroup$

Formula that count the number of partitions of a n-set into k-parts of size 1 or 2 is
$$\overline{p}_k(n,N_2) =\binom{k}{n-k} \frac{n!}{k!\cdot2^{n-k}}$$

$\endgroup$
  • $\begingroup$ Does it mean that each and every one of the subsets are in size 1 or 2? what if I want to count all the partitions that include at least one subset of size 1? Thank you. $\endgroup$ – Evya Jun 20 '14 at 9:03

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.