Schematická algebra - Vlastní druhy

Trojúhelník vlastních druhů

Oblast, kterou zde studujeme, je v kombinační teorii známa jako Kombinatorika náhrdelníků (Combinatorics of necklaces).

Úvod

Trojúhelník vlastních druhů tvoří jádro Pascalova trojúhelníka.

                       0
                     1   1
                    0  1  0
                  0  1   1  0
                 0  1  1  1  0
               0  1  2  2  1   0
             0  1  2   3  2  1  0
           0  1   3  5   5  3  1  0
         0  1   3  7   8  7   3  1  0
       0  1   4   9 14  14  9  4   1  0
     0  1   4  12 20  25 20  12  4  1  0
   0  1  5  15  30  42  42 30 15  5  1  0
 0  1  5  18  40  66  75 66  40 18  5  1 0 
0  1  6 22  55  99 132 132 99  55 22 6  1  0

Pascalův může být získán součtováním členů trojúhelníka vlastních druhů (součtováním přes dělitele řádu k).

Se strukturou trojúhelníka vlastních druhů souvisí také rozložení prvočísel připomínající Wilsonovu větu.

Algoritmus pro vytvoření

Protože vlastní strukturu trojúhelníka neznáme, vycházíme při jeho vytváření z Pascalova trojúhelníka:

const int size = 22;
long[,] instances = new long[size+1, size+1];
for (int k = 1; k < size; k++)
{
    for (int i = 0; i < k; i++)
    {
        instances[k, i] = MathSupport.Binom(k, i); //// všechny instance
    }
}

Vlastní instance dostaneme postupným odčítáním vnořených instancí:

for (int k = 1; k < size; k++)
{
    for (int q = 1; q < k / 2; q++)
    {
        if (k % q != 0)
        {
            continue;
        }

        var t = k / q;
        for (int j = 0; j < q; j++)
        {
            var nested = instances[q, j]; //// vnořené instance
            instances[k, j*t] -= nested;
        }
    }
}

Nakonec postupně vypíšeme všechny hodnoty instances[k, i]/k:

01: 1, 1, 
02: 0, 1, 0, 
03: 0, 1, 1, 0, 
04: 0, 1, 1, 1, 0, 
05: 0, 1, 2, 2, 1, 0, 
06: 0, 1, 2, 3, 2, 1, 0, 
07: 0, 1, 3, 5, 5, 3, 1, 0, 
08: 0, 1, 3, 7, 8, 7, 3, 1, 0, 
09: 0, 1, 4, 9, 14, 14, 9, 4, 1, 0, 
10: 0, 1, 4, 12, 20, 25, 20, 12, 4, 1, 0, 
11: 0, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 0, 
12: 0, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1, 0, 
13: 0, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1, 0, 
14: 0, 1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1, 0, 
15: 0, 1, 7, 30, 91, 200, 333, 429, 429, 333, 200, 91, 30, 7, 1, 0, 
16: 0, 1, 7, 35, 112, 273, 497, 715, 800, 715, 497, 273, 112, 35, 7, 1, 0, 
17: 0, 1, 8, 40, 140, 364, 728, 1144, 1430, 1430, 1144, 728, 364, 140, 40, 8, 1, 0, 
18: 0, 1, 8, 45, 168, 476, 1026, 1768, 2424, 2700, 2424, 1768, 1026, 476, 168, 45, 8, 1, 0, 
19: 0, 1, 9, 51, 204, 612, 1428, 2652, 3978, 4862, 4862, 3978, 2652, 1428, 612, 204, 51, 9, 1, 0, 
20: 0, 1, 9, 57, 240, 775, 1932, 3876, 6288, 8398, 9225, 8398, 6288, 3876, 1932, 775, 240, 57, 9, 1, 0, 
21: 0, 1, 10, 63, 285, 969, 2583, 5537, 9690, 13995, 16796, 16796, 13995, 9690, 5537, 2583, 969, 285, 63, 10, 1, 0, 
22: 0, 1, 10, 70, 330, 1197, 3384, 7752, 14520, 22610, 29372, 32065, 29372, 22610, 14520, 7752, 3384, 1197, 330, 70, 10, 1, 0,

Rovnice z řádek trojúhelníků

Reciproké rovnice sestavené z řádek Pascalova trojúhelníka, např. x²+2x+1 = 0 dávají vždy řešení x=−1. Přitom rovnice (x+1)^k=0 má řešení k−násobné. Bude nás zajímat, zda je nějaká pravidelnost také v rovnicích jiných trojúhelníků.

Nulování trojúhelníku

V kapitole o Vrstvení struktur jsme řekli, že "Trojúhelník vlastních druhů nuluje posloupnost {1,−1,0,1,−1,0,...}".

Pokud je tato věta pravdivá, máme první důležitou informaci o struktuře trojúhelníka: součet vybraných čísel v každém řádku je roven součtu jiných čísel v témže řádku! První množitu čísel začneme vlevo číslem 1 a pokračujeme každým 3-tím číslem. Např. podle 10-tého řádku {0, 1, 4, 12, 20, 25, 20, 12, 4, 1, 0} píšeme: {1,20,12}. Za druhou množinou vybereme podobně čísla o jednu pozici vpravo: {4,25,4}. To co nyní tvrdíme je, že 1+20+12 = 4+25+4, což skutečně platí.

V případě k mod 3 = 0 se toto pravidlo stává triviální, protože jde o stejná čísla. Např. pro k=9 je: 1+14+4 = 4+14+1.

Zde se vnucuje myšlenka, zda také zbývající čísla, která jsme v řádku vynechali, nedávají stejný součet. To ale pravda není - určitě ne v některých řádcích. Např. v řádku 12 (hudební struktury) je součet první i druhé množiny: 1+40+66+5 = 112 a zbyla čísla 18+75+18 = 111. Skutečně počet vlastních druhů hudebních struktur není 3*112 = 336 ale o jednotku méně, tj.335.

Společné součty prvních dvou množin vytváří následující posloupnost:

1, 2, 3, 6, 10, 19, 33, 62, 112, 210, 387, 728, 1360, 2570, 4845, 9198, 17459, 33288, 63519, ...

Kociemba, Herbert

Kociemba, Herbert , německý učitel matematiky a fyziky, autor optimálního algoritmu skládání Rubikovy kostky. Publikoval některé důležité vytvořující funkce týkající se Kombinatoriky náhrdelníků.

Posloupnosti na diagonálách

Pascalův trojúhelník

V Pascalově trojúhelníku vzniká každý nový řádek součtem čísel předchozího řádku.

Proto také posloupnost na určité diagonále je součtovou, (resp. rozdílovou) posloupností posloupnosti sousední diagonály.

              1
            1   1
          1   2   1
        1   3   3   1
      1   4   6   4   1
    1   5  10  10   5   1 
  1   6  15  20  15   6   1
1   7  21  35  35  21   7   1

Očíslujme diagonály čísly k=0,1,2,3,4... a posloupnosti označme {uk(n)}.

   1, 4, 10, 20, 35,...
     3, 6, 10, 15,..
       3, 4, 5,...
         1, 1,....

Např. pro k= 3 je u3(n)= {1,4,10,20,35,...}.

Charakteristikou této posloupnosti je [1,3,3,1]:

Jednotlivé diagonály tvoří aritmetické posloupnosti, jejichž charakteristikami jsou řádky Pascalova trojúhelníka. Posloupnost na k-té diagonále sestává z čísel a má charakteristiku určenou čísly , kde tεN udává pořadové číslo prvku na diagonále a L je úroveň (L=0..k).

V trojúhelníku vlastních druhů (na rozdíl od Pascalova trojúhelníka) diagonály netvoří součtové ani rozdílové posloupnosti. Označme {v_k,n} posloupnosti na diagonálách trojúhelníka vlastních druhů.

První tři řady čísel (pro n>0) převedeme na rekurentní tvar a najdeme k nim vytvořující funkce.

 k=1: 0,1,1, 1, 1, 1, 1, 1, 1, 1,...        v1(x) = 1/(1−x)
 k=2: 0,1,1, 2, 2, 3, 3, 4, 4, 5,...        v2(x) = 1/(1−x²)(1−x)
 k=3: 0,1,2, 3, 5, 7, 9,12, 15, 18,...      v3(x) = 1/(1−x³)(1−x)²
 k=4: 0,1,2, 5, 8,14,20,30, 40, 55,...
 k=5: 0,1,3, 7,14,25,42,66, 99,143,...

Pro vyšší čísla n se vztahy komplikují.

Rozdílové posloupnosti

Podívejme se na rozdílové posloupnosti čísel na diagonálách.

 d= 1:   0,1,1,1,1,1,1,...

 d= 2:   0,1,1,2,2,3,3,...
          1,0,1,0,1,0,1,0,

 d= 3:   0,1,2,3,5,7,9,12,15,18,...
          1,1,1,2,2,2,3,3,3,
           0,0,1,0,0,1,0,0,

 d= 4:   0,1,2,5,8,14,20,30,40,55,70,...
          1,1,3,3, 6, 6,10,10,15,15,
           0,2,0, 3, 0, 4, 0, 5, 0

 d= 5:   0,1,3,7,14 ,25,42,66,99,143,200,273,364,...
          1,2,4,7 ,11,17,24,33, 44, 57, 73, 91,
           1,2,3 , 4, 6,7, 9, 11, 13, 16, 18,
            1,1, 1, 2, 1, 2, 2,  2,  3,  2,
             0, 0, 1,-1, 1, 0, 0, 1,  -1,

 d= 6: 0,1,3,9,20,42,75,132,212,333,497,728,...
        1,2,6,11,22,33,57,80,121,164,231,
         1,4,5,11,11,24,23,41, 43, 67,
          3,1,6, 0, 13,-1,18,2, 24
          -2,5,-6,13,-14,19,-20,22,
            7,-11,19,-27,33,-39,42, ...

 d= 7: 0,1,4,12,30,66,132 , 245,429,715,1144,...
        1,3,8,18,36,66 , 113,184,286,429,
         2,5,10,18,30 , 47,71,102,143,
          3,5,8,12 , 17, 24, 31, 41,
           2,3,4 , 5,  7,  7,  10,
            1 , 1 , 1, 2,  0,  3,
             0 , 0, 1, -2, 3,

Posloupnosti se zdají být jednodušší v případě, že d je prvočíslo.

Prvočíselné řády

Pro diagonály s prvočíselným k=p, p>2 existuje podobná symetrie charakteristik jako v Pascalově trojúhelníku.
V případě p=7, jsou čísla {0,1,4,12,30,66,132} na obou stranách obrazce tvořeného rozdíly těchto čísel:

n= 1 :  0                n= 7 : 0 ,1, 2, 3, 2, 1, 0
                                  1, 3, 5, 5, 3, 1
n= 2 :  0,1                        4, 8,10, 8, 4
         1                          12,18,18,12
                                     30,36,30
n= 3 :  0,1,0                          66,66
         1,1                            132
          2
n= 5 :  0,1,1,1,0
         1,2,2,1
          3,4,3
           7,7
           14

(Mají tuto vlastnost symetrie všechny posloupnosti se symetrickou charakteristikou?)

Symetrie charakteristik

Označme {s_p,n} posloupnosti, jejichž charakteristikami jsou řádky trojúhelníku vlastních druhů systémů G(2,k), kde k=p−1 a pε P, P>2:

    k  p Charakteristika        Posloupnost {s_p,n}
   ──────────────────────────────────────────────────────────
    2  3 [0,1,0]                {0,1,2, 3, 4, 5, 6, 7, 8, 9, 10}
    4  5 [0,1,1,1,0]            {0,1,3, 7,14,25, 41, 63, 92,129, 175}
    6  7 [0,1,2,3,2,1,0]        {0,1,4,12,30,66,132,245,428,711,1132}
   10 11 [0,1,4,12,20,25,..]    {0,1,...}

Porovnejme tyto posloupnosti {s_p,n} s posloupnostmi {v_p,n}.
Např. pro p=5 dostáváme rozdíl {v_5,n}−{s_5,n}:

n: 0,1,2,3, 4, 5, 6, 7, 8, 9, 10,...
v₅: 0,1,3,7,14,25,42,66,99,143,...
s₅: 0,1,3,7,14,25,41,63,92,129,175, ...
───────────────────────────────────────────────
0,0,0,0, 0, 0, 1, 3, 7, 14, ...

tj. ve tvaru polynomů:

v₅(x) = 0+x+3x²+7x³+14x⁴+25x⁵+42x⁶+66x⁷+ 99x⁸+...
s₅(x) = 0+x+3x²+7x³+14x⁴+25x⁵+41x⁶+63x⁷+ 92x⁸+...
─────────────────────────────────────────────────
            1x⁶+ 3x⁷+ 7x⁸+...

Ukazuje se, že: v₅(x) = s₅(x) + x⁵∙s₅(x) + (?)

Pokud obdobný posun nastane i po dalších 5-ti členech, bude platit:

v_p(x) = s_p(x) + x^p∙s_p(x) +x²p∙s_p(x)+ +x³p∙s_p(x) + ...

v_p(x) = s_p(x) (1+ x^p +x²p +x³p+ ...)

V závorce je součet geometrické posloupnosti, proto:

v_p(x) = s_p(x) / (1− x^p)

Ověříme tento vztah ještě pro p=3 (kde je k dispozici více "cyklů"):

  Funkce      Posloupnost
  ───────────────────────────────────────────────
  s₃(x)      0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,...
  x³∙s₃(x)    0, 1, 2, 3, 4, 5, 6, 7,...
  x⁶∙s₃(x)    0, 1, 2, 3, 4,...
  x⁹∙s₃(x)    0, 1,...
  ───────────────────────────────────────────────
  v3(x)   0, 1, 2, 3, 5, 7, 9, 12, 15, 18, 22,...

Posloupnosti s₃(x) odpovídá vytvořující funkce 1/(1−x)². Vztah v₃(x) = s₃(x)/(1− x³) proto souhlasí s již uvedenou vytvořující funkcí v₃(x) = 1/(1− x³)(1−x)².

Příklad rekurence

Podívejme se znovu na posloupnosti a_k(n) na diagonálách trojúhelníků vlastních druhů.
n=1: 0,1,1, 1, 1, 1, 1, 1, 1, 1,...
n=2: 0,1,1, 2, 2, 3, 3, 4, 4, 5,...
n=3: 0,1,2, 3, 5, 7, 9,12, 15, 18,...
n=4: 0,1,2, 5, 8,14,20,30, 40, 55,...
n=5: 0,1,3, 7,14,25,42,66, 99,143,...

Nechť posloupnosti {r_k(n)} jsou definované rekurentně:

Když k < 1 tak r_k(n) = 0;
Kdyľ k = 1 tak r_k(n) = 1;
Jinak r_k(n) = r_k-c(n) + z; kde z= binom(n-2+k-1,n-2) = binom(k-1,n-2)

Posloupnosti r_k(n) mají tvar:

F_n,c= 1/ (1 - x^c) (1 - x)^{n - 1}

Případ c=n.
Pro n=1,2,3 odpovídají rekurentní {r_k(n)} posloupnostem vlastních druhů {a_k(n)}.

Pro n=1,2..5 dostáváme posloupnosti:

n=1 r_k(1) = r_k-1(1) + binom[-2+k, -1] = r_k-1 + 0 a(0)=1;
F_1,1= 1/ (1-x) = 1 + 1x¹+ 1x²+ 1x³+ 1x⁴+ 1x⁵+ 1x⁶+... i.e. { r_k(1)} = { 0,1,1,1,1,1,1,1,1,1...}
n=2 r_k(2)= r_k-2(2)+ binom[ k-1, 0] = r_k-2+ 1 a(1)=1 /(1-x);
F_2,2=1/ [(1-x²) (1-x)] = 1 + 1x¹+ 2x²+ 2x³+ 3x⁴+ 3x⁵+... i.e. { r_k(2)} = { 0,1,1,2,2,3,3,4,4,5...}
n=3 r_k(3)= r_k-3(3) + binom[ k, 1] = r_k-3 + k a(k)=1 /(1-x)²;
F_3,3=1/[(1-x³) (1-x)²] = 1 + 2x¹+ 3x²+ 5x³+ 7x⁴+ 9x⁵+ ... i.e. { r_k(3)} = { 0,1,2,3,5,7,9,12,15,18,...}
n=4 r_k(4) = r_k-4(4) + binom[k+1, 2] = r_k-4+ k (k+1) / 2 a(k(k+1)/2)=1 /(1-x)³;
F_4,4= 1/ [(1-x⁴) (1-x)³] = 1 + 3x¹+ 6x²+ 10x³+ 16x⁴+ 24x⁵+ ... i.e. { r_k(4)} = { 0,1,3,6,10,16,24,34,46,61,...}
n=5 r_k(5) = r_k-5(5) + binom[ k+2, 3] = r_k-5+ k (k+1)(k+2)/6 a(k (k+1)(k+2)/6)=1/(1-x)⁴
F_5,5= 1/ [(1-x⁵) (1-x)⁴] = 1 + 4x¹+ 10x²+ 20x³+ 35x⁴+ ... i.e. { r_k(5)} = { 0,1,4,10,20,35,57,88,130...}

where a(z)= F_n,c(x)-x^cF_n,c(x).

Správný tvar vytvořujících funkcí pro posloupnosti na diagonálách ukázal Herbert Kociemba (2016).

Pro prvočíselné řády k:

v₂(x) =  [1/(1-x)²) - 1/(1-x²)]/2x
v₃(x) =  [1/(1-x)³) - 1/(1-x³)]/3x
v₅(x) =  [1/(1-x)⁵) - 1/(1-x⁵)]/5x
v₇(x) =  [1/(1-x)⁷) - 1/(1-x⁷)]/7x

Pro složené řády k:

v₄(x) = [1/(1-x)⁴) - 1/(1-x²)²]/4x
v₆(x) = [1/(1-x)⁶) - 1/(1-x²)³ -1/(1-x)³)² + 1/(1-x⁶)]/6x

Vznik těchto funkcí si můžeme představit nejjednodušeji pomocí "vnořování", nebo pomocí Mobiovy funkce.

Vztahy je možné zkontrolovat s pomocí následujících posloupností:

Posloupnosti 1/(1-x)^n

 (1)/ 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1            
 (2)/ 1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,           
 (3)/ 1,  3,  6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210,    
 (4)/ 1,  4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, 1140, 1330, 1540,
 (5)/ 1,  5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315
 (6)/ 1,  6, 21, 56, 126, 252, 462, 792, 1287, 2002, 3003, 4368, 6188, 8568, 11628, 15504, 20349
 (7)/ 1,  7, 28, 84, 210, 462, 924, 1716, 3003, 5005, 8008, 12376, 18564, 27132, 38760, 54264, 74613
 (8)/ 1,  8, 36, 120, 330, 792, 1716, 3432, 6435, 11440, 19448, 31824, 50388, 77520, 116280, 170544
 (9)/ 1,  9, 45, 165, 495, 1287, 3003, 6435, 12870, 24310, 43758, 75582, 125970, 203490, 319770
(10)/ 1, 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, 92378, 167960, 293930, 497420      
(11)/ 1, 11, 66, 286, 1001, 3003, 8008, 19448, 43758, 92378, 184756, 352716, 646646, 1144066   
(12)/ 1, 12, 78, 364, 1365, 4368, 12376, 31824, 75582, 167960, 352716, 705432, 1352078, 2496144

Posloupnosti 1/(1-x^2)^n

(1)/ 1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0 
(2)/ 1,  0,  2,  0,  3,  0,  4,  0,  5,  0,  6,  0,  7,  0,  8,  0,  9,  0, 10,  0
(3)/ 1,  0,  3,  0,  6,  0, 10,  0, 15,  0, 21,  0, 28,  0, 36,  0, 45,  0, 55,  0
  ...

Posloupnosti 1/(1-x^3)^n

(1)/ 1,  0,  0,  1,  0,  0,  1,  0,  0,  1,  0,  0,  1,  0,  0,  1,  0,  0,  1,  0 
(2)/ 1,  0,  0,  2,  0,  0,  3,  0,  0,  4,  0,  0,  5,  0,  0,  6,  0,  0,  7,  0 
(3)/ 1,  0,  0,  3,  0,  0,  6,  0,  0, 10,  0,  0, 15,  0,  0, 21,  0,  0, 28,  0
  ...

Posloupnosti 1/(1-x^2) /(1-x)^n

 (1) 1,  1,  2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  9,  9, 10, 10
 (2) 1,  2,  4,  6,  9, 12, 16, 20, 25, 30, 36, 42, 49, 56, 64, 72, 81, 90, 100, 110
 (3) 1,  3,  7, 13, 22, 34, 50, 70, 95, 125, 161, 203, 252, 308, 372, 444, 525, 615, 715, 825
 (4) 1,  4, 11, 24, 46, 80, 130, 200, 295, 420, 581, 784, 1036, 1344, 1716, 2160, 2685, 3300, 4015
 (5) 1,  5, 16, 40, 86, 166, 296, 496, 791, 1211, 1792, 2576, 3612, 4956, 6672, 8832, 11517, 14817
 (6) 1,  6, 22, 62, 148, 314, 610, 1106, 1897, 3108, 4900, 7476, 11088, 16044, 22716, 31548, 43065 
 (7) 1,  7, 29, 91, 239, 553, 1163, 2269, 4166, 7274, 12174, 19650, 30738, 46782, 69498, 101046
 (8) 1,  8, 37, 128, 367, 920, 2083, 4352, 8518, 15792, 27966, 47616, 78354, 125136, 194634
 (9) 1,  9, 46, 174, 541, 1461, 3544, 7896, 16414, 32206, 60172, 107788, 186142, 311278, 505912
(10) 1, 10, 56, 230, 771, 2232, 5776, 13672, 30086, 62292, 122464, 230252, 416394, 727672
(11) 1, 11, 67, 297, 1068, 3300, 9076, 22748, 52834, 115126, 237590, 467842, 884236, 1611908 
(12) 1, 12, 79, 376, 1444, 4744, 13820, 36568, 89402, 204528, 442118, 909960, 1794196, 3406104

Posloupnosti 1/(1-x^3) /(1-x)^n

 (1)/ 1,  1,  1,  2,  2,  2,  3,  3,  3,  4,  4,  4,  5,  5,  5,  6,  6,  6,  7,  7
 (2)/ 1,  2,  3,  5,  7,  9, 12, 15, 18, 22, 26, 30, 35, 40, 45, 51, 57, 63, 70, 77
 (3)/ 1,  3,  6, 11, 18, 27, 39, 54, 72, 94, 120, 150, 185, 225, 270, 321, 378, 441, 511, 588
 (4)/ 1,  4, 10, 21, 39, 66, 105, 159, 231, 325, 445, 595, 780, 1005, 1275, 1596, 1974, 2415, 2926
 (5)/ 1,  5, 15, 36, 75, 141, 246, 405, 636, 961, 1406, 2001, 2781, 3786, 5061, 6657, 8631, 11046
 (6)/ 1,  6, 21, 57, 132, 273, 519, 924, 1560, 2521, 3927, 5928, 8709, 12495, 17556, 24213, 32844
 (7)/ 1,  7, 28, 85, 217, 490, 1009, 1933, 3493, 6014, 9941, 15869, 24578, 37073, 54629, 78842
 (8)/ 1,  8, 36, 121, 338, 828, 1837, 3770, 7263, 13277, 23218, 39087, 63665, 100738, 155367
 (9)/ 1,  9, 45, 166, 504, 1332, 3169, 6939, 14202, 27479, 50697, 89784, 153449, 254187, 409554
(10)/ 1, 10, 55, 221, 725, 2057, 5226, 12165, 26367, 53846, 104543, 194327, 347776, 601963
(11)/ 1, 11, 66, 287, 1012, 3069, 8295, 20460, 46827, 100673, 205216, 399543, 747319, 1349282
(12)/ 1, 12, 78, 365, 1377, 4446, 12741, 33201, 80028, 180701, 385917, 785460, 1532779, 2882061

Posloupnosti 1/(1-x^4) /(1-x)^n

(1)/ 1,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  3,  4,  4,  4,  4,  5,  5,  5,  5
(2)/ 1,  2,  3,  4,  6,  8, 10, 12, 15, 18, 21, 24, 28, 32, 36, 40, 45, 50, 55, 60
(3)/ 1,  3,  6, 10, 16, 24, 34, 46, 61, 79, 100, 124, 152, 184, 220, 260, 305, 355, 410, 470
(4)/ 1,  4, 10, 20, 36, 60, 94, 140, 201, 280, 380, 504, 656, 840, 1060, 1320, 1625, 1980, 2390, 2860
(5)/ 1,  5, 15, 35, 71, 131, 225, 365, 566, 846, 1226, 1730, 2386, 3226, 4286, 5606, 7231, 9211, 11601
(6)/ 1,  6, 21, 56, 127, 258, 483, 848, 1414, 2260, 3486, 5216, 7602, 10828, 15114, 20720, 27951
(7)/ 1,  7, 28, 84, 211, 469, 952, 1800, 3214, 5474, 8960, 14176, 21778, 32606, 47720, 68440, 96391
(8)/ 1,  8, 36, 120, 331, 800, 1752, 3552, 6766, 12240, 21200, 35376, 57154, 89760, 137480, 205920
(9)/ 1,  9, 45, 165, 496, 1296, 3048, 6600, 13366, 25606, 46806, 82182, 139336, 229096, 366576
(10)/ 1, 10, 55, 220, 716, 2012, 5060, 11660, 25026, 50632, 97438, 179620, 318956, 548052, 914628
(11)/ 1, 11, 66, 286, 1002, 3014, 8074, 19734, 44760, 95392, 192830, 372450, 691406, 1239458
(12)/ 1, 12, 78, 364, 1366, 4380, 12454, 32188, 76948, 172340, 365170, 737620, 1429026, 2668484

Posloupnosti 1/(1-x^5) /(1-x)^n

(1)/ 1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  3,  3,  3,  3,  3,  4,  4,  4,  4,  4
(2)/ 1,  2,  3,  4,  5,  7,  9, 11, 13, 15, 18, 21, 24, 27, 30, 34, 38, 42, 46, 50
(3)/ 1,  3,  6, 10, 15, 22, 31, 42, 55, 70, 88, 109, 133, 160, 190, 224, 262, 304, 350, 400
(4)/ 1,  4, 10, 20, 35, 57, 88, 130, 185, 255, 343, 452, 585, 745, 935, 1159, 1421, 1725, 2075, 2475
(5)/ 1,  5, 15, 35, 70, 127, 215, 345, 530, 785, 1128, 1580, 2165, 2910, 3845, 5004, 6425, 8150, 10225
(6)/ 1,  6, 21, 56, 126, 253, 468, 813, 1343, 2128, 3256, 4836, 7001, 9911, 13756, 18760, 25185
(7)/ 1,  7, 28, 84, 210, 463, 931, 1744, 3087, 5215, 8471, 13307, 20308, 30219, 43975, 62735, 87920
(8)/ 1,  8, 36, 120, 330, 793, 1724, 3468, 6555, 11770, 20241, 33548, 53856, 84075, 128050, 190785
(9)/ 1,  9, 45, 165, 495, 1288, 3012, 6480, 13035, 24805, 45046, 78594, 132450, 216525, 344575
(10)/ 1, 10, 55, 220, 715, 2003, 5015, 11495, 24530, 49335, 94381, 172975, 305425, 521950, 866525
(11)/ 1, 11, 66, 286, 1001, 3004, 8019, 19514, 44044, 93379, 187760, 360735, 666160, 1188110
(12)/( 1, 12, 78, 364, 1365, 4369, 12388, 31902, 75946, 169325, 357085, 717820, 1383980, 2572090

Posloupnosti 1/(1-x^6) /(1-x)^n

(1)/ 1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,  3,  3,  3,  3,  3,  3,  4,  4
(2)/ 1,  2,  3,  4,  5,  6,  8, 10, 12, 14, 16, 18, 21, 24, 27, 30, 33, 36, 40, 44
(3)/ 1,  3,  6, 10, 15, 21, 29, 39, 51, 65, 81, 99, 120, 144, 171, 201, 234, 270, 310, 354
(4)/ 1,  4, 10, 20, 35, 56, 85, 124, 175, 240, 321, 420, 540, 684, 855, 1056, 1290, 1560, 1870, 2224
(5)/ 1,  5, 15, 35, 70, 126, 211, 335, 510, 750, 1071, 1491, 2031, 2715, 3570, 4626, 5916, 7476, 9346
(6)/ 1,  6, 21, 56, 126, 252, 463, 798, 1308, 2058, 3129, 4620, 6651, 9366, 12936, 17562, 23478
(7)/ 1,  7, 28, 84, 210, 462, 925, 1723, 3031, 5089, 8218, 12838, 19489, 28855, 41791, 59353, 82831
(8)/ 1,  8, 36, 120, 330, 792, 1717, 3440, 6471, 11560, 19778, 32616, 52105, 80960, 122751, 182104
(9)/ 1,  9, 45, 165, 495, 1287, 3004, 6444, 12915, 24475, 44253, 76869, 128974, 209934, 332685
(10)/ 1, 10, 55, 220, 715, 2002, 5006, 11450, 24365, 48840, 93093, 169962, 298936, 508870
(11)/ 1, 11, 66, 286, 1001, 3003, 8009, 19459, 43824, 92664, 185757, 355719, 654655, 1163525
(12)/ 1, 12, 78, 364, 1365, 4368, 12377, 31836, 75660, 168324, 354081, 709800, 1364455, 2527980

Posloupnosti 1/(1-x^7) /(1-x)^n

(1)/ 1,  1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,  2,  3,  3,  3,  3,  3,  3
(2)/ 1,  2,  3,  4,  5,  6,  7,  9, 11, 13, 15, 17, 19, 21, 24, 27, 30, 33, 36, 39
(3)/ 1,  3,  6, 10, 15, 21, 28, 37, 48, 61, 76, 93, 112, 133, 157, 184, 214, 247, 283, 322
(4)/ 1,  4, 10, 20, 35, 56, 84, 121, 169, 230, 306, 399, 511, 644, 801, 985, 1199, 1446, 1729, 2051
(5)/ 1,  5, 15, 35, 70, 126, 210, 331, 500, 730, 1036, 1435, 1946, 2590, 3391, 4376, 5575, 7021, 8750
(6)/ 1,  6, 21, 56, 126, 252, 462, 793, 1293, 2023, 3059, 4494, 6440, 9030, 12421, 16797, 22372
(7)/ 1,  7, 28, 84, 210, 462, 924, 1717, 3010, 5033, 8092, 12586, 19026, 28056, 40477, 57274, 79646
(8)/ 1,  8, 36, 120, 330, 792, 1716, 3433, 6443, 11476, 19568, 32154, 51180, 79236, 119713, 176987
(9)/ 1,  9, 45, 165, 495, 1287, 3003, 6436, 12879, 24355, 43923, 76077, 127257, 206493, 326206
(10)/ 1, 10, 55, 220, 715, 2002, 5005, 11441, 24320, 48675, 92598, 168675, 295932, 502425, 828631
(11)/ 1, 11, 66, 286, 1001, 3003, 8008, 19449, 43769, 92444, 185042, 353717, 649649, 1152074
(12)/ 1, 12, 78, 364, 1365, 4368, 12376, 31825, 75594, 168038, 353080, 706797, 1356446, 2508520

Centrální posloupnosti

Páteří trojúhelníka vlastních druhů jsou dvě posloupnosti:

 0 [    0] 0
 1 [    2] 1
 2 [    1] 0 1
 3 [    2] 0 1
 4 [    3] 0 1 1
 5 [    6] 0 1 2
 6 [    9] 0 1 2  3
 7 [   18] 0 1 3  5
 8 [   30] 0 1 3  7   8
 9 [   56] 0 1 4  9  14
10 [   99] 0 1 4 12  20  25
11 [  186] 0 1 5 15  30  42
12 [  335] 0 1 5 18  40  66  75
13 [  630] 0 1 6 22  55  99 132

Catalánova posloupnost {1,1,2,5,14,42,132,429,1430,...}, t.j. posloupnost nejvyšších čísel v lichých řádcích
Posloupnost {1,1,3,8,25,75,...}, t.j. posloupnost nejvyšších čísel v sudých řádcích

Dále se budeme zabývat především první z nich.

Catalan, Eugéne

Catalan, Eugéne Charles , 1814-1894, belgický matematik a politik. Zabýval se teorií čísel, zvláště nekonečnými zlomky.

Catalánova posloupnost

Posloupnost čísel {1,1,2,5,14,42,132,429,1430,...} tj. /(2s+1) pochází z tzv. Catalánova trojúhelníka:

Catalánův trojúhelník

Posloupnost objevil E.Catalan (r.1838,spolu s Rodriguesem) při řešení problému rozdělení konvexního n−úhelníku na trojúhelníky pomocí úhlopříček, které se vzájemně neprotínají. Každý n-úhelník má takových úhlopříček maximálně (n−3), přičemž dělí n-úhelník na (n−2) trojúhelníků.

  1 
  1   2 
  1   3   5 
  1   4   9  14
  1   5  14  28  42
  1   6  20  48  90  132

Počet možných rozdělení p(n):

2∙6∙10...∙2(2n−5)   1∙3∙5... ∙(2n−5) 
p(n) = ────────────────── = 2ⁿ⁻² ─────────────────
(n−1)!     (n−1)!

p(n) = / (2n−3)

Pro s= n−2 (tj. pro s+2 úhelník) se vztah ještě zjednoduší [Vilenkin]:

p(s) = /(2s+1)

Stejné výsledky dává úloha požadující najít všechna možná ozávorkování výrazu a+b+c+....
Např. existuje 5 možných umístění dvou neprotínajících se úhlopříček do pětiúhelníka a stejný počet možných ozávorkování výrazu a+b+c+d.

Upravený Pascalův trojúhelník

Posloupnost najdeme také v jedné z úprav Pascalova trojúhelníku. Uvažujme uspořádání čísel určené rekurentním vztahem:

c(n+1,k)= c(n,k−1)+2∙c(n,k)+c(n,k+1):

Např. 27= 1+2∙6+14, 48 = 6+2∙14+14, ...

1 
1  2 
1  4   5 
1  6  14  14 
1  8  27  48  42 
1 10  44 110 165 132

Spinové stavy

Posloupnost {1,1,2,5,14,42,132,429,1430,...}, t.j. posloupnost nejvyšších čísel v lichých řádcích, je [2n+1 | n]/(2n+1).

Tato posloupnost se objevuje také v trojúhelníku konstruovaném následujícím způsobem:

1
1  5
1  4 14
1  3  9  28
1  2  5  14  42

V prvním sloupci jedničky.

Členy v prvním řádku jsou součtem svých sousedů zleva.
Např. 2 = 1 + 1; 5 = 2 + 3; 14 = 5 + 9; 42 = 14 + 28.

Členy na dalších řádcích jsou součty čísel zdola a z levé horní diagonály.
Např. 3 = 2 + 1; 9 = 5 + 4; 28 = 14 + 14.

Toto schéma je převzato z [Fišer], jednotlivá čísla udávají počty nezávislých spinových stavů -multipletů (výše položené řádky odpovídají vyššímu spinu).

Inverze Catalánovy posloupnosti

S Catalánovou posloupností se váže ještě jedna vlastnost. Označme A(x) mocninou řadu odpovídající posloupnosti {1,1,2,5,14,42,132,429,1430,...}. Ptáme se, jak vypadá posloupnost odpovídající podílu 1/A(x)? Takovou posloupností je {1,−1,−1,−2,−5,−14,−42,−132,... } tj. 1− x∙A(x). A ze vztahu 1/A(x) = 1− x∙A(x) plyne:

x∙A²(x)−A(x) +1 = 0

Když rozepíšeme tento vztah po členech, tj. zapíšeme A(x) = a0 + a1.x +a2.x^2 + ... a porovnáme členy se stejnou mocninou x dostaneme jako řešení postupně {a0, a1, a2, ...}, tedy A(x), co6 je právě Catalánova posloupnost.

Rekurentní zápis

Rekurentní zápis Catalánovy posloupnosti plyne z následujícího schematu [Vrba]:

p₃ = 1
p₄ = p₃ +p₃ = 2
p₅ = p₄ +p₃p₃ +p₄ = 5
p₆ = p₅ +p₃p₄ +p₄p₃ +p₅ = 14
p₇ = p₆ +p₃p₅ +p₄p₄ +p₅p₃ +p₆ = 42
p₈ = p₇ +p₃p₆ +p₄p₅ +p₅p₄ +p₆p₃ +p₇ = 132

Kongruence

Wilsonovy úrovně

V kapitole Kongruence trojúhelníků jsme sledovaly řádky trojúhelníků podle pevně daného modulu r. Uvažujme nyní kongruenci podle prvočíselných modulů p závislých na řádu systému k (tj.číslu řádku)vztahem p = κ(k). Zajímat nás budou řádky trojúhelníku vlastních druhů systémů G(2,k), kde k=2p−1, podle modulu p.

Když p je prvočíslo pak pro čísla c= , s=1,2..p−1, platí:

c = ±1 (mod p); c/(2p−1) = ±1 (mod p)

Např.:

mod 2=+1 mod 2=−1

mod 3=+1 mod 3=−1 mod 3=+1

mod 5=+1 mod 5=−1 mod 5=+1 mod 5=−1 . . .

V případě k=2p−1 číslo c udává počet vlastních instancí.
Tedy c/(2p−1) je počet vlastních druhů.

Trojúhelník vlastních druhů pro k =2p−1:

(p=2)    3:  0   1
(p=3)    5:    0   1   2
(p=5)    9:  0   1   4   9  14
(p=7)   13:    0  1  6  22  55  99 132

Tato čísla mod p dávají vždy +1 nebo −1:

(p=2)    3:  0  +1
(p=3)    5:      0  +1  −1
(p=5)    9:  0  +1  −1  −1  −1
(p=7)   13:    0 +1 −1  +1  −1  +1  −1

Např. pro p=7 máme, tj. 2p−1=13:

i:          0     1    2      3     4      5     6
──────────────────────────────────────────────────────
c(i):      0    13    78    286   715   1287  1716 ...
c(i)/13:   0     1     6     22    55     99   132 ...
mod 7:     0    +1    −1     +1    −1     +1    −1 ...

Kongruence podle p²

Gauss ukázal, že Fermatova rovnice x^p+y^p=z^p (pro p>>2) může mít řešení jedině tehdy, když p² | V_p(x,y), kde V_p(x,y) = (x+y)^p − x^p − y^p (viz dále Cauchyho polynomy), tj. pokud platí:

(x+y)^p − x^p − y^p ≡ 0 (mod p²)

Když nejde o triviální případ (p|x nebo p|y) a kongruence nemá řešení, pak platí 1. případ VF věty (viz).

Polynomy vlastních druhů

Sestavení polynomů

Z čísel trojúhelníka vlastních druhů vytvoříme mnohočleny:

k mnohočleny vlastních druhů

 2: 1
 3: x + 1
 4: x²+ 1x +   1
 5: x³+ 2x²+  2x +   1
 6: x⁴+ 2x³+  3x²+  2x +   1
 7: x⁵+ 3x⁴+  5x³+  5x²+  3x +   1
 8: x⁶+ 3x⁵+  7x⁴+  8x³+  7x²+  3x +   1
 9: x⁷+ 4x⁶+  9x⁵+ 14x⁴+ 14x³+  9x²+  4x + 1
10: x⁸+ 4x⁷+ 12x⁶+ 20x⁵+ 25x⁴+ 20x³+ 12x²+4x + 1
11: x⁹+ 5x⁸+ 15x⁷+ 30x⁶+ 42x⁵+ 42x⁴+ 30x³+ 15x²+5x + 1

Rozklad polynomů

Polynomy se pokusíme rozložit v součin prvočinitelů:

k	Rozvoj polynomu V_k(x)	Pro x=1	Stupeň
2	1	1=1	0=0
3	(x+1)	2=2	1=1
4	(x²+x+1)	3=3	2=2
5	(x+1)(x²+x+1)	2∙3=6	1+2=3
6	(x²+x+1)²	3²=9	2∙2=4
7	(x+1)(x²+x+1)²	2∙3²=18	1+2∙2=5
8	(x²+x+1)(x⁴+2x³+4x²+2x+1)	3∙10=30	2+4=6
9	(x+1)³ (x⁴+x³+3x²+x+1)	2³∙7 =56	3∙1+4=7
10	(x²+x+1)² (x⁴+2x³+5x²+2x+1)	3²∙11=99	2∙2+4=8
11	(x+1)(x²+x+1) (x⁶+3x⁵+7x⁴+9x³+7x²+3x+1)	2∙3 ... ∙31=186	1+2 ... +6=9
13	(x+1)(x²+x+1)² (x⁶+3x⁵+8x⁴+11x³+8x²+3x+1)	2∙3² ∙35=630	1+4 ... +6=11
17	(x+1)(x²+x+1)(x¹²+6x¹¹+26x¹⁰+ +75x⁹+156x⁸+240x⁷+277x⁶…+1)	2∙3 ... ∙1285=7710	1+2 ...+12=15

Všimněme si, že:

· Hodnota polynomů po dosazením x=1 udává počet druhů m(2,k) v systému G(2,k).

· Hodnoty pro x=1, kεP tvoří Fermatovy koeficienty (2^k−2)/k. Jejich dělitelnost určuje i dělitelnost polynomů. Např. pro k=11 je 186=2∙3∙31 a proto je odpovídající polynom dělitelný výrazem s hodnotou 2 a 3, tj. (x+1) a (x²+x+1).

· Pro lichá k jsou polynomy dělitelné (x+1).

· Pro k= 4,6,7,8,10,11,... jsou dělitelné (x²+x+1).

Lamé, Gabriel

Lamé, Gabriel [], 1795-1871, francouzský matematik, jako první (r.1839) dokázal VF větu pro k=7. Inspiroval další vývoj v dokazování VF věty.

Přepis Fermatovy věty

Obecný Laméův důkaz VF věty se ukázal být sice nesprávný, používá ale zajímavé konstrukce. Lamé přepsal výraz x^p+y^p = z^p (pro pεP, p>2) do tvaru:

(x+y)(x+ry)(x+r²y).....(x+r^p−1) = z^p

kde r je komplexní p-tá odmocnina z čísla 1.

Násobíme-li výrazy (x+y)(x+ry)(x+r²y)... postupně zleva a vypustíme-li členy x^p+y^p (jimž se má celý součin rovnat) dostaneme (za předpokladu r^p = 1) následující výrazy:

    p  Výraz
    ─────────────────────────────────────────────
    3  (x²y+xy²) (1/r+1+r) = 0
    5  (x⁴y+2x³y²+2x²y³+xy⁴) (1/r²+1/r+1+r+r²) = 0
    7  (x⁶y+3x⁵y2+5x⁴y3+5x³y⁴+3x²y⁵+xy⁶) (1/r³+1/r²+1/r+1+r+r²+r³) = 0

Koeficienty výrazů se zdají tvořit řádky příslušející trojúhelníku vlastních druhů:

    p  Koeficienty
    ─────────────────────
    3  1  1 
    5  1  2  2  1
    7  1  3  5  5  3  1

Cauchy, Augustin Louis

Cauchy, Augustin Louis , [koši] 1789-1857, francouzský matematik. Zabýval se algebrou, teorií čísel a analytickými metodami. V souvislosti s problematikou řešitelnosti algebraických rovnic studoval vlastnosti permutací a rozpracoval teorii determinantů. Zavedl tzv. konjugované soustavy substitucí, předchůdce grup. Zasloužil se o aritmetizaci a zpřesnění pojmů matematické analýzy, pracoval na teorii komplexních funkcí a teorii diferenciálních rovnic. Věnoval se také variačnímu počtu a teorii pravděpodobnosti.

Cauchyovy polynomy

V souvislosti s Laméovým důkazem velké Fermatovy věty (pro k=7), studovali Cauchy a Liouville (v letech 1839-1841) polynomy tvaru (x+y)^k−(x^k+y^k).

R₃(x,y) = (x+y)³−x³−y³ = 3xy(x+y)
R₅(x,y) = (x+y)⁵−x⁵−y⁵ = 5xy(x+y)(x²+xy+y²)
R₇(x,y) = (x+y)⁷−x⁷−y⁷ = 7xy(x+y)(x²+xy+y²)²

Pro lichá k (k>1) jsou R_k(x,y) násobky x,y a (x+y). Pro pεP odpovídají koeficienty R_p(x,y) řádkům trojúhelníka vlastních instancí a jsou tedy dělitelné p; po vydělení p jsou rovny koeficientům polynomů vlastních druhů.

Pro k≡±1 (mod 6) je R_k(x,y) dělitelné výrazem (x²+xy+y²)^t, přičemž t=1 pro k ≡ −1 (mod 6) a t=2 pro k ≡ +1 (mod 6). Když pεP, p≡±1 (mod 6) mají R_p (x,y) tvar:

R_p(x,y) = (x+y)^p−x^p−y^p = p∙xy(x+y)(x²+xy+y²)^t∙C_p(x,y)

Tímto vztahem se dále zabývali: Cayley (1878), Catalan (1884), Lucas (1888)...). Výrazy C_p(x,1) se označují zkráceně C_p (x) a nazývají se Cauchyovy polynomy .

Stupeň polynomů C_p (x) pro p=6s±1 je roven 6(s−1). polynomy nemají reálné kořeny (existují vztahy určující jejich komplexní kořeny).

C₅(x)  = 1
C₇(x)  = 1
C₁₁(x) = x⁶+3x⁵+7x⁴+ 9x³+7x²+3x+1
C₁₃(x) = x⁶+3x⁵+8x⁴+11x³+8x²+3x+1

Složení Cauchyových polynomů

V souvislosti s problémem velké Fermatovy věty se objevily pokusy zapisovat polynomy C_p (x) jen pomocí výrazů v=xy(x+y) a u=(x²+xy+y²) [Ribenboim]:

C₁₁(x) = (x²+xy+y²)³ +  [xy(x+y)]² = u³+   v²
C₁₃(x) = (x²+xy+y²)³ + 2[xy(x+y)]² = u³+ 2∙v²

K rozpisu se využívá Waringových vztahů (viz.). Místo R_k(x,y) se také zavádí výrazy S_k(x,y):

S_k(x,y) = (x+y)^k+(−1)^k∙(x^k+y^k) = (x+y)^k+(−x)^k+(−y)^k

Tyto výrazy pak umožňují sestavení rekurentních vztahů pro rozpis.

Složení polynomů vlastních druhů

Pro prvočíselná k jsou polynomy R_k(x,1) i S_k(x,1) ekvivalentní polynomům vlastních druhů V(x). Rozepišme několik těchto polynomů pomocí x a výrazů v=(x+1) a u=(x²+x+1):

k	Rozvoj polynomu V_k(x)	Substituce
2	1	1
3	(x+1)	v
4	(x²+x+1)	u
5	(x+1)(x²+x+1)	vu
6	(x²+x+1)²	u²
7	(x+1)(x²+x+1)²	vu²
8	(x²+x+1)(x⁴+2x³+4x²+2x+1)	u(v⁴−2xu)
9	(x+1)³ (x⁴+x³+3x²+x+1)	v³(v⁴−3xu)
10	(x²+x+1)² (x⁴+2x³+5x²+2x+1)	u²(u²+3x²)
11	(x+1)(x²+x+1) (x⁶+3x⁵+7x⁴+9x³+7x²+3x+1)	vu (u³+2x²v²)
13	(x+1)(x²+x+1)² (x⁶+3x⁵+8x⁴+11x³+8x²+3x+1)	vu² (u³+3x²v²)
17	(x+1)(x²+x+1)(x¹²+6x¹¹+26x¹⁰+ +75x⁹+156x⁸+240x⁷+277x⁶…+1)	vu (u⁶+5x²u⁴+5x³u³+x⁴v⁴)

Třídy polynomů

Dělitelnost polynomů S_k(x) závisí jen na jejich příslušnosti k třídám podle modulu 6.

Stejnou zákonitost pozorujeme i u polynomů V_k(x).