$SPAD/src/input cycles.input

Timothy Daly December 3, 2016

Abstract

Contents

2

1 License

— license —

--Copyright The Numerical Algorithms Group Limited 1991.

———-

— * —

)set break resume
)spool cycles.output
)set message test on
)set message auto off
)clear all

———-

Examples of Polya-Redfield enumeration methods.

This file is based upon the paper J.H.Redfield ’The Theory of Group-Reduced Distributions’ American J. Math.,49 (1927) 433-455, and is an application of group theory to enumeration problems. It is a development of the work by P.A.MacMahon on the application of symmetric functions and Hammond operators to combinatorial theory.

The theory is based upon the symmetric functions s_{i} which are the sum of the i-th powers of the variables.

The cycle index of a permutation may be represented as a partition. For example, the partition (3^{2}21^{2}) will be used to represent

s_{3}^{2}s_{2}S_{1}^{2}

will indicate that the permutation has two cycles of length 3, one of length 2 and two of length 1.

The cycle index of a permutation group is the sum of the cycle indices of its permutations divided by the number of permutations.

The cycle indices of certain groups are provided. complete n is the cycle index of the symmetric group of order n

— * —

)clear all
)expose EVALCYC
--S 1 of 46
complete 1
--R
--R
--R   (1)  (1)
--R                                 Type: SymmetricPolynomial(Fraction(Integer))

--E 1
--S 2 of 46
complete 2
--R
--R
--R        1       1   2
--R   (2)  - (2) + - (1 )
--R        2       2
--R                                 Type: SymmetricPolynomial(Fraction(Integer))
--E 2
--S 3 of 46
complete 3
--R
--R
--R        1       1         1   3
--R   (3)  - (3) + - (2 1) + - (1 )
--R        3       2         6
--R                                 Type: SymmetricPolynomial(Fraction(Integer))
--E 3
--S 4 of 46
complete 7
--R
--R
--R   (4)
--R     1       1          1          1     2     1         1            1     3
--R     - (7) + - (6 1) + -- (5 2) + -- (5 1 ) + -- (4 3) + - (4 2 1) + -- (4 1 )
--R     7       6         10         10          12         8           24
--R   +
--R      1   2      1     2     1       2     1     4     1   3      1   2 3
--R     -- (3 1) + -- (3 2 ) + -- (3 2 1 ) + -- (3 1 ) + -- (2 1) + -- (2 1 )
--R     18         24          12            72          48         48
--R   +
--R      1      5      1    7
--R     --- (2 1 ) + ---- (1 )
--R     240          5040
--R                                 Type: SymmetricPolynomial(Fraction(Integer))
--E 4

———-

The function elementary n is the nth elementary symmetric function.

— * —

--S 5 of 46
elementary 7
--R
--R

--R   (5)
--R     1       1          1          1     2     1         1            1     3
--R     - (7) - - (6 1) - -- (5 2) + -- (5 1 ) - -- (4 3) + - (4 2 1) - -- (4 1 )
--R     7       6         10         10          12         8           24
--R   +
--R      1   2      1     2     1       2     1     4     1   3      1   2 3
--R     -- (3 1) + -- (3 2 ) - -- (3 2 1 ) + -- (3 1 ) - -- (2 1) + -- (2 1 )
--R     18         24          12            72          48         48
--R   +
--R        1      5      1    7
--R     - --- (2 1 ) + ---- (1 )
--R       240          5040
--R                                 Type: SymmetricPolynomial(Fraction(Integer))
--E 5

———-

The function alternating n is the cycle index of the alternating group having an even number of even parts in each cycle partition.

— * —

--S 6 of 46
alternating 7
--R
--R
--R   (6)
--R     2       1     2    1           1   2      1     2     1     4     1   2 3
--R     - (7) + - (5 1 ) + - (4 2 1) + - (3 1) + -- (3 2 ) + -- (3 1 ) + -- (2 1 )
--R     7       5          4           9         12          36          24
--R   +
--R       1    7
--R     ---- (1 )
--R     2520
--R                                 Type: SymmetricPolynomial(Fraction(Integer))
--E 6

———-

The function cyclic n is the cycle index of the cyclic group — * —

--S 7 of 46
cyclic 7
--R
--R
--R        6       1   7
--R   (7)  - (7) + - (1 )
--R        7       7
--R                                 Type: SymmetricPolynomial(Fraction(Integer))
--E 7

———-

The function dihedral n is the cycle index of the dihedral group — * —

--S 8 of 46
dihedral 7
--R
--R
--R        3       1   3      1   7
--R   (8)  - (7) + - (2 1) + -- (1 )
--R        7       2         14
--R                                 Type: SymmetricPolynomial(Fraction(Integer))
--E 8

———-

The function graphs n is the cycle index of the group of permutations on the edges of the complete graph with n nodes induced by applying the symmetric group to the nodes.

— * —

--S 9 of 46
graphs 5
--R
--R
--R   (9)
--R   1           1   2    1   2     1   3     1   4 2     1   3 4     1    10
--R   - (6 3 1) + - (5 ) + - (4 2) + - (3 1) + - (2 1 ) + -- (2 1 ) + --- (1  )
--R   6           5        4         6         8          12          120
--R                                 Type: SymmetricPolynomial(Fraction(Integer))
--E 9

———-

The cycle index of a direct product of two groups is the product of the cycle indices of the groups. Redfield provided two operations on two cycle indices which will be called cup and cap here. The cup of two cycle indices is a kind of scalar product that combines monomials for permutations with the same cycles.

The cap operation provides the sum of the coefficients of the result of the cup operation which will be an integer that enumerates group-reduced distributions.

We can for example represent complete 2 * complete 2 as the set of objects a a b b

and complete 2 * complete 1 * complete 1 as c c d e.
   The integer cap(complete 2**2,complete 2*complete 1**2) is the number of differ-

ent sets of four pairs.

  a a b b     a a b b    a a b b   a a b b
  c c d e     c d c e    c e c d   d e c c

— * —

--S 10 of 46
cap(complete 2**2,complete 2*complete 1**2)
--R
--R
--R   (10)  4
--R                                                      Type: Fraction(Integer)
--E 10

———-

The integer cap(elementary 2**2,complete 2*complete 1**2) is the number of different

sets of four pairs no two pairs being equal.

    a a b b    a a b b
    c d c e    c e c d

— * —

--S 11 of 46
cap(elementary 2**2,complete 2*complete 1**2)
--R
--R
--R   (11)  2
--R                                                      Type: Fraction(Integer)
--E 11

———-

In this case the configurations enumerated are easily constructed, however the theory merely enumerates them providing little help in actually constructing them. Similarly the number of 6-pairs, first from a a a b b c, second from d d e e f g.

— * —

--S 12 of 46
cap(complete 3*complete 2*complete 1,complete 2**2*complete 1**2)
--R
--R
--R   (12)  24
--R                                                      Type: Fraction(Integer)
--E 12

———-

Same again, but with no equal pairs — * —

--S 13 of 46
cap(elementary 3*elementary 2*elementary 1,complete 2**2*complete 1**2)
--R
--R

--R   (13)  8
--R                                                      Type: Fraction(Integer)
--E 13
--S 14 of 46
cap(complete 3*complete 2*complete 1,elementary 2**2*elementary 1**2)
--R
--R
--R   (14)  8
--R                                                      Type: Fraction(Integer)
--E 14

———-

The number of 6-triples, first from a a a b b c, second from d d e e f g, third from h h

i i j j

— * —

--S 15 of 46
eval(cup(complete 3*complete 2*complete 1, _
     cup(complete 2**2*complete 1**2,complete 2**3)))
--R
--R
--R   (15)  1500
--R                                                      Type: Fraction(Integer)
--E 15

———-

The cycle index of vertices of a square is dihedral 4 — * —

--S 16 of 46
square:=dihedral 4
--R
--R
--R         1       3   2    1     2    1   4
--R   (16)  - (4) + - (2 ) + - (2 1 ) + - (1 )
--R         4       8        4          8
--R                                 Type: SymmetricPolynomial(Fraction(Integer))
--E 16

———-

The number of different squares with 2 red vertices and 2 blue vertices — * —

--S 17 of 46
cap(complete 2**2,square)
--R
--R

———-

The number of necklaces with 3 red beads,2 blue beads and 2 green beads — * —

--S 18 of 46
cap(complete 3*complete 2**2,dihedral 7)
--R
--R
--R   (18)  18
--R                                                      Type: Fraction(Integer)
--E 18

———-

The number of graphs with 5 nodes and 7 edges — * —

--S 19 of 46
cap(graphs 5,complete 7*complete 3)
--R
--R
--R   (19)  4
--R                                                      Type: Fraction(Integer)
--E 19

———-

The cycle index of rotations of vertices of a cube — * —

--S 20 of 46
macro s == powerSum
--R
--R                                                                   Type: Void
--E 20
--S 21 of 46
cube:=(1/24)*(s 1**8+9*s 2**4 + 8*s 3**2*s 1**2+6*s 4**2)
--R
--R
--R         1   2    1   2 2    3   4     1   8
--R   (21)  - (4 ) + - (3 1 ) + - (2 ) + -- (1 )
--R         4        3          8        24
--R                                 Type: SymmetricPolynomial(Fraction(Integer))
--E 21

———-

The number of cubes with 4 red vertices and 4 blue vertices — * —

--S 22 of 46
cap(complete 4**2,cube)
--R
--R
--R   (22)  7
--R                                                      Type: Fraction(Integer)
--E 22

———-

The number of labeled graphs with degree sequence 2 2 2 1 1 with no loops or multiple edges — * —

--S 23 of 46
cap(complete 2**3*complete 1**2,wreath(elementary 4,elementary 2))
--R
--R
--R   (23)  7
--R                                                      Type: Fraction(Integer)
--E 23

———-

with loops allowed but not multiple edges — * —

--S 24 of 46
cap(complete 2**3*complete 1**2,wreath(elementary 4,complete 2))
--R
--R
--R   (24)  17
--R                                                      Type: Fraction(Integer)
--E 24

———-

with multiple edges allowed, but not loops — * —

--S 25 of 46
cap(complete 2**3*complete 1**2,wreath(complete 4,elementary 2))
--R
--R
--R   (25)  10
--R                                                      Type: Fraction(Integer)
--E 25

———-

with both multiple edges and loops allowed — * —

--S 26 of 46
cap(complete 2**3*complete 1**2,wreath(complete 4,complete 2))
--R
--R
--R   (26)  23
--R                                                      Type: Fraction(Integer)
--E 26

———-

Having constructed a cycle index for a configuration we are at liberty to evaluate the s_{i} components any way we please. For example we can produce enumerating generating functions. This is done by providing a function f from an integer i to the value required of s_{i}, and then

evaluating eval(f,cycleindex)

— * —

--S 27 of 46
x:ULS(FRAC INT,'x,0):=x
--R
--R
--R   (27)  x
--R                         Type: UnivariateLaurentSeries(Fraction(Integer),x,0)
--E 27
--S 28 of 46
ZeroOrOne:INT->ULS(FRAC INT,'x,0)
--R
--R                                                                   Type: Void
--E 28
--S 29 of 46
Integers:INT->ULS(FRAC INT,'x,0)
--R
--R                                                                   Type: Void
--E 29

———-

For the integers 0 1 , or two colors — * —

--S 30 of 46
ZeroOrOne n == 1+x**n
--R
--R                                                                   Type: Void
--E

--S 31 of 46
ZeroOrOne 5
--R
--R   Compiling function ZeroOrOne with type Integer ->
--R      UnivariateLaurentSeries(Fraction(Integer),x,0)
--R
--R              5
--R   (31)  1 + x
--R                         Type: UnivariateLaurentSeries(Fraction(Integer),x,0)
--E 31

———-

For the integers 0,1,2,...

— * —

--S 32 of 46
Integers n == 1/(1-x**n)
--R
--R                                                                   Type: Void
--E 32
--S 33 of 46
Integers 5
--R
--R   Compiling function Integers with type Integer ->
--R      UnivariateLaurentSeries(Fraction(Integer),x,0)
--R
--R              5    10      11
--R   (33)  1 + x  + x   + O(x  )
--R                         Type: UnivariateLaurentSeries(Fraction(Integer),x,0)
--E 33

———-

The coefficient of x^{n} below is the number of graphs with 5 nodes and n edges. — * —

--S 34 of 46
eval(ZeroOrOne,graphs 5)
--R
--R
--R                   2     3     4     5     6     7     8    9    10      11
--R   (34)  1 + x + 2x  + 4x  + 6x  + 6x  + 6x  + 4x  + 2x  + x  + x   + O(x  )
--R                         Type: UnivariateLaurentSeries(Fraction(Integer),x,0)
--E 34

———-

The coefficient of x^{n} is the number of necklaces with n red beads and n-8 green beads. — * —

--S 35 of 46
eval(ZeroOrOne,dihedral 8)
--R
--R
--R                   2     3     4     5     6    7    8
--R   (35)  1 + x + 4x  + 5x  + 8x  + 5x  + 4x  + x  + x
--R                         Type: UnivariateLaurentSeries(Fraction(Integer),x,0)
--E 35

———-

The coefficient of x^{n} is the number of partitions of n into 4 or fewer parts — * —

--S 36 of 46
eval(Integers,complete 4)
--R
--R
--R   (36)
--R             2     3     4     5     6      7      8      9      10      11
--R   1 + x + 2x  + 3x  + 5x  + 6x  + 9x  + 11x  + 15x  + 18x  + 23x   + O(x  )
--R                         Type: UnivariateLaurentSeries(Fraction(Integer),x,0)
--E 36

———-

The coefficient of x^{n} is the number of partitions of n into 4 boxes containing ordered distinct parts.

— * —

--S 37 of 46
eval(Integers,elementary 4)
--R
--R
--R   (37)
--R      6    7     8     9     10     11     12      13      14      15      16
--R     x  + x  + 2x  + 3x  + 5x   + 6x   + 9x   + 11x   + 15x   + 18x   + 23x
--R   +
--R        17
--R     O(x  )
--R                         Type: UnivariateLaurentSeries(Fraction(Integer),x,0)
--E 37

———-

The coefficient of x^{n} is the number of partitions of n into exactly 4 parts.

The coefficient of x^{n} is the number of different cubes with n red vertices and 8-n green ones.

— * —

--S 38 of 46
eval(ZeroOrOne,cube)
--R
--R
--R                   2     3     4     5     6    7    8
--R   (38)  1 + x + 3x  + 3x  + 7x  + 3x  + 3x  + x  + x
--R                         Type: UnivariateLaurentSeries(Fraction(Integer),x,0)
--E 38

———-

The coefficient of x^{n} is the number of different cubes with integers on the vertices whose sum is n.

— * —

--S 39 of 46
eval(Integers,cube)
--R
--R
--R   (39)
--R               2     3      4      5      6       7       8       9       10
--R     1 + x + 4x  + 7x  + 21x  + 37x  + 85x  + 151x  + 292x  + 490x  + 848x
--R   +
--R        11
--R     O(x  )
--R                         Type: UnivariateLaurentSeries(Fraction(Integer),x,0)
--E 39

———-

The coefficient of x^{n} is the number of graphs with 5 nodes and with integers on the edges whose sum is n. In other words the enumeration is of multigraphs with 5 nodes and n edges.

— * —

--S 40 of 46
eval(Integers,graphs 5)
--R
--R
--R   (40)
--R               2     3      4      5      6       7       8       9       10
--R     1 + x + 3x  + 7x  + 17x  + 35x  + 76x  + 149x  + 291x  + 539x  + 974x
--R   +
--R        11
--R     O(x  )
--R                         Type: UnivariateLaurentSeries(Fraction(Integer),x,0)
--E 40

———-

Graphs with 15 nodes enumerated with respect to number of edges — * —

--S 41 of 46
eval(ZeroOrOne ,graphs 15)
--R
--R
--R   (41)
--R               2     3      4      5      6       7       8        9        10
--R     1 + x + 2x  + 5x  + 11x  + 26x  + 68x  + 177x  + 496x  + 1471x  + 4583x
--R   +
--R        11
--R     O(x  )
--R                         Type: UnivariateLaurentSeries(Fraction(Integer),x,0)
--E 41

———-

Necklaces with 7 green beads, 8 white beads, 5 yellow beads and 10 red beads. — * —

--S 42 of 46
cap(dihedral 30,complete 7*complete 8*complete 5*complete 10)
--R
--R
--R   (42)  49958972383320
--R                                                      Type: Fraction(Integer)
--E 42

———-

The function SFunction is the S-function of a partition written as a descending list of integers expressed in terms of power sum symmetric functions.

— * —

--S 43 of 46
sf3221:= SFunction [3,2,2,1]
--R
--R
--R   (43)
--R      1          1     2     1   2     1            1     4     1   2
--R     -- (6 2) - -- (6 1 ) - -- (4 ) + -- (4 3 1) + -- (4 1 ) - -- (3 2)
--R     12         12          16        12           24          36
--R   +
--R      1   2 2     1     2      1       3     1     5     1    4     1   3 2
--R     -- (3 1 ) - -- (3 2 1) - -- (3 2 1 ) - -- (3 1 ) - --- (2 ) + -- (2 1 )
--R     36          24           36            72          192        48
--R   +
--R      1   2 4     1      6     1    8
--R     -- (2 1 ) - --- (2 1 ) + --- (1 )
--R     96          144          576
--R                                 Type: SymmetricPolynomial(Fraction(Integer))
--E 43

———-

It counts the number of different tableaux of shape 3,2,2,1 filled with objects with an ascending order in the columns and a non-descending order in the rows.

cap(sf3221,complete 4**2) is the number filled with a a b b c c d d.

— * —

--S 44 of 46
cap(sf3221,complete 2**4)
--R
--R
--R   (44)  3
--R                                                      Type: Fraction(Integer)
--E 44

———-

The configurations enumerated are

a a b    a a c    a a d
b c      b b      b b
c d      c d      c c
d        d        d

cap(sf3221,powerSum 1**8) is the number of tableaux filled with 1..8.

— * —

--S 45 of 46
cap(sf3221,powerSum 1**8)
--R
--R
--R   (45)  70
--R                                                      Type: Fraction(Integer)
--E 45

———-

The coefficient of x^{n} below is the number of column strict reverse plane partitions of n of shape 3 2 2 1. The smallest is

0 0 0
1 1
2 2
3

— * —

--S 46 of 46
eval(Integers,sf3221)
--R
--R

--R   (46)
--R      9     10     11      12      13      14      15       16       17       18
--R     x  + 3x   + 7x   + 14x   + 27x   + 47x   + 79x   + 126x   + 196x   + 294x
--R   +
--R         19      20
--R     432x   + O(x  )
--R                         Type: UnivariateLaurentSeries(Fraction(Integer),x,0)
--E 46
)spool
)lisp (bye)

———-

References^{[1] nothing}

18