3582308151

MATEMATYKA DYSKRETNA 2011/12 ZESTAW 01

PODSTAWY KOMB1NATORYKI

1. TEORIA

Dany niech będzie n-elementowy zbiór X, n > 0, oraz liczba naturalna k taka, że 0 < k < n. Klasycznym problemem kombinatorycznym jest pytanie o to, na ile sposobów można ze zbioru X wybrać k elementów. Należy jednak ustalić dwie rzeczy: po pierwsze, czy wybrane elementy mogą się powtarzać; po drugie, czy kolejność wyboru elementów jest istotna. Jak widać, istnieją cztery różne schematy wyboru.

Wariacja z powtórzeniami, fe-elementową wariacją z powtórzeniami ze zbioru ^-elementowego nazywamy liczbę możliwych wyborów k elementów z n-elemento-wego zbioru, przy czym wybierane elementy mogą się powtarzać, a ich kolejność ma znaczenie.

Wariacja bez powtórzeń, fc-elementową wariacją bez powtórzeń ze zbioru n~e lementowego nazywamy liczbę możliwych wyborów k elementów z n-elementowego zbioru, przy czym wybierane elementy nie mogą się powtarzać, a ich kolejność ma znaczenie.

Kombinacja bez powtórzeń, -elementową kombinacją bez powtórzeń (lub prościej: kombinacją) ze zbioru n-elementowego nazywamy liczbę możliwych wyborów k różnych elementów z n-elementowego zbioru, przy czym kolejność wybieranych elementów nie ma znaczenia.

Kombinacja z powtórzeniami, fe-elementową kombinacją z powtórzeniami ze zbioru n-elementowego nazywamy liczbę możliwych wyborów k elementów z n-elementcwego zbioru, przy czym kolejność wybieranych elementów nie ma znaczenia, a elementy mogą się powtarzać (wybrane elementy tworzą multizbiór).

Szczególnym przypadkiem wariacji bez powtórzeń, dla k = n, jest permutacja.

Permutacja. Permutacją zbioru n-elementowego nazywamy liczbę możliwych ułożeń elementów tego zbioru w ciąg.

Oznaczenia. Wprowadźmy oznaczenia dla powyższych schematów. Dla ustalonych k oraz n będziemy pisać:

•    Wn - na oznaczenie wariacji z powtórzeniami

•    i/f - na oznaczenie wariacji bez powtórzeń

•    C% - na oznaczenie kombinacji z powtórzeniami

•    ej -na oznaczenie kombinacji bez powtórzeń

•    n! - na oznaczenie permutaeji