Schematic algebra - Self classes

You're reading an English translation of the original Czech page.

Triangle of self classes

The area we are studying here is in the combinatorial theory known as Combinatorics of necklaces.

Introduction

Triangle of self classes is a core of the Pascal’s triangle.

                       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’s triangle can be derived by summing up of members of triangle of self classes (summation goes through divisors of the order k).

Structure of the triangle relates to Wilson’s prime-number theorem.

Algorithm for creation

Because we do not know the triangle's own structure, we begin with its creation from the Pascal triangle:

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); //// all instances
    }
}

We get the custom instance by subtracting nested instances gradually:

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]; //// nested instances
            instances[k, j*t] -= nested;
        }
    }
}

Finally, we will gradually write down all the values 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,

Equations from rows of triangles

Reciprocal equations get from row of Pascal’s triangle, e.g.. x²+2x+1 = 0 have always solution x=−1. And equations (x+1)^k=0 have always k-multiple solution.

Later we will look for regularities in equations from other triangles.

Zeroing of the triangle

In the chapter Stratification we said that "The triangle of its own species nulls the sequence {1,-1,0,1,-1,0, ...}".

If this sentence is true, we have the first important information about the triangle structure: the sum of the selected numbers in each row is equal to the sum of the other numbers in the same row! We begin with the first number 1 on the left and continue with every third number. E.g. according to the 10th line {0, 1, 4, 12, 20, 25, 20, 12, 4, 1, 0} we write: {1,20,12}. For the second set, we select numbers one position on the right: {4,25,4}. What we now say is that 1 + 20 + 12 = 4 + 25 + 4, which is true.

In the case of mod 3 = 0 this rule becomes trivial because there are the same numbers. E.g. for k = 9 is: 1 + 14 + 4 = 4 + 14 + 1.

Here the idea came of whether the remaining numbers we missed in the line, do not give the same sum. But that's not true - certainly not in every line. E.g. line 12 (musical structures) has the sum of the first and second sets: 1 + 40 + 66 + 5 = 112 and the numbers 18 + 75 + 18 = 111 left. The actual number of self classes of music structures is not 3 * 112 = 336 but a unit less, ie, 335.

The common sums of the first two sets form the following sequence:

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

Kociemba, Herbert

Kociemba, Herbert , German teacher of mathematics and physics, the author of the optimal algorithm of Rubik's cube. He has published some important generating functions regarding combinatorics of necklaces.

Sequences on diagonals

Pascal triangle

             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

Pascal‘s triangle

Any row in Pascal’s triangle is sum of numbers from the previous row.

So sequence on certain diagonal is sum (resp. differential) sequence of adjacent diagonal.

Let us mark the diagonals by numbers k=0,1,2,3,4... and their sequences by notation {u_k(n)}.

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

E.g. for k= 3 is u₃(n)= {1,4,10,20,35,...}.

Characteristic of this sequence is [1,3,3,1]:

Particular diagonals contain arithmetic sequences. Their characteristics are rows of Pascal’s triangle. Sequence on k-th diagonal is made from numbers and has characteristic determined by numbers , where tεN is ordinal number of elements on diagonal and L is level (L=0..k).

Diagonals in the triangle of self classes do not make sum or differential sequences. Let us mark {v_k,n} sequences on diagonals of triangle of self classes.

Let us find recurrent form of the first progressions of numbers (for n>0) and look for generating functions:

 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,...

Relation for higher numbers n gets more complicated.

Differential sequences

Let us observe the numbers from differential sequences on diagonals.

 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,

When d is prime the sequences seems to be simpler.

Prime orders

Similar symmetry of characteristics as in Pascal’s triangle exists for diagonals with prime k=p, p>2.
In case p=7, are numbers {0,1,4,12,30,66,132} on both sides of figures made from differences of these numbers:

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

(Do have this property of symmetry all sequences with symmetric characteristic?)

Symmetry of charakteristics

Symmetry of characteristics

Let us mark {s_p,n} sequences derived from characteristics, that are get from rows of triangles of self classes in systems G(2,k), where k=p−1 and pε P, P>2:

    k  p Characteristic         Sequence {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,...}

Let us compare sequences {s_p,n} and sequences {v_p,n}.
E.g. for p=5 we get differences {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, ...

i.e. in form of polynomials:

 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⁸+...

We se, that: v₅(x) = s₅(x) + x⁵∙s₅(x) + (?)

If there is a similar shift also after the next 5 members, it holds:

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+ ...)

In the bracket is sum of geometrical progression, therefore:

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

Let us check this relation for p=3 (where more cycles can be seen):

  Function    Sequence
  ───────────────────────────────────────────────
  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,...

Sequences s₃(x) has its generating function 1/(1−x)². So relation v₃(x) = s₃(x)/(1− x³) match with mentioned generating function v₃(x) = 1/(1− x³)(1−x)².

Example of recurence

Let us again look for sequences a_k(n) on diagonals of triangles of self classes.
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,...

Let sequences {r_k(n)} are defined by recurent rules:

If k < 1 then r_k(n) = 0; If k = 1 then r_k(n) = 1;
Otherwise r_k(n) = r_k-c(n) + z; where z= binom(n-2+k-1,n-2) = binom(k-1,n-2)/li>

Sequences r_k(n) have form:

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

Case c=n.
For n=1,2,3 recurrent {r_k(n)} corresponds to sequences of self classes {a_k(n)}.

For n=1,2..5 we get sequences:

n=1 r_k(1) = r_k-1(1) + [-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)+ [ 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) + [ 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) + [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) + [ 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).

Correct form of generating functions for sequences on diagonals showed Herbert Kociemba (2016).

For prime orders 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

For composed orders 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

We can imagine the emergence of these functions in the simplest way by "nesting" or using Mobius's function.

Relationships can be checked using the following sequences:

Sequences 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

Sequences 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
  ...

Sequences 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
  ...

Sequences 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

Sequences 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

Sequences 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

Sequences 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

Sequences 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

Sequences 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

Central sequences

Backbone of the self classes triangle is made of two sequences:

 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

Sequence {1,1,2,5,14,42,132,429,1430,...}, i.e. sequence of highest numbers in odd rows
Sequence {1,1,3,8,25,75,...}, i.e. sequence of highest numbers in even rows

We will deal mainly with the firsts of them in the next.

Catalan, Eugéne Charles

Catalan, Eugéne Charles , 1814-1894 Belgian mathematician and politician. He dealt with the theory of numbers, especially with infinite fractions.

Catalan‘s sequence

Sequence of numbers {1,1,2,5,14,42,132,429,1430,...} i.e. /(2s+1) came from so called Catalan triangle:

Catalan‘s triangle

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

E.Catalan and Rodrigues (1838) used this sequence while solving problem of partitioning of convex n−gon to triangles with help of not-crossing diagonals.

Number of diagonals in n-gon is maximally (n−3) and diagonals separate n-gon into (n−2) triangles.

Number of possible partitions p(n):

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

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

For s= n−2 (i.e. for s+2 gon) relation gets simpler form [Vilenkin]:

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

This problem is equivalent to task of putting brackets into expression a+b+c+....
E.g. there exist 5 possible variants of not-crossing diagonals in pentagon and the same number of possible bracketing of expression a+b+c+d.

Modified Pascal triangle

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

Catalan sequence appears also in the following modification of Pascal’s triangle. Let us consider arrangement of numbers given by recurrent relation:

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

E.g. 27= 1+2∙6+14, 48 = 6+2∙14+14,...

Spinové stavy

Sequence {1,1,2,5,14,42,132,429,1430,...}, i.e. sequence of highest numbers in odd rows, is [2n+1 | n]/(2n+1).

Catalan sequence appears also in triangle constructed in the following way:

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

.Numbers 1 in the first column.

Members of the first row are sums of numbers from the left.
E.g. 2 = 1 + 1; 5 = 2 + 3; 14 = 5 + 9; 42 = 14 + 28.

Members on the nexts rows are sums of numbers from below and from the left upper diagonal.
E.g. 3 = 2 + 1; 9 = 5 + 4; 28 = 14 + 14.

This schema came from [Fišer], particular numbers express numbers of independent spin states (multiplets).

Inversion of Catalan sequence

Let us mark A(x) power progression corresponding to sequence {1,1,2,5,14,42,132,429,1430,...}.

What is the sequence 1/A(x)? Result is {1,−1,−1,−2,−5,−14,−42,−132,... } i.e. 1− x∙A(x).

From relation 1/A(x) = 1− x∙A(x) follows:

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

Recurrent notation

Recurrent notation of Catalan sequence follows from the following schema [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

Congruence

Wilson‘s levels

We have observed rows of triangles according to given module r in the paragraph Congruence of triangles.

Now let us consider congruence according to prime module p dependent on order of system k (i.e. number of row) by relation p = κ(k).

Let us observe rows of triangles of self classes of systems G(2,k), for k=2p−1, according to module p.

When p is prime then for numbers c= , s=1,2..p−1, it holds:

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

E.g.:

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 . . .

In case k=2p−1 number c denote number of self instances.
Therefore c/(2p−1) is number of self classes.

Triangle of self classes for 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

These numbers mod p always give +1 or −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

E.g. for p=7 we have, i.e. 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 ...

Congruence according p²

Gauss has shown, that Fermat’s equation x^p+y^p=z^p (for p>>2) can have solution only if p² | V_p(x,y), where V_p(x,y) = (x+y)^p − x^p − y^p (see Cauchy’s polynomials below), i.e. if it holds:

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

If it is not trivial case (p|x or p|y) and congruence does not have solution, then 1.case of LF theorem holds.

Polynomials of self classes

Assembling of polynomials

Let us make polynomials from numbers in triangle of self classes:

k polynomials of self classes

 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

Partition of polynomials

Polynomials as products of prime factors:

k	Partition of polynomial V_k(x)	For x=1	Degree
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

Note that:

Value of polynomials from substitution x=1 determine number of classes m(2,k) in system G(2,k).

Values for x=1, kεP make Fermat’s coefficients (2^k−2)/k. Divisibility o these values determine also divisibility of polynomials. E.g. for k=11 is 186=2∙3∙31 and therefore corresponding polynomial is divisible by expression (x+1) (x²+x+1), according to values 2 and 3.

For odd k polynomials are divisible by (x+1). For k= 4,6,7,8,10,11,... polynomials are divisible by (x²+x+1).

Lamé, Gabriel

Lamé, Gabriel [], 1795-1871, French mathematician, as first (1839) proved the LF theorem for k = 7. He inspired further developments in proving the LF theorem.

Transcription of Fermat‘s theorem

General Lame’s prove of the LF theorem is incorrect, but it uses interesting construction. Lame rewrote expression

x^p+y^p = z^p (for pεP, p>2)

into form:

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

where r is complex p-th root of numbers 1.

Let use multiple expressions (x+y)(x+ry)(x+r²y)... from the left and remove terms x^p+y^p (i.e. z^p) we get (from assumption r^p = 1) the following expressions:

    p  Expression
    ─────────────────────────────────────────────
    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

Coefficients of expressions seem to make rows of triangle of self classes:

    p  Coefficients
    ─────────────────────
    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, French mathematician. He dealt with algebra, number theory and analytical methods. In connection with solving problems of algebraic equations, he studied the properties of permutations and elaborated the theory of determinants. Introduced the so-called conjugated substitution system, the predecessor of the group. He work on arithmetisation and on refinement of the terms of mathematical analysis, worked on the theory of complex functions and the theory of differential equations. Also dealt with variance and probability theory.

Cauchy‘s polynomials

In connection to Lame’s prove of the Last Fermat theorem (for k=7), Cauchy and Liouville studied (in years 1839-1841) polynomials of the form (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²)²

For odd k (k>1) are R_k(x,y) multiples of x,y and (x+y). For pεP coefficients R_p(x,y) corresponds to rows of triangle of self instances and are therefore divisible by p. After division by p we get coefficients of polynomials of self classes.

For k≡±1 (mod 6) is R_k(x,y) divisible by expression (x²+xy+y²)^t, where t=1 for k ≡ −1 (mod 6) and t=2 for k ≡ +1 (mod 6). If pεP, p≡±1 (mod 6) have R_p (x,y) form:

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

These relations were studied also by: Cayley (1878), Catalan (1884), Lucas (1888)...). Expressions C_p(x,1) = C_p (x) are called Cauchy’s polynomials .

Degree of polynomials C_p (x) for p=6s±1 is equal to 6(s−1). Polynomials don’t have real roots (there exists relations from their complex roots).

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

Composing of Cauchy polynomials

In connection to problem of the Last Fermat’s theorem polynomials C_p (x) were rewritten with help of expressions 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²

In other cases Waring’s relations are applied or instead R_k(x,y) expressions S_k(x,y) are used:

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

These expressions help to compose recurrent relations of observed polynomials.

Composing of polynomials of self classes

For prime k are polynomials R_k(x,1) i S_k(x,1) equivalent polynomials self classes V(x).

Let us write several polynomials with help of x and expressions v=(x+1) and u=(x²+x+1):

k	Partition of polynomial V_k(x)	Substitution
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⁴)

Classes of polynomials

Divisibility of polynomials S_k(x) depends on their assignment to classes according to module 6.

The same regularity is observed also for polynomials V_k(x).