Trójkąt dzwonkowy
W matematyce trójkąt Bella jest trójkątem liczb analogicznym do trójkąta Pascala , którego wartości zliczają podziały zbioru , w którym dany element jest największym singletonem . Jego nazwa pochodzi od jego bliskiego związku z liczbami Bella , które można znaleźć po obu stronach trójkąta i które z kolei zostały nazwane na cześć Erica Temple Bella . Trójkąt Bella został odkryty niezależnie przez wielu autorów, poczynając od Charlesa Sandersa Peirce'a ( 1880 ), a także Alexandra Aitkena ( 1933 ) oraz Cohna i in. (1962) iz tego powodu jest również nazywany tablicą Aitkena lub trójkątem Peirce'a .
Wartości
Różne źródła podają ten sam trójkąt w różnych orientacjach, niektóre odwrócone względem siebie. W formacie podobnym do trójkąta Pascala iw kolejności podanej w Online Encyclopedia of Integer Sequences , kilka pierwszych wierszy to:
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
Budowa
Trójkąt Bell można zbudować, umieszczając cyfrę 1 na jej pierwszej pozycji. Po tym umieszczeniu najbardziej wysunięta na lewo wartość w każdym rzędzie trójkąta jest wypełniana przez skopiowanie najbardziej wysuniętej na prawo wartości z poprzedniego wiersza. Pozostałe pozycje w każdym rzędzie są wypełniane według zasady bardzo podobnej do trójkąta Pascala : są sumą dwóch wartości po lewej i lewej górnej stronie pozycji.
Tak więc, po początkowym umieszczeniu cyfry 1 w górnym rzędzie, jest to ostatnia pozycja w swoim rzędzie i jest kopiowana do skrajnej lewej pozycji w następnym rzędzie. Trzecia wartość w trójkącie, 2, jest sumą dwóch poprzednich wartości po lewej i lewej stronie tego trójkąta. Jako ostatnia wartość w swoim wierszu, 2 jest kopiowane do trzeciego wiersza, a proces jest kontynuowany w ten sam sposób.
Interpretacja kombinatoryczna
liczby Bell po lewej i prawej stronie trójkąta zliczają liczbę sposobów podziału skończonego zbioru na podzbiory lub równoważnie liczbę relacji równoważności na zbiorze. Sun i Wu (2011) podają następującą kombinatoryczną interpretację każdej wartości w trójkącie. Idąc za Sun i Wu, niech A n,k oznacza wartość, która jest k pozycji od lewej w n -tym rzędzie trójkąta, gdzie wierzchołek trójkąta oznaczymy jako A 1,1 . Wtedy A n,k zlicza liczbę podziałów zbioru {1, 2, ..., n + 1}, w którym element k + 1 jest jedynym elementem swojego zbioru, a każdy element o wyższym numerze jest w zbiorze więcej niż jednego elementu. Oznacza to, że k + 1 musi być największym singletonem partycji.
Na przykład liczba 3 w środku trzeciego rzędu trójkąta byłaby oznaczona, w ich notacji, jako A 3,2 i zlicza liczbę partycji {1, 2, 3, 4}, w których 3 to największy element singletonowy. Istnieją trzy takie partycje:
- {1}, {2, 4}, {3}
- {1, 4}, {2}, {3}
- {1, 2, 4}, {3}.
Pozostałe partycje tych czterech elementów albo nie mają same 3 w zbiorze, albo mają większy zbiór singletonowy {4} iw żadnym przypadku nie są liczone w A 3,2 .
W tej samej notacji Sun i Wu (2011) powiększają trójkąt o kolejną przekątną na lewo od jego innych wartości, liczb
liczenie partycji tego samego zestawu n + 1 elementów, w których tylko pierwszy element jest singletonem. Ich powiększony trójkąt to
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
Ten trójkąt może być skonstruowany podobnie do oryginalnej wersji trójkąta Bella, ale z inną zasadą rozpoczynania każdego rzędu: wartość najbardziej wysunięta na lewo w każdym rzędzie jest różnicą wartości najbardziej wysuniętych na prawo i na lewo z poprzedniego rzędu.
Alternatywną, ale bardziej techniczną interpretację liczb w tym samym powiększonym trójkącie podaje Quaintance & Kwong (2013) .
Sumy przekątnych i wierszy
Skrajne lewe i prawe przekątne trójkąta Bella zawierają sekwencję 1, 1, 2, 5, 15, 52, ... liczb Bella ( z brakującym elementem początkowym w przypadku skrajnej prawej przekątnej). Następna przekątna równoległa do skrajnej prawej przekątnej daje sekwencję różnic dwóch kolejnych liczb Bella, 1, 3, 10, 37, ..., a każda kolejna przekątna równoległa daje sekwencję różnic poprzednich przekątnych.
W ten sposób, jak zauważył Aitken (1933) , trójkąt ten można interpretować jako implementację wzoru interpolacji Gregory'ego-Newtona , który znajduje współczynniki wielomianu z sekwencji jego wartości w kolejnych liczbach całkowitych za pomocą kolejnych różnic. Ta formuła bardzo przypomina relację rekurencyjną , której można użyć do zdefiniowania liczb Bella.
Sumy każdego rzędu trójkąta, 1, 3, 10, 37, ..., to ta sama sekwencja pierwszych różnic pojawiających się na drugiej od prawej przekątnej trójkąta. n - ta liczba w tym ciągu zlicza również liczbę podziałów n elementów na podzbiory, z których jeden z podzbiorów jest odróżniony od pozostałych; na przykład istnieje 10 sposobów podzielenia trzech elementów na podzbiory, a następnie wybrania jednego z podzbiorów.
Powiązane konstrukcje
Aigner (1999) opisał inny trójkąt liczb, z liczbami Bella tylko po jednej stronie i z każdą liczbą określoną jako ważona suma sąsiednich liczb w poprzednim rzędzie .
Notatki
- Aigner, Martin (1999), „Charakterystyka liczb Bella” , Matematyka dyskretna , 205 (1–3): 207–210, doi : 10.1016 / S0012-365X (99) 00108-9 , MR 1703260 .
- Aitken, AC (1933), „Problem w kombinacjach”, Mathematical Notes , 28 : 18–23, doi : 10.1017 / S1757748900002334 .
- Cohn, Martin; Nawet Szymon ; Menger, Karl, Jr .; Hooper, Philip K. (1962), „Notatki matematyczne: o liczbie podziałów zbioru n różnych obiektów”, American Mathematical Monthly , 69 (8): 782–785, doi : 10,2307/2310780 , JSTOR 2310780 , MR 1531841 .
- Gardner, Martin (1978), „The Bells: wszechstronne liczby, które mogą liczyć partycje zbioru, liczby pierwsze, a nawet rymy”, Scientific American , 238 : 24–30, Bibcode : 1978SciAm.238e..24G , doi : 10.1038/scientificamerican0578 -24 . Przedrukowano z dodatkiem jako „The Tinkly Temple Bells”, rozdział 2 Fractal Music, Hypercards i nie tylko ... Mathematical Recreations from Scientific American , WH Freeman, 1992, s. 24–38.
- Peirce, CS (1880), „O algebrze logiki”, American Journal of Mathematics , 3 (1): 15–57, doi : 10.2307/2369442 , JSTOR 2369442 . Trójkąt jest na str. 48.
- Znajomość, Jocelyn; Kwong, Harris (2013), „Kombinatoryczna interpretacja tabel różnic liczbowych katalońskich i Bell” (PDF) , liczby całkowite , 13 : A29 .
- Shallit, Jeffrey (1980), „Trójkąt dla liczb Bell”, Zbiór rękopisów związanych z ciągiem Fibonacciego (PDF) , Santa Clara, Kalifornia: Stowarzyszenie Fibonacciego, s. 69–71, MR 0624091 .
- Słońce, Yidong; Wu, Xiaojuan (2011), „Największe singletony zestawów partycji”, European Journal of Combinatorics , 32 (3): 369–382, arXiv : 1007,1341 , doi : 10,1016/j.ejc.2010.10.011 , MR 2764800 , S2CID 30627275 .