[kółko] Funkcje tworzące

Iniemamocni · Rejestracja: 12.12.04 16:18 Posty: 913

Definicja i oznaczenia

Funkcja tworząca

dla ciągu

jest to formalny szereg potęgowy

.
Przy tych oznaczeniach dla prostoty będziemy oznaczać

.

Podstawowe przykłady

$\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

mających

jedynek oraz żadne z jedynek nie stoją obok siebie ?

Niech

to szukana wartość, mamy wtedy:

$\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

nazywamy samolubnym jeśli zawiera ilość swoich elementów
jako element, natomiast inne elementy są od niej większe. Znajdź ilość samolubnych
podzbiorów.

Oznaczmy przez

szukaną wartość, wtedy:

$\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

będzie liczbą pierwszą. Udowodnij, że

.

$\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ę

podzbiorów zbioru

nazywamy dopuszczalną, gdy

dla każdego

oraz

dla każdego

. Znajdź ilość dopuszczalnych par.

Oznaczmy przez

szukaną wartość, wtedy kombinatorycznie mamy:

. Wówczas :

$\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

oznacza ilość partycji liczby

takich, że żadna para liczb w partycji nie
różni się wiecej niż o jeden. Oblicz wartosc

.

$\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

$\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 :

$\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

bedzię partycją,

ilością jedynek w partycji

, natomiast

oznacza ilość
róznych liczb użytych w partycji

. Pokaz, że

, gdzie sumowanie odbywa
się po wszystkich partycjach ustalonej liczby

.

Wskazówka: funkcja tworząca dla obu stron to :

$\frac{x}{(1-x)^2(1-x^2)(1-x^3)(1-x^4)\cdots}$

Zadanie 8.
Udowodnij, że przy ustalonym

zachodzi :

$\sum_{i+j+k=n}{i+j \choose i}{j+k \choose j}{k+i \choose k}=\sum_{m=0}^{n}{2m \choose m}$

misioo · Rejestracja: 12.04.06 15:11 Posty: 6634

fajne wprowadzenie, z rozwiązanymi przykładami ... niech dołączy do powyższych kółkowych opracowań - przyklejam

Wydarzenie ... już wkrótce

Twój profil? tak, całkowicie własny:)

[kółko] Funkcje tworzące

Kto jest na forum