Dwunasty sposób

W kombinatoryce dwunastokrotny sposób jest systematyczną klasyfikacją 12 powiązanych problemów wyliczeniowych dotyczących dwóch skończonych zbiorów, które obejmują klasyczne problemy liczenia permutacji , kombinacji , multizbiorów i podziałów zbioru lub liczby . Pomysł klasyfikacji przypisuje się Gian-Carlo Rota , a nazwę zasugerował Joel Spencer .

Przegląd

Niech N i X będą skończonymi zbiorami . Niech ${\ displaystyle n = | N |}$ i ${\ Displaystyle x=|X|}$ będzie licznością zbiorów. Zatem N jest zbiorem n , a X jest zbiorem x .

${\ Displaystyle f: N \ do X}$ wyliczenie klas równoważności funkcji → .

Funkcje podlegają jednemu z trzech następujących ograniczeń:

1. Brak warunku: każde a w N może być wysłane przez f do dowolnego b w X i każde b może wystąpić wiele razy.
2. f jest iniekcyjne : każda wartość dla $b$ w N musi być od każdej innej, więc każde w może wystąpić co najwyżej raz na obrazie f
3. f jest suriekcją : dla każdego b w X musi istnieć co najmniej jedno a w N takie, że ${\ Displaystyle f (a) = b}$ , a zatem każde b wystąpi co najmniej raz na obrazie f .

(Warunek „ f jest bijektywna ” jest tylko opcją, gdy ${\ displaystyle n = x}$ ; ale wtedy jest równoważny zarówno „ f jest iniekcyjne”, jak i „ f jest surjektywne”).

Istnieją cztery różne relacje równoważności , które można zdefiniować na zbiorze funkcji f od N do X :

1. równość;
2. równość do permutacji N ; _ _
3. równość do permutacji X ;
4. równość aż do permutacji N i X .

Trzy warunki dotyczące funkcji i cztery relacje równoważności można sparować na 3 × 4 = 12 sposobów.

Dwanaście problemów liczenia klas równoważności funkcji nie wiąże się z tymi samymi trudnościami i nie ma jednej systematycznej metody ich rozwiązywania. Dwa z problemów są trywialne (liczba klas równoważności wynosi 0 lub 1), pięć problemów ma rozwiązanie w postaci multiplikatywnego wzoru n i x , a pozostałe pięć problemów ma rozwiązanie w postaci funkcji kombinatorycznych ( liczby Stirlinga i funkcja podziału dla danej liczby części).

Włączenie klasycznych problemów z wyliczaniem do tego ustawienia jest następujące.

• Zliczanie n -permutacji (tj. częściowych permutacji lub sekwencji bez powtórzeń) X jest równoważne zliczaniu funkcji iniekcyjnych N → X .
• Liczenie n -kombinacji X jest równoważne zliczaniu funkcji iniekcyjnych N → X aż do permutacji N .
• Zliczanie permutacji zbioru X jest równoważne zliczaniu funkcji iniekcyjnych N → X , gdy n = x, a także liczeniu funkcji surjekcyjnych N → X , gdy n = x .
• Zliczanie multizbiorów o rozmiarze n (znanych również jako n - kombinacje z powtórzeniami) elementów w X jest równoważne zliczaniu wszystkich funkcji N → X aż do permutacji N .
• Liczenie części zbioru N na x podzbiorów jest równoważne zliczaniu wszystkich funkcji suriekcyjnych N → X aż do permutacji X .
• Liczenie kompozycji liczby n na x części jest równoważne zliczaniu wszystkich funkcji suriekcyjnych N → X aż do permutacji N .

Punkty widzenia

Różne problemy w dwunastokrotny sposób można rozpatrywać z różnych punktów widzenia.

Kule i pudełka

Tradycyjnie wiele problemów w dwunastokrotny sposób było formułowanych w kategoriach umieszczania kul w pudełkach (lub podobnej wizualizacji) zamiast definiowania funkcji. Zbiór N można utożsamiać ze zbiorem kulek, a X ze zbiorem pudełek; funkcja ƒ : N → X opisuje następnie sposób rozmieszczenia piłek w pudełkach, mianowicie poprzez umieszczenie każdej piłki a w pudełku ƒ ( a ). Funkcja przypisuje unikalny obraz do każdej wartości w swojej dziedzinie; ta właściwość jest odzwierciedlona przez właściwość, że dowolna kula może trafić tylko do jednego pudełka (wraz z wymogiem, aby żadna kula nie pozostawała poza pudełkami), podczas gdy każde pudełko może pomieścić dowolną liczbę piłek. Wymaganie dodatkowo ƒ , aby było iniekcyjne, oznacza zakaz umieszczania więcej niż jednej piłki w jednym pudełku, podczas gdy wymaganie, aby ƒ było surjekcją, oznacza naleganie, aby każde pudełko zawierało co najmniej jedną piłkę.

Zliczanie permutacji modulo N lub X jest odzwierciedlane przez nazywanie odpowiednio kulek lub pudełek „nie do odróżnienia”. Jest to nieprecyzyjne sformułowanie, mające na celu wskazanie, że różnych konfiguracji nie należy liczyć oddzielnie, jeśli jedną można przekształcić w drugą przez zamianę kulek lub pudełek. Ta możliwość transformacji jest sformalizowana przez działanie przez permutacje.

Próbowanie

Innym sposobem myślenia o niektórych przypadkach jest dobór próby w statystyce . Wyobraźmy sobie populację X elementów (lub osób), z których wybieramy N . Zwykle opisywane są dwa różne schematy, znane jako „ pobieranie próbek z zastępstwem ” i „ pobieranie próbek bez zastępowania ”. W pierwszym przypadku (dobór próby z zamianą) po wybraniu elementu umieszczamy go z powrotem w populacji, abyśmy mogli wybrać go ponownie. W rezultacie każdy wybór jest niezależny spośród wszystkich innych wyborów, a zbiór próbek jest technicznie określany jako niezależny identycznie rozłożony . Jednak w tym drugim przypadku po wybraniu przedmiotu odkładamy go na bok, aby nie móc wybrać go ponownie. Oznacza to, że akt wyboru przedmiotu ma wpływ na wszystkie kolejne wybory (konkretnego przedmiotu nie można zobaczyć ponownie), więc nasze wybory są od siebie zależne.

Drugie rozróżnienie między schematami pobierania próbek dotyczy tego, czy kolejność ma znaczenie. Na przykład, jeśli mamy dziesięć przedmiotów, z których wybieramy dwa, to wybór (4,7) jest inny niż (7,4), jeśli kolejność ma znaczenie; z drugiej strony, jeśli kolejność nie ma znaczenia, to wybory (4,7) i (7,4) są równoważne. (Innym sposobem myślenia o tym jest posortowanie każdego wyboru według numeru elementu i wyrzucenie wszelkich duplikatów, które wynikają).

Pierwsze dwa wiersze i kolumny poniższej tabeli odpowiadają pobieraniu próbek ze zwracaniem i bez zwracania, z uwzględnieniem kolejności i bez. Przypadki pobierania próbek z zamianą znajdują się w kolumnie oznaczonej „Dowolne f ”, natomiast przypadki pobierania próbek bez zwracania znajdują się w kolumnie oznaczonej „Iniekcja f ”. Przypadki, w których kolejność ma znaczenie, znajdują się w wierszu oznaczonym jako „Wyraźne”, a przypadki, w których kolejność nie ma znaczenia, znajdują się w wierszu oznaczonym jako „S _n orbity”. Każdy wpis w tabeli wskazuje, ile różnych zestawów wyborów istnieje w określonym schemacie próbkowania. Trzy z tych wpisów w tabeli odpowiadają również rozkładom prawdopodobieństwa. Próbkowanie z zastępowaniem , w którym kolejność jest porównywalna z opisywaniem łącznego rozkładu N oddzielnych losowych zmienne , każda z rozkładem jakościowym X. Próbkowanie z zastępowaniem, w przypadku gdy kolejność nie ma znaczenia, jest jednak porównywalne z opisywaniem pojedynczego rozkładu wielomianowego N losuje z kategorii X -krotnej, w której liczy się tylko widoczna liczba każdej kategorii. Próbkowanie bez zamiany, gdy kolejność nie ma znaczenia, jest porównywalne z pojedynczym wielowymiarowym rozkładem hipergeometrycznym . Próbkowanie bez zamiany, gdzie kolejność ma znaczenie, nie wydaje się odpowiadać rozkładowi prawdopodobieństwa. Należy zauważyć, że we wszystkich przypadkach „iniekcyjnych” (tj. próbkowania bez zwracania) liczba zestawów wyborów wynosi zero, chyba że N ≤ X . („Porównywalne” w powyższych przypadkach oznacza, że ​​każdy element przestrzeni próbki odpowiedniego rozkładu odpowiada osobnemu zestawowi wyborów, stąd liczba w odpowiednim polu wskazuje wielkość przestrzeni próbki dla danego rozkładu).

Z punktu widzenia próbkowania kolumna „Surjektywne f ” jest nieco dziwna: zasadniczo pobieramy próbki z wymianą, dopóki nie wybierzemy każdego elementu przynajmniej raz. Następnie liczymy, ile dokonaliśmy wyborów, a jeśli nie jest równe N , wyrzucamy cały zestaw i powtarzamy. Jest to z grubsza porównywalne z problemem kolekcjonera kuponów , w którym proces polega na „zbieraniu” (poprzez próbkowanie z wymianą) zbioru X kupony, dopóki każdy kupon nie zostanie wyświetlony przynajmniej raz. Zauważ, że we wszystkich przypadkach „surjektywnych” liczba zestawów wyborów wynosi zero, chyba że N ≥ X .

Etykietowanie, selekcja, grupowanie

Funkcję ƒ : N → X można rozpatrywać z perspektywy X lub N . Prowadzi to do różnych poglądów:

• funkcja ƒ oznacza każdy element N przez element X .
• funkcja ƒ wybiera (wybiera) element zbioru X dla każdego elementu N , w sumie n wyborów.
• funkcja ƒ grupuje razem elementy N , które są odwzorowane na ten sam element X .

Te punkty widzenia nie pasują jednakowo do wszystkich przypadków. Punkty widzenia etykietowania i selekcji nie są dobrze kompatybilne z permutacją elementów X , ponieważ zmienia to etykiety lub selekcję; z drugiej strony punkt widzenia grupowania nie daje pełnych informacji o konfiguracji, chyba że elementy X mogą być dowolnie permutowane. Punkty widzenia etykietowania i wyboru są mniej więcej równoważne, gdy N nie jest permutowany, ale kiedy jest, punkt widzenia selekcji jest bardziej odpowiedni. Selekcję można wtedy postrzegać jako selekcję nieuporządkowaną: dokonywany jest pojedynczy wybór (wielo)zbioru n elementów z X.

Etykietowanie i selekcja z powtórzeniami lub bez

Postrzegając ƒ jako etykietę elementów N , te ostatnie można traktować jako ułożone w sekwencji, a etykiety z X jako kolejno im przypisywane. Wymóg, aby ƒ był wstrzykiwany, oznacza, że ​​żadna etykieta nie może być użyta po raz drugi; wynikiem jest sekwencja etykiet bez powtórzeń . W przypadku braku takiego wymogu stosuje się termin „sekwencje z powtórzeniami”, co oznacza, że ​​etykiety mogą być używane więcej niż jeden raz (chociaż dozwolone są również sekwencje, które są bez powtórzeń).

Kiedy postrzegamy ƒ jako nieuporządkowaną selekcję elementów X , stosuje się ten sam rodzaj rozróżnienia. Jeśli ƒ musi być iniekcyjne, to wybór musi obejmować n różnych elementów X , więc jest to podzbiór X o rozmiarze n , zwany także n -kombinacją . Bez wymogu jeden i ten sam element X może występować wielokrotnie w selekcji, a wynikiem jest multiset o rozmiarze n elementów z X , zwana także n - multikombinacją lub n - kombinacją z powtórzeniami.

Wymóg, aby ƒ był suriekcją, z punktu widzenia elementów etykietujących N , oznacza, że ​​każda etykieta ma być użyta przynajmniej raz; z punktu widzenia selekcji z X oznacza to, że każdy element X musi być zawarty w selekcji przynajmniej raz. Etykietowanie z surjekcją jest równoważne grupowaniu elementów N , a następnie oznaczaniu każdej grupy elementem X , a zatem jest nieco bardziej skomplikowane do opisania matematycznego.

Podziały zbiorów i liczb

Postrzegając ƒ jako grupę elementów N (co zakłada, że ​​​​identyfikuje się pod permutacjami X ), wymaganie, aby ƒ było surjekcją, oznacza, że ​​​​liczba grup musi wynosić dokładnie x . Bez tego wymogu liczba grup może wynosić co najwyżej x . Wymóg iniekcji ƒ oznacza, że ​​każdy element N musi być grupą samą w sobie, co pozostawia co najwyżej jedno prawidłowe ugrupowanie i dlatego stwarza raczej nieciekawy problem z liczeniem.

Gdy dodatkowo identyfikuje się pod permutacjami N , oznacza to zapomnienie samych grup, ale zachowanie tylko ich rozmiarów. Co więcej, te rozmiary nie występują w żadnej określonej kolejności, podczas gdy ten sam rozmiar może wystąpić więcej niż jeden raz; można je ułożyć w słabo malejącą listę liczb, których suma jest liczbą n . Daje to kombinatoryczne pojęcie podziału liczby n na dokładnie x (dla suriekcji ƒ ) lub co najwyżej x (dla dowolnych ƒ ) części.

Formuły

Formuły dla różnych przypadków dwunastokrotnej drogi podsumowano w poniższej tabeli; każdy wpis w tabeli prowadzi do podsekcji poniżej wyjaśniającej formułę.

Dwanaście obiektów kombinatorycznych i ich wzory wyliczeniowe

klasa f	dowolny f	iniekcyjne _	suriekcja ż
Wyraźny f	n -sekwencja w X ${\ Displaystyle x ^ {n}}$	n -permutacja X ${\ Displaystyle x ^ {\ podkreślenie {n}}}$	złożenie N z x podzbiorami ${\ Displaystyle x! \ lewo \ {{n \ na szczycie x} \ prawo \}}$
S n orbit f ∘ S n	n -wiele podzbiorów X ${\ Displaystyle {\ binom {x + n-1} {n}}}$	n -podzbiór X ${\ Displaystyle {\ binom {x} {n}}}$	skład n z x terminami ${\ Displaystyle {\ binom {n-1} {nx}}}$
S x orbity S x ∘ fa	podział N na ≤ x podzbiory ${\ Displaystyle \ suma _ {k = 0} ^ {x} \ lewo \ {{n \ na szczycie k} \ prawo \}}$	podział N na ≤ x elementy ${\ Displaystyle [n \ równoważnik x]}$	podział N na x podzbiorów ${\ Displaystyle \ lewo \ {{n \ na szczycie x} \ prawo \}}$
S n × S x orbity S x ∘ f ∘ S n	podział n na ≤ x części ${\ Displaystyle p_ {x} (n + x)}$	podział n na ≤ x części 1 ${\ Displaystyle [n \ równoważnik x]}$	podział n na x części ${\ Displaystyle p_ {x} (n)}$

Konkretne stosowane oznaczenia to:

• spadająca potęga silni ${\ textstyle x ^ {\ podkreślenie {n}} = {\ Frac {x!} {(xn)!}} = x ( x-1)(x-2)\cdots (x-n+1)}$ ,
• rosnąca potęga silni ${\ textstyle x ^ {\ overline {n}} = {\ Frac {(x + n-1)!} {(x- 1)!}}=x(x+1)(x+2)\cdots (x+n-1)}$ ,
• silnia ${\ textstyle n! = n ^ {\ podkreślenie {n}} = n (n-1) (n-2) \ cdots 1}$ _
• liczba Stirlinga drugiego rodzaju ${\textstyle \left\{{n \na szczycie k}\right\}}$ , oznaczająca liczbę sposobów podziału zbioru n elementów na k podzbiorów
• współczynnik dwumianu ${\ textstyle {\ binom {n} {k}} = {\ frac {n ^ {\ podkreślenie {k}}} {k!}}}$
• nawias Iversona [ ] kodujący wartość logiczną jako 0 lub 1
• liczba $\ textstyle p_ {k} (n)$ { } partycji n na k części

Intuicyjne znaczenie wierszy i kolumn

To jest krótkie podsumowanie tego, co oznaczają różne przypadki. Przypadki zostały szczegółowo opisane poniżej.

Pomyśl o zbiorze X ponumerowanych elementów (ponumerowanych od 1 do x $)$ których wybieramy n , uzyskując uporządkowaną listę elementów: np. jeśli istnieją , z których wybieramy ${\ displaystyle n = 3}$ wynikiem może być lista (5, 2, 10). Następnie liczymy, ile różnych takich list istnieje, czasem najpierw przekształcając listy w sposób zmniejszający liczbę różnych możliwości.

Wtedy kolumny oznaczają:

Dowolny f

Po wybraniu przedmiotu odkładamy go z powrotem, abyśmy mogli wybrać go ponownie.

Injective f

Po wybraniu przedmiotu odkładamy go na bok, więc nie możemy wybrać go ponownie; stąd otrzymamy n różnych elementów. $.$ koniecznie, chyba że w ogóle wybrać żadnej listy

Surjective f

Po wybraniu przedmiotu odkładamy go z powrotem, abyśmy mogli wybrać go ponownie — ale na koniec musimy wybrać każdy przedmiot przynajmniej raz. Zatem koniecznie, chyba że ${\ displaystyle n \ geq x}$ w ogóle nie można wybrać żadnej listy.

A wiersze oznaczają:

Wyraźny

Zostaw listy w spokoju; policz je bezpośrednio.

S _n orbity

Przed liczeniem posortujlisty według numerów wybranych pozycji, aby kolejność nie miała znaczenia, np. (5, 2, 10), (10, 2, 5), (2, 10, 5 ) → (2, 5, 10).

S _x orbity

Przed liczeniem przenumeruj widziane przedmioty tak, aby pierwsza widziana rzecz miała numer 1, druga 2 itd. Liczby mogą się powtarzać, jeśli rzecz była widziana więcej niż jeden raz, np. (3, 5, 3), (5 , 2, 5), (4, 9, 4) → (1, 2, 1) podczas gdy (3, 3, 5), (5, 5, 3), (2, 2, 9) → (1, 1 , 2).

S _n × S _x orbit

Dwie listy liczą się jako takie same, jeśli można zmienić kolejność i zmienić ich etykietę, jak powyżej, i uzyskać ten sam wynik. Na przykład (3, 5, 3) i (2, 9, 9) liczą się tak samo, ponieważ można je zmienić na (3, 3, 5) i (9, 9, 2), a następnie ponowne oznaczenie obu daje to samo lista (1, 1, 2).

Intuicyjne znaczenie wykresu przy użyciu scenariusza Balls and Boxes

Poniższy wykres jest podobny do powyższego, ale zamiast pokazywać formuły, daje intuicyjne zrozumienie ich znaczenia na podstawie znanego przykładu kulek i pudełek. Rzędy reprezentują odrębność piłek i pudełek. Kolumny wskazują, czy dozwolone są opakowania zbiorcze (więcej niż jedna piłka w jednym pudełku) lub puste pudełka. Komórki na wykresie pokazują pytanie, na które można odpowiedzieć, rozwiązując formułę podaną na powyższym wykresie formuł.

Tabela 12 obiektów kombinatorycznych - intuicyjny wykres z wykorzystaniem kulek i pudełek

	dowolny f (brak zasad umieszczania)	iniekcyjne _ (opakowania zbiorcze niedozwolone)	suriekcja ż (brak pustych pól)
f (piłki i pudełka zaznaczone)	n -sekwencja w X Na ile sposobów można umieścić n zaznaczonych piłek w x zaznaczonych pudełkach, bez żadnych innych zasad umieszczania?	n -permutacja w X Na ile sposobów można umieścić n oznaczonych piłek w x oznaczonych pudełkach, nie dopuszczając wielopaków?	złożenie N z x podzbiorami Na ile sposobów można umieścić n zaznaczonych kul w x zaznaczonych pudełkach, tak aby żadne puste pola nie były dozwolone?
f ∘ S n (Kulki gładkie, Pudełka zaznaczone)	n -wielopodzbiór X Na ile sposobów można umieścić n zwykłych kul w pudełkach oznaczonych x, bez żadnych innych zasad umieszczania?	n - podzbiór X Na ile sposobów można umieścić n zwykłych piłek w pudełkach oznaczonych x, nie dopuszczając wielopaków?	złożenie n z x wyrazami Na ile sposobów można umieścić n zwykłych kul w pudełkach oznaczonych x, nie dopuszczając pustych pudełek?
S x ∘ f (kulki oznaczone, pudełka gładkie)	podział N na podzbiory ≤ x Na ile sposobów można umieścić n zaznaczonych piłek w x pustych pudełkach, bez żadnych innych zasad umieszczania?	podział N na ≤ x elementów Na ile sposobów można umieścić n oznaczonych piłek w x pustych pudełkach, nie dopuszczając wielopaków?	podział N na x podzbiorów Na ile sposobów można umieścić n zaznaczonych piłek w x pustych pudełkach, bez pustych pudełek?
S x ∘ f ∘ S n (Kulki i pudełka gładkie)	podział n na ≤ x części Na ile sposobów można umieścić n zwykłych kul w x pustych pudełkach, bez żadnych innych zasad umieszczania?	podział n na ≤ x części 1 Na ile sposobów można umieścić n zwykłych piłek w x pustych pudełkach, nie dopuszczając wielopaków?	podział n na x części Na ile sposobów można umieścić n zwykłych kul w x pustych pudełkach, nie dopuszczając pustych pudełek?

Szczegóły różnych przypadków

Poniższe przypadki są uporządkowane w taki sposób, aby pogrupować te przypadki, dla których powiązane są argumenty użyte do liczenia, co nie jest uporządkowaniem w podanej tabeli.

Funkcje od N do X

Ten przypadek jest równoważny zliczaniu sekwencji n elementów X bez ograniczeń: funkcja f : N → X jest określona przez n obrazów elementów N , z których każdy może być niezależnie wybrany spośród elementów x . Daje to w sumie x ⁿ możliwości.

Przykład:

${\ Displaystyle X = \ {a, b, c \}, N = \ {1,2 \} {\ tekst {, a następnie} }}$

${\ Displaystyle \ lewo \ vert \ {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c,a),(c,b),(c,c)\}\right\vert =3^{2}=9}$

Funkcje iniekcyjne od N do X

z liczeniem sekwencji n różnych elementów X , zwanych także n -permutacjami X lub sekwencjami bez powtórzeń ; ponownie ta sekwencja jest utworzona przez n obrazów elementów N . Przypadek ten różni się od przypadku sekwencji nieograniczonych tym, że jest o jeden wybór mniej dla drugiego elementu, o dwa mniej dla trzeciego elementu i tak dalej. Dlatego zamiast zwykłej potęgi x wartość jest dana przez a malejąca potęga silni x , w której każdy kolejny czynnik jest o jeden mniejszy od poprzedniego. Formuła jest

${\ Displaystyle x ^ {\ podkreślenie {n}} = x (x-1) \ cdots (xn + 1).}$

Zauważmy, że jeśli n > x to otrzymujemy czynnik zero, więc w tym przypadku w ogóle nie ma funkcji iniekcyjnych N → X ; jest to tylko powtórzenie zasady szufladkowania .

Przykład:

${\ Displaystyle X = \ {a, b, c, d \}, N = \ {1,2 \} {\ tekst {, Następnie }}}$

${\ Displaystyle \ lewo \ vert \ {(a, b), (a, c), (a, d), (b, a), (b, c) ( b,d),(c,a),(c,b),(c,d),(d,a),(d,b),(d,c)\}\right\vert =4^{ \podkreślenie {2}}=4\razy 3=12}$

Funkcje iniekcyjne od N do X , aż do permutacji N

Ten przypadek jest równoważny z liczeniem podzbiorów z n elementami X , zwanymi także n -kombinacjami X : spośród sekwencji n różnych elementów X , te , które różnią się tylko kolejnością ich wyrazów , są identyfikowane przez permutacje N . Ponieważ we wszystkich przypadkach to grupuje razem dokładnie n ! różnych ciągów, możemy podzielić liczbę takich ciągów przez n ! aby uzyskać liczbę n -kombinacji X . Liczba ta jest znana jako współczynnik dwumianowy , który jest zatem podawany przez ${\ Displaystyle {\ tbinom {x} {n}}}$

${\ Displaystyle {\ binom {x} {n}} = {\ Frac {x ^ {\ podkreślenie {n}}} {n!}} = {\ Frac {x (x-1) \ cdots (xn) +2)(x-n+1)}{n(n-1)\cdots 2\cdots 1}}.}$

Przykład:

${\ Displaystyle X = \ {a, b, c, d \}, N = \ {1,2 \} {\ tekst {, Następnie }}}$

${\ Displaystyle \ lewo \ vert \ {\ {a, b \}, \ {a, c \}, \ {a, d \}, \ {b, c \}, \ {b, d \}, \ {c,d\}\}\right\vert ={\frac {4^{\podkreślenie {2}}}{2!}}={\frac {4\times 3}{2}}=6}$

Funkcje od N do X aż do permutacji N

Ten przypadek jest równoważny liczeniu multisetów z n elementami z X (zwanych także n -multikombinacjami). Powodem jest to, że dla każdego elementu X określa się, ile elementów N jest do niego odwzorowanych przez f , podczas gdy dwie funkcje, które dają takie same „krotności” każdemu elementowi X , zawsze można przekształcić w inny przez permutację N. _ Formuła licząca wszystkie funkcje N → X nie jest tutaj przydatne, ponieważ liczba ich zgrupowanych razem przez permutacje N różni się w zależności od funkcji. Raczej, jak wyjaśniono w punkcie kombinacje , liczba n - multikombinacji ze zbioru z x elementami może być postrzegana jako taka sama jak liczba n -kombinacji ze zbioru z x + n - 1 elementami. Zmniejsza to problem do innego w dwunastokrotny sposób i daje rezultat

${\ Displaystyle {\ binom {x + n-1} {n}} = {\ Frac {(x + n-1) (x + n-2) \ cdots (x + 1) x} {n (n- 1)\cdots 2\cdot 1}}={\frac {x^{\overline {n}}}{n!}}.}$

Przykład:

${\ Displaystyle X = \ {a, b, c \}, N = \ {1,2 \} {\ tekst {, a następnie} }}$

${\ Displaystyle \ lewo \ vert \ {\ {a, a \}, \ {a, b \}, \ {a, c \}, \ {b, b \}, \ {b, c \}, \ {c,c\}\}\right\vert ={\frac {3^{\overline {2}}}{2!}}={\frac {4\times 3}{2}}=6}$

Funkcje suriekcyjne od N do X , aż do permutacji N

Ten przypadek jest równoważny liczeniu multisetów z n elementami z X , dla których każdy element X występuje co najmniej raz. Jest to również równoważne z liczeniem kompozycji n z x (niezerowymi) wyrazami , poprzez wypisanie krotności elementów x w celu. Odpowiedniość między funkcjami a multizbiorami jest taka sama jak w poprzednim przypadku, a wymóg surjekcji oznacza, że ​​wszystkie krotności są co najmniej jednością. Zmniejszając wszystkie krotności o 1, sprowadza się to do poprzedniego przypadku; ponieważ zmiana zmniejsza wartość n o x , wynikiem jest

${\ Displaystyle {\ binom {n-1} {nx}}.}$

Zauważ, że gdy n < x nie ma w ogóle funkcji suriekcyjnych N → X (rodzaj zasady „pustej przegródki”); jest to uwzględniane we wzorze, zgodnie z konwencją, że współczynniki dwumianowe wynoszą zawsze 0, jeśli dolny indeks jest ujemny. Tę samą wartość podaje również wyrażenie

${\ Displaystyle {\ binom {n-1} {x-1}}}$

z wyjątkiem skrajnego przypadku n = x = 0 , gdzie przy pierwszym wyrażeniu poprawnie daje ${\ Displaystyle {\ tbinom {-1} {0}} = 1}$ , podczas gdy drugie niepoprawnie daje ${\ Displaystyle {\ tbinom {-1} {-1}} = 0}$ .

Postać wyniku sugeruje poszukiwanie sposobu powiązania klasy funkcji suriekcyjnych N → X bezpośrednio z podzbiorem n − x elementów wybranych z sumy n − 1 , co można zrobić w następujący sposób. Najpierw wybierz całkowite uporządkowanie zbiorów N i X , i zauważ, że stosując odpowiednią permutację N , każdą suriekcję N → X można przekształcić w jednoznaczną słabo rosnącą (i oczywiście nadal suriekcją). Jeżeli połączymy elementy N w kolejności n − 1 łukami w graf liniowy , to wybierając dowolny podzbiór n − x łuków i usuwając resztę, otrzymamy graf o x połączonych składowych i wysyłając je do kolejnych elementów z X , otrzymuje się słabo rosnącą funkcję suriekcji N → X ; również rozmiary połączonych elementów dają skład n na x Części. Ten argument jest w zasadzie argumentem podanym przy gwiazdach i słupkach , z wyjątkiem tego, że dokonuje się tam uzupełniającego wyboru x - 1 „separacji”.

Przykład:

${\ Displaystyle X = \ {a, b \}, N = \ {1,2,3 \} {\ tekst {, a następnie} }}$

${\ Displaystyle \ lewo \ vert \ {\ {a, a, b \}, \ {a, b, b \} \} \ prawo \ vert = {\ binom {3-1} {3-2}} = {\binom {2}{1}}={\frac {2!}{1!\razy (2-1)!}}=2}$

Funkcje iniekcyjne od N do X , aż do permutacji X

W tym przypadku rozważamy sekwencje n różnych elementów z X , ale identyfikujemy te otrzymane z siebie nawzajem, stosując do każdego elementu permutację X . Łatwo zauważyć, że zawsze można zidentyfikować dwie różne takie sekwencje: permutacja musi odwzorowywać wyraz i z pierwszej sekwencji na wyraz i z drugiej sekwencji, a ponieważ żadna wartość nie występuje dwukrotnie w żadnej z sekwencji, wymagania te nie są ze sobą sprzeczne; pozostaje odwzorować elementy niewystępujące w pierwszej sekwencji bijektywnie na te, które nie występują w drugiej sekwencji w dowolny sposób. Jedyny fakt, od którego zależy wynik n i x w ogóle polega na tym, że istnienie jakichkolwiek takich ciągów na początek wymaga n ≤ x , zgodnie z zasadą przegródki. Liczba $zatem$ , Iversona .

Funkcje iniekcyjne od N do X , aż do permutacji N i X

Ten przypadek sprowadza się do poprzedniego: ponieważ wszystkie sekwencje n różnych elementów z X można już przekształcić w siebie nawzajem, stosując permutację X do każdego z ich terminów, również zezwolenie na zmianę kolejności terminów nie daje żadnych nowych identyfikacji; liczba pozostaje ${\ Displaystyle [n \ równoważnik x]}$ .

Funkcje suriekcyjne od N do X aż do permutacji X

Ten przypadek jest równoważny z liczeniem x partycji N na x (niepuste) podzbiory lub zliczaniem relacji równoważności na N z dokładnie klasami . Rzeczywiście, dla dowolnej funkcji suriekcyjnej f : N → X , relacja posiadania tego samego obrazu pod f jest taką relacją równoważności i nie zmienia się, gdy permutacja X jest następnie stosowana; odwrotnie, można przekształcić taką relację równoważności w funkcję suriekcji, przypisując w jakiś sposób elementy X do klas równoważności x . Liczba takich podziałów lub relacji równoważności jest z definicji liczbą Stirlinga drugiego rodzaju S ( n , x ), również zapisaną ${\ displaystyle \ textstyle \ {{n \ na szczycie x} \}}$ . Jego wartość można opisać za pomocą relacji rekurencji lub za pomocą funkcji generujących , ale w przeciwieństwie do współczynników dwumianowych nie ma zamkniętego wzoru na te liczby, który nie wymaga sumowania .

Funkcje suriekcyjne od N do X

Dla każdej funkcji suriekcyjnej f : N → X jej orbita pod permutacjami X ma x ! elementy, ponieważ złożenie (po lewej) z dwiema różnymi permutacjami X nigdy nie daje tej samej funkcji na N (permutacje muszą się różnić w pewnym elemencie X , co zawsze można zapisać jako f ( i ) dla pewnego i ∈ N , oraz kompozycje będą się wtedy różnić przy i ). Wynika z tego, że liczba dla tego przypadku to x ! razy liczba z poprzedniego przypadku, czyli ${\ Displaystyle \ textstyle x! \ {{n \ na szczycie x} \}.}$

Przykład:

${\ Displaystyle X = \ {a, b \}, N = \ {1,2,3 \} {\ tekst {, a następnie} }}$

${\ Displaystyle \ lewo \ vert \ {(a, a, b), (a, b, a), (a, b, b), (b, a, a) ,(b,a,b),(b,b,a)\}\right\vert =2!\left\{{3 \na górze 2}\right\}=2\times 3=6}$

Funkcje od N do X aż do permutacji X

Ten przypadek jest podobny do odpowiedniego dla funkcji suriekcyjnych, ale niektóre elementy x mogą w ogóle nie odpowiadać żadnej klasie równoważności (ponieważ rozważa się funkcje aż do permutacji X , nie ma znaczenia , które elementy są zainteresowane, tylko ile) . W konsekwencji liczy się relacje równoważności na N z co najwyżej x klasami, a wynik otrzymuje się ze wspomnianego przypadku przez sumowanie po wartościach do x , co daje ${\ Displaystyle \ textstyle \ suma _ {k = 0} ^ {x} \ {{n \ na szczycie k} \}}$ . W przypadku x ≥ n , rozmiar x nie stanowi żadnego ograniczenia i liczy się wszystkie relacje równoważności na zbiorze n elementów (równoważnie wszystkie podziały takiego zbioru); dlatego ${\ Displaystyle \ textstyle \ suma _ {k = 0} ^ {n} \ {{n \ na szczycie k} \}}$ daje wyrażenie na numer dzwonka B _n .

Funkcje suriekcyjne od N do X aż do permutacji N i X

Ten przypadek jest równoważny z liczeniem części liczby n na x niezerowych części . $)$ z przypadkiem liczenia funkcji suriekcyjnych tylko do permutacji X ( , zachowuje się tylko rozmiary klas równoważności, które N na (w tym krotność każdego rozmiaru), ponieważ dwie relacje równoważności można przekształcić w siebie przez permutację N wtedy i tylko wtedy, gdy rozmiary ich klas są zgodne. To właśnie odróżnia pojęcie podziału n od podziału N , więc w rezultacie z definicji otrzymuje się liczbę p _x ( n ) podziałów n na x niezerowych części.

Funkcje od N do X , aż do permutacji N i X

Ten przypadek jest równoważny z liczeniem części liczby n na ≤ x części . Skojarzenie jest takie samo jak w poprzednim przypadku, z wyjątkiem tego, że teraz niektóre części podziału mogą być równe 0. (W szczególności odpowiadają one elementom X nie znajdującym się w obrazie funkcji). Każdy podział n na co najwyżej x niezerowych części można rozszerzyć do takiego podziału, dodając wymaganą liczbę zer, a to uwzględnia wszystkie możliwości dokładnie raz, więc wynik jest określony przez ${\ Displaystyle \ textstyle \ suma _ {k = 0} ^ {x} p_ {k} (n)}$ . Dodając 1 do każdej z x części, otrzymuje się podział n + x na x niezerowych części, a ta zgodność jest bijektywna; stąd podane wyrażenie można uprościć, zapisując je jako ${\ Displaystyle p_ {x} (n + x)}$ .

Ekstremalne przypadki

Powyższe wzory podają odpowiednie wartości dla wszystkich skończonych zbiorów N i X . W niektórych przypadkach istnieją alternatywne formuły, które są prawie równoważne, ale które nie dają poprawnego wyniku w niektórych ekstremalnych przypadkach, na przykład gdy N lub X są puste. Poniższe uwagi dotyczą takich przypadków.

• Dla każdego zbioru X istnieje dokładnie jedna funkcja ze zbioru pustego do X (nie ma wartości tej funkcji do określenia), która jest zawsze iniekcyjna, ale nigdy surjektywna, chyba że X jest (również) pusty.
• Dla każdego niepustego zbioru N nie ma funkcji od N do zbioru pustego (istnieje co najmniej jedna wartość funkcji, która musi być określona, ​​ale nie może).
• Gdy n > x nie ma funkcji iniekcyjnych N → X , a jeśli n < x nie ma funkcji surjektywnych N → X .
• Wyrażenia użyte we wzorach mają określone wartości

${\ Displaystyle 0 ^ {0} = 0 ^ {\ podkreślenie {0}} = 0! = {\ binom {0} {0}} = {\binom {-1}{0}}=\left\{{0 \atop 0}\right\}=p_{0}(0)=1}$

(pierwsze trzy to wystąpienia pustego produktu , a wartość ${\ Displaystyle {\ tbinom {-1} {0}} = {\ tfrac {(-1) ^ {\ podkreślenie {0}}} {0!}} = 1} jest podane przez$ konwencjonalne rozszerzenie współczynników dwumianowych do dowolne wartości indeksu górnego), podczas gdy

${\ Displaystyle \ lewo \ {{n \ na górze x} \ prawo \} = p_ {x} (n) = 0 \ quad {\ hbox {kiedykolwiek}} n> 0 = x {\ hbox {lub}} 0 \równik n<x.}$

$liczenia$ w przypadku multisetów z n z X , podane przypadków ${\ Displaystyle {\ tbinom {n + x-1} {x-1}}}$ , ale to drugie wyrażenie dałoby 0 dla przypadku n = x = 0 (zgodnie ze zwykłą konwencją, że współczynniki dwumianowe z ujemnym dolnym indeksem wynoszą zawsze 0). Podobnie w przypadku liczenia kompozycji n z x niezerowymi częściami podane wyrażenie jest prawie równoważne wyrażeniu $nx}}}$ { ${\ Displaystyle {\ tbinom {n-1} {x-1}}}$ podane przez gwiazdy i słupki argument, ale ten ostatni podaje nieprawidłowe wartości dla n = 0 i wszystkich wartości x . W przypadkach, w których wynik obejmuje sumowanie, a mianowicie zliczanie podziałów N na co najwyżej x niepustych podzbiorów lub podziałów n na co najwyżej x części niezerowych, przyjmuje się, że indeks sumowania zaczyna się od 0; chociaż odpowiedni termin wynosi zero, gdy n > 0 , jest to unikalny termin niezerowy, gdy n = 0 , a wynik byłby błędny w tych przypadkach, gdyby sumowanie rozpoczęło się od 1.

Uogólnienia

Możemy dalej uogólniać, pozwalając innym grupom permutacji działać na N i X . Jeśli G jest grupą permutacji N , a H jest grupą permutacji X , to liczymy klasy równoważności funkcji ${\ Displaystyle f \ okrężnica N \ rightarrow X}$ . Dwie funkcje f i F są uważane za równoważne wtedy i tylko wtedy, gdy istnieje ${\ Displaystyle g \ in G, h \ in H}$ tak, że ${\ Displaystyle F = h \ circ f \ circ g}$ . To rozszerzenie prowadzi do takich pojęć, jak cykliczne i dwuścienne , a także cykliczne i dwuścienne podziały liczb i zbiorów.

Dwudziestokrotny sposób

Inne uogólnienie, zwane dwudziestokrotnym sposobem, zostało opracowane przez Kennetha P. Bogarta w jego książce „Kombinatoryka dzięki odkrywaniu kierowanemu”. W problemie rozmieszczania przedmiotów w pudełkach zarówno przedmioty, jak i pudełka mogą być identyczne lub różne. Bogart identyfikuje 20 przypadków.

Dwudziestokrotny sposób; modele dystrybucji n obiektów wśród x odbiorców

№	Obiekty	Warunek dystrybucji	Odbiorcy
			Odrębny	Identyczny
1	Odrębny	Bez ograniczeń	n -sekwencja w X ${\ Displaystyle x ^ {n}}$	podział N na ≤ x podzbiory ${\ Displaystyle \ suma _ {i = 0} ^ {x} \ lewo \ {{n \ na szczycie i} \ prawo \}}$
2		Maksymalnie po jednym	n -permutacja X ${\ Displaystyle x ^ {\ podkreślenie {n}}}$	${\ Displaystyle {\ rozpocząć {przypadki} 1 i {\ tekst {jeśli}} n \ równoważnik x \\ 0 i {\ tekst {inaczej}} \ koniec {przypadków}}}$
3		Przynajmniej po jednym	złożenie N z x podzbiorami ${\ Displaystyle x! \ lewo \ {{n \ na szczycie x} \ prawo \}}$	podział N na x podzbiorów ${\ Displaystyle \ lewo \ {{n \ na szczycie x} \ prawo \}}$
4		Dokładnie po jednym	${\ Displaystyle n! = x!}$ permutacje	${\ Displaystyle {\ rozpocząć {przypadki} 1 i {\ tekst {jeśli}} n = x \\ 0 & {\ tekst {w przeciwnym razie}} \ koniec {przypadków}}}$
5	Wyraźny, uporządkowany	Bez ograniczeń	uporządkowane funkcje ${\ displaystyle x ^ {\ overline {n}}}$	${\ Displaystyle \ suma _ {i = 1} ^ {x} L (n, i)}$$części$ ( ) Gdzie ${\ Displaystyle L (n, i)}$ to liczba Lah
6		Przynajmniej po jednym	${\ Displaystyle (n) ^ {\ podkreślenie {x}} (n-1) ^ {\ podkreślenie {nx}}}$ uporządkowane na funkcje	${\ Displaystyle L (n, x) = \ lewo ({n \ na górze x} \ prawej) (n-1) ^ {\ podkreśl {nx}}}$ przerwane permutacje ( x części) gdzie ${\ Displaystyle L (n, x)}$ to liczba Lah
7	Identyczny	Bez ograniczeń	n -wiele podzbiorów X ${\ Displaystyle \ lewo ({x + n-1 \ na górze n} \ prawej)}$	${\ Displaystyle \ suma _ {i = 1} ^ {x} p_ {i} (n)}$ liczba partycji ( ${\ Displaystyle \ leq x}$ części)
8		Maksymalnie po jednym	n -podzbiór X ${\ Displaystyle \ lewo ({x \ na górze n} \ prawej)}$	${\ Displaystyle {\ rozpocząć {przypadki} 1 i {\ tekst {jeśli}} n \ równoważnik x \\ 0 i {\ tekst {inaczej}} \ koniec {przypadków}}}$
9		Przynajmniej po jednym	${\ Displaystyle \ lewo ({n-1 \ na szczycie x-1} \ prawej)}$ kompozycje ( x części)	podział n na x części ${\ Displaystyle p_ {x} (n)}$
10		Dokładnie po jednym	${\ Displaystyle {\ rozpocząć {przypadki} 1 i {\ tekst {jeśli}} n = x \\ 0 & {\ tekst {w przeciwnym razie}} \ koniec {przypadków}}}$	${\ Displaystyle {\ rozpocząć {przypadki} 1 i {\ tekst {jeśli}} n = x \\ 0 & {\ tekst {w przeciwnym razie}} \ koniec {przypadków}}}$

Zobacz też

• Gwiazdy i słupki (kombinatoryka)