Ćwiczenia 7: zasada włączania-wyłączania, wieżomiany

Zadanie 1

Udowodnij, że liczba elementów zbioru X należących do co najmniej \(r>0\) spośród zbiorów \(A_1,\ldots,A_n\), gdzie \(A_i\subseteq X\) dla \(i=1,\ldots n\), wynosi
\[\sum_{k=r}^n (-1)^{k-r}{{k-1}\choose{r-1}} S_k\ ,\]
gdzie \(S_k=\sum_{1\leq i_1 < \ldots < i_k\leq n}|A_{i_1}\cap\ldots\cap A_{i_k}|\).

Zadanie 2

Oblicz, ile jest liczb 8-cyfrowych nie zawierających cyfry 0 ani ciągu kolejnych cyfr \(\ldots 121\ldots\).

Zadanie 3

Znajdź liczbę permutacji zbioru \(\{1,\ldots,7\}\) nie zawierających czterech kolejnych elementów w porządku rosnącym.

Zadanie 4

Pokaż, że wielomiany \(ax+1, ax^2+(a+2)x+1, abx^2+(a+b+1)x+1\) są wieżowe dla dow. a,b naturalnych.

Zadanie 5

Znajdź liczbę n-nieporządków za pomoca wieżomianow (liczba rozstawień wież na dopełnieniu przekątnej).

Zadanie 6

7 krasnoludków \(k_1,\ldots,k_7\) ma codziennie do wykonania 7 prac \(k_1,\ldots,k_7\), przy czym:
\(k_1\) nie umie wykonać \(p_2, p_3\)
\(k_2\) nie umie wykonać \(p_1, p_5\)
\(k_4\) nie umie wykonać \(p_2, p_7\)
\(k_5\) nie umie wykonac \(p_4\).
Przez ile dni mogą rozdzielać prace codziennie inaczej?

Zadanie 7

Udowodnij, że wielomianem wieżowym planszy \(\{(i,i), (i,i+1): i = 1,\ldots,n\}\) jest \(\sum_{k=0}^n {{2n+1-k}\choose{k}} x^k\).

Zadanie 8

Na ile sposobów można rozstawić 6 nie atakujących się wież na czarnych polach szachownicy 8x8?