Application Center - Maplesoft
  Submit your work
Application Center Applications Polya Theory by Maple Preview

App Preview:

Polya Theory by Maple

You can switch back to the summary page by clicking here.

Learn about Maple
Download Application



> 

NULL

 

Polya Theory  by Maple

Kahtan H. Alzubaidy

 

 

 

  Key Words : Permutation Groups, Burnside's Theorem, Polya's Theorems

 

 

  Introduction

     In this application of Maple a few procedures are written to do the computations related to Burnside's counting  theorem and also to Polya's theorems.

  Everything is done in terms of permutation groups.

 

 

   Permutations Group

   A permutation for example   "((1 2 3 4) ? (2 1 4 3)) is represented by the permutation list [2,1,4,3] or "  "((1 2 3 4) ? (2 1 4 3))=""((1 2 ) ? (2 1 ))""(( 3 4) ? ( 4 3))"= (1,2)(3,4) is represented by disjoint cycles

" as a list of lists [[1,2],[3,4]]."

   The identity of degree 4 , for example is given by [1,2,3,4] or [[1],[2],[3],[4]].

   A permutation group is denoted by a list of its permutations.

 

> 

restart
> 

with(combinat):

 

   A product of two permutations S and T of degree n.

 

> 

p:=proc(S,T,n)
> 

[seq(S[T[r]],r=1..n)];
> 

end proc;

proc (S, T, n) [seq(S[T[r]], r = 1 .. n)] end proc

 (1)
> 

``
> 

``

    Basic Examples of Permutation Groups

      

  Trivial group of degree 4

  Id4:=[[1,2,3,4]];

[[1, 2, 3, 4]]

 (2)

All*permutations(Symmetric Group  S(n) of degree n )

> 

NULL
> 

S:=proc(n)
> 

permute(n);
> 

end proc;

proc (n) combinat:-permute(n) end proc

 (3)
> 

NULL
> 

S(1);

[[1]]

 (4)
> 

S(2);

[[1, 2], [2, 1]]

 (5)
> 

S(3);

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

 (6)
> 

S(4);

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

 (7)
> 

Z2 := [[1, 2], [2, 1]];

[[1, 2], [2, 1]]

 (8)
> 

Z3 := [[1, 2, 3], [2, 3, 1], [3, 1, 2]];

[[1, 2, 3], [2, 3, 1], [3, 1, 2]]

 (9)
> 

Z4 := [[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]];

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

 (10)
> 

V := [[1, 2, 3, 4], [2, 1, 3, 4], [1, 2, 4, 3], [2, 1, 4, 3]];

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

 (11)
> 

D4 := [[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3], [2, 1, 4, 3], [4, 3, 2, 1], [3, 2, 1, 4], [1, 4, 3, 2]];

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

 (12)

 

   The above examples can be put in terms of disjoint cycles  including 1-cycles as follows

``

> 

CId2 := [[[1], [2]]];

[[[1], [2]]]

 (13)
> 

CId3 := [[[1], [2], [3]]];

[[[1], [2], [3]]]

 (14)
> 

NULL
> 

CId4 := [[[1], [2], [3], [4]]];

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

 (15)
> 

CS(2) := [[[1], [2]], [[2, 1]]];

[[[1], [2]], [[2, 1]]]

 (16)
> 

CS(3) := [[[1], [2], [3]], [[1], [3, 2]], [[2, 1], [3]], [[2, 3, 1]], [[3, 1, 2]], [[3, 1], [2]]];

[[[1], [2], [3]], [[1], [3, 2]], [[2, 1], [3]], [[2, 3, 1]], [[3, 1, 2]], [[3, 1], [2]]]

 (17)
> 

CZ2 := [[[1], [2]], [[2, 1]]];

[[[1], [2]], [[2, 1]]]

 (18)
> 

CZ3 := [[[1], [2], [3]], [[2, 3, 1]], [[3, 1, 2]]];

[[[1], [2], [3]], [[2, 3, 1]], [[3, 1, 2]]]

 (19)
> 

CZ4 := [[[1], [2], [3], [4]], [[2, 3, 4, 1]], [[1, 3], [2, 4]], [[4, 1, 2, 3]]];

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

 (20)
> 

CV := [[[1], [2], [3], [4]], [[3], [4], [2, 1]], [[1], [2], [4, 3]], [[2, 1, 4, 3]]];

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

 (21)
> 

CD4 := [[[1], [2], [3], [4]], [[1, 2, 3, 4]], [[1, 3], [2, 4]], [[4, 1, 2, 3]], [[1, 2], [3, 4]], [[1, 4], [2, 3]], [[1], [3], [2, 4]], [[1, 3], [2], [4]]];

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

 (22)
> 

NULL
> 

NULL

 

   Burnside Counting Theorem

 

     Fixed Points of a Permutation

> 

FixedPoints:=proc(L)
> 

{select(x->is (x=L[x]),L)[]};
> 

end proc;
> 

 

proc (L) {select(proc (x) options operator, arrow; is(x = L[x]) end proc, L)[]} end proc

 (23)
> 

NULL

    Group Action

    Action of a permutation L of degree n on element x in {1,2,...,n}.

> 

NULL
> 

action:=proc(L,x)
> 

L[x];
> 

end proc;

proc (L, x) L[x] end proc

 (24)

   Orbit of x in a permutation group G

> 

NULL
> 

orbit:=proc(x,G)
> 

{seq(action(L,x),L in G)};
> 

end proc;
> 

 

proc (x, G) {seq(action(L, x), `in`(L, G))} end proc

 (25)
> 

orbit(2, S(3));

{1, 2, 3}

 (26)
> 

 

> 

``

     Burnside counting theorem

     Number of orbits  =  "(1)/(|G|)(∑) FixedPoints(g)"

 

     G is a permutation group of degree n

 

> 

Burnside:=proc(G,n)
> 

1/nops(G)*add(nops(FixedPoints(g)),g = G);
> 

end proc;

proc (G, n) add(nops(FixedPoints(g)), g = G)/nops(G) end proc

 (27)
> 

Burnside([[1, 2, 3, 4]], 4);

4

 (28)
> 

Burnside([[1, 2, 3, 4], [2, 1, 3, 4]], 4);

3

 (29)
> 

Burnside(S(3), 3);

1

 (30)
> 

Burnside(V, 4);

2

 (31)
> 

Burnside(D4, 4);

1

 (32)
> 

Burnside(Z3, 3);

1

 (33)

 

   Polya Theorems

 

   Cycle Index Polynomial  ZG of  a permutation group G of degree n.

 

                   ZG("x[1],x[2],...,x[n]) = (1)/(|G|)(∑) (∏)x[k]^(c[k](g)) , "where  "(c[k])^(g) is the number of cycles of order k in g."

      

   In the following procedurs permutation groups should be given in cycle notations

 

> 

NULL
> 

expo:=proc(L)
> 

[seq(nops(op(i,L)),i=1..nops(L))];
> 

end proc;

proc (L) [seq(nops(op(i, L)), i = 1 .. nops(L))] end proc

 (34)
> 

NULL
> 

l:=proc(L,m,t)
> 

  nops(select(x-> is(nops(x)=t),L));
> 

end proc;

proc (L, m, t) nops(select(proc (x) options operator, arrow; is(nops(x) = t) end proc, L)) end proc

 (35)
> 

NULL
> 

NULL
> 

exponents:=proc(L,m)
> 

 [seq(l(L,m,t),t=1..m)];
> 

end proc;

proc (L, m) [seq(l(L, m, t), t = 1 .. m)] end proc

 (36)
> 

``
> 

NULL
> 

vars:=proc(m)
> 

 [seq(x[i],i=1..m)];
> 

end proc;

proc (m) [seq(x[i], i = 1 .. m)] end proc

 (37)
> 

NULL
> 

NULL
> 

mono:=proc(L,m) local B,E;
> 

 B:= [seq(x[i],i=1..m)];
> 

 E:=exponents(L,m);
> 

 product((x[r])^E[r],r=1..m);
> 

end proc;
> 

 

proc (L, m) local B, E; B := [seq(x[i], i = 1 .. m)]; E := exponents(L, m); product(x[r]^E[r], r = 1 .. m) end proc

 (38)
> 

NULL
> 

NULL
> 

ZG:=proc(G,m)

> 

  1/nops(G) *add(mono(L,m),L=G);
> 

end proc;

proc (G, m) add(mono(L, m), L = G)/nops(G) end proc

 (39)
> 

ZG(CId2, 2);

x[1]^2

 (40)
> 

ZG(CId3, 3);

x[1]^3

 (41)
> 

ZG(CId4, 4);

x[1]^4

 (42)
> 

ZG(CS(2), 2);

(1/2)*x[1]^2+(1/2)*x[2]

 (43)
> 

ZG(CS(3), 3);

(1/6)*x[1]^3+(1/2)*x[1]*x[2]+(1/3)*x[3]

 (44)
> 

ZG(CZ3, 3);

(1/3)*x[1]^3+(2/3)*x[3]

 (45)
> 

ZG(CV, 4);

(1/4)*x[1]^4+(1/2)*x[1]^2*x[2]+(1/4)*x[4]

 (46)
> 

ZG([[[1], [2], [3]], [[1], [3, 2]]], 3);

(1/2)*x[1]^3+(1/2)*x[1]*x[2]

 (47)
> 

ZG(CD4, 4)

(1/8)*x[1]^4+(1/4)*x[4]+(3/8)*x[2]^2+(1/4)*x[1]^2*x[2]

 (48)

   

   Let D and R be two finite sets.
"R^(D)= {f | f:D->R is a function}. Let G be a permutation group of D. Define a binary relation ≈on R^(D) as follows"

   "f[1] ≈ f[2] iff f[1]= f[2]g for some g in G. ≈ is an equivalence relation."

 

Polya Enumeration Theorem

   The number of equivalence classes induced by "≈on R^(D) is given by "

    PG(abs(R), abs(R), () .. (), abs(R))

 

> 

Polya1:=proc(G,d,r)
> 

 

> 

 ZG(G,d);
> 

 subs([seq(x[i] = r, i = 1 .. d)],ZG(G,d));
> 

end proc;

proc (G, d, r) ZG(G, d); subs([seq(x[i] = r, i = 1 .. d)], ZG(G, d)) end proc

 (49)
> 

Polya1(CId4, 4, r);

r^4

 (50)
> 

Polya1(CS(2), 2, r);

(1/2)*r^2+(1/2)*r

 (51)
> 

Polya1(CS(3), 3, r);

(1/6)*r^3+(1/2)*r^2+(1/3)*r

 (52)
> 

Polya1(CZ3, 3, r);

(1/3)*r^3+(2/3)*r

 (53)
> 

Polya1(CV, 4, r);

(1/4)*r^4+(1/2)*r^3+(1/4)*r

 (54)
> 

Polya1(CD4, 4, r);

(1/8)*r^4+(1/4)*r+(3/8)*r^2+(1/4)*r^3

 (55)

 

    Inventory Polynomials

    Let D and R be two finite sets. The weight of  r2R is a symbol w(r) associated with r. The weight of a function f; proc (D) options operator, arrow; R end proc is defined by

            w(f)="(∏)w(f(d)). "Note that w("f[1])=w(f[2]) if f[1] ≈ f[2] ."

    The inventory of  F4"R^(D) is given by Inv(F)= (∑)w(f) ."

 

    Theorem.

     Let  "D[1],D[2],...,D[n] be a partition of D. Then Inv(R^(D))= (∏)[ (∑)(w(r))^(|D[i]|) ] ."

 

 

    Polya Fundamental Theorem.

    Let D and R be two finite sets and G a permutation group of D.  Then  Inv("R^(D))=PG(Sigma w(r),Sigma (w(r))^(2), ...)."

  

 

    The following procedure computes the inventory polynomial of a permutation group G of degree  d  in terms of the symbols  "a[1],a[2], ..., a[r] ."

> 

NULL
> 

Polya2:=proc(G,d,r)
> 

 seq(a[i],i=1..r);  
> 

 

> 

 ZG(G,d);
> 

 subs([seq(x[t] = sum(a[i]^t, i = 1 .. r),t=1..d)],ZG(G,d));
> 

end proc;
> 

 

proc (G, d, r) seq(a[i], i = 1 .. r); ZG(G, d); subs([seq(x[t] = sum(a[i]^t, i = 1 .. r), t = 1 .. d)], ZG(G, d)) end proc

 (56)
> 

Polya2(CId4, 4, 3);

(a[1]+a[2]+a[3])^4

 (57)
> 

Polya2(CS(2), 2, 2);

(1/2)*(a[1]+a[2])^2+(1/2)*a[1]^2+(1/2)*a[2]^2

 (58)
> 

``
> 

Polya2(CS(2), 2, 3);

(1/2)*(a[1]+a[2]+a[3])^2+(1/2)*a[1]^2+(1/2)*a[2]^2+(1/2)*a[3]^2

 (59)
> 

expand(%);

a[1]^2+a[1]*a[2]+a[1]*a[3]+a[2]^2+a[2]*a[3]+a[3]^2

 (60)
> 

Polya2(CS(3), 3, 3);

(1/6)*(a[1]+a[2]+a[3])^3+(1/2)*(a[1]+a[2]+a[3])*(a[1]^2+a[2]^2+a[3]^2)+(1/3)*a[1]^3+(1/3)*a[2]^3+(1/3)*a[3]^3

 (61)
> 

expand(%);

a[1]^3+a[1]^2*a[2]+a[1]^2*a[3]+a[1]*a[2]^2+a[1]*a[2]*a[3]+a[1]*a[3]^2+a[2]^3+a[2]^2*a[3]+a[2]*a[3]^2+a[3]^3

 (62)
> 

Polya2(CV, 4, 2, 2);

(1/4)*(a[1]+a[2])^4+(1/2)*(a[1]+a[2])^2*(a[1]^2+a[2]^2)+(1/4)*a[1]^4+(1/4)*a[2]^4

 (63)
> 

Polya2(CD4, 4, 3);

(1/8)*(a[1]+a[2]+a[3])^4+(1/4)*a[1]^4+(1/4)*a[2]^4+(1/4)*a[3]^4+(3/8)*(a[1]^2+a[2]^2+a[3]^2)^2+(1/4)*(a[1]+a[2]+a[3])^2*(a[1]^2+a[2]^2+a[3]^2)

 (64)
> 

``

   Let D and R be two finite sets. Suppose that  G is a permutation group of degree "|D| and H is a permutation group of degree |R|. Define a binary relation ≈ on R^(D) as follows "

   "f[1] ≈ f[2] iff hf[1]= f[2]g for some g in G and some h in H. ≈ is an equivalence relation." 

 

   Polya Generalized Theorem(DeBruijn)

   The number of equivalence classes induced by "≈on R^(D) is given by "

           "(1)/(|H|)(∑)ZG(|R[h]|, |R[h^(2)]|,..., |R[h^(k)]|), where R[h^(k)] is the set of points of R fixed fixed by h^(k). "

  

 

   The following procedures lead to the computation of the number of these equivalence classes.

> 

NULL

   The powers  h^r

 

> 

pr:=proc(h,p,n,r)
> 

local q;
> 

q:=t->p(q(t-1),h,n);
> 

q(1):=h;
> 

q(r);
> 

end proc;

proc (h, p, n, r) local q; q := proc (t) options operator, arrow; p(q(t-1), h, n) end proc; q(1) := h; q(r) end proc

 (65)
> 

NULL

   List  of numbers of fixed points of  h, "h^(2), ... ,h^(m)."

 

 

> 

NULL
> 

R:=proc(h,p,n,m)
> 

 

> 

[seq(nops(FixedPoints(pr(h,p,n,r))),r=1..m)]
> 

end proc;

proc (h, p, n, m) [seq(nops(FixedPoints(pr(h, p, n, r))), r = 1 .. m)] end proc

 (66)
> 

NULL

    List of numbers of fixed points of  "h^(r) , where h in H."

 

> 

RR:=proc(H,n,m)
> 

[seq(R(h,p,n,m),h in H)];
> 

end proc;

proc (H, n, m) [seq(R(h, p, n, m), `in`(h, H))] end proc

 (67)
> 

``

" Arguments includes G of degree m in cycles and variables a[1],..,a[m]."

> 

pgg:=proc()
> 

local m,PP;
> 

m:=nargs-1;PP:=PG(args[1],m);
> 

subs([seq(x[i-1]=args[i],i=2..m+1)],PP);
> 

end proc;
> 

 

proc () local m, PP; m := nargs-1; PP := PG(args[1], m); subs([seq(x[i-1] = args[i], i = 2 .. m+1)], PP) end proc

 (68)
> 

``
> 

``

   G of degree m in cycles and H of degree n in permutation lists

 

> 

Polya3:=proc(G,m,H,n)
> 

local RRR;
> 

RRR:=RR(H,n,m);
> 

1/nops(H) *add(z,z in [seq(pgg(G,RRR[i][]),i=1..nops(H))]);
> 

end proc;
> 

 

proc (G, m, H, n) local RRR; RRR := RR(H, n, m); add(z, `in`(z, [seq(pgg(G, RRR[i][]), i = 1 .. nops(H))]))/nops(H) end proc

 (69)
> 

Polya3(CS(3), 3, S(2), 2);

PG([[[1], [2], [3]], [[1], [3, 2]], [[2, 1], [3]], [[2, 3, 1]], [[3, 1, 2]], [[3, 1], [2]]], 3)

 (70)
> 

Polya3(CS(3), 3, S(3), 3);

PG([[[1], [2], [3]], [[1], [3, 2]], [[2, 1], [3]], [[2, 3, 1]], [[3, 1, 2]], [[3, 1], [2]]], 3)

 (71)
> 

Polya3(CS(3), 3, [[1, 2]], 2);

PG([[[1], [2], [3]], [[1], [3, 2]], [[2, 1], [3]], [[2, 3, 1]], [[3, 1, 2]], [[3, 1], [2]]], 3)

 (72)
> 

Polya3(CD4, 4, [[1, 2, 3, 4]], 4);

PG([[[1], [2], [3], [4]], [[1, 2, 3, 4]], [[1, 3], [2, 4]], [[4, 1, 2, 3]], [[1, 2], [3, 4]], [[1, 4], [2, 3]], [[1], [3], [2, 4]], [[1, 3], [2], [4]]], 4)

 (73)
> 

Polya3(CS(3), 4, [[1, 2, 3, 4]], 4);

PG([[[1], [2], [3]], [[1], [3, 2]], [[2, 1], [3]], [[2, 3, 1]], [[3, 1, 2]], [[3, 1], [2]]], 4)

 (74)
> 

Polya3(CS(3), 3, [[1, 2, 3]], 3);

PG([[[1], [2], [3]], [[1], [3, 2]], [[2, 1], [3]], [[2, 3, 1]], [[3, 1, 2]], [[3, 1], [2]]], 3)

 (75)
> 

NULL

  

Generalized Polya's Fundamental Theorem(DeBruijn)

 

   N =   
"(1)/(|H|) (∑)ZG(alpha[1](h),alpha[2](h),..., alpha[m](h)), where alpha[k](h)= (∑) (∏)t[h^(i).a] ; k=1, ... ,m and a in R. "

 

Note that  D ={1,2,..., m} and  R ={ 1,2,...,n}.

One may program this formula by Maple to complete the procedures.

 

    Department of Mathematics,

    Faculty of Science,

    University of Benghazi,  Libya

    E-mail: kahtanalzubaidy@yahoo.com

 

 

> 

 

> 

``
> 

``