Dwumian Newtona i modulo - współczynnik dwumianowy C(n,k) i reszta z dzielenia

Symbol Newtona C(49,6) daje dokładnie 13 983 816. Tyle jest sposobów na wybranie 6 liczb z 49. Szansa na szóstkę w Lotto to zatem 1 do prawie 14 milionów. Większość osób słyszy tę liczbę, kiwa głową i wraca do kupowania kuponów. Mało kto sprawdza, skąd ta liczba się bierze.

Z kolei reszta z dzielenia 17 przez 5 to 2. Bo 5 mieści się w 17 trzy razy (5 x 3 = 15), a zostaje 2. Operacja modulo - prosta jak odejmowanie. I równie użyteczna.

Te dwa narzędzia - dwumian Newtona i modulo - wydają się odległe od siebie. Jedno liczy kombinacje, drugie reszty z dzielenia. Ale oba pojawiają się na maturze z matematyki rozszerzonej i w informatyce. Oba mają wzory, które da się policzyć ręcznie przy małych liczbach i potrzebują kalkulatora przy większych.

8:00 - zadanie na rozgrzewkę: ile kombinacji?

Zacznijmy od konkretnego problemu. Komisja egzaminacyjna wybiera 3 pytania z puli 10. Kolejność nie ma znaczenia - liczy się zestaw. Ile jest takich zestawów?

Wzór na symbol Newtona: C(n,k) = n! / (k! x (n-k)!)

Dla C(10,3): 10! / (3! x 7!) = (10 x 9 x 8) / (3 x 2 x 1) = 120

120 zestawów. Brzmi dużo, ale to dopiero 10 po 3. Przy C(20,5) wynik skacze do 15 504. Przy C(49,6) - do tych 13,98 miliona.

Widać prawidłowość: im bliżej k jest do n/2, tym wynik wyższy. C(10,5) = 252, podczas gdy C(10,1) = 10 i C(10,9) = 10. Dwumian jest symetryczny - C(n,k) = C(n,n-k).

9:30 - rozwinięcie (a+b)^n na tablicy

Ale symbol Newtona to tylko połowa dwumianu. Druga połowa to rozwinięcie potęgi sumy. Wpisz do kalkulatora (2+3)^5 i dostaniesz tabelę:

(2+3)^5 = 32 + 240 + 720 + 1080 + 810 + 243 = 3125

Każdy wyraz to C(5,k) x 2^(5-k) x 3^k. Zerowy wyraz: C(5,0) x 32 x 1 = 32. Pierwszy: C(5,1) x 16 x 3 = 240. I tak dalej. Suma musi dawać (2+3)^5 = 5^5 = 3125. To szybki sposób na weryfikację - jeśli suma wyrazów nie zgadza się z (a+b)^n, gdzieś jest błąd.

Na maturze rozszerzonej typowe zadanie brzmi: "Podaj współczynnik przy x^3 w rozwinięciu (2x+1)^7". Odpowiedź: C(7,4) x (2x)^3 x 1^4 = 35 x 8x^3 = 280x^3. Współczynnik to 280.

10:15 - trójkąt Pascala i wzorce

Trzeci tryb kalkulatora pokazuje trójkąt Pascala - tabelę współczynników dwumianowych ułożonych w trójkąt. Wiersz zerowy: 1. Wiersz pierwszy: 1, 1. Wiersz piąty: 1, 5, 10, 10, 5, 1.

Suma każdego wiersza to potęga dwójki: 2^n. Wiersz piąty sumuje się do 32, szósty do 64. Każdy element wewnętrzny to suma dwóch elementów z wiersza wyżej - stąd konstrukcja trójkąta. C(5,2) = C(4,1) + C(4,2) = 4 + 6 = 10. Proste, a działa dla dowolnego n.

11:00 - zmiana tematu: reszta z dzielenia

Operacja modulo to coś zupełnie innego niż dwumian, ale nie mniej przydatnego. 17 mod 5 - ile zostaje po podzieleniu 17 przez 5? Pięć mieści się w 17 trzy razy. 3 x 5 = 15. Zostaje 2.

Wzór: a = b x q + r, gdzie q to iloraz (quotient), a r to reszta (remainder). Dla 17 mod 5: 17 = 5 x 3 + 2. Reszta jest zawsze z przedziału od 0 do b-1. Dla dzielnika 5 reszta może wynosić 0, 1, 2, 3 lub 4 - i nic innego.

Gdzie to się przydaje poza klasówką? W programowaniu - codziennie. Sprawdzanie parzystości: n mod 2 = 0 oznacza liczbę parzystą. Cykliczne indeksy: element tablicy na pozycji i mod n. Walidacja numerów: PESEL, NIP, IBAN - wszystkie używają modulo do sprawdzania cyfry kontrolnej.

12:30 - tabela reszt i wzorce podzielności

Kalkulator w trybie "tabela reszt" generuje reszty z dzielenia dla całego zakresu. Dla dzielnika 7 i zakresu 1-21:

Wzorzec jest cykliczny. Reszty powtarzają się co 7 liczb: 1, 2, 3, 4, 5, 6, 0, 1, 2, 3... Wielokrotności 7 (7, 14, 21) mają resztę 0. To jest sedno podzielności - liczba jest podzielna przez b wtedy i tylko wtedy, gdy a mod b = 0.

13:45 - gdzie te dwa tematy się spotykają

Na pierwszy rzut oka dwumian Newtona i modulo nie mają ze sobą nic wspólnego. Ale w praktyce łączą się częściej niż można by się spodziewać.

Twierdzenie Lucasa mówi, że C(m,n) mod p (dla p pierwszego) zależy od cyfr m i n w systemie o podstawie p. To jest właśnie połączenie kombinatoryki z arytmetyką modularną. Na konkursach matematycznych i w kryptografii taki zestaw narzędzi jest standardem.

Ale nawet bez zaawansowanej teorii - na co dzień oba narzędzia rozwiązują problemy różnego typu. Dwumian odpowiada na pytanie "ile jest sposobów?". Modulo odpowiada na pytanie "co zostaje?". Kiedy potrzebujesz jednego, a kiedy drugiego?

15:00 - co by było gdyby: bez kalkulatora

Policzmy C(10,3) ręcznie. 10! = 3 628 800. 3! = 6. 7! = 5 040. Dzielenie: 3 628 800 / (6 x 5 040) = 3 628 800 / 30 240 = 120. Trzy minuty z kartką.

A teraz C(49,6) ręcznie. 49! to liczba z 63 cyframi. Nie, to nie literówka. Sześćdziesiąt trzy cyfry. Oczywiście silnie się skracają w ułamku - wystarczy policzyć (49 x 48 x 47 x 46 x 45 x 44) / (6 x 5 x 4 x 3 x 2 x 1) = 10 068 347 520 / 720 = 13 983 816. Ale próba policzenia tego w głowie skończy się prędzej niż wynik. Kalkulator podaje odpowiedź natychmiast.

Z modulo jest łatwiej - 17 mod 5 policzy każdy w sekundę. Ale 123 456 789 mod 97? Tu potrzeba dzielenia pisemnego albo kalkulatora. A akurat 97 to dzielnik używany w walidacji IBAN - numer konta bankowego jest poprawny, jeśli po konwersji na liczbę daje resztę 1 z dzielenia przez 97.

15:30 - ściągawka: wzory i właściwości

Kompaktowo, do zapisania:

Dwumian Newtona:

• C(n,k) = n! / (k! x (n-k)!)
• C(n,0) = C(n,n) = 1
• C(n,k) = C(n,n-k) (symetria)
• C(n,k) = C(n-1,k-1) + C(n-1,k) (trójkąt Pascala)
• Suma wiersza: C(n,0) + C(n,1) + ... + C(n,n) = 2^n
• Kalkulator obsługuje n do 170 (powyżej wynik przekracza zakres JavaScript)

Modulo:

• a mod b = a - b x floor(a/b)
• Reszta z przedziału 0 do b-1
• a mod b = 0 oznacza: a jest podzielne przez b
• (a + b) mod n = ((a mod n) + (b mod n)) mod n
• (a x b) mod n = ((a mod n) x (b mod n)) mod n

Narzędzia omawiane w tym artykule

Kalkulator Dwumianu Newtona

Trzy tryby w jednym narzędziu: symbol Newtona C(n,k), rozwinięcie (a+b)^n na wyrazy i trójkąt Pascala do wiersza 170. Tabela współczynników, suma wyrazów i sprawdzenie symetrii. Oblicz dwumian Newtona

Kalkulator Modulo

Reszta z dzielenia, tabela reszt dla dowolnego zakresu i sprawdzanie podzielności. Podaj dzielną i dzielnik - kalkulator pokaże iloraz, resztę i wzór a = b x q + r. Oblicz resztę z dzielenia

Więcej narzędzi z kategorii Matematyka

• Kalkulator Kombinacji i Permutacji - P(n,k) i C(n,k) w jednym miejscu
• Kalkulator Silni - n! dla dowolnego n
• Kalkulator Prawdopodobieństwa - zdarzenia proste i złożone
• Kalkulator Ciągu Fibonacciego - wyrazy ciągu do F(1000)
• Kalkulator Potęg i Pierwiastków - potęgowanie i pierwiastkowanie
• Kalkulator Wariacji z Powtórzeniami - uporządkowane wybory z powtórzeniami
• Kalkulator Kombinacji z Powtórzeniami - nieuporządkowane wybory z powtórzeniami
• Kalkulator NWD i NWW - największy wspólny dzielnik i najmniejsza wspólna wielokrotność

Oblicz modulo dla popularnych wartości

• 10 modulo - ostatnia cyfra
• 17 modulo - zadania z matematyki
• 256 modulo - programowanie, bajty
• 365 modulo - dzień roku
• 1024 modulo - kilobajt