Factorials and permutations

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

Faktorials

Faktorial

Product numbers 1∙2∙3...∙n is called factorial and denoted n!. Factorial is possible to write recursively: n! = (n−1)!∙n. It applies: φ(n)|(n−1)!, see Euler function.

Divisibility of factorials

Denote κ(n,d) integer share n div d. In the breakdown of n! to product of prime factors can only be prime factors p≤n. The prime factor p occurs in n! at the power given by relation (Legendre,1808):

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

E.g. for 10! and prime factor 2 is

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

Really 10! = 28 ∙ 14175.

For n=a+b+c... platí κ(a+b+c...,p) ≥ κ(a,p) + κ(b,p) + .... a proto also:

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

Result of a division (a+b+c....)!/a!b!c!.. gives the number of permutations with repetition of a+b+c,... items. In the form (a+b)!/a!b! it determine number ofcombinations k-th class of n elements, where n=a+b and k=a or k=b.

Euler generalization

    Generally if 
        n! = (n-2)!*(n-1)*n, 
    then
        n! = (n-2)!*(n-1)*[1+(n-1)]  = (n-2)!*(n-1) + (n-1)!*(n-1).
Recurrent relation for factorial inspired Euler to some other generalizations. In sequences 1,1,2,6,24,120,720, ... it applies:

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

Hence:

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

L.Euler showed that the relation a(n)=(n−1)[a(n−1)+ a(n−2)] is satisfied not only by sequence of faktorials (1,2,6,24,120,720,...), but also by sequence of numbers {0,1,2,9,44,265,...}. These numbers are called subfaktorials.

Gama function

In an attempt to calculate factorials not only for natural but also for real numbers, L.Euler introduced so called gamma function Γ(x), Γ(x+1) = (x)∙Γ(x). In the field of real numbers he defined: n! = (0,1)∫(−ln(x))n dx , which for integer n gives values of factorial and for non-integer n certain interpolations between these values. Enumeration Γ²(1/2) gives the Wallis' formula for area of a circle.
Legendre has modified the Euler integral (by substitution x=e−t) to form: Γ(x) = ∫tx−1/et dt. In the field of natural numbers n is Γ(n+1)= n! = (0,∞) ∫tn/et dt.
Function Γ allows to simplify the calculation of certain integrals (e.g integrals of goniometric function ...).

Super-factorials

Let us consider n objects arranged in a certain order (number of their permutations is determined by factorial). We have to find a number of such permutations that does not respect either of the original positions.

This problem is known in connection with hats. The aim is to find a number of possibilities by which n-people can put on (when returning from the theater ..) their hats on their heads so, that nobody should have his original hat.

The solution is subfactorial; e.g. for n=3 is factorial=6 and subfactorial=2:

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

Values of subfactorials can be counted also according to relation:

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

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

The Euler's number

Limit of ratios between members of sequences of factorials and subfactorials is Euler number e:

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

More sequences

Now we know 2 sequences, with the ratio in the limit equal to Euler's number e. Can we add to them some next seuence?
Euler number is derermined by serie:

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

By summing it from the beginning we get successively numbers:

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

numbers (1,2,5,16,65,326,...) are called super-factorials.

If we divide sequence (1,2,5,16,65,326,...) by sequence of faktorials (1,1,2,6,24,120,...) we again get the Euler number.

Members of individual sequences are numbered n (according to n!), with the series of n extended into negative territory.

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

Differential sequences of super-factorials

Sequence of super-factorials is not aritmetic (there is an infinite number of differential sequences), but we can determine its characteristics. The characteristic of sequence of super-factorials is sequence of factorials.

Generalization

Let us try to find other sequences that should have the share of respective members close to Euler number e. Because the series for super-factorials does not satisfy the relation a(n) = (n-1) [a(n-1) + a(n-2)], we must look for an another expression.

The recurrent relation according to next table offers:

    super-factorials (r=1) factorials (r=0) sub-factorials (r=−1)
    ─────────────────────────────────────────────────────────
     1 = 0∙  1+1         1   = 1             ?
     2 = 1∙  1+1         1   = 1∙  1         0 = ?
     5 = 2∙  2+1         2   = 2∙  1         1 = 2∙0  +1
    16 = 3∙  5+1         6   = 3∙  2         2 = 3∙1  −1
    65 = 4∙ 16+1        24   = 4∙  6         9 = 4∙2  +1
   326 = 5∙ 65+1       120   = 5∙ 24        44 = 5∙9  −1
  1957 = 6∙326+1       720   = 6∙120       265 = 6∙44 +1

Let's define sequences of the variable r:

For n>−r:

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

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

We get:

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

Proportion of members of neighboring sequences fr+1 and fr (rεN), appears to approach in the limit of n s to the Euler number e.

E.g. for r=2, we get series:{ 1/1, 4/3, 17/10, 78/38, 393/168, 2208/872, 13977/5296, ...72865089/26813184,...} i.e. { 1.0, 1.33, 1.7, 2.05, 2.34, 2.53, 2.63,...,2.7175,..}

Stirling, James
Stirling, James , 1692-1770, Scottish mathematician and physicist. He dealt with the methods of differential calculus - infinite rows, summarization, interpolation and with quadratures.
Approximation of faktorials

The factorial function can be approximated by J.Stirling's relationship:

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

E.g. for n=9 is √(18π) (9/e)&sup9; = 7.5199 x 47811.5 = 359536.9, which differs from 9! = 362880 less than by 1%.

With increasing n also the relative precision of the approximation increases:
E.g. for n=18 is √(36π) (18/e)18 = 10.6347 x 599244998013963.7 = 6372804626194309.2, which differs from 18! = 6402373705728000 less than by 0.5%.

Recurrent sequences

Moivre, Abraham de
Moivre, Abraham de [moavr], 1667-1754, French mathematician working in England, known for trigonometric series of the n-th power of complex numbers. He transfered solution of binomial equation xn−1=0 to n part rings. He deal with mathematical analysis, recurrent series and probability. Pointed out the similarities between normal and binomial probability distribution (ie. the Stirling formula).

Relationships, where a term f(n) depends on some of the expressions f(n-1), f(n-2), .. are called recurrent.
The name comes from the French 'récurrent' (returning). Within the theory of recurrent sequences it is generally possible to study a particular group of sequences (including arithmetic and geometric sequences).
Development of the theory of recurrent sequences was then made by: A.Moivre, D.Bernoulli, L.Euler, P.L.Čebyšev ...

Recurrent notation of aritmetic sequences:
1.řádu: an+1 = an + d
2.řádu: an+2 = 2an+1 − an
3.řádu: an+3 = 3an+2 − 3an−1 + an
Recurrent notation of geometric sequences:
an+1 = an ∙ q

Not every sequence is possible to write recursively, recurrent notation does not exists for e.g.:

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

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

·sequence of primes.

Fibonacci sequence

Sequence identified by relationship a(t) = a(t-2) + a(t-1), i.e. each additional member of the sequence is the sum of the two preceding, is called Fibonacci sequence. t 1,2,3,4,5,6,7,8,9,10,11,12, ... a(t) 1,1,2,3,5,8,13,21,34,55,89, ...

Relationship, which prescribes the dependence of several members of the sequence is called recurrent equation

Fibonacci sequence is determined by the equation: a(t+2)−a(t+1)−a(t) = 0.

Stirling's numbers of the first kind

Numbers identified by recurrent relationship with two parameters:

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

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

are called Stirling's numbers of the first kind s(k,m).

E.g.:

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

For kεP are inner coefficients m=2..(k−1) divisible k, e.g. 3|(−3), 5|(−50), 5|35, 5|(−10), ...

Stirling's numbers of the second kind
k=2: 1  1 
k=3: 1  3   1
k=4: 1  7   6   1
k=5: 1 15  25  10   1
k=6: 1 31  90  65  15  1
k=7: 1 63 301 350 140  21  1

The numbers of distribution possibilities of a given set to non-empty subsets are given by Stirling's numbers of the second kind S(k,m).
E.g. S(4,2) presents these 7 possibilities of decomposition of 4-element set:

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

Recurrent relation applies:

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

E.g.:

S(5,2) = 2∙S(4,2)+S(4,1) = 2∙7+1 = 14+1 = 15 S(5,3) = 3∙S(4,3)+S(4,2) = 3∙6+7 = 18+7 = 25

Taylor Brook
Taylor Brook [tejlor], 1685-1731, English mathematician and physicist known for his formulas regarding development of function to infinite series. He developed a theory of finite increments, today called differential calculus. Also devoted to perspective, defined photogrammetric problem.

Difference equation

For each recurrent equation there exists an associated difference equation (and vice versa). Difference equations have similar characteristics as the differential equations, which are observed in the mathematical analysis.

For given difference equation, we determine corresponding recurrent equation according to relations:

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

where there are difference expressions on the left side and recurrent expressions on the right side.

On the contrary if recurrent equation is given, the procedure is more complicated.


Let recurrent equation of the second order (k=2) with coefficients p0,p1,p2: p0∙a(t+2)+p1∙a(t+1)+p2∙a(t) = 0 corresponds to difference equation with coefficients 1,q1,q2: a''(t)+q1∙a'(t)+q2∙a(t) = 0 .

It applies:

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

E.g. for p0=1, p1=−5, p2=6 is q1 = −3 a q2 = +2: q1 = −5 + f_binom_2_1 ∙1 = −5+2 = −3 q2 = +6 + f_binom_2-1_1 ∙(−5) + f_binom_2_2 ∙1 = +6−5+1 = 2

Therefore recurrent equation a(t+2)−5a(t+1)+6a(t) = 0 corresponds to differential equation a''(t)−3a'(t)+2a(t) = 0

Čebyšev, Pofnutij Lvovič
Čebyšev, Pofnutij Lvovič [Čebyšev], 1821-1894, Russian mathematician and inventor. He was interested in the theory of numbers, theory of integration, interpolation methods. Refines the original Euler and Legendre estimations for π (r). In probability theory, he generalized law of large numbers. He suggested several dozen mechanisms (sorting machine, wheelchair ...) He dealt with the construction of calculating machine.
Chebyshev polynomials

To calculate expressions for cos(nx) and sin(nx) so-called Chebyshev polynomials can be used. Consider a sequence of functions defined by recurrent relation:

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

By substitution z = cos(x) we get from these polynomials expressions for cos(k∙x):
 k  a(k)(z)    a(k)(cos x)       cos kx
 ────────────────────────────────────────
 0  1          1                 cos 0x
 1  z          cos(x)            cos 1x
 2  2z2−1      2∙cos2x−1         cos 2x
 3  4z3−3z     4∙cos3x−3cosx     cos 3x
 4  8z4−8z2+1  8∙cos4x−8cos2x+1  cos 4x 

We will write coefficients successively into rows:

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

We get the other members, e.g. c1, c2, according to: c1= 2∙160 −(−112) = 432, c2 = 2∙(−256) − 64 = −576.

Sequences in columns are alternating. The first column is a unit sequence, the second sequence of odd numbers. In the third column are twice squares (that we know from the construction of periodic table of atom elements ...).

On the diagonal right are numbers 2k−1. Among them, the left downward are sequences of numbers whose sum is zero, wherein the sum of the members of the same parity is in absolute value 3k−1:

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

Recurrences and derivation

Let us derive expressions (n+1)k−nk (see G-systems, number of all instances in segments s(n,k)):

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

It applies:

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

Hermite polynomials

Hermite polynomials, known from applications in quantum mechanics, are constructed in a similar manner. Derivation Hk'(x) of polynomial of degree k is (2k) a multiple of polynomial of degree (k−1).
E.g. H2'(x) = (4x²−2)'=8x = 4∙2x= (2∙2)∙H1(x):

k     Hk(x)           Hk'(x)
────────────────────────────────────────────
0     1                          0
1     2x                         2
2     4x²−2                 8x  
3     8x³−12x               24x²−12 
4     16x4−48x²+12     64x³−96x    
5     32x5−160x³+120x    160x4−480x²+120
6     64x6−480x4+720x²−120    384x5−1920x³+1440x
Laguerre, Nicolas Edmond
Laguerre, Nicolas Edmond , 1834-1886, French mathematician. He dealt with differential equations, in the solution of one of them so called Laguerr's polynomials figure.

It holds:

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

Polynomials determined by relationship: Pk'(x) = Pk−1(x), resp. Pk'(x) = k∙Pk−1(x) are called Appell's polynomials. Special cases of Appell's polynomials are Hermite and Laguerre polynomials.

Generating functions

If we write to the members of the sequences {a0,a1,..,an,..}
0-th, first,... n-th power
of the variable x we get so-called power serie, where the powers of x define the order of members of given sequences.

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

The advantage of such notation of sequences is that the resulting expression can be written in a simpler way, e.g as a proportion of two simple polynomials.
E.g. expression f(x)=1/(1−x) give series 1+x+x²+..., i.e. the unit sequence {1,1,...1}. Expressions that simplify writing of sequences are called generating functions. What sequences arise from other generating functions?
For simplicity we will only pass functions with the lowest possible coefficients {0,1,2, ..}. We will divide generating functions into several groups according to the degree of function in the numerator. And we focus only on functions f(x), which determine the sequences whose members are all positive.

Laplace Pierre Simon de
Laplace Pierre Simon de , [laplas] 1749-1827, French mathematician, physicist, astronomer and politician, known for his treatment on celestial mechanics. He tried to create a general theory of mechanics, which describes the motion of celestial bodies, including all anomalies. Intervened in mathematical analysis and probability theory, suggested integral transformation of differential equations and probabilistic calculation method, now known as the "Monte Carlo". He introduced the generating functions. He is the author of hypothesis about the origin of the solar system from a rotating nebula (Kant-Laplace theory).
Example of functions

1.group

Function     Sequence         Note
──────────────────────────────────────────────
1/(1−x)    1, 1, 1,  1,  1......,1   a(t)=1 
1/(1−2x)   1, 2, 4,  8, 16,.....,2n   a(t)=2t 
1/(1−3x)   1, 3, 9, 27, 81,.....,3n   a(t)=3t 
....
1/(1−ax)   1,a,a²,a³,a4,.....,an  a(t)=at

2.group

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

3.group

Function     Sequence         Note
───────────────────────────────────────────────
1/(1−x³)       1, 0, 0, 1,  0, 0, 1,...
1/(1−x)³   1, 3, 6,10,15,21,28,... a(t)= f_binom_t_2 
1/(1−x+x²−x³)  1, 1, 0, 0, 1, 1, 0,... 
1/(1−x−x²+x³)  1, 1, 2, 2, 3, 3, 4,..
1/(1−x−x²−x³)  1, 1, 2, 4, 7,13,24,..      a(t)=a(t−3)+a(t−2)+a(t−1)
Combinations of functions

Let us note yet some combinations of functions:

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

Because Sa=Fa/(1−x) a Sb=Fb/(1−x) are sequences Sa,Sb sum-sequences Fa,Fb. (What are the other relationships? Is e.g. each member of sequence Sb divisible by corresponding member of not only Fb but also Sa?)

The transition through sequences

Let's look at the three sequences:

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

By the sum of the first few members of the sequence in one row we get always a certain member of the sequence in the lower row. E.g. 1+0+1+0+1=3, resp. 1+1+2+2+3=9. In doing so f2=f1/(1−x) and f3=f2/(1−x). We get the sum of sequences by dividing of the generating function by (1-x) and the differential sequences by multiplying (1-x).

Generating functions

Consider the quadratic polynomials whose coefficients (with negative signs) take all the instances of G(3,2).

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

Each of the functions 1/F is generating function for a sequence and we are interested in what sequences these are. If we write each of the sequences recursively, the relation to the coefficients of the original polynomials F shows. Suppose a(0)=0, a(1)=1, n>1.

    Coefficients  Polynomial F (mod 3)  Recurrent notation for 1/F  
    ───────────────────────────────────────────────────────────
      00        x²             a(n) = 0
    * 01        x²     −1      a(n) = a(n−2)
      10        x²     −x      a(n) = a(n−1)
      02        x²     −2      a(n) = 2∙a(n−2)
      20        x² −2x         a(n) = 2∙a(n−1)
      11        x²  −x −1      a(n) = a(n−1) +  a(n−2)
      21        x² −2x −1      a(n) = 2a(n−1) +  a(n−2)
    * 12        x²  −x −2      a(n) = a(n−1) + 2a(n−2)
    * 22        x² −2x −2      a(n) =  2a(n−1) + 2a(n−2)

(Irreducible polynomials are marked with an asterisk, see Simple polynomials.)

Fibonacci sequence

Fibonacci, Leonardo Pissano
Fibonacci, Leonardo Pissano [fibonači], 1170-1230, Italian mathematician. He traveled through Egypt, Syria, Greece, Sicily and studied regional mathematical techniques. He continued on the work of Al-Chvárizmí. In the book of arithmetic and algebra he use Arabic numerals and the decimal numeral systems. He entered into the history of mathematics by "the exercise about rabbits" from which follows the sequence of numbers in which each next number is the sum of the two previous.
Properties of Fibonacci sequence

Fibonacci sequence has a variety of properties, e.g. it applies:

· a(t) | a(s) only if t | s, therefore, any two adjacent numbers are relatively prime

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

·member a(t+s) = a(t−1)a(s)+ a(t)a(s+1)

·if a(n)εP then also nεP (but not vice versa).

. ratio of values q=a(t+1)/a(t) is gradually approaching the ratio of so called golden section Q = (a+b)/a = a/b; Q is the solution of equation Q²−Q−1 = 0 (s roots Q1=−1/Q2)

Derived sequences

For members of Fibonacci sequences this relation was derived:

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

where c=5. This begs the question what sequences arise for others c εN.

By gradual substitution and after the transfer of the denominator to form 2k−1 we get:

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

We are only interested in the sequences in numerators:

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

These sequences are - for various c - designed by recurrent relation:

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

In doing so lim(a(k)/a(k−1)) for k going to infinity is 1+√k.

Permutation of equations

Permutation

Permutation is mapping of a set of numbers to the same set. E.g. there are 6 permutations on the set A = {1,2,3}: p0 =(123/123), p1 =(123/312), p2 =(123/231), p3 =(123/132), p4 =(123/321), p5 =(123/213). Each permutation can be broken down into cycles. Listing lengths of cycles (starting with length 1) is called the cycle type of the permutation. Each cycle of length 2 is (so called) transposition (inversion). Order of the permutation is the least common multiple of lengths of separate (disjoint) cycles.

 pi  u   (123)   Cycles     Lengths   Parity
───────────────────────────────────────────────
 p0  1   (123)   (1)(2)(3)   1 1 1       S
 p1  2   (312)   (1,3,2)     3           S
 p2  4   (231)   (1,2,3)     3           S
 p3  3   (132)   (1)(2,3)    1 2         L
 p4  6   (321)   (2)(1,3)    1 2         L
 p5  5   (213)   (3)(1,2)    1 2         L 

Parity of permutations

Decomposition of the permutation to the product of transpositions is ambiguous, for example: [1,2,3] = [1,3] [2,3] = [1,2] [1,3] i.e. (123 => 321 => 231 ~ 123 => 213 => 231) One permutation can not be composed together from an odd number of transpositions and some even number of other transpositions.

Parity of permutation is (−1)t, where t is the number of transpositions, which forms the permutation. Parity of odd permutation is -1, parity of even permutation is 1. Transposition is an odd permutation. Cycle length L has the parity (-1) L-1.

The overall parity decide cycles with odd (L-1), i.e. the cycles of even length. If the number of cycles of even length is odd, the permutation is odd, otherwise permutation is even. Composition of even (S) and odd (L) permutation is an odd permutation, in other cases even permutations arise:

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

Permutation groups

Permutations of degree n form a group, with n! elements, i.e. so-called permutation group of order n!. Groups of permutations are not generally commutative. They were introduced by N.H.Abel and E.Galois in relation to solving of equations. Elements of permutation groups are permutations (P0, P1, ..), e.g. for n = 3:

 pi  u        (123)   Cycle  Length of cycles Parity
────────────────────────────────────────────────────
 p0  1   1    (123)   (1)(2)(3)   1 1 1       S
 p1  2   a    (312)   (1,3,2)     3           S
 p2  4   a²   (231)   (1,2,3)     3           S
 p3  3   b    (132)   (1)(2,3)    1 2         L
 p4  6   ba   (321)   (2)(1,3)    1 2         L
 p5  5   ba²  (213)   (3)(1,2)    1 2         L 

Each group is a copy of a subset of permutation group (Cayley's theorem). E.g. groups of occultation movements, ie. groups of symmetry operations form copies of subsets of permutation groups. Such groups are called symmetric groups.

Permutation of the equation

When solving equations obtained by permutation of the coefficients x²−5x+6=0, we get two trios of discriminants - one trio for odd, second trio for even permutations:

pi  u (123) Cycles  Parity  Equation   D     Solutions
────────────────────────────────────────────────────────────────
p0  1 (123) (1)(2)(3) S   1x²−5x+6=0    1    2         3
p1  2 (312) (1,3,2)   S   6x²+1x−5=0  121   −1         5/6
p2  4 (231) (1,2,3)   S  −5x²+6x+1=0   56   −3−√14    −3+√14
p3  3 (132) (1)(2,3)  L   1x²+6x−5=0   56   (3−√14)/5 (3+√14)/5
p4  6 (321) (2)(1,3)  L   6x²−5x+1=0    1    1/2       1/3
p5  5 (213) (3)(1,2)  L  −5x²+1x+6=0  121    −1        6/5 

The same discriminant have equations (by the numbers u):

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

Values u, v in pairs of equations with the same D are complementary:

 u1+u2 = P+1 

where P is the number of permutations.
In the pairs are the equations mutually inverted, ie. also the solutions are mutually inverse:

 xu1∙xu2 = 1 

Intervallic series

All-interval series

All-interval serie  is a sequence of tones, in which each musical interval and tone (in octave) represented exactly once.
For Example the so-called serie of the Mallalieu  [C,Db,E,D,A,F,B,Eb,Ab,Bb,G,F#] includes intervals 1,3,10,7,8,6,4,5,2,9,11,(6).
The interval between the last tone F# and first tone C  is  6 (=tritonus, i.e. 6 halftones) - here is the repetition of the interval tolerated.

In general, numbers 1,2, ..., k-1 have the sum S (k) = k (k-1)/2 and starting with the tone 0 ends on the tone S(k) mod k,  
that is ends on the tone 0 (=the initial tone) for odd n, or on the tone n/2 (the median of the musical system of k) for even k, 
see table.

n 1 2 3 4 5 6 7 8 9 10 11 12
S(n) = n (n-1)/2 0 1 3 6 10 15 21 28 36 45 55 66
S(n) mod n 0 1 0 2 0 3 0 4 0 5 0 6

Generation

We generate the all-interval series by a ' brute force '- i.e. we create all the possible permutations of tones and we knock off of them, those that do not have the required properties. 

According to this:
1/ we generate a permutation of (k-1) elements.
2/ we calculate the partial sums (mod k) for each permutation.
3/ only such permutation, in which all the partial sums (mod k) give just numbers 0, ..., k-1 are written.

For example, for k = 6: the permutation (1, 4, 3, 2, 5) makes totals {0, 1, 5, 8, 10, 15}
and {0, 1, 5, 8, 10, 15} mod 6 = {0, 1, 5, 2, 4, 3}, therefore this permutation complies with the conditions and we write it.
 
Condition 3/(the existence of all the different tones) can be met only for even k.
The last member of the serie for odd k is always congruent with 0 (mod k).
For example, for k = 5 is S(5) =5 * 4/2 = 10 divisible by k = 5, which leads to repetition of the initial tone and to exclusion of the serie.

Enumeration

For particular k we get the following numbers of the resulting series:

k 2 4 6 8 10 12
Number 1 2 24  288  3856 
These numbers are very low comparing to (k-1)! and they are not in general divisors of (k-1)!.

Results

All-interval series of order k=2,4,6,8:
k=2
(1): 0,1

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

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

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

Reverse permutations

Every permutation (for k>2) have corresponding 'reverse' permutation
and also corresponding 'complementary' permutation.
E.g. for k=8  permutation (1,6,4,3,7,5,2) have reverse  (2,5,7,3,4,6,1)  [i.e. numbers written in reverse order]
and  complement (7,2,4,5,1,3,6)  [differences from the number k].

If the permutation is all-interval serie, then its reverse and complementary permutation is also such a serie.
Number of all-interval series  is therefore (for k>2)  even number.

Sometimes is reverse permutation the same as complementary permutation, e.g. (1,6,3,4,5,2,7) is this case.

Nested permutations

Permutation, that makes all-interval serie have certain hidden structure,
e.g. for k=8 the following pairs  make permutations of numbers 2-6:
  (1,2,3,4,5,6,7)  (3,6,1,4,7,2,5)
  (1,6,3,4,5,2,7)  (3,2,1,4,7,6,5)

 Similarly this pair makes permutations of numbers 1-3 and 5-7
  (1,2,3,4,5,6,7)
  (3,2,1,4,7,6,5)

Other such cycles (1-3,2-6,5-7) occur in pairs:
  (1,5,7,6,4,3,2)     (2,1,3,7,4,6,5)  (1,6,4,3,7,5,2)
  (3,7,5,2,4,1,6)     (6,3,1,5,4,2,7)  (3,2,4,1,5,7,6) .

Primitive roots

The previous paragraph reminds permutations of primitive roots - see restricted systems R(n,k,r),  e.g. for k = 12:

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

Here - total number 1!1!2!2!2!4!=192 of series arises from permutations of observed cycles [1][12][3,9][5,8][4,10][2,6,11,7].

Euler totient function

Other observation (Caleb Morgan): 
there are exactly 12 primitive roots mod 37:  2,5,13,15,17,18,19,20,22,24,32,35.

These relations hold  (mod 37) :
 21=2, 511=2, 1323=2, 1525=2, 1731=2, 1817=2,
1935=2, 2013=2, 227=2, 245=2, 3229=2, and 3519=2. 

We take only the exponents: 1,11,23,25,31,17,35,13,7,5,29,19.
and if we rank them (ascending):
we get order 1(0),11(3),23(7),25(8),31(9),17(5),35(10),13(4),7(2),5(1),29(9),19(6).

After transformation to tones, we get all-interval serie:
[C(0),Eb(3),G(7),Ab(8),Bb(9),F(5),B(10),E(4),D(2),C#(1),A(9),F#(6)].

The exponents 1,11,23,25,31,17,35,13,7,5,29,19 in case mod 37 are numbers having no common divisor with number 36.
Count of such numbers is determined by Euler totient function phi.
But result of Euler function can not make any integer, so it is not possible to use this principle  to make all-interval series for each k; e.g. it is not possible for k=14, because there exists no number with Euler function 14 ...