Faktoriály a permutace

Faktoriály

Faktoriál

Součin čísel 1∙2∙3...∙n se nazývá faktoriál a značí se n!. Faktoriál je možné zapsat rekurentně: n! = (n−1)!∙n. Platí: φ(n)|(n−1)!, viz Eulerova funkce.

Dělitelnost faktoriálů

Označme κ(n,d) celočíselný podíl n div d. V rozkladu n! v součin prvočinitelů mohou být jedině prvočinitelé p≤n. V kolikáté mocnině se prvočinitel p v n! vyskytuje určuje vztah (Legendre,1808):

t = κ(n,p)+κ(n,p²)+κ(n,p³)+....

Např. pro 10! a prvočinitel 2 je

t = κ(10,2)+κ(10,4)+κ(n,8) = 10 div 2 +10 div 4 +10 div 8 = 5 +2 +1 = 8

Skutečně 10! = 28 ∙ 14175.

Pro n=a+b+c... platí κ(a+b+c...,p) ≥ κ(a,p) + κ(b,p) + .... a proto také:

a!b!c! ..... | (a+b+c....)!

Podíl (a+b+c....)!/a!b!c!.. udává počet permutací s opakováním a+b+c,... předmětů. Ve tvaru (a+b)!/a!b! určuje počet kombinací k-té třídy z n prvků, kde n=a+b a k=a nebo k=b.

Eulerovo zobecnění

    Obecně když 
        n! = (n-2)!*(n-1)*n, 
    tak 
        n! = (n-2)!*(n-1)*[1+(n-1)]  = (n-2)!*(n-1) + (n-1)!*(n-1).

Rekurentní vztah pro faktoriál inspiroval Eulera k některým dalším zobecněním. V posloupnosti 1,1,2,6,24,120,720, ... platí:

  2 = 1∙( 1+ 1)
  6 = 2∙( 1+ 2)
 24 = 3∙( 2+ 6)
120 = 4∙( 6+ 24)
720 = 5∙(24+120)

Odtud:

n! = (n−1)∙[(n−1)!+(n−2)!]

L.Euler ukázal, že vztahu a(n)=(n−1)[a(n−1)+ a(n−2)] vyhovuje nejen posloupnost faktoriálů (1,2,6,24,120,720,...), ale také posloupnost čísel {0,1,2,9,44,265,...}. Tato čísla se nazývají subfaktoriály.

Gama funkce

Ve snaze počítat faktoriály nejen pro přirozená ale také reálná čísla zavedl L.Euler tzv. funkci gama Γ(x), Γ(x+1) = (x)∙Γ(x). V oboru reálných čísel definoval: n! = (0,1)∫(−ln(x))n dx , který pro celočíselná n dává hodnoty faktoriálu a pro neceločíselná n určité interpolace mezi těmito hodnotami. Vyčíslení Γ²(1/2) dává Wallisův vzorec pro obsah kruhu.
Legendre upravil Eulerův integrál (substitucí x=e−t) na tvar: Γ(x) = ∫tx−1/et dt. V oboru přirozených čísel n je Γ(n+1)= n! = (0,∞) ∫tn/et dt.
Funce Γ umožňuje zjednodušit výpočet některých integrálů (např. integrálů goniometrických funkcí,...).

Subfaktoriály

Uvažujme n předmětů seřazených v určitém pořadí (počet jejich permutací určuje faktoriál). Má se najít počet permutací takových, které nerespektují ani jednu z původních pozic.

Tato úloha je známa ve spojení s klobouky. Má se najít počet možností, kterými si může n-lidí nasadit (při návratu z divadla ..) své klobouky na hlavu tak, aby nikdo neměl svůj původní klobouk.

Řešením je subfaktoriál; např. pro n=3 je faktoriál=6 a subfaktoriál=2:

123 −> 123,132,213,231,312,321

Hodnoty subfaktoriálů je možné počítat také podle vztahu:

s(n) = n! [1/2!−1/3!+1/4!−...+(−1)n/n!

Např. s(5) = 120[1/2−1/6+1/24−1/120] = 44.

Eulerovo číslo

Limitou podílů členů posloupnosti faktoriálů a subfaktoriálů je Eulerovo číslo e:

2/1=2, 6/2=3, 24/9=2.667, 120/44=2.727, 720/265=2.717,...

Více posloupností

Nyní známe 2 posloupnosti, jejichž poměrem je v limitě Eulerovo číslo e. Můžeme k nim přidat nějakou další?
Eulerovo číslo je určené řadou:

e = 1+ 1/1!+ 1/2!+ 1/3!+ 1/4!+ 1/5!+ 1/6!+...

Sčítáním od začátku dostaneme postupně čísla:

1= 1/1, 2=2/1, 2.5=5/2, 2.666=16/6, 2.708=65/24, 2.717= 326/120, ...

čísla (1,2,5,16,65,326,...) nazveme nadfaktoriály.

Dělíme-li posloupnost (1,2,5,16,65,326,...) posloupností faktoriálů (1,1,2,6,24,120,...) dostaneme opět Eulerovo číslo.

Členy jednotlivým posloupností očíslujeme n (podle n!), s tím že řadu n prodloužíme i do záporných hodnot.

    n  −1, 0, 1, 2, 3,  4,  5,    6,    7,    8, ...
    ───────────────────────────────────────────────────────
        1, 1, 2, 5,16, 65, 326, 1957, 13700, 109601, .. nadfaktoriály
    n!     1, 1, 2, 6, 24, 120,  720,  5040,  40320, ... faktoriály
             0, 1, 2,  9,  44,  265,  1854,  14833, ... subfaktoriály
1,2,5,16,65,326,1957,13700,109601
 1,3,11,49,261,1631,11743,...
  2,8,38,212,1370,10112,...
   6,30,174,1158,8742,...
    24,144,984,7584,...
     120,840,6600,...
       720,5760,...
         5040,...

Rozdílové posloupnosti nadfaktoriálů

Posloupnost nadfaktoriálů není aritmetická (existuje nekonečný počet rozdílových posloupností), můžeme ale určit její charakteristiku. Charakteristikou posloupnosti nadfaktoriálů je posloupnost faktoriálů.

Zobecnění

Pokusme se najít další posloupnosti, které by měly podíl příslušných členů blízký Eulerovu číslu e. Protože řada pro nadfaktoriály nevyhovuje vztahu a(n)=(n−1)[a(n−1)+ a(n−2)], musíme hledat jiný výraz.

Nabízí se rekurentní vztah podle následující tabulky:

    nadfaktoriály (r=1)  faktoriály (r=0)   subfaktoriály (r=−1)
    ─────────────────────────────────────────────────────────
     1 = 0∙  1+1         1   = 1             ?
     2 = 1∙  1+1         1   = 1∙  1         0 = ?
     5 = 2∙  2+1         2   = 2∙  1         1 = 2∙0  +1
    16 = 3∙  5+1         6   = 3∙  2         2 = 3∙1  −1
    65 = 4∙ 16+1        24   = 4∙  6         9 = 4∙2  +1
   326 = 5∙ 65+1       120   = 5∙ 24        44 = 5∙9  −1
  1957 = 6∙326+1       720   = 6∙120       265 = 6∙44 +1

Definujme posloupnosti proměnné r takto:

For n>−r:

fr(n)= n∙f(n−1) + rn

For n=−r: fr (n)= 1, for n<−r: fr (n)= 0.

Dostaneme:

r\n│ 0, 1,   2,    3,     4,      5,       6,       7,        8,        9,       10
───┼────────────────────────────────────────────────────────────────────────────────────
−2 │ 0, 0,   0,    1,    20,     68,     472,     3176,     25664,    230464,    2305664
−1 │ 0, 0,   1,    2,     9,     44,     265,     1854,     14833,    133496,    1334961
 0 │ 0, 1,   2,    6,    24,    120,     720,     5040,     40320,    362880,    3628800
 1 │ 1, 2,   5,   16,    65,    326,    1957,    13700,    109601,    986410,    9864101
 2 │ 1, 3,  10,   38,   168,    872,    5296,    37200,    297856,   2681216,   26813184
 3 │ 1, 4,  17,   78,   393,   2208,   13977,   100026,    806769,   7280604,   72865089
 4 │ 1, 5,  26,  142,   824,   5144,   34960,   261104,   2154368,  19651456,  197563136
 5 │ 1, 6,  37,  236,  1569,  10970,   81445,   648240,   5576545,  52142030,  531185925
 6 │ 1, 7,  50,  366,  2760,  21576,  176112,  1512720,  13781376, 134110080, 1401566976
 7 │ 1, 8,  65,  538,  4553,  39572,  355081,  3309110,  32237681, 330492736, 3587402609
 8 │ 1, 9,  82,  758,  7128,  68408,  672592,  6805296,  71219584, 775193984, 8825681664
 9 │ 1,10, 101, 1032, 10689, 112494, 1206405, 13227804, 148869153,1727242866,20759213061
10 │ 1,11, 122, 1366, 15464, 177320, 2063920, 24447440, 295579520,3660215680,46602156800

Podíl členů sousedních posloupností fr+1 a fr (rεN), se zdá v limitě n blížit Eulerovu číslu e.

Např. pro r=2, dostáváme řadu:{ 1/1, 4/3, 17/10, 78/38, 393/168, 2208/872, 13977/5296, ...72865089/26813184,...} tj. { 1.0, 1.33, 1.7, 2.05, 2.34, 2.53, 2.63,...,2.7175,..}

Stirling, James
Stirling, James , 1692-1770, skotský matematik a fyzik. Zabýval se metodami diferenciálního počtu - nekonečnými řadami, součtováním, interpolacemi a kvadraturami.
Approximation of factorials

Funkci faktoriálu je možné aproximovat vztahem J.Stirlinga:

n! ~ √(2πn) (n/e)n

Např. pro n=9 je √(18π) (9/e)&sup9; = 7.5199 x 47811.5 = 359536.9, což se od hodnoty 9! = 362880 liší méně než o 1%.

S rostoucím n přitom roste i relativní přesnost přiblížení:
Např. pro n=18 je √(36π) (18/e)18 = 10.6347 x 599244998013963.7 = 6372804626194309.2, což se od hodnoty 18! = 6402373705728000 liší méně než o 0.5%.

Rekurentní posloupnosti

Moivre, Abraham de
Moivre, Abraham de [moavr], 1667-1754, francouzský matematik působící v Anglii, známý trigonometrickou větou pro n-tou mocninu komplexního čísla. Převedl řešení binomické rovnice xn−1=0 na dělení kruhu s n částmi. Zabýval se také matematickou analýzou, rekurentními řadami a pravděpodobností. Poukázal na podobnost normálního a binomického rozdělení pravděpodobnosti (tzv. Stirlingova formule).

Vztahy, kdy určitý výraz f(n) závisí na některých výrazech f(n−1),f(n−2),.. se nazývají rekurentní.
Pojmenování pochází z francouzského 'récurrent' (vracející se). V rámci teorie rekurentních posloupností je možné studovat obecně určitou skupinu posloupností (včetně aritmetických a geometrických posloupností).
Na rozvoji teorie rekurentních posloupností se podíleli: A.Moivre, D.Bernoulli, L.Euler, P.L.Čebyšev,... [Markuševič]

Rekurentní zápis
aritmetické posloupnosti:
1.řádu: an+1 = an + d
2.řádu: an+2 = 2an+1 − an
3.řádu: an+3 = 3an+2 − 3an−1 + an
Rekurentní zápis
geometrické posloupnosti:
an+1 = an ∙ q

Ne každou posloupnost je možné zapsat rekurentně, rekurentní zápis neexistuje např. pro:

·posloupnost 1,1/2,1/3,....,1/n,

·posloupnost 1,√2,√3,....,√n,

·posloupnost prvočísel.

Fibonacciho posloupnost

Posloupnost určená vztahem a(t)=a(t−2)+a(t−1), tj. každý další člen posloupnosti je součtem dvou předcházejících, se nazývá Fibonacciho posloupnost t 1,2,3,4,5,6,7,8,9,10,11,12, ... a(t) 1,1,2,3,5,8,13,21,34,55,89, ...

Vztah, který předepisuje závislost několika členů posloupnosti se nazývá rekurentní rovnice.

Fibonacciho posloupnost je určena rovnicí: a(t+2)−a(t+1)−a(t) = 0.

Stirlingova čísla prvního druhu

Čísla určená rekurentním vztahem se dvěma parametry:

s(k,m) = s(k−1,m−1)−(k−1)∙s(k−1,m)

  k=2:  −1    1
  k=3:   2   −3    1
  k=4:  −6   11   −6   1
  k=5:  24  −50   35 −10   1
  k=6: −120 274 −225  85 −15  1

se nazývají Stirlingova čísla prvního druhu s(k,m).

Např.:

            s(5,2) = s(4,1)−4∙s(4,2) = −6−4∙(11) = −6+44 =−50
            s(5,3) = s(4,2)−4∙s(4,3) = 11−4∙(−6) = 11+24 = 35

Pro kεP jsou vnitřní koeficienty m=2..(k−1) dělitelné k, např. 3|(−3), 5|(−50), 5|35, 5|(−10), ...

Stirlingova čísla druhého druhu
  k=2: 1  1 
  k=3: 1  3   1
  k=4: 1  7   6   1
  k=5: 1 15  25  10   1
  k=6: 1 31  90  65  15  1
  k=7: 1 63 301 350 140  21  1

Počet možností rozdělení množiny na neprázdné podmnožiny udávají Stirlingova čísla druhého druhu S(k,m).
Např. S(4,2) představuje následujících 7 možností rozkladu 4-prvkové množiny:

[1][2,3,4];  [2][1,3,4];  [3][1,2,4];  [4][1,2,3]
[1,2][3,4];  [1,3][2,4];  [1,4][2,3];

Platí rekurentní vztah:

S(k,m) = m∙S(k−1,m)+S(k−1,m−1)

Např.:

            S(5,2) = 2∙S(4,2)+S(4,1) = 2∙7+1 = 14+1 = 15
            S(5,3) = 3∙S(4,3)+S(4,2) = 3∙6+7 = 18+7 = 25
Taylor Brook
Taylor Brook [tejlor], 1685-1731, anglický matematik a fyzik, známý svým vztahem pro rozvoj funkce v nekonečnou řadu. Vypracoval teorii konečných přírůstků, dnes nazývanou diferenční počet. Věnoval se také perspektivě, definoval fotogrammetrickou úlohu.

Diferenční rovnice

Ke každé rekurentní rovnici existuje přidružená diferenční rovnice (a naopak). Diferenční rovnice mají analogické rysy jako rovnice
diferenciální, kterými se zabývá matematická analýza.

Je-li dána diferenční rovnice, pak jí odpovídající rekurentní rovnici určíme podle vztahů:

a'(t) = a(t+1)−a(t) a''(t) = (a(t+2)−a(t+1))− (a(t+1)−a(t)) = a(t+2)−2a(t+1)+ a(t)

kde na levé straně jsou výrazy diferenční, na pravé rekurentní.

Je-li naopak dána rekurentní rovnice, je postup složitější.


Nechť rekurentní rovnici 2.řádu (k=2) s koeficienty p0,p1,p2: p0∙a(t+2)+p1∙a(t+1)+p2∙a(t) = 0 odpovídá diferenční rovnice s koeficienty 1,q1,q2: a''(t)+q1∙a'(t)+q2∙a(t) = 0 .

Platí:

q1 = p1 + f_binom_k_1 p0, q2 = p2 + f_binom_k-1_1 p1 + f_binom_k_2 p0

Např. pro p0=1, p1=−5, p2=6 je q1 = −3 a q2 = +2: q1 = −5 + f_binom_2_1 ∙1 = −5+2 = −3 q2 = +6 + f_binom_2-1_1 ∙(−5) + f_binom_2_2 ∙1 = +6−5+1 = 2

Proto rekurentní rovnici a(t+2)−5a(t+1)+6a(t) = 0 odpovídá diferenční rovnice a''(t)−3a'(t)+2a(t) = 0

Čebyšev, Pofnutij Lvovič
Čebyšev, Pofnutij Lvovič [Čebyšev], 1821-1894, ruský matematik a vynálezce. Zabýval se teorií čísel, teorií integrace, interpolačními metodami. Zpřesnil původní Eulerovy a Legendreovy odhady hodnot π(r). V teorii pravděpodobnosti zobecnil zákon velkých čísel. Navrhl několik desítek mechanizmů (třídící stroj, pojízdné křeslo,...) Zabýval se také konstrukcí počítacího stroje.
Čebyševovy polynomy

K výpočtu výrazů pro cos(nx) a sin(nx) je možné použít tzv. Čebyševovy polynomy. Uvažujme posloupnost funkcí definovanou rekurentním vztahem:

a(k+1)(z) = 2z∙a(k)(z) − a(k−1)(z)

Substitucí z=cos(x) dostaneme z těchto polynomů výrazy pro cos(k∙x):
 k  a(k)(z)    a(k)(cos x)       cos kx
 ────────────────────────────────────────
 0  1          1                 cos 0x
 1  z          cos(x)            cos 1x
 2  2z2−1      2∙cos2x−1         cos 2x
 3  4z3−3z     4∙cos3x−3cosx     cos 3x
 4  8z4−8z2+1  8∙cos4x−8cos2x+1  cos 4x 

Koeficienty postupně vepíšeme do řádků:

 k  1  z  z2  z3  z4  z5  z6  z7  z8
─────────────────────────────────
 1    1
 2 −1    2
 3   −3     4
 4  1   −8      8
 5    5    −20     16 
 6 −1   18    −48      32 
 7   −7     56   −112     64 
 8  1  −32    160    −256    128
 9    9    120     c1      c2 
10 −1 …

Další členy, např. c1, c2, dostaneme podle: c1= 2∙160 −(−112) = 432, c2 = 2∙(−256) − 64 = −576.

Posloupnosti ve sloupcích jsou alternující. V prvním sloupci je jednotková posloupnost, ve druhém posloupnost lichých čísel. Ve třetím sloupci jsou dvojnásobky druhých mocnin (které známe z výstavby periodické tabulky prvků...).

Na diagonále vpravo jsou čísla 2k−1. Z nich směrem doleva dolů vychází řady čísel, jejichž součet je nula, přičemž součet členů stejné parity je v absolutní hodnotě 3k−1:

Čísla                  ∑(+)=|∑(−)|
─────────────────────────────────
 1   −1                     1   
 2   −3    1                3    
 4   −8    5   −1           9
 8  −20   18   −7  +1      27
16  −48   56  −32   9  −1  81

Rekurence a derivace

Derivujme výrazy (n+1)k−nk (viz G-systémy,počet všech instancí v segmentech s(n,k)):

k  s(n,k)                  s'(n,k)
───────────────────────────────────────────────────────────
1  1                       0
2  2n+1                    2               =  2∙1
3  3n²+3n+1           6n+3            =  3∙(2n+1)
4  4n³+6n²+4n+1 12n²+12n+4  =  4∙(3n²+3n+1)

Platí:

s'(n,k) = k∙s(n,k−1)

Hermitovy polynomy

Hermitovy polynomy, známé z aplikací v kvantové mechanice, jsou postaveny podobným způsobem. Derivace Hk'(x) polynomu stupně k je (2k) násobkem polynomu stupně (k−1).
Např. H2'(x) = (4x²−2)'=8x = 4∙2x= (2∙2)∙H1(x):

k    Hk(x)         Hk'(x)
──────────────────────────────────────────────────────────────
0    1                        0
1    2x                       2
2    4x²−2               8x  
3    8x³−12x             24x²−12 
4   16x4−48x²+12   64x³−96x    
5   32x5−160x³+120x    160x4−480x²+120
6   64x6−480x4+720x²−120     384x5−1920x³+1440x
Laguerre, Nicolas Edmond
Laguerre, Nicolas Edmond , 1834-1886, francouzský matematik. Zabýval se diferenciálními rovnicemi, v řešení jedné z nich figurují tzv.Laguerrovy polynomy.

Platí:

Hk'(x) = 2∙k∙Hk(x)

Polynomy určené vztahem: Pk'(x) = Pk−1(x), resp. Pk'(x) = k∙Pk−1(x) se nazývají Appellovy polynomy. Speciálními případy Appellových polynomů jsou Hermitovy a Laguerrovy polynomy.

Vytvořující funkce

Pokud k členům posloupnosti {a0,a1,..,an,..}
dopíšeme 0-tou, první,... n-tou mocninu
proměnné x dostaneme tzv. mocninou řadu, kde mocniny x vymezují pořadí členů dané posloupnosti.

a0+a1∙x1+.....+an∙xn+...

Výhodou takového zápisu posloupnosti je, že výsledný výraz může jít zapsat jednodušším způsobem, např. jako podíl dvou jednoduchých polynomů.
Např. výraz f(x)=1/(1−x) dává řadu 1+x+x²+..., tj. jednotkovou posloupnost {1,1,...1}. Výrazům, které zjednodušují zápis řady se říká vytvořující funkce . Jaké posloupnosti vzniknou z jiných vytvořujících funkcí?
Pro jednoduchost se omezíme jen na funkce s nejnižšími možnými koeficienty {0,1,2,..}. Podle stupně funkce v čitateli rozdělíme vytvořující funkce do několika skupin. Zaměříme se jen na funkce f(x), které určují posloupnosti, jejichž všechny členy jsou kladné.

Laplace Pierre Simon de
Laplace Pierre Simon de , [laplas] 1749-1827, francouzský matematik, fyzik, astronom a politik známý svým zpracováním nebeské mechaniky. Snažil se vytvořit obecnou teorii mechaniky, která popíše pohyb nebeských těles včetně všech anomálií. Zasáhl do matematické analýzy a teorie pravděpodobnosti, Navrhl intergrální transformaci diferenciálních rovnic a pravděpodobnostní metodu výpočtu, dnes známou pod pojmem "Monte Carlo". Zavedl vytvořující funkce. Je autorem hypotézy o vzniku sluneční soustavy z rotující mlhoviny (Kantova-Laplacova teorie).
Příklady funkcí

1. skupina

 Funkce     Posloupnost             Poznámka
 ────────────────────────────────────────────────────────────────────────────
 1/(1−x)    1, 1, 1,  1,  1......,1               a(t)=1 
 1/(1−2x)   1, 2, 4,  8, 16,.....,2n              a(t)=2t 
 1/(1−3x)   1, 3, 9, 27, 81,.....,3n              a(t)=3t 
 ....
 1/(1−ax)   1,a,a²,a³,a4,.....,an  a(t)=at

2.skupina

Funkce           Posloupnost         Poznámka
──────────────────────────────────────────────
1/(1−x²)    1, 0, 1, 0, 1, 0,  1,…
1/(1−x)²    1, 2, 3, 4, 5, 6,  7,… 
a(t)= f_binom_t_1
1/(1−x−x²)  1, 1, 2, 3, 5, 8, 13,… 
a(t)=a(t−2)+a(t−1)  
           
Fibonacci
1/(1−x−2x²) 1, 1, 3, 5,11,21, 43,...
1/(1−2x−x²) 1, 2, 5,12,29,70,169,...

3.skupina

Funkce               Posloupnost        Poznámka
───────────────────────────────────────────────
1/(1−x³)       1, 0, 0, 1,        0, 0, 1,...
1/(1−x)³   1, 3, 6,10,15,21,28,... a(t)= f_binom_t_2

1/(1−x+x²−x³)  1, 1, 0, 0, 1, 1,  0,... 
1/(1−x−x²+x³)  1, 1, 2, 2, 3, 3, 4,..
1/(1−x−x²−x³)  1, 1, 2, 4, 7,13,24,..
a(t)=a(t−3)+a(t−2)+a(t−1)
Kombinace funkcí

Poznamenáme si ještě některé kombinace funkcí:

Funkce           Posloupnost        Poznámka
───────────────────────────────────────────────────────────
Fa=1/(1−x)/(1+x²)    1, 1, 0, 0, 1, 1, 0, 0, 1,... {a(t)}
Fb=1/(1−x)/(1−x²)  1, 1, 2, 2, 3, 3, 4, 4, 5,... {b(t)}
Sa=1/(1−x)²/(1+x²)   1, 2, 2, 2, 3, 4, 4, 4, 5,... {a'(t)}
Sb=1/(1−x)²/(1−x²)   1, 2, 4, 6, 9,12,16,20,25,... {b'(t)}

Protože Sa=Fa/(1−x) a Sb=Fb/(1−x) jsou posloupnosti Sa,Sb součtovými posloupnostmi Fa,Fb. (Jaké platí další vztahy? Je např. každý člen posloupnosti Sb dělitelný odpovídajícím členem nejen Fb ale i Sa?)

Přechod mezi posloupnostmi

Podívejme se na následující tři posloupností:

Funkce         Posloupnost 
───────────────────────────────────────────────────────
f1=  1/(1−x²)              1, 0, 1, 0, 1, 0, 1,...
f2=  1/(1−x)/(1−x²)        1, 1, 2, 2, 3, 3, 4, 4, 5,...
f3=  1/(1−x)²/(1−x²)  1, 2, 4, 6, 9,12,16,20,25,...

Součtem několika prvních členů posloupnosti jednoho řádku dostaneme vždy určitý člen posloupnosti v nižším řádku. Např. 1+0+1+0+1=3, resp. 1+1+2+2+3=9. Přitom f2=f1/(1−x) a f3=f2/(1−x). Součtové posloupnosti získáváme dělením příslušné vytvořující funkce (1−x), rozdílové posloupnosti násobením (1−x).

Vytvořující funkce

Uvažujme kvadratické polynomy, jejichž koeficienty (se zápornými znaménky) vyčerpávají všechny instance z G(3,2).

Koeficienty  polynom F (mod 3)  Posloupnost pro 1/F  
────────────────────────────────────────────────────────
    00    x²                1,0,0, 0, 0, 0,  0, 0, 0,..
  * 01    x²          −1    1,0,1, 0, 1, 0, 1, 0, 1,..
    10    x²  −x            1,1,1, 1, 1, 1, 1, 1, 1,..
    02    x²          −2    1,0,2, 0, 4, 0, 8, 0, 16,..
    20    x² −2x            1,2,4, 8,16, 32, 64,128, 256,..
    11    x²  −x      −1    1,1,2, 3, 5, 8, 13, 21, 34,..
    21    x² −2x      −1    1,2,5,12,29, 70,169,408, 985,..
  * 12    x²  −x      −2    1,1,3, 5,11, 21, 43, 85, 171,..
  * 22    x² −2x      −2    1,2,6,16,44,120,328,896,2448,..

Každá z funkcí 1/F je vytvořující funkcí pro nějakou posloupnost a nás zajímá, jaké jsou to posloupnosti. Zapíšeme-li každou z posloupností rekurentně, ukáže se vztah ke koeficientům původních polynomů F. Předpokládejme a(0)=0, a(1)=1, n>1.

Koeficienty  Polynom F (mod 3)  Rekurentní zápis pro 1/F  
───────────────────────────────────────────────────────────
    00        x²             a(n) = 0
  * 01        x²     −1      a(n) = a(n−2)
    10        x²     −x      a(n) = a(n−1)
    02        x²     −2      a(n) = 2∙a(n−2)
    20        x² −2x         a(n) = 2∙a(n−1)
    11        x²  −x −1      a(n) = a(n−1) +  a(n−2)
    21        x² −2x −1      a(n) = 2a(n−1) +  a(n−2)
  * 12        x²  −x −2      a(n) = a(n−1) + 2a(n−2)
  * 22        x² −2x −2      a(n) =  2a(n−1) + 2a(n−2)

(Hvězdičkou jsou označeny nerozložitelné polynomy, viz Prosté polynomy.)

Fibonacciho posloupnost

Fibonacci, Leonardo Pissano
Fibonacci, Leonardo Pissano [fibonači], 1170-1230, italský matematik. Cestoval po Egyptě, Sýrii, Řecku, Sicílii a studoval místní matematické techniky. Navázal na práci Al-Chvárizmího. V knize aritmetiky a algebry používal arabských číslic a desítkové číselné soustavy. Do historie matematiky se zapsal "úlohou o králících" ze které vychází posloupnost čísel, v níž každé následující číslo je součtem dvou předcházejících.
Vlastnosti Fibonacciho posloupnosti

Fibonacciho posloupnost má celou řadu vlastností, např. platí:

· a(t) | a(s) jedině v případě, že t | s, proto každá dvě sousední čísla jsou nesoudělná

· mocnina a(n)² = a(n−1)∙a(n+1) + (−1)n−1

· člen a(t+s) = a(t−1)a(s)+ a(t)a(s+1)

· když a(n)εP tak i nεP (nikoli ale naopak).

· poměr hodnot q=a(t+1)/a(t) se postupně blíží k poměru tzv. zlatého řezu Q = (a+b)/a = a/b; Q je řešením rovnice Q²−Q−1 = 0 (s kořeny Q1=−1/Q2)

Odvozené posloupnosti

Pro členy Fibonacciho posloupnosti byl odvozen vztah:

F(k)={[(1+√c)/2]k−[(1−√c)/2]k}/ √c

kde c=5. Nabízí se otázka jak vypadají posloupnosti pro jiná c εN.

Postupným dosazováním a po převodu nad jmenovatele tvaru 2k−1 dostaneme:

k:    1    2    3     4     5      6       7 
──────────────────────────────────────────────────
c=1: 1/1, 2/2, 4/4,  8/8, 16/16,  32/32,  64/64,…
c=2: 1/1, 2/2, 5/4, 12/8, 29/16,  70/32, 169/64,…
c=3: 1/1, 2/2, 6/4, 16/8, 44/16, 120/32, 328/64,…
c=4: 1/1, 2/2, 7/4, 20/8, 61/16, 182/32, 547/64,…     
c=5: 1/1, 2/2, 8/4, 24/8, 80/16, 256/32, 832/64,…

Zajímat nás budou jen posloupnosti v čitatelích:

k:   1  2  3   4  5    6    7
──────────────────────────────────────────────────
c=1: 1, 2, 4,  8, 16,  32,  64,…  a(k)= 2∙a(k−1)
c=2: 1, 2, 5, 12, 29,  70, 169,…  a(k)= 2∙a(k−1)+1∙a(k−2)
c=3: 1, 2, 6, 16, 44, 120, 328,…  a(k)= 2∙a(k−1)+2∙a(k−2)
c=4: 1, 2, 7, 20, 61, 182, 547,…  a(k)= 2∙a(k−1)+3∙a(k−2)   
c=5: 1, 2, 8, 24, 80, 256, 832,…  a(k)= 2∙a(k−1)+4∙a(k−2)     

Pro různá c jsou tyto posloupnosti určené rekurentně vztahem:

a(k) = 2∙a(k−1)+(c−1)∙a(k−2)

Přitom lim(a(k)/a(k−1)) pro k jdoucí do nekonečna je 1+√k.

Permutace rovnic

Permutace

Permutace je zobrazení množiny čísel na tutéž množinu. Např. na množině A={1,2,3} existuje 6 permutací:  p0 =(123/123), p1 =(123/312), p2 =(123/231), p3 =(123/132), p4 =(123/321), p5 =(123/213). Každou permutaci je možné rozepsat do cyklů. Výpis délek cyklů (počínaje délkou 1) se nazývá cyklový typ permutace. Každý cyklus délky 2 je transpozice (inverze). Řád permutace je nejmenším společným násobkem délek samostatných (disjunktních) cyklů.

 pi  u   (123)   Cykly       Délky cyklů Parita
──────────────────────────────────────────
 p0  1   (123)   (1)(2)(3)   1 1 1      S
 p1  2   (312)   (1,3,2)     3          S
 p2  4   (231)   (1,2,3)     3          S
 p3  3   (132)   (1)(2,3)    1 2        L
 p4  6   (321)   (2)(1,3)    1 2        L
 p5  5   (213)   (3)(1,2)    1 2        L 

Parita permutací

Rozložení permutace v součin transpozic je nejednoznačné, např. [1,2,3] = [1,3][2,3] = [1,2][1,3]. Jednu permutaci nelze složit zároveň z lichého počtu nějakých transpozic a sudého počtu jiných transpozic.

Parita permutace je (−1)t, kde t je počet transpozic, které permutaci tvoří. Lichá permutace má paritu −1, sudá paritu 1, Transpozice je lichá permutace. Cyklus délky L má paritu (−1)L−1.

O celkové paritě rozhodují cykly s lichým (L−1), tj. cykly sudé délky. Je-li počet cyklů sudé délky lichý, je permutace lichá, v opačném případě sudá. Složením sudé (S) a liché (L) permutace je permutace lichá, v ostatních případech vznikají sudé permutace:

        S  L          1  −1
     S  S  L      1   1  −1
     L  L  S     −1  −1   1 

Permutační grupy

Permutace stupně n tvoří grupu s n! prvků, tj. tzv. permutační grupu řádu n!. Grupy permutací nejsou obecně komutativní. Byly zavedeny N.H.Abelem a E.Galoisem v souvislosti s řešením rovnic. Prvky permutačních grup jsou permutace (p0,p1,..), viz Permutace. Např. pro n=3:

 pi  u        (123)   Cyklus      Délky cyklů Parita
────────────────────────────────────────────────────
 p0  1   1    (123)   (1)(2)(3)   1 1 1       S
 p1  2   a    (312)   (1,3,2)     3           S
 p2  4   a²   (231)   (1,2,3)     3           S
 p3  3   b    (132)   (1)(2,3)    1 2         L
 p4  6   ba   (321)   (2)(1,3)    1 2         L
 p5  5   ba²  (213)   (3)(1,2)    1 2         L 

Každá grupa je kopií podmnožiny nějaké permutační grupy (Cayleyova věta). Např. grupy zákrytových pohybů, tj. grupy operací symetrie tvoří kopie podmnožin permutačních grup. Takovým grupám se říká symetrické grupy.

Permutace rovnice

Při řešení rovnic vzniklých permutací koeficientů x²−5x+6=0, dostaneme dvě trojice diskriminantů, jednu trojici pro liché, druhou pro sudé permutace:

pi  u (123) Cyklus  Parita  Rovnice   D     Řešení
────────────────────────────────────────────────────────────────
p0  1 (123) (1)(2)(3) S   1x²−5x+6=0    1    2         3
p1  2 (312) (1,3,2)   S   6x²+1x−5=0  121   −1         5/6
p2  4 (231) (1,2,3)   S  −5x²+6x+1=0   56   −3−√14    −3+√14
p3  3 (132) (1)(2,3)  L   1x²+6x−5=0   56   (3−√14)/5 (3+√14)/5
p4  6 (321) (2)(1,3)  L   6x²−5x+1=0    1    1/2       1/3
p5  5 (213) (3)(1,2)  L  −5x²+1x+6=0  121    −1        6/5 

Stejný diskriminant mají rovnice (podle čísel u):

   u1  u2     D
   ──────────────
   1, 6      1
   2, 5    121
   3, 4     56 

Hodnoty u v párech rovnic se stejným D se doplňují:

 u1+u2 = P+1 

kde P je počet permutací.
V párech jsou rovnice vzájemně převrácené, tj. i řešení jsou vzájemně převrácená:

 xu1∙xu2 = 1 

Intervalové řady

Všeintervalové řady

Všeintervalová řada je taková posloupnost tónů, ve které je každý hudební interval i tón (v rámci oktávy) zastoupen právě jednou.
Např. tzv. řada Mallalieu [C,Db,E,D,A,F,B,Eb,Ab,Bb,G,F#] zahrnuje intervaly 1,3,10,7,8,6,4,5,2,9,11,(6).
Interval   mezi posledním tónem F# a prvním C  je  6 (=triton, tj. 6 půltónů) - zde se opakování intervalu toleruje.
Obecně čísla 1,2,...k-1 mají součet S(k) =k (k-1)/2 a počínaje tónem 0 končí na tónu S(k) mod k,
to jest končí na tónu 0 (=počáteční tón) pro lichá n nebo na tónu n/2 (medián hudební soustavy řádu k) pro sudá k,
viz tabulka.
n 1 2 3 4 5 6 7 8 9 10 11 12
S(n) = n (n-1)/2 0 1 3 6 10 15 21 28 36 45 55 66
S(n) mod n 0 1 0 2 0 3 0 4 0 5 0 6

Generování

Všeintervalové řady budeme generovat "hrubou silou" - tedy vytvoříme všechny možné permutace tónů a vyřadíme z nich ty, které nemají požadované vlastnosti.  

 Podle toho:
1/ vygenerujeme permutace (k-1) prvků.
2/ vypočítáme dílčí součty (mod k) pro každou permutaci.
3/ zapisujeme jen takové permutace, ve kterých všechny dílčí součty (mod k) dávají jen  0,..,k-1.

Například pro k=6: permutace (1,4,3,2,5)  tvoří součty {0,1,5,8,10,15}
a {0,1,5,8,10,15} mod 6  = {0,1,5,2,4,3},  tedy tato permutace splňuje podmínky a zapíšeme ji.

Podmínka 3/ (existence všech různých tónů) může být splněna jedině pro sudá k.
Poslední člen řady je pro lichá k vždy kongruentní s 0 (mod k).
Například pro k=5 je
S(5) = 5*4/2=10 dělitelné k=5, což vede k opakování počátečního tónu  a vyloučení řady.

Enumerace

Pro jednotlivá k dostáváme následující počty výsledných řad:
k 2 4 6 8 10 12
Počet 1 2 24  288  3856 
Tyto  počty jsou  v porovnávání s (k-1)!  velmi nízké a nejsou obecně děliteli (k-1)!.
 

Výsledky

Všeintervalové řady pro řád k=2,4,6,8:
k=2
(1): 0,1

k=4
(1,2,3): 0,1,3,2    (3,2,1): 0,3,1,2

k=6
(1,4,3,2,5): 0,1,5,2,4,3    (5,2,3,4,1): 0,5,1,4,2,3
(2,5,3,1,4): 0,2,1,4,5,3    (4,1,3,5,2): 0,4,5,2,1,3

k=8
(1,2,3,4,5,6,7): 0,1,3,6,2,7,5,4    (7,6,5,4,3,2,1): 0,7,5,2,6,1,3,4
(1,5,7,6,4,3,2): 0,1,6,5,3,7,2,4    (7,3,1,2,4,5,6): 0,7,2,3,5,1,6,4
(1,6,3,4,5,2,7): 0,1,7,2,6,3,5,4    (7,2,5,4,3,6,1): 0,7,1,6,2,5,3,4
(1,6,4,3,7,5,2): 0,1,7,3,6,5,2,4    (7,2,4,5,1,3,6): 0,7,1,5,2,3,6,4
(2,1,3,7,4,6,5): 0,2,3,6,5,1,7,4    (6,7,5,1,4,2,3): 0,6,5,2,3,7,1,4
(2,3,4,6,7,5,1): 0,2,5,1,7,6,3,4    (6,5,4,2,1,3,7): 0,6,3,7,1,2,5,4
(2,5,7,3,4,6,1): 0,2,7,6,1,5,3,4    (6,3,1,5,4,2,7): 0,6,1,2,7,3,5,4
(2,7,4,6,3,1,5): 0,2,1,5,3,6,7,4    (6,1,4,2,5,7,3): 0,6,7,3,5,2,1,4
(3,2,1,4,7,6,5): 0,3,5,6,2,1,7,4    (5,6,7,4,1,2,3): 0,5,3,2,6,7,1,4
(3,2,4,1,5,7,6): 0,3,5,1,2,7,6,4    (5,6,4,7,3,1,2): 0,5,3,7,6,1,2,4
(3,6,1,4,7,2,5): 0,3,1,2,6,5,7,4    (5,2,7,4,1,6,3): 0,5,7,6,2,3,1,4
(3,7,5,2,4,1,6): 0,3,2,7,1,5,6,4    (5,1,3,6,4,7,2): 0,5,6,1,7,3,2,4

Opačné permutace

Všechny permutace (pro k > 2) mají odpovídající 'opačnou' permutaci
a také odpovídající 'doplňkovou' permutaci.
Pro k = 8 má například permutace (1,6,4,3,7,5,2) opak  (2,5,7,3,4,6,1) [tj. čísla  v opačném sledu] a
doplněk  (7,2,4,5,1,3,6) [rozdíly od  k].

Je-li daná permutace všintervalovou řadou, pak je také její opačná a doplňková permutace je takovou řadou.
Počet všeintervalových řad
 je proto (pro k > 2) sudé číslo.
 
Někdy je reverzní permutace stejná jako doplňková permutace,  například (1,6,3,4,5,2,7) je tento případ.

Vnořené permutace

Permutace, které tvoří všeintervalové řady mají jistou skrytou strukturu,
například pro k = 8 následující páry permutují čísla 2-6:
  (1,2,3,4,5,6,7)     (3,6,1,4,7,2,5)
  (1,6,3,4,5,2,7)     (3,2,1,4,7,6,5)
Podobně tato dvojice permutuje čísla 1-3 a 5-7
  (1,2,3,4,5,6,7)
  (3,2,1,4,7,6,5)
 
Další takové cykly (1-3,2-6,5-7) se vyskytují v párech:
  (1,5,7,6,4,3,2)     (2,1,3,7,4,6,5)     (1,6,4,3,7,5,2)
  (3,7,5,2,4,1,6)     (6,3,1,5,4,2,7)     (3,2,4,1,5,7,6) .

Primitivní kořeny

Předchozí odstavec připomíná permutaci primitivních kořenů - viz omezené systémy R(n,k,r), např. pro k = 12:

    R (2,12,13): 1 2 4 8 3 6 12 11 9 5 10 7
    R (6,12,13): 1 6 10 8 9 2 12 7 3 5 4 11
    R (7,12,13): 1 7 10 5 9 11 12 6 3 8 4 2
    R(11,12,13): 1 11 4 5 3 7 12 2 9 8 10-6

Tady - celkový počet 1! 1! 2! 2! 2! 4! = 192 řad vzniká z permutací pozorovaných cyklů [1] [12] [3,9] [5,8] [4,10] [2,6,11,7].

Eulerova funkce

Další pozorování (Caleb Morgan):
existuje přesně 12 primitivních kořenů mod 37: 2,5,13,15,17,18,19,20,22,24,32,35.
 
Tyto vztahy držet (mod 37):
  21=2, 511=2, 1323=2, 1525=2, 1731=2, 1817=2,
1935=2, 2013=2, 227=2, 245=2, 3229=2, and 3519=2. 

Vezmeme jen exponenty: 1,11,23,25,31,17,35,13,7,5,29,19.
a jestliže je seřadíme (vzestupně): 1,5,7,11,13,17,19,23,25,29,31,35
zjistíme pořadí: 1(0),11(3),23(7),25(8),31(9),17(5),35(10),13(4),7(2),5(1),29(9),19(6).

Po transformaci do tónů dostaneme všeintervalovou řadu:
[C (0), Eb (3), G (7), Ab (8), Bb (9), F (5), B (10), E (4), D (2), C

Exponenty 1,11,23,25,31,17,35,13,7,5,29,19 v případě mod 37 jsou čísla, která nemají žádného společného dělitele s číslem 36.
Počet těchto čísel určuje Eulerova funkce phi.
Ale výsledkem Eulerovy funkce nemůže být libovolné celé číslo, takže není možné použít tento princip k vytváření všeintervalových řad pro každé k; například není to možné pro k = 14, protože neexistuje žádné číslo s Eulerovou funkcí 14...