Números de Stirling de segunda clase con restricciones

Aquí hay un enfoque basado en la generación de funciones. Lo siguiente se puede encontrar en la sección II.3.1 en Combinatoria analítica por P. Flajolet y R. Sedgewick:

La clase$S^{(A,B)}$de particiones establecidas con tamaños de bloque en$A\subseteq \mathbb{Z}_{\geq 1}$y con un número de bloques que pertenece a$B$tiene función generadora exponencial

$$\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*}$$

Descomponemos el problema en dos partes y usamos (1) para derivar funciones generatrices para cada parte.

Primera parte: Consideramos$p$particiones con tamaño$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*}$$

Obtenemos una función generadora

$$\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*}$$

Segunda parte: Consideramos$k-p$particiones con tamaño$\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*}$$

Obtenemos una función generadora

$$\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*}$$ Nótese que los coeficientes de (3) son los números de Stirling de segunda clase .

Dado que el problema original es el producto cruzado de las dos partes, las funciones generadoras resultantes son el producto de las funciones generadoras en (2) y (3). denotamos con

$$\begin{align*} a_{r,p}(n,k) \end{align*}$$ el número de distribuciones de $n$elementos en $k$particiones con al menos $p$particiones que tienen exactamente $r$elementos.

Obtenemos por$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*}$$

Concluimos:

$$\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*}$$

Ejemplo: Ejemplo de cálculo de OP con$n=4,k=2,p=1$y$r=1$usando (4) da como resultado

$$\begin{align*} a_{1,1}(4,2)=\binom{4}{1}{3\brace 1}=4 \end{align*}$$ de acuerdo con el cálculo de OP.

La fórmula que cuenta el número de particiones de un conjunto n en k partes de tamaño 1 o 2 es

$$\overline{p}_k(n,N_2) =\binom{k}{n-k} \frac{n!}{k!\cdot2^{n-k}}$$