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 f_binom_t_k a má charakteristiku určenou čísly f_binom_k_l , 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 {vk,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 {sp,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 {sp,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 {sp,n} s posloupnostmi {vp,n}.
Např. pro p=5 dostáváme rozdíl {v5,n}−{s5,n}:

n : 0,1,2,3, 4, 5, 6, 7, 8, 9, 10,...
v5: 0,1,3,7,14,25,42,66,99,143,...
s5: 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ů:

v5(x) = 0+x+3x²+7x³+14x4+25x5+42x6+66x7+ 99x8+...
s5(x) = 0+x+3x²+7x³+14x4+25x5+41x6+63x7+ 92x8+...
─────────────────────────────────────────────────
              1x6+ 3x7+ 7x8+...

Ukazuje se, že: v5(x) = s5(x) + x5∙s5(x) + (?)

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

vp(x) = sp(x) + xp∙sp(x) +x²p∙sp(x)+ +x³p∙sp(x) + ...

vp(x) = sp(x) (1+ xp +x²p +x³p+ ...)

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

vp(x) = sp(x) / (1− xp)

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

  Funkce      Posloupnost
  ───────────────────────────────────────────────
  s3(x)       0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,...
  x3∙s3(x)    0, 1, 2, 3, 4, 5, 6, 7,...
  x6∙s3(x)    0, 1, 2, 3, 4,...
  x9∙s3(x)    0, 1,...
  ───────────────────────────────────────────────
  v3(x)   0, 1, 2, 3, 5, 7, 9, 12, 15, 18, 22,...

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

Příklad rekurence

Podívejme se znovu na posloupnosti ak(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 {rk(n)} jsou definované rekurentně:

Posloupnosti rk(n) mají tvar:

Fn,c= 1/ (1 - xc) (1 - x)n - 1

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

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

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

Pro prvočíselné řády k:

v2(x) =  [1/(1-x)2) - 1/(1-x2)]/2x
v3(x) =  [1/(1-x)3) - 1/(1-x3)]/3x
v5(x) =  [1/(1-x)5) - 1/(1-x5)]/5x
v7(x) =  [1/(1-x)7) - 1/(1-x7)]/7x

Pro složené řády k:

v4(x) = [1/(1-x)4) - 1/(1-x2)2]/4x
v6(x) = [1/(1-x)6) - 1/(1-x2)3 -1/(1-x)3)2 + 1/(1-x6)]/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

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. f_binom_2s1_s /(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) = ────────────────── = 2n−2 ─────────────────
(n−1)!     (n−1)!  

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

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

p(s) = f_binom_2s1_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]:

p3 = 1
p4 = p3 +p3 = 2
p5 = p4 +p3p3 +p4 = 5
p6 = p5 +p3p4 +p4p3 +p5 = 14
p7 = p6 +p3p5 +p4p4 +p5p3 +p6 = 42
p8 = p7 +p3p6 +p4p5 +p5p4 +p6p3 +p7 = 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= f_binom_2p-1_s , s=1,2..p−1, platí:

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

Např.:

f_binom_3_0 mod 2=+1 f_binom_3_1 mod 2=−1

f_binom_5_0 mod 3=+1 f_binom_5_1 mod 3=−1 f_binom_5_2 mod 3=+1

f_binom_9_0 mod 5=+1 f_binom_9_1 mod 5=−1 f_binom_9_3 mod 5=+1 f_binom_9_4 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 xp+yp=zp (pro p>>2) může mít řešení jedině tehdy, když p² | Vp(x,y), kde Vp(x,y) = (x+y)p − xp − yp (viz dále Cauchyho polynomy), tj. pokud platí:

(x+y)p − xp − yp ≡ 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: x4+ 2x³+  3x²+  2x +   1
 7: x5+ 3x4+  5x³+  5x²+  3x +   1
 8: x6+ 3x5+  7x4+  8x³+  7x²+  3x +   1
 9: x7+ 4x6+  9x5+ 14x4+ 14x³+  9x²+  4x + 1
10: x8+ 4x7+ 12x6+ 20x5+ 25x4+ 20x³+ 12x²+4x + 1
11: x9+ 5x8+ 15x7+ 30x6+ 42x5+ 42x4+ 30x³+ 15x²+5x + 1
Rozklad polynomů

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

k

Rozvoj polynomu Vk(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)(x4+2x³+4x²+2x+1) 3∙10=30 2+4=6
9 (x+1)³ (x4+x³+3x²+x+1) 2³∙7 =56 3∙1+4=7
10 (x²+x+1)² (x4+2x³+5x²+2x+1) 3²∙11=99 2∙2+4=8
11 (x+1)(x²+x+1) (x6+3x5+7x4+9x³+7x²+3x+1) 2∙3 ... ∙31=186 1+2 ... +6=9
13 (x+1)(x²+x+1)² (x6+3x5+8x4+11x³+8x²+3x+1) 2∙3² ∙35=630 1+4 ... +6=11
17 (x+1)(x²+x+1)(x12+6x11+26x10+ +75x9+156x8+240x7+277x6…+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 (2k−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 xp+yp = zp (pro pεP, p>2) do tvaru:

(x+y)(x+ry)(x+r²y).....(x+rp−1) = zp

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 xp+yp (jimž se má celý součin rovnat) dostaneme (za předpokladu rp = 1) následující výrazy:

    p  Výraz
    ─────────────────────────────────────────────
    3  (x²y+xy²) (1/r+1+r) = 0
    5  (x4y+2x³y²+2x²y³+xy4) (1/r²+1/r+1+r+r²) = 0
    7  (x6y+3x5y2+5x4y3+5x³y4+3x²y5+xy6) (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−(xk+yk).

R3(x,y) = (x+y)³−x³−y³ = 3xy(x+y)
R5(x,y) = (x+y)5−x5−y5 = 5xy(x+y)(x²+xy+y²)
R7(x,y) = (x+y)7−x7−y7 = 7xy(x+y)(x²+xy+y²)²

Pro lichá k (k>1) jsou Rk(x,y) násobky x,y a (x+y). Pro pεP odpovídají koeficienty Rp(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 Rk(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í Rp (x,y) tvar:

Rp(x,y) = (x+y)p−xp−yp = p∙xy(x+y)(x²+xy+y²)t∙Cp(x,y)

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

Stupeň polynomů Cp (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).

C5(x)  = 1
C7(x)  = 1
C11(x) = x6+3x5+7x4+ 9x³+7x²+3x+1
C13(x) = x6+3x5+8x4+11x³+8x²+3x+1

Složení Cauchyových polynomů

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

C11(x) = (x²+xy+y²)³ +  [xy(x+y)]² = u³+   v²
C13(x) = (x²+xy+y²)³ + 2[xy(x+y)]² = u³+ 2∙v²

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

Sk(x,y) = (x+y)k+(−1)k∙(xk+yk) = (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 Rk(x,1) i Sk(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 Vk(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)²
7 (x+1)(x²+x+1)² vu²
8 (x²+x+1)(x4+2x³+4x²+2x+1) u(v4−2xu)
9 (x+1)³ (x4+x³+3x²+x+1) v³(v4−3xu)
10 (x²+x+1)² (x4+2x³+5x²+2x+1) u²(u²+3x²)
11 (x+1)(x²+x+1) (x6+3x5+7x4+9x³+7x²+3x+1) vu (u³+2x²v²)
13 (x+1)(x²+x+1)² (x6+3x5+8x4+11x³+8x²+3x+1) vu² (u³+3x²v²)
17 (x+1)(x²+x+1)(x12+6x11+26x10+ +75x9+156x8+240x7+277x6…+1) vu (u6+5x²u4+5x³u³+x4v4)

Třídy polynomů

Polynomy Dělitelé 
──────────────────────────
V3(x), V9(x) v
V4(x),
    V10(x) u
V5(x), V11(x), V17(x) vu
V6(x) u2 
V7(x),
    V13(x) vu2
V8(x) u

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

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