\1cw  Verze 2.10
\pTM 0
\pBM 0
\pPL 120
\pLM 1
\pRM 65
\HD
\+

\=
\HE
\+

\=
\FD
\+

\=
\FE
\+

\=
\+
\+
\"8. G R O U P S   O F   C Y C L I C   P E R M U T A T I O N S\,
\-\1
\+
\+
8\4.1 Notion of cyclic permutations\,
\-\1
\+
\+
   Suppose that we have n labelled objects arranged in an natural
\-\/
\+
\+
order and \ we change their \ positions. It is \ convenient to write
\-
\+
\+
this operation \ in two lines, \ one corresponding to \ the starting
\-\/
\+
\+
position, the second one giving the final position. E.g.\,
\-
\+
\+
Start    1   2   3   4   5   6\,
\-
\+
\+
1. Step  2   3   1   5   4   6\,
\-
\+
\+
   The first 3 objects \ are permuted in a cycle of \ length 3, the
\-\/
\+
\+
next 2 form \ a cycle of length \ 2 and the last \ object remains on
\-
\+
\+
its \ place. By \ repeating \ the \ procedure \ we \ obtain permutations
\-\/
\+
\+
2 till 6.\,
\-
\+
\+
2. Step  3   1   2   4   5   6\,
\-
\+
\+
3. Step  1   2   3   5   4   6\,
\-
\+
\+
4. Step  2   3   1   4   5   6\,
\-
\+
\+
5. Step  3   1   2   5   4   6\,
\-
\+
\+
6. Step  1   2   3   4   5   6\,
\-
\+
\+
7.\ Step  2   3   1   5   4   6\,
\-
\+
\+
     The string returns in the 7. \ step to the initial order. The
\-\/
\+
\+
starting position, \ corresponding to the diagonal \ unit matrix \4I\1,
\-
\+
\+
can be \ considered as the \ zero order. The \ last element remained
\-
\+
\+
alvays in its original position \ and the first three elements re-\A
\-
\+
\+
turned \ to \ their \ positions \ twice \ and \ two elements made three
\-
\+
\+
turns. The length of the total cycle is the product of individual
\-
\+
\+
cycles: 3*2*1 = 6. The individual cycles are written usually with
\-\2
\+\1
\+
elements forming cycles in \ brackets: (2,3,1)(5,4)(6).\,
\-\2
\+\1
\+
     Linear \ translations \ can \ be \ wiewed \ as \ strings of cyclic
\-\2
\+\1
\+
permutations\,
\-\2
\+\1
\+
\4\ \ \ \ \ \ \ P\ \ \ \ \ \ \ \ \ P\ \ \ \ \ \ \ \ \ \ \ \ \ P\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ P\,
\-\2\ \ \ \ \ \ \ \ 1\ \ \ \ \ \ \ \ \ 2\ \ \ \ \ \ \ \ \ \ \ \ \ 3\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 4
\+\1
\+\8\ \ \ pp\ \ \ \ pp\ pp\ \ \ \ \ \ \ pp\ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
   pp\10  1\8pp pp\11  0  0\8pp  pp\11  0  0  0\8pp    pp\11  0  0  0  0\8pp\,
\-\ \ \ pp\ \ \ \ pp\ pp\ \ \ \ \ \ \ pp\ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ pp\ pp\ \ \ \ \ \ \ pp\ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ pp\ pp\ \ \ \ \ \ \ pp\ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
   pp\11  0\8pp pp\10  0  1\8pp  pp\10  1  0  0\8pp    pp\10  1  0  0  0\8pp\,
\-\ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ pp\ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ pp\ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ pp\ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
            pp\10  1  0\8pp  pp\10  0  0  1\8pp    pp\10  0  1  0  0\8pp\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
                         pp\10  0  1  0\8pp    pp\10  0  0  0  1\8pp\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
\1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0  0  0\ \ 1  0\8pp\,
\-\1
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\7     T\1he string \4P P P P  \1transform \ the vector (1,0,0,0)  into the
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 4\ 3\ 2\ 1\/
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \   T
\1vector  (0,0,0,1,) .\,
\-
\+
\+
     Here we use at first the notion of partitions. The number of
\-\/
\+
\+
elements n splits into k cycles, k going from 1 till n. The cycle
\-\/
\+
\+
structure is described by partition orbits.\,
\-
\+
\+
     We can map the cycle changes as additive operators \4S\1, having
\-\2\/
\+\1
\+
zero rows for unmoved objects (+1 and -1 appear on the same place
\-\2
\+\1
\+
s  ). This operator \ is formed by cycles. But now
\-\2\ ij
\+\1
\+
we will study the multiplication \ operators \4P\1. Their matrices are
\-
\+
\+
naive, they have \ in each row only one \ unit element and moreover
\-
\+
\+
only one unit element in each column. The matrices \4P \1are simulta-\A
\-\2
\+\1
\+
neously notations of permutations, \ since their row unit elements
\-\2\/
\+\1
\+
p   correspond to symbols j.\,
\-\2\ ij
\+\1
\+
     Using multiplicative operators, \ permutations are results of
\-
\+
\+
multiplications of the row vectors by the unit permutation matrix
\-
\+
\+\2
\4P \1from the \ right and column \ vectors by the \ multiplication with
\-
\+
\+\2
\1the \ permutation matrix \ from the \ left. Different \ steps can \ be
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i
\1written as powers of these \ matrices \4P \1, the unit diagonal matrix
\-
\+
\+\2\ \ \ \ \ 0
\4I \1= \4P \1. The last \ but one power of any \ permutation matrix is its
\-
\+
\+\2\ \ \ \ \ \ \ \ \ -1\ \ \ \ n-1
\1inverse \4P   \1= \4P   \2. \1It is rather easy to find this matrix, becau-\A
\-\/
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1se it is identical with the transposed matrix \4P \1. \,
\-
\+
\+
     The set \ of all permutation \ matrices \4P \1with n rows \ and co-\A
\-\/
\+
\+\2
\1lumns \ represents all \ possible permutations. \ A special class of
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1permutation \ matrices are \ symmetrical \ ones, \ which have \ \4P \1= \4P
\-\1
\+
\+\2\ \  -1
\1= \4P  \1. Such matrices \ have all unit elements either \ on the diago-\A
\-
\+
\+
nal, or otherwise, they form cycles of the length 2. These permu-\A
\-\/
\+
\+
tations \ are known \ as \ \4convolutions\1. \ We will \ find a surprising
\-\/
\+
\+
technique for their generating.\,
\-
\+
\+
\48.2 Young tables\,
\-\1
\+
\+
     Here we return to Ferrers \ graphs. We will reconstruct their
\-\/
\+
\+
sequence, finding all ways how they can be formed from lower ones
\-
\+
\+
by adding one element. For it, we will index order, each new pla-\A
\-
\+
\+
ce appeared inthe larger Ferrers graph. Eqivalent places will ha-\A
\-\/
\+
\+
ve different \ indices, because they \ can be reached \ in different
\-
\+
\+
steps. Such labelled Ferrers graphs are known as Young tables. \,
\-\/
\+
\+
E. g.\,
\-
\+\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ u-o
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ p
\1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ m-.
\+\ \ \ \ u----o
\+\ \ \ \ p\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ u-o
\1    \ 1  2\                              \8p\11\8p\,
\-\ \ \ \ m----.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ p
\+\1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2
\+\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ m-.
\1\,
\-
\+
\+\8\ \ \ \ u-------o\ \ \ p----o\ u----o\ \ \ \ \ \ \ \ \ \ u-o
\1\ \ \ \ \ 1  2  3\    \8p\11  2\8p p\11  3\8p        \ \ p\11\8p\,
\-\ \ \ \ m-------.\ \ \ p\ \ \ \ p\ p\ \ \ \ p\ \ \ \ \ \ \ \ \ \ p\ p
\+\1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 3\ \ \ \ \ \ 2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \8p\12\8p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ m----.\ m----.\ \ \ \ \ \ \ \ \ \ p\ p
\1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 3\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ m-.
\+\1
\+
     Young tables \ are connected with permutations \ by the follo-\A
\-\/
\+
\+
wing algorithm:\,
\-
\+
\+
     1. If a greater index follows a lesser one, it is written in
\-\/
\+
\+
the next free column of the Young table. \,
\-
\+
\+
     2. If a lesser index follows a greater one in a permutation, \,
\-
\+
\+
it replaces it \ in its column \ of the Young \ table and shifts \ it
\-\/
\+
\+
down to the next row. For example:\,
\-
\+
\+
3412 \8---\1>   3  4  \ \8---\1> \ 1  4  \8----\1>   1  2\,
\-
\+
\+                         3             3  4
\,
\-
\+
\+
or : 4231 \8----\1>  4 \8----\1> 2 \8----\1> 2  3 \8----\1> 1  3\,
\-
\+
\+
                         4       4          2\,
\-
\+
\+
                                            4\,
\-
\+
\+
     The algorithm has one property, which seems to be its disad-\A
\-\/
\+
\+
vantage, but \ it only reproduces \ relations between permutations.
\-
\+
\+
It allows that an asymmetric permutation matrix can be decomposed
\-
\+
\+
differently \ according to \ its rows \ and columns. \ But both Young
\-\/
\+
\+
tables belong to an equal type of Ferrers graphs. For example:\,
\-
\+
\+\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\10   0   0   1   0   0   0  \8p \14\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ u---------o
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ p
\10   0   0   0   0   1   0  \8p \16         \8p\11   3   7\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ u---.
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ p
\10   1   0   0   0   0   0  \8p \12         \8p\12   5\8p\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ p
\10   0   0   0   1   0   0  \8p \15         \8p\14   6\8p\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ m-----.
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\10   0   0   0   0   0   1  \8p \17\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\11   0   0   0   0   0   0  \8p \11\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\10   0   1   0   0   0   0  \  3\,
\-\8---------------------------.
\+\1
\+
6   3   7   1   4   2   5  \  \,
\-
\+\8\ \ u----------o
\+\ \ p\ \ \ \ \ \ \ \ \ \ p
  p \11   2   5\8p\,
\-\ \ p
\+\ \ p\ \ \ \ \ \ \ u--.
\+\ \ p\ \ \ \ \ \ \ p
  p \13   4 \8p\,
\-\ \ p\ \ \ \ \ \ \ p
\+\ \ p\ \ \ \ \ \ \ p
\+\ \ p\ \ \ \ \ \ \ p
\1  \  6   7\,
\-\8\ \ m-------.
\+\1
\+
     Remember, \ that convolutions \ have symmetrical \ matrices and
\-\/
\+
\+
that at them column and row readings are identical. A permutation
\-
\+
\+
matrix or \ a Young table is \ always a product of \ two permutation
\-
\+
\+
matrices or Young tables of the \ same format. They can be identi-\A
\-
\+
\+
cal in \ case of convolutions, \ but mostly they \ are different for
\-
\+
\+
rows and columns, as\,
\-
\+\8\ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ p
\ \ \ \ \         p \11  0  0\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ p
       \ \ \ \   p \10  0  1\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ p
             p \10  1  0\,
\-
\+\8\ \ \ \ ---------k---------
\+\ \ \ \ \ \ \ \ \ \ \ \ \ p
\1     0  1  0 \8p \10  0  1\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ p
\1     1  0  0 \8p \11  0\ \ 0\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ p
\1     0  0  1 \8p \10  1  0\ \ \ \ \ \ \ \ \ \ \ (a,c,b)*(b,a,c) = (c,a,b)\,
\-
\+
\+
     So there appears a relation between the number of partitions
\-\/
\+
\+
orbits p(n), \ the number of Young \ tables Y(n) and the \ number of
\-\/
\+
\+
permutation matrices P(n).\,
\-
\+
\+\2
\1     The Young tables are formed from Ferrers graphs by an recur-\A
\-\/
\+
\+\2
\1sive algorithm. If we use for \ the number of Young tables corres-\A
\-
\+
\+\2
\1ponding \ to a Ferrers \ graph with \ an index \ k the notation y(k),
\-\/
\+
\+\2\ \  \ \ \ 0
\1then y (k) = 1, \ and we have \ the relation between \ the number of
\-\/
\+
\+\2
\1partitions and the number of \ Young tables Y(n). Similarly, if we
\-
\+
\+\2
\1square all y(k), we obtain all permutations of n elements. There-\A
\-\/
\+
\+\2
\1fore\,
\-
\+
\+\2\ \ \ 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \   \  \ \ 2
\7S \1y\ (k) = p(n); \7S \1y(k) = Y(n) ; \7S \1y\ (k) = P(n) = n!    (8.1)\,
\-
\+
\+
     Here n! means n factorial. It is a product of the successive
\-\/
\+
\+\2
\1natural numbers: \,
\-\2
\+\1
\+\2\ \ \ \ \ \  n
\7     P    \1k = n!. \,
\-\2\ \ \ \ \  k=1
\+\1
\+
     We will explain \ this function later, when we \ will look for
\-\/
\+
\+
other formulas determining the number of permutations. Before it,
\-
\+
\+
we will study convolutions. Here we give an example, how equation
\-
\+
\+
(8.1) works. \ The corresponding Young tables \ are counted on Fig.
\-\/
\+
\+
8.1:\,
\-
\+\8\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \22\ \ \ \ 2\ \ \ \ \ \ \ 3\ \ \ \ \ 5\ \8p
\1Partition:  \8p \15;   4,1;   3,2;  3,1\ ;  2\ 1;  2,1\ ;   1\  \8p\7S   \17\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1y(k)        \8p \11     4     5      6     5      4      1  \8p   \126\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\2\ 2\72\ \ \ \ \ \ \ \ \ \8p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1y\ (k)       \8p \11    16    25     36    25     16      1  \8p  \1120\,
\-
\+
\+
\48.3 The number of convolutions\,
\-\1
\+
\+
     The \ number of \ convolutions is \ the number \ of all possible
\-\/
\+
\+
connections in a telephone network, too. We classify all convolu-\A
\-
\+
\+
tions according to \ the number of elements which \ remain on their
\-
\+
\+
places, it \ means unconnected. It \ is easy to \ fill the following
\-\/
\+
\+
table\,
\-
\+
\+
\4Table 8.1 Distribution of convolutions\,
\-\1
\+\8------------i----------------------------i---
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1On diagonal \8p \10   1   2   3   4   5   6  \8p  \7S\,
\-\1
\+\8------------k----------------------------k---
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1n= 0        \8p \11                          \8p  \11\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1   1        \8p \10   1                      \8p  \11\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1   2        \8p \11   0   1                  \8p  \12\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1   3        \8p \10   3   0   1              \8p  \14\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1   4        \8p \13   0   6   0   1          \8p \110\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1   5        \8p \10  15   0  10   0   1      \8p \126\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1   6        \8p\115   0  45   0  15   0   1  \8p \176\,
\-
\+
\+
   The reccurence of table elements is \,
\-\2
\+\1
\+
\ \ \ \ \ \ \ \ y\ \  = 1;   y\ \  = (i - 1)y\ \ \ \ \  + y\ \ \ \ \ \ \     (8.2)\,
\-\2\ \ \ \ \ \ \ \ \ 00      \ \ \ ij\ \ \ \ \ \ \ \ \ \ \ i-2,j\ \ \ \ i-1,j-1
\+\1
\+
     The inverse table \ has the same elements, only \ the signs at
\-\/
\+
\+
elements which indices differ by the value (4k + 2) are negative.
\-
\+
\+
All \ convolution matrices \ are obtained \ by adding \ 1 on the last
\-
\+
\+
place \ of diagonal. \ These convolutions \ are counted \ by the term
\-\2
\+\1
\+
y       . If we \ add the unit element in the \ last row off diago-\A
\-\2\ i-1,j-1
\+\1
\+
nal, we must \ simultaneously add an unit element \ in the last co-\A
\-
\+
\+
lumn into the corresponding row, i=j. \ There are (n - 1) off dia-\A
\-
\+
\+
gonal places where \ it is possible to form \ a new convoluted pair
\-
\+
\+
to j already existing pairs in a matrix of convolutions. This new
\-
\+
\+
pair occupies two rows and columns \ and therefore it is formed in
\-
\+
\+
matrices with (n - 2) rows and \ columns. It does not increase the
\-
\+
\+
number of elements on the diagonal, so it increases the number of
\-\/
\+
\+
elements in the same column.\,
\-
\+
\+
     A similar reccurence is applied to the row sums counting the
\-\/
\+
\+
total number of convolutions\,
\-
\+
\+
\ \ \ \ \ \ \ \ Y(n) = (n - 1)Y(n - 2) + Y(n - 1)           (8.3)\,
\-
\+
\+
     It is \ possible to determine \ the elements of \ the Table 8.1
\-\/
\+
\+
directly, because they are calculated according to the formula\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ t
\1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ y\ \  = i !/j!t!2\                     (8.4)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ij
\+\1
\+
     where t \ = (i - j)/2 is \ the number of \ cycles of length \ 2.
\-\/
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2
\1This formula \ contains 3 factorials. The \ term 2  eqilibrates the
\-
\+
\+
string of \ t divisors. Notice, that \ (8.4) counts together \ Young
\-
\+
\+
tables of different formats, they \ must have only the same number
\-\/
\+
\+
of columns. Still \ another expression \ of the \ number of convolu-\A
\-\/
\+
\+
tions is a formal binomial equation\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n
\1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Y(n) = (1 + y\ )\ \                 (8.5)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i
\+\1
\+\2
\1     where the terms in the first column of the Table 8.1 y   are
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \                    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \   k0\/
\+\1
\+\2
\1considered \ as powers \ of y at \ the multiplication \ of the sum \,
\-\2
\+\1
\+\2\ \ \ \ \ \ \ \ \  k\ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ 6
\1(1 + y): y  = y  \2. \1E. g. (1 \ + y)  = 1*1 \ \ + 6*0 \ \ + 15*1 \ + 20*0
\-\2\ \ \ \ \ \ \ \ \  i\ \ \ \ k0\/
\+\1
\+\2
\1+ 15*3 + 6*0 +1*15 = 76.\,
\-\2
\+\1
\+\2
\1     The convolutions \ counted by these terms have no elements on
\-\2\/
\+\1
\+\2
\1the main \ diagonal and are \ obtained by multiplying \ odd numbers.
\-\2\/
\+\1
\+\2
\1They are \ odd factorials, since they \ are obtained by consecutive
\-\2
\+\1
\+\2
\1multiplications of odd numbers: 1*3*5*7*9*11*13*15* and so on.\,
\-\2
\+\1
\+\0
\48.4 Index of cyclic permutations\,
\-\1
\+
\+
     The number \ of all permutation \ matrices P(n) is \ determined
\-\/
\+
\+
easily by counting possibilities how to arrange units in rows and
\-
\+
\+
columns \ in a permutation \ matrix. In \ the first \ row, there \ are
\-
\+
\+
n possibilities, in the second one \ column is blocked by the ele-\A
\-
\+
\+
ment of the \ first row. The second row element \ can not be in the
\-
\+
\+
same column. The opportunities decrease regularly. In each row (n
\-
\+
\+
- i) remaining places are \ free. These opportunities are indepen-\A
\-
\+
\+
dent and therefore they multiply for \ all rows. We get the facto-\A
\-\/
\+
\+
rial \,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n
\1\ \ \ \ \ \ \ \ \ \ P(n) = n*(n-1)*..*2*1 =\7P\ \ \  \1j = n!      (8.6)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j=1
\+\1
\+
     We complete this \ definition by the term \ 0! = 1. We already
\-\/
\+
\+
did something \ similar, defining the empty \ partition. Here it is
\-
\+
\+
possible by defining the function gamma as a function of a conti-\A
\-
\+
\+
nuous argument \7G\1(x) = x\7G\1(x-1). Inserting \ x = 1 we obtain the va-\A
\-
\+
\+
lue of \7G\1(0) easily: 1! = \ 1*1!. The function gamma coincides with
\-
\+
\+
factorials of natural numbers.\ It is difficult to calculate valu-\A
\-\/
\+
\+
es of the gamma function for rational and irrational numbers. But
\-
\+
\+
we can estimate the behaviour of this function for negative argu-\A
\-
\+
\+
ments. It oscillates \ there from minus to plus \ infinity. In area
\-
\+
\+
of positive numbers, \ it is an evergrowing function. \ There is no
\-
\+
\+
solid space in area of \ negative numbers. \,
\-
\+
\+
     The factorial function has \ an interesting property. If p is
\-\/
\+
\+
a prime number, then \ (p -1)! mod p = (p \ - 1) and simultaneously
\-
\+
\+
(p -2)! mod p = 1. If this value  were other one, say a, then be-\A
\-
\+
\+
cause the factorial is divisible by all its factors, say b chosen
\-
\+
\+
in such \ a way, that a + \ b = p, the factorial were \ divisible by
\-
\+
\+
the prime \ number greater than its \ factors, which is impossible.
\-
\+
\+
For example: p =7, 720 mod 7 \9_ \16, 120 mod 7 \9_\ \11.\,
\-
\+
\+
     After this transgression, we return to permutations and find
\-\2\/
\+\1
\+
formulas, how to determine their numbers at each cycle structure.
\-\2
\+\1
\+\2
\1This cycle structure \ forms an orbit of permutations \ and the sum
\-\2
\+\1
\+\2
\1over \ all orbits \ gives the \ factorial. A partition \ orbit counts
\-\2
\+\1
\+\2
\1 all permutations of \ an cycle s  of \ the length k. \ If there are
\-\2              \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k
\+\1
\+\2
\1more cycles of equal length, \ their lengths s  multiply. This gi-\A
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ t
\1ves \ terms s \2k\1, \ where  t  is \ the number \ of cycles s . Moreover
\-\2\ \ \ \ \ \ \ \ \ \ \ \ k\ \   \ \ \ \ \ \ \ \ k\ \ \ \ \ \ \ \    \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ k
\+\1
\+
different cycles of \ equal length can be permuted \ against  them-\A
\-
\+
\+
selves when \ their elements interchange. \ This interchanges  \ are
\-\/
\+
\+
counted by \ partial factorials t !. The \ index of cyclic permuta-\A
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k\/
\+\1
\+
tions is\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ t
\1     n!/\7P\1n !s \2k\,
\-\ \ \ \ \ \ \ \ \ \ k\ \ k
\+\1
\+
   For example for n = 4 : \,
\-
\+\8\ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1Orbit   \    Cycle index      \          Value\,
\-\8--------k--------------------k---------------
\+\ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \21\ \ \ \ \ \ \ \ \ \ \8p
\14       \8p   \14!/1!4\           \8p           \16\,
\-\8\ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \21\ 1\ \ \ \ \ \ \8p
\131      \8p   \14!/1!1!3\ 1\       \8p           \18\,
\-\8\ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \22\ \ \ \ \ \ \ \ \ \ \8p
\122      \8p   \14!/2!2\           \8p           \13\,
\-\8\ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\2\ \ 2\ \ \ \ \ \8p\ \ \ \ \ \ \ \ \ \ \ \21\ 2\ \ \ \ \ \ \8p
\121\      \8p   \14!/1!2!2\ 1\       \8p           \16\,
\-\8\ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\2\ 4\ \ \ \ \ \ \8p\ \ \ \ \ \ \ \ \ \24\ \ \ \ \ \ \ \ \ \ \8p
\11\       \8p   \14!/4!1\           \8p           \11\,
\-
\+\8--------k--------------------k------------
\+\ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
        p                    p    \1Sum   24\,
\-
\+\8
\+\1
\48.5 Permutation schemes\,
\-\1
\+
\+
   We introduced orbit schemes and now we have the first opportu-\A
\-\/
\+
\+
nity to exploit \ them for making partial sums \ of cyclic indices.
\-
\+
\+
These partial sums are known as different combinatorial identiti-\A
\-
\+
\+
es. At first, we will arrange \ partition schemes according \ to the
\-
\+
\+
number of \ cycles in permutations \ and the length \ of the longest
\-\/
\+
\+
cycle k. E. g. for n = 6 we get\,
\-
\+\8\ \ \ \ \ p
\+\ \ \ \ \ p
\1n    \    1    2    3    4    5    6\,
\-\8-----k-----------------------------
\+\ \ \ \ \ p
\+\ \ \ \ \ p
\1k=6  \8p \1120 \,
\-\8\ \ \ \ \ p
\+\ \ \ \ \ p
\+\ \ \ \ \ p
\1  5  \8p      \1144\,
\-\8\ \ \ \ \ p
\+\ \ \ \ \ p
\+\ \ \ \ \ p
\1  4  \8p       \190   90\,
\-\8\ \ \ \ \ p
\+\ \ \ \ \ p
\+\ \ \ \ \ p
\1  3  \8p       \140  120   40\,
\-\8\ \ \ \ \ p
\+\ \ \ \ \ p
\+\ \ \ \ \ p
\1  2  \8p            \115   45   15 \,
\-\8\ \ \ \ \ p
\+\ \ \ \ \ p
\+\ \ \ \ \ p
\1  1  \8p                            \11\,
\-
\+\8-----k-----------------------------
\+\ \ \ \ \ p
\7 S   \8p\1120  274  225   85    15    1\,
\-
\+\8
\+\1
   The row sums of consecutive schemes \ give the Table 8.2 of the
\-\/
\+\8
\+\1
Stirling numbers of the first kind. Their name witness that the-\A
\-
\+\8
\+\1
re are more \ kinds of Stirling numbers. They \ are related by many
\-\/
\+\8
\+\1
ways which we will see later.\,
\-
\+
\+
\4Table  8.2  Stirling numbers of the first kind\,
\-\1
\+\8----i-----------------------------------i-----
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1t   \8p   \11     2     3     4     5     6 \8p   \7S\,
\-\1
\+\8----k-----------------------------------k-----
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1n=1 \8p   \11                               \8p   \11\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  2 \8p   \11     1                         \8p   \12\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  3 \8p   \12     3     1                   \8p   \16\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  4 \8p   \16    11     6     1             \8p  \124\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  5 \8p  \124    50    35    10     1       \8p \1120\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  6 \8p \1120   274   225    85    15     1 \8p \1720\,
\-\8\ \ \ \ p
\+\1
\+
   The recurrence of Stirling numbers is \,
\-
\+
\+
\ \ \ \ \ \ \ \ \ \ \ \ s\ \  = (n - 1)s\ \ \ \ \  + s\ \ \ \ \ \ \       (8.8)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ ij\ \ \ \ \ \ \ \ \ \ \ i-1,j\ \ \ \ i-1,j-1
\+\1
\+
     The formula was explained by describing how permutation mat-\A
\-\2\ \ \ \ \   \ \ \ \ \  \ \ \          \/
\+\1
\+
rices \4P    \1are increased with the \ new row and column. We have (n
\-\2\ \ \ \ \ \ \ n-1
\+\1
\+
- 1) off diagonal places in the \ last row which split (n - 1) di-\A
\-\2
\+\1
\+
mensional permutation matrices and prolong some existing cycle or
\-\2
\+\1
\+
cycles but do \ not change their number. Then we \ can add the unit
\-\2
\+\1
\+
element on the diagonal, but \ this operation increases the number
\-\2
\+\1
\+
of cycles of \ unit length. So we obtain \ the intermediate sums of
\-\2
\+\1
\+
several cycle indices directly \ without changes of all correspon-\A
\-\2
\+\1
\+
ding orbits. Remember that these sums correspond to vertices, ed-\A
\-\2
\+\1
\+
ges, \ surfaces and \ generally n dimensional \ subsimplices of \ the
\-\2
\+\1
\+
surface simplex. But \ here they split only one \ original orbit in
\-\2\/
\+\1
\+
the center of the plane simplex.\,
\-\2
\+\1
\+
\48.6 Rencontres numbers\,
\-\1
\+
\+
   Another possibility \ how to count \ permutations is to \ use the
\-\/
\+
\+
number of unit cycles, to determine the unit elements on the main \,
\-
\+
\+
diagonal of the unit permutation matrices, known \ as unmoved ele-\A
\-
\+
\+
ments. We have \ shown, how the counts of \ partitions are obtained
\-
\+
\+
according to the number of \ ones in partitions. Using this scheme
\-
\+
\+
for tabulating permutation indices, we \ get the column sums known
\-\/
\+
\+
as the rencontres numbers. They are shown in the Table 8.3.\,
\-
\+
\+
\4Table 8.3 Rencontre numbers\,
\-\1
\+
\+\8\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1s\    \8p   \10     1     2     3     4     5     6  \8p   \7S\,
\-\2\ 1
\+\8-----k------------------------------------------k----
\+\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1n=0  \8p   \11                                      \8p   \11\,
\-\8\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  1  \8p   \10     1                                \8p  \ \11\,
\-\8\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  2  \8p   \11     0     1                          \8p   \12\,
\-\8\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  3  \8p   \12     3     0     1                    \8p   \16\,
\-\8\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  4  \8p   \19     8     6     0     1              \8p  \124\,
\-\8\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  5  \8p  \144    45    20    10     0     1        \8p \1120\,
\-\8\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  6  \8p \1265   264   135    40    15     0     1  \8p \1720\,
\-
\+
\+
   The reccurence \ is somewhat surprising, \ the rencontres numbers
\-\/
\+
\+
are obtained from the zero column by multiplying it with binomial
\-\/
\+
\+
coefficients\,
\-
\+
\+\0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ( \1i \0)
\1\ \ \ \ \ \ \ \ \ \ \ \ \ \ r\ \  = \ \ \ \ \ r\ \ \ \ \ \               (8.9)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ij\ \ \ \09 \1j \00\ \2i-j,0
\+\1
\+
     Compare it \ with the Table 5.6 \ of partitions ordered accor-\A
\-\/
\+
\+
ding to the number of unit parts. Now these parts are just combi-\A
\-
\+
\+
ned with other parts. The elements \ of the table 8.3 are obtained
\-\/
\+
\+
as terms of a somewhat complicated expression\,
\-
\+
\+
n! = 1 + (1 -1/1!)n + (1 -1/1! +1/2!)n(n-1) + ...\,
\-
\+
\+
which can be formulated as \,
\-
\+
\+\2\ \ \ \ \ \ k=n\ \   \ \ \ \ \  k
\1n!\ = \7S     \1( -1/k!) (n)\ . \,
\-\2\ \ \ \ \ \ k=0\ \ \ \ \   \ \ \ \ \  \ k
\+\6\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \6t\6
\+\1
E.g.: 4! = 1 + 0 + (1/2)*12 + (2/6)*24 + (9/24)*24.\,
\-\2
\+\1
\+
     It is necessary to explain at least, that the binomial coef-\A
\-\/
\+
\+\0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ( \1i \0)
\1ficient is a ratio of 3 factorials       = i!/j!(i-j)!. How a bi-\A
\-\0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 9 \1j \00
\+\1
\+
nomial coefficient is \ obtained, we will see later. \ Here we give
\-\0\/
\+\1
\+
an example: 1*44 + 5*9 + 10*2 + 10*1 + 5*0 +1*1 = 120.\,
\-\0
\+\1
\+
     Numbers \ röö \ count \ permutations \ matrices \ with \ i \ rows and
\-\2\ \ \ \ \   \ \ \ \ \ \ \ \ io
\+\1
\+
columns having \ no unit elements \ on the diagonal. These \ matrices
\-\2
\+\1
\+
are combined \ with the diagonal \ unit matrices \4I \ \1with (i-j) rows
\-\2
\+\1
\+
and \ columns \ in \ all \ possible \ ways \ counted \ by \ the \ binomial
\-\2
\+\1
\+
coefficient.\,
\-\2
\+\1
\+
   Rencontre numbers r   are known also as subfactorials, because
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i0\/
\+\1
\+\2
\1they produce \ factorials by the following \ equation, where formal
\-\2\/
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i
\1powers of subfactorials r = r  are inserted:\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n
\1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n! = (r\  + 1)\               (8.10)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i
\+\1
\+
   It is possible \ to formulate (8.9) also in \ the matrix form as
\-\/
\+
\+\2
\1the direct product \7D\1(n!) = \4R\1*\4B \1, where \4R \1is the matrix of subfac-\A
\-\/
\+
\+\2
\1torials in rows and \4B \1is \ the matrix of binomial coefficients. In-\A
\-\2\/
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n
\1versing the formal powers we \ have r(n) = (k! - 1). Inserting
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0\/
\+\1
\+\ \ \ \ n
(k!)  = n! we obtain the formula \,
\-
\+
\+\0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ( \1n \0)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\1n\0)\ \ \ \ \ \ \ \ \ \ \ \ \2n
\1n! - n(n-10)! + \ \ \ \ \ (n-2)! - ....+/-\ \ \ (n-n)! =(k!)\,
\-\0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 9 \12 \00\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 9\1n\00
\+\1
\+
   This becomes for n going to infinity\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n
\1n![1 - 1 \ + 1/2! - 1/3! + \ .....] \9= \1n/eö, where e \ is the base of
\-
\+
\+
natural \ logarithms. This \ approximate \ formula \ is known \ as the
\-
\+
\+
rough Stirling approximation for factorials of large numbers.\,
\-
\+
\+
    We should mention still another formal notation for subfacto-\A
\-\/
\+
\+
rials. It is the notation of \ the theory of finite differences. It
\-
\+
\+
will be explained in Chapter 11.4\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n\ \ \ \ \ \ n
\1\ \ \ \ \ \ \ \ \ \ \ \ \ \ r\ (n) = [E - 1]\ 0! = \7D\ \10!      (8.11)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0
\+\1
\+\2\ \ \ \ \ \ \ \ \ n
\1   Here \7Dö \1is not a diagonal \ matrix but a difference of the n-th
\-
\+
\+\2
\1degree, or n times repeated difference \ of the basic state E.\,
\-
\+
\+\2
\1     We rencontre rencontre numbers in Chapter 16, again. \,
\-
\+
\+
     There exists still another reccurence for subfactorials\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n
\1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ r\ \  = nr      + (-1)\        (8.12)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n0\ \ \ \  n-1,0
\+\1
\+
e.g. 5*9 - 1 \ = 44; 6*44 + 1 = 245. When we \ return to the parti-\A
\-\/
\+
\+
tion scheme in Table 8.3 and reclassify permutations without unit
\-
\+
\+
cycles according to the number of \ cycles, or when we delete from
\-
\+
\+
the original \ scheme (Table 8.2) all \ permutations with unit cyc-\A
\-\/
\+
\+
les, we obtain the Table 8.9 \ of the adjoined Stirling numbers of
\-\/
\+
\+
the first kind.\,
\-
\+
\+
\4Table 8.9 Adjoined Stirling numbers of the first kind\,
\-\1
\+
\+\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1j   \8p    \10    1     2     3    \8p \7S\1= r\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i0
\+\8----k--------------------------k-------
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1i=0 \8p    \11                     \8p    \11\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  1 \8p         \10                \8p    \10\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  2 \8p         \11                \8p    \11\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  3 \8p         \12                \8p    \12\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  4 \8p         \16     3          \8p    \19\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  5 \8p        \124    20          \8p   \144\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  6 \8p       \1120   130    15    \8p  \1265\,
\-
\+
\+
  The reccurence is \,
\-
\+
\+
\ \ \ \ \ \ \ \ \ \ a\ \ \ \ \ = i[a\ \  + a\ \ \ \ \ \ \ ]              (8.13)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ i+1,j\ \ \ \ \ ij\ \ \ \ i-1,j-1
\+\1
\+
   It \ is justified \ again by \ possibilities, how \ to insert a new
\-\/
\+
\+
element to existing cycles. Either we \ can insert it into an exis-\A
\-
\+
\+
ting cycle. It is simpler, if \ we formulate it for (i + 1) matri-\A
\-
\+
\+
ces. There \ we have in (i \ + 1) dimensional matrix i off-diagonal
\-
\+
\+
opportunities. Or we can add \ a new 2 dimensional cycle to matri-\A
\-\/
\+
\+
ces with (i - 1) rows with the same number of possibilities.\,
\-
\+
\+
\8.7 Euler numbers\,
\-\1
\+
\+
     We have not exhausted all possibilities how to classify per-\A
\-\/
\+
\+
mutations. Another \ statistics counts the \ number of segments \ of
\-
\+
\+
a permutations in \ which its elements \ are arranged according \ to
\-
\+
\+
their \ natural order \ as increasing \ indices. E.g. \ a permutation
\-
\+
\+
357/1689/4/2 has \ 4 segments. The reccurence \ of this statistics,
\-\/
\+
\+
known as Euler numbers, is:\,
\-
\+
\+
\ \ \ \ \ \ e\ \  = 1; e\ \  = je\ \ \ \ \  + (i - j + 1)e\ \ \ \ \ \ \    (8.14)\,
\-\2\ \ \ \ \ \ \ 11\ \ \ \ \ \ \ ij\ \ \ \ \ i-1,j\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i-1,j-1
\+\1
\+
   If we \ give the i-th element \ on the end of \ each segment, the
\-\/
\+
\+
number \ of segments \ remain unchanged. If \ we put \ it on the first
\-
\+
\+
place, we increase \ the number of segments. Similarly, \ if we put
\-
\+
\+
it inside \ an existing segment, \ this is then \ splitted into two.
\-
\+
\+
There are (i - j) \ places inside segments. An alternative explana-\A
\-
\+
\+
tion is, that this statistics \ counts elements of permutation mat-\A
\-
\+
\+
rices, which are over the main diagonal. Here the index j goes from
\-\/
\+
\+
0 till (n-1). The corresponding matrix is Table 8.10.\,
\-
\+
\+
\4Table 8.10 Euler numbers\,
\-\1
\+
\+\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1j   \8p  \11    2    3    4    5    6  \8p   \7S\,
\-\1
\+\8----k------------------------------k----
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1i=1 \8p  \11                           \8p   \11\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  2 \8p  \11    1                      \8p   \12\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  3 \8p  \11    4    1                 \8p   \16\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  4 \8p  \11   11   11    1            \8p  \124\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  5 \8p  \11   26   66   26    1       \8p \1120\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  6 \8p  \11   57  302  302   57    1  \8p \1720\,
\-
\+
\+
\8\,
\-\1
\+
\+
    Till now we have counted permutations as objects. Now we will
\-
\+

\+
count \ their moments, \ expressed by \ the number \ of inversions in
\-\/
\+
\+
permutations. They are counted by zero elements over unit elements
\-
\+
\+
which are below \ the main diagonal as in the \ example, where 4 on
\-
\+
\+
the first place has 3 inversions and 3 on the second place only 2\,
\-
\+
\+
                 *   *   1   0\,
\-
\+
\+
                 *   *   0   1\,
\-
\+
\+
                 *   1   0   0\,
\-
\+
\+
                 1   0   0   0\,
\-
\+
\+
    Permutations counted \ according to this \ method give the \ Mac
\-
\+
\+
Mahon numbers as in Table 8.11\,
\-
\+
\+
\4Table 8.11 Mac Mahon numbers\,
\-\1
\+
\+\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1k   \8p   \10   1   2   3   4   5   6   7   8   9  10 \8p   \,
\-\1
\+\8----k---------------------------------------------l
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1n=1 \8p   \11\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \8p\,
\-\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  2 \8p   \11   1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \8p\,
\-\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  3 \8p   \11   2   2   1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \8p\,
\-\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  4 \8p   \11   3   5   6   5   3   1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \8p\,
\-\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \   p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \   p
\1  5 \8p   \11   4   9  15  20  22  20  15  9   4   1  \8p\,
\-\ \ \ \ p
\+\1
\+
   Notice, that \ here the parameter \ k does not end \ at the number
\-\/
\+
\+
n but it continues till the value \ n(n-1)/2. It is as if we coun-\A
\-
\+
\+
ted these values on the \ diagonal of a square. The maximal moment
\-
\+
\+
k is just the sum of values \ (i-1) where i is going from 1 till n\,
\-\/
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ n\ \ \ \ \ \ \ \ \ \ \ \ \0( \1n \0)
\7\ \ \ \ \ \ \ \ \ \ \ S \ \  \1(i - 1) = \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (8.15)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ i=1\ \ \ \ \ \ \ \ \ \ \ \09 \12 \00
\+\1
\+
   The distribution of moments \ is symmetric, therefore the matrix
\-
\+
\+
elements are \ related as möö = \ möööööööööööööö. The reccurence of
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ik\ \ \ \ \ i,[i(i-1)/2]-k
\+\1
\+
Mac Mahon numbers is \,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n
\1\ \ \ \ \ \ \ \ \ \ \ \ m(m,n) = \7S \ \ \1(m-k,n-1) ; m  \2= \11        (8.16)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k=0\ \ \ \ \ \ \ \ \ \ \ \  10
\+\1
\+
   or for the k \9< \1i:  m   = m      + m     . If we add to a lesser
\-\2\ \   \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \   ij\ \ \ \ i-1,j\ \ \ \ i,j-1\/
\+\1
\+
permutation matrix \ the unit element on \ the last diagonal place,
\-\2
\+\1
\+
it \ does not \ change the \ sum of \ displacements. It gives the term
\-\2
\+\1
\+
m     . Matrices counted by the \ term m      are sums of elements
\-\2\ i-1,j\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i,j-1
\+\1
\+
of previous rows which moments are increased by adding a new ele-\A
\-\2
\+\1
\+
ment into the corresponding \ column. They have the required dimen-\A
\-\2
\+\1
\+
sionality. Their moments are increased by permutations of the last
\-\2\/
\+\1
\+
element into the first column.\,
\-\2
\+\1
\+
\48.9 Spearman correlation coefficient\,
\-\1
\+
\+
   The \ sum \ of \ differences \ of \ permutations \ against \ the unit
\-
\+
\+
permutation \ is 0. \ These differences \ can be \ either positive or
\-
\+
\+
negative, but the sum of \ squared differences is always positive.
\-\/
\+
\+
For exemple   1   2   3   4   5   \,
\-
\+
\+
              5   2   4   3   1\,
\-
\+
\+
              4   0   1  -1  -4\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ ---------------------------
\+\1
\+
             16   0   1   1  16   \7S \1= 34\,
\-
\+
\+
     If we divide obtained values \ by the largest possible sum of
\-\/
\+
\+
squares, \ which is \ here 40, \ we obtain \ values going from 0 till
\-
\+
\+
1 which characterize \ permutations and are known \ as the Spearman
\-
\+
\+
correlation coefficient. It is used for evaluation of probability
\-\/
\+
\+
of an obtained rank statistics.\,
\-
\+
\+
    Till now we have worked with permutations which could be read
\-
\+
\+
from one side, only. But recall that we introduced as a matrix o-\A
\-
\+
\+
perations: \ transposing \ and \ transversing, \ which changed permuta-\A
\-
\+
\+
tions. Our \ symbols determine \ from which \ side they \ must be read
\-
\+
\+
(with \ some exceptions \ as W, \ A, 8, \ T and other symmetric sym-\A
\-
\+
\+
bols). Imagine now, that \ a permutation is represented by a string
\-\/
\+
\+
of colored beads as\,
\-
\+
\+
\ \ \ \ \ \ \ \ \ \ \ \ \ \ (red)-(blue)-(white)-(green)-(yellow)\,
\-
\+
\+
   If we find it accidentally, we can not tell from which side we
\-\/
\+
\+
should read it. The result is \ that we can not distinguish a half
\-
\+
\+
of permutations \ as: 123<-->321; 213<-->312; \ 132<-->231. The name
\-\/
\+
\+
of such a group, which \ is undistinguishable at readings from both
\-
\+
\+
sides is dihedral.\,
\-
\+
\+
     Still more \ complicated the situation \ is, if the \ string of
\-\/
\+
\+
colored beads forms a necklage. Then we can not find not only the
\-
\+
\+
reading direction, but also \ the beginning of a permutation. Thus
\-
\+
\+
we \ have undistinguishable \ permutations: (123-231-312)<-->(213-
\-\/
\+
\+
132-321).\,
\-
\+
\+
     From problems \ connected with these groups, \ we mention only
\-\/
\+
\+
the task of menages: n maried couples should be seated at a round
\-
\+
\+
table in such a way that \ a woman should seat between 2 males but
\-\/
\+
\+
not alongside her husband. For n = 4 there are 2 seating orders\,
\-
\+
\+
         B   a   C                C   a   D\,
\-
\+
\+
         d   *   b                d   *   b\,
\-
\+
\+
         A   c   D                B   c   A\,
\-
\+
\+
     the menage numbers are:\,
\-
\+
\+\8\ \ p
\1n \8p   \10   1   2   3   4   5   6\,
\-
\+\8--k----------------------------
\+\ \ p
  p   \12  -1   0   1   2  13  80\,
\-
\+
\+
   The negative \ value at n \ = 1 is necessary \ for complying with
\-\/
\+
\+
the reccurent relation:\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (n+1)
\1\ \ \ \ \ \ (n - 2)U\  = n(n - 2)U\ \ \ + nU\ \ \  +4(-1)\ \ \ \ \      (8.17)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ n\ \ \ \ \ \ \ \ \ \ \ \ n-1\ \ \ \ n-2
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6
\1   For example: 3U\  = 15*2 + 5*1 + 4(-1)\  = 39. \,
\-\2\ \    \ \ \ \ \ \ \ \ \ \ \ \ \ 5
\+\1
\+
\48.11 Groups of symmetry\,
\-\1
\+
\+
   \ \ Till \ now \ we \ have \ supposed \ that \ vectors \ are defined in
\-
\+
\+
multidimensional \ space and \ that the \ number of \ permutations is
\-
\+
\+
determined by the dimensionality of \ the space. It is possible to
\-
\+
\+
define groups \ which are only \ isomorphic with some \ groups Sö of
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n
\+\1
\+
cyclic permutations. \ As an example \ we introduce the \ group of 6
\-
\+
\+
matrices with 2 rows and columns, which is isomorphic with S\ :\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 3
\+\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ p\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ p
\4I \8p\11   0\8p               \4A \8p\11   0\8p                \4D \8p\1-1/2  \0r\13/2\8p  \,
\-\ \ p\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ p
\+\ \ p\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ p
\+\ \ p\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ p
  p\10   1\8p                 p\10  -1\8p                  p \0r\13/2  1/2\8p\,
\-\1
\+
\+\8\ \ p\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \  p\ \ \ \ \ \ \ \ \ \ \ p
\4G \8p\1-1/2  -\0r\13/2\8p         \4E \8p \11/2  \0r\13\ 2\8p           \4P \8p\1-1/2  -\0r\13/2\8p\,
\-\ \ p\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \  p\ \ \ \ \ \ \ \ \ \ \ p
\+\ \ p\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \  p\ \ \ \ \ \ \ \ \ \ \ p
\+\ \ p\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \  p\ \ \ \ \ \ \ \ \ \ \ p
  p\1-\0r\13/2  -1/2\8p           p\1-\0r\13/2 -1/2\8p\ \            p\0r\13/2  -1/2\ \8p\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\1
\+
     If we multiply by these matrices 2 dimensional matrices from
\-\/
\+
\+
the right \ and from the \ left, there remains \ constant only their
\-
\+
\+
Euclidean length, \ and not the \ sum of their \ elements. Moreover,
\-
\+
\+
there remains constant also their \ determinant, if you know, what
\-
\+
\+
is it. The effect of these matrices can be shown on the unit cir-\A
\-
\+
\+\2
\1cle. Operators \4I \1and \4A \1are \ mutually orthogonal, the other matri-\A
\-\/
\+
\+\2
\1ces rotate vectors for 2/3\7P\1, it is 120 degrees.\,
\-
\+
\+
   Instead of \ cycles of different lenghts, \ new symmetry elements
\-
\+
\+
appear in the 3 dimensional geometry.\,
\-
\+
\+
   There \ are \ rotation \ axes. \ If \ a \ figure \ has \ k dimensional
\-
\+
\+
rotation axis, \ it has k equivalent positions \ and returns to its
\-\/
\+
\+
original \ position after \ k translations, which \ rotate it around
\-\/
\+
\+
the axis. \,
\-
\+
\+
   The other \ kind of symmetry elements \ is the reflection plane,
\-
\+
\+
which reflects a figure as a double sided mirror.\,
\-
\+
\+
   These basic \ symmetry elements combine \ in different ways \ and
\-
\+
\+
they \ systems \ are \ known \ under \ different \ names. \,
\-
\+
\+
\48.12 Vierer gruppe\,
\-\1
\+
\+
     One system of 4 unit permutation matrices 4*4 is:\,
\-
\+
\+\8\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\4I  \8pp \11             \8pp      \4A \8pp     \11\ \ \ \ \ \ \ \ \ \8pp\,
\-\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
   pp     \11         \8pp        pp  \11\ \ \ \ \ \ \ \ \ \ \ \ \8pp\,
\-\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
   pp         \11     \8pp        pp              \11\8pp\,
\-\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
   pp             \11 \8pp        pp         \11\,
\-
\+
\+\8\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\4B  \8pp         \11     \8pp      \4C \8pp              \11\8pp\,
\-\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
   pp             \11 \8pp        pp         \11\ \ \ \ \ \8pp\,
\-\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
   pp  \11            \8pp        pp     \11\ \ \ \ \ \ \ \ \ \8pp\,
\-\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\ \ \ pp\ \ \ \ \ \ \11        \8pp        pp  \11\ \ \ \ \ \ \ \ \ \ \ \ \8pp\,
\-\1
\+
\+
     If \ we \ imagine \ that \ these \ matrices \ permute \ vertices of
\-\2\/
\+\1
\+
a square, \4I \1is \ the identity, which leaves \ the square unchanged,
\-\2
\+\1
\+
\4A \1and \4C \1reflect \ according to the \ planes perpendicular with \ the
\-\2
\+\1
\+
sides of the square and \4B \1rotates \ the square about an axis going
\-\2
\+\1
\+
through its \ center. The group contains \ all possible products of
\-\/
\+
\+
these four matrices.\,
\-
\+
\+
     With the \ group of these 4 matrices \ such groups of matrices
\-\/
\+
\+
are \ isomorphic, \ which \ are \ obtained \ by \ multiplying \ the unit
\-
\+
\+
permutation matrices from the left \ by a suitable matrix and from
\-
\+
\+
the right by its inverse\,
\-
\+
\+\2\ \ \ -1
\4UPU   \1= \4P\,
\-\2\ \ \ \ \ \ \ \  a
\+\1
\+\2\ \ -1
\4UU   \1= \4I\,
\-\1
\+
\+
     Using Hadamard matrices (see later), we get another group of
\-
\+
\+
four matrices\,
\-
\+
\+
\4I  \8pp \11             \8pp\ \ \ \ \ \ \ \4A  \8pp \11             \8pp\,
\-\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
   pp     \11         \8pp\ \ \ \ \ \ \    pp     \11         \8pp\,
\-\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
   pp         \11     \8pp\ \ \ \ \ \ \    pp        \1-1     \8pp\,
\-\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
   pp             \11 \8pp\ \ \ \ \ \ \    pp            \1-1 \8pp\,
\-\1
\+
\+
\4B  \8pp \11             \8pp\ \ \ \ \ \ \ \ \4C  \8pp \11             \8pp\,
\-\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
   pp    \1-1         \8pp\ \ \ \ \ \ \ \    pp    \1-1         \8pp\,
\-\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
   pp         \11     \8pp\ \ \ \ \ \ \ \    pp        \1-1     \8pp\,
\-\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
   pp            \1-1 \8pp\ \ \ \ \ \ \ \    pp             \11 \8pp\,
\-\1
\+
\+
     Notice, that \ corresponding matrices have \ identical traces,
\-
\+
\+
which are known as characters of the group.\,
\-
\+
\,
\-
\+
\,
\-
\+
\+
\"9. N A I V E   M A T R I C E S   \ I N   L 0 V E R  \,
\-\1
\+
\+
\" T R I A N G U L A R   F O R M\,
\-\1
\+
\+
\"\,
\-\1
\+
\+
\49.1 Another factorial function\,
\-\1
\+
\+
   Before we will study all naive matrices \ \4N\1, we will deal \ with
\-\/
\+
\+
the naive \ matrices in lower \ triangular form, which \ form a sub-\A
\-
\+
\+
group of naive matrices. The other naive matrices can be obtained
\-
\+
\+
from them by permuting columns with the unit permutation matrices
\-
\+
\+
from right. Recall \ that naive matrices have one \ unit element in
\-
\+
\+
each row. \ If a matrix is in \ the lower triangular form, then all
\-
\+
\+
its nonzero elements must be on or below the main diagonal. Simi-\A
\-
\+
\+
larly, if a matrix is in the \ upper triangular form, then all its
\-
\+
\+
nonzero elements \ must be on \ or over the \ main diagonal. From all
\-
\+
\+
permutation matrices only the \ identity matrix \4I \1has the triangu-\A
\-
\+
\+
lar form. \ But it exists simultaneously \ in both triangular forms
\-\/
\+
\+
similarly as all diagonal matrices. \,
\-
\+
\+
     Because all rows of the naive matrices are independent, the-\A
\-\/
\+
\+
re is only one opportunity in the first row for the unit element,
\-
\+
\+
two places are in the second \ row and always one possibility more
\-
\+
\+\2
\1in each consecutive \ row. This situation is just \ opposite to the
\-
\+
\+\2
\1construction \ of permutation \ matrices. There \ the possibilities,
\-
\+
\+\2
\1how to \ place an unit element, \ decreased in every row. \ But both
\-
\+
\+\2
\1approaches \ give the \ same result. \ Therefore there \ are n! naive
\-
\+
\+\2
\1matrices in the lower triangular form, or in the case of transpo-\A
\-
\+
\+\2   \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1sed naive matrices \4N  \1in the upper triangular form. We have shown \,
\-
\+
\+
how the transposed naive matrices \ can be mapped onto points with \,
\-
\+
\+
natural coordinates in m-dimensional cubes.\,
\-
\+
\+
   If \ we leave \ the first \ column as \ a dummy \ variable for \ the
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0
\1center of the \ coordinate system: \4e\1ö = 1, \ the naive matrices can \,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j
\+\1
\+
be compared with terms of the formal multiplication\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n\ \0(  \2n    \0)
\1\ \ \ \ \ \ \ \ (1)(1 + a)(1 + a + b)... = \7P\ \ \ \ S\   \4e\ \ \     \1(9.1)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i=1\09 \2j=1 j \00
\+\1
\+\2\ \ \ \ \    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1     All transposed matrices \4N  \1are \ placed in m-dimensional rec-\A
\-\/
\+
\+
tangular parallepiped \ which sides are \ 0,1,2,3,..,(n-1). We will
\-
\+
\+
repeat with these matrices all classifications as with the permu-\A
\-
\+
\+
tation matrices. \ Matrices with m rows form \ in these paralepides
\-
\+
\+
the factorial plane simplices. Compare them with the generating func-\A
\-
\+
\+
tion of \ partitions, explained in Chapter \ 5.10, where the number
\-\/
\+
\+
of elements decreased, too, but from other reasons.\,
\-
\+
\+
\49.2 Decreasing order classification\,
\-\1
\+
\+
   In \ preceding chapter \ we \ have \ introduced Young \ tables and
\-
\+
\+
compared them with convolutions having \ cycles of length 1 and 2,
\-
\+
\+
only. \ For naive \ matrices the \ Young tables \ correspond to naive
\-
\+
\+
matrices \ which partial \ column sums \ are always \ ordered in \ the
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k\ \ \ \ \ \ \ \ \ \ k
\1decreasing order: \7S\ \   \1n\ \  \9> \7S\ \ \ \1n\ \ \ \ \ .\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i=1\ \ ij\ \ \ \ i=1\ i,j+1
\+\1
\+
For example two naive matrices n=3 are excluded by this rule:\,
\-
\+
\+
   1   0   0                 1   0   0\,
\-
\+
\+
   0   1   0                 1   0   0\,
\-
\+
\+
   0   1   0                 0   0   1\,
\-
\+
\+
\49.3 Stirling numbers of the first kind\,
\-\1
\+
\+
     These numbers count the \ naive matrices classified according
\-\/
\+
\+
to the number k of elements on the main diagonal\,
\-
\+
\+
\ \ \ \ \ \ \ \ \ \ \ \ \ s\ \  = (n - 1)s\ \ \ \ \  +s\ \ \ \ \ \ \       (9.2)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ nk\ \ \ \ \ \ \ \ \ \ \ n-1,k\ \ \ n-1,k-1
\+\1
\+
   There are (n \ - 1) places under the diagonal \ in the n-th row
\-\/
\+
\+
which can \ be added to each \ naive matrix with k elements \ on the
\-
\+
\+
main diagonal without changing k. This multiplies the first term.\,
\-
\+
\+
If we \ add 1  , we \ increase the number \ of elements on \ the main
\-\2\ \ \ \ \ \ \ \ \ \ \ \ nn\/
\+\1
\+
diagonal counted by the second term. See Table 8.2. \,
\-
\+
\+
     It is not \ all, what can be told \ about the Stirling numbers
\-\/
\+
\+\2
\1of \ the first \ kind. If \ \ we multiply \ them directly \ with powers \,
\-
\+
\+\2\ (j-1)
\12      we get a table which row sums are equal to the half of the
\-
\+
\+
higher factorial (i+1)!/2 as in\,
\-
\+\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1m=1 \8p \11                      \7S \8p  \11\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  2 \8p \11    2                   \8p  \13\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  3 \8p \12    6    4              \8p \112\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  4 \8p \16   22   24   8          \8p \160\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  5 \8p\124  100  140  80  16      \8p\1360\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (i-j)
\1   When \ we multiply \ them with \ powers 2ööööö, then the row sums
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i
\1 give \ (2i \ +1)!/i!2ö or products of m odd \ numbers \ 1*3*5*. The
\-
\+
\+\2
\1factorial is depleted of even numbers.\,
\-
\+
\+\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1m=1 \8p   \11                    \7S\8p   \11\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  2 \8p   \12   1                 \8p   \13\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\-\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\-\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\1
  3 \8p   \18   6   1             \8p  \115\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  4 \8p  \148  44  12   1         \8p \1105 \,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\1
\+
     If the columns are \ multiplied with +/- signs alternatively,
\-\/
\+
\+
then in the first case the row \ sums are zero, except m=2, and in
\-
\+
\+\ \ \ \ ööööööööööööööööööööööööööööööööööööööööööööööööööööööööööö
the second they give lower odd factorials. It is given without
\-\/
\+
\+ööööööööööööööööööööööööööööööö
a proof, which will be shown later.\,
\-
\+
\+
\49.4 Euler polynomials\,
\-\1
\+
\+
   The Euler numbers (Table \ 8.10) classify naive matrices accor-\A
\-\/
\+
\+
ding to the \ number k of nonzero columns. We can \ add the new ele-\A
\-
\+
\+
ment in \ the last row into \ k already occupied columns or \ we can
\-\/
\+
\+
put it into (n - k) unoccupied \ columns. It is clear that here the
\-\/
\+
\+
index k can not be 0, as \ it was convenient at permutation matri-\A
\-\/
\+
\+
ces.\,
\-
\+
\+
     The Euler numbers are just a beginning of a serie of polyno-\A
\-\2\/
\+\1
\+
mials E (r) where \ r = 1. The Euler \ polynomial E (2) is obtained
\-\2\ \ \ \    n\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \    n
\+\1
\+
if we \ multiply each previous \ column, except the \ first one, by
\-
\+
\+
powers of 2 as if elements of naive matrices in columns had signs
\-
\+
\+
+/- \ and all \ their combinations \ were acceptable. \ The resulting \,
\-
\+
\+
numbers are given in the \ Table 9.1, which elements are differen-\A
\-
\+
\+
ces of the matrix, obtained by \ multiplying the matrix of the Eu-\A
\-\/
\+
\+
ler numbers with the matrix of m th powers of 2:\,
\-
\+\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
                     p \11   1   1   1\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
                     p     \12   2   2\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
                     p         \14   4\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
                     p             \18\,
\-
\+\8---------------------k--------------
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\11                    \8p \11   1   1   1\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\11   1                \8p \11   3   3   3\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\11   4   1            \8p \11   9  13  13\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\11  11  11   1        \8p \11  23  67  75\,
\-
\+
\+
\4Table 9.1  Euler polynomials E\ (2)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \     n
\+\1
\+\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1k   \8p  \11     2     3     4     5     6  \8p   \7S\,
\-\1
\+\8----k-----------------------------------k----
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1n=1 \8p  \11                                \8p   \11\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  2 \8p  \11     2                          \8p   \13\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  3 \8p  \11     8     4                    \8p  \113\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  4 \8p  \11    22    44     8              \8p  \175\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  5 \8p  \11    52   264   208    16        \8p \1541\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  6 \8p  \11   114  1208  2416   912    32  \8p\14683 \,
\-
\+
\+
   There are interesting the row \ sums. They are generated by the
\-\/
\+
\+
formal equation \,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ m
\1\ \ \ \ \ \ \ \ \ \ \ [1 + E(k)]\  = 2E(m)                   (9.3)\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \0(\11\0)      (\11\0)
\1where E(k)ö = E(i) and E(0) = 1. Then 2E(1)=öööE(0)ö+öööE(1), from
\-\0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ 9\10\00      9\11\00
\+\1
\+
it \ E(1) = 1 and so on. These \ numbers will appear later many ti-\A
\-\/
\+
\+
mes, as \ differences of complete \ plane simplices, but \ here they
\-
\+
\+\2
\1appeared as an extension of factorial simplices or as the product
\-
\+
\+\2
\1of the \ matrix of the Euler \ numbers with the diagonal \ matrix of
\-\/
\+
\+\2\ \ \ \ \ \ \ \ j-1
\1powers 2   .\,
\-
\+
\+
\49.5 Mac Mahon numbers\,
\-\1
\+
\+
     This statistics (Table 8.11) counts naive matrices according
\-
\+
\+
their moments, which are obtained by multiplying naive matrices by
\-
\+
\+
the diagonal matrix with indices \ \7D\1(j - 1). The reccurence is obtai-\A
\-
\+
\+
ned from lesser \ matrices by repeating n times terms \ of the last
\-
\+
\+
but one row \ of the table of Mac Mahon \ numbers with equal or in-\A
\-\/
\+
\+
creased moments. The moment remains the same, if the unit element
\-
\+
\+
in the last row is placed in \ the first column and it is increased
\-
\+
\+
till \ (n-1), \ if \ it \ is \ placed \ in \ the \ n th column. From each
\-
\+
\+
matrix with (n-1) rows n new matrices are produced. Their moments
\-
\+
\+
are counted as e.g. for n = 5:\,
\-
\+
\+\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1Moments :         \8p  \10   1   2   3   4   5   6   7   8   9  10\,
\-
\+\8------------------k---------------------------------------------
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\14 rows and columns\   1   3   5   6   5   3   1\,
\-\8------------------k---------------------------------------------
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\16.term            \8p                          \11   1   1   1   1\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\15.term            \8p                      \13   3   3   3   3\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\14.term            \8p                  \15   5   5   5   5\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\13.term            \8p              \16   6   6   6   6  \,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\12.term            \8p          \15   5   5   5   5\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\11.term            \8p      \13   3   3   3   3\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\10.term            \8p  \11   1   1   1   1\,
\-
\+\8------------------k-------------------------------------------
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1Mac Mahon numbers \8p  \11   4   9  15  20  22  20  15  9   4   1 \,
\-
\+\8
\+\1
   This \ scheme \ gives \ automatically \ the \ factorials.\,
\-
\+
\+
\49.6 Stirling numbers of the second kind\,
\-\1
\+
\+
   When we \ look on the sequence \ aac, we see that \ in its matrix
\-
\+
\+
the column b is missing. We excluded such strings as faulty Young
\-
\+
\+
tables or \ convolutions, but there were \ not allowed also strings
\-
\+
\+
as abb, where b appeared twice but a only once. There is a diffe-\A
\-
\+
\+
rence in these two cases: If not all columns are not occupied suc-\A
\-
\+
\+
cessively, we jump in the space. \ Therefore we will now count all
\-
\+
\+
naive matrices in the lower triangular form with successively oc-\A
\-\/
\+
\+
cupied columns. Their reccurence is \,
\-
\+
\+
\ \ \ \ \ \ \ \ \ \ \ s\ \  = 1;   s\ \  = js\ \ \ \ \  + s\ \ \ \ \ \ \     (9.4)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ 11\ \ \ \ \ \ \ \ \ ij\ \ \ \ \ i-1,j\ \ \ \ i-1,j-1
\+\1
\+
   It is possible to place \ a new element into j already occupied
\-\/
\+
\+
columns and \ only one possibility, how to increase \ the number of
\-
\+
\+
occupied \ columns. In \ such a way, we obtain \ a table of \ numbers
\-\/
\+
\+
which are known as the Stirling numbers of the second kind.\,
\-
\+
\+
\4Table 9.2  Stirling numbers of the second kind\,
\-\1
\+
\+\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1j   \8p   \11    2    3    4    5    6  \8p   \7S\,
\-\1
\+\8----k-------------------------------k-----
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1n=1 \8p   \11                           \8p   \11\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  2 \8p   \11    1                      \8p   \12\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  3 \8p   \11    3    1                 \8p   \15\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  4 \8p   \11    7    6    1            \8p  \115\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  5 \8p   \11   15   25   10    1       \8p  \152\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  6 \8p   \11   31   90   65   15    1  \8p \1203\,
\-
\+
\+
   Stirling numbers of the second \ kind are inverses of the Stir-\A
\-\/
\+
\+
ling numbers of \ the first kind or Stirling \ numbers of the first
\-
\+
\+
kind are inverses of the Stirling numbers of the second kind, when
\-
\+
\+\2
\1one from both matrices ( Table \ 8.11 and Table 9.2) is multiplied
\-\/
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i-j
\1with alternating signs (-1)   .\,
\-
\+
\+
   Stirling found \ numbers bearing his name, when he compared po-\A
\-\2\/
\+\1
\+
wers of any \ number t with its factorial moments \ (t)  defined by
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k
\+\1
\+
products (t)  \ = t(t - 1)...(t - \ k + 1). Stirling numbers of \ the
\-\2\ \ \ \ \ \ \ \ \ \ \ \ k
\+\1
\+
first kind transform sums and differences of powers into factori-\A
\-\2
\+\1
\+\2
\1al moments as in: (4) \ = 24 = 2*4 - 3*16 + 1*64. Stirling numbers
\-
\+
\+\2
\1of the second \ kind invert sums of factorial \ moments into powers
\-
\+
\+\2\ \ \ \ \ \ \ \ \ 3
\1as in : 4  = 64 = 1 *4 + 3*12 \ + 1* 24. Here t can substitute ra-\A
\-\/
\+
\+
tional numbers, too.\,
\-
\+
\+
   The \ row sums \ of Stirling numbers of \ the second \ kind, which
\-\/
\+
\+
count naive matrices in the \ lower triangular form with successi-\A
\-\/
\+
\+
vely occupied columns, are obtained as a selfgenerating function \,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n-1 \ \  \ \ \ \ \ \ i
\1\ \ \ \ \ \ \ \ \ \ \ S(n) = (S\  + 1)\ \ \ \ , where S\  = S\      (9.5)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  i\ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ i
\+\1
\+
or using \ matrices. Then these \ numbers S(n) are \ obtained on the
\-
\+
\+
diagonal of the \ product. We can multiply the \ product further by
\-\/
\+
\+
the diagonal index matrix to obtain moments\,
\-
\+
\+\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
                    p  \11   1   1   1 \8p \11\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
                    p      \11   2   3 \8p     \12\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
                    p          \11   3 \8p         \13\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
                    p              \11 \8p             \14\,
\-
\+\8--------------------k----------------k---------------
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1    1               \8p  \11   1   1   1 \8p \11   2   3   4\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1    1   1           \8p  \11   2   3   4 \8p \11   4   9  16\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1    1   1   2       \8p  \11   2   5  10 \8p \11   4  15  40\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1    1   1   2   5   \8p  \11   2   5  15 \8p \11   4  15  60\,
\-
\+
\+
     Notice, \ that the \ matrix of \ Stirling sums \ begins with two
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \/
\+
\+\2
\11 and on the diagonal of the product is only one 1 and then imme-\A
\-
\+
\+\2
\1diately  \ higher sums follow. In \ the final product the \ sums are
\-
\+
\+\2
\1multiplied with \ corresponding powers. If we \ label the matrix of
\-
\+\8
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1binomial \ coefficients as \ \4B \1, then \ we can \ consider its product
\-
\+\8
\+\1
with \ the \ diagonal \ matrix \ \7D\1(i) \ as \ the logarithmic difference
\-
\+\8
\+\1
d(log\4S\1), similarly as it was \ derived in Chapter 7.4. The inverse
\-
\+\8
\+\2
\1matrix of \ sums of Stirling numbers \ of the second kind \ has ele-\A
\-\2\/
\+\8
\+\2\ \ \ \ \ \ \ \ \ -1\       -1
\1ments : s   = 1; s      \2= \1-[S   /S ]; s   = 0 otherwise.\,
\-\2\ \ \ \ \ \ \ \ \ jj\       j-1,j\ \ \ \ \ \ j-1\ \ j\ \ \ \ ij
\+\1
\+
   We have shown one relation between Stirling numbers of the se-\A
\-\/
\+
\+
cond kind with the binomial coefficients. But there appears still
\-
\+
\+
another relation. The difference of \ two successive sums is gene-\A
\-\/
\+
\+
rated again by a binomial\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n-2
\7\ \ \ \ \ \ \ \ \ \ \ \ \ D\1S\ = S\  - S\ \ \ = (S\ \ \  + 1)\ \ \       (9.6)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ n\ n\ \ \ n\ \ \ \ n-1\ \ \ \ k+1
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k
\1where again we put Sö = Sö. E.g.: Sö - Sö = 1*1 +4*2 + 6*5 + 4*15
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k\ \ \ \  \ \ \ \ 6\ \ \ \ 5
\+\1
\+\2
\1+ 1*52 = 151.\,
\-\2
\+\1
\+
   The Stirling numbers of the second kind can be defined by the
\-
\+
\+
formal relation\,
\-
\+
\+\2\ 1\ \ \ n\ \ \ n-1\ \ \ \ \ \ \ \ \ \ n-1\ \ \ \ \ \ \ \ \ \ \ \ n-2\ \ \ \ \ \ \ \ \ \ \ \ \ 0
\7D\ \1(m)\ \2= \1m\ \ \  [(1 +1/m)\ \ \  + (1 + 1/m)\ \ \ ...+(1 - 1/m)\ ]\,
\-\2n
\+\1
\+
Inserting m = 1, we obtain numbers S(n,2): \,
\-
\+
\+\2\ 1\ n\ \ \ \ n-1\ \ n-1\ \ \ \ n-2\ \ \ \ \ \ 0
\7Dö\11ö = 1ööö[2ööö + 2ööö...+ 2ö]. The other numbers are derived by
\-\2m
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ m\ n\ \ \ \ \ \ \ \ \ \ \ \ m\ n-1\ \ \ \ m-1\ n-1
\1the relation \7Dö\11ö = (m + \ 1)\7D\1ö1ööö + \7D\1ööö1ööö under the condition
\-
\+
\+\2\ 0\ 0
\7D\ \11\  = 1.\,
\-
\+
\+
   The differences of the Stirling numbers of the second kind \,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n-1\ m
\1S(m,n) - S(m-1,n) = \7D\ \ \ \12\  form the following Table (9.4).\,
\-
\+
\+
\4Table 9.4 Differences of Stirling numbers of the second kind\,
\-\1
\+
\+\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1n   \8p   \11    2    3    4    5    6 \8p  \7S\,
\-\1
\+\8----k------------------------------k----
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1m=1 \8p   \11                          \8p  \11\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  2 \8p   \10    1                     \8p  \11\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  3 \8p   \10    2    1                \8p  \13\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  4 \8p   \10    4    5    1           \8p \110\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  5 \8p   \10    8   19    9    1      \8p \137\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  6 \8p   \10   16   65   55   14    1 \8p\1151\,
\-
\+
\+\2\ \ \ \ \ \   \ \ \ \ \ 2\ 6\ \ \ \ \ \ \ \ \ \ 3\ \ \ \ \ \ \ \ 2\ \ \ \ \ \ \ \ \ 1\ \ \ \  \ \ \ 0
\1     E. g.: \7Dö\12ö = 8[(3/2)ö + (3/2)ö + \ (3/2)ö + (3/2)ö] = 65.
\-
\+
\+\2
\1     This number \ counts naive matrices in \ lower triangular form
\-\/
\+
\+\2
\1with \ 3 occupied columns \ and 6 rows, \ obtained from \ 15 matrices
\-
\+
\+\2
\1counted by S(5,2) \ by adding the unit element \ into the 3. column \,
\-
\+
\+\2
\1and 2*25 matrices counted by \ S(5,3) increased by adding the unit
\-
\+
\+\2
\1element into two first columns.\,
\-
\+
\+
\49.7 Substirlings\,
\-\1
\+
\+
     In \ analogy with \ subfactorials defined \ in Chapter \ 8.6, we
\-\/
\+
\+
introduce numbers, \ which we will \ call substirlings. They \ count
\-
\+
\+
naive matrices in lower triangular form with successively occupi-\A
\-
\+
\+
ed columns in \ another order, according to the \ number of columns
\-
\+
\+
containing just one nonzero element. \ We have shown that such or-\A
\-
\+
\+
bits are differences of plane simplices, therefore even now these
\-
\+
\+
matrices \ form differences. \ Their matrix \ is in \ the Table \ 9.5,
\-
\+
\+\2
\1which is \ completed by the \ row and column \ indexed from 0. \ E.g.
\-\2\/
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 4  2\ 2
\1s  = 4 counts \4N\1: a ,a b ,abba,abab.\,
\-\2\ 40
\+\1
\+
\,
\-
\+
\+
\4Table 9.5 Substirlings\,
\-\1
\+
\+\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1n\   \8p  \10    1    2    3    4    5 \8p  \7S\,
\-\2\ 1
\+\8----k-----------------------------k---
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1n=0 \8p  \11                          \8p  \11\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  1 \8p  \10    1                     \8p  \11\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  2 \8p  \11    0    1                \8p  \12\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  3 \8p  \11    3    0    1           \8p  \15\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  4 \8p  \14    4    6    0    1      \8p \115\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  5 \8p \111   20   10   10    0    1 \8p \152\,
\-
\+
\+
     Again, \ there appeared \ binomial coefficients \ as generating
\-\/
\+
\+
factors. Naive matrices without \ any columns, containing just one
\-
\+
\+
unit \ element, are \ combined with \ n  columns \ with just one unit
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1
\+\1
\+
element and the result gives \ the matrix elements. Therefore sums
\-
\+
\+\2
\1of Stirling \ numbers of the second \ kind are obtained by the for-\A
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \        \/
\+\1
\+\2\ \ \ \ \   \ \ \ \ \ \ \          \        n\ \ \ \ \ \  \ k
\1mal binomial  : S  = (s   + 1)   where s  = s  .\,
\-\2                \ n\ \ \ \ \ n0\ \  \ \ \ \ \ \ \ \ \ \   \ \ \ \ \ k0
\+\1
\+
     Another possibility, how the \ Stirling numbers of the second
\-
\+
\+
kind \ are obtained, is the direct count of corresponding matrices
\-
\+
\+
arranged according to the powers of a. E.g.:\,
\-
\+
\+
a\,
\-
\+
\+
ab           aa\,
\-
\+
\+
abb, abc;    aab, aba;    aaa\,
\-
\+
\+
     We get the \ table, in which naive natrices \ are arranged ac-\A
\-\/
\+
\+
cording to the rows containing the symbol a. Again they are obta-\A
\-
\+
\+
ined by multiplying lower matrices (without this symbol) by bino-\A
\-\/
\+
\+
mial coefficients, showing possibilities:\,
\-
\+
\+\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1n   \  1   2   3   4   5   6  \    \7S\,
\-\8----k------------------------k----
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1m=1 \8p \11\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \8p   \11\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  2 \8p \11   1                  \8p   \12\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  3 \8p \12   2   1              \8p   \15\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  4 \8p \15   6   3   1          \8p  \115\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  5 \8p\115  20  12   4   1      \8p  \152\,
\-\8\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  6 \8p\152  75  50  20   5   1  \8p \1203\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\1
\+
     Substirlings are in their turn \ again just sums of the asso-\A
\-\/
\+
\+
ciated \ Stirling numbers \ of the \ second kind, \ which count naive
\-
\+
\+
matrices in the lower triangular \ form without empty columns, ha-\A
\-
\+
\+
ving column sums at least m = 2. Their reccurence is given by the
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k\/
\+\1
\+
formula \,
\-\2
\+\1
\+
\ \ \ \ \ \ \ \ \ \ \ \ \ a\ \  = ja      + (i-1)a\ \ \ \ \ \ \ \ \ \ \ \ \ (9.7)\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ ij\ \ \ \ \ i-1,j         i-2,j-1
\+\1
\+
and they are given in Table 9.6\,
\-
\+
\+
\4Table 9.6 Associated Stirling numbers of the second kind\,
\-\1
\+
\+\8\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1n  \8p \10   1   2   3    \8p  \7S\,
\-\1
\+\8---k------------------k-----
\+\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1m=0\8p \11                \8p  \11\,
\-\8\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  1\8p \10   0            \8p  \10\,
\-\8\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  2\8p     \11            \8p  \11\,
\-\8\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  3\8p     \11            \8p  \11\,
\-\8\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  4\8p     \11   3        \8p  \14\,
\-\8\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  5\8p     \11  10        \8p \111\,
\-\8\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1  6\8p     \11  25  15\ \ \ \ \8p\ \141\,
\-
\+
\+
\49.8 Space of 4 statistics\,
\-\1
\+
\+
     We have \ mapped naive matrices in \ the lower triangular form
\-\/
\+
\+
on \ points \ of \ rectangular \ n-dimensional \ parallepipeds. \ These
\-
\+
\+
points are \ classified by 3 different \ statistics Euler, Stirling
\-
\+
\+
and Mac Mahon, \ in 3 directions. They split the \ space behind the
\-
\+
\+
Euclidean one. These statistics distribute points differently, as
\-
\+
\+
it is shown on the \ following Fig.9.1 for 2 dimensional space and
\-\/
\+
\+
on the scheme for 3 dimensional space.\,
\-
\+
\+
\4Table 9.7 Scheme of 3 statistics\,
\-\1
\+\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
          p  \1Stirling      \8p      \1Mac Mahon\,
\-\8\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
          p \16  \ \ \ \ \ \ \ \ \ \ \ \ \8p\,
\-\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
          p     \18   \ \ \ \ \ \ \ \8p\,
\-\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
          p     \13   6 \ \ \ \ \ \8p\,
\-\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
          p             \11  \8p  \11   3   5   6   5   3   1\,
\-
\+\8----------k----------------k----------------------------
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1Euler   1 \8p \11              \8p                          \11\,
\-\8\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1       11 \8p \14   7          \8p          \11   2   5   3\,
\-\8\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1       11 \8p \11   4   6      \8p      \13   4   4    \,
\-\8\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1        1 \              1  \   1\,
\-\8----------k----------------k-----------------------------
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
          p \16  11   6   1\ \ \8p\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\1
\+
     We have compared 3 statistics, but the fourth appeared here,
\-\/
\+
\+
too, on the diagonal of \ the Stirling and Euler statistics. Euler
\-
\+
\+
numbers divide naive matrices in the lower triangular form accor-\A
\-
\+
\+
ding to the \ number of occupied columns. Stirling \ numbers of the
\-
\+
\+
second kind count matrices \ which rows are occupied consecutively
\-
\+
\+
and these matrices appear on the crossections of both statistics.ööööööööööö\,
\-
\+
\+
     I do not know, what you think about these coincidencies. But
\-\/
\+
\+
you must admit, that the Euclidean \ space is full of surprises as
\-
\+
\+
a Fairy land. It \ seems to be alive and if \ we try to analyse it,
\-
\+
\+
there appear \ new layers just on \ elementary levels. Euclides was
\-
\+
\+
wrong, when he \ thought that there was no other \ way to his space
\-
\+
\+
then his axioms. He did not \ know what was behind. Different com-\A
\-
\+
\+
binatorial \ functions lead \ through \ this \ maze as \ the Adriane's
\-\/
\+
\+
thread.\,
\-
\+

\=