Możliwe kombinacje. Elementy kombinatoryki
Kombinacja to nieuporządkowany wybór elementów skończonego zbioru o ustalonej liczbie i bez powtarzania się elementów. Różne kombinacje muszą różnić się co najmniej jednym elementem, a kolejność elementów nie ma znaczenia. Na przykład ze zbioru wszystkich samogłosek liter łacińskich (AEIOU) można utworzyć 10 różnych kombinacji 3 liter, tworząc następujące nieuporządkowane trójki:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Warto zauważyć, że z tych samych pięciu liter można również uzyskać 10 różnych kombinacji, jeśli połączysz je po 2 litery, tworząc następujące nieuporządkowane pary:
AE, AI, AO, AU, EI, EO, UE, IO, IU, OU.
Jeśli jednak połączysz te same samogłoski łacińskie przez 4, otrzymasz tylko 5 różnych kombinacji:
AEIO, AEIU, AIOU, EIOU, AEOU.
W ogólnym przypadku, aby oznaczyć liczbę kombinacji n różnych elementów przez m elementów, stosuje się następującą symbolikę funkcjonalną, indeksową lub wektorową (Appela):
Niezależnie od formy oznaczenia liczbę kombinacji n elementów na m elementów można wyznaczyć za pomocą następujących wzorów multiplikatywnych i silniowych:
Łatwo sprawdzić, że wynik obliczeń przy użyciu tych wzorów pokrywa się z wynikami powyższego przykładu z kombinacjami samogłosek łacińskich. W szczególności dla n=5 i m=3 obliczenia z wykorzystaniem tych wzorów dadzą następujący wynik:
W ogólnym przypadku wzory na liczbę kombinacji mają znaczenie kombinatoryczne i obowiązują dla dowolnych wartości całkowitych n i m takich, że n > m > 0. Jeżeli m > n i m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
Ponadto warto pamiętać o następujących liczbach granicznych kombinacji, które można łatwo sprawdzić poprzez bezpośrednie podstawienie do wzorów multiplikatywnych i silniowych:
Należy również zauważyć, że formuła multiplikatywna pozostaje ważna nawet wtedy, gdy n jest liczbą rzeczywistą, o ile m jest nadal liczbą całkowitą. Jednak wówczas wynik obliczeń na nim, przy zachowaniu ważności formalnej, traci swój kombinatoryczny sens.
TOŻSAMOŚCI KOMBINACYJNE
Praktyczne zastosowanie wzorów multiplikatywnych i silniowych do określania liczby kombinacji dla dowolnych wartości n i m nie jest zbyt produktywne ze względu na wykładniczy wzrost iloczynów silni ich licznika i mianownika. Nawet w przypadku stosunkowo małych wartości n i m produkty te często przekraczają możliwości reprezentowania liczb całkowitych w nowoczesnych systemach komputerowych i programowych. Jednocześnie ich wartości okazują się znacznie większe niż wynikająca z tego wartość liczby kombinacji, która może być stosunkowo niewielka. Przykładowo liczba kombinacji n=10 na m=8 elementów wynosi tylko 45. Aby jednak znaleźć tę wartość za pomocą wzoru silni, należy najpierw obliczyć znacznie większe wartości 10! w liczniku i 8! w mianowniku:
Aby wykluczyć czasochłonne operacje przetwarzania dużych wartości, aby określić liczbę kombinacji, można zastosować różne relacje powtarzania, które wynikają bezpośrednio ze wzorów multiplikatywnych i silniowych. W szczególności ze wzoru multiplikatywnego wynika następująca relacja powtarzalności, która pozwala przyjąć stosunek jego wskaźników poza znakiem liczby kombinacji:
Wreszcie, pozostawienie indeksu dolnego bez zmian zapewnia następującą powtarzalność, którą można łatwo uzyskać ze wzoru silni na liczbę kombinacji:
Po elementarnych przekształceniach trzy powstałe relacje rekurencji można przedstawić w postaci:
Jeśli teraz dodamy lewą i prawą część pierwszych 2 wzorów i zmniejszymy wynik o n, otrzymamy ważną relację powtarzania, którą nazywamy tożsamością dodawania liczb kombinacji:
Tożsamość dodawania zapewnia podstawową regułę rekurencyjną do wydajnego określania liczby kombinacji dla dużych wartości n i m, ponieważ pozwala na zastąpienie operacji mnożenia w iloczynach silni prostszymi operacjami dodawania i dla mniejszej liczby kombinacji. W szczególności, korzystając z tożsamości addycyjnej, łatwo jest teraz wyznaczyć liczbę kombinacji n=10 na m=8 elementów, co rozważano powyżej, wykonując następującą sekwencję powtarzalnych przekształceń:
Ponadto z tożsamości addycyjnej można wyprowadzić kilka przydatnych relacji do obliczania sum skończonych, w szczególności wzór na sumowanie indeksu dolnego, który ma następującą postać:
Zależność taką uzyskuje się rozszerzając powtarzalność tożsamości addycyjnej po wyrazie o największym indeksie górnym, o ile jego indeks dolny jest większy od 0. Poniższy przykład liczbowy ilustruje wskazany proces przekształceń rekurencyjnych:
Formuła sumowania indeksu dolnego jest często używana do obliczania sumy potęg liczb naturalnych. W szczególności, zakładając m=1, korzystając z tego wzoru łatwo jest znaleźć sumę n pierwszych liczb ciągu naturalnego:
Inną użyteczną wersję wzoru na sumowanie można uzyskać, rozszerzając powtarzalność tożsamości addycyjnej w wyrazie z najmniejszym indeksem górnym. Poniższy przykład numeryczny ilustruje ten wariant przekształceń powtarzalnych:
W ogólnym przypadku w wyniku takich przekształceń otrzymuje się sumę liczb kombinacji, których oba indeksy różnią się o jeden od wyrazów sąsiednich, a różnica wskaźników pozostaje stała (w rozważanym przykładzie jest to również równy jeden). W ten sposób otrzymuje się następujący wzór na sumowanie obu indeksów liczb kombinacji:
Oprócz omówionych powyżej relacji powtarzania i wzorów sumowania, w analizie kombinatorycznej uzyskano wiele innych przydatnych tożsamości liczb kombinacji. Najważniejszym z nich jest tożsamość symetrii, który ma następującą postać:
Ważność tożsamości symetrii można zobaczyć w następującym przykładzie, porównując liczby kombinacji 5 elementów przez 2 i przez (5 2) = 3:
Tożsamość symetrii ma oczywiste znaczenie kombinatoryczne, gdyż określając liczbę możliwości wyboru m elementów z n elementów, ustala jednocześnie liczbę kombinacji z pozostałych (nm) niewybranych elementów. Wskazaną symetrię uzyskuje się natychmiast poprzez wzajemne zastąpienie m przez (nm) we wzorze silni na liczbę kombinacji:
Liczby i tożsamości kombinacji są szeroko stosowane w różnych obszarach współczesnej matematyki obliczeniowej. Jednak ich najpopularniejsze zastosowanie wiąże się z dwumianem Newtona i trójkątem Pascala.
DWUMIAN NEWTONA
Aby wykonać różne przekształcenia i obliczenia matematyczne, ważna jest możliwość przedstawienia dowolnej potęgi naturalnej dwumianu algebraicznego (dwumianu) w postaci wielomianu. W przypadku małych stopni żądany wielomian można łatwo uzyskać, bezpośrednio mnożąc dwumiany. W szczególności z matematyki elementarnej dobrze znane są następujące wzory na kwadrat i sześcian sumy dwóch wyrazów:
W ogólnym przypadku, dla dowolnego stopnia n dwumianu, pożądaną reprezentację w postaci wielomianu zapewnia twierdzenie Newtona o dwumianie, które stwierdza, że zachodzi następująca równość:
Równość tę nazywa się zwykle dwumianem Newtona. Wielomian po prawej stronie jest sumą iloczynów n wyrazów X i Y dwumianu po lewej stronie, a współczynniki przed nimi nazywane są dwumianami i są równe liczbie uzyskanych kombinacji z indeksami od swoich mocy. Biorąc pod uwagę szczególną popularność wzoru dwumianu Newtona w analizie kombinatorycznej, terminy współczynnik dwumianu i liczba kombinacji są zwykle uważane za synonimy.
Oczywiście wzory na sumę kwadratową i sześcienną są szczególnymi przypadkami twierdzenia o dwumianie, odpowiednio dla n=2 i n=3. Aby poradzić sobie z większymi potęgami (n>3), należy zastosować wzór dwumianu Newtona. Jej zastosowanie dla dwumianu czwartego stopnia (n=4) ilustruje następujący przykład:
Należy zauważyć, że wzór dwumianowy był znany średniowiecznym matematykom arabskiego Wschodu i Europy Zachodniej jeszcze przed Newtonem. Dlatego jego nazwa zwyczajowa nie jest historycznie poprawna. Zasługą Newtona jest to, że uogólnił ten wzór na przypadek dowolnego rzeczywistego wykładnika r, który może przyjmować dowolne dodatnie lub ujemne wartości racjonalne i niewymierne. W ogólnym przypadku taki wzór dwumianu Newtona ma po prawej stronie nieskończoną sumę i zwykle zapisuje się ją w następujący sposób:
Na przykład przy dodatniej wartości ułamkowej wykładnika r=1/2, biorąc pod uwagę wartości współczynników dwumianowych, uzyskuje się następujące rozwinięcie:
W ogólnym przypadku wzór dwumianu Newtona na dowolny wykładnik jest szczególną wersją wzoru Maclaurina, który daje rozwinięcie dowolnej funkcji w szeregu potęgowym. Newton pokazał to dla |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . Jeśli teraz wstawimy Z=X/Y i pomnożymy lewą i prawą część przez Yn, otrzymamy wariant wzoru dwumianu Newtona omówiony powyżej.
Pomimo swojej uniwersalności twierdzenie o dwumianie zachowuje swoje kombinatoryczne znaczenie tylko dla nieujemnych potęg całkowitych dwumianu. W tym przypadku można go użyć do udowodnienia kilku przydatnych tożsamości współczynników dwumianowych. W szczególności omówiono powyżej wzory sumowania liczb kombinacji według dolnego indeksu i obu wskaźników. Brakującą tożsamość sumowania indeksu górnego można łatwo uzyskać ze wzoru dwumianu Newtona, ustawiając w nim X = Y = 1 lub Z = 1:
Inna przydatna tożsamość ustala równość sum współczynników dwumianowych z liczbami parzystymi i nieparzystymi. Można to natychmiast uzyskać ze wzoru dwumianu Newtona, jeśli X = 1 i Y = 1 lub Z = 1:
Ostatecznie z obu rozważanych tożsamości otrzymuje się tożsamość sumy współczynników dwumianowych tylko z liczbami parzystymi lub tylko nieparzystymi:
Na podstawie rozważonych tożsamości oraz rekurencyjnej reguły usuwania indeksów spod znaku liczby kombinacji można otrzymać szereg ciekawych zależności. Na przykład, jeśli we wzorze na sumowanie indeksu górnego zastąpimy wszędzie n przez (n1) i usuniemy indeksy w każdym wyrazie, to otrzymamy następującą zależność:
Stosując podobną technikę we wzorze na sumę współczynników dwumianu dla liczb parzystych i nieparzystych, można udowodnić zasadność np. następującej zależności:
Inna przydatna tożsamość ułatwia obliczenie sumy iloczynów symetrycznie położonych współczynników dwumianu dwóch dwumianów o dowolnych stopniach n i k przy użyciu następującego wzoru Cauchy'ego:
Trafność tego wzoru wynika z niezbędnej równości współczynników dla dowolnego stopnia m zmiennej Z po lewej i prawej stronie następującej relacji tożsamości:
W szczególnym przypadku, gdy n=k=m, uwzględniając identyczność symetrii, otrzymuje się bardziej popularny wzór na sumę kwadratów współczynników dwumianu:
Wiele innych przydatnych tożsamości współczynników dwumianowych można znaleźć w obszernej literaturze na temat analizy kombinatorycznej. Jednak ich najsłynniejsze zastosowanie praktyczne związane jest z trójkątem Pascala.
TRÓJKĄT PASKALA
Trójkąt arytmetyczny Pascala tworzy nieskończoną tablicę liczbową złożoną ze współczynników dwumianowych. Jego wiersze są uporządkowane według potęg dwumianowych od góry do dołu. W każdym wierszu współczynniki dwumianu są ułożone w porządku rosnącym według górnych indeksów odpowiednich liczb kombinacji, od lewej do prawej. Trójkąt Pascala jest zwykle zapisywany w formie równoramiennej lub prostokątnej.
Bardziej wizualny i powszechny jest format równoramienny, w którym współczynniki dwumianowe ułożone w szachownicę tworzą nieskończony trójkąt równoramienny. Jej początkowy fragment dla dwumianów do IV stopnia (n=4) wygląda następująco:
Ogólnie rzecz biorąc, trójkąt równoramienny Pascala zapewnia wygodną regułę geometryczną do wyznaczania współczynników dwumianu, która opiera się na tożsamościach addycyjnych i symetrii liczb kombinacji. W szczególności, zgodnie z tożsamością dodawania, każdy współczynnik dwumianowy jest sumą dwóch współczynników z poprzedniego wiersza najbliższego mu. Zgodnie z tożsamością symetrii trójkąt równoramienny Pascala jest symetryczny względem swojej dwusiecznej. Zatem każdy z jego wierszy jest palindromem liczbowym współczynników dwumianowych. Te cechy algebraiczne i geometryczne ułatwiają rozwinięcie trójkąta równoramiennego Pascala i konsekwentne znajdowanie wartości współczynników dwumianowych o dowolnych stopniach.
Jednak do badania różnych właściwości trójkąta Pascala wygodniej jest zastosować formalnie bardziej rygorystyczny format prostokątny. W tym formacie jest on określony przez dolną trójkątną macierz współczynników dwumianowych, gdzie tworzą one nieskończony trójkąt prostokątny. Początkowy fragment trójkąta prostokątnego Pascala dla dwumianów do 9 stopnia (n=9) ma następującą postać:
Geometrycznie taką prostokątną tabelę uzyskuje się poprzez poziome odkształcenie trójkąta równoramiennego Pascala. W rezultacie szeregi liczbowe równoległe do boków trójkąta równoramiennego Pascala zamieniają się w piony i przekątne prawego trójkąta Pascala, a poziomy obu trójkątów pokrywają się. Jednocześnie zasady dodawania i symetrii współczynników dwumianowych pozostają ważne, chociaż trójkąt prostokątny Pascala traci wizualną symetrię właściwą swojemu odpowiednikowi równoramiennemu. Aby to zrekompensować, wygodniej jest formalnie przeanalizować różne właściwości numeryczne współczynników dwumianu dla poziomów, pionów i przekątnych prawego trójkąta Pascala.
Rozpoczynając analizę konturów trójkąta prostokątnego Pascala łatwo zauważyć, że suma elementów dowolnego wiersza o liczbie n jest równa 2 n zgodnie ze wzorem na sumowanie dwumianu przez indeks górny. Wynika z tego, że suma elementów na którymkolwiek z poziomów o liczbie n jest równa (2 n 1). Wynik ten staje się całkiem oczywisty, jeśli wartość sumy elementów każdego poziomu zostanie zapisana w systemie liczb binarnych. Przykładowo dla n=4 taki dodatek można zapisać następująco:
Oto kilka bardziej interesujących właściwości linii konturowych, które są również powiązane z potęgami dwójki. Okazuje się, że jeśli liczba pozioma jest potęgą dwójki (n=2 k), to wszystkie jej elementy wewnętrzne (oprócz skrajnych) są liczbami parzystymi. I odwrotnie, wszystkie liczby poziome będą nieparzyste, jeśli ich liczba będzie o jeden mniejsza od potęgi dwójki (n=2 k 1). Prawdziwość tych własności można sprawdzić sprawdzając parzystość wewnętrznych współczynników dwumianu, np. w poziomach n=4 i n=3 lub n=8 i n=7.
Niech teraz numer wiersza prawego trójkąta Pascala będzie liczbą pierwszą p. Wtedy wszystkie jego wewnętrzne współczynniki dwumianowe są podzielne przez p. Właściwość tę można łatwo sprawdzić dla małych wartości prostych liczb poziomych. Na przykład wszystkie wewnętrzne współczynniki dwumianu piątej poziomej (5, 10 i 5) są oczywiście podzielne przez 5. Aby udowodnić ważność tego wyniku dla dowolnej liczby pierwszej poziomej p, musimy napisać multiplikatywny wzór jej dwumianu współczynniki w następujący sposób:
Ponieważ p jest liczbą pierwszą i dlatego nie jest podzielne przez m!, iloczyn pozostałych czynników licznika tego wzoru musi być podzielny przez m!, aby zagwarantować całkowitą wartość współczynnika dwumianu. Wynika z tego, że relacja w nawiasach kwadratowych jest liczbą naturalną N i pożądany wynik staje się oczywisty:
Korzystając z tego wyniku można stwierdzić, że liczby wszystkich konturów trójkąta Pascala, których elementy wewnętrzne są podzielne przez daną liczbę pierwszą p, są potęgą p, czyli mają postać n=p k. W szczególności, jeśli p=3, to liczba pierwsza p dzieli nie tylko wszystkie wewnętrzne elementy rzędu 3, jak ustalono powyżej, ale np. 9. poziomą (9, 36, 84 i 126). Z drugiej strony w trójkącie Pascala nie można znaleźć poziomej, której wszystkie elementy wewnętrzne są podzielne przez liczbę złożoną. W przeciwnym razie liczba takiej poziomej musi być jednocześnie stopniem dzielników pierwszych liczby złożonej, przez który podzielone są wszystkie jej elementy wewnętrzne, co jest jednak z oczywistych względów niemożliwe.
Rozważane rozważania pozwalają na sformułowanie następującego ogólnego kryterium podzielności elementów poziomych trójkąta Pascala. Największy wspólny dzielnik (gcd) wszystkich elementów wewnętrznych dowolnej poziomej trójkąta Pascala o liczbie n jest równy liczbie pierwszej p, jeśli n=pk lub 1 we wszystkich pozostałych przypadkach:
NWD(Cmn) = ( ) dla dowolnego 0< m < n .
Podsumowując analizę poziomych, warto rozważyć jeszcze jedną ciekawą właściwość, jaką ma tworzący je szereg dwumianowych współczynników. Jeśli współczynniki dwumianowe dowolnej poziomej o liczbie n pomnożymy przez kolejne potęgi liczby 10, a następnie dodamy wszystkie te iloczyny, otrzymamy 11 n. Formalnym uzasadnieniem tego wyniku jest podstawienie wartości X=10 i Y=1 (lub Z=1) do wzoru dwumianu Newtona. Poniższy przykład numeryczny ilustruje implementację tej właściwości dla n=5:
Analizę właściwości pionów trójkąta prostokątnego Pascala można rozpocząć od zbadania indywidualnych cech ich elementów składowych. Formalnie każde pionowe m jest utworzone przez następującą nieskończoną sekwencję współczynników dwumianowych ze stałym indeksem górnym (m) i przyrostem indeksu dolnego:
Oczywiście, gdy m=0, otrzymujemy ciąg jedynek, a gdy m=1, tworzymy ciąg liczb naturalnych. Dla m=2 pion składa się z liczb trójkątnych. Każdą liczbę trójkątną można przedstawić na płaszczyźnie jako trójkąt równoboczny, który jest wypełniony dowolnymi obiektami (jądrami) ułożonymi w szachownicę. W tym przypadku wartość każdej liczby trójkątnej T k określa liczbę jąder reprezentujących, a indeks pokazuje, ile rzędów jąder potrzeba do jej reprezentacji. Na przykład 4 początkowe liczby trójkątne reprezentują następujące konfiguracje z odpowiedniej liczby znaków jądra „@”:
Warto zauważyć, że w podobny sposób można uwzględnić liczby kwadratowe S k, które otrzymuje się przez podniesienie do kwadratu liczb naturalnych oraz w ogóle wielokątne liczby figuratywne powstałe w wyniku regularnego wypełniania wielokątów foremnych. W szczególności 4 początkowe liczby kwadratowe można przedstawić w następujący sposób:
Wracając do analizy pionów trójkąta Pascala, można zauważyć, że kolejny pion w punkcie m=3 jest wypełniony liczbami czworościennymi (piramidalnymi). Każda taka liczba P k określa liczbę jąder, które można ułożyć w czworościan, a indeks określa, ile poziomych warstw trójkątnych z rzędów jąder potrzeba, aby przedstawić go w przestrzeni trójwymiarowej. W takim przypadku wszystkie warstwy poziome należy przedstawić jako kolejne liczby trójkątne. Elementy kolejnych pionów trójkąta Pascala dla m>3 tworzą rzędy liczb hipertetraedalnych, które nie mają jasnej interpretacji geometrycznej na płaszczyźnie ani w przestrzeni trójwymiarowej, ale formalnie odpowiadają wielowymiarowym analogom liczb trójkątnych i czworościennych.
Chociaż pionowe szeregi liczbowe trójkąta Pascala mają rozpatrywane indywidualne cechy kręcone, ale dla nich możliwe jest obliczenie sum częściowych wartości elementów początkowych w ten sam sposób, korzystając ze wzoru na sumowanie liczb kombinacji według indeksu dolnego . W trójkącie Pascala wzór ten ma następującą interpretację geometryczną. Suma wartości n górnych współczynników dwumianu dowolnego pionu jest równa wartości elementu następnego pionu, który znajduje się jedną linię poniżej. Wynik ten jest również zgodny ze strukturą geometryczną liczb trójkątnych, czworościennych i hiperczterościennych, ponieważ reprezentacja każdej takiej liczby składa się z warstw jądra, które reprezentują liczby niższego rzędu. W szczególności n-tą liczbę trójkątną T n można otrzymać sumując wszystkie liczby naturalne reprezentujące jej włókna liniowe:
Podobnie łatwo jest znaleźć liczbę czworościenną P n, obliczając następującą sumę pierwszych n liczb trójkątnych tworzących jej poziome warstwy jądrowe:
Oprócz poziomów i pionów w trójkącie prostokątnym Pascala można prześledzić ukośne rzędy elementów, których badanie właściwości jest również szczególnie interesujące. W tym przypadku zwykle rozróżnia się przekątne zstępujące i rosnące. Zstępujące przekątne są równoległe do przeciwprostokątnej prawego trójkąta Pascala. Tworzą je szeregi współczynników dwumianowych z przyrostem obu wskaźników. Ze względu na tożsamość symetrii zstępujące przekątne pokrywają się pod względem wartości swoich elementów z odpowiednimi pionowymi rzędami trójkąta Pascala i dlatego powtarzają wszystkie swoje właściwości omówione powyżej. Określoną zgodność można prześledzić poprzez zbieżność wartości elementów malejącej przekątnej i pionu z dowolną liczbą n, jeśli nie zostaną uwzględnione zera pionowe:
Przekątne rosnące tworzą rzędy liczb geometrycznie prostopadłe do przeciwprostokątnej prawego trójkąta Pascala. Wypełniane są współczynnikami dwumianowymi z przyrostem indeksu dolnego i przyrostem indeksu górnego. W szczególności 7 górnych rosnących przekątnych tworzy następującą sekwencję liczbową, z wyłączeniem zer końcowych:
W ogólnym przypadku następujące współczynniki dwumianu znajdują się na rosnącej przekątnej z liczbą n, której suma wskaźników każdego z nich jest równa (n1):
Dzięki identyczności dodawania liczb kombinacji każdy element przekątny jest równy sumie dwóch elementów odpowiadających indeksom dwóch poprzednich rosnących przekątnych. Dzięki temu każdą kolejną przekątną rosnącą można zbudować poprzez sumowanie parami sąsiednich elementów poziomych z dwóch poprzednich przekątnych, nieskończenie rozszerzając trójkąt Pascala wzdłuż przekątnej. Poniższy fragment trójkąta Pascala ilustruje budowę rosnącej przekątnej z liczbą 8 wzdłuż przekątnych z liczbami 6 i 7:
Dzięki tej metodzie konstrukcji suma elementów dowolnej rosnącej przekątnej, zaczynając od trzeciej, będzie równa sumie elementów dwóch poprzednich rosnących przekątnych, a pierwsze 2 przekątne składają się tylko z jednego elementu, wartości z czego wynosi 1. Wyniki odpowiednich obliczeń układają się w następujący ciąg liczbowy, zgodnie z którym można zweryfikować ważność rozważanej własności rosnących przekątnych trójkąta prostokątnego Pascala:
Analizując te liczby, można zauważyć, że zgodnie z podobnym prawem powstaje dobrze znany ciąg liczb Fibonacciego, w którym każda kolejna liczba jest równa sumie dwóch poprzednich, a dwie pierwsze liczby są równe 1:
Można zatem wyciągnąć następujący ważny wniosek: sumy diagonalne elementów trójkąta Pascala tworzą ciąg Fibonacciego. Ta właściwość pozwala nam ustalić kolejną interesującą cechę trójkąta Pascala. Rozwijając rekurencyjnie wzór Fibonacciego, łatwo jest udowodnić, że suma n pierwszych liczb Fibonacciego jest równa (F n+2 1).
Dlatego suma współczynników dwumianu wypełniających n górnych przekątnych jest również równa (F n+2 1). Wynika z tego, że suma pierwszych n przekątnych trójkąta Pascala jest o 1 mniejsza niż suma współczynników dwumianu, które stoją na jego przekątnej z liczbą (n + 2).
Podsumowując, należy zauważyć, że rozważane właściwości poziomów, pionów i przekątnych trójkąta Pascala nie wyczerpują ogromnej różnorodności możliwości, które łączą ze sobą różne aspekty matematyczne, które na pierwszy rzut oka nie mają ze sobą nic wspólnego. Tak niezwykłe właściwości pozwalają uznać trójkąt Pascala za jeden z najbardziej zaawansowanych systemów liczbowych, którego wszystkich możliwości nie sposób wymienić i trudno przecenić.
Algorytm obliczania liczby kombinacji za pomocą trójkąta Pascala przedstawiono poniżej:
Funkcja prywatna SochTT (ByVal n jako liczba całkowita, ByVal k jako liczba całkowita) As Double Dim i As Integer Dim j As Integer Dim TT () As Double ReDim TT (n, k) Dla i = 0 To n TT (0, i) = 1 TT (i, i) = 1 Następny Dla i = 2 Do n Dla j = 1 Do i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Następny Następny SochTT = TT (n, k) Funkcja końcowa
Jeśli musisz obliczyć liczbę kombinacji wiele razy, wygodniej będzie zbudować trójkąt Pascala raz, a następnie pobrać dane z tablicy.
Dim TT () As Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Funkcja prywatna SochTT (ByVal n jako liczba całkowita, ByVal k jako liczba całkowita) As Double If n > Ubound (TT) Następnie BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) Funkcja końcowa Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal początek jako liczba całkowita, ByVal koniec jako liczba całkowita) Dim i jako liczba całkowita Dim j Jako liczba całkowita ReDim Zachowaj TT (koniec, koniec) Dla i = początek Do końca TT (0, i) = 1 TT (i, i) = 1 Następny Jeśli koniec< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
Najpierw musisz wywołać procedurę CreateTT. Następnie możesz uzyskać liczbę kombinacji za pomocą funkcji SochTT. Gdy nie będziesz już potrzebował trójkąta, zadzwoń do TerminateTT. W powyższym kodzie, przy wywołaniu funkcji SochTT, jeśli trójkąt nie został jeszcze uzupełniony do wymaganego poziomu, to dopełnia się go za pomocą procedury BuildTT. Następnie funkcja pobiera wymagany element tablicy TT i zwraca go.
Dim X () jako liczba całkowita Dim Counter () jako liczba całkowita Dim K jako liczba całkowita Dim N jako liczba całkowita Public Sub Soch() Dim i jako liczba całkowita N = CInt(InputBox("Enter N")) K = CInt(InputBox("Enter K ")) K = K + 1 ReDim X(N) For i = 1 Do N X(i) = i Next txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c jako liczba całkowita) Dim i jako liczba całkowita Dim j jako liczba całkowita Dim n1 jako liczba całkowita Dim Out() jako liczba całkowita Dim X1() jako liczba całkowita Jeśli c = K Następnie ReDim Out(K) X1 = X Dla i = 1 Do K - 1 n1 = 0 Dla j = 1 Do N Jeśli X1(j)<>0 Wtedy n1 = n1 + 1 Jeśli n1 = Licznik(i) Wtedy Out(i) = X1(j) X1(j) = 0 Wyjście na koniec If Next txtOut.Text = txtOut.Text & CStr(Out(i)) Następny txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub
Wyliczanie kombinacji liczb naturalnych
Aby rozwiązać wiele praktycznych problemów, należy wyliczyć wszystkie kombinacje ustalonej liczności, jakie można otrzymać z elementów danego zbioru skończonego, a nie tylko określić ich liczbę. Biorąc pod uwagę zawsze istniejącą możliwość całkowitoliczbowej numeracji elementów dowolnego zbioru skończonego, w większości przypadków dopuszczalne jest ograniczenie się do stosowania algorytmów wyliczania kombinacji liczb naturalnych. Najbardziej naturalnym i najprostszym z nich jest algorytm wyliczania kombinacji liczb naturalnych porządek leksygraficzny.
Dla formalnego opisu tego algorytmu wygodnie jest założyć, że zbiór główny, w którym muszą zostać wymienione wszystkie kombinacje m elementów, tworzy kolejne liczby naturalne od 1 do n. Następnie dowolna kombinacja m W wyniku uporządkowania wartość w każdej pozycji takiego wektora kombinacji w naturalny sposób okazuje się ograniczona wartościowo od góry i od dołu w następujący sposób: Algorytm leksygraficzny generuje sekwencyjnie takie wektory kombinacji, zaczynając od wektora najmniejszego leksygraficznie, gdzie wszystkie pozycje zawierają następujące minimalne możliwe wartości elementów równe ich indeksom: Każdy kolejny wektor kombinacji tworzony jest na podstawie bieżącego po przejrzeniu jego elementów od lewej do prawej w celu znalezienia najbardziej wysuniętego na prawo elementu, który nie osiągnął jeszcze swojej wartości granicznej: Wartość takiego elementu należy zwiększyć o 1. Każdemu elementowi na prawo od niego należy przypisać najmniejszą możliwą wartość, czyli o 1 więcej niż sąsiad po lewej stronie. Po tych zmianach kolejny wektor kombinacji będzie miał następujący skład pierwiastkowy: Zatem następny wektor kombinacji będzie leksygraficznie większy niż poprzedni, ponieważ wartości ich elementów początkowych (j1) są równe, a wartość elementu na pozycji j jest o 1 większa niż wartość poprzedniego . Gwarantuje się, że określona relacja rosnącego porządku leksygraficznego będzie spełniona we wszystkich iteracjach algorytmu. W rezultacie powstaje rosnący ciąg leksygraficzny, który uzupełnia największy leksygraficznie wektor kombinacji, w którym elementy na wszystkich pozycjach mają następujące wartości maksymalne: Rozważany algorytm leksygraficzny ilustruje następujący przykład, w którym należy wymienić w rosnącym porządku leksygraficznym wszystkie 15 kombinacji n=6 pierwszych liczb naturalnych z m=4 liczbami, czyli wszystkie możliwe 4-elementowe podzbiory głównego zespołu prądotwórczego ( 1, 2, 3, 4, 5, 6) z 6 elementów. Wyniki obliczeń przedstawiono w poniższej tabeli: W tym przykładzie największe dopuszczalne wartości liczb w pozycjach wektorów kombinacji to odpowiednio 3, 4, 5 i 6. Dla wygody interpretacji wyników w każdym wektorze kombinacji najbardziej na prawo element, który nie został osiągnął jeszcze swoją wartość maksymalną, jest podkreślone. Indeksy numeryczne wektorów kombinacji określają ich numerację w porządku leksygraficznym. W ogólnym przypadku liczbę leksygraficzną N dowolnej kombinacji n elementów na m można obliczyć za pomocą następującego wzoru, gdzie ze względów kosmetycznych do oznaczenia liczby kombinacji zastosowano symbolikę Appela: W szczególności poniższe obliczenia z wykorzystaniem tego wzoru dla liczby kombinacji (1, 3, 4, 6) n=6 elementów przez m=4 w porządku leksygraficznym dadzą wynik N=8, co odpowiada przykładowi omówionemu powyżej: W ogólnym przypadku, korzystając z tożsamości sumy liczb kombinacji dla obu wskaźników, można wykazać, że liczba najmniejszej kombinacji leksygraficznej (1, ... i, ... m) przy jej obliczaniu za pomocą tego formuła będzie zawsze równa 1: Oczywiste jest również, że liczba największej leksygraficznie kombinacji (m, ... nm+i, ... n) przy obliczaniu jej według tego wzoru będzie równa liczbie kombinacji n elementów na m: Wzór na obliczenie liczb leksygraficznych kombinacji można zastosować do rozwiązania problemu odwrotnego, w którym wymagane jest określenie wektora kombinacji na podstawie jego numeru w porządku leksygraficznym. Aby rozwiązać taki odwrotny problem, należy go zapisać jako równanie, w którym wszystkie nieznane wartości elementów wektora pożądanej kombinacji (C 1 , ... C i , ... C m) są skoncentrowane liczby kombinacji jego prawej strony oraz znaną różnicę L liczby kombinacji zapisuje się po lewej stronie n elementów przez m i numer pożądanej kombinacji N: Rozwiązanie tego równania zapewnia następujący algorytm „zachłanny”, w którego iteracjach wybierane są kolejno wartości elementów wektora pożądanej kombinacji. W początkowej iteracji wybierana jest minimalna możliwa (w jej granicach) wartość C 1, w której pierwszy wyraz po prawej stronie będzie miał wartość maksymalną nie przekraczającą L: Teraz lewą stronę L należy pomniejszyć o pierwszą liczbę kombinacji po prawej stronie z wybraną wartością C 1 , a wartość C 2 należy wyznaczyć w ten sam sposób w drugiej iteracji: Podobnie należy wykonać wszystkie kolejne iteracje, aby wybrać wartości wszystkich pozostałych elementów C i pożądanej kombinacji, aż do ostatniego elementu C m: Z oczywistych względów wartość ostatniego elementu C m można wyznaczyć na podstawie równości liczby jego kombinacji z wartością rezydualną lewej strony L: Należy zauważyć, że wartość ostatniego elementu kombinacji C m można znaleźć jeszcze prościej, bez wyliczania jego możliwych wartości: Implementację iteracji rozważanego algorytmu ilustruje następujący przykład, w którym konieczne jest wyznaczenie kombinacji z liczbą N=8 w porządku leksygraficznym, jeśli n=6 i m=4: Algorytmiczna możliwość ustalenia kombinacji przez daną liczbę w porządku leksygraficznym może być wykorzystana w różnych kierunkach. W szczególności przy wymienianiu kombinacji w porządku leksygraficznym wymagane jest podanie powrotu do dowolnej kombinacji uzyskanej wcześniej, wystarczy znać jedynie jej numer. Ponadto możliwe staje się generowanie kombinacji w dowolnej kolejności, która reguluje dowolnie zadaną sekwencję ich numerów leksygraficznych. Przedstawiamy teraz algorytm generowania kombinacji w porządku leksykograficznym: 2 dla i:= 1 do k do A[i] := i; 5 rozpocznij pisanie(A, …, A[k]); 6 jeśli A[k] = n to p:= p 1 else p:= k; 8 dla i:= k aż do p do A[i] := A[p] + i p + 1 KOMBINACJE Z POWTÓRKAMI ELEMENTÓW W przeciwieństwie do klasycznej kombinacji, gdzie wszystkie elementy są różne, kombinacja z powtórzeniami tworzy nieuporządkowaną selekcję elementów skończonego zbioru, gdzie dowolny element może pojawiać się nieskończenie często i niekoniecznie występuje w pojedynczym egzemplarzu. Jednocześnie liczba powtórzeń elementów jest zwykle ograniczona jedynie długością kombinacji, a kombinacje różniące się przynajmniej jednym elementem uważa się za różne. Przykładowo, wybierając 4 opcjonalnie różne liczby ze zbioru 1, 2 i 3, możesz wykonać 15 następujących kombinacji z powtórzeniami: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
W ogólnym przypadku kombinacje z powtórzeniami można utworzyć poprzez wybór n elementów dowolnego typu. Można je jednak zawsze powiązać z kolejnymi liczbami naturalnymi od 1 do n. Wtedy dowolną kombinację m opcjonalnie różnych liczb z tego zakresu można zapisać w postaci wektorowej, ułożonej w niemalejącej kolejności od lewej do prawej: Naturalnie przy tej formie pisma wszelkie sąsiednie elementy mogą być równe ze względu na możliwość nieograniczonej liczby powtórzeń. Jednakże każdy wektor kombinacji z powtórzeniami n elementów na m można powiązać z wektorem kombinacji (n + m - 1) elementów na m, który jest skonstruowany w następujący sposób: Oczywiste jest, że dla dowolnych wartości elementów wektora f elementy wektora C są gwarantowane różne i ściśle uporządkowane w kolejności rosnącej ich wartości z zakresu od 1 do (n+m1) : Obecność zgodności jeden do jednego między elementami wektorów kombinacji f i C pozwala nam zaproponować następującą prostą metodę systematycznego wyliczania kombinacji z powtórzeniami n elementów na m. Wystarczy wymienić np. w porządku leksygraficznym wszystkie C kombinacji (n + m1) elementów przez m, przeliczając kolejno elementy każdego z nich na odpowiadające im elementy kombinacji z powtórzeniami f według następującego wzoru: W efekcie powstaje ciąg wektorów kombinacji z powtórzeniami elementów, które ułożone są w kolejności wygenerowanej przez wyliczenie odpowiednich kombinacji bez powtórzeń elementów. W szczególności, aby otrzymać powyższy ciąg kombinacji 3 cyfr 1, 2 i 3 z powtórzeniami 4 cyfr, należy wypisać w porządku leksygraficznym wszystkie kombinacje bez powtórzeń 6 cyfr 1,2,3,4,5 i 6 na 4 cyfry, konwertując je w określony sposób. Poniższy przykład pokazuje taką transformację kombinacji (1,3,4,6) z numerem leksygraficznym 8: Rozważana zgodność jeden do jednego pomiędzy kombinacjami z powtórzeniami i bez powtórzeń elementów oznacza, że ich zbiory są równoważne. Zatem w ogólnym przypadku liczba kombinacji z powtórzeniami n elementów na m jest równa liczbie kombinacji bez powtórzeń z (n + m1) elementów na m. Używając tej samej symboliki do oznaczenia liczby kombinacji z powtórzeniami f i bez powtórzeń C, równość tę można zapisać w następujący sposób: Łatwo sprawdzić, że dla powyższego przykładu, gdzie n=3 i m=4, liczba kombinacji z powtórzeniami wyniesie 15, co pokrywa się z wynikiem ich bezpośredniego wyliczenia: Należy zaznaczyć, że w odróżnieniu od wersji klasycznej wartości parametrów kombinacji z powtórzeniami n i m nie są ze sobą bezpośrednio powiązane, zatem f(n,m)>0 dla dowolnej kombinacji ich wartości dodatnich. Odpowiednie warunki brzegowe wyznacza się z równości wartości (n+m1) i (n1) lub (n+m1) i m: Powinno być również całkiem oczywiste, że jeśli m jest równe 1, to nie jest możliwe powtórzenie elementów i dlatego dla dowolnej dodatniej wartości n>0 zachodzi równość: Dodatkowo dla liczb kombinacji z powtórzeniami dla dowolnych dodatnich wartości n i m zachodzi następująca relacja powtarzalności, która jest podobna do tożsamości dodawania dla liczb kombinacji bez powtórzeń elementów: W rzeczywistości zamienia się w określoną tożsamość addycyjną z formalnym podstawieniem odpowiednich liczb kombinacji bez powtórzeń w lewej i prawej części: Rozważana relacja powtarzalności może być wykorzystana do efektywnego określenia liczby kombinacji z powtórzeniami, gdy ważne jest wykluczenie czasochłonnych operacji obliczania iloczynów silni i zastąpienie ich prostszymi operacjami dodawania. Jednocześnie, aby obliczyć wartość f(n,m), wystarczy zastosować tę relację powtarzania, aż otrzymamy sumę wyrazów postaci f(1,m) i f(i,1), gdzie i przyjmuje wartości z zakresu od n do 1. Z definicji takie terminy są równe odpowiednio 1 i i. Poniższy przykład ilustruje zastosowanie tej techniki transformacji dla przypadku n=3 i m=4: Wyliczanie kombinacji binarnych Podczas implementowania kombinacji sprzętowych lub programowania w języku asemblera ważna jest możliwość przetwarzania rekordów kombinacji w formacie binarnym. W takim przypadku dowolną kombinację n elementów na m należy podać w postaci n-bitowej liczby binarnej (B n ,…B j ,…B 1), gdzie m pojedynczych cyfr oznacza elementy kombinacji, a pozostałe (nm) cyfry mają wartości zerowe. Oczywiście przy tej formie zapisu różne kombinacje powinny różnić się układem jednostek i istnieją tylko C (n, m) sposoby rozmieszczenia m jedynek lub (nm) zer w n-bitowym zestawie binarnym. Na przykład poniższa tabela zawiera listę wszystkich 6 takich kombinacji binarnych, które zapewniają 4-bitowe liczby binarne dla wszystkich kombinacji 4 elementów dowolnego zbioru (E 1 , E 2 , E 3 , E 4 ) przez 2: W ogólnym przypadku zadanie wyliczenia takich kombinacji binarnych sprowadza się do systematycznego wyliczania wszystkich n-bitowych zbiorów binarnych z różnymi układami m pojedynczych i (nm) bitów zerowych. W najprostszej postaci takie wyliczenie realizuje się różnymi metodami transpozycji sąsiednich cyfr z przesunięciem (algorytmy przesunięcia transpozytywnego). Są to algorytmy iteracyjne, a ich nazwy odzwierciedlają charakter operacji wykonywanych na każdym kroku. Procedury iteracyjne algorytmów przesunięcia transpozytywnego tworzą sekwencje kombinacji binarnych, które zaczynają się od zbioru binarnego, w którym wszystkie jedynki są skoncentrowane w dolnych bitach (po prawej), a kończą, gdy wszystkie jedynki znajdują się w wyższych bitach (po lewej): Zbiegające się w kombinacjach początkowych i końcowych, sekwencje te różnią się kolejnością wyliczania pośrednich zbiorów binarnych. Jednak we wszystkich przypadkach każda kolejna kombinacja binarna powstaje zgodnie z poprzednią w wyniku wykonania odpowiednich operacji transpozycji i przesunięcia. Jednocześnie różne algorytmy przesunięcia transpozytywnego różnią się sposobem wyboru pary cyfr do transpozycji i grupy cyfr do przesunięcia. Ta specyfika jest rozważana poniżej dla algorytmów transpozycji z przesunięciem w lewo i w prawo. W algorytmie transpozycji z przesunięciem w lewo w każdym kroku, kolejną kombinację binarną uzyskuje się z aktualnej poprzez zastąpienie skrajnej lewej pary bitów 01 przez 10 (transpozycja) i przesunięcie grupy wiodących pojedynczych bitów, jeśli takie istnieją, blisko para 10 uzyskana po transpozycji (przesunięciu). Jeżeli w tym przypadku w najwyższych bitach aktualnej kombinacji binarnej nie ma jedynek, to przesunięcie nie jest wykonywane, nawet jeśli jednostka wiodąca zostanie uzyskana po transpozycji na tym etapie. Przesunięcie nie jest również wykonywane, gdy w bitach wyższego rzędu przed parą dziesiątek uzyskanych po transpozycji nie ma zer. Rozważane działania ilustruje następujący przykład wykonania dwóch kolejnych iteracji tego algorytmu, gdzie w jednej iteracji (15) wykonywana jest tylko transpozycja (T”), a w drugiej iteracji (16) transpozycja jest uzupełniana przesunięciem (T"+S"): W algorytmie transpozycji z przesunięciem w prawo na każdym kroku wykonywane są koncepcyjnie podobne działania. Tylko transpozycja gwarantuje, że skrajne prawe bity liczby 01 zostaną zastąpione przez 10 (zamiast skrajnie lewych), a następnie wszystkie jednostki po prawej stronie zostaną przesunięte do niższych bitów. Tak jak poprzednio, przesunięcie następuje tylko wtedy, gdy istnieją jednostki, które można przesunąć w prawo. Rozważane działania ilustruje następujący przykład wykonania dwóch kolejnych iteracji tego algorytmu, gdzie w jednej iteracji (3) wykonywana jest tylko transpozycja (T”), a w drugiej iteracji (4) transpozycja jest uzupełniana przez przesunięcie (T"+S"): Należy zaznaczyć, że iteracje obu algorytmów można zapisać w formie addytywnej, jeżeli kombinacje binarne interpretować będziemy jako liczby całkowite w systemie liczbowym o podstawie 2. W szczególności dla algorytmu transpozycji z przesunięciem w prawo każda kolejna kombinacja binarna (B „ n ,…B” j , …B” 1) można zawsze otrzymać z aktualnej kombinacji (B n ,…B j ,…B 1) wykonując operacje dodawania liczb całkowitych przy użyciu następującego wzoru na dodawanie: W tym wzorze addytywnym wykładniki dwójek f i t oznaczają odpowiednio liczbę zer bieżącej kombinacji binarnej i liczbę jedynek w rzędzie po ich lewej stronie. Na przykład dla czwartej kombinacji binarnej (001110) n=6 bitów, f =1 i t =3. Dlatego obliczenie kolejnej kombinacji binarnej za pomocą wzoru addytywnego w iteracji 5 da następujący wynik, który jest równoważny wykonaniu operacji transpozycji i przesunięcia: Do analizy porównawczej rozpatrywanych algorytmów transpozycji z przesunięciami w lewo i w prawo wskazane jest porównanie ciągów kombinacji binarnych, jakie generują one w swoich iteracjach. Poniższa tabela przedstawia dwie takie sekwencje kombinacji binarnych 4 elementów na 2, które uzyskuje się odpowiednio za pomocą algorytmów przesunięcia w lewo (TSL) i w prawo (TSR): Porównując te 2 sekwencje, widać, że są one odbiciem lustrzanym. Oznacza to, że dowolne dwie kombinacje binarne, które znajdują się w nich w tej samej odległości od wzajemnie przeciwnych końców ich ciągów, są swoimi odbiciami lustrzanymi, to znaczy pokrywają się przy przejściu na odwrotne indeksowanie bitów w którymkolwiek z nich. Na przykład drugi wzór binarny od początku sekwencji TSL (0101) jest lustrzanym odbiciem wzoru binarnego (1010), który jest drugi od końca sekwencji TSR. W ogólnym przypadku dowolna kombinacja binarna z liczbą i jednego ciągu jest lustrzanym odbiciem kombinacji binarnej z liczbą (ni + 1) innego ciągu. Taki stosunek tych ciągów jest konsekwencją symetrycznego charakteru operacji transpozycji i przesunięcia w dwóch rozpatrywanych algorytmach wyliczania kombinacji binarnych. Należy zaznaczyć, że w formacie binarnym można także zapisywać kombinacje z powtórzeniami elementów. Aby to zrobić, musisz ustalić zgodność jeden do jednego między kombinacjami z powtórzeniami i kombinacjami binarnymi, które są zbudowane w następujący sposób. Niech będzie dowolna kombinacja z powtórzeniami, którą uzyskuje się wybierając m opcjonalnie różnych elementów z n elementów zespołu prądotwórczego. Aby ustalić pożądaną zgodność, należy najpierw dołączyć do kombinacji wszystkie elementy zespołu prądotwórczego (cat), a następnie tak posortować powstałą konkatenację (sort), aby wszystkie identyczne elementy znajdowały się w pobliżu. Wynikiem jest sekwencja (n+m) elementów, w której n grup identycznych elementów. Pomiędzy elementami będą tylko (n+m1) odstępy, wśród których będą (n1) odstępy pomiędzy grupami identycznych elementów oraz m odstępy pomiędzy elementami w obrębie grup. Dla przejrzystości w określonych odstępach można umieścić znaki „|” i odpowiednio. Jeśli teraz odwzorujemy 1 na przerwy między grupami (|) i 0 na wszystkie pozostałe przerwy (), wówczas otrzymamy kombinację binarną. Tworzy go binarny zbiór cyfr (n+m1), gdzie (n1) to jedyneki, a m cyfr zerowych, których położenie jednoznacznie odpowiada oryginalnej kombinacji z powtórzeniami od elementów n do m. Rozważaną technikę transformacji ilustruje następujący przykład konstrukcji kombinacji binarnej (1001101) poprzez kombinację z powtórzeniami (BBD), której elementy wybierane są ze zbioru generującego pierwszych pięciu liter łacińskich: Ogólnie rzecz biorąc, liczba takich zbiorów binarnych określa liczbę sposobów ułożenia (n1) jedynek (lub m zer) w (n+m1) cyfr binarnych. Wartość ta jest oczywiście równa liczbie kombinacji z (n+m1) przez (n1) lub przez m, czyli C(n+m1,n1) lub C(n+m1,m), która jest równa liczba kombinacji z powtórzeniami f( n,m) n elementów na m. Zatem mając zgodność jeden do jednego między kombinacjami z powtórzeniami i kombinacjami binarnymi, uzasadnione jest ograniczenie wyliczania kombinacji z powtórzeniami do wyliczania kombinacji binarnych, na przykład za pomocą algorytmów transpozycji z przesunięciem w lewo lub w prawo. Następnie wystarczy przywrócić żądane kombinacje za pomocą powtórzeń z uzyskanych kombinacji binarnych. Zawsze można to zrobić, stosując następującą technikę odbudowy. Niech zbiór główny, z którego powstają kombinacje z powtórzeniami m, ewentualnie różnych elementów, będzie uporządkowany dowolnie tak, aby każdy z jego elementów miał określony numer porządkowy od 1 do n. Zastosujmy także wyliczenie kombinacji binarnych (n+m1) cyfr binarnych, gdzie (n1) to cyfry pojedyncze, a m cyfry zerowe. Każdą powstałą kombinację binarną można uzupełnić po lewej stronie fikcyjną cyfrą jedności, a wszystkie cyfry jedności można ponumerować od lewej do prawej liczbami całkowitymi od 1 do n. Wtedy liczba zer stojących w rzędzie po każdej i-tej jednostce kombinacji binarnej będzie równa liczbie wystąpień i-tego elementu zbioru głównego w odpowiedniej kombinacji z powtórzeniami. Rozważaną technikę ilustruje następujący przykład, w którym kombinacja binarna (1001101) odtwarza kombinację z powtórzeniami BBD, których elementy są wybrane z zestawu generującego pierwszych pięciu liter łacińskich zapisanych w kolejności alfabetycznej, a nadkreślenie wskazuje elementy, których nie ma w tej kombinacji: Wykonując podobne czynności w warunkach tego przykładu, możesz wyświetlić listę wszystkich 35 kombinacji binarnych, które tworzą 7-bitowe zestawy binarne, w których są 4 jedyneki i 3 zera, i przywrócić odpowiednie kombinacje z powtórzeniami 5 elementów przez 3. Zbliżała się zima i Khoma i Gopher postanowili zaopatrzyć się w groszek. Przez cały dzień biegali do stodoły i ciągnęli kilka strąków: Khoma cztery i Gopher dwa. Wieczorem policzyli wszystkie strąki, które przynieśli, i zastanawiali się, jak teraz podzielić ten groszek. Khoma argumentował, że jeśli będzie ciągnął za jednym razem dwa razy więcej niż Gopher, to powinien dostać dwa razy więcej groszku. Gopher słusznie sprzeciwił się temu, że po pierwsze, prędkość Khomy jest zauważalnie mniejsza niż Gophera, a po drugie, kto wie, może Khoma uciekł tylko raz lub dwa razy, a resztę czasu był bezczynny… Pomóż swoim przyjaciołom choć trochę zrozumieć tę trudną sytuację. Określ wszystkie możliwe opcje, ile kapsułek przyniósł Susły i ile Homa. Pierwsza linia zawiera parzystą liczbę całkowitą M, czyli liczbę skradzionych strąków, 2 ≤ M ≤ 1000. Wszystkie możliwe kombinacje liczby strąków przyniesionych przez Gophera i Khomę, po jednej kombinacji w wierszu. Każda kombinacja to dwie nieujemne liczby całkowite oddzielone spacją: pierwsza liczba to liczba strąków przyniesionych przez Gophera, druga - przyniesiona przez Khomę. Posortuj kombinacje w kolejności malejącej od pierwszej liczby. #włączać używając przestrzeni nazw std ; int główna()( int a, b = 0; cin >> a; podczas gdy (a >= 0 ) ( cout<<
a
<<
" "
<<
b
<<
"\n"
;
a-= 4; b += 4; zwróć 0; Niech a będzie liczbą strąków przyniesionych przez Homę, a b liczbą strąków przyniesionych przez Gophera. Ponieważ zgodnie z warunkiem problemu Khoma niósł tylko cztery strąki, rozważymy a = a-4 i b = b + 4, aby posortować wszystkie możliwe kombinacje liczby strąków przyniesionych przez Gophera i Khomę. Używamy również pętli chwila, co będzie powtarzać akcję opisaną powyżej aż do \geq 0. W odpowiedzi wypisujemy wszystkie możliwe kombinacje liczby podów przyniesionych przez znajomych, po jednym w wierszu, posortowane w kolejności malejącej od pierwszej liczby. Przykład // Kombinacje 3 z 52 for (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
Tutaj rozważymy bardziej złożone zadanie, którego rozwiązania nie znalazłem w Runecie (podam jednak jeden link, ale ta formuła jest wyraźnie błędna) - w oparciu o samą kombinację (w tym przypadku zestaw trzech liczby) znajdź jego indeks. Załóżmy dla pewności, że po uporządkowaniu i1 = 3, i2 = 7, i3 = 12. Typowy algorytm generowania polega na tym, że generujemy kombinacje 2 z 52, a dla każdej takiej kombinacji w zagnieżdżonej pętli generujemy kombinacje 3 z 50 i sprawdzamy, czy indeksy (i3, i4, i5) w zagnieżdżonej kombinacji nie dopasowują indeksów (i1, i2) w kombinacji zewnętrznej: Kod C++ // KOMBINACJA ZEWNĘTRZNA for (int i1 = 0; i1< 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРЕННЕЕ СОЧЕТАНИЕ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...
Kod C++ jeśli (i3 >= i1) --i3; jeśli (i3 >= i2) --i2; //podobnie dla i4, i5 Przykładowy kod podziału indeksu przez 2, 3, 47 int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) ( // Indeks kombinacji 2 z 52 pomnożony przez C(3, 50) int offset = ((52*51 - (51 -i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // "Reindeksuj" grupę wewnętrzną tak, aby numeracja wynosiła 0...49 if (i3 >= i1) - -i3;if (i3 >= i2) --i3;if (i4 >= i1) --i4;if (i4 >= i2) --i4;if (i5 >= i1) --i5;if (i5 >= i2) --i5; // Teraz dodaj indeks kombinacji powyżej 3 // 0: // SUMA dla n = 0 przez i3-1 KOMBINACJE (2, 49-n) // = SUMA dla m = 50-i3 powyżej 49 (m * (m-1) / 2) przesunięcie += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)* (50-i3 )) / 2) / 2); // 1: // SUMA dla n = i3+1 przez i4-1 KOMBINACJE (1, 49-n) offset += (((48-i3)*( 49-i3) - (49-i4)*(50-i4)) / 2); // 2: // SUMA dla n = i4+1 przez i5-1 (1) przesunięcie += (i5 - i4 - 1 ); przesunięcie zwrotu ;) Ogólnie algorytmy kombinatoryczne podzieliłbym na następujące klasy: Liczba kombinacji połączenie z N Przez k zwany zestawem k elementy wybrane z danych N elementy. Zestawy, które różnią się jedynie kolejnością elementów (ale nie kompozycją), są uważane za takie same; w ten sposób kombinacje różnią się od rozmieszczenia. Liczba kombinacji z N Przez k
jest równy współczynnikowi dwumianu Dla stałej wartości N generując funkcję liczby kombinacji z powtórzeniami N Przez k Jest: Dwuwymiarowa funkcja generująca liczbę kombinacji z powtórzeniami to: Fundacja Wikimedia. 2010 . 70 siedemdziesiąt 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Rozkład na czynniki: 2×5×7 Notacja rzymska: LXX Binarny: 100 0110 ... Wikipedia Liczba światła, liczba warunkowa, która jednoznacznie wyraża zewnętrzną. warunki podczas fotografowania (zwykle jasność obiektu i czułość użytego materiału fotograficznego). Dowolną wartość E. h. można wybrać kilka. Kombinacje liczb f ... ... Duży encyklopedyczny słownik politechniczny Forma liczby odróżniająca dwa obiekty zarówno w odniesieniu do pojedynczego obiektu, jak i w odniesieniu do wielu obiektów. Ta forma nie istnieje we współczesnym języku rosyjskim, ale zachowały się pozostałości jej wpływów. Zatem kombinacje dwóch tabel (por. liczba mnoga ... ... Słownik terminów językowych Matematyka kombinatoryczna, kombinatoryka, dział matematyki zajmujący się rozwiązywaniem problemów wyboru i porządkowania elementów pewnego, zwykle skończonego, zbioru według zadanych reguł. Każda taka reguła wyznacza sposób konstruowania... ... Encyklopedia matematyczna W kombinatoryce kombinacja by to zbiór elementów wybranych z danego zestawu zawierającego różne elementy. Zestawy różniące się jedynie kolejnością elementów (ale nie składem) uważa się za takie same, te kombinacje… ... Wikipedia Zajmuje się badaniem zdarzeń, których wystąpienie nie jest pewne. Pozwala ocenić zasadność oczekiwania wystąpienia niektórych zdarzeń w porównaniu z innymi, choć przypisywanie wartości liczbowych prawdopodobieństwu zdarzeń jest często zbędne… ... Encyklopedia Colliera 1) to samo, co matematyczna analiza kombinatoryczna. 2) Sekcja matematyki elementarnej związana z badaniem liczby kombinacji pod pewnymi warunkami, które można utworzyć z danego skończonego zbioru obiektów ... ... Wielka encyklopedia radziecka - (greckie paradoksos nieoczekiwany, dziwny) w szerokim znaczeniu: stwierdzenie ostro sprzeczne z ogólnie przyjętą, utrwaloną opinią, zaprzeczenie temu, co wydaje się „niewątpliwie słuszne”; w węższym sensie dwa przeciwstawne stwierdzenia, ponieważ ... ... Encyklopedia filozoficzna - (lub zasada włączeń wyłączeń) wzór kombinatoryczny pozwalający wyznaczyć potęgę sumy skończonej liczby skończonych zbiorów, które w ogólnym przypadku mogą się ze sobą przecinać... Wikipedia Teoria matematyczna zajmująca się wyznaczaniem liczby różnych sposobów rozmieszczenia danych obiektów w znanej kolejności; ma szczególne znaczenie w teorii równań i teorii prawdopodobieństwa. Najprostsze zadania tego rodzaju to ... ... Słownik encyklopedyczny F.A. Brockhausa i I.A. EfronaDane wejściowe
Wyjście
Testy
Dane wejściowe
Wyjście
6
\\ 6 \; 0 \\ 2 \; 4
11
\\ 11\;0 \\ 7\;4 \\ 3\;8
18
\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16
Kod programu
Rozwiązanie problemu
Indeks kombinacji
Każdą kombinację, permutację, położenie i inne obiekty kombinatoryczne można powiązać z indeksem - jest to liczba, w jakiej się on pojawia podczas iteracji przez ten algorytm.
Istnieje opcja brutalnej siły. Włączamy licznik kombinacji, przyjmujemy powyższy algorytm i dopóki nie dotrzemy do żądanej opcji, sortujemy wszystko. Ta opcja ma bardzo dużą złożoność czasową, więc ją odrzucimy.
Załóżmy, że na wejściu znajdują się liczby i1, i2, i3. Przede wszystkim musimy ułożyć je w porządku rosnącym (zauważ, że sam algorytm generowania, podany powyżej, zawsze wyprowadza je w uporządkowanej formie, chociaż samo pojęcie „kombinacji” implikuje dowolną kolejność).
Oznacza to, że „przeszliśmy” wszystkie kombinacje, w których i1 było równe 0, 1 i 2.
Dla i1 = 0 przeszliśmy przez kombinacje C(2, 51), ponieważ indeksy i1, i2 przebiegają przez wszystkie kombinacje 2 z 51 liczb.
Dla i1 = 1 przeszliśmy przez kombinacje C(2, 50).
Dla i1 = 2 przeszliśmy przez kombinacje C(2, 49).
W sumie przeszliśmy przez SUMĘ (od n = 0 do n = i1-1) C (2, 51-n).
Dla i1 = 3 rozważmy już te kombinacje, które przeszliśmy, przechodząc przez indeks i2 (a zaczyna się od i2 = i1+1 = 4).
Dla i2 = 4 kombinacje C(1, 47) zaliczone, dla i2 = 5 kombinacje C(1, 46) zaliczone, dla i2 = 6 kombinacje C(1, 45) zaliczone.
Przez pełną analogię, dla i2 = 7, rozważamy kombinacje, przez które przeszedł indeks i3.
Otrzymujemy wzór ogólny:
Pożądany indeks kombinacji = SUMA (od n = 0 do i1-1) C(2, 51-n) + SUMA (od n = i1+1 do i2-1) C(1, 51-n) + SUMA (od n = i2+1 przez i3-1) C(0, 51-n).Indeks podzbioru
W kombinatoryce istnieje również bardziej złożony obiekt - dzielenie na podzbiory. Na przykład podział 52-elementowego zbioru na trzy podzbiory składające się, powiedzmy, odpowiednio z 2, 3 i 47 elementów, przy czym kolejność elementów w każdym podzbiorze jest nieistotna. (Nawiasem mówiąc, kombinacja 2 z 52 to tylko szczególny przypadek podziału na dwa podzbiory odpowiednio 2 i 50 elementów).
Ponownie każda taka partycja ma swój własny indeks.
Okazuje się, że nasz algorytm znajdowania indeksu kombinacji można zmodyfikować, aby znaleźć indeks podziału.
Należy zaznaczyć, że indeksy w „kombinacji zewnętrznej” musimy uporządkować między sobą, a indeksy i3, i4, i5 – między sobą, ale niezależnie od dwóch pierwszych.
Należy również zaznaczyć, że w „kombinacji zagnieżdżonej” tak naprawdę pracujemy ze zbiorem 50 elementów, ale indeksy i3, i4, i5 trzeba w określony sposób „przesunąć” tak, aby nie zmieniały się z 0 do 51, ale od 0 do 49:
(że tak powiem, wycinamy indeksy i1, i2 z naszego 52-elementowego zbioru, a następnie przesuwamy pozostały zbiór, aby zamknąć dziury, natomiast indeksy i3-i5 są przesuwane).
Należy wziąć pod uwagę, że wewnątrz każdej kombinacji „zewnętrznej” mamy dokładnie C(3, 50) kombinacji „zagnieżdżonych”.
Następnie algorytm zostanie zredukowany do następującego:
COMBINATION_INDEX (i1, i2 z 52) * COMBINATION_IN_3_FROM_50 + COMBINATION_INDEX (i3, i4, i5 z 50 po przesunięciu indeksu). Doprowadzanie algorytmów do stałej złożoności
Od razu powinienem zwrócić uwagę, że we wzorze pojawia się „błąd”, jeśli np. i1 = 0 (liczymy sumę dla n = od 0 do -1) lub i2 = 1 (liczymy sumę od 1 do 0) . W rzeczywistości w takich przypadkach odpowiednią kwotę należy przyjąć równą zero, a wynik będzie poprawny.
Powinienem także zwrócić uwagę na złożoność czasową naszych algorytmów: mają one złożoność liniową, pod warunkiem, że weźmiemy pod uwagę C jako czas stały. To już jest znacznie lepsze niż brutalna siła.
Ale tak na prawdę (w naszym przypadku 52) nic nie stoi na przeszkodzie, abyśmy sprowadzili algorytm do stałej złożoności. Aby to zrobić, wykorzystujemy wiedzę matematyczną i analitycznie obliczamy wszystkie sumy.
Na przykład liczba kombinacji C(2, K), jeśli „otworzysz” ją w postaci wzoru K! / ((K-2)! * 2!), sprowadza się do wielomianu drugiego stopnia. A skoro mamy to pod znakiem sumy, to możemy zastosować wzory na sumę N-tych potęg liczb ciągu naturalnego (patrz Wikipedia) i otrzymać pojedynczy wielomian trzeciego stopnia. Co oczywiście ma stałą złożoność czasową. (Co więcej, „błąd”, który przytoczyłem na początku podtytułu, nie objawia się w żaden sposób, formuła pozostaje poprawna).
Powtarzam, to dla stałego wymiaru zestawu podstawowego. Jestem jednak pewien, że za pomocą metaprogramowania możesz „nauczyć” kompilator, aby wykonał tę pracę za Ciebie. Posłowie
W moim symulatorze pokera (Texas Hold „em) chciałem wstępnie obliczyć i zapisać prawdopodobieństwa wygranej dla wszystkich możliwych kombinacji moich kart z ręki (2 sztuki) i wszystkich kart z flopa (3 karty na stole). Odpowiada to podziałowi zbiór 52 na 2, 3, 47 podzbiorów.
obliczone i zapisane.
Kiedy jednak przyszedł czas na wczytanie danych z pliku dla konkretnej kombinacji, naprawdę nie chciało mi się tam długo liczyć ani szukać w gigabajtowym pliku. Teraz po prostu określam przesunięcie w pliku i bezpośrednio czytam, czego potrzebuję.
Byłoby interesujące mieć przewodnik po algorytmach kombinatorycznych dla wszystkich obiektów kombinatorycznych, w tym permutacji, kombinacji, rozmieszczeń, podzbiorów, kombinacji z powtórzeniami, rozmieszczeń z powtórzeniami. Wyraźne formuły
Spinki do mankietów
Zobacz, jaka jest „Liczba kombinacji” w innych słownikach:
Książki