UKTG Prednáška 8. týždeň (Princíp inklúzie a exklúzie)

Zhrnutie prednášky

Prednáška zavádza princíp inklúzie a exklúzie na úlohe určiť, koľko čísel z množiny {1, …, n} je súdeliteľných s n. Pre n = p·r a n = p·q·r sa postupne odvodzuje, že pri súčte násobkov jednotlivých prvočísel sa niektoré čísla započítajú viackrát, a preto sa musia odpočítať prieniky dvojíc a pripočítať prienik trojice. Z toho vzniká zovšeobecnené pravidlo súčtu pre zjednotenie troch a následne n množín, ktoré sa strieda sčítaním a odčítaním súčtov prienikov. Na záver sa hľadá presný zápis tohto vzorca pomocou súčtov S₁, S₂, …, S_k cez k-prvkové kombinácie indexov i₁ < i₂ < … < i_k z rozsahu 1 až n.

• - Úloha: spočítať čísla z {1, …, n} súdeliteľné s n; pre prvočíslo ide o jeho násobky.
• - Pre n = p·r sa počet násobkov p a r sčíta a prienik (číslo p·r) sa odpočíta, čo je zovšeobecnené pravidlo súčtu pre dve množiny.
• - Pre n = p·q·r sa sčítajú jednotlivé množiny, odpočítajú prieniky dvojíc a pripočíta prienik všetkých troch.
• - Princíp inklúzie a exklúzie určuje počet prvkov zjednotenia n množín striedavým sčítaním a odčítaním prienikov.
• - Pravidlo súčtu pre disjunktné množiny je špeciálny prípad, keď sú prieniky prázdne.
• - Člen S_k je súčet počtov prvkov prienikov všetkých k-prvkových výberov množín.
• - Pri zápise sa používajú indexy i₁ < i₂ < … < i_k z rozsahu 1 až n, aby sa žiadna kombinácia nezapočítala viackrát.

Zhrnutie pripravené s pomocou AI z prepisu videa.