Las particiones y los números de Bell

Question

Deje $F(n)$ el número de todas las particiones de $[n]$ sin singleton bloques.

1. Encontrar la fórmula recursiva para los números de $F(n)$ en términos del número de $F(i)$, $i ≤ n − 1$

2. Encontrar una fórmula para $F(n)$ en términos de la Campana Números de $B(n)$.

Para la primera pregunta, obviamente, es algo como $F(n+1) = \sum_{i=0}^n {n \choose i} F(i)$, ya que eso es lo que es, para la Campana de números, pero que realmente no puede ver cómo iba a llegar a la fórmula correcta.

Para el segundo, creo que estoy supone que el uso de la inclusión-exclusión, pero estoy un poco perdido.

Answer 1

Decir que una partición de $[n]$ es buena si no tiene singleton bloques y malo lo contrario. $B_n$ , $n$- ésimo de la Campana número, es el número total de particiones de $[n]$. Si $b(n)$ es el número de la mala particiones de $[n]$, $F(n)=B_n-b(n)$. Como de costumbre, un poco de datos no puede lastimar. Directa de la enumeración de $F(n)$ $b(n)$ y un cuadro de la Campana de los números de encuentro:

$$\begin{array}{cccc} n&F(n)&b(n)&B_n\\ \hline 0&0&1&1\\ 1&0&1&1\\ 2&1&1&2\\ 3&1&4&5\\ 4&4&11&15\\ 5&11&41&52\\ 6&41&162&203 \end{array}$$

Esta muy sugiere fuertemente que $F(n+1)=b(n)$$n\ge 1$. Para ver por qué esto es cierto, en primer lugar, imaginemos que $\pi$ es una mala partición de $[n]$; entonces podemos formar una buena partición de $[n+1]$ mediante la recopilación de todos los embarazos únicos de $\pi$ en un solo bloque y poner $n+1$ dentro de ese bloque. Por el contrario, si $\pi$ es una buena partición de $[n+1]$, podemos formar una mala partición de $[n]$ tomando el bloque de $\pi$ contiene $n+1$, tirar la $n+1$, y convertir el resto del bloque únicos. Estas operaciones son claramente inversos el uno del otro y así establecer un bijection entre el mal particiones de $[n]$ y buena particiones de $[n+1]$.

Esto inmediatamente nos da la recurrencia $F(n+1)=B_n-F(n)$. A desenvolver la recurrencia, nos encontramos con que

$$\begin{align*} F(n+1)&=B_n-F(n)\\ &=B_n-\big(B_{n-1}-F(n-1)\big)\\ &=B_n-B_{n-1}+F(n-1)\\ &=B_n-B_{n-1}+\big(B_{n-2}-F(n-2)\big)\\ &=B_n-B_{n-1}+B_{n-2}-F(n-2)\\ &\;\vdots\\ &=\sum_{i=0}^k(-1)^iB_{n-i}+(-1)^{k+1}F(n-k)\\ &\;\vdots\\ &=\sum_{i=0}^{n-1}(-1)^iB_{n-i}\;. \end{align*}$$

Agregado: Para la primera pregunta, vamos a $\pi$ ser una buena partición de $[n+1]$, y deje $B$ ser el bloque que contiene a $n+1$. Hay al menos un elemento de a $[n]$ en el bloque, por lo $[n]\setminus B$ es un subconjunto de a $[n]$. Si $|[n]\setminus B|=k$, $\pi\setminus\{B\}$ puede ser cualquiera de las $F(k)$ bien las particiones de $[n]\setminus B$. Por el contrario, todos bien las particiones de $[n+1]$ puede ser obtenida mediante la elección de un subconjunto $S$$[n]$, la formación de una buena partición de $S$, y a la incorporación de la cuadra $\{n+1\}\cup([n]\setminus S)$. Desde $[n]$ $\binom{n}k$ subconjuntos de cardinalidad $k$, $[n+1]$ ha $\binom{n}kF(k)$ bien las particiones en la que el bloque que contiene a $n+1$ $n-k$ otros elementos, y de ello se sigue que $$F(n+1)=\sum_{k=0}^{n-1}\binom{n}kF(k)\;.$$

Answer 2

Es algo sorprendente que no había respuesta en términos de generación de función que estos son bastante sencillos. Las especies de las particiones del conjunto está dada por $$\mathfrak{P}(\mathfrak{P_{\ge 1}}(\mathcal{Z}))$$ y por lo tanto tiene la exponencial de generación de función $$G(z) = \exp(\exp(z)-1).$$ Las especies de las particiones del conjunto de exclusión de singleton es $$\mathfrak{P}(\mathfrak{P_{\ge 2}}(\mathcal{Z}))$$ y por lo tanto tiene la exponencial de generación de función $$H(z) = \exp(\exp(z)-1-z).$$ Para responder a la primera pregunta diferenciar $H(z)$ para obtener $$H'(z) = H(z) \times (\exp(z)-1).$$ Aquí es útil la observación que he incluido en varios de mis posts. Cuando multiplicamos dos exponenciales funciones de generación de las secuencias de $\{a_n\}$ $\{b_n\}$ obtenemos que $$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\elegir k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ es decir, el producto de las dos funciones de generación es la generación de la función de $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

Por lo tanto, cuando se realiza la extracción de los coeficientes de la diferencian de la ecuación de $H(z)$ tenemos $$F(n+1) = \sum_{k=0}^{n-1} {n\elegir k} F(k) \times 1 = \sum_{k=0}^{n-1} {n\elegir k} F(k).$$ El límite superior es de $n-1$ e no $n$ porque $\exp(z)-1$ no tiene término constante. Esto es válido para $n\ge 1.$ La base de los casos se $F(0)=1$ $F(1)=0.$

Para la segunda parte de la pregunta reescribir la ecuación de $H(z)$ como este: $$H(z) = \exp(\exp(z)-1)\exp(-z).$$ El uso de la convolución de la exponencial en la generación de funciones una vez más y reconociendo $G(z)$ desde arriba, obtenemos que $$F(n) = \sum_{k=0}^n {n\elegir k} B_k (-1)^{n-k} = (-1)^n \sum_{k=0}^n {n\elegir k} (-1)^k B_k.$$

He aquí algunos de Arce código para explorar estos números.

con(planta, campana);
con(planta, setpartition);

nsb :=
proc(n)
opción de recordar;
local p, admitir, s, res, k;

 res := 0;
 para p en setpartition([seq(k, k=1..n)]) 
 admitir := true;

 de s en p ¿
 si nops(s) = 1 entonces
 admitir := false;
break;
fi;
od;

 si admitir, a continuación, res := res+1; fi;
od;

res;
end;

F :=
proc(n)
 opción de recordar;

 si n=0 entonces devolver 1 fi;
 si n=1 entonces devuelve 0 fi;

 agregar(binomial(n-1, k)*F(k), k=0..n-2);
end;

q := n -> (-1)^n*agregar(binomial(n, k)*(-1)^k*bell(k), k=0..n);