Kalkulator liczb Stirlinga

Witaj w Kalkulatorze liczb Stirlinga, wszechstronnym narzędziu kombinatorycznym do obliczania liczb Stirlinga pierwszego rodzaju (bezznakowe — permutacje na cykle) oraz drugiego rodzaju (podziały zbioru na niepuste podzbiory). Dzięki interaktywnym wizualizacjom trójkątów, wyprowadzeniom rekurencyjnym krok po kroku, wykresom rozkładu słupkowego i głębokim interpretacjom kombinatorycznym, kalkulator ten jest przeznaczony dla studentów, nauczycieli, badaczy i programistów, którzy potrzebują szybkich, dokładnych wyników w kontekście edukacyjnym.

Czym są liczby Stirlinga?

Liczby Stirlinga to dwie rodziny liczb, które naturalnie pojawiają się w kombinatoryce, algebrze i analizie. Nazwane na cześć szkockiego matematyka Jamesa Stirlinga (1692–1770), stanowią pomost między silniami, współczynnikami dwumianowymi i tożsamościami wielomianowymi. Chociaż są mniej znane niż trójkąt Pascala, są równie fundamentalne i występują w całej matematyce dyskretnej.

Liczby Stirlinga pierwszego rodzaju

Bezznakowe liczby Stirlinga pierwszego rodzaju, oznaczane jako \(|s(n,k)|\) lub \(\left[{n \atop k}\right]\), określają liczbę permutacji \(n\) elementów, które rozkładają się na dokładnie \(k\) rozłącznych cykli.

Intuicja: Rozważmy, gdzie trafia element \(n\). Albo jest on wstawiany do jednego z istniejących cykli (istnieje \(n-1\) pozycji do jego wstawienia, po jednej przed każdym z \(n-1\) pozostałych elementów) — co daje składnik \((n-1)\cdot|s(n-1,k)|\) — albo tworzy on swój własny nowy 1-cykl, co daje \(|s(n-1,k-1)|\).

Kluczowe fakty:

• \(|s(n,1)| = (n-1)!\) — permutacje cykliczne (jeden duży cykl)
• \(|s(n,n)| = 1\) — permutacja identycznościowa (same punkty stałe)
• \(|s(n,n-1)| = \binom{n}{2}\) — jedna transpozycja
• \(\sum_{k=0}^{n} |s(n,k)| = n!\) — całkowita liczba permutacji

Liczby Stirlinga drugiego rodzaju

Liczby Stirlinga drugiego rodzaju, oznaczane jako \(S(n,k)\) lub \(\left\{{n \atop k}\right\}\), określają liczbę sposobów podziału zbioru \(n\) elementów na dokładnie \(k\) niepustych podzbiorów.

Intuicja: Rozważmy, gdzie trafia element \(n\). Albo dołącza on do jednego z \(k\) istniejących podzbiorów (\(k\) wyborów) — co daje składnik \(k \cdot S(n-1,k)\) — albo tworzy on swój własny nowy podzbiór jednoelementowy, co daje \(S(n-1,k-1)\).

Kluczowe fakty:

• \(S(n,1) = 1\) — tylko jeden sposób: wszystkie elementy w jednym zbiorze
• \(S(n,n) = 1\) — tylko jeden sposób: każdy element jest osobnym podzbiorem
• \(S(n,2) = 2^{n-1} - 1\) — sposoby na podział na dwa niepuste podzbiory
• \(S(n,n-1) = \binom{n}{2}\) — wybór pary dzielącej podzbiór
• \(\sum_{k=0}^{n} S(n,k) = B(n)\) — n-ta liczba Bella

Jawny wzór (drugi rodzaj)

Jak korzystać z tego kalkulatora

1. Wprowadź n: Całkowita liczba elementów (od 0 do 200).
2. Wprowadź k: Liczba cykli (pierwszy rodzaj) lub podzbiorów (drugi rodzaj), przy czym 0 ≤ k ≤ n.
3. Wybierz rodzaj: Wybierz pierwszy rodzaj, drugi rodzaj lub oba dla porównania obok siebie.
4. Oblicz: Kliknij "Oblicz liczby Stirlinga", aby zobaczyć wyniki z wyprowadzeniem krok po kroku, wizualizacją trójkąta i wykresem rozkładu.

Porównanie: Pierwszy rodzaj vs Drugi rodzaj

Zastosowania liczb Stirlinga

Konwersja wielomianowa

Liczby Stirlinga łączą różne bazy wielomianowe:

• Silnia górna: \(x^{(n)} = \sum_{k} |s(n,k)|\, x^k\)
• Zwykła potęga: \(x^n = \sum_{k} S(n,k)\, x^{\underline{k}}\) (silnia dolna)

Prawdopodobieństwo i statystyka

Liczby Stirlinga pojawiają się w obliczaniu momentów rozkładów prawdopodobieństwa, szczególnie przy konwersji między momentami zwykłymi a silniowymi. Są niezbędne w analizie losowych permutacji i problemach zajętości.

Informatyka

W analizie algorytmów liczby Stirlinga występują przy liczeniu sposobów rozmieszczenia obiektów w kontenerach, analizie tablic mieszających oraz badaniu losowych permutacji. Drugi rodzaj odnosi się bezpośrednio do zliczania funkcji surjektywnych: liczba funkcji "na" ze zbioru n-elementowego w zbiór k-elementowy wynosi \(k!\, S(n,k)\).

Teoria liczb

Liczby Stirlinga łączą się z liczbami Bernoulliego, liczbami harmonicznymi i różnymi tożsamościami sumacyjnymi. Pojawiają się w rachunku różnic skończonych oraz we wzorze Eulera-Maclaurina.

Często zadawane pytania

Czym są liczby Stirlinga pierwszego rodzaju?

Bezznakowe liczby Stirlinga pierwszego rodzaju, oznaczane jako |s(n,k)|, określają liczbę permutacji n elementów, które rozkładają się na dokładnie k rozłącznych cykli. Spełniają one zależność rekurencyjną |s(n,k)| = (n−1)·|s(n−1,k)| + |s(n−1,k−1)| przy |s(0,0)| = 1. Sumy wierszy dają n!, ponieważ każda permutacja posiada określoną liczbę cykli.

Czym są liczby Stirlinga drugiego rodzaju?

Liczby Stirlinga drugiego rodzaju, oznaczane jako S(n,k), określają liczbę sposobów podziału zbioru n elementów na dokładnie k niepustych podzbiorów. Spełniają one zależność rekurencyjną S(n,k) = k·S(n−1,k) + S(n−1,k−1) przy S(0,0) = 1. Sumy wierszy dają liczby Bella B(n).

Jaka jest różnica między liczbami Stirlinga pierwszego i drugiego rodzaju?

Pierwszy rodzaj (bezznakowy) liczy permutacje z k cyklami — kolejność wewnątrz każdego cyklu ma znaczenie. Drugi rodzaj liczy podziały zbioru na k podzbiorów — kolejność wewnątrz podzbiorów nie ma znaczenia. Są one powiązane poprzez odwracanie macierzy: trójkąt liczb Stirlinga pierwszego rodzaju ze znakiem jest odwrotnością trójkąta liczb drugiego rodzaju.

Jak liczby Stirlinga są wykorzystywane w matematyce?

Liczby Stirlinga pojawiają się w konwersji wielomianów między silniami dolnymi/górnymi a zwykłymi potęgami, w obliczaniu momentów rozkładów prawdopodobieństwa, w tożsamościach kombinatorycznych, w teorii liczb oraz w analizie algorytmów.

Jaki jest związek między liczbami Stirlinga a liczbami Bella?

n-ta liczba Bella B(n) jest równa sumie wszystkich liczb Stirlinga drugiego rodzaju w wierszu n: B(n) = Σ S(n,k) dla k = 0 do n. Liczby Bella określają całkowitą liczbę podziałów zbioru n elementów na dowolną liczbę niepustych podzbiorów.

Czy istnieje jawny wzór na liczby Stirlinga?

Tak, liczby drugiego rodzaju mają jawny wzór oparty na zasadzie włączania-wyłączania: S(n,k) = (1/k!) Σ (−1)^(k−j) C(k,j) j^n dla j = 0 do k. Liczby pierwszego rodzaju można obliczyć za pomocą rekurencji lub poprzez powiązanie z silniami górnymi.

Dodatkowe zasoby

• Liczby Stirlinga pierwszego rodzaju - Wikipedia (EN)
• Liczby Stirlinga drugiego rodzaju - Wikipedia (EN)
• OEIS A008277 - Liczby Stirlinga drugiego rodzaju
• OEIS A130534 - Bezznakowe liczby Stirlinga pierwszego rodzaju