path: root/src/input/cycles.input.pamphlet

\documentclass{article}
\usepackage{axiom}
\begin{document}
\title{\$SPAD/src/input cycles.input}
\author{The Axiom Team}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{License}
<<license>>=
--Copyright The Numerical Algorithms Group Limited 1994.
@
<<*>>=
<<license>>
 
--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   which are the
--                                                   i
--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
--   2     2                                2      2
-- (3  2 1  )  will be used to represent  s   s  s   and
--                                          3  2  1
-- 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
complete 1
--
--   (1)  (1)
--
complete 2
--
--        1       1   2
--   (2)  - (2) + - (1 )
--        2       2
--
complete 3
--
--        1       1         1   3
--   (3)  - (3) + - (2 1) + - (1 )
--        3       2         6
--
--
complete 7
--
--   (7)
--     1       1         1          1      2    1          1           1      3
--     - (7) + - (6 1) + -- (5 2) + -- (5 1 ) + -- (4 3) + - (4 2 1) + -- (4 1 )
--     7       6         10         10          12         8           24
--   +
--     1    2     1      2    1        2    1      4    1    3     1    2 3
--     -- (3 1) + -- (3 2 ) + -- (3 2 1 ) + -- (3 1 ) + -- (2 1) + -- (2 1 )
--     18         24          12            72          48         48
--   +
--      1      5     1     7
--     --- (2 1 ) + ---- (1 )
--     240          5040
--
--elementary n is the nth elementary symmetric function.
--
elementary 7
--
--   (8)
--     1       1         1          1      2    1          1           1      3
--     - (7) - - (6 1) - -- (5 2) + -- (5 1 ) - -- (4 3) + - (4 2 1) - -- (4 1 )
--     7       6         10         10          12         8           24
--   +
--     1    2     1      2    1        2    1      4    1    3     1    2 3
--     -- (3 1) + -- (3 2 ) - -- (3 2 1 ) + -- (3 1 ) - -- (2 1) + -- (2 1 )
--     18         24          12            72          48         48
--   +
--        1      5     1     7
--     - --- (2 1 ) + ---- (1 )
--       240          5040
--
--alternating n is the cycle index of the alternating group
--having an even number of even parts in each cycle partition.
--
alternating 7
--
--   (9)
--     2       1     2    1           1   2     1      2    1      4    1    2 3
--     - (7) + - (5 1 ) + - (4 2 1) + - (3 1) + -- (3 2 ) + -- (3 1 ) + -- (2 1 )
--     7       5          4           9         12          36          24
--   +
--      1     7
--     ---- (1 )
--     2520
--
--
--cyclic n is the cycle index of the cyclic group
cyclic 7
--
--         6       1   7
--   (10)  - (7) + - (1 )
--         7       7
--
--dihedral n is the cycle index of the dihedral group
--
dihedral 7
--
--         3       1   3     1    7
--   (11)  - (7) + - (2 1) + -- (1 )
--         7       2         14
--
--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.
graphs 5
--
--   (12)
--   1           1   2    1   2     1   3     1   4 2    1    3 4     1    10
--   - (6 3 1) + - (5 ) + - (4 2) + - (3 1) + - (2 1 ) + -- (2 1 ) + --- (1  )
--   6           5        4         6         8          12          120
--
--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 different 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
--
cap(complete 2**2,complete 2*complete 1**2)
--
--   (13)  4
--
--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
--
cap(elementary 2**2,complete 2*complete 1**2)
--
--   (14)  2
--
--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.
--
cap(complete 3*complete 2*complete 1,complete 2**2*complete 1**2)
--
--   (15)  24
--
--Same again, but with no equal pairs
--
cap(elementary 3*elementary 2*elementary 1,complete 2**2*complete 1**2)
--
--   (16)  8
--
cap(complete 3*complete 2*complete 1,elementary 2**2*elementary 1**2)
--
--   (17)  8
--
--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
--
eval(cup(complete 3*complete 2*complete 1, cup(complete 2**2*complete 1**2,complete 2**3)))
--
--   (18)  1500
--
--The cycle index of vertices of a square is dihedral 4
--
square:=dihedral 4
--
--         1       3   2    1     2    1   4
--   (19)  - (4) + - (2 ) + - (2 1 ) + - (1 )
--         4       8        4          8
--
--The number of different squares with 2 red vertices and 2 blue vertices
--
cap(complete 2**2,square)
--
--   (20)  2
--
--The number of necklaces with 3 red beads,2 blue beads and 2 green beads
--
cap(complete 3*complete 2**2,dihedral 7)
--
--   (21)  18
--
--The number of graphs with 5 nodes and 7 edges
--
cap(graphs 5,complete 7*complete 3)
--
--   (22)  4
--The cycle index of rotations of vertices of a cube
--
macro s == powerSum
cube:=(1/24)*(s 1**8+9*s 2**4 + 8*s 3**2*s 1**2+6*s 4**2)
--
--         1   2    1   2 2    3   4    1    8
--   (23)  - (4 ) + - (3 1 ) + - (2 ) + -- (1 )
--         4        3          8        24
--
--The number of cubes with 4 red vertices and 4 blue vertices
cap(complete 4**2,cube)
--
--   (24)  7
--
--The number of labeled graphs with degree sequence 2 2 2 1 1
--with no loops or multiple edges
cap(complete 2**3*complete 1**2,wreath(elementary 4,elementary 2))
--with loops allowed but not multiple edges
cap(complete 2**3*complete 1**2,wreath(elementary 4,complete 2))
-- with multiple edges allowed, but not loops
cap(complete 2**3*complete 1**2,wreath(complete 4,elementary 2))
-- with both multiple edges and loops allowed
cap(complete 2**3*complete 1**2,wreath(complete 4,complete 2))
--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  , and then evaluating eval(f,cycleindex)
--                   i
x:ULS(FRAC INT,'x,0):=x
ZeroOrOne:INT->ULS(FRAC INT,'x,0)
Integers:INT->ULS(FRAC INT,'x,0)
--For the integers 0 1 , or two colors
ZeroOrOne n == 1+x**n
ZeroOrOne 5
--For the integers 0,1,2,...
Integers n == 1/(1-x**n)
Integers 5
--
--The coefficient of x**n below is the number of graphs with 5 nodes
--and n edges.
--
eval(ZeroOrOne,graphs 5)
--
--                   2     3     4     5     6     7     8    9    10      11
--   (30)  1 + x + 2x  + 4x  + 6x  + 6x  + 6x  + 4x  + 2x  + x  + x   + O(x  )
--
--The coefficient of x**n is the number of necklaces with
-- n red beads and n-8 green beads.
eval(ZeroOrOne,dihedral 8)
--The coefficient of x**n is the number of partitions of n
--into 4 or fewer parts
eval(Integers,complete 4)
--
--   (32)
--             2     3     4     5     6      7      8      9      10      11
--   1 + x + 2x  + 3x  + 5x  + 6x  + 9x  + 11x  + 15x  + 18x  + 23x   + O(x  )
--
--The coefficient of x**n is the number of partitions of n into 4
-- boxes containing ordered distinct parts.
eval(Integers,elementary 4)
--
--          6    7     8     9     10      11
--   (33)  x  + x  + 2x  + 3x  + 5x   + O(x  )
--
--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.
--
eval(ZeroOrOne,cube)
--
--                   2     3     4     5     6    7    8
--   (36)  1 + x + 3x  + 3x  + 7x  + 3x  + 3x  + x  + x
--
--The  coefficient of x**n is the number of different cubes with integers
-- on the vertices whose sum is n.
--
eval(Integers,cube)
--
--   (37)
--               2     3      4      5      6       7       8       9       10
--     1 + x + 4x  + 7x  + 21x  + 37x  + 85x  + 151x  + 292x  + 490x  + 848x
--   +
--        11
--     O(x  )
--
-- 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.
eval(Integers,graphs 5)
--
--   (38)
--               2     3      4      5      6       7       8       9       10
--     1 + x + 3x  + 7x  + 17x  + 35x  + 76x  + 149x  + 291x  + 539x  + 974x
--   +
--        11
--     O(x  )
--
--Graphs with 15 nodes enumerated with respect to number of edges
--
eval(ZeroOrOne ,graphs 15)
--
--   (39)
--               2     3      4      5      6       7       8        9        10
--     1 + x + 2x  + 5x  + 11x  + 26x  + 68x  + 177x  + 496x  + 1471x  + 4583x
--   +
--           11         12          13          14           15            16
--     15036x   + 51814x   + 185987x   + 691001x   + 2632420x   + 10176660x
--   +
--              17             18             19              20      21
--     39500169x   + 152374465x   + 578891716x   + 2149523582x   + O(x  )
--
--
--Necklaces with 7 green beads, 8 white beads, 5 yellow beads and 10
--red beads.
--
cap(dihedral 30,complete 7*complete 8*complete 5*complete 10)
--
--   (40)  49958972383320
-- 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.
sf3221:= SFunction [3,2,2,1]
-- 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.
cap(sf3221,complete 2**4)
-- 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.
cap(sf3221,powerSum 1**8)
--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
eval(Integers,sf3221)
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}