Nombres de Bell

En matemàtiques combinatòries, els nombres de Bell compten les possibles particions d'un conjunt. Aquests nombres han estat estudiats pels matemàtics des del segle XIX, i les seves arrels es remunten al Japó medieval. En un exemple de la llei de l'eponímia de Stigler, reben el nom d'Eric Temple Bell, que va escriure sobre ells a la dècada de 1930.

Es denoten els números de campana $B_{n}$, on $n$ és un nombre enter superior o igual a zero. Començant per $B_{0}=B_{1}=1$, els primers números de Bell són

$1,1,2,5,15,52,203,877,4140,\dots$ (successió A000110 a l'OEIS).

El número de campana $B_{n}$ compta les diferents maneres de particionar un conjunt que té exactament $n$ elements, o equivalentment, les relacions d'equivalència sobre ell. $B_{n}$ també compta els diferents esquemes de rima per $n$-poemes en línia.

Les particions de conjunts es poden organitzar en un ordre parcial, mostrant que cada partició d'un conjunt de mida n "utilitza" una de les particions d'un conjunt de mida n − 1.

Comptant

Establir particions

Les 52 particions d'un conjunt amb 5 elements

En general, $B_{n}$ és el nombre de particions d'un conjunt de mida $n$. Una partició d'un conjunt $S$ es defineix com una família de subconjunts disjunts per parelles no buits de $S$ la unió del qual és $S$. Per exemple, $B_{3}=5$ perquè el conjunt de 3 elements $\{a,b,c\}$ es pot dividir de 5 maneres diferents:

$\{\{a\},\{b\},\{c\}\},$

$\{\{a\},\{b,c\}\},$

$\{\{b\},\{a,c\}\},$

$\{\{c\},\{a,b\}\},$

$\{\{a,b,c\}\}.$

Tal com suggereix la notació de conjunt anterior, no es considera l'ordenació dels subconjunts dins de la família; les particions ordenades es compten per una seqüència diferent de números, els números de campana ordenats. $B_{0}$ és 1 perquè hi ha exactament una partició del conjunt buit. Aquesta partició és en si mateix el conjunt buit; es pot interpretar com una família de subconjunts del conjunt buit, format per zero subconjunts. És ben cert que tots els subconjunts d'aquesta família són subconjunts no buits del conjunt buit i que són subconjunts disjunts per parelles del conjunt buit, perquè no hi ha subconjunts que tinguin aquestes propietats poc probables.

Les particions d'un conjunt corresponen un a un amb les seves relacions d'equivalència. Aquestes són relacions binàries que són reflexives, simètriques i transitives. La relació d'equivalència corresponent a una partició defineix dos elements com a equivalents quan pertanyen al mateix subconjunt de particions entre si. Per contra, cada relació d'equivalència correspon a una partició en classes d'equivalència. Per tant, els nombres de Bell també compten les relacions d'equivalència.

Factoritzacions

Si un número $N$ és un nombre enter positiu lliure de quadrats, el que significa que és el producte d'algun nombre $n$ de nombres primers diferents, doncs $B_{n}$ dóna el nombre de particions multiplicatives diferents de $N$. Aquestes són factoritzacions de $N$ en nombres superiors a un, tractant dues factoritzacions com a iguals si tenen els mateixos factors en un ordre diferent. Per exemple, 30 és el producte dels tres primers 2, 3 i 5, i té $B_{3}$=5 factoritzacions:

$30=2\times 15=3\times 10=5\times 6=2\times 3\times 5$

Esquemes de rimes

Els números de campana també compten els esquemes de rima d'un poema o estrofa de n línies. Un esquema de rima descriu quines línies rimen entre si, i per tant es pot interpretar com una partició del conjunt de línies en subconjunts rimats. Els esquemes de rima s'escriuen normalment com una seqüència de lletres romanes, una per línia, amb les línies rimades amb la mateixa lletra entre elles i amb les primeres línies de cada conjunt de rima etiquetades per ordre alfabètic. Així, els 15 possibles esquemes de rima de quatre línies són AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC i ABCD.

Permutacions

Els números de Bell apareixen en un problema de barreja de cartes esmentat a l'annex a Gardner 1978. Si es barreja una baralla de n cartes traient repetidament la carta superior i tornant-la a inserir en qualsevol lloc de la baralla (inclosa la seva posició original a la part superior de la baralla), amb exactament n repeticions d'aquesta operació, llavors hi ha nⁿ barreges diferents que es pot realitzar. D'aquests, el nombre que retorna la baralla al seu ordre original és exactament B_n. Així, la probabilitat que la baralla estigui en el seu ordre original després de remenar-la d'aquesta manera és B_n/nⁿ, que és significativament més gran que 1/n! probabilitat que descriuria una permutació uniformement aleatòria de la baralla.

Relacionats amb la barreja de cartes, hi ha altres problemes de comptar tipus especials de permutacions que també es responen amb els números de Bell. Per exemple, l' èsimo nombre de Bell és igual al nombre de permutacions en n elements en què no hi ha tres valors ordenats que tinguin els dos últims d'aquests tres consecutius. En una notació per a patrons de permutació generalitzats on els valors que han de ser consecutius s'escriuen al costat dels altres, i els valors que poden aparèixer de manera no consecutiva estan separats per un guió, aquestes permutacions es poden descriure com les permutacions que eviten el patró 1-23. Les permutacions que eviten els patrons generalitzats 12-3, 32-1, 3-21, 1-32, 3-12, 21-3 i 23-1 també es compten amb els números de Bell. Les permutacions en què cada patró 321 (sense restricció de valors consecutius) es pot estendre a un patró 3241 també es compten amb els números de Bell. No obstant això, els nombres de Bell creixen massa ràpidament per comptar les permutacions que eviten un patró que no s'ha generalitzat d'aquesta manera: segons la conjectura de Stanley-Wilf (ara provada), el nombre d'aquestes permutacions és individualment exponencial, i els nombres de Bell tenen una taxa de creixement asimptòtica més alta que aquesta.

Esquema triangular per als càlculs

Els números de Bell es poden calcular fàcilment creant l'anomenat triangle de Bell, també anomenat matriu d'Aitken o triangle de Peirce en honor a Alexander Aitken i Charles Sanders Peirce.

1. Començar pel número u. Posar això en una fila per si mateix. ( $x_{0,1}=1$ )
2. Iniciar una fila nova amb l'element més a la dreta de la fila anterior com a número més a l'esquerra ( $x_{i,1}\leftarrow x_{i-1,r}$ on r és l'últim element de la fila ( i -1)
3. Determinar els nombres que no estan a la columna de l'esquerra sumant el nombre a l'esquerra i el nombre a sobre del número a l'esquerra, és a dir, el nombre en diagonal cap amunt i a l'esquerra del nombre que estem calculant $(x_{i,j}\leftarrow x_{i,j-1}+x_{i-1,j-1})$
4. Repetir el pas tres fins que hi hagi una nova fila amb un número més que la fila anterior (feu el pas 3 fins que $j=r+1$ )
5. El número a l'esquerra d'una fila determinada és el número de campana d'aquesta fila ( $B_{i}\leftarrow x_{i,1}$ )

Aquí les cinc primeres files del triangle construït per aquestes regles:

${\begin{array}{l}1\\1&2\\2&3&5\\5&7&10&15\\15&20&27&37&52\end{array}}$

Els números de campana apareixen tant al costat esquerre com al dret del triangle.