Kombinácie bez opakovania

Doplnková kombinácia

Kombinácie \small  K a \small  L množiny \small  M_n sa nazývajú navzájom doplnkové ak platí: \small  K ∩ L = ∅ a \small  K \cup L=M_n .
                                                                           

Z pohľadu teórie množín je podmnožina \small  L doplnok podmnožiny \small  K v základnej množine \small  M_n .
Veta: Počet r - kombinácií množiny \small  M_n sa rovná počtu jej (n-r)- kombinácií: \small  C(n, r)=C(n, n - r) .

 

Dôkaz tvrdenia:
Označme \small  A(r) resp. \small  A(n-r) množinu všetkých r- kombinácií resp. (n-r)- kombinácií množiny \small  M_n .
    Skonštruujme zobrazenie \small  \phi : A(r) \rightarrow A(n-r) nasledovne:
    ak \small  K \in A(r) , tak jeho obrazom \small  \phi (K)   bude doplnková kombinácia ku \small  K .
    Zrejme zobrazenie  \phi je bijekcia, preto množiny \small  A(r) a \small  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.

\( .\)