Faktoriály a permutace
Faktoriály
FaktoriálSouč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 čísloLimitou 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. |
Funkci faktoriálu je možné aproximovat vztahem J.Stirlinga:
n! ~ √(2πn) (n/e)n
Např. pro n=9 je √(18π) (9/e)9 = 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 posloupnostPosloupnost 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.
Čí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), ...
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 [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 +
p0,
q2 = p2 +
p1 +
p0
|
Např. pro p0=1, p1=−5, p2=6 je q1
= −3 a q2 = +2:
q1 = −5 +
∙1 = −5+2 = −3
q2 = +6 +
∙(−5) +
∙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. |
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 , 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 , [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). |
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)=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)=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)
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. |
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)
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.
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 | 4 | 24 | 288 | 3856 |
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' permutacia 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...