Funkcje tworzące dla zawodników

Zbiór informacji o elementarnych zagadnieniach matematyki, klasyfikowanych najczęściej jako "ciekawostki" właśnie...
koobstrukcja
Użytkownik
Użytkownik
Posty: 83
Rejestracja: 14 paź 2008, o 19:53
Płeć: Mężczyzna
Podziękował: 1 raz
Pomógł: 12 razy

Funkcje tworzące dla zawodników

Post autor: koobstrukcja » 30 lip 2011, o 00:10

Definicja i oznaczenia

Funkcja tworząca \(\displaystyle{ F(x)}\) dla ciągu \(\displaystyle{ a_0, a_1, \ldots a_n, \ldots}\) jest to formalny szereg potęgowy \(\displaystyle{ a_0+a_1 x+ \cdots +a_nx^n+ \cdots}\).
Przy tych oznaczeniach dla prostoty będziemy oznaczać \(\displaystyle{ [x^n]F(x)=a_n}\).

Podstawowe przykłady

\(\displaystyle{ \begin{array}{c|c} \mbox{Ciąg} & \mbox{Funkcja tworząca}\\\cline{1-2}\\ 1, 1, 1, 1, 1, \ldots &\frac{1}{1-x}\\\\ 1, 2, 3, 4, 5, \ldots & \frac{1}{(1-x)^2}\\\\ \binom{k}{0}, \binom{k}{1}, \binom{k}{2}, \ldots & (1+x)^k\\\\ \mbox{ciąg Fibonacciego}\; f_n & \frac{x}{1-x-x^2}\\\\ 1, k, k^2, k^3, k^4, \ldots & \frac{1}{1-kx}\\\\ 0, 1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \ldots & \ln(\frac{1}{1-x})\\\\ 1, \frac{1}{1!}, \frac{1}{2!}, \frac{1}{3!}, \frac{1}{4!}, \ldots & e^x \end{array}}\)

Zadania z rozwiązaniami

Zadanie 1.
Ile jest ciągów binarnych długości \(\displaystyle{ n}\) mających \(\displaystyle{ k}\) jedynek oraz żadne z jedynek nie stoją obok siebie ?

Niech \(\displaystyle{ S}\) to szukana wartość, mamy wtedy:

\(\displaystyle{ \begin{array}{ccl} S&=&[x^n](x+x^2+x^3+\ldots)(x^2+x^3+x^4+\ldots)^{k-1}(1+x+x^2+\ldots)\\ &=&[x^n]\frac{x^{2k-1}}{(1-x)^{k+1}}\\ &=&[x^{n-2k+1}]\frac{1}{(1-x)^{k+1}}\\ &=&{n-k+1\choose k}. \end{array}}\)

Zadanie 2.
Podzbiór zbioru \(\displaystyle{ \{1,\ldots, n\}}\) nazywamy samolubnym jeśli zawiera liczbę swoich elementów
jako element, natomiast inne elementy są od niej większe. Znajdź liczbę samolubnych
podzbiorów.


Oznaczmy przez \(\displaystyle{ b(n)}\) szukaną wartość, wtedy:

\(\displaystyle{ \begin{array}{ccl} b(n)&=&[x^n]\sum_{m=0}^{\infty}x^m\sum_{k=0}^{\infty}x^k(x+x^2+x^3+\cdots )^{k-1}\\ &=&[x^n]\frac{x}{1-x-x^2}\\&=&f_n. \end{array}}\)

Zadanie 3.
Niech \(\displaystyle{ p>2}\) będzie liczbą pierwszą. Udowodnij, że \(\displaystyle{ \sum_{n=0}^{p}{p\choose n}{{p+n} \choose n} \equiv 2^p+1 \pmod {p^2}}\).

\(\displaystyle{ \begin{array}{ccl} \sum_{n=0}^{p}{p\choose n}{{p+n} \choose n}&=&[x^p]\sum_{n=0}^{p}{p\choose n}(1+x)^{p+n}\\&=&[x^p](1+x)^p(1+(1+x))^p\\ &=&\sum_{n=0}^{p}{p\choose n}{p \choose {p-n}}2^n\\&\equiv& 2^p+1 \pmod {p^2}. \end{array}}\)

Zadanie 4.
Uporządkowaną parę \(\displaystyle{ (A,B)}\) podzbiorów zbioru \(\displaystyle{ \{1, \ldots, n\}}\) nazywamy dopuszczalną, gdy
\(\displaystyle{ a > |B|}\) dla każdego \(\displaystyle{ a\in A}\) oraz \(\displaystyle{ b > |A|}\) dla każdego \(\displaystyle{ b\in B}\). Znajdź liczbę dopuszczalnych par.


Oznaczmy przez \(\displaystyle{ c(n)}\) szukaną wartość, wtedy kombinatorycznie mamy:
\(\displaystyle{ c(n)=\sum_{a+b\leq n}{n-b\choose a}{n-a\choose b}}\). Wówczas :

\(\displaystyle{ \begin{array}{ccl} c(n)&=&[x^n]\sum_{k=0}^{\infty}x^k\sum_{a=0}^{\infty}\binom{a+k}{a}x^a\sum_{b=0}^{\infty}\binom{b+k}{b}x^b\\&=&[x^n]\sum_{k=0}^{\infty}\left(\frac{1}{(1-x)^{k+1}}\right)^2\\ &=&[x^n]\frac{1}{(1-x)^2}\sum_{k=0}^{\infty}\left(\frac{x}{(1-x)^2}\right)^k\\&=&[x^n]\frac{1}{1-3x+x^2}=[x^n]\frac{1}{(1-x)^2-x}=[x^{2n}]\frac{1}{(1-x^2)^2-x^2}\\ &=&[x^{2n}]\frac{1}{(1-x-x^2)(1+x-x^2)}\\ &=&[x^{2n}]\frac{1+x}{1-x-x^2}=f_{2n}+f_{2n+1}=f_{2n+2}. \end{array}}\)

Zadanie 5.
Niech \(\displaystyle{ c(n)}\) oznacza liczbę partycji liczby \(\displaystyle{ n}\) takich, że żadna para liczb w partycji nie
różni się wiecej niż o jeden. Oblicz wartosc \(\displaystyle{ c(n)}\).


\(\displaystyle{ \begin{array}{ccl} c(n)&=&[x^n]\sum_{k=1}^{\infty}(x+x^{k+k}+\cdots)(1+x^{k+1}+x^{(k+1)+(k+1)}+\cdots)\\ &=&[x^n]\sum_{k=1}^{\infty}\frac{x^k}{1-x^k}\frac{1}{1-x^{k+1}}\\ &=&[x^n]\frac{1}{(1-x)^2}\sum_{k=1}^{\infty}\frac{x^k}{(1+x+\cdots +x^{k-1})(1+x+\cdots +x^{k})}\\ &=&[x^n]\frac{1}{(1-x)^2}\lim_{m\to\infty}\left(1-\frac{1-x}{1-x^{m+1}}\right)\\&=&[x^n]\frac{x}{(1-x)^2} \\&=&n. \end{array}}\)

Zadania do samodzielnego rozwiązywania

Zadanie 6.
Udowodnij poniższą tożsamość ze współczynnikami Newtona i liczbami Fibonacciego
\(\displaystyle{ \sum_{k=0}^n\binom{n}{k}\binom{n+k}{k}f_{k+1} \ =\ \sum_{k=0}^n\binom{n}{k}\binom{n+k}{k}(-1)^{n-k}f_{2k+1}}\)


Wskazówka: funkcja tworząca dla obu stron to : \(\displaystyle{ \frac{\sqrt{3 x^2-2x+3+2 \sqrt{x^4-8 x^3-2 x^2-8 x+1}}}{\sqrt{5}\cdot\sqrt{x^4-8 x^3-2 x^2-8 x+1}}}\)

Zadanie 7.
Niech \(\displaystyle{ p}\) bedzię partycją, \(\displaystyle{ f(p)}\) liczbą jedynek w partycji \(\displaystyle{ p}\), natomiast \(\displaystyle{ g(p)}\) oznacza liczbę
róznych liczb użytych w partycji \(\displaystyle{ p}\). Pokaz, że \(\displaystyle{ \sum f(p)=\sum g(p)}\), gdzie sumowanie odbywa
się po wszystkich partycjach ustalonej liczby \(\displaystyle{ n}\).


Wskazówka: funkcja tworząca dla obu stron to : \(\displaystyle{ \frac{x}{(1-x)^2(1-x^2)(1-x^3)(1-x^4)\cdots}}\)

Zadanie 8.
Udowodnij, że przy ustalonym \(\displaystyle{ n\in\mathbb{N}}\) zachodzi :
\(\displaystyle{ \sum_{i+j+k=n}{i+j \choose i}{j+k \choose j}{k+i \choose k}=\sum_{m=0}^{n}{2m \choose m}}\)
Ostatnio zmieniony 2 sie 2015, o 11:43 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.

ODPOWIEDZ