Przeczytaj

Liczby Catalana

RwBJWbd00ST5q

Ilustracja przedstawia trójkąt zbudowany z cyfr. Dla ułatwienia opiszemy trójkąt, zaczynając od jego wierzchołka, a kolejne sekwencje cyfr ułożonych w rzędy nazwiemy piętrami. Na wierzchołku trójkąta znajduje się jedynka, drugie piętro składa się z dwóch jedynek, trzecie z liczb 1, 2 i 1, czwarte z liczb 1, 3, 3 oraz 1, piąte z liczb: 1, 4, 6, 4 i 1, szóste z liczb: 1, 5, 10, 10, 5, 1, siódme: 1, 6, 15, 20, 15, 6, 1, ósme: 1, 7, 21, 35, 35, 21, 7, 1, dziewiąte: 1, 8, 28, 56, 70, 56, 28, 8, 1 i ostatnie, dziesiąte: 1, 9, 36, 84, 126, 126, 84, 36, 9, 1; W trójkącie zaznaczone zostały cyfry znajdujące się na wysokości tego trójkąta upuszczonej na podstawę tego trójkąta z wierzchołka, w którym znajduje się jedynka, są to cyfry kolejno, zaczynając od wierzchołka: 1, 2, 6, 20, siedemdziesiąt.

Rozpatrzmy środkowe liczby w trójkącie Pascala: $1$ , $2$ , $6$ , $20$ , $70$ , $\dots$

Zauważmy, że liczby te można podzielić odpowiednio przez: $1$ , $2$ , $3$ , $4$ , $5$ , $\dots$ i otrzymać ciąg liczb naturalnych: $1$ , $1$ , $2$ , $5$ , $14$ , $42$ , $123$ , $429$ , $\dots$

Tak utworzone liczby nazywamy liczbami Catalana, na cześć belgijskiego matematyka E. Catalana ( $1814$ – $1894$ ).

Każdy $n$ –ty wyraz ciągu liczb Catalana określony jest wzorem:

$c_{n} = \frac{1}{n + 1} (\begin{matrix} 2 n \\ n \end{matrix}) = \frac{(2 n)!}{(n + 1)! \cdot n!}$ dla $n \geq 0$

Liczby Catalana spełniają zależność:

$c_{n} = (\begin{matrix} 2 n \\ n \end{matrix}) - (\begin{matrix} 2 n \\ n + 1 \end{matrix})$ dla $n \geq 1$

Liczby te mają wiele interpretacji kombinatorycznych. Na przykład liczba $c_{n}$ wyraża liczbę sposobów podziału wielokąta wypukłego, mającego $n + 2$ boków, na różne trójkąty przy pomocy przekątnych nieprzecinających się wewnątrz wielokąta.

R1BNHZup5jQ3y

Ilustracja przedstawia trzy rzędy figur z wrysowanymi wewnątrz przekątnymi. W każdym rzędzie znajdują się identyczne figury. Pierwszy rząd opisany jako dwa przedstawia dwa kwadraty z wrysowanymi przekątnymi, w pierwszym poziomo, w drugim pionowo względem monitora. Drugi rząd opisany jako pięć przedstawia pięć pięciokątów z wrysowanymi wewnątrz każdego z nich dwiema przekątnymi, które wychodzą każdorazowo z jednego wierzchołka. Trzeci rząd opisany jako czternaście przedstawia czternaście sześciokątów z wrysowanymi w każdy z nich trzema przekątnymi we wszystkich możliwych kombinacjach.

Trójkąt Catalana to trójkąt liczbowy, w którym każdy element (oprócz pierwszego) jest równy sumie elementu stojącego powyżej oraz elementu stojącego po lewej stronie.

R1cEy3c0DnqBj

Ilustracja przedstawia trójkąt prostokątny zbudowany z siedmiu kolumn cyfr. Pierwsza kolumna od lewej będąca pionową przyprostokątną trójkąta składa się z siedmiu jedynek, druga kolumna, patrząc od góry składa się z cyfr:1, 2, 3, 4, 5, 6, trzecia kolumna to kolejno: 2, 5, 9, 14, 20. Czwarta kolumna to: 5, 14, 28, 48, piąta kolumna to: 14, 42, 90, szósta kolumna: 42 i 132 oraz ostatnia kolumna- siódma to liczba sto trzydzieści dwa.

Suma liczb każdego wiersza jest równa ostatniej liczbie w następnym rzędzie i jest równa liczbie Catalana.

RkqIBw0bHbOfu

Przykład 1

Znajdziemy ostatnią liczbę ósmego wiersza trójkąta Catalana.

Obliczamy sumę liczb stojących w siódmym wierszu. Ich suma będzie szukaną liczbą.

$1 + 6 + 20 + 48 + 90 + 132 + 132 = 429$

Odpowiedź:

Ostatnia liczba w ósmym wierszu trójkąta Catalana, to liczba Catalana $429$ .

Liczby Bella

Czy zdarzyło ci się zastanawiać, ile jest sposobów pogrupowania obiektów, jeśli są one rozróżnialne? Odpowiedź na to pytanie znalazł Eric Bell ( $1883$ – $1960$ ) – amerykański matematyk, autor powieści science–fiction.

RWxyrZ4gSIKfh

Ilustracja przedstawia trójkąt zbudowany z cyfr. W całym trójkącie jest siedem wierszy. Na wierzchołku jest cyfra 1, drugi wiersz: zero i jeden, trzeci wiersz: zero, jeden, jeden, czwarty wiersz: zero, jeden, trzy, jeden, piąty wiersz: zero, jeden, siedem, sześć, jeden, szósty wiersz: zero, jeden, piętnaście, dwadzieścia pięć, dziesięć, jeden i siódmy wiersz: zero, jeden, trzydzieści jeden, dziewięćdziesiąt, sześćdziesiąt pięć, piętnaście, jeden. Po prawej stronie zapisana została suma każdego z wierszy, kolejno od góry: jeden, jeden, dwa, pięć, piętnaście, pięćdziesiąt dwa, dwieście trzy.

Liczba możliwych pogrupowań nazywa się liczbą Bella. Kolejne liczby Bella to: $1$ , $1$ , $2$ , $5$ , $15$ , $52$ , $203$ , $877$ , $\dots$

Liczba Bellaliczba BellaLiczba Bella określa na przykład:

liczbę rozmieszczeń $n$ różnych obiektów w co najwyżej $n$ identycznych pudełkach,
liczba usadzeń $n$ osób dookoła co najwyżej $n$ stolików (gdy nieważny jest sposób usadzenia osób przy stoliku),
liczba różnych schematów rymowych w strofie $n$ –wersowej.

Przykład 2

Pokażemy, jak utworzyć trójkąt Bella, w którym w lewej kolumnie znajdują się kolejne liczby Bella:

Pierwsza liczba to $1$ .

W każdym następnym wierszu pierwsza liczba jest równa ostatniej z poprzedniego wiersza.

Pierwsza liczba w drugim wierszu to zatem $1$ .
Następne liczby znajdujemy, dodając ostatnią liczbę do liczby stojącej nad nią. Zatem na drugim miejscu w wierszu drugim zapiszemy liczbę: $1 + 1 = 2$ .
$1$
$1 2$

Trzeci wiersz zaczynamy od ostatniej liczby z wiersza drugiego, czyli $2$ .
Do liczby $2$ dodajemy liczbę stojącą powyżej, czyli $1$ . Otrzymujemy: $2 + 1 = 3$ .
Do $3$ dodajemy liczbę stojącą powyżej: $3 + 2 = 5$ .
$1$
$1 2$
$2 3 5$

Pierwszą liczbą czwartego wiersza jest $5$ (ostatnia liczba z wiersza $3$ ). Następnie: $5 + 2 = 7$ .
I dalej: $7 + 3 = 10$ . Ostatnia liczba to: $10 + 5 = 15$ .

Podobnie powstaje piąty wiersz i kolejne.
$1$
$1 2$
$2 3 5$
$5 7 10 15$
$15 20 27 37 52$
$\dots$

Liczby Faulhabera

Znamy już wzór na sumę $0$ , wzór na sumę $1$ , wzór na sumę $2$ i wzór na sumę $3$ potęg kolejnych liczb naturalnych.

1^{0} + 2^{0} + 3^{0} + \dots + n^{0} = n

1^{1} + 2^{1} + 3^{1} + \dots + n^{1} = \frac{n^{2} + n}{2}

1^{2} + 2^{2} + 3^{2} + \dots + n^{2} = \frac{1}{3} \cdot (n^{3} + \frac{3}{2} n^{2} + \frac{1}{2} n)

1^{3} + 2^{3} + 3^{3} + \dots + n^{3} = \frac{1}{4} \cdot (n^{4} + 2 n^{3} + n^{2})

Niemiecki matematyk Johann Faulhaber ( $1580$ – $1635$ ), zwany przez współczesnych Wielkim Matematykiem z Ulm, podał wzór na sumę wyższych potęg kolejnych liczb naturalnych.

1^{k - 1} + 2^{k - 1} + \dots + n^{k - 1} =

= \frac{1}{k} \cdot [n^{k} + (\begin{matrix} k \\ 1 \end{matrix}) \cdot n^{k - 1} \cdot \frac{1}{2} + (\begin{matrix} k \\ 2 \end{matrix}) \cdot n^{k - 1} \cdot \frac{1}{6} + (\begin{matrix} k \\ 3 \end{matrix}) \cdot n^{k - 3} \cdot 0 + \dots]

Zauważmy, że wyrażenie w nawiasie kwadratowym przypomina wzór dwumianowy Newtona. Brak tylko wyrazu wolnego, wyrazy mnożone są przez pewne stałe, zwane czasem liczbami Faulhabera.

$1$ , $\frac{1}{2}$ , $\frac{1}{6}$ , $0$ , $- \frac{1}{30}$ , $0$ , $\frac{1}{42}$ , $0$ , $\dots$

Przykład 3

Znajdziemy sumę sześcianów kolejnych liczb naturalnych, mniejszych od $101$ .

Oznaczmy: $S = 1^{3} + 2^{3} + \dots + 100^{3}$ .

Korzystamy ze wzoru: $1^{3} + 2^{3} + 3^{3} + \dots + n^{3} = \frac{1}{4} \cdot (n^{4} + 2 n^{3} + n^{2})$ .

Stąd:

$L = \frac{1}{4} \cdot (100^{4} + 2 \cdot 100^{3} + 100^{2})$

$L = \frac{1}{4} \cdot (100000000 + 2000000 + 10000) = 25502500$

Odpowiedź:

Suma sześcianów kolejnych liczb naturalnych mniejszych od $101$ to $25502500$ .

Słownik

liczba Bella

dla liczby naturalnej $n$ to liczba podzbiorów zbioru $\{1, 2, 3, \dots, n\}$

Wprowadzenie

Animacja

Liczby Catalana

Liczby Bella

Liczby Faulhabera

Słownik