Kombinatorika: Doplnková kombinácia

Kombinatorika

Kombinácie

$K$ a

$L$ množiny

$M_n$ sa nazývajú navzájom doplnkové ak platí:

$K ∩ L = ∅$ a

$K \cup L=M_n$ .

Z pohľadu teórie množín je podmnožina

$L$ doplnok podmnožiny

$K$ v základnej množine

$M_n$ .

Veta: Počet

$r -$ kombinácií množiny

$M_n$ sa rovná počtu jej

$(n-r)-$ kombinácií: $C(n, r)=C(n, n - r)$ .

Dôkaz tvrdenia:

Označme

$A(r)$ resp.

$A(n-r)$ množinu všetkých

$r-$ kombinácií resp.

$(n-r)-$ kombinácií množiny

$M_n$ .
Skonštruujme zobrazenie

$\phi : A(r) \rightarrow A(n-r)$ nasledovne:
ak

$K \in A(r)$ , tak jeho obrazom

$\phi (K)$ bude doplnková kombinácia ku

$K$ .

Zrejme zobrazenie

$\phi$ je bijekcia, preto množiny

$A(r)$ a

$A(n-r)$ majú rovnaký počet prvkov. Tým je dôkaz ukončený.

Príklad.
Pri výťahu, do ktorého môžu nastúpiť najviac tri osoby, stojí 5 osôb. Označme je

$a,b,c,d,e$ . Zostavte všetky trojice osôb, ktoré môžu nastúpiť do výťahu.
Riešenie:

Otvorte si zadanie Tu

$<span class="nolink">$ .$ $