Wyrazić przez podłogi i sufity moc zbioru \(\mathbb{Z}\cap[a,b]\), \(\mathbb{Z}\cap[a,b)\), \(\mathbb{Z}\cap(a,b]\), \(\mathbb{Z}\cap(a,b)\), dla dowolnych rzeczywistych a, b.
Czy dla każdego rzeczywistego \(x\ge 1\) zachodzi równość \(\lceil\lg\lceil x\rceil\rceil = \lceil\lg x\rceil\)? Co jeśli wszystkie/niektóre sufity zamienimy na podłogi?
Spróbuj udowodnić przez indukcję nierówność \(\sum_{k=1}^n 1/k^2\le 2\). Jeśli nie wychodzi, to spróbuj wzmocnić tezę.
Udowodnij przez indukcję dolne oszacowanie dla liczb harmonicznych: \(H_{2^n}\ge \frac{n}{2}+1\).
Udowodnij przez indukcję nierówność Bernoulli'ego:
\[
1+nh\le (1+h)^n\ ,
\]
która zachodzi dla rzeczywistego \(h\ge-1\) i naturalnego \(n\).
Do problemu wież z Hanoi dokładamy dodatkowe ograniczenie: nie wolno przekładać krążka bezpośrednio między słupkami A i C. Ile teraz potrzeba ruchów? W oryginalnym problemie pojawia się \(2^n\) konfiguracji krążków na słupkach, podczas gdy wszystkich jest \(3^n\). Jak rozpoznać, czy dana konfiguracja wystąpi podczas przekładania krążków w oryginalnym problemie?
Oblicz sumy
(a) \( \sum_{0\leq i < n} (-1)^i i^3 \)
(b) \(\sum_{0 < i < n}i\,(i-1) 3^i\)
(c) \(\sum_{k=2}^n \frac{1}{(k-1)k(k+1)}\)
Oblicz następujące sumy podwójne:
(a) \(\sum_{1\le j\le i \le n} 2^i \)
(b) \(\sum_{1\le i\le j\le n}(j-i) \)
(c) \(\sum_{1\le k, j\le n} k\cdot j\)
(d) \(\sum_{1 \le j< k \le n}\frac{1}{k-j}\)
Oblicz sumę \(\sum_{0 \le i \le n} \left\lceil \sqrt{i} \right\rceil\)
Pokaż następującą równość, sumując przez części:
\[
\sum_{0\le i < n}i\, H_i \,=\, \frac{n^{\underline{2}}}{2}\,\Bigl(H_n-\frac{1}{2} \Bigr)\ .
\]
Dla jakich wartości \(i\) współczynnik dwumianowy \({n \choose i}\) przyjmuje wartość maksymalną, przy ustalonym \(n\)?
Wyprowadź wzór sumowania równoległego przez interpretację kombinatoryczną.
Wyprowadź wzór na sumowanie po górnym wskaźniku:
\[\sum_{i=0}^n {{i}\choose{ k}} = {{n+1}\choose{ k+1}}\]
na trzy sposoby:
a) indukcja z tożsamości Pascala,
b) interpretacja kombinatoryczna,
c) sumując przez różnice skończone.
Uprość następujące sumy:
(a) \(\sum_{i} i\, {{n}\choose{ i}} \)
(b) \(\sum_{i}i^2\, {{n}\choose{ i}}\)
(c) \(\sum_{k=0}^n (-1)^k {{n}\choose{ k}} {{k}\choose{ j}}\)
(d) \(\sum_{k=0}^{\lfloor n/2 \rfloor} {{n}\choose{2k}}\, 2^{2k} \);
(e) \(\sum_{k=0}^m (-1)^k \,{{n}\choose{ k}}\, {{n}\choose{ m-k}}\)
Oblicz sumę
\[ \sum_{ A,B\subseteq X}|A\cup B|\ , \]
sumując po wszystkich parach \(\langle A, B\rangle \)
podzbiorów zbioru X, gdzie \(|X|=n\).
Znajdź wzór na liczbę n-permutacji o danej sygnaturze.
Permutacja f jest inwolucją gdy \(f\circ f = id\). Pokaż, że
(a) permutacja jest inwolucją w.t.w. gdy ma sygnaturę \(1^{\alpha_1}2^{\alpha_2}\);
(b) każda permutacja jest złożeniem dwóch inwolucji.
Dane są liczby naturalne \(n\ge k>0\). Jakie jest prawdopodobieństwo, że w losowej n-permutacji jedynka należy do cyklu o długości k?
Pokaż, że losowa n-permutacja z prawdopodobieństwem $H_{n-1}/n$ składa się dokładnie z dwóch cykli.
Mamy n skarbonek i n kluczy, przy czym każdy klucz pasuje do dokładnie jednej skarbonki. Wrzucamy losowo po jednym kluczu do każdej skarbonki, po czym rozbijamy k skarbonek, \(1\leq k\leq n\). Oblicz prawdopodobieństwo tego, że dzięki temu będzie można otworzyć wszystkie pozostałe skarbonki.
Pokaż tożsamość
\[ x^n = \sum_k \left\{{n}\atop{k}\right\}\, x^{\underline{k}} \]
przez interpretację kombinatoryczna.
Pokaż następujące wzory:
\[ \left\{{n}\atop{k}\right\} = \sum_{i_1,\ldots,i_{n-k}}i_1\cdot i_2\dots i_{n-k} \cdot [1\le i_1\le i_2 \le \ldots \le i_{n-k}\le k]\ ,\]
\[\left[{n}\atop{k}\right] = \sum_{i_1,\ldots,i_{n-k}}i_1\cdot i_2\dots i_{n-k} \cdot [0< i_1 < i_2 < \ldots < i_{n-k} < n]\]
Znajdź funkcje tworzące ciągów \(\langle H_n\rangle\) i \(\langle n^2\rangle\).
Oblicz \( a_n = \sum_{0\le i\le n} F_i\cdot F_{n-i}\).
Niech
\[
G_k(z)=\sum_n\left\{{n}\atop{k}\right\}\,\frac{z^n}{n!}
\]
będzie w.f.t. dla liczb Stirlinga drugiego rodzaju, przy ustalonym dolnym wskaźniku. Pokaż, że \(G_k(z)=\frac{(e^z-1)^k}{k!}\), dowodząc kolejno tożsamości:
(a) \(\left\{{n+1}\atop{k+1}\right\} = \sum_{m}{{n}\choose{ m}}\left\{{m}\atop{k}\right\} \)
(b) \(\left\{{n+1}\atop{k+1}\right\} = \left\{{n}\atop{k+1}\right\}(k+1)+\left\{{n}\atop{k}\right\}\)
(c) \(G_k\, e^z = (k+1)\, G_{k+1} + G_k\).
Znajdź zwarty wzór na wykładniczą funkcję tworzącą liczb Bella \(B_n = \sum_k\left\{{n}\atop{k}\right\}\).
Permutacja f jest inwolucją, gdy złożenie f ze sobą jest identycznością. Pokaż, że wykładniczą f.t. dla liczby inwolucji jest \(e^{z+\frac{z^2}{2}}\) .
Oblicz, na ile sposobów można zapisać liczbę naturalną n jako sumę k nieujemnych całkowitych składników, gdzie rozkłady \(n=s_1+\cdots+s_k\) i \(n=t_1+\cdots+t_k\) są różne, gdy \(s_i\ne t_i\) dla pewnego \(1\le i\le k\).
Niech n będzie liczbą naturalną. Znajdź liczbę rozwiązań równania
\[
x_1+2\cdot x_2+2\cdot x_3 = n
\]
w~liczbach naturalnych \(x_1,x_2,x_3\).
Niech \(a_n\) oznacza liczbę ciągów długości n złożonych z liter A, B, C i nie zawierających dwóch sąsiednich liter A, ani dwóch sąsiednich liter B. Znajdź zwarty wzór na~\(a_n\).
Z kostek o wymiarach 1x2 układamy prostokąt o pionowej krawędzi długości 2 i poziomej krawędzi długości n. Kostki nie mogą na siebie
nachodzić; każda z połówek kostki może być pomalowana na jeden z dwóch kolorów (biały lub czarny). Kostki układamy od strony lewej do prawej: pierwszą kostkę kładziemy pionowo, a pozostałe tak, aby cała lewa krawędź każdej nowo kładzionej kostki dotykała kostek ułożonych wcześniej. Obowiązuje przy tym zasada, że kładziona kostka wzdłuż lewej krawędzi musi mieć takie same kolory, jak występujące na sąsiadujących z nią z lewej strony polach. Oblicz, na ile sposobów można ułożyć taki prostokąt.
Niech \(h_n\) oznacza liczbę sposobów pokolorowania szczebli n-szczeblowej drabiny na cztery kolory (czerwony, biały, niebieski i zielony) tak, że liczba szczebli czerwonych jest parzysta, a białych --- nieparzysta. Znajdź wykładniczą funkcję tworzącą ciągu \(h_n\) i oblicz \(h_{2001}\).
`
Na ile sposobów można rozdzielić 33 tys. zł. premii pomiędzy 22 pracowników firmy, w tym prezesa i jego zastępcę, jeśli szeregowy pracownik może dostać 1000 lub 1500 zł., a członek kierownictwa - nic, 1500 lub 3000 zł.?
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}|\).
Oblicz, ile jest liczb 8-cyfrowych nie zawierających cyfry 0 ani ciągu kolejnych cyfr \(\ldots 121\ldots\).
Znajdź liczbę permutacji zbioru \(\{1,\ldots,7\}\) nie zawierających czterech kolejnych elementów w porządku rosnącym.
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.
Znajdź liczbę n-nieporządków za pomoca wieżomianow (liczba rozstawień wież na dopełnieniu przekątnej).
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?
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\).
Na ile sposobów można rozstawić 6 nie atakujących się wież na czarnych polach szachownicy 8x8?
Pokaż następujące rekurencje na liczby \(p_k(n)\) (liczba podziałów n na k składników):
\(p_k(n) = p_{k-1}(n-1)+p_{k}(n-k)\)
\(p_k(n) = p_{k}(n-k)+p_{k-1}(n-k) +\cdots+p_{1}(n-k)\)
Oblicz \(p_2(n)\) i \(p_3(n)\).
Pokaż oszacowanie
\[\frac{1}{k!}\cdot{{n-1}\choose{k-1}}\ \le \ p_k(n)\ \le \ \frac{1}{k!}\cdot{{n+\frac{k(k-1)}{2}-1}\choose{k-1}} .\]
Pokaż, że liczba \(P(n)-P(n-1)\) jest równa liczbie podziałów~n na składniki większe niż 1.
Niech \(D(n;a_1,\ldots,a_m)\) oznacza liczbę podziałów n na części rozmiarów należących do zbioru \(\{a_1, a_2,\ldots, a_m\}\).
(a) Pokaż, że ten ciąg ma \(1/(1-t^{a_1})(1-t^{a_2})\ldots(1-t^{a_m})\) jako swoją f.t.
(b) Z rozkładu na ułamki proste
\[ \frac{1}{(1-t)(1-t^2)}=\frac{1}{2(1-t)^2}+\frac{1}{4(1-t)}+\frac{1}{4(1+t)} \]
wyprowadź wzór na D(n;1,2).
Wykaż, że łączna liczba składników we wszystkich podziałach liczby n jest równa \(\sum_{k=0..n-1} P(k) \tau(n-k)\), gdzie P(k) to liczba
podziałów k, a \(\tau(m) = \sum_{d | m} 1\) jest liczbą (dodatnich) dzielników m.
Rozwiąż równanie rekurencyjne
\(f_n = \frac{2n-1}{n}f_{n-1} - \frac{n-1}{n} f_{n-2} + 1, \quad f_0 = 0, f_1 = 1\ .\)
Jakie jest prawdopodobieństwo, że w losowej 6-permutacji 1 i 2 są w tym samym cyklu, a 3 -- w innym?
Udowodnij tożsamość
\[ {{i+j}\choose{i}}\left\{{n}\atop{i+j}\right\} = \sum_{k=0}^n {{n}\choose{k}}\left\{{k}\atop{i}\right\}\left\{{n-k}\atop{j}\right\}\ .\]
Znajdź \( \sum_{n=0}^\infty \sum_{k=0}^n \frac{F_{2k}F_{n-k}}{10^n}, \) gdzie \(F_n\) to n-ta liczba Fibonacciego.
Udowodnij, że na każdym przyjęciu są dwie osoby o takiej samej liczbie
znajomych.
Udowodnij, że przynajmniej jeden z grafów G, G' (dopełnienie) jest spójny. Niech diam(G) oznacza średnicę grafu G (nieskończoność jeśli G jest niespójny) i niech f(G) = min(diam(G), diam(G')). Znajdź sup f(G) po wszystkich grafach G.
Udowodnij, że w K6 dowolnie pokolorowanym krawędziowo na 2 kolory jest
monochromat. trojkat (są nawet dwa!), ale w K5 niekoniecznie.
Rozstrzygnij, czy istnieje:
a) graf o ciągu stopni wierzchołków (3 3 3 3 5 6 6 6 6 6 6)
b) (3 3 3 3 3 5 6 6 6 6 6 6)
c) dwudzielny (3 3 3 3 3 5 6 6 6 6 6 6)
d) drzewo (dowolny ciąg długości n o sumie 2n-2)
Podaj przykład dwóch nieizomorficznych grafów spójnych o takich samych
ciągach stopni wierzchołków.
Graf niezorientowany jest orientowalny, jeśli można na jego krawędziach
dorysować strzałki tak, żeby dostać digraf silnie spójny. Pokaż, że graf spójny
jest orientowalny wtedy i tylko wtedy, gdy nie ma mostów.
Centrum grafu G to zbiór wierzchołków v, dla których maxw d(v,w) jest najmniejsze. Udowodnij, że centrum drzewa to pojedynczy wierzchołek albo para wierzchołków połaczonych krawędzią.
Udowodnij twierdzenie Cayleya o zliczaniu drzew etykietowanych: Kn ma nn-2 drzew rozpinających
(a) wskazując bijekcję między takimi drzewami a (n-2)-ciągami o elementach ze zbioru {1,...,n} (kody Prufera);
(b) sumując liczby drzew o ustalonym układzie stopni wierzchołków.
Podaj przykłady grafów na wszystkie cztery kombinacje:
(istnieje/nie istnieje) x (cykl Eulera/cykl Hamiltona)
Udowodnij, ze jeśli G jest spójny o k>0 wierzchołkach nieparzystych stopni,
to k jest parzyste i k/2 jest najmniejszą liczbą krawędziowo rozłącznych
łańcuchów pokrywających wszystkie krawędzie G.
Z kompletu 28 kamieni domina (od 0-0 do 6-6) usuwamy kamienie 0-1, 0-2,
0-3. Ile jeszcze trzeba usunać, żeby resztę dało się ułożyć w łańcuch
zamknięty?
Które pełne grafy dwudzielne i trójdzielne są eulerowskie?
hamiltonowskie?
Pokaż, że graf Petersena jest maksymalny niehamiltonowski.
Pokaż, że turniej jest hamiltonowski <=> jest silnie spójny.
Udowodnij, że jesli z kodu Graya zdefiniowanego rekurencyjnie
G(0) = pusty ciąg; G(n+1) = (0G(n); 1G(n)R)
wypisać wektory zawierające k jedynek, to dwa sąsiednie (cyklicznie)
wektory mają odległość Hamminga równą 2. Napisać wzór rekurencyjny na taki
'okrojony' kod Graya G(n,k).