MATEMATYKA
Polub moją stronę:)
The Mathteacher FILM
Tomasz Grębski
Kombinatoryka
Nowa strona 1

Oznaczenia i potrzebne definicje
 

  • Silnia
    Formula, symbol Formula czyta się ,,n silnia", umownie przyjmuje się, że Formula.
    Wypiszmy kilka watości silni: 1!=1, 2!=2, 3!=6, 4!=24, 5!=120, ....
    Często symbol Formula "trzeba widzieć" w zadaniach jako:

    Formula

  • Współczynniki dwumianu Newtona
    Dla Formula określamy liczbę
    Formula (symbol Formulaczytamy ,,n nad k").
    Jest to liczba Formula wyrazowych podzbiorów, jakie można utworzyć ze zbioru Formula-elementowego.
    Z równości

    Formula


    wynika, że liczba wszystkich podzbiorów - włączając w to zbiór pusty i cały zbiór - jakie można utworzyć ze zbioru Formula-elementowego jest równa 2n.

  • Ciągi i zbiory elementów
    (a,b) - para uporządkowana
    (ciąg) dwóch elementów, ważne jest to jakie elementy ją tworzą, ale także ich kolejność,
    {a,b} - para nieuporządkowana (zbiór) dwóch elementów, kolejność nie jest ważna, {a,b} = {b,a}.
    Podobnie dla trójek:
    (a,b,c) - uporządkowana trójka, czyli ciąg z trzech elementów,
    {a,b,c} - zbiór trójelementowy.

  • Liczbę elementów zbioru A nazywamy mocą tego zbioru i oznaczamy Formula lub |A|.

  • Jeżeli Formula to moc Formula
    zawsze, dla dowolnych A i B: Formula

Schematy wyboru

Niech A będzie zbiorem skończonym Formula-elementowym
Formula
Zajmiemy się losowym wybieraniem Formula elementów spośród Formula elementów tego zbioru.
Przed przystąpieniem do losowania trzeba ustalić:
1. czy istotna jest kolejność w jakiej wybieramy elementy. Inaczej - czy z wylosowanych elementów tworzymy ciąg czy zbiór,
2. czy wybrany element jest zwracany do zbioru A. Inaczej - czy losowanie jest ,,bez zwracania" czy ,,ze zwrotem".

Zasady przeliczania

Prawo (reguła) mnożenia
Jeżeli pewna procedura (pewien wybór) może być rozbita na Formula kolejnych kroków z Formula wynikami w pierwszym kroku, Formula wynikami w drugim kroku, ... , Formula wynikami w Formula-tym kroku, to cała procedura może być zrealizowana na Formula sposobów.

Prawo dodawania
Jeżeli zbiory A i B są rozłączne, tzn. gdy Formula to
Formula

Tak samo dla większej liczby rozłącznych zbiorów.

Przeliczanie zbiorów (liczby wyborów) metodą prymitywną tzn. przez wypisanie wszystkich możliwości, ma sens wówczas, gdy liczba elementów zbioru jest mała. W przeciwnym razie trzeba znać wzór na liczbę wyborów lub metodę przeliczania. Są cztery podstawowe schematy zliczania - schematy kombinatoryczne.
1. Losujemy bez zwracania Formula elementów Formula i ustawiamy je kolejno - tworzymy Formula-wyrazowy ciąg. Każdy z powstałych ciągów nazywa się wariacją bez powtórzeń z Formula elementów po Formula elementów.
 

Wszystkich wariacji bez powtórzeń z Formula elementów po Formula elementów Formula jest
Formula

2. Losujemy ze zwrotem Formula elementów Formula i ustawiamy je kolejno - tworzymy Formula-wyrazowy ciąg. Każdy z takich ciągów nazywa się wariacją z powtórzeniami z Formula elementów po Formula elementów.
 

Wszystkich wariacji z powtórzeniami z Formula elementów po Formula elementów Formula jest
Formula

3. Mamy zbiór Formula elementowy. Elementy tego zbioru ustawiamy w ciąg Formula lub - co na jedno wychodzi - numerujemy je od 1 do Formula Każdy z takich ciągów nazywa się permutacją Formulaelementów.
 

Liczba wszystkich możliwych sposobów ustawienia (permutacji) różnych Formula elementów jest równa
Formula

4. Mamy zbiór Formula elementowy. Wybieramy z niego Formula elementów Formula bez zwrotu i tworzymy z nich zbiór, kolejność nie ma znaczenia. Każdy z takich zbiorów nazywamy kombinacją Formula-elementową ze zbiorów Formula-elementowego.
 

Wszystkich kombinacji z Formula elementów po Formula elementów Formula jest
Formula

Dołączamy jeszcze:
1. Wzór na liczbę podziałów niepustego zbioru. Niech A będzie zbiorem Formula-elementowym, który dzielimy na Formula rozłącznych podzbiorów składających się z Formula elementów Formula Liczba różnych takich podziałów wyraża się wzorem:
Formula
Np. Liczba różnych rozdań 52 kart po 13 dla każdego z czterech grających w brydża jest równa
Formula
2. Wzór na liczbę rozmieszczeń Formulanierozróżnialnych kul w Formula komórkach - czyli kombinacji z powtórzeniami:
Formula
Np. Na ile sposobów Formula pasażerów może wysiąść z windy na Formula piętrach?
Formula



Podziel się z innymi: Facebook Google Tweet This

POLECAM
 

 

 

 

 

 

 

 

 

 

 

 

 

 



TEORIA
Logowanie
Nazwa użytkownika

Hasło



Nie możesz się zalogować?
Poproś o nowe hasło