Probar

Question

Si $C_n$ es el número de las formas de partición $\{1,2,\dots ,n \}$ en subconjuntos que tiene al menos dos miembros y $B_n$ es el número de las formas para el mismo conjunto en subconjuntos no vacíos de la partición entonces demostrar que:

$C_n=B_{n-1}-B_{n-2}+\dots +(-1)^nB_1$

Parece que tenemos que utilizar el principio de inclusión-exclusión, pero ¿cómo podemos conectar $C_n$ $B_{n-1}$? Primero pensé que deberíamos miembro y partición de los demás a algunos conjuntos no vacíos, pero no funcionó. ¿Cualquier sugerencias?

Answer 1

El siguiente argumento se basa en la idea de que cada partición de $\{1,\cdots, n\}$ con un singleton

corresponde a una partición de $\{1,\cdots, n+1\}$ sin un singleton.

---

Deje $T_n$ ser el conjunto de particiones de $[n]$, con al menos 2 elementos de cada subconjunto de la partición, y

deje $P=\{A_1,\cdots,A_m\}$$Q$.

1)$\;\;$ Si $|A_i|\ge2$$1\le i\le m$,$P\in T_n$.

2)$\;\;$ Si $P\not\in T_{n}, \text{ with }|A_i|\ge2$ $1\le i\le r$ $A_i=\{a_i\}$ $r+1\le i\le m$ (donde $r<m$),

$\hspace{.27 in}$deje $P^{\prime}=\{A_1,\cdots,A_r,B\}$ donde$B=\{a_{r+1},\cdots,a_m,n+1\};\;$$P^{\prime}\in T_{n+1}$.

Esto establece una correspondencia 1-1 entre particiones de $[n]$ que no están en $T_n$ y particiones de $[n+1]$ que están en $T_{n+1}$, ya que el $P^{\prime}\in T_{n+1}$ $P^\prime=\{B_1,\cdots,B_r, B_{r+1}\}$ y $B_{r+1}=\{a_1,\cdots,a_l,n+1\}$ corresponde a la partición de $P=\{B_1,\cdots,B_r,\{a_1\},\cdots,\{a_l\}\}$$T_n$.

Por lo tanto, tenemos que $\color{blue}{B_n=C_n+C_{n+1}}$$n\ge1$; así

$\;C_n=B_{n-1}-C_{n-1}=B_{n-1}-\left(B_{n-2}-C_{n-2}\right)= \;\cdots\;=B_{n-1}-B_{n-2}+\cdots+(-1)^nB_1$.

Answer 2

La exponencial de la generación de la función de $B_n$ (la Campana números) está dada por $$ B(x)=\sum_{n=0}^{\infty}B_n\frac{x^n}{n!}=\exp(e^x-1)\etiqueta{1} $$ desde la Campana-los números de satisfacer la recurrencia $$ B_{n+1}=\sum_{k=0}^{n}\binom{n}{k} B_k;\quad B_0=B_1=1. $$ La exponencial de la generación de la función de $C_n$ está dado por $$ C(x)=\sum_{n=0}^{\infty}C_n\frac{x^n}{n!}=\exp(e^x-1-x).\la etiqueta{2} $$ Tenga en cuenta que $$ C(x)+C'(x)=B(x) $$ lo que implica que $$ B_n=C_n+C_{n+1}. \quad(n\geq 1) $$ En este punto vistazo a la última línea de la respuesta de user84413.