Úkoly z diskrétní matematiky, 7. série

Veškerá tvrzení precizně zdůvodněte.

Pokud něco dokazujete/počítáte principem inkluze a exkluze, podrobně popište, odkud se berou jednotlivé vzorce, přesně napište, jaké množiny sjednocujete. (Prostě: chrchel faktoriálů se zdůvodněním ţtak to vyjde� neberu.)

(7.1) Na plese se sešlo n manželských párů. Kolika možnostmi je lze rozdělit do tanečních párů (pro jistotu: vždy muže s ženou) tak, aby spolu nikdy netančil manželský pár? 2 body

(7.2) Kolik je permutací s právě k pevnými body? 2 body

(7.3) Kolika možnostmi lze postavit do řady písmena A až P tak, aby se v řetězci nevyskytovala jako vybraný podřetězec (což není to samé jako souvislý podblok, podřetězec vznikne škrtnutím některých písmen a sešoupnutím zbývajících k sobě) slova DOBA, PONK, COP a OPICE? 3 body

(7.4) Kolik je všech funkcí f: [n] → [m], které jsou na? 3 body

(7.5) Máme k kuliček a n přihrádek. Kolika možnostmi můžeme kuličky umístit do přihrádek, když

(i) kuličky jsou rozlišitelné a do přihrádek lze umístit libovolný počet kuliček (ii) kuličky jsou nerozlišitelné a do přihrádek lze umístit libovolný počet ku-

liček (iii) kuličky jsou rozlišitelné a do přihrádek je třeba umístit alespoň jednu

kuličku (iv) kuličky jsou nerozlišitelné a do přihrádek je třeba umístit alespoň jednu

kuličku 6 bodů