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.
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):
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! = 2^{8} ∙ 14175.
For n=a+b+c... platí κ(a+b+c...,p) ≥ κ(a,p) + κ(b,p) + .... a proto also:
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.
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).
2 = 1∙( 1+ 1) 6 = 2∙( 1+ 2) 24 = 3∙( 2+ 6) 120 = 4∙( 6+ 24) 720 = 5∙(24+120)
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) = ∫t^{x−1}/e^{t} dt.
In the field of natural numbers n is
Γ(n+1)= n! = (0,∞) ∫t^{n}/e^{t} dt.
Function Γ allows to simplify the calculation of certain integrals
(e.g integrals of goniometric function ...).
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:
E.g. s(5) = 120[1/2−1/6+1/24−1/120] = 44.
The Euler's numberLimit 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,...
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,...
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.
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: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 f_{r+1} and f_{r} (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, JamesStirling, James , 1692-1770, Scottish mathematician and physicist. He dealt with the methods of differential calculus - infinite rows, summarization, interpolation and with quadratures. |
The factorial function can be approximated by J.Stirling's relationship:
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%.
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 x^{n}−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: a_{n+1} = a_{n} + d 2.řádu: a_{n+2} = 2a_{n+1} − a_{n} 3.řádu: a_{n+3} = 3a_{n+2} − 3a_{n−1} + a_{n}
Recurrent notation of geometric sequences: a_{n+1} = a_{n} ∙ 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 sequenceSequence 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.
Numbers identified by recurrent relationship with two parameters:
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), ...
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:
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 [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. |
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
p_{0},p_{1},p_{2}:
p_{0}∙a(t+2)+p_{1}∙a(t+1)+p_{2}∙a(t) = 0
corresponds to difference equation with coefficients 1,q_{1},q2:
a''(t)+q_{1}∙a'(t)+q_{2}∙a(t) = 0 .
It applies:
q_{1} = p_{1} + _{ } p_{0}, q_{2} = p_{2} + _{ } p_{1} + _{ } p_{0} |
E.g. for p0=1, p_{1}=−5, p_{2}=6 is q_{1} = −3 a q_{2} = +2: q_{1} = −5 + _{ }∙1 = −5+2 = −3 q_{2} = +6 + _{ }∙(−5) + _{ }∙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. |
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:
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. c_{1}, c_{2,} according to: c_{1}= 2∙160 −(−112) = 432, c_{2} = 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 2^{k−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 3^{k−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
Let us derive expressions (n+1)^{k}−n^{k} (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:
Hermite polynomials, known from applications in quantum mechanics,
are constructed in a similar manner.
Derivation H_{k}'(x) of polynomial of degree k is (2k) a multiple of polynomial of degree (k−1).
E.g. H_{2}'(x) = (4x²−2)'=8x = 4∙2x= (2∙2)∙H_{1}(x):
k H_{k}(x) H_{k}'(x) ──────────────────────────────────────────── 0 1 0 1 2x 2 2 4x²−2 8x 3 8x³−12x 24x²−12 4 16x^{4}−48x²+12 64x³−96x 5 32x^{5}−160x³+120x 160x^{4}−480x²+120 6 64x^{6}−480x^{4}+720x²−120 384x^{5}−1920x³+1440x
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:
Polynomials determined by relationship: P_{k}'(x) = P_{k−1}(x), resp. P_{k}'(x) = k∙P_{k−1}(x) are called Appell's polynomials. Special cases of Appell's polynomials are Hermite and Laguerre polynomials.
If we write to the members of the sequences
{a_{0},a_{1},..,a_{n},..}
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.
a_{0}+a_{1}∙x^{1}+.....+a_{n}∙x^{n}+...
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 , [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). |
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,.....,2^{n} a(t)=2^{t} 1/(1−3x) 1, 3, 9, 27, 81,.....,3^{n} a(t)=3^{t} .... 1/(1−ax) 1,a,a²,a³,a^{4},.....,a^{n} a(t)=a^{t}
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)= _{} 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)= _{ } 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)
Let us note yet some combinations of functions:
Function Sequence Note ─────────────────────────────────────────────────────────── F_{a}=1/(1−x)/(1+x²) 1, 1, 0, 0, 1, 1, 0, 0, 1,... {a(t)} F_{b}=1/(1−x)/(1−x²) 1, 1, 2, 2, 3, 3, 4, 4, 5,... {b(t)} S_{a}=1/(1−x)²/(1+x²) 1, 2, 2, 2, 3, 4, 4, 4, 5,... {a'(t)} S_{b}=1/(1−x)²/(1−x²) 1, 2, 4, 6, 9,12,16,20,25,... {b'(t)}
Because S_{a}=F_{a}/(1−x) a S_{b}=F_{b}/(1−x) are sequences S_{a},S_{b} sum-sequences F_{a},F_{b}. (What are the other relationships? Is e.g. each member of sequence S_{b} divisible by corresponding member of not only F_{b} but also S_{a}?)
Let's look at the three sequences:
Function Sequence ─────────────────────────────────────────────────────── f_{1}= 1/(1−x²) 1, 0, 1, 0, 1, 0, 1,... f_{2}= 1/(1−x)/(1−x²) 1, 1, 2, 2, 3, 3, 4, 4, 5,... f_{3}= 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 f_{2}=f_{1}/(1−x) and f_{3}=f_{2}/(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).
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, 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. |
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)
For members of Fibonacci sequences this relation was derived:
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 2^{k−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:
In doing so lim(a(k)/a(k−1)) for k going to infinity is 1+√k.
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
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
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.
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:
where P is the number of permutations.
In the pairs are the equations mutually inverted, ie. also the solutions are mutually inverse:
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 |
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.
For particular k we get the following numbers of the resulting series:
k | 2 | 4 | 6 | 8 | 10 | 12 |
Number | 1 | 2 | 4 | 24 | 288 | 3856 |
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.
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) .
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].
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)
:
2^{1}=2, 5^{11}=2, 13^{23}=2,
15^{25}=2, 17^{31}=2, 18^{17}=2,
19^{35}=2,
20^{13}=2, 22^{7}=2, 24^{5}=2, 32^{29}=2, and 35^{19}=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 ...