Úvod do řešení problémů … (IPS)

Příklady ze semináře 20. 10.

1. Počet posloupností N nul a jedniček, které neobsahují dvě jedničky za sebou.
2. Počet dláždění obdélníka 2xN kostkami 1x2 a 2x1.
3. Počet uzávorkování s N levými a N pravými závorkami.
4. Počet cest v mřížce z bodu (0,0) do bodu (M,N) skládajících se z kroků (1,0) a (0,1).
5. ... takových, že nikdy neprotnou úhlopříčku?
6. Suma pro K=0 až N z C(n,k)*k, kde C(n,k) je kombinační číslo "N nad K".
7. Suma pro K=L až N z C(N,K)*C(K,L).
8. Suma pro K=0 až N z C(N,K)*2^K.
9. Suma pro K=0 až N z C(N,K)².
10. Počet K-rozměrných stěn N-rozměrné krychle.
11. Počet binárních stromů na N vrcholech.
12. Počet neklesajících funkcí z {1,…N} do {1,…,M}.
13. Počet permutací na {1,…,N} takových, že 1 a 2 jsou na společném cyklu.
14. Počet pěstovaných stromů na N vrcholech.
15. Nechť X je N-prvková množina. Počítejte dvojice množin (A,B) takových, že A je podmnožinou B a B podmnožinou X.
16. Počet permutací f na {1,…,N} takových, že f složeno s f je identita.
17. Počet podmnožin {1,…,N}, které neobsahují 2 po sobě jdoucí čísla.