Números combinatorios clásicos · Definición

Número de Bell

combinatoria enumerativanúmeros combinatorios clásicos

Antes de empezar necesitas conocer

Los números de Bell aparecen al contar agrupaciones sin orden de elementos distinguibles. Se relacionan directamente con los números de Stirling de segunda especie.

Definición

El número de Bell \(B_n\) es la cantidad de particiones de un conjunto de \(n\) elementos, es decir, de formas de dividirlo en subconjuntos no vacíos disjuntos.

\[B_n=\sum_{k=0}^{n-1}\binom{n-1}{k}B_k\]

Por definición, \(B_n=\sum_{k=0}^{n}S(n,k)\), donde \(S(n,k)\) es el número de Stirling de segunda especie. Así, \(B_0=1\), \(B_1=1\), \(B_2=2\), \(B_3=5\) y \(B_4=15\). La sucesión satisface la recurrencia de Bell, que permite calcularla sin conocer los Stirling uno a uno.

Para \(n=3\), el conjunto \(\{a,b,c\}\) admite cinco particiones: una con un bloque \(\{a,b,c\}\), tres con un bloque de dos y otro de uno, y una con tres bloques unitarios. Por tanto \(B_3=1+3+1=5\), que coincide con la suma \(S(3,1)+S(3,2)+S(3,3)\).

Un error típico es confundir \(B_n\) con el número de Stirling \(S(n,k)\) fijando un \(k\) concreto, o contar particiones ordenadas de los bloques. Los bloques de una partición no tienen orden, así que no deben multiplicarse por factoriales.

Para pensar

¿Por qué reordenar los bloques de una partición no produce una partición nueva?

Porque una partición es un conjunto de subconjuntos y un conjunto no tiene orden, así que reordenar sus bloques da la misma partición.

Ejercicios 10

  1. ¿Cuál es el valor de \(B_2\)?
  2. ¿Cuál de estas colecciones es una partición de \(\{1,2,3\}\)?
  3. ¿Cuál es el valor de \(B_0\)?
  4. ¿Cuántas particiones tiene un conjunto de 3 elementos en total?
  5. ¿Qué expresión relaciona \(B_n\) con los números de Stirling de segunda especie?
  6. Calcula \(B_4\) sabiendo que \(S(4,1)=1\), \(S(4,2)=7\), \(S(4,3)=6\) y \(S(4,4)=1\).
  7. Usando \(B_0=1\), \(B_1=1\) y \(B_2=2\), calcula \(B_3\) con la recurrencia de Bell.
  8. ¿Cuántas particiones de \(\{1,2,3,4\}\) tienen exactamente dos bloques?
  9. Demuestra que \(B_5=52\) sumando \(S(5,k)\) para \(k=1,\dots,5\), sabiendo que \(S(5,1)=1\), \(S(5,2)=15\), \(S(5,3)=25\), \(S(5,4)=10\) y \(S(5,5)=1\). ¿Cuál es el paso que da el resultado correcto?
  10. Si \(B_n\) cuenta particiones de un conjunto de \(n\) elementos, ¿cuál es el valor de \(B_4\) según la recurrencia \(B_4=\sum_{k=0}^{3}\binom{3}{k}B_k\) con \(B_0=1\), \(B_1=1\), \(B_2=2\), \(B_3=5\)?

Referencias

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.