Wikipedia

Triunghiul lui Bell

tablou triunghiular analog triunghiului lui Pascal

În matematică triunghiul lui Bell este un triunghi de numere analog cu triunghiul lui Pascal, elementele sale fiind numărul de partiții ale unei mulțimi în care un element dat este cel mai mare singleton. Este numit astfel datorită legăturii sale strânse cu numerele Bell⁠(d), care pot fi găsite pe ambele părți ale triunghiului și care sunt, la rândul lor, numite după Eric Temple Bell. După Martin Gardner[1], acest nume a fost sugerat de Jeffrey Shallit, a cărui lucrare despre același triunghi a fost publicată ulterior[2]. La rândul său, Shallit îi atribuie definiția triunghiului lui Cohn, Even, Menger și Hooper,[3] dar Cohn și colaboratorii săi nu a denumit astfel triunghiul.

Construcția triunghiului lui Bell

Triunghiul lui Bell a fost descoperit independent de mai mulți autori, începând cu Charles Sanders Peirce,[4] apoi de Alexander Aitken[5] și Cohn, Even, Menger și Hooper,[3] motiv pentru care a mai fost numit tabloul lui Aitken sau triunghiul lui Peirce.[6]

Valori

modificare

Surse diferite dau același triunghi în orientări diferite, unele in ordine inversă față de altele. De exemplu, Gardner[1] arată două orientări, ambele diferite de cea de aici. Într-un format similar cu cel al triunghiului lui Pascal și în ordinea din Online Encyclopedia of Integer Sequences (în română Enciclopedia online a șirurilor de întregi), primele rânduri ale sale sunt:[6] 

                    1
                 1     2
              2     3     5
           5     7    10    15
       15    20    27    37    52
    52    67    87   114   151   203
203   255   322   409   523   674   877

Construcție

modificare

Triunghiul lui Bell poate fi construit plasând numărul 1 pe prima sa poziție. După această plasare, valoarea cea mai din stânga din fiecare rând al triunghiului este completată prin copierea valorii din dreapta din rândul anterior. Pozițiile rămase din fiecare rând sunt completate cu o regulă foarte asemănătoare cu cea din triunghiul lui Pascal: sunt suma celor două valori din stânga și din stânga sus a poziției.

Astfel, după plasarea inițială a numărului 1 în rândul de sus, acesta este ultima poziție din rândul său și este copiat în poziția din stânga din rândul următor. A treia valoare din triunghi, 2, este suma celor două valori anterioare din stânga sus și din stânga acestuia. Ca ultimă valoare din rândul său, 2 este copiat în al treilea rând, iar procesul continuă în același mod.

Interpretare combinatorică

modificare

Numerele Bell de pe părțile din stânga și din dreapta triunghiului, arată numărul de moduri de partiționare a unei mulțimi finite în submulțimi, sau, echivalent, numărul de relații de echivalență pe mulțime. Sun și Wu[7] dau următoarea interpretare combinatorică a fiecărei valori din triunghi: fie An,k valoarea care este k poziții din stânga în rândul n al triunghiului, cu partea de sus a triunghiului notată A1,1. Apoi An,k indică numărul de partiții ale mulțimii {1, 2, ..., n + 1} în care elementul k + 1 este singurul element al mulțimii sale și fiecare element cu valoare mai mare se află într-o mulțime cu mai mult de un element. Adică k + 1 trebuie să fie cel mai mare singleton al partiției.

De exemplu, numărul 3 din mijlocul celui de-al treilea rând al triunghiului ar fi notat, în notația lor, drept A3,2 și indică numărul de partiții ale lui {1, 2, 3, 4}, în care 3 este cel mai mare element singleton. Există trei astfel de partiții:

{1}, {2, 4}, {3}
{1, 4}, {2}, {3}
{1, 2, 4}, {3}.

Partițiile rămase ale acestor patru elemente fie nu au 3 într-o mulțime de sine stătătoare, fie au un singleton al mulțimii mai mare {4}. În niciunul dintre cazuri nu sunt numărate în A3,2.

În aceeași notație, Sun și Wu [8] extind triunghiul cu o altă diagonală la stânga celorlalte valori ale sale, a numerelor An,0 = 1, 0, 1, 1, 4, 11, 41, 162, ...[9], care indică numărul partițiilor din aceeași mulțime de n + 1 articole, în care doar primul articol este un singleton. Triunghiul lor augmentat este[10] 

                       1
                    0     1
                 1     1     2
              1     2     3     5
           4     5     7    10    15
       11    15    20    27    37    52
    41    52    67    87   114   151   203
162   203   255   322   409   523   674   877

Acest triunghi poate fi construit similar cu versiunea originală a triunghiului lui Bell, dar cu o regulă diferită pentru începutul fiecărui rând: valoarea cea mai din stânga din fiecare rând este diferența dintre valorile din dreapta și din stânga ale rândului anterior.

O interpretare alternativă, dar mai tehnică, a numerelor din același triunghi augmentat este dată de Quaintance și Kwong.[11].

Diagonale și sumele pe rânduri

modificare

Diagonalele din stânga și din dreapta ale triunghiului Bell conțin ambele șirul 1, 1, 2, 5, 15, 52, ... al numerelor Bell (elementul inițial lipsește în cazul diagonalei din dreapta). Următoarea diagonală paralelă cu diagonala cea mai din dreapta dă șirul diferenței⁠(d) a două numere Bell consecutive, 1, 3, 10, 37, ..., iar fiecare diagonală paralelă ulterioară oferă succesiunea diferențelor diagonalelor precedente.

În acest fel, după cum a observat Aitken,[12] acest triunghi poate fi interpretat ca implementând formula de interpolare Gregory–Newton, care găsește coeficienții unui polinom din șirul valorilor sale la numere întregi consecutive folosind diferențe succesive. Această formulă seamănă foarte mult cu o relație de recurență care poate fi folosită pentru a defini numerele Bell.

Sumele fiecărui rând al triunghiului, 1, 3, 10, 37, ..., sunt aceeași succesiune de primele diferențe care apar în diagonala a doua de la dreapta a triunghiului.[13] Al n-lea număr din această secvență indică și numărul de partiții în submulțimi de n elemente, unde una dintre submulțimi se distinge de celelalte. De exemplu, există 10 moduri de a împărți trei elemente în submulțimi și apoi de a alege una dintre submulțimi.[14]

Construcții înrudite

modificare

Un triunghi de numere diferit, cu numerele Bell pe o singură parte și cu fiecare număr determinat ca o sumă ponderată a numerelor din apropiere din rândul anterior, a fost descris de Aigner.[15]

Note

modificare
  1. ^ a b Gardner, 1978
  2. ^ Shallit, 1980
  3. ^ a b Cohn ș.a., 1962
  4. ^ Peirce, 1880
  5. ^ Aitken, 1933
  6. ^ a b Șirul A011971 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
  7. ^ Sun, Wu, 2011
  8. ^ Sun, Wu, 2011
  9. ^ Șirul A000296 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
  10. ^ Șirul A106436 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
  11. ^ Quaintance, Kwong, 2013
  12. ^ Aitken, 1933
  13. ^ Gardner, 1978
  14. ^ Șirul A005493 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
  15. ^ Aigner, 1999

Bibliografie

modificare
  • en Aigner, Martin (), „A characterization of the Bell numbers”, Discrete Mathematics, 205 (1–3): 207–210, doi:10.1016/S0012-365X(99)00108-9  , MR 1703260 
  • en Aitken, Alexander C. (), „A problem in combinations”, Mathematical Notes, 28: 18–23, doi:10.1017/S1757748900002334   
  • en Cohn, Martin; Even, Shimon; Menger, Karl, Jr.; Hooper, Philip K. (), „Mathematical Notes: On the number of partitionings of a set of n distinct objects”, American Mathematical Monthly, 69 (8): 782–785, doi:10.2307/2310780, JSTOR 2310780, MR 1531841 
  • en Gardner, Martin (), „The Bells: versatile numbers that can count partitions of a set, primes and even rhymes”, Scientific American, 238: 24–30, Bibcode:1978SciAm.238e..24G, doi:10.1038/scientificamerican0578-24 . Reprinted with an addendum as "The Tinkly Temple Bells", Chapter 2 of Fractal Music, Hypercards, and more ... Mathematical Recreations from Scientific American, W. H. Freeman, 1992, pp. 24–38.
  • en Peirce, C. S. (), „On the algebra of logic”, American Journal of Mathematics, 3 (1): 15–57, doi:10.2307/2369442, JSTOR 2369442 . The triangle is on p. 48.
  • en Quaintance, Jocelyn; Kwong, Harris (), „A combinatorial interpretation of the Catalan and Bell number difference tables” (PDF), Integers, 13: A29 
  • en Shallit, Jeffrey (), „A triangle for the Bell numbers”, A collection of manuscripts related to the Fibonacci sequence (PDF), Santa Clara, Calif.: Fibonacci Association, pp. 69–71, MR 0624091 
  • en Sun, Yidong; Wu, Xiaojuan (), „The largest singletons of set partitions”, European Journal of Combinatorics, 32 (3): 369–382, arXiv:1007.1341  , doi:10.1016/j.ejc.2010.10.011, MR 2764800 

Legături externe

modificare
  Portal Matematică
Adus de la https://ro.wikipedia.org/w/index.php?title=Triunghiul_lui_Bell&oldid=15806713