RP_Kombinatoryka.doc

                                                                                                     Semestr Zimowy 2012/13

Informacje wstepne 

Wyklad: Podstawy Metod Probabilistycznych i Statystyki

dr hab. Janusz Szczepanski, prof. nadzw. UKW http://www.ippt.gov.pl/~jszczepa

KOMBINATORYKA

Definiujemy

, przyjmujemy 0!=1

Permutacje

Niech H bedzie zbiorem skończonym liczbie elementów rownej n. Kazde uporządkowanie zbioru H nazywamy permutacja. Matematycznie odpowiada to następującemu pojeciu, kazda funkcje roznowartosciowa ze zbioru H w zbior nazywamy permutacja zbioru H.

Na zbiorze mamy naturalny porządek. Przyporzadkowana liczba odpowiada pozycji elementu w zbiorze uporządkowanym.

Można tez spojrzec na permutację jak na odwzorowanie różnowartościowe ze zbioru n-elementowego w ustalony zbior n-elementowy.

Zachodzi pytanie ile jest permutacji zbioru H liczącego n elementow.

Twierdzenie

Ilosc permutacji zbioru n elementowego jest rowna

Dowod

Indukcyjny

n=1 oczywiste

Zalozmy, ze jest prawdziwe twierdzenie dla n.

Rozpatrzmy zbior n+1 elementowy.

Ustalmy jeden element. Wówczas z każdym porzadkiem pozostałych n elementow można po dodaniu tego elementu stowarzyszyc n+1 permutacji pelnego n+1 elementowego ciagu. Zatem (rysunek)

Wariacje (bez powtórzeń)

Dany jest zbior n-elementowy H. Na ile sposobow można wybrac, ze zbioru H uporządkowane podzbiory m-elementowe.

Matematycznie, oznacza to, ile jest funkcji różnowartościowych, ze zbioru m-elementowego w zbior n-elementowy. Oznaczmy ta ilość przez

Twierdzenie

Ilosc wariacji

Dowod

Indukcja ze względu na m.

n=1,    Przyjmuje się, że 0!=1

Zalozmy, ze Tw. jest prawdziwe dla ustalonego n i dla . Rozpatrzmy odwzorowania różnowartościowe ze zbioru m+1 elementowego w zbior n elementowy. Pierwszych m elementow można odwzorowac na  sposobow. Z każdym odwzorowaniem można stowarzyszyc n-m odwzorowan zbioru m+1 elementowego wiec

co konczy dowod.

Kombinacje

Problem: Na ile sposobow można wybrac podzbior m elementowy ze zbioru n elementowego.

Innymi slowy ile jest kombinacji m elementowych spośród elementow zbioru n elementowego.

Twierdzenie

Ilosc kombinacji m elementowych sposrod elementow zbioru n elementowego jest rowna

Dowod.

Biorąc pod uwagę, że nie uwzględniamy porzadku, mamy:

Wariacje z powtorzeniami

Na ile sposobow można odwzorowac zbior m elementowy w zbior n elementowy?

Oznaczmy ilość wszystkich takich odwzorowan symbolem .

Twierdzenie

Ilosc wszystkich wariacji z powtorzeniami

Dowod

Indukcyjny ze wzgledu na m.

m=1 oczywiste

Zakladamy, ze jest prawdziwy wzor dla m, wiec . Można zauważyć, ze