Obyvatelé /7-poschoďového domu
V domě majícím n poschodí bydlí lidé. Pro každé / = 1, 2,..., n v /-tém poschodí bydlí / manželských párů. Úkolem je zjistit, kolika způsoby lze z těchto obyvatel domu vybrat skupinu dvojic složených z jednoho muže a jedné ženy, mají-li být splněny následující podmínky. Každá taková dvojice je tvořena obyvateli stejného poschodí, ale nesmí to být manželé. Žádné dvě různé dvojice přitom nepochází z téhož poschodí ani ze dvou poschodí ležících bezprostředně pod sebou.
Nechť bn je hledaný počet způsobů, jak takovou skupinu dvojic složenou z obyvatel domu sestavit. Najdeme nejprve rekurentní formuli pro čísla bn. Zřejmě bo = 1 a b\ = 1. Pro n ^ 2 z podmínek úlohy rozlišením možností, zda v dané skupině je či není přítomna některá dvojice pocházející z n-tého poschodí, snadno plyne rekurentní vztah
bn = bn-i + n(n - l)bn-2-
Směřujeme nyní k využití exponenciální generující funkce pro posloupnost čísel {bn}^Lo- To jest uvažujeme mocninnou řadu
A7=0
Uvažujme k tomu navíc ještě mocninnou řadu
oo
3(x) =      . b"...xn+1
n=0
(n + 1)
Pak ovšem mocninná řada Jř(x) je derivací mocninné řady ír(x), čili máme rovnost Jř(x) = ^'(x). Z uvedené rekurentní formule pak plyne
EOn_xn = Ďn-lxn + n\n ~ l)bn-2
/7=2 /7=2 /7=2
OO     , OO
bn-l   n  , ^A7-2 n
a?! ^Wa7-2)"
A7=2 A7=2  v 7
OO , OO
Ebn n+1   i     2 ^" a? --— X ^ +x • > —x
n=l V J n=0
Z toho využitím počátečních podmínek vyplývá
OO     i OO i OO i
V — x" - 1 + V_—_xn+1 + x2- V — x"
A7=0 A7=0 v J n=0
neboli
5R(x) = l + 3(x) + x2-íř(x),
anebo jinak
takže
(l-x2)-3?(x) = 3(x) + l
3ř(x)
■S(x) +
1-x2    v ' 1-x2 Poněvadž 3fř(x) = 9'(x), dostáváme tak lineární diferenciální rovnici 1. řádu
pro neznámou funkci ^(x), přičemž S(0) = 0.
Připomeňme z kurzu matematické analýzy, že obecným řešením lineární diferenciální rovnice 1. řádu
je množina funkcí
/{x) = f{x)y{x)+g{x)
y(x) =    f{x)dx\C + / g(x)e" / ^xc/x
pro všechny reálné konstanty C.
Obecným řešením výše uvedené diferenciální rovnice pro ^(x) je tedy množina
1
funkcí
>J   1 —xz
C +
- f —
dx
l-x:
c/x
v I ' I       '    I I I z'""
Přitom
1
2
1
2
1-x2     l + x     1 - X
takže
1-x-
dx
1
2
1+X
c/x +
1
2
1-x
dx = - ln(l +x)
2K1-*)
1,   l + x     ,     /1 + X
- In-= In
2 1-x
1-x
odkud plyne
/    i   </x /1+X
1-x
Takže obecným řešením shora uvedené diferenciální rovnice pro ^(x) je množina funkcí
l+x 1-x
C +
1-x
1 - x2 V 1 +
dx
X
to jest množina funkcí
X
X
C +
V(1 + X)3VT^
dx
pro všechny reálné konstanty C.
Integrál
, - t_d x
^(í + xyvi^
vystupující v poslední formuli je primitivní funkcí F (x) k zlomku uvedenému v tomto integrálu. Tato primitivní funkce F (x) je určena jednoznačně až na aditivní konstantu. Zvolme tuto konstantu tak, aby primitivní funkce F (x) splňovala podmínku F(0) = 0. Potom vzhledem k tomu, že naše řešení ^(x) uvedené diferenciální rovnice má splňovat podmínku ^(0) = 0, plyne odtud, že Q(x) je tím řešením řečené diferenciální rovnice, které je dáno hodnotou C = 0. Vychází tak, že
vi - x
kde ,
F(x) = / -= c/x   splňuje   F(0) = 0.
Vraťme se k úkolu vypočíst čísla bn pro všechna n ^ 0. Z definice mocninné řady
oo
^(X) = ^--— X
A7=0
{n + iy
plyne, že pro její derivaci Sj'"+1'(x) vzatou v nule vychází
Q("+1'(0) = b„.
Abychom tedy vypočetli čísla bn, je třeba nejprve najít všechny kladné derivace nalezeného řešení Q(x) naší diferenciální rovnice. Toto řešení lze přepsat do tvaru
3(x) = (l + x)*-(l-x)-5-F(x),
kde
F(x) = y (1 -x)-3.(i + x)~idx   splňuje   F(0) = 0. To znamená, že
F/(x) = (l-x)-5-(l + x)-i. Odtud vzhledem k známým vztahům o derivacích součinů funkcí plyne, že
3("+D(x) = ]T (" + ^ [(1 + x)5-(l - x)-i]W-F("+1-fe)(x)
/C=0  ^ '
/c=0 ^ '
+ [(l+x)^.(l-x)-^"+1)-F(x).
Poněvadž F(0) = 0 a my potřebujeme vypočíst 9(n+1)(0), stačí počítat pouze sumu v prvním sčítanci za poslední rovností. Vzhledem k výše uvedenému vyjádření derivace F\x) lze tuto sumu přepsat ve tvaru
É (" 1 ľ) K1 +     "í1 - ^)_l](/<)-[(l - x)"*-(1 + x)-i]<"
/c=0 ^ '
-k)
Výpočtem naznačených derivací součinů funkcí nabývá posléze tato suma tvaru
n
E
k=0
n + 1 k
E (í) [(l + x)^P-[(l-x)-]^
U=o
£
n-k
E
L*=o
n — k g
) [(l-x)-i]^-[(l + x)-i](n
Postupnými úpravami přejde nakonec tato suma do tvaru
n k "-k n+i /n\
a7+1-/C UJ U
fc=0 €=0 g=0
g
[(l + x)Í]<ť>.[(l-x)-*]<k-*>.
[(1 - X)-5]^).[(1 + xj-i]^"*-*)
/7        /C    A7— k
n + 1
a7
/c=0 ^=0 g"=0
a7 + l- /c \£,k - £,g,n - k - g
[(l + x)5]W-[(l-x)-5p-*)
[(l-xJ-^^-Kl + x)-^^-^)
=   y —n + 1       n /)[(1 + x)i]W.[(i_x)-i](<).
e+i+g+j=n [(1 _ x)-5]<*>-[(l + X)"Í]W
Připomeňme, že známe rozvoje funkcí
OO     / i
(i+x)i=x;(|
xp
p=0
oo / i
(l-x)-Í=^(-l)M    5 x«;
<7=0 V 4
(l + x)-!=^
oo    / 3
r
2 »xr
r=0
Hodnoty derivací těchto funkcí naznačených v poslední shora vyčíslené sumě v nule pak vycházejí
[u-*r!]i!!o = (-i)'(?)<•!.
[(1-*)-
(g)
x=0
= (-1)
g
1
2
g
x=0
J
2 , -j
Víme už, že bn = ^""^(O) a že toto číslo je rovno hodnotě již zmíněné shora vyčíslené sumy v nule. S využitím předchozích vztahů tedy dostáváme
3<»+i)(o)=     ]T (-1)
£+i+g+j=n
n + 1
n
n + l-í-i U,i,g,j
1
2
1
2
3 2
7
7
= (n + l)!- ]T
£+i+g+j=n
(-iy+g
n+l-í-
Poněvadž ještě n + 1 — č — i = č + i + g+ j + l—č — i = g+ j + l, nakonec tedy vychází
bn = (n+l)\.   V    i-Ü t
£+i+g+j=n
pro všechna n ^ 0.