\\ PARI Functions for Polya Enumeration
\\ ------------------------------------
\\ Author: Andrew Howroyd.
\\ This script or parts thereof may be freely used for private, educational, open source or commercial purposes.
\\ No waranty of any kind. Use at own risk.

\\ This is not intended to be a library.
\\     Source code will not be updated with improvements and bug fixes. 
\\     Functions do not check arguments for correct usage. Garbage in garbage out.
\\
\\ If you use any of the functions to enumerate new sequences, you should independently check initial terms by
\\ another method.  You are 100% responsible. Do not blame the script or author for wrong results / bugs.
\\
\\ Please feel free to steal/adapt any lines for your own personal collection. There is no need to acknowledge
\\ source when using - in fact please don't do this! (Once you copy characters from this file they are yours)
 

\\ This script is intended to be read in conjunction with Marks Nester's "Mathematical investigations of some
\\ plant interaction designs", PhD Thesis. University of Queensland, Brisbane, Australia. (Pdf in A056391)
\\ As such there is limited explanation (especially for the harder stuff)

\\ -----------------------------------------------
\\ Indexed variables. 
\\ This is a global collection of variables indexed by integers. Variables are named j_1, j_2 etc, but
\\ the variables are not the same as any variables you happen to call j_1, j_2 etc. To avoid confusion
\\ it is best to avoid use of these names. It is, in fact, possible to also allocate variables using a
\\ polynomial index - for example, if you need more than one set. Experimentally, variables indexed by
\\ vectors don't work (and break the dictionary).
\\ 
\\ Example use:
\\    IndexedVar(2) => j_2.
\\    IndicesToVars([3, 5, 4]) => [j_3, j_5, j_4].
\\    VarsToIndices(IndicesToVars([3, 5, x + 3*y])) => [3, 5, x + 3*y].
\\    (IndexedVar(2)+IndexedVar(3))^2 => j_2^2 + 2*j_3*j_2 + j_3^2.
\\    IndexedSubst((IndexedVar(2)+IndexedVar(3))^2, i->1+x^i) => x^6 + 2*x^5 + x^4 + 4*x^3 + 4*x^2 + 4.
\\    IndexedSubst([IndexedVar(2),IndexedVar(3)], i->if(i%2,IndexedVar(i-1),i)) => [2, j_2].


\\ The global collection.
\\ The 'if' statement is to prevent the map being created more than once even if script run again.
\\ This would be undersirable as it would leave any existing variables orphaned.
if (type(IndexedVarMap)=="t_POL", IndexedVarMap=Map());
\\ Gets a variable by its index. A new variable is created if one does not already exist.
IndexedVar(n)={my(v); if(!mapisdefined(IndexedVarMap, n, &v), v=varlower(Str("j_",n)); mapput(IndexedVarMap,n,v)); v}
\\ Gets a vector of variables from a vector of indices.
IndicesToVars(indices)={apply(i->IndexedVar(i),indices)}
\\ Gets a vector of indices from a vector of variables.
VarsToIndices(vars)={my(t=Vec(IndexedVarMap));substvec(vars, apply(i->mapget(IndexedVarMap,i), t), t)}

\\ Replaces all indexed variables in an expression with values based upon index.
\\ The expression may not contain any other variables except indexed variables.  
IndexedSubst(expr, f)={my(cv=variables(expr)); substvec(expr, cv, apply(i->f(i), VarsToIndices(cv)));}

\\ -----------------------------------------------
\\ Permutations groups.
\\ Permutations are represented by small vectors or integers. A group is represented by a vector of permutations.

\\ Construct a permutation group from a single generator. Returned permutation group will necessarily be cyclic.
PermsByGenerator(gen)={
    my(L=List([vectorsmall(#gen,i,i)]), p=Vecsmall(gen));
    while(p!=L[1], listput(L,p); p=vectorsmall(#gen,i,gen[p[i]]));
    Vec(L);
  }

\\ Forms the product of two permutation groups
PermsByProduct(g1,g2)={concat(Vec(Col(matrix(#g1,#g2,i,j,my(p=g1[i],q=g2[j]);vectorsmall(#p,k,p[q[k]])))))}

\\ Various permutation groups. All self explanatory.
IdentityPerms(n)={[vectorsmall(n,i,i)]}
ReversiblePerms(n)={PermsByGenerator(vectorsmall(n,i,n+1-i))}
CyclicPerms(n)={PermsByGenerator(vectorsmall(n,i,(i%n)+1))}
DihedralPerms(n)={if(n<3,CyclicPerms(n),PermsByProduct(CyclicPerms(n), ReversiblePerms(n)))}
MultiplicativePerms(n)={apply(v->vectorsmall(n-1,i,i*v%n), select(v->gcd(n,v)==1,[1..n]))}
HalfMultiplicativePerms(n)={apply(v->vectorsmall(n\2,i,abs((v*i+n\2)%n-n\2)), select(v->gcd(n,v)==1,[1..n\2]))}
StepShiftPerms(n)={apply(v->vectorsmall(n,i,if(i==n,n,i*v%n)), select(v->gcd(n,v)==1,[1..n]))}
CyclicStepShiftPerms(n)={PermsByProduct(StepShiftPerms(n),CyclicPerms(n))}
SquareCyclicPerms(n)={PermsByGenerator(concat(Vec(Col(matrix(n,n,j,i, i*n+1-j )))))}
SquareDihedralPerms(n)={my(g=PermsByGenerator(concat(Vec(Col(matrix(n,n,i,j, i*n+1-j )))))); PermsByProduct(g, SquareCyclicPerms(n))}
SquareTransposePerms(n)={PermsByGenerator(concat(Vec(Col(matrix(n,n,j,i, (i-1)*n+j )))))}
RectanglePerms(a,b)={if(a<=1||b<=1, ReversiblePerms(a*b), apply(f->Vecsmall(concat(Vec(Col(matrix(a,b,i,j,f(i,j)))))), 
    [(i,j)->(i-1)*b+j, (i,j)->i*b+1-j, (i,j)->(a-i)*b+j, (i,j)->(a-i+1)*b+1-j]))}
TriangleCyclicPerms(n)={PermsByGenerator(concat(vector(n, k, vector(k, i, n+1-k+(n+i-k)*(n+i-k-1)/2))))}
TriangleDihedralPerms(n)={my(g=PermsByGenerator(concat(vector(n, k, vector(k, i, k*(k+1)/2+1-i))))); PermsByProduct(g, TriangleCyclicPerms(n))}
CylinderPerms(c,k)={PermsByGenerator(vectorsmall(c*k,i,(i-1+k)%(c*k)+1))}
TorusPerms(a,b)={PermsByProduct(CylinderPerms(a,b), PermsByGenerator(vectorsmall(a*b, i, i%b + (i-1)\b*b + 1)))}


\\ -----------------------
\\ Miscellaneous functions

\\ Converts list of items into a bag with counts for each item. Bag is represented as matrix with two columns.
\\ Example: OccurrenceBag([x,y,x,x,y]) => [x, 3; y, 2]
OccurrenceBag(v)={my(M=Map()); for(i=1, #v, my(t=v[i],z); mapput(M, t, if(mapisdefined(M, t, &z), z+1, 1))); Mat(M)}

\\ Converts a partition into a polynomial in x. Each term t in the input list is made into x^t.
\\ PartPoly([1,1,1,5],x) => x^5 + 3*x
PartPoly(p,x)={sum(i=1, #p, x^p[i])}

\\ The number of permutations corresponding to a given partition. The partition is given in polynomial form.
\\ PermMultiplicityByPart(PartPoly([1,1,1,5], x)) => 1344
PermMultiplicityByPart(partPoly) = {my(m=1,s=0); for(i=0, poldegree(partPoly), my(c=polcoeff(partPoly,i)); if(c, s+=c*i; m*=c!*i^c)); s!/m}

\\ -----------------------------------
\\ Polya enumeration - the cycle index
\\ Cycle indexes are represented as polynomials in indexed variables.
\\ A cycle index can be created from a single permutation, a group of permutations or manually (say from a reference).
\\ Example use:
\\    PermCycleIndex([1,2,3]) => j_1^3.
\\    PermCycleIndex([2,3,1]) => j_3.
\\    PermCycleIndex([2,3,1,4]) => j_3*j_1.
\\    6 * GroupCycleIndex(CyclicPerms(6)) => j_1^6 + (j_2^3 + (2*j_3^2 + 2*j_6)).

\\ Cycle index from a permutation
PermCycleIndex(p)={my(r=1);for(i=1,#p,my(m=1,t=p[i]);while(t>i,t=p[t];m++);if(t==i,r*=IndexedVar(m)));r}
\\ Cycle index from a group of permutations
GroupCycleIndex(group)={sum(i=1,#group,PermCycleIndex(group[i]))/#group}
\\ Cycle index from Wikipedia (https://en.wikipedia.org/wiki/Cycle_index)
CubeFaceCycleIndex()={(IndexedVar(1)^6 + 6*IndexedVar(1)^2*IndexedVar(4) + 3*IndexedVar(1)^2*IndexedVar(2)^2 + 8*IndexedVar(3)^2 + 6*IndexedVar(2)^3)/24}
\\ Cycle index of symmetric group
SymmetricGroupCycleIndex(n)={my(v=vector(n)); for(n=1,#v,v[n]=sum(k=1,n,IndexedVar(k)*if(k==n,1,v[n-k]))/n); v[n]}

\\ Cycle index as a bag
\\ We also use cycle indexes represented as a bag of polynomials in x - in the case that access is required to the terms.
\\ (The multivariate form, although good for standard algebraic manipulation, is hard to process in other ways)
\\ Example use:
\\    PermCyclePoly([1,2,3],x) => 3*x.
\\    PermCyclePoly([2,3,1],x) => x^3.
\\    PermCyclePoly([2,3,1,4],x) => x^3 + x. 
\\    GroupCycleBag(CyclicPerms(6)) => [6*x, 1; 3*x^2, 1; 2*x^3 2; x^6 2].
PermCyclePoly(p,x)={my(r=0);for(i=1,#p,my(m=1,t=p[i]);while(t>i,t=p[t];m++);if(t==i,r+=x^m));r}
GroupCycleBag(group)={OccurrenceBag(apply(p->PermCyclePoly(p,x), group))}

\\ -------------------------------------------------
\\ Polya enumeration - without permutation of colors

\\ Number of non equivalent words with equivalence defined by given group using a given maximum number of colors.
\\ Example: NonequivalentWords(IdentityPerms(5), z) => z^5.
\\          NonequivalentWords(CyclicPerms(5), z) => 1/5*z^5 + 4/5*z.
NonequivalentWords(group, colors)={IndexedSubst(GroupCycleIndex(group), i->colors)}
\\ Alternate implementation of NonequivalentWords
NonequivalentWordsAlt(group, colors)={vecsum(apply(p->colors^PermCyclePoly(p,1), group))/#group}
\\ Variation on NonequivalentWords that returns a vector of values for each color <= colors.
NonequivalentWordsRow(group, colors)={my(cp=NonequivalentWords(group,x));vector(colors,k,subst(cp,x,k));}
\\ Number of non equivalent words with equivalence defined by given group using exactly a given number of colors.
NonequivalentWordsExactly(group, colors)={my(v=NonequivalentWordsRow(group,colors));sum(k=1,#v,(-1)^(colors-k)*v[k]*binomial(colors,k))}
\\ Variation on NonequivalentWordsExactly that returns a vector of values for each color <= colors.
NonequivalentWordsExactlyRow(group, colors)={my(v=NonequivalentWordsRow(group,colors));vector(colors,j,sum(k=1,j,(-1)^(j-k)*v[k]*binomial(j,k)))}

\\ -----------------------------------------------------------------
\\ Polya enumeration - with permutation of colors under second group
\\ This is de Bruins extension. 

\\ helper
QPoly(n)={sumdiv(n,d,d*IndexedVar(d))}

\\ Computes the number of non equivalent colorings for a collection of color permutations. Does not divide by size of coloring group.
\\ See Mark's Nesters thesis for some details on the mechanics of the substitutions, but mostly this is magic.
SortsByCycleIndex(cycleIndex, colorPermCycleBag)={
    my(cv = variables(cycleIndex), M=colorPermCycleBag);
    my(qp = apply(i->QPoly(i), VarsToIndices(cv))); my(qv = variables(qp)); my(qi = VarsToIndices(qv));
    sum(r=1, matsize(M)[1], my(p=M[r,1]);M[r,2] * substvec(cycleIndex, cv, substvec(qp, qv, apply(i->polcoeff(p,i), qi) ) ) );
}

\\ Number of non equivalent functions with permutations in both domain and codomain defined by groups.
\\ By definition NonequivalentWords(group,colors) == NonequivalentSorts(group, IdentityPerms(colors)).
\\ A high level wrapper aroung SortsByCycleIndex.
NonequivalentSorts(group, colorGroup)={SortsByCycleIndex(GroupCycleIndex(group), GroupCycleBag(colorGroup))/#colorGroup} 

\\ Computes the number of non equivalent colorings where all color permutations are allowed. (color group is symmetric group)
StructsByCycleIndex(cycleIndex, colors)={
    my(cv = variables(cycleIndex));
    my(qp = apply(i->QPoly(i), VarsToIndices(cv))); my(qv = variables(qp)); my(qi = VarsToIndices(qv));
    my(total = 0);
    forpart(p=colors, my(px=PartPoly(p,x)); total += PermMultiplicityByPart(px) * substvec(cycleIndex, cv, substvec(qp, qv, apply(i->polcoeff(px,i), qi) ) ) );
    total / colors!;
  }

\\ Number of non equivalent structures with equivalence defined by a group and permuting the colors does not change the structure.
NonequivalentStructs(group, colors)={StructsByCycleIndex(GroupCycleIndex(group), colors)}
NonequivalentStructsExactly(group, colors)={my(ci=GroupCycleIndex(group)); StructsByCycleIndex(ci, colors)-if(colors>1, StructsByCycleIndex(ci,colors-1), 0)}

\\ STOP
\\ The remainder of this file is just results. All shared code is above this line.

\\ ------------------------------------------------------------------------------------
\\ Results Part I. (no permutation of colors)
\\ These results are straight forward and could equally be obtained by other methods.
\\ List is not intended to be complete - only a few sequences have been included!
\\ Skip to Part II for those sequences where permutation of colors is part of the mix. 

\\ Number of n-bead necklaces using a maximum of k different colored beads
A075195(n,k) = NonequivalentWordsRow(CyclicPerms(n),k);
A000031(n) = NonequivalentWords(CyclicPerms(n),2);
A056665(n) = NonequivalentWords(CyclicPerms(n),n);
A047996(n) = Vecrev(IndexedSubst(GroupCycleIndex(CyclicPerms(n)), i->(1+x^i)));
\\ Number of n-bead necklaces using exactly k different colored beads
A087854(n) = NonequivalentWordsExactlyRow(CyclicPerms(n),n);
A052823(n) = NonequivalentWordsExactly(CyclicPerms(n),2);
\\ Number of n-bead bracelets using a maximum of k different colored beads
A081720(n,k) = NonequivalentWordsRow(DihedralPerms(n),k);
A000029(n) = NonequivalentWords(DihedralPerms(n),2);
A081721(n) = NonequivalentWords(DihedralPerms(n),n);
A052307(n) = Vecrev(IndexedSubst(GroupCycleIndex(DihedralPerms(n)), i->(1+x^i)));
\\ Number of n-bead bracelets using exactly k different colored beads
A273891(n) = NonequivalentWordsExactlyRow(DihedralPerms(n),n);
A056342(n) = NonequivalentWordsExactly(DihedralPerms(n),2);
\\ Number of classes of endofunctions of [n] under reversal
A275549(n) = NonequivalentWords(ReversiblePerms(n),n);

\\ Number of k-colorings of an n X n grid, up to rotational symmetry.
A047937(n) = NonequivalentWords(SquareCyclicPerms(n),2); \\ k=2
A047938(n) = NonequivalentWords(SquareCyclicPerms(n),3); \\ k=3
A047939(n) = NonequivalentWords(SquareCyclicPerms(n),4); \\ k=4
A282613(n) = NonequivalentWords(SquareCyclicPerms(3),n);
A283027(n) = NonequivalentWords(SquareCyclicPerms(4),n);
\\ Number of inequivalent n X n matrices over GF(k) under action of dihedral group of the square D_4.
A054247(n) = NonequivalentWords(SquareDihedralPerms(n),2); \\ k=2
A054739(n) = NonequivalentWords(SquareDihedralPerms(n),3); \\ k=3
A054751(n) = NonequivalentWords(SquareDihedralPerms(n),4); \\ k=4
A217331(n) = NonequivalentWords(SquareDihedralPerms(3),n);
A217338(n) = NonequivalentWords(SquareDihedralPerms(4),n);
A200564(n) = NonequivalentWords(SquareTransposePerms(n),2);
\\ Number of binary pattern classes in the (m,n)-rectangular grid.
A225910(m,n) = NonequivalentWords(RectanglePerms(m,n),2);
A225826(n) = NonequivalentWords(RectanglePerms(n,2),2);
A225827(n) = NonequivalentWords(RectanglePerms(n,3),2);
\\ Number of k-colorings of triangular arrays under rotational symmetries
A241806(n) = NonequivalentWords(TriangleCyclicPerms(n),2);
A061348(n) = NonequivalentWords(TriangleDihedralPerms(n),2);
\\ Number of n X n (0,1)-matrices modulo cyclic permutations of the rows
A086675(n) = NonequivalentWords(CylinderPerms(n,n),2);
\\ Number of n X n {-1,0,1} matrices modulo cyclic permutations of the rows
A086683(n) = NonequivalentWords(CylinderPerms(n,n),3);
\\ Number of toroidal arrays
A184271(n,m) = NonequivalentWords(TorusPerms(n,m),2);
A179043(n) = NonequivalentWords(TorusPerms(n,n),2);
A184284(n,m) = NonequivalentWords(TorusPerms(n,m),3);
A184278(n) = NonequivalentWords(TorusPerms(n,n),3);
A222188(n,m) = NonequivalentWords(PermsByProduct(RectanglePerms(n,m),TorusPerms(n,m)),2);
A209251(n) = NonequivalentWords(PermsByProduct(RectanglePerms(n,n),TorusPerms(n,n)),2);
A255015(n) = NonequivalentWords(PermsByProduct(SquareTransposePerms(n),TorusPerms(n,n)),2); 
A255016(n) = NonequivalentWords(PermsByProduct(SquareDihedralPerms(n),TorusPerms(n,n)),2); 

\\ Number of inequivalent ways to color faces of a cube using at most n colors
A047780(n) = IndexedSubst(CubeFaceCycleIndex(), i->n);
\\ Number of inequivalent ways (mod D_4) a pair of checkers can be placed on an n X n board
A014409(n) = polcoeff(IndexedSubst(GroupCycleIndex(SquareDihedralPerms(n)), i->(1+x^i)),2);
A082966(n) = polcoeff(IndexedSubst(GroupCycleIndex(SquareDihedralPerms(n)), i->(1+x^i)),3);
A019318(n) = polcoeff(IndexedSubst(GroupCycleIndex(SquareDihedralPerms(n)), i->(1+x^i)),n);
A054772(n) = Vecrev(IndexedSubst(GroupCycleIndex(SquareCyclicPerms(n)), i->(1+x^i)));
A054773(n) = polcoeff(IndexedSubst(GroupCycleIndex(SquareCyclicPerms(4)),i->1/(1-x^i)+O(x^(n+1))),n);
A226048(n) = Vecrev(IndexedSubst(GroupCycleIndex(RectanglePerms(n,2)), i->(1+x^i)));
A226290(n) = Vecrev(IndexedSubst(GroupCycleIndex(RectanglePerms(n,3)), i->(1+x^i)));

\\ Number of n-bead necklaces labeled with numbers -k..k allowing reversal, with sum zero.
A208825(n,k) = my(t=sum(i=0,2*k,x^i)); polcoeff(IndexedSubst(GroupCycleIndex(DihedralPerms(n)),i->subst(t,x,x^i)), k*n);
\\ 
A285522(n, k) = NonequivalentWordsRow(MultiplicativePerms(n),k); \\ gives n'th column
A056391(n) = NonequivalentWords(MultiplicativePerms(n),2); \\ k=2
\\ Number of step shifted (decimated) sequences using a maximum of k different symbols.
A132191(n, k) = NonequivalentWordsRow(StepShiftPerms(n),k); \\ gives n'th column
A056371(n) = NonequivalentWords(StepShiftPerms(n),2); \\ k=2
\\ Number of step cyclic shifted sequences using a maximum of k different symbols
A285548(n, k) = NonequivalentWordsRow(CyclicStepShiftPerms(n), k); \\ gives n'th column
A002729(n) = NonequivalentWords(CyclicStepShiftPerms(n),2); \\ k=2
A056411(n) = NonequivalentWords(CyclicStepShiftPerms(n),3); \\ k=3
\\ Number of step cyclic shifted sequences using exactly k different symbols.
A056415(n) = NonequivalentWordsExactly(CyclicStepShiftPerms(n),2); \\ k=2
A056416(n) = NonequivalentWordsExactly(CyclicStepShiftPerms(n),3); \\ k=3
\\ Number of circulant graphs on n vertices up to Cayley isomorphism.
A285620(n) = if(n<2,n==1,NonequivalentWords(HalfMultiplicativePerms(n),2));

\\ self complementary necklaces and bracelets
A000013(n) = IndexedSubst(GroupCycleIndex(CyclicPerms(2*n)), i->if(i%2,0,2));
A007148(n) = IndexedSubst(GroupCycleIndex(DihedralPerms(2*n)), i->if(i%2,0,2));

\\ ------------------------------------------------------------------------------------
\\ Results Part II. Structures (also allow permutation of colors) 
\\ Another way of looking at this - is that these are set partitions.

\\ Number of word structures of length n using a k-ary alphabet
A278984(n, k) = NonequivalentStructs(IdentityPerms(n), k); \\ transposed
A056272(n) = NonequivalentStructs(IdentityPerms(n), 5); \\ k = 5
\\ Number of reversible string structures with n beads using a maximum of k different colors
A005418(n) = NonequivalentStructs(ReversiblePerms(n), 2);
A056323(n) = NonequivalentStructs(ReversiblePerms(n), 4);
\\ Number of reversible string structures with n beads using exactly k different colors.
A284949(n,k) = NonequivalentStructsExactly(ReversiblePerms(n), k);
A056327(n) = NonequivalentStructsExactly(ReversiblePerms(n), 3); \\ k=3
A056328(n) = NonequivalentStructsExactly(ReversiblePerms(n), 4); \\ k=4
A103293(n) = NonequivalentStructs(ReversiblePerms(n), n); \\ row sums

\\ Number of necklace structures using a maximum of k different colored beads.
A000013(n) = NonequivalentStructs(CyclicPerms(n), 2);
A002076(n) = NonequivalentStructs(CyclicPerms(n), 3);
\\ Number of k-block partitions of an n-set up to rotations
\\ & Number of n-bead necklace structures using exactly k different colored beads
A152175(n,k) = NonequivalentStructsExactly(CyclicPerms(n), k);
A084423(n) = NonequivalentStructs(CyclicPerms(n), n); \\ row sums
A056296(n) = NonequivalentStructsExactly(CyclicPerms(n), 3); \\ k=3
\\ Number of bracelet structures using a maximum of k different colored beads.
A000011(n) = NonequivalentStructs(DihedralPerms(n), 2);
A056353(n) = NonequivalentStructs(DihedralPerms(n), 3);
\\ Number of k-block partitions of an n-set up to rotations and reflections.
\\ & Number of bracelet structures using exactly k different colored beads
A152176(n,k) = NonequivalentStructsExactly(DihedralPerms(n), k);
A084708(n) = NonequivalentStructs(DihedralPerms(n), n); \\ row sums
A056358(n) = NonequivalentStructsExactly(DihedralPerms(n), 3); \\ k=3
\\ Number of step shifted (decimated) sequence structures of length n using k different symbols
A288620(n,k) = NonequivalentStructsExactly(StepShiftPerms(n), k)
A288621(n) = NonequivalentStructs(StepShiftPerms(n), n);
A056392(n) = NonequivalentStructs(StepShiftPerms(n), 3);
A056397(n) = NonequivalentStructsExactly(StepShiftPerms(n), 3);
\\ Number of step cyclic shifted sequence structures of length n using k different symbols.
A288627(n,k) = NonequivalentStructsExactly(CyclicStepShiftPerms(n), k)
A288628(n) = NonequivalentStructs(CyclicStepShiftPerms(n), n);
A056429(n) = NonequivalentStructs(CyclicStepShiftPerms(n), 2);
A056430(n) = NonequivalentStructs(CyclicStepShiftPerms(n), 3);
A056435(n) = NonequivalentStructsExactly(CyclicStepShiftPerms(n), 3);


\\ Number of colorings of an n X n grid with at most k interchangeable colors under rotational and reflectional symmetry.
A182044(n) = NonequivalentStructs(SquareDihedralPerms(n), 2);
A264741(n) = NonequivalentStructs(SquareDihedralPerms(n), 3);
A264742(n) = NonequivalentStructs(SquareDihedralPerms(n), 4);
A264743(n) = NonequivalentStructs(SquareDihedralPerms(n), 5);
\\ Number of colorings of an n X n grid with any number of interchangeable colors under rotational and reflectional symmetry.
A264787(n) = NonequivalentStructs(SquareDihedralPerms(n), n^2);

\\ Number of classes of endofunctions of [n] under vertical translation mod n and reversal.
A275551(n) = NonequivalentSorts(ReversiblePerms(n), CyclicPerms(n));
\\ Number of classes of endofunctions of [n] under translation mod n and rotation
\\ & Number of necklaces of n beads with up to n colors, with cyclic permutation {1,..,n} of the colors taken to be equivalent.
A130293(n) = NonequivalentSorts(CyclicPerms(n), CyclicPerms(n));
\\ Number of classes of endofunctions of [n] under vertical translation mod n, rotation and reversal
A275555(n) = NonequivalentSorts(DihedralPerms(n), CyclicPerms(n));
\\ Number of classes of endofunctions of [n] under reversal and complement to n+1.
A275550(n) = NonequivalentSorts(ReversiblePerms(n), ReversiblePerms(n));
\\ Number of classes of endofunctions of [n] under rotation and complement to n+1
A275557(n) = NonequivalentSorts(CyclicPerms(n), ReversiblePerms(n));
\\ Number of classes of endofunctions of [n] under rotation, complement to n+1 and reversal.
A275558(n) = NonequivalentSorts(DihedralPerms(n), ReversiblePerms(n));
\\ Number of classes of endofunctions of [n] under vertical translation mod n and complement to n+1
A275552(n) = NonequivalentSorts(IdentityPerms(n), DihedralPerms(n));
\\ Number of classes of endofunctions of [n] under vertical translation mod n, complement to n+1 and reversal.
A275553(n) = NonequivalentSorts(ReversiblePerms(n), DihedralPerms(n));
\\ Number of classes of endofunctions of [n] under vertical translation mod n, rotation and complement to n+1.
A275554(n) = NonequivalentSorts(CyclicPerms(n), DihedralPerms(n));
\\ Number of classes of endofunctions of [n] under vertical translation mod n, rotation, complement to n+1 and reversal.
A275556(n) = NonequivalentSorts(DihedralPerms(n), DihedralPerms(n));

\\ Number of partitions of {1..2n} that are invariant under a permutation consisting of n 2-cycles
A002872(n) = 2*NonequivalentStructs(CylinderPerms(2,n),2*n) - sum(k=1,2*n,stirling(2*n,k,2));
A293181(n,k) = 2*NonequivalentStructsExactly(CylinderPerms(2, n), k) - stirling(2*n, k, 2);