Współczynnik dwumianowy: definicje, implementacja i użycie

Wstęp

W statystyce współczynniki dwumianowe są głównie używane wraz z rozkładami. Ale jest ich więcej, gdy zastosujemy je do algorytmów obliczeniowych. Są szeroko stosowane w dziedzinie statystycznego uczenia maszynowego oraz programowania dynamicznego. Najbardziej podstawowe pojęcie o współczynnikach dwumianowych pochodzi z rozkładu dwumianowego. Współczynniki są używane w twierdzeniu dwumianowym, stąd nazwa.

Przede wszystkim współczynniki dwumianowe mają dwie definicje. Są to:

1. Współczynniki dwumianowe do znajdowania kombinacji

Współczynniki dwumianowe służą do znalezienia liczby sposobów wybrania określonej liczby obiektów z dostarczonej puli obiektów. Statystycznie współczynnik dwumianowy może pomóc w określeniu liczby sposobów wyboru y obiektów z łącznej liczby x obiektów. Liczba y podzbiorów elementów od x.

Formuła jest wyprowadzana jako:

W celu wybrania podzbiorów elementów y z obiektów x, możliwe są współczynniki dwumianowe lub kombinacje xCy = x! / y! * (xy)!

Ta metoda może być niezwykle przydatna, gdy trzeba obliczyć liczbę możliwych kombinacji z dużej puli obiektów. Ale gdzie to ma zastosowanie?

Przykład

Wyobraź sobie, że jest klasa z 15 uczniami. Jeśli chcesz wybrać do konkursu zespół składający się z 7 uczniów, musisz wymyślić możliwe kombinacje. Korzystając ze wzoru na współczynniki dwumianowe , odpowiedź można było łatwo obliczyć.

Suma kombinacji = 15! / 7! * (15-7)! = 15! / 7! * 8!

Wiele innych przypadków jest znacznie bardziej skomplikowanych, w których stosuje się współczynniki dwumianowe . Na przykład wybór partii politycznej w wyborach, a dokładniej syndykatu. Wyobraź sobie, że trzeba uchwalić ustawę, a ty jesteś batem większości dla partii rządzącej. Musisz zdecydować, które głosy są dostępne i ilu członków będzie potrzebnych do głosowania za ustawą. Członkowie muszą pochodzić zarówno z rządzących, jak iz partii opozycyjnej. Kombinatoryka może być zastosowana w celu znalezienia członków, od których ma zostać oddany głos.

Przeczytaj o: 13 ciekawych pomysłów na projekt struktury danych i tematów dla początkujących

2. Współczynniki dwumianowe dla rozkładu

Ta definicja jest bardziej formalna i statystyczna. Oznacza to znalezienie współczynników rozwinięcia wielomianu. Mówiąc prościej, dwumianowy współczynnik C(a, b) można zdefiniować jako współczynnik x^b w postaci rozłożonej (x+1)^a.

Zrozummy to na przykładzie.

Przykład

Na przykład potrzebujesz rozwinięcia wielomianu (x+1)^2. Jeśli porównamy to z naszą definicją, otrzymamy a=2 i b=0,1,2.

Dzięki ręcznym obliczeniom wiemy, że rozwinięcie (x+1)^2 = x^2 + 2x + 1. Ale jak obliczane są te współczynniki?

Zastosujmy wzór:

Współczynnik x^0 = C(2,0)

Współczynnik x^1 = C(2,1)

Współczynnik x^2 = C(2,2)

Stąd rozwinięcie można zapisać jako: C(2,0)x^0 + C(2,1)x^1 + C(2,2)x^2

Formuła pozostaje taka sama. C(a,b) = a! / b! *(ab)!

Stosując tę ​​samą formułę tutaj, C(2,0) = 2! / 0! * (2-0)! = 1

C(2,1) = 2! / 1! * (2-1)! = 2

C(2,2) = 2! / 2! * (2-2)! = 1

Teraz, jeśli podstawimy te wartości w rozwinięciu, otrzymamy x^2 + 2x + 1.

To jest dokładna odpowiedź, której potrzebowaliśmy. Ponieważ było to mniejsze rozszerzenie, możesz poczuć, że prosty sposób mnożenia jest lepszy. Ale co, jeśli musisz obliczyć rozwiniętą formę (x+1)^17?

Nie ma mnożenia tak wiele razy, a to będzie męcząca praca. Ale dzięki koncepcji współczynników dwumianowych zadanie staje się proste.

Przeczytaj: Koncepcja funkcji rekurencyjnych Pythona: Samouczek Pythona dla początkujących

Implementacja Pythona

Przed zastosowaniem wzoru na znalezienie współczynników dwumianowych należy zwrócić uwagę na kilka punktów. Do realizacji funkcji potrzebne są dwie części. Jedna to podstruktura, a druga to funkcja powtarzania podstruktur.

Aby rekurencyjnie znaleźć wartość C(a, b), możemy użyć następującej podstruktury:

C(a, 0) i C(a, a) = 1

C(a, b) = C(a-1, b) + C(a-1, b-1)

Korzystając z tych dwóch formuł, można zaimplementować funkcję rekurencyjną. Zwróć uwagę, że przy wyższym stopniu ekspansji wiele podkonstrukcji będzie się powtarzać. Może to wydłużyć czas obliczeń, jeśli obliczenia są powtarzane niepotrzebnie. Dlatego dla efektywnej implementacji ważne jest utrzymywanie słownika ze wszystkimi poprzednimi obliczeniami.

Ten typ implementacji ma złożoność czasową O(a*b). Złożoność przestrzeni różni się w zależności od implementacji, ale może być ograniczona do O(b).

Jeśli używasz Pythona i nie chcesz samodzielnie implementować funkcji, możesz użyć biblioteki Pythona SciPy. Specjalny moduł w SciPy posiada funkcję binom(). Oto jak można go używać:

Po prostu wpisz scipy.special.binom(a, b) i poda wartość tego samego. Na przykład scipy.special.binom(4,3); da wynik – 4,0

Stosowanie

Podstawowe zastosowania współczynników dwumianowych zostały już omówione powyżej. Do analizy wykorzystywane są współczynniki dwumianowe oraz podstawa rozkładu dwumianowego. Mniej znanym zastosowaniem jest to, że współczynniki dwumianowe reprezentują wpisy w trójkącie Pascala. Tego rodzaju przyczyny statystyczne sprawiają, że konieczne jest zrozumienie współczynników dwumianowych .

Także kasa: Rozkład dwumianowy w Pythonie z przykładami ze świata rzeczywistego

Wniosek

Tak więc chodziło o współczynniki dwumianowe ze statystycznego i wdrożeniowego punktu widzenia. Omówiliśmy dwie definicje współczynników dwumianowych , dla kombinacji i do obliczania współczynników rozszerzalności. Omówiono strategię wdrożenia, a także wdrożenie biblioteki.

Istnieje wiele innych zastosowań statystycznych dla współczynników dwumianowych , zwłaszcza gdy są one widoczne z rozkładami. Dlatego ważne jest, aby poznać współczynniki dwumianowe przed przejściem do zaawansowanych koncepcji opartych na statystykach, takich jak podstawowe algorytmy uczenia maszynowego i analizy.

Jeśli chcesz dowiedzieć się więcej o uczeniu maszynowym, sprawdź dyplom PG IIIT-B i upGrad w uczeniu maszynowym i sztucznej inteligencji, który jest przeznaczony dla pracujących profesjonalistów i oferuje ponad 450 godzin rygorystycznego szkolenia, ponad 30 studiów przypadków i zadań, IIIT- Status absolwenta B, ponad 5 praktycznych, praktycznych projektów zwieńczenia i pomoc w pracy z najlepszymi firmami.