Kombinacja to nieuporządkowany wybór elementów skończonego zbioru o ustalonej liczbie i bez powtórzeń elementów. Różne kombinacje muszą różnić się przynajmniej jednym elementem, a kolejność elementów nie ma znaczenia. Na przykład ze zbioru wszystkich samogłosek liter łacińskich (AEIOU) możesz 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 na raz, 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 litery łacińskie samogłosek przez 4, otrzymasz tylko 5 różnych kombinacji:
AEIO, AEIU, AIOU, EIOU, AEOU.
Ogólnie rzecz biorąc, aby oznaczyć liczbę kombinacji n różnych elementów m elementów, stosuje się następującą symbolikę funkcjonalną, indeksową lub wektorową (Appela):
Niezależnie od formy zapisu 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 omówionego powyżej przykładu z kombinacjami samogłosek w literach ł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 jak n > m > 0. Jeśli m > n i m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
Ponadto warto pamiętać o następujących ograniczeniach liczby kombinacji, które można łatwo sprawdzić poprzez bezpośrednie podstawienie do wzorów multiplikatywnych i silniowych:
Należy również zauważyć, że wzór mnożnikowy pozostaje ważny nawet wtedy, gdy n jest liczbą rzeczywistą, o ile m jest nadal wartością całkowitą. Jednak wówczas wynik obliczeń z jego wykorzystaniem, przy zachowaniu ważności formalnej, traci swój kombinatoryczny sens.
TOŻSAMOŚĆ KOMBINACJI
Praktyczne zastosowanie wzorów multiplikatywnych i silniowych do określenia liczby kombinacji dla dowolnych wartości n i m okazuje się mało 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. Co więcej, 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 wyeliminować czasochłonne operacje przetwarzania dużych ilości, aby określić liczbę kombinacji, można zastosować różne relacje powtarzalności, które bezpośrednio wynikają 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, utrzymanie stałego indeksu dolnego zapewnia następującą relację powtarzalności, 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ą stronę 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łę powtarzania, która pozwala efektywnie określać liczbę kombinacji dla dużych wartości n i m, ponieważ umożliwia zastąpienie operacji mnożenia w iloczynach silni prostszymi operacjami dodawania oraz w przypadku 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 omówiono 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 według indeksu dolnego, który ma następującą postać:
Zależność tę uzyskujemy, jeśli w tożsamości addycyjnej rozwiniemy rekurencję wzdłuż wyrazu o największym indeksie górnym, podczas gdy jego indeks dolny jest większy od 0. Poniższy przykład liczbowy ilustruje ten proces powtarzalnych przekształceń:
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 wzdłuż wyrazu z najmniejszym indeksem górnym. Poniższy przykład liczbowy ilustruje tę wersję przekształceń powtarzalnych:
W ogólnym przypadku w wyniku takich przekształceń otrzymuje się sumę liczb kombinacji, których oba wskaźniki różnią się o jeden od wyrazów sąsiednich, a różnica wskaźników pozostaje stała (w rozpatrywanym przykładzie jest to również równy jeden). W ten sposób otrzymujemy 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 wygląda tak:
Ważność tożsamości symetrii można zweryfikować na poniższym 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ż wyznaczają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, zastępując 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 zastosowania związane są 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 potęg żą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 wymaganą reprezentację w postaci wielomianu zapewnia twierdzenie Newtona o dwumianie, które stwierdza, że prawdziwa jest następująca równość:
Równość tę nazywa się zwykle dwumianem Newtona. Wielomian po prawej stronie tworzy suma 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 kombinacji ze wskaźnikami, które są uzyskiwane z ich mocy. Biorąc pod uwagę szczególną popularność wzoru dwumianu Newtona w analizie kombinatorycznej, terminy współczynnik dwumianu i liczba kombinacji są ogólnie 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 obsłużyć wyższe stopnie (n>3), należy zastosować wzór dwumianu Newtona. Jego zastosowanie do 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 ogólnie przyjęta nazwa nie jest historycznie sprawiedliwa. 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 nieskończoną sumę po prawej stronie i zwykle jest zapisywany 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 specjalną wersją wzoru Maclaurina, który daje rozwinięcie dowolnej funkcji w szereg potęgowy. Newton pokazał to dla |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . Jeśli teraz ustawimy Z=X/Y i pomnożymy lewą i prawą stronę przez Yn, otrzymamy wersję dwumianu Newtona omówioną powyżej.
Pomimo swojej uniwersalności twierdzenie o dwumianu 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 na sumowanie liczb kombinacji według indeksu dolnego i obu wskaźników. Brakującą tożsamość sumowania w indeksie górnym można łatwo uzyskać ze wzoru dwumianu Newtona, wstawiając do niego 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 otrzymujemy tożsamość sumy współczynników dwumianowych tylko z liczbami parzystymi lub tylko nieparzystymi:
Bazując na rozważanych tożsamościach i powtarzającej się zasadzie usuwania indeksów spod znaku liczby kombinacji, można otrzymać szereg ciekawych zależności. Na przykład, jeśli we wzorze na sumowanie w indeksie górnym zastąpimy wszędzie n przez (n1) i usuniemy indeksy w każdym wyrazie, otrzymamy następującą zależność:
Stosując podobną technikę we wzorze na sumę współczynników dwumianu liczb parzystych i nieparzystych, można wykazać zasadność np. następującej zależności:
Kolejna przydatna tożsamość pozwala łatwo obliczyć sumę iloczynów symetrycznie położonych współczynników dwumianu dwóch dwumianów o dowolnych stopniach n i k za pomocą następującego wzoru Cauchy'ego:
Ważność 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 identycznej relacji:
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 linie są uporządkowane według potęg dwumianów od góry do dołu. W każdym wierszu współczynniki dwumianu są ułożone w kolejności rosnącej indeksów górnych 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, przesunięte, tworzą nieskończony trójkąt równoramienny. Jego początkowy fragment dla dwumianów do IV stopnia (n=4) ma postać:
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ści dodawania i symetrii kombinacji liczb. 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żda z jego linii jest palindromem numerycznym współczynników dwumianowych. Wskazane cechy algebraiczne i geometryczne umożliwiają łatwe rozwinięcie trójkąta równoramiennego Pascala i konsekwentne znajdowanie wartości współczynników dwumianowych potęg dowolnych.
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 linie poziome 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ę charakterystyczną dla swojego równoramiennego odpowiednika. Aby to skompensować, 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ę poziomych trójkąta prostokątnego Pascala łatwo zauważyć, że suma elementów dowolnego wiersza o liczbie n jest równa 2n zgodnie ze wzorem na sumowanie dwumianów przez indeks górny. Wynika z tego, że suma elementów powyżej którejkolwiek z poziomych linii 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. Na przykład dla n=4 dodatek ten można zapisać w następujący sposób:
Oto kilka bardziej interesujących właściwości poziomów, 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 (z wyjątkiem zewnętrznych) są liczbami parzystymi. I odwrotnie, wszystkie liczby linii poziomej będą nieparzyste, jeśli jej liczba będzie o jeden mniejsza niż potęga 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ć w przypadku małych wartości liczb konturów pierwszych. Na przykład wszystkie wewnętrzne współczynniki dwumianu piątej poziomej (5, 10 i 5) są oczywiście podzielne przez 5. Aby udowodnić ten wynik dla dowolnej liczby pierwszej poziomej p, należy zapisać wzór multiplikatywny na jej współczynniki dwumianowe 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 stosunek w nawiasach kwadratowych jest liczbą naturalną N i pożądany wynik staje się oczywisty:
Korzystając z tego wyniku, możemy ustalić, że liczby wszystkich prostych poziomych trójkąta Pascala, których elementy wewnętrzne są podzielne przez daną liczbę pierwszą p, są potęgami p, czyli mają postać n=p k. W szczególności, jeśli p=3, to liczba pierwsza p dzieli nie tylko wszystkie elementy wewnętrzne 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źć prostej poziomej, której wszystkie elementy wewnętrzne są podzielne przez liczbę złożoną. W przeciwnym wypadku liczba takiej prostej poziomej musi być jednocześnie potęgą dzielników pierwszych liczby złożonej, przez którą podzielone są wszystkie jej elementy wewnętrzne, co jednak z oczywistych względów jest 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 (NWD) wszystkich elementów wewnętrznych dowolnej linii 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 zwrócić uwagę na jeszcze jedną interesującą właściwość, jaką posiada tworzący je szereg dwumianowych współczynników. Jeśli współczynniki dwumianowe dowolnej linii poziomej o liczbie n pomnożymy przez kolejne potęgi liczby 10, a następnie dodamy wszystkie te iloczyny, otrzymamy wynik 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 liczbowy ilustruje spełnienie tej własnoś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 szereg liczb naturalnych. Gdy m=2 pion składa się z liczb trójkątnych. Każdą liczbę trójkątną można przedstawić na płaszczyźnie w postaci trójkąta równobocznego, 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 przedstawienia. Na przykład 4 początkowe liczby trójkątne reprezentują następujące konfiguracje odpowiedniej liczby symboli nuklearnych „@”:
Warto zauważyć, że w podobny sposób można uwzględnić liczby kwadratowe Sk, które otrzymuje się przez podniesienie do kwadratu liczb naturalnych i ogólnie liczb figurowych wielokątnych, powstałych poprzez regularne wypełnianie 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żemy 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ę rdzeni, które można ułożyć w kształt czworościanu, a indeks określa, ile poziomych trójkątnych warstw rzędów rdzeni potrzeba, aby przedstawić go w przestrzeni trójwymiarowej. W tym przypadku wszystkie warstwy poziome muszą być reprezentowane jako kolejne liczby trójkątne. Elementy kolejnych pionów trójkąta Pascala dla m>3 tworzą szeregi liczb hipertetraedalnych, które nie mają wizualnej 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 kształtu, dla nich można w ten sam sposób obliczyć sumy cząstkowe wartości elementów początkowych, 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 rdzenia, które reprezentują liczby niższego rzędu. W szczególności n-tą liczbę trójkątną Tn można otrzymać sumując wszystkie liczby naturalne reprezentujące jej warstwy liniowe:
Podobnie nie jest trudno znaleźć liczbę czworościenną Pn, obliczając następującą sumę pierwszych n liczb trójkątnych tworzących jej poziome warstwy rdzenia:
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 również jest interesujące. W tym przypadku zwykle dokonuje się rozróżnienia między przekątnymi zstępującymi i rosnącymi. Przekątne skierowane w dół 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ę wartościami swoich elementów z odpowiednimi pionowymi rzędami trójkąta Pascala i dlatego powtarzają wszystkie omówione powyżej właściwości. Wskazaną 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ą szeregi liczbowe geometrycznie prostopadłe do przeciwprostokątnej prawego trójkąta Pascala. Wypełniane są współczynnikami dwumianowymi z ubytkiem dolnego i przyrostem indeksu górnego. W szczególności 7 górnych rosnących przekątnych tworzy następującą sekwencję liczbową bez uwzględnienia końcowych zer:
Ogólnie rzecz biorąc, rosnąca liczba przekątna n zawiera następujące współczynniki dwumianowe, których suma wskaźników każdego z nich jest równa (n1):
Dzięki tożsamoś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. Pozwala to na zbudowanie każdej kolejnej rosnącej przekątnej poprzez parami sumowanie 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 liczby 8 wzdłuż przekątnych liczby 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ń tworzą następujący ciąg liczbowy, zgodnie z którym można sprawdzić ważność rozważanej własności rosnących przekątnych prawego trójkąta 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żemy 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 znajdujących się na jego przekątnej z liczbą (n+2).
Podsumowując, należy zauważyć, że rozpatrywane 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 najdoskonalszych układów liczbowych, którego wszystkich możliwości nie da się 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 może być jednokrotne skonstruowanie trójkąta Pascala, a następnie otrzymanie danych 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 trójkąt nie będzie Ci już potrzebny, wywołaj procedurę 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 żądany 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
WYKAZ KOMBINACJI LICZB NATURALNYCH
Aby rozwiązać wiele praktycznych problemów, konieczne jest wypisanie wszystkich kombinacji ustalonej liczności, jakie można otrzymać z elementów danego zbioru skończonego, a nie tylko określenie ich liczby. 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 prostym z nich jest algorytm wyliczania kombinacji liczb naturalnych porządek leksygraficzny.
Aby formalnie opisać ten algorytm, 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 z bieżącego po przeskanowaniu jego elementów od lewej do prawej w celu znalezienia skrajnego prawego 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ększą od sąsiada 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. Rezultatem jest 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 przez m=4 liczby, czyli wszystkie możliwe 4-elementowe podzbiory głównego generującego zbiór (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 wynoszą odpowiednio 3, 4, 5 i 6. Dla ułatwienia interpretacji wyników, w każdym wektorze kombinacji skrajny prawy element, który ma nie osiągnęła jeszcze wartości maksymalnej, jest podkreślona. 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 używana jest symbolika Appela: W szczególności poniższe obliczenia z wykorzystaniem tego wzoru dla liczby kombinacji (1, 3, 4, 6) n=6 elementów 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 indeksów, można wykazać, że liczba najmniejszej kombinacji leksygraficznej (1, ... i, ... m) obliczona za pomocą tego formuła będzie zawsze równa 1: Jest także oczywiste, że liczba największej leksygraficznie kombinacji (m, … nm+i, … n) obliczona za pomocą tego wzoru będzie równa liczbie kombinacji n elementów na m: Wzór na obliczanie liczb kombinacji leksygraficznych można zastosować do rozwiązania problemu odwrotnego, w którym należy określić wektor kombinacji na podstawie jego numeru w porządku leksygraficznym. Aby rozwiązać taki odwrotny problem, należy go zapisać w formie równania, w którym wszystkie nieznane wartości elementów wektora pożądanej kombinacji (C 1, ... C i, ... C m ) skupiają się w liczbie kombinacji jego prawej strony, a znana różnica L liczby kombinacji jest zapisana po lewej stronie n elementów każdego m i liczby wymaganej kombinacji N: Rozwiązanie tego równania zapewnia następujący algorytm „zachłanny”, podczas którego iteracje wybierają kolejno wartości elementów wektora pożądanej kombinacji. W początkowej iteracji wybierana jest minimalna możliwa (w jej granicach) wartość C 1, przy 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 i analogicznie wyznaczyć wartość C 2 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 wymieniając kombinacje w porządku leksygraficznym należy zadbać o powrót do dowolnej kombinacji otrzymanej wcześniej, wystarczy znać jedynie jej numer. Ponadto możliwe staje się generowanie kombinacji w dowolnej kolejności, która jest regulowana przez dowolnie zadaną sekwencję ich numeracji leksygraficznej. 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 POWTARZAJĄCYMI SIĘ ELEMENTAMI W odróżnieniu od klasycznej kombinacji, w której 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. W tym przypadku 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żna utworzyć 15 następujących kombinacji z powtórzeniami: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
Ogólnie rzecz biorąc, kombinacje z powtórzeniami można utworzyć, wybierając 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, układając je w niemalejącej kolejności od lewej do prawej: Oczywiście przy tej formie zapisu dowolne 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 rosnącej kolejności 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 listowania kombinacji z powtórzeniami n elementów przez m. Wystarczy wymienić np. w porządku leksygraficznym wszystkie C kombinacji (n+m1) elementów m, przekształcając kolejno elementy każdego z nich na odpowiadające im elementy kombinacji z powtórzeniami f, korzystając ze wzoru: W efekcie powstaje ciąg wektorów kombinacji z powtórzeniami elementów, które ułożone są w kolejności wygenerowanej poprzez wypisanie 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 wymienić w porządku leksygraficznym wszystkie kombinacje bez powtórzeń 6 cyfr 1,2,3,4, 5 a 6 to po 4 cyfry, przeliczając je zgodnie ze wskazówkami. Poniższy przykład pokazuje taką konwersję kombinacji (1,3,4,6) z liczbą leksykograficzną 8: Rozważana zgodność jeden do jednego pomiędzy kombinacjami z powtórzeniami elementów i bez nich oznacza, że ich zestawy są równie potężne. Zatem w ogólnym przypadku liczba kombinacji z powtórzeniami n elementów na m jest równa liczbie kombinacji bez powtórzeń (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 rozważanego przykładu, gdzie n=3 i m=4, liczba kombinacji powtórzeń będzie równa 15, co pokrywa się z wynikiem ich bezpośredniego zestawienia: 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 wyznaczane są z równości wartości (n+m1) i (n1) lub (n+m1) i m: Powinno być też całkiem oczywiste, że jeśli m jest równe 1, to nie są możliwe żadne powtórzenia elementów, a zatem dla dowolnej dodatniej wartości n>0 prawdziwa będzie równość: Dodatkowo dla liczb kombinacji z powtórzeniami dla dowolnych dodatnich wartości n i m obowiązuje następująca relacja powtarzalności, która jest podobna do tożsamości dodawania dla liczb kombinacji bez powtórzeń elementów: Właściwie zamienia się we wskazaną tożsamość addycyjną po formalnym podstawieniu odpowiednich liczb kombinacji bez powtórzeń po lewej i prawej stronie: Rozważana relacja powtarzalności może być wykorzystana do efektywnego określenia liczby kombinacji z powtórzeniami, gdy istotne jest wyeliminowanie pracochłonnych operacji obliczania iloczynów silni i zastąpienie ich prostszymi operacjami dodawania. W tym przypadku, 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 wielkości takie wyrazy są równe odpowiednio 1 i i. Poniższy przykład ilustruje zastosowanie tej techniki transformacji dla przypadku n=3 i m=4: WYKAZ KOMBINACJI BINARNYCH Podczas wdrażania kombinacji w sprzęcie lub programowania w języku asemblera ważna jest możliwość przetwarzania rekordów kombinacji w formacie binarnym. W tym przypadku dowolną kombinację n elementów m należy podać w postaci n-bitowej liczby binarnej (B n,...B j,...B 1), gdzie m cyfr jednostkowych oznacza elementy kombinację, a pozostałe (nm) cyfry mają wartości zerowe. Oczywiście w tej formie zapisu różne kombinacje muszą różnić się układem cyfr jedynki 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 przeszukiwania wszystkich n-bitowych zbiorów binarnych o różnych układach m jeden i (nm) bitów zerowych. W najprostszej formie takie wyszukiwanie realizowane jest różnymi metodami transpozycji sąsiednich bitów 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ą skupione w cyfrach najniższego rzędu (po prawej), a kończą, gdy wszystkie jedynki znajdują się w cyfrach wyższego rzędu ( po lewej): Podczas dopasowywania kombinacji początkowych i końcowych sekwencje te różnią się kolejnością, w jakiej wymienione są pośrednie zestawy binarne. Jednak we wszystkich przypadkach każda kolejna kombinacja binarna powstaje z poprzedniej w wyniku wykonania odpowiednich operacji transpozycji i przesunięcia. Jednocześnie różne algorytmy przesunięcia transpozytywnego różnią się sposobem wybierania pary bitów do transpozycji i grupy bitów do przesunięcia. Ta specyfika została omówiona 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 z aktualnej uzyskuje się kolejną kombinację binarną poprzez zastąpienie skrajnej lewej pary cyfr 01 cyfrą 10 (transpozycja) i przesunięcie grupy wiodących cyfr jednostkowych, jeśli takie występują, blisko para 10 uzyskana po transpozycji (przesunięciu). Jeśli w tym przypadku w cyfrach wiodących aktualnej kombinacji binarnej nie ma jednostek, to przesunięcie nie jest wykonywane, nawet jeśli jednostka wiodąca zostanie uzyskana po transpozycji na tym etapie. Przesunięcia nie dokonuje się również wtedy, gdy w najbardziej znaczących bitach przed parą 10 otrzymaną 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 kroki. Tylko transpozycja zapewnia, że skrajne prawe bity 01 zostaną zastąpione przez 10 (zamiast skrajnie lewych), a następnie wszystkie bity po prawej stronie zostaną przesunięte do najmniej znaczących 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 przesunięciem ( T"+S"): Należy zaznaczyć, że iteracje obu algorytmów można zapisać w formie addytywnej, jeżeli kombinacje binarne interpretujemy 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), zawsze można otrzymać z aktualnej kombinacji (B n,…B j,…B 1) wykonując operacje dodawania liczb całkowitych stosując następujący wzór na dodawanie: W tym wzorze addytywnym wykładniki potęg dwójek f i t oznaczają odpowiednio liczbę cyfr zerowych niskiego rzędu bieżącej kombinacji binarnej i liczbę jedynek w rzędzie po ich lewej stronie. Na przykład dla czwartej kombinacji binarnej (001110) n=6 cyfr f =1 i t =3. Dlatego obliczenie kolejnej kombinacji binarnej przy użyciu wzoru addytywnego w iteracji 5 da następujący wynik, 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 po 2, które uzyskuje się odpowiednio za pomocą algorytmów przesunięcia lewego (TSL) i prawego (TSR): Porównując te 2 sekwencje widać, że są one odwróconym lustrem. 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ą dla siebie lustrzanym odbiciem, to znaczy pokrywają się, gdy indeksowanie bitów w którymkolwiek z nich zostanie odwrócone. 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. Ogólnie rzecz biorąc, każda kombinacja binarna z liczbą i jednego ciągu jest lustrzanym odbiciem kombinacji binarnej z liczbą (ni+1) innego ciągu. Ta zależność pomiędzy tymi ciągami 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 rejestrować także kombinacje z powtórzeniami elementów. Aby to zrobić, konieczne jest ustalenie zgodności 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ą uzyskamy wybierając m opcjonalnie różnych elementów z n elementów zespołu prądotwórczego. Aby ustalić pożądane dopasowanie, należy najpierw dodać do kombinacji wszystkie elementy zestawu tworzącego (cat), a następnie powstałą konkatenację (sort) posortować tak, aby wszystkie identyczne elementy znajdowały się obok siebie. Wynikiem jest ciąg (n+m) elementów, w którym istnieje n grup identycznych elementów. Łącznie będzie (n+m1) przerw pomiędzy elementami, wśród których będzie (n1) przerw pomiędzy grupami identycznych elementów oraz m przerw pomiędzy elementami w obrębie grup. Dla przejrzystości możesz umieścić symbole „|” we wskazanych miejscach. i odpowiednio. Jeśli teraz dopasujemy 1 do spacji między grupami (|) i 0 do wszystkich pozostałych spacji (), otrzymamy kombinację binarną. Tworzy go binarny zbiór (n+m1) bitów, gdzie (n1) to jedynki, a m bitów zerowych, których położenie jednoznacznie odpowiada oryginalnej kombinacji z powtórzeniami elementów od n do m. Rozważaną technikę transformacji ilustruje następujący przykład konstrukcji kombinacji binarnej (1001101) przy użyciu kombinacji 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 (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, m każdy. 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ć wymagane kombinacje za pomocą powtórzeń, korzystając z powstałych kombinacji binarnych. Zawsze można to zrobić, stosując następującą technikę odzyskiwania. Niech zbiór główny, z którego powstaną kombinacje z powtórzeniami m niekoniecznie różnych elementów, będzie uporządkowany w sposób dowolny, tak aby każdy z jego elementów miał określony numer porządkowy od 1 do n. Zaimplementujmy także wyliczenie kombinacji binarnych (n+m1) cyfr binarnych, gdzie (n1) jedynek i m cyfr zerowych. 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. Wówczas liczba zer w wierszu 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 za pomocą kombinacji binarnej (1001101) odtwarzana jest kombinacja z powtórzeniami BBD, której elementy wybierane są 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 po 3. W kombinatoryce badają pytania o to, ile kombinacji danego typu można utworzyć z danych obiektów (elementów). Narodziny kombinatoryki jako gałęzi kojarzone są z pracami B. Pascala i P. Fermata na temat teorii hazardu. Wielki wkład w rozwój metod kombinatorycznych wniósł G.V. Leibniza, J. Bernoulliego i L. Eulera. Francuski filozof, pisarz, matematyk i fizyk Blaise Pascal (1623–1662) wcześnie wykazał się swoimi wybitnymi zdolnościami matematycznymi. Zakres zainteresowań matematycznych Pascala był bardzo różnorodny. Pascal udowodnił jedno Gottfried Wilhelm Leibniz (1646–1716) był niemieckim filozofem, matematykiem, fizykiem i wynalazcą, prawnikiem, historykiem i językoznawcą. W matematyce wraz z I. Newtonem opracował rachunek różniczkowy i całkowy. Wniósł istotny wkład w kombinatorykę. W szczególności jego nazwisko kojarzone jest z problemami teorii liczb. Gottfried Wilhelm Leibniz nie miał zbyt imponującego wyglądu i dlatego sprawiał wrażenie raczej zwyczajnej osoby. Pewnego dnia w Paryżu wszedł do księgarni w nadziei, że kupi książkę znajomego filozofa. Kiedy gość zapytał o tę książkę, księgarz, obejrzawszy go od stóp do głów, kpiąco powiedział: „Po co ci to? Czy naprawdę potrafisz czytać takie książki?” Zanim naukowiec zdążył odpowiedzieć, do sklepu wszedł sam autor książki ze słowami: „Pozdrowienia i szacunek dla Wielkiego Leibniza!” Sprzedawca nie mógł zrozumieć, że to naprawdę był słynny Leibniz, którego książki cieszyły się dużym zainteresowaniem wśród naukowców. W przyszłości następujące elementy będą odgrywać ważną rolę Lemat. Wpuść zestaw elementów i zestaw - elementy. Następnie liczba wszystkich odrębnych par gdzie będzie równa . Dowód. Rzeczywiście z jednego elementu ze zbioru możemy stworzyć tak różne pary i w sumie w zbiorze elementów. Umiejscowienia, permutacje, kombinacje Załóżmy, że mamy zbiór trzech elementów. W jaki sposób możemy wybrać dwa z tych elementów? . Definicja. Układy zbioru różnych elementów według elementów to kombinacje, które składają się z danych elementów według > elementów i różnią się albo samymi elementami, albo kolejnością elementów. Liczbę wszystkich układów zbioru elementów według elementów oznaczamy (od pierwszej litery francuskiego słowa „układ”, co oznacza układ), gdzie i . Twierdzenie. Liczba rozmieszczeń zbioru elementów według elementów jest równa Dowód. Powiedzmy, że mamy elementy. Niech będą możliwe miejsca docelowe. Będziemy budować te miejsca docelowe sekwencyjnie. Najpierw zdefiniujmy pierwszy element rozmieszczenia. Z danego zbioru elementów można go wybierać na różne sposoby. Po wybraniu pierwszego elementu nadal istnieją sposoby na wybranie drugiego elementu itp. Ponieważ każdy taki wybór daje nowe miejsce, wszystkie te wybory można ze sobą dowolnie łączyć. Dlatego mamy: Przykład. Na ile sposobów flaga może składać się z trzech poziomych pasów w różnych kolorach, jeśli materiał jest w pięciu kolorach? Rozwiązanie. Wymagana ilość flag trójpasmowych: Definicja. Permutacja zbioru elementów to ułożenie elementów w określonej kolejności. Zatem wszystkie różne permutacje zbioru trzech elementów są Wskazana jest liczba wszystkich permutacji elementów (od pierwszej litery francuskiego słowa „permutacja”, co oznacza „permutacja”, „ruch”). Dlatego liczbę wszystkich różnych permutacji oblicza się ze wzoru Przykład. Na ile sposobów można ustawić wieże na szachownicy, aby się nie atakowały? Rozwiązanie. Wymagana liczba wież A-przeorat! Definicja. Kombinacje różnych elementów po elementach to kombinacje, które składają się z danych elementów po elementach i różnią się co najmniej jednym elementem (innymi słowy -elementowymi podzbiorami danego zbioru elementów). Jak widać, w kombinacjach, w przeciwieństwie do rozmieszczeń, nie jest brana pod uwagę kolejność elementów. Wskazana jest liczba wszystkich kombinacji elementów, elementów w każdym (od pierwszej litery francuskiego słowa „kombinacja”, co oznacza „kombinacja”). Liczby Wszystkie kombinacje z zestawu dwóch są . Właściwości liczb (\sf C)_n^k Rzeczywiście, każdy podzbiór -elementów danego zbioru -elementów odpowiada jednemu i tylko jednemu podzbiórowi -elementów tego samego zbioru. Rzeczywiście, podzbiory elementów możemy wybierać w następujący sposób: naprawić jeden element; liczba podzbiorów -elementów zawierających ten element jest równa ; liczba podzbiorów -element niezawierających tego elementu jest równa . Trójkąt Pascala W tym trójkącie skrajne liczby w każdym rzędzie są równe 1, a każda liczba nieekstremalna jest równa sumie dwóch liczb znajdujących się nad nią z poprzedniego wiersza. Zatem ten trójkąt pozwala obliczać liczby. Twierdzenie. Dowód. Rozważmy zbiór elementów i rozwiążmy następujące zadanie na dwa sposoby: ile ciągów można utworzyć z elementów danego zbioru 1 sposób. Wybieramy pierwszego członka sekwencji, następnie drugiego, trzeciego itd. członek Metoda 2. Wybierzmy najpierw elementy z danego zbioru, a następnie ułóżmy je w jakiejś kolejności Pomnóż licznik i mianownik tego ułamka przez: Przykład. Na ile sposobów możesz wybrać 5 liczb z 36 w grze „Sportloto”? Wymagana liczba sposobów Zadania. 1.
Tablice rejestracyjne samochodów składają się z 3 liter alfabetu rosyjskiego (33 litery) i 4 cyfr. Ile jest różnych numerów rejestracyjnych? Partycje uważa się za różne, jeśli różnią się liczbą lub kolejnością ich elementów. Ile jest różnych podziałów liczby na wyrazy? Liczba kombinacji Połączenie z N Przez k zwany zestawem k elementy wybrane z danych N elementy. Zestawy różniące się jedynie kolejnością elementów (ale nie kompozycją) uważa się za identyczne, dlatego kombinacje różnią się od rozmieszczenia. Liczba kombinacji N Przez k
równy współczynnikowi dwumianu Dla stałej wartości N generowanie funkcji liczby kombinacji z powtórzeniami z 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 to, co zewnętrzne warunki podczas fotografowania (zwykle jasność obiektu i światłoczułość użytego materiału fotograficznego). Dowolną wartość E. h. można wybrać kilkukrotnie. kombinacje numer przysłony... ... Wielki 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 pozostałości jej wpływów pozostają. 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 określa sposób budowy... ... 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 identyczne, te kombinacje... ...Wikipedia Zajmuje się badaniem zdarzeń, których wystąpienie nie jest znane z całą pewnością. 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 niepotrzebne... ... Encyklopedia Colliera 1) to samo, co matematyczna analiza kombinatoryczna. 2) Dział matematyki elementarnej związany z badaniem liczby kombinacji, które pod pewnymi warunkami można utworzyć z danego skończonego zbioru obiektów... ... Wielka encyklopedia radziecka - (greckie paradoksos nieoczekiwany, dziwny) w szerokim znaczeniu: stwierdzenie ostro odbiegające od ogólnie przyjętej, ustalonej opinii, zaprzeczenie temu, co wydaje się „bezwarunkowo poprawne”; w węższym znaczeniu dwa przeciwstawne stwierdzenia, gdyż... ... Encyklopedia filozoficzna - (lub zasada włączeń i wyłączeń) wzór kombinatoryczny, który pozwala określić liczność 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 znanym porządku; jest szczególnie ważne w teorii równań i teorii prawdopodobieństwa. Najprostsze zadania tego typu to... ... Słownik encyklopedyczny F.A. Brockhausa i I.A. Efrona W tym artykule porozmawiamy o specjalnej gałęzi matematyki zwanej kombinatoryką. Wzory, reguły, przykłady rozwiązywania problemów – to wszystko znajdziesz czytając artykuł do samego końca. Czym więc jest ta sekcja? Kombinatoryka zajmuje się problemem liczenia dowolnych obiektów. Ale w tym przypadku obiektami nie są śliwki, gruszki czy jabłka, ale coś innego. Kombinatoryka pomaga nam znaleźć prawdopodobieństwo zdarzenia. Na przykład podczas gry w karty – jakie jest prawdopodobieństwo, że przeciwnik ma atut? Albo ten przykład: jakie jest prawdopodobieństwo, że z worka dwudziestu kulek wypadnie biała kulka? Do rozwiązywania tego rodzaju problemów musimy znać przynajmniej podstawy tej gałęzi matematyki. Rozważając problematykę podstawowych pojęć i wzorów kombinatoryki, nie sposób nie zwrócić uwagi na konfiguracje kombinatoryczne. Służą nie tylko do formułowania, ale także do rozwiązywania różnych przykładów.Przykładami takich modeli są: O pierwszych trzech porozmawiamy bardziej szczegółowo później, ale w tej sekcji zwrócimy uwagę na kompozycję i partycjonowanie. Kiedy mówią o składzie pewnej liczby (na przykład a), mają na myśli przedstawienie liczby a jako uporządkowanej sumy pewnych liczb dodatnich. A podział jest sumą nieuporządkowaną. Zanim przejdziemy bezpośrednio do formuł kombinatoryki i rozpatrywania problemów, warto zwrócić uwagę na fakt, że kombinatoryka, podobnie jak inne gałęzie matematyki, ma swoje własne podrozdziały. Obejmują one: W pierwszym przypadku mówimy o kombinatoryce obliczeniowej, problemy dotyczą wyliczania lub liczenia różnych konfiguracji, które tworzą elementy zbiorów. Z reguły na te zbiory nakładane są pewne ograniczenia (odrębność, nierozróżnialność, możliwość powtórzenia itp.). A liczbę tych konfiguracji oblicza się za pomocą zasad dodawania lub mnożenia, o których porozmawiamy nieco później. Kombinatoryka strukturalna obejmuje teorie grafów i matroidów. Przykładem ekstremalnego problemu kombinatoryki jest największy wymiar grafu spełniającego następujące własności... W czwartym akapicie wspomnieliśmy o teorii Ramseya, która bada obecność struktur regularnych w losowych konfiguracjach. Kombinatoryka probabilistyczna jest w stanie odpowiedzieć na pytanie - jakie jest prawdopodobieństwo, że dany zbiór ma określoną własność. Jak można się domyślić, kombinatoryka topologiczna stosuje metody w topologii. I wreszcie punkt siódmy - nieskończona kombinatoryka bada zastosowanie metod kombinatoryki do zbiorów nieskończonych. Wśród formuł kombinatoryki można znaleźć formuły całkiem proste, z którymi znamy się już od dawna. Przykładem jest reguła sumy. Załóżmy, że mamy dane dwie akcje (C i E), jeśli się one wykluczają, akcję C można wykonać na kilka sposobów (na przykład a), a akcję E można wykonać na b-sposoby, to dowolny z nich ( C lub E) można wykonać na sposoby a + b. Teoretycznie jest to dość trudne do zrozumienia, postaramy się przekazać całość na prostym przykładzie. Weźmy średnią liczbę uczniów w jednej klasie – powiedzmy, że wynosi ona dwudziestu pięciu. Wśród nich jest piętnaście dziewcząt i dziesięciu chłopców. Do każdych zajęć przydzielana jest codziennie jedna osoba dyżurująca. Na ile sposobów można obecnie wyznaczyć opiekuna klasy? Rozwiązanie problemu jest dość proste, skorzystamy z reguły dodawania. Z treści zadania nie wynika, że na służbie mogą pełnić wyłącznie chłopcy lub tylko dziewczęta. Zatem może to być dowolna z piętnastu dziewcząt lub którykolwiek z dziesięciu chłopców. Stosując regułę sumy, otrzymujemy dość prosty przykład, z którym bez problemu poradzi sobie uczeń szkoły podstawowej: 15 + 10. Po przeliczeniu otrzymujemy odpowiedź: dwadzieścia pięć. Oznacza to, że na dzień dzisiejszy istnieje tylko dwadzieścia pięć sposobów przydzielenia klasy dyżurującej. Do podstawowych wzorów kombinatoryki zalicza się także regułę mnożenia. Zacznijmy od teorii. Załóżmy, że musimy wykonać kilka akcji (a): pierwszą akcję wykonujemy na 1 sposób, drugą na 2 sposoby, trzecią na 3 sposoby i tak dalej, aż do ostatniej akcji wykonywanej na 3 sposoby. Wtedy wszystkie te akcje (w sumie mamy) można wykonać na N sposobów. Jak obliczyć nieznane N? Pomoże nam w tym wzór: N = c1 * c2 * c3 **…* ca. Znów nic nie jest jasne w teorii, więc przejdźmy do prostego przykładu zastosowania reguły mnożenia. Weźmy tę samą dwudziestopięcioosobową klasę, w której jest piętnaście dziewcząt i dziesięciu chłopców. Tylko tym razem musimy wybrać dwie osoby na służbie. Mogą to być tylko chłopcy lub dziewczęta, albo chłopiec i dziewczynka. Przejdźmy do elementarnego rozwiązania problemu. Wybieramy pierwszą osobę na dyżurze, jak ustaliliśmy w ostatnim akapicie, otrzymujemy dwadzieścia pięć możliwych opcji. Drugą osobą pełniącą dyżur może być dowolna z pozostałych osób. Mieliśmy dwudziestu pięciu uczniów, wybraliśmy jednego, co oznacza, że drugą osobą na dyżurze może być dowolna z pozostałych dwudziestu czterech osób. Na koniec stosujemy zasadę mnożenia i stwierdzamy, że dwóch funkcjonariuszy pełniących służbę można wybrać na sześćset sposobów. Otrzymaliśmy tę liczbę, mnożąc dwadzieścia pięć i dwadzieścia cztery. Teraz przyjrzymy się innej formule kombinatoryki. W tej części artykułu porozmawiamy o permutacjach. Proponujemy natychmiastowe rozważenie problemu na przykładzie. Weźmy kule bilardowe, mamy ich n-tą liczbę. Musimy policzyć, ile jest opcji, aby ułożyć je w rząd, czyli stworzyć uporządkowany zestaw. Zacznijmy, jeśli nie mamy piłek, to mamy również zerowe możliwości umieszczenia. A jeśli mamy jedną kulę, to układ też jest taki sam (matematycznie można to zapisać następująco: P1 = 1). Dwie kule można ułożyć na dwa różne sposoby: 1,2 i 2,1. Zatem P2 = 2. Trzy kule można ułożyć na sześć sposobów (P3 = 6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. A co jeśli nie będzie trzech takich piłek, ale dziesięć lub piętnaście? Wypisanie wszystkich możliwych opcji zajęłoby bardzo dużo czasu, wtedy z pomocą przychodzi nam kombinatoryka. Wzór permutacji pomoże nam znaleźć odpowiedź na interesujące nas pytanie. Pn = n * P (n-1). Jeśli spróbujemy uprościć wzór, otrzymamy: Pn = n* (n - 1) ** 2 * 1. A to jest iloczyn pierwszych liczb naturalnych. Liczba ta nazywana jest silnią i jest oznaczana jako n! Rozważmy problem. Każdego ranka doradca ustawia swój zespół (dwadzieścia osób). W drużynie jest trzech najlepszych przyjaciół - Kostya, Sasha i Lesha. Jakie jest prawdopodobieństwo, że staną obok siebie? Aby znaleźć odpowiedź na pytanie, należy podzielić prawdopodobieństwo „dobrego” wyniku przez całkowitą liczbę wyników. Całkowita liczba permutacji wynosi 20! = 2,5 tryliona. Jak policzyć liczbę „dobrych” wyników? Załóżmy, że Kostya, Sasha i Lesha są jednym supermanem. Zatem mamy tylko osiemnaście przedmiotów. Liczba permutacji w tym przypadku wynosi 18 = 6,5 biliarda. Dzięki temu Kostya, Sasha i Lesha mogą dowolnie poruszać się między sobą w swojej niepodzielnej trójce, a to jeszcze 3! = 6 opcji. Oznacza to, że w sumie mamy 18 „dobrych” aranżacji! * 3! Wszystko, co musimy zrobić, to znaleźć pożądane prawdopodobieństwo: (18! * 3!) / 20! Co równa się w przybliżeniu 0,016. Jeśli przeliczyć na procenty, okazuje się, że jest to zaledwie 1,6%. Teraz przyjrzymy się innej bardzo ważnej i niezbędnej formule kombinatoryki. Pozycjonowanie to nasze kolejne zagadnienie, do rozważenia którego zapraszamy w tej części artykułu. Idziemy w stronę komplikacji. Załóżmy, że chcemy rozważyć możliwe permutacje nie z całego zbioru (n), ale z mniejszego (m). Oznacza to, że rozważamy permutacje n elementów przez m. Podstawowe formuły kombinatoryki należy nie tylko zapamiętać, ale i zrozumieć. Chociaż stają się one bardziej skomplikowane, ponieważ mamy nie jeden parametr, ale dwa. Załóżmy, że m = 1, następnie A = 1, m = 2, następnie A = n * (n - 1). Jeśli jeszcze bardziej uprościmy wzór i przejdziemy na notację za pomocą silni, otrzymamy całkowicie lakoniczny wzór: A = n! / (n - m)! Przeanalizowaliśmy prawie wszystkie podstawowe formuły kombinatoryki z przykładami. Przejdźmy teraz do ostatniego etapu rozważań na temat podstawowego kursu kombinatoryki – poznawania kombinacji. Teraz wybierzemy m elementów z n, które mamy i wybierzemy wszystko na wszelkie możliwe sposoby. Czym to się zatem różni od umiejscowienia? Zamówienie nie będzie brane pod uwagę. Ten nieuporządkowany zestaw będzie kombinacją. Wprowadźmy od razu zapis: C. Rozmieszczenie m piłek bierzemy z n. Przestajemy zwracać uwagę na kolejność i kończymy na powtarzających się kombinacjach. Aby otrzymać liczbę kombinacji, liczbę miejsc docelowych należy podzielić przez m! (m silnia). Oznacza to, że C = A / m! Zatem istnieje tylko kilka sposobów wyboru spośród n kulek, co jest w przybliżeniu równe liczbie sposobów wyboru prawie wszystkich z nich. Jest na to logiczne wyrażenie: wybrać trochę, to to samo, co wyrzucić prawie wszystko. Należy również wspomnieć w tym miejscu, że maksymalną liczbę kombinacji można uzyskać, próbując wybrać połowę elementów. Szczegółowo zbadaliśmy podstawowe formuły kombinatoryki: umiejscowienie, permutacja i kombinacja. Teraz naszym zadaniem jest ułatwienie wyboru niezbędnego wzoru do rozwiązania problemu kombinatoryki. Możesz użyć następującego dość prostego schematu: Przyjrzeliśmy się elementom kombinatoryki, formułom i kilku innym zagadnieniom. Przejdźmy teraz do rozważenia prawdziwego problemu. Wyobraź sobie, że masz przed sobą kiwi, pomarańczę i banana. Pytanie pierwsze: na ile sposobów można je przestawić? W tym celu skorzystamy ze wzoru permutacyjnego: P = 3! = 6 sposobów. Pytanie drugie: na ile sposobów możesz wybrać jeden owoc? To oczywiste, mamy tylko trzy możliwości – wybierz kiwi, pomarańczę lub banana, ale zastosujmy wzór na kombinację: C = 3! / (2! * 1!) = 3. Pytanie trzecie: na ile sposobów możesz wybrać dwa owoce? Jakie w ogóle mamy opcje? Kiwi i pomarańcza; kiwi i banan; pomarańcza i banan. Oznacza to, że istnieją trzy opcje, ale łatwo to sprawdzić za pomocą wzoru kombinacji: C = 3! / (1! * 2!) = 3 Pytanie czwarte: na ile sposobów możesz wybrać trzy owoce? Jak widać, istnieje tylko jeden sposób wyboru trzech owoców: weź kiwi, pomarańczę i banana. C = 3! / (0! * 3!) = 1. Pytanie piąte: na ile sposobów możesz wybrać przynajmniej jeden owoc? Warunek ten oznacza, że możemy zjeść jeden, dwa lub wszystkie trzy owoce. Dlatego dodajemy C1 + C2 + C3 = 3 + 3 + 1 = 7. Oznacza to, że mamy siedem sposobów na pobranie przynajmniej jednego owocu ze stołu. Policzmy w MS EXCEL liczbę kombinacji n elementów przez k. Za pomocą wzorów wyświetlimy na arkuszu wszystkie warianty kombinacji (angielskie tłumaczenie terminu: Kombinacje bez powtórzeń). Kombinacje n różnych elementów k elementów to kombinacje, które różnią się co najmniej jednym elementem. Przykładowo poniżej znajdują się WSZYSTKIE kombinacje 3-elementowe wzięte z zestawu składającego się z 5 elementów (1; 2; 3; 4; 5): (1; 2; 3); (1; 2; 4); (1; 2; 5); (1; 3; 4); (1; 3; 5); (1; 4; 5); (2; 3; 4); (2; 3; 5); (2; 4; 5); (3; 4; 5) Notatka: To jest artykuł o liczeniu kombinacji w programie MS EXCEL. Zalecamy zapoznanie się z podstawami teoretycznymi w specjalistycznym podręczniku. Uczenie się kombinacji z tego artykułu to zły pomysł. W przykładowym pliku utworzone zostały formuły wyświetlające wszystkie Kombinacje dla danych n i k. Określając liczbę elementów zbioru (n) i liczbę elementów, które z niego wybieramy (k), za pomocą wzorów możemy wyświetlić wszystkie Kombinacje. Transporter samochodowy może przewieźć 4 samochody. Do przewiezienia jest 7 różnych samochodów (LADA Granta, Hyundai Solaris, KIA Rio, Renault Duster, Łada Kalina, Volkswagen Polo, Łada Largus). Na ile różnych sposobów można napełnić pierwszy transporter samochodowy? Konkretne miejsce samochodu w transporterze samochodowym nie jest istotne. Musimy ustalić liczbę Kombinacje 7 samochodów na 4 miejscach autotransportera. Te. n=7 i k=4. Okazuje się, że jest 35 takich opcji = LICZBA KOMB(7,4).
z podstawowych twierdzeń geometrii rzutowej (twierdzenie Pascala), zaprojektował maszynę sumującą (maszynę dodającą Pascala), podał metodę obliczania współczynników dwumianowych (trójkąt Pascala), jako pierwszy dokładnie zdefiniował i zastosował metodę indukcji matematycznej do dowodu, uczynił znaczący krok w rozwoju analizy nieskończenie małej, odegrał ważną rolę w powstaniu teorii prawdopodobieństwa. W hydrostatyce Pascal ustanowił swoje podstawowe prawo (prawo Pascala). „Listy do prowincjała” Pascala były arcydziełem francuskiej prozy klasycznej.
zestawy, w których żaden element nie pojawia się dwukrotnie?
2.
Fortepian ma 88 klawiszy. Na ile sposobów możesz wydać kolejno 6 dźwięków?
3.
Ile jest liczb sześciocyfrowych podzielnych przez 5?
4.
Na ile sposobów można umieścić 7 różnych monet w trzech kieszeniach?
5.
Ile liczb pięciocyfrowych można utworzyć, w których w zapisie dziesiętnym przynajmniej raz pojawia się cyfra 5?
6.
Na ile sposobów można posadzić 20 osób przy okrągłym stole, biorąc pod uwagę sposoby, aby były takie same, jeśli można je uzyskać od siebie, poruszając się po okręgu?
7.
Ile jest liczb pięciocyfrowych, które są podzielne przez 5 i nie zawierają identycznych cyfr?
8.
Na papierze w kratkę o boku komórki 1 cm narysowano okrąg o promieniu 100 cm, który nie przechodzi przez wierzchołki komórek i nie dotyka boków komórek. Ile komórek może przeciąć ten okrąg?
9.
Na ile sposobów można ułożyć liczby w rzędzie, tak aby liczby sąsiadowały ze sobą i były ułożone w kolejności rosnącej?
10.
Ile liczb pięciocyfrowych można utworzyć z cyfr, jeśli każdej cyfry można użyć tylko raz?
11.
Ze słowa ROT, przestawiając litery, można uzyskać następujące słowa: TOP, ORT, OTR, TRO, RTO. Nazywa się je anagramami. Ile anagramów można ułożyć ze słowa LOGARITM?
12.
Zadzwońmy rozdzielać liczba naturalna, jej przedstawienie jako suma liczb naturalnych. Oto na przykład wszystkie części liczby:
13.
Ile jest liczb trzycyfrowych o nierosnącym porządku cyfr?
14.
Ile jest liczb czterocyfrowych o nierosnącym porządku cyfr?
15.
Na ile sposobów można ustawić 17 osób w rzędzie tak, aby znalazły się obok siebie?
16.
dziewczęta i chłopcy siedzą losowo w rzędach siedzeń. Na ile sposobów można je usiąść tak, aby żadne dwie dziewczyny nie siedziały obok siebie?
17.
dziewczęta i chłopcy siedzą losowo w rzędach siedzeń. Na ile sposobów można je posadzić tak, aby wszystkie dziewczynki usiadły obok siebie?Wyraźne formuły
Spinki do mankietów
Zobacz, co oznacza „Liczba kombinacji” w innych słownikach:
Książki
Konfiguracje kombinatoryczne
Sekcje
Zasada dodawania
Reguła mnożenia
Przegrupowanie
Zakwaterowanie
Połączenie
Jak wybrać formułę rozwiązania problemu?
Przykład
Różnica między kombinacjami i miejscami docelowymi
Wyświetlanie wszystkich kombinacji kombinacji
Zadanie