Współczynnik dwumianowy - Binomial coefficient
W matematyce , że dwumianowy współczynniki są dodatnie liczby całkowite , które występują jako współczynniki w dwumianowym twierdzenia . Zwykle dwumianowego współczynnik jest indeksowany przez parę liczb całkowitych n ≥ k ≥ 0 i jest zapisywany Jest to współczynnik x k terminu w wielomian ekspansji w dwumianowego mocy (1 + x ) n i jest podane przez wzór
Na przykład czwarta potęga 1 + x to
a współczynnik dwumianowego jest współczynnik x 2 okresie.
Ułożenie liczb w kolejnych wierszach daje trójkątną tablicę zwaną trójkątem Pascala , spełniającą relację powtarzalności
Współczynniki dwumianowe występują w wielu dziedzinach matematyki, a zwłaszcza w kombinatoryce . Symbol jest zwykle odczytywany jako „ n wybierz k ”, ponieważ istnieją sposoby na wybranie (nieuporządkowanego) podzbioru k elementów ze ustalonego zestawu n elementów. Na przykład istnieją sposoby wyboru 2 elementów z a mianowicie i
Współczynniki dwumianowe można uogólnić na dowolną liczbę zespoloną z i liczbę całkowitą k ≥ 0 , a wiele ich własności nadal zachowuje tę bardziej ogólną formę.
Historia i notacja
Andreas von Ettingshausen wprowadził notację w 1826 roku, chociaż liczby były znane wieki wcześniej (patrz trójkąt Pascala ). Najwcześniejsze znane szczegółowe omówienie Symbol Newtona jest w komentarzu X wieku, przez Halayudha , na starożytnych sanskryckiego tekstu, Pingala „s Chandaḥśāstra . Około roku 1150 indyjski matematyk Bhaskaracharya przedstawił w swojej książce Līlāvatī wykłady dotyczące współczynników dwumianowych .
Alternatywne zapisy obejmują C ( n , k ) , n C k , n C k , C k n , C n k i C n , k we wszystkich z których C oznacza kombinacje lub wybory . Wiele kalkulatorów używa wariantów notacji C, ponieważ mogą ją przedstawić na wyświetlaczu jednowierszowym. W tej postaci współczynniki dwumianowe można łatwo porównać z k -permutacjami n , zapisanymi jako P ( n , k ) , itd.
Definicja i interpretacje
k
n
|
0 | 1 | 2 | 3 | 4 | ⋯ |
---|---|---|---|---|---|---|
0 | 1 | 0 | 0 | 0 | 0 | ⋯ |
1 | 1 | 1 | 0 | 0 | 0 | ⋯ |
2 | 1 | 2 | 1 | 0 | 0 | ⋯ |
3 | 1 | 3 | 3 | 1 | 0 | ⋯ |
4 | 1 | 4 | 6 | 4 | 1 | ⋯ |
⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋱ |
Kilka pierwszych współczynników dwumianowych na wyrównanym do lewej trójkącie Pascala |
Dla liczb naturalnych (przyjmowana zawierać 0) n i k , dwumianowy współczynnik może być zdefiniowana jako współczynnik z Jednomian X K w ekspansji (1 + X ) n . Ten sam współczynnik występuje również (jeśli k ≤ n ) we wzorze dwumianowym
-
( * ),
(ważne dla wszystkich elementów, x , y, o zmiennym pierścieniu ), co wyjaśnia nazwę „Symbol Newtona”.
Innym występowaniem tej liczby jest kombinatoryka, gdzie podaje ona liczbę sposobów, nie zważając na kolejność, że k obiektów może być wybranych spośród n obiektów; bardziej formalnie, liczba k -elementowych podzbiorów (lub k - kombinacji ) zbioru n -elementowego. Liczba ta może być postrzegane jako równa jeden z pierwszą definicją niezależnie któregokolwiek z poniższych wzorów, aby ją obliczyć: jeśli w każdym z n czynników mocy (1 + X ) n jeden tymczasowo etykiet termin X ze związkiem indeks i (od 1 do n ), to każdy podzbiór k indeksów daje po rozwinięciu wkład X k , a współczynnik tego jednomianu w wyniku będzie liczbą takich podzbiorów. Pokazuje to w szczególności, że jest to liczba naturalna dla dowolnych liczb naturalnych n i k . Istnieje wiele innych kombinatorycznych interpretacji współczynników dwumianowych (zagadnień liczenia, dla których odpowiedź jest podana przez wyrażenie współczynnika dwumianowego), na przykład liczba słów utworzonych z n bitów (cyfry 0 lub 1), których suma wynosi k jest podana przez , natomiast liczba sposobów pisania, w których każde a i jest nieujemną liczbą całkowitą, jest dana przez . Łatwo zauważyć, że większość z tych interpretacji jest równoważna liczeniu k- kombinacji.
Obliczanie wartości współczynników dwumianowych
Istnieje kilka metod obliczania wartości bez faktycznego rozszerzania potęgi dwumianowej lub liczenia k -kombinacji.
Formuła rekurencyjna
Jedna metoda wykorzystuje rekurencyjną , czysto addytywną formułę
- dla wszystkich liczb całkowitych takich, że
z wartościami początkowymi/granicznymi
- dla wszystkich liczb całkowitych
Formuła wynika z rozpatrzenia zbioru {1, 2, 3, ..., n } i zliczenia osobno (a) zgrupowań k- elementowych, które zawierają określony element zbioru, powiedzmy „ i ”, w każdej grupie (od „ i ” " jest już wybrane, aby wypełnić jedno miejsce w każdej grupie, musimy tylko wybrać k − 1 z pozostałych n − 1) i (b) wszystkie k -grupowania, które nie zawierają " i "; to wylicza wszystkie możliwe kombinacje k n elementów. Wynika to również z prześledzenia wkładów do X k w (1 + X ) n -1 (1 + X ) . Ponieważ istnieje zero X n +1 lub X -1 w (1 + X ) n , można rozszerzyć definicję poza powyższe granice, aby uwzględnić, gdy albo k > n, albo k < 0. Ta rekursywna formuła pozwala na skonstruowanie wzoru Pascala trójkąt , otoczony białymi spacjami w miejscu zer lub trywialnych współczynników.
Wzór mnożnikowy
Bardziej wydajną metodę obliczania poszczególnych współczynników dwumianowych podaje wzór
gdzie licznik pierwszego ułamka jest wyrażony jako spadająca potęga silni . Ten wzór jest najłatwiejszy do zrozumienia przy kombinatorycznej interpretacji współczynników dwumianowych. Licznik podaje liczbę sposobów wyboru sekwencji k różnych obiektów, zachowując kolejność wyboru, z zestawu n obiektów. Mianownik zlicza liczbę odrębnych sekwencji, które definiują tę samą k- kombinację, gdy nie uwzględnia się kolejności.
Ze względu na symetrię współczynnika dwumianowego względem k i n − k , obliczenia można zoptymalizować, ustawiając górną granicę iloczynu powyżej na mniejszą z k i n − k .
Formuła czynnikowa
Wreszcie, chociaż obliczeniowo nieodpowiednie, istnieje zwarta forma, często używana w dowodach i wyprowadzeniach, która wielokrotnie używa znanej funkcji silni :
gdzie n ! oznacza silnię n . Formuła ta wynika z powyższej formuły multiplikatywnej przez pomnożenie licznika i mianownika przez ( n − k )! ; w konsekwencji obejmuje wiele czynników wspólnych dla licznika i mianownika. Jest to mniej praktyczne w przypadku obliczeń jawnych (w przypadku, gdy k jest małe, a n jest duże), chyba że wspólne czynniki zostaną najpierw anulowane (w szczególności, ponieważ wartości silni rosną bardzo szybko). Formuła wykazuje symetrię, która jest mniej oczywista ze wzoru multiplikatywnego (chociaż wynika z definicji)
-
( 1 )
co prowadzi do wydajniejszej multiplikatywnej rutyny obliczeniowej. Używając notacji z silnią opadającą ,
Uogólnienie i połączenie z szeregiem dwumianowym
Wzór multiplikatywny pozwala rozszerzyć definicję współczynników dwumianowych poprzez zastąpienie n dowolną liczbą α (ujemną, rzeczywistą, zespoloną) lub nawet elementem dowolnego pierścienia przemiennego, w którym wszystkie liczby całkowite dodatnie są odwracalne:
Przy tej definicji mamy do czynienia z uogólnieniem wzoru dwumianowego (z jedną ze zmiennych ustawioną na 1), co uzasadnia nadal nazywanie współczynników dwumianowych:
-
( 2 )
Ten wzór obowiązuje dla wszystkich liczb zespolonych α i X z | X | < 1. Może być również interpretowane jako identyczność formalnych szeregów potęgowych w X , gdzie faktycznie może służyć jako definicja dowolnych potęg szeregów potęgowych o stałym współczynniku równym 1; chodzi o to, że przy tej definicji wszystkie tożsamości utrzymują, że oczekuje się potęgowania , w szczególności
Jeśli α jest nieujemną liczbą całkowitą n , to wszystkie wyrazy o k > n wynoszą zero, a nieskończony szereg staje się sumą skończoną, odzyskując w ten sposób wzór dwumianowy. Jednak dla innych wartości α , w tym ujemnych liczb całkowitych i liczb wymiernych, szereg jest naprawdę nieskończony.
Trójkąt Pascala
Reguła Pascala jest ważną relacją powtarzalności
-
( 3 )
co można wykorzystać do udowodnienia przez indukcję matematyczną, że jest liczbą naturalną dla wszystkich liczb całkowitych n ≥ 0 i wszystkich liczb całkowitych k , fakt, który nie jest od razu oczywisty ze wzoru (1) . Po lewej i prawej stronie trójkąta Pascala wszystkie wpisy (pokazane jako puste miejsca) są zerowe.
Z reguły Pascala powstaje również trójkąt Pascala :
0: 1 1: 1 1 2: 1 2 1 3: 1 3 3 1 4: 1 4 6 4 1 5: 1 5 10 10 5 1 6: 1 6 15 20 15 6 1 7: 1 7 21 35 35 21 7 1 8: 1 8 28 56 70 56 28 8 1
Numer wiersza n zawiera liczby dla k = 0, ..., n . Jest konstruowany przez umieszczenie jedynek na skrajnych pozycjach, a następnie wypełnienie każdej wewnętrznej pozycji sumą dwóch liczb bezpośrednio powyżej. Ta metoda pozwala na szybkie obliczenie współczynników dwumianowych bez konieczności ułamków lub mnożenia. Na przykład, patrząc na wiersz numer 5 w trójkącie, można to szybko odczytać
Kombinatoryka i statystyka
Współczynniki dwumianowe mają znaczenie w kombinatoryce , ponieważ dostarczają gotowych wzorów na pewne częste problemy liczenia:
- Istnieją sposoby na wybranie k elementów ze zbioru n elementów. Zobacz Kombinacja .
- Istnieją sposoby na wybranie k elementów z zestawu n elementów, jeśli dozwolone są powtórzenia. Zobacz Multiset .
- Istnieją łańcuchy zawierające k jedynek i n zer.
- Istnieją ciągi składające się z k jedynek i n zer, tak że żadne dwie jedynek nie sąsiadują ze sobą.
- Te numery Kataloński są
- Rozkład dwumianowy w statystyce to
Współczynniki dwumianowe jako wielomiany
Dla dowolnej nieujemnej liczby całkowitej k wyrażenie można uprościć i zdefiniować jako wielomian dzielony przez k !:
to przedstawia wielomian w t ze współczynnikami wymiernymi .
W związku z tym można ją obliczyć przy dowolnej liczbie rzeczywistej lub zespolonej t, aby zdefiniować współczynniki dwumianowe z takimi pierwszymi argumentami. Te „uogólnione współczynniki dwumianowe” pojawiają się w uogólnionym twierdzeniu dwumianowym Newtona .
Dla każdego k , wielomian można scharakteryzować jako jedyny stopień k wielomianu p ( t ), które spełniają p (0) = s (1) = ⋯ = P ( K - 1) = 0 i P ( k ) = 1.
Jego współczynniki są wyrażalne w liczbach Stirlinga pierwszego rodzaju :
Pochodną od można obliczyć logarytmiczną różnicowania :
Może to powodować problem przy obliczaniu liczb całkowitych od do , ale korzystając z poniższych tożsamości, możemy obliczyć pochodną jako:
Współczynniki dwumianowe jako podstawa przestrzeni wielomianów
Na dowolnym polu o charakterystyce 0 (to znaczy dowolnym polu, które zawiera liczby wymierne ), każdy wielomian p ( t ) stopnia co najwyżej d można jednoznacznie wyrazić jako liniową kombinację współczynników dwumianowych. Współczynnik a k jest k- tą różnicą ciągu p (0), p (1), ..., p ( k ). Wyraźnie,
-
( 4 )
Wielomiany o wartościach całkowitych
Każdy wielomian ma wartość całkowitą : ma wartość całkowitą na wszystkich wejściach liczb całkowitych . (Jednym ze sposobów udowodnienia tego jest indukcja na k , używając identyczności Pascala .) Dlatego każda całkowita kombinacja liniowa wielomianów współczynników dwumianowych jest również wartością całkowitą. Odwrotnie, ( 4 ) pokazuje, że każdy wielomian o wartościach całkowitych jest całkowitą liniową kombinacją tych wielomianów współczynników dwumianowych. Bardziej ogólnie, dla dowolnego podpierścienia R charakterystycznego pola K , wielomian w K [ t ] przyjmuje wartości w R we wszystkich liczbach całkowitych wtedy i tylko wtedy, gdy jest R- liniową kombinacją wielomianów współczynników dwumianowych.
Przykład
Wielomian o wartościach całkowitych 3 t (3 t + 1)/2 można przepisać jako
Tożsamości obejmujące współczynniki dwumianowe
Formuła czynnikowa ułatwia powiązanie pobliskich współczynników dwumianowych. Na przykład, jeśli k jest liczbą całkowitą dodatnią, a n jest dowolne, wtedy
-
( 5 )
i przy odrobinie pracy,
Ponadto przydatne mogą być:
Dla stałej n mamy następującą powtarzalność:
Sumy współczynników dwumianowych
Formuła
-
( ** )
mówi, że elementy w n- tym rzędzie trójkąta Pascala zawsze sumują się do 2 podniesionych do n- tej potęgi. Uzyskuje się to z twierdzenia dwumianowego ( ∗ ) przez ustawienie x = 1 i y = 1. Wzór ma również naturalną interpretację kombinatoryczną: lewa strona sumuje liczbę podzbiorów {1, ..., n } rozmiarów k = 0, 1, ..., n , co daje całkowitą liczbę podzbiorów. (To znaczy, lewa strona zlicza zbiór potęg {1, ..., n }.) Jednak te podzbiory mogą być również generowane przez sukcesywne wybieranie lub wykluczanie każdego elementu 1, ..., n ; gdy n niezależnych wyborów binarnych (bit-strings) pozwalają łącznie wyborów. Lewa i prawa strona to dwa sposoby liczenia tego samego zbioru podzbiorów, więc są one równe.
Formuły
-
( 6 )
oraz
wynikają z twierdzenia dwumianowego po zróżnicowaniu względem x (dwukrotnie dla tego ostatniego), a następnie podstawieniu x = y = 1 .
Chu-Vandermonde tożsamości , co odnosi się do dowolny kompleks Wartości m i n i dowolna nieujemną liczbę całkowitą k jest
-
( 7 )
i można je znaleźć badając współczynnik rozwinięcia (1 + x ) m (1 + x ) n − m = (1 + x ) n przy użyciu równania ( 2 ). Gdy m = 1 , równanie ( 7 ) redukuje się do równania ( 3 ). W szczególnym przypadku n = 2 m , k = m , używając ( 1 ), rozwinięcie ( 7 ) staje się (jak widać w trójkącie Pascala po prawej)
-
( 8 )
gdzie wyraz po prawej stronie jest centralnym współczynnikiem dwumianowym .
Inną formą tożsamości Chu-Vandermonde, która dotyczy dowolnych liczb całkowitych j , k i n spełniających 0 ≤ j ≤ k ≤ n , jest
-
( 9 )
Dowód jest podobny, ale wykorzystuje rozwinięcie w szereg dwumianowy ( 2 ) z ujemnymi wykładnikami całkowitymi. Gdy j = k , równanie ( 9 ) daje tożsamość kija hokejowego
i jego krewny
Niech K ( n ) oznaczają n -tej liczby Fibonacciego . Następnie
Można to udowodnić przez indukcję za pomocą ( 3 ) lub przez reprezentację Zeckendorfa . Poniżej przedstawiono dowód kombinatoryczny.
Wielosekcje sum
Dla liczb całkowitych s i t takich, że szereg wielosekcja daje następującą tożsamość dla sumy współczynników dwumianowych:
Dla małych s te serie mają szczególnie ładne formy; na przykład,
Sumy częściowe
Chociaż nie ma zamkniętej formuły na sumy częściowe
współczynników dwumianowych można ponownie użyć ( 3 ) i indukcji, aby pokazać, że dla k = 0, ..., n − 1 ,
ze specjalnym przypadkiem
dla n > 0. Ten ostatni wynik jest również szczególnym przypadkiem wyniku z teorii różnic skończonych, że dla dowolnego wielomianu P ( x ) stopnia mniejszego niż n ,
Różniczkowanie ( 2 ) k razy i ustawienie x = −1 daje to dla , gdy 0 ≤ k < n , a ogólny przypadek następuje poprzez wzięcie ich liniowych kombinacji.
Gdy P ( x ) jest stopnia mniejszego lub równego n ,
-
( 10 )
gdzie jest współczynnikiem stopnia n w P ( x ).
Bardziej ogólnie dla ( 10 ),
gdzie m i d są liczbami zespolonymi. Wynika to natychmiastowe zastosowanie ( 10 ) do wielomianu zamiast Widać, że wciąż ma poziom mniejszy niż lub równą n , a jego współczynnik stopnia n jest d n n .
Seria jest zbieżny dla k ≥ 2. Wzór ten jest stosowany w analizie problemu niemieckiego zbiornika . Z czego wynika indukcja na M .
Tożsamości z dowodami kombinatorycznymi
Wiele tożsamości obejmujących współczynniki dwumianowe można udowodnić za pomocą środków kombinatorycznych . Na przykład dla nieujemnych liczb całkowitych tożsamość
(co redukuje się do ( 6 ) gdy q = 1) może otrzymać dowód podwójnego liczenia , jak następuje. Lewa strona zlicza liczbę sposobów wybrania podzbioru [ n ] = {1, 2, ..., n } z co najmniej q elementami i zaznaczenia q elementów spośród wybranych. Prawa strona liczy się tak samo, ponieważ istnieją sposoby wyboru zbioru q elementów do oznaczenia, a także wyboru, które z pozostałych elementów [ n ] również należą do podzbioru.
W tożsamości Pascala
obie strony liczą liczbę k- elementowych podzbiorów [ n ]: dwa terminy po prawej stronie grupują je w te, które zawierają element n i te, które go nie zawierają.
Tożsamość ( 8 ) ma również dowód kombinatoryczny. Tożsamość czyta
Załóżmy, że masz puste kwadraty ułożone w rzędzie i chcesz zaznaczyć (wybrać) n z nich. Są na to sposoby. Z drugiej strony, możesz wybrać swoje n kwadratów, wybierając k kwadratów spośród pierwszych n i kwadratów z pozostałych n kwadratów; każde k od 0 do n będzie działać. To daje
Teraz zastosuj ( 1 ), aby uzyskać wynik.
Jeżeli oznaczymy przez F ( i ) ciąg liczb Fibonacciego , indeksowanych tak, że F (0) = F (1) = 1 , to identyczność
Suma współczynników wiersz
Liczba k - kombinacji dla wszystkich k , , jest sumą
n- tego wiersza (licząc od 0) współczynników dwumianowych. Kombinacje te są wyliczane przez 1 cyfrę zestawu liczb o podstawie 2 licząc od 0 do , gdzie każda pozycja cyfry jest elementem ze zbioru n .Tożsamość Dixona
lub, bardziej ogólnie,
gdzie a , b i c są nieujemnymi liczbami całkowitymi.
Tożsamości ciągłe
Niektóre całki trygonometryczne mają wartości wyrażalne za pomocą współczynników dwumianowych: For any
Można to udowodnić za pomocą wzoru Eulera do konwersji funkcji trygonometrycznych na złożone wykładniki, rozszerzając za pomocą twierdzenia dwumianowego i całkując wyraz po wyrazie.
Kongruencje
Jeśli n jest liczbą pierwszą, to
dla każdego k z Bardziej ogólnie, pozostaje to prawdą, jeśli
n jest dowolną liczbą, a k jest takie, że wszystkie liczby między 1 a k są względnie pierwsze od n .Rzeczywiście, mamy
Generowanie funkcji
Zwykłe funkcje generujące
Do stałej n The zwykłą funkcję generowania sekwencji jest
Dla ustalonego k zwykłą funkcją tworzącą ciągu jest
Funkcja generowania dwuwymiarowych z dwumianowego współczynników jest
Symetryczna dwuwymiarowa funkcja generująca współczynników dwumianowych to
który jest taki sam jak poprzednia funkcja generująca po podstawieniu .
Funkcja generowania wykładniczego
Symetryczna wykładnicza dwuwymiarowa funkcja generująca współczynniki dwumianowe to:
Własności podzielności
W 1852 Kummer okazało się, że jeżeli m i n są liczbami całkowitymi nieujemnymi i p jest liczbą pierwszą, wtedy największą moc p rozdzielenia równe
p c , gdzie c jest liczbą przenosi gdy m i n są dodawane w bazie p . Równoważnie, wykładnik doskonałej p w jest równa liczbie nieujemnej liczb całkowitych j takie, że ułamkowe części od k / p j jest większa niż część ułamkową n / p j . Można wywnioskować z tego, że jest podzielne przez n / gcd ( n , k ). W szczególności z tego wynika, że p dzieli się na wszystkie dodatnie liczby całkowite r i s takie, że s < p r . Nie dotyczy to jednak wyższych potęg p : na przykład 9 nie dzieli .Nieco zaskakującym wynikiem Davida Singmastera (1974) jest to, że każda liczba całkowita dzieli prawie wszystkie współczynniki dwumianowe. Dokładniej, ustal liczbę całkowitą d i niech f ( N ) oznacza liczbę współczynników dwumianowych z
n < N tak, że d dzieli . NastępniePonieważ liczba współczynników dwumianowych z
n < N wynosi N ( N + 1) / 2, oznacza to, że gęstość współczynników dwumianowych podzielnych przez d wynosi 1.Współczynniki dwumianowe mają właściwości podzielności związane z najmniejszymi wspólnymi wielokrotnościami kolejnych liczb całkowitych. Na przykład:
dzieli .
jest wielokrotnością .
Inny fakt: liczba całkowita n ≥ 2 jest liczbą pierwszą wtedy i tylko wtedy, gdy wszystkie pośrednie współczynniki dwumianowe
są podzielne przez n .
Dowód: Gdy p jest liczbą pierwszą, p dzieli
- dla wszystkich 0 < k < p
ponieważ jest liczbą naturalną, a
p dzieli licznik, ale nie mianownik. Gdy n jest złożone, niech p będzie najmniejszym czynnikiem pierwszym n i niech k = n/p . Wtedy 0 < p < n iw przeciwnym razie licznik k ( n − 1)( n − 2)×...×( n − p + 1) musi być podzielny przez n = k × p , może to mieć miejsce tylko wtedy, gdy ( n − 1)( n − 2)×...×( n − p + 1) jest podzielne przez p . Ale n jest podzielne przez p , więc p nie dzieli n − 1, n − 2, ..., n − p + 1, a ponieważ p jest liczbą pierwszą, wiemy, że p nie dzieli ( n − 1)( n − 2)×...×( n − p + 1), a więc licznik nie może być podzielny przez n .
Granice i wzory asymptotyczne
Następujące granice utrzymania dla wszystkich wartości
n i k takich, że 1 ≤ k ≤ n :- .
Pierwsza nierówność wynika z tego, że
a każdy z tych terminów w tym produkcie to . Podobny argument można wysnuć, aby pokazać drugą nierówność. Ostateczna ścisła nierówność jest równoważna , co jest jasne , ponieważ RHS jest wyrazem szeregu wykładniczego .
Z własności podzielności możemy wywnioskować, że
- ,
gdzie można osiągnąć obie równouprawnienia.
W teorii informacji przydatne są następujące ograniczenia:
gdzie jest
funkcją entropii binarnej . Można go dodatkowo dokręcić doZarówno n, jak i k duże
Aproksymacja Stirlinga daje następujące przybliżenie, ważne, gdy oba mają tendencję do nieskończoności:
Ponieważ formy nierówności wzoru Stirlinga również ograniczają silnie, niewielkie warianty powyższego przybliżenia asymptotycznego dają dokładne granice. W szczególności, gdy jest wystarczająco duży, trzeba
- oraz
a ogólniej dla m ≥ 2 i n ≥ 1,
Jeśli n jest duże, a k jest liniowe w n , istnieją różne dokładne asymptotyczne oszacowania współczynnika dwumianowego . Na przykład, jeśli wtedy
gdzie d = n − 2 k .
n znacznie większe niż k
Jeśli n jest duże, a k to o ( n ) (to znaczy, jeśli
k / n → 0 ), toSumy współczynników dwumianowych
Prostą i przybliżoną górną granicę sumy współczynników dwumianowych można otrzymać za pomocą twierdzenia dwumianowego :
Bardziej precyzyjne granice są podane przez
ważne dla wszystkich liczb całkowitych z .
Uogólnione współczynniki dwumianowe
Nieskończony składu produktu w funkcji gamma daje także ekspresję współczynników dwumiennych
co daje asymptotyczne formuły
jak .
To asymptotyczne zachowanie jest zawarte w przybliżeniu
także. (Tutaj jest w
k -tym liczba harmonicznych i jest stała Eulera-Mascheroni ).Dalej, asymptotyczna formuła
prawda, zawsze i dla jakiejś liczby zespolonej .
Uogólnienia
Uogólnienie na wielomiany
Współczynniki dwumianowe można uogólnić na współczynniki wielomianowe zdefiniowane jako liczba:
gdzie
Podczas gdy współczynniki dwumianowe reprezentują współczynniki ( x + y ) n , współczynniki wielomianowe reprezentują współczynniki wielomianu
Przypadek r = 2 daje współczynniki dwumianowe:
Kombinatorycznych interpretacja współczynników wielomianowych jest podział n elementów wyróżniających się r (wyczuwalne) pojemników, z których każdy zawiera dokładnie k I elementy, gdzie i jest indeksem pojemnika.
Współczynniki wielomianowe mają wiele właściwości podobnych do współczynników dwumianowych, na przykład relacja powtarzalności:
i symetria:
gdzie jest
permutacją (1, 2, ..., r ).Seria Taylora
Korzystanie Stirling ilości pierwszego rodzaju po ekspansji serii około dowolnie wybranego punktu jest
Współczynnik dwumianowy z n = 1/2
Definicję współczynników dwumianowych można rozszerzyć do przypadku, gdy jest rzeczywisty i jest liczbą całkowitą.
W szczególności dla każdej nieujemnej liczby całkowitej obowiązuje następująca tożsamość :
Pojawia się to po rozwinięciu do szeregu potęgowego przy użyciu szeregu dwumianowego Newtona:
Iloczyny współczynników dwumianowych
Iloczyn dwóch współczynników dwumianowych można wyrazić jako liniową kombinację współczynników dwumianowych:
gdzie współczynniki połączenia są współczynnikami wielomianowymi . Jeśli chodzi o oznakowane obiekty kombinatoryczne, współczynniki połączenia reprezentują liczbę sposobów przypisania m + n − k etykiet do pary oznakowanych obiektów kombinatorycznych – o wadze odpowiednio m i n – które mają pierwsze k etykiet zidentyfikowanych lub sklejonych ze sobą aby otrzymać nowy oznaczony kombinatoryczny obiekt o wadze m + n − k . (Oznacza to, że do rozdzielenia etykiet na trzy części, aby zastosować się do klejonej części, w Unglued części pierwszego obiektu, a Unglued części drugiego obiektu). W związku z tym, Symbol Newtona mają wykładniczej serii generujących jakie spadające silni są do zwykłych szeregów generujących.
Iloczyn wszystkich współczynników dwumianowych w n- tym wierszu trójkąta Pascala wyraża wzór:
Rozkład częściowy frakcji
Częściowy rozkład frakcji wzajemnej jest przez
Szeregi dwumianowe Newtona
Szereg dwumianowy Newtona, nazwany na cześć Sir Isaaca Newtona , jest uogólnieniem twierdzenia dwumianowego na szereg nieskończony:
Tożsamość można uzyskać pokazując, że obie strony spełniają równanie różniczkowe (1 + z ) f' ( z ) = α f ( z ).
Promień zbieżności tej serii wynosi 1. Alternatywna ekspresja jest
gdzie tożsamość?
jest stosowany.
Multiset (rosnący) współczynnik dwumianowy
Współczynniki dwumianowe zliczają podzbiory o określonej wielkości z danego zbioru. Pokrewnym problemem kombinatorycznym jest liczenie multisetów o zadanej wielkości z elementami wylosowanymi z danego zbioru, czyli liczenie ilości sposobów wybrania określonej liczby elementów z danego zbioru z możliwością wielokrotnego wybierania tego samego elementu. Otrzymane liczby nazywane są współczynnikami wielozbiorowymi ; liczba sposobów na "wielokrotny wybór" (tj. wybór z zamianą) k elementów z n zestawu elementów jest oznaczona .
Aby uniknąć niejasności i pomyłek z główną denotacją n w tym artykule,
niech f = n = r + ( k – 1) i r = f – ( k – 1).
Współczynniki wielozbiorowe mogą być wyrażone w postaci współczynników dwumianowych według reguły
Jedna z możliwych alternatywnych charakterystyk tej tożsamości jest następująca: Możemy zdefiniować silnię opadającą jako
- ,
i odpowiednia silnia narastająca as
- ;
więc na przykład
- .
Wtedy współczynniki dwumianowe można zapisać jako
- ,
podczas gdy odpowiedni współczynnik wielozbiorowości jest definiowany przez zastąpienie opadania silnią narastającą:
- .
Uogólnienie na liczby całkowite ujemne n
Dla każdego n ,
W szczególności, współczynniki dwumianowe oszacowane na ujemnych liczbach całkowitych n są podane przez wielozestawowe współczynniki ze znakiem. W szczególnym przypadku zmniejsza się to do
Na przykład, jeśli n = -4 i k = 7, to r = 4 i f = 10:
Dwa prawdziwe lub złożone wartościowane argumenty
Współczynnik dwumianowy jest uogólniany na dwa rzeczywiste lub złożone argumenty o wartościach za pomocą funkcji gamma lub funkcji beta poprzez
Ta definicja dziedziczy następujące dodatkowe właściwości z :
Ponadto,
Wynikowa funkcja była mało zbadana, podobno jako pierwsza została wykreślona w ( Fowler 1996 ). Warto zauważyć, że wiele tożsamości dwumianowych zawodzi: ale dla
n dodatnich (tak ujemnych). Zachowanie jest dość złożone i wyraźnie różne w różnych oktantach (to znaczy w odniesieniu do osi x i y oraz linii ), przy czym zachowanie dla ujemnego x ma osobliwości przy ujemnych wartościach całkowitych i szachownicę obszarów dodatnich i ujemnych:- w oktancie jest to gładko interpolowana forma zwykłego dwumianu z grzbietem („grzbiet Pascala”).
- w oktancie i kwadrancie funkcja jest bliska zeru.
- w kwadrancie funkcja jest na przemian bardzo duża dodatnia i ujemna na równoległobokach z wierzchołkami
- w oktancie zachowanie jest znowu na przemian bardzo duże dodatnie i ujemne, ale na siatce kwadratowej.
- w oktancie jest bliski zeru, z wyjątkiem bliskich osobliwości.
Uogólnienie do q -series
Współczynnik dwumianowy ma uogólnienie q-analogowe znane jako współczynnik dwumianowy Gaussa .
Uogólnienie na nieskończonych kardynałów
Definicję współczynnika dwumianowego można uogólnić na nieskończone kardynały , definiując:
gdzie A jest pewnym zbiorem z kardynalnością . Można pokazać, że uogólniony współczynnik dwumianowy jest dobrze zdefiniowany, w tym sensie, że bez względu na to, jaki zestaw wybierzemy do reprezentowania liczby kardynalnej , pozostanie taki sam. W przypadku skończonych kardynałów definicja ta pokrywa się ze standardową definicją współczynnika dwumianowego.
Zakładając Aksjomat Wyboru , można to wykazać dla każdego nieskończonego kardynała .
W językach programowania
Notacja jest wygodna w charakterystyce pisma ręcznego, ale niewygodna dla
maszyn do pisania i terminali komputerowych . Wiele języków programowania nie oferuje standardowego podprogramu do obliczania współczynnika dwumianowego, ale na przykład zarówno język programowania APL, jak i (powiązany) język programowania J używają wykrzyknika: . Współczynnik dwumianowy jest zaimplementowany w SciPy jako scipy.special.comb .k ! n
Naiwne implementacje formuły czynnikowej, takie jak następujący fragment kodu w Pythonie :
from math import factorial
def binomial_coefficient(n: int, k: int) -> int:
return factorial(n) // (factorial(k) * factorial(n - k))
są bardzo powolne i bezużyteczne do obliczania silni o bardzo dużych liczbach (w językach takich jak C lub Java z tego powodu występują błędy przepełnienia). Bezpośrednia implementacja formuły multiplikatywnej działa dobrze:
def binomial_coefficient(n: int, k: int) -> int:
if k < 0 or k > n:
return 0
if k == 0 or k == n:
return 1
k = min(k, n - k) # Take advantage of symmetry
c = 1
for i in range(k):
c = c * (n - i) / (i + 1)
return c
(W Pythonie range(k) tworzy listę od 0 do k–1.)
Reguła Pascala dostarcza rekurencyjną definicję, którą można również zaimplementować w Pythonie, chociaż jest mniej wydajna:
def binomial_coefficient(n: int, k: int) -> int:
if k < 0 or k > n:
return 0
if k > n - k: # Take advantage of symmetry
k = n - k
if k == 0 or n <= 1:
return 1
return binomial_coefficient(n - 1, k) + binomial_coefficient(n - 1, k - 1)
Wspomniany powyżej przykład można również napisać w stylu funkcjonalnym. Poniższy przykład schematu używa definicji rekurencyjnej
Wymierną arytmetykę można łatwo uniknąć, używając dzielenia liczb całkowitych
Poniższa implementacja wykorzystuje wszystkie te pomysły
(define (binomial n k)
;; Helper function to compute C(n,k) via forward recursion
(define (binomial-iter n k i prev)
(if (>= i k)
prev
(binomial-iter n k (+ i 1) (/ (* (- n i) prev) (+ i 1)))))
;; Use symmetry property C(n,k)=C(n, n-k)
(if (< k (- n k))
(binomial-iter n k 0 1)
(binomial-iter n (- n k) 0 1)))
Podczas obliczania w języku z liczbami całkowitymi o stałej długości mnożenie przez może się przepełnić, nawet jeśli wynik będzie pasował. Przepełnienia można uniknąć, dzieląc najpierw i ustalając wynik za pomocą reszty:
Implementacja w języku C:
#include <limits.h>
unsigned long binomial(unsigned long n, unsigned long k) {
unsigned long c = 1, i;
if (k > n-k) // take advantage of symmetry
k = n-k;
for (i = 1; i <= k; i++, n--) {
if (c/i >= ULONG_MAX/n) // return 0 on potential overflow
return 0;
c = c / i * n + c % i * n / i; // split c * n / i into (c / i * i + c % i) * n / i
}
return c;
}
Innym sposobem obliczenia współczynnika dwumianowego przy użyciu dużych liczb jest rozpoznanie, że
gdzie oznacza
logarytm naturalny w funkcję gamma w . Jest to specjalna funkcja, która jest łatwa do obliczenia i jest standardem w niektórych językach programowania, takich jak log_gamma w Maxima , LogGamma w Mathematica , gammaln w MATLAB i moduł SciPy Pythona , lngamma w PARI/GP lub lgamma w C, R i Julia . Błąd zaokrąglenia może spowodować, że zwracana wartość nie będzie liczbą całkowitą.Zobacz też
- Przekształcenie dwumianowe
- Numer Delannoya
- Liczba Eulera
- Funkcja hipergeometryczna
- Lista tematów czynnikowych i dwumianowych
- Macaulay reprezentacja liczby całkowitej
- Numer Motzkina
- Wielokrotności wpisów w trójkącie Pascala
- Liczba Narayana
- Twierdzenie o gwiazdach Dawida
- Ciekawa tożsamość Sun
- Tabela serii Newtona
- Rozszerzenie trójmianowe
Uwagi
Bibliografia
- Ash, Robert B. (1990) (1965). Teoria informacji . Dover Publications, Inc. ISBN 0-486-66521-6.
- Benjamin, Artur T .; Quinn, Jennifer J. (2003). Dowody, które naprawdę się liczą: sztuka dowodu kombinatorycznego . Ekspozycje matematyczne Dolciani. 27 . Amerykańskie Stowarzyszenie Matematyczne . Numer ISBN 978-0-88385-333-7.
- Bryant, Victor (1993). Aspekty kombinatoryki . Wydawnictwo Uniwersytetu Cambridge. Numer ISBN 0-521-41974-3.
- Flum, Jörg; Grohe, Marcina (2006). Sparametryzowana teoria złożoności . Skoczek. Numer ISBN 978-3-540-29952-3.
- Fowler, David (styczeń 1996). „Funkcja współczynnika dwumianowego”. Amerykański miesięcznik matematyczny . Amerykańskie Stowarzyszenie Matematyczne. 103 (1): 1-17. doi : 10.2307/2975209 . JSTOR 2975209 .
- Goetgheluck, P. (1987). „Obliczanie współczynników dwumianowych”. Amerykański miesięcznik matematyczny . 94 (4): 360-365. doi : 10.2307/2323099 . JSTOR 2323099 .
- Graham, Ronald L .; Knuth, Donald E .; Patasznik, Oren (1994). Matematyka konkretna (druga ed.). Addisona-Wesleya. s. 153 -256. Numer ISBN 0-201-55802-5.
- Gradsztejn, IS; Ryżik, IM (2014). Tabela całek, serii i produktów (wyd. 8). Prasa akademicka. Numer ISBN 978-0-12-384933-5.
- Grinshpan, AZ (2010), „Ważone nierówności i ujemne dwumiany”, Advances in Applied Mathematics , 45 (4): 564-606, doi : 10.1016/j.aam.2010.04.004
- Higham, Mikołaj J. (1998). Podręcznik pisania dla nauk matematycznych . SIAM . P. 25 . Numer ISBN 0-89871-420-6.
- Knut, Donald E. (1997). Sztuka programowania komputerowego, tom 1: Podstawowe algorytmy(Wyd. trzecie). Addisona-Wesleya. s. 52–74. Numer ISBN 0-201-89683-4.
- Mistrz śpiewu, Dawid (1974). „Uwagi dotyczące współczynników dwumianowych. III. Każda liczba całkowita dzieli prawie wszystkie współczynniki dwumianowe”. Dziennik Londyńskiego Towarzystwa Matematycznego . 8 (3): 555–560. doi : 10.1112/jlms/s2-8.3.555 .
- Szyłow, GE (1977). Algebra liniowa . Publikacje Dovera. Numer ISBN 978-0-486-63518-7.
Zewnętrzne linki
- „Współczynniki dwumianowe” , Encyklopedia Matematyki , EMS Press , 2001 [1994]
- Andrzeja Granville'a (1997). „Właściwości arytmetyczne współczynników dwumianowych I. Współczynniki dwumianowe modulo potęgi pierwsze” . Konf. CMS Proc . 20 : 151–162. Zarchiwizowane od oryginału dnia 2015-09-23 . Pobrano 2013-09-03 .
Ten artykuł zawiera materiał z następujących PlanetMath artykułów, które na podstawie licencji Creative Commons Attribution / Share-Alike License : Symbol Newtona , kresy dolny i górny do Symbol Newtona , współczynnik dwumianowy jest liczbą całkowitą , Uogólnione Symbol Newtona .