###################################################################### ##GraphEnumeration: Save this file as GraphEnumeration # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read GraphEnumeration # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #zeilberg at math dot rutgers dot edu # ###################################################################### #Created: June 2010 print(`Created: June 2010`): print(` This is GraphEnumeration `): print(`It accompanyies Doron Zeilberger's talk at the Berlin Mathematical`): print(`School delivered on June 18, 2010 `): print(``): print(`Please report bugs to zeilberg at math dot rutgers dot edu`): print(``): print(`The most current version of this package and paper`): print(` are available from`): print(`http://www.math.rutgers.edu/~zeilberg/ .`): print(`For a list of the procedures type ezra();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): with(combinat): ezra1:=proc() if args=NULL then print(` The supporting procedures are: ApplySiPer, `): print(` Bn, CICube, CIk,HGn, HGnx,Gnx,InPer, InSiPer `): print(` NIPVecs, NIVecs, Wtk, WtSiPer `): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: BnSeq, BnxSeq`): print(` Cseq, Cseqx, HGseq, HGseqx,Gseq, Gseqx, RTseq, Tseq, UGdeg, UMGdeg, `): elif nops([args])=1 and op(1,[args])=ApplySiPer then print(`ApplySiPer(v,pi,s): given a signed permutation (pi,s)`): print(`applies it to the [0,1] vector v. For example, try:`): print(`ApplySiPer([1,0,1],[2,3,1],[1,0,0]);`): elif nops([args])=1 and op(1,[args])=Bn then print(`Bn(n): the number of Boolean functions on n variables`): print(`up to symmetry and negation`): print(`For example, try:`): print(`Bn(3);`): elif nops([args])=1 and op(1,[args])=BnSeq then print(`BnSeq(n): the first n members of the sequence for the`): print(`number of Boolean functions on n variables`): print(`up to symmetry and negation`): print(`For example, try:`): print(`BnSeq(7);`): elif nops([args])=1 and op(1,[args])=Bnx then print(`Bnx(n,x): the`): print(`generating function, in x, such that the coeff. of x^i is`): print(` the number of equivalence classes of Boolean functions`): print(`(under permutations of the variables and negation)`): print(`with n variables and exactly i truth-false vectors that evaluate to`): print(`true`): print(`For example, try:`): print(`Bnx(7,x);`): elif nops([args])=1 and op(1,[args])=BnxSeq then print(`BnxSeq(n,x): the first n terms of the sequence of`): print(`generating functions, in x, such that the coeff. of x^i is`): print(` the number of equivalence classes of Boolean functions`): print(`(under permutations of the variables and negation)`): print(`with n variables and exactly i truth-false vectors that evaluate to`): print(`true`): print(`For example, try:`): print(`BnxSeq(5,x);`): elif nops([args])=1 and op(1,[args])=CICube then print(`CICube(s,n): The cycle-index polynomial of the group`): print(`of signed permutations acting on the Boolean lattice`): print(`using using s[1], ..., s[n]`): print(`For example try:`): print(`CICube(s,3);`): elif nops([args])=1 and op(1,[args])=CIk then print(`CIk(s,k,n): The cycle-index polynomial of S_n using s[1], ..., s[n]`): print(`for k-uniform hypergraphs. For example, try:`): print(`CIk(s,2,3);`): elif nops([args])=1 and op(1,[args])=Cseqx then print(`Cseqx(n,y): the first n terms of the sequence of generating functions`): print(`in y, for the number of unlabeled connected graphs on n vertices `): print(`according to edges`): print(`In other words the coeff. of y^m of the i-th entry of the output`): print(`is the number of unlabeled connected graphs with i vertices`): print(`and n edges `): print(`For example, try:`): print(`Cseqx(10,y);`): elif nops([args])=1 and op(1,[args])=Cseq then print(`Cseq(n): the first n terms of the sequence for counting unlabeled`): print(`connected graphs`): elif nops([args])=1 and op(1,[args])=HGnx then print(`HGnx(n,k,x): the generating function of all unlabeled `): print(`k-uniform hypergraphs with`): print(`n vertices according to the number of edges. For example, try:`): print(`HGnx(5,2,x);`): elif nops([args])=1 and op(1,[args])=HGseq then print(`HGseq(k,n): the first n terms of the sequence counting the`): print(`number of unlabeled k-uniform hypergraphs. `): print(`For example, try:`): print(`HGseq(2,10);`): elif nops([args])=1 and op(1,[args])=HGseqx then print(`HGseqx(k,n,x): the first n terms of a the sequence of `): print(`generating functions`): print(`in x, for the number of unlabeled k-uniform hypergraphs on n vertices `): print(`according to edges `) : print(`In other words the coeff. of x^m of the i-th entry of the output`): print(`is the number of unlabeled k-uniform hypergraphs with i vertices`): print(`and n edges `): print(`For example, try:`): print(`HGseqx(2,10,x);`): elif nops([args])=1 and op(1,[args])=InSiPer then print(`InSiPer(pi,s): inputs a signed permutation (pi,s) `): print(`and outputs the induced`): print(`permutation on {0,1}^n (n=nops(pi)) .`): print(`For example, try:`): print(`InSiPer([1,3,2],[1,0,1]);`): elif nops([args])=1 and op(1,[args])=Gnx then print(`Gnx(n,x): the generating function of all unlabeled `): print(`graphs with`): print(`n vertices according to the number of edges. For example, try:`): print(`Gnx(5,x);`): elif nops([args])=1 and op(1,[args])=Gseq then print(`Gseq(n): the first n terms of the sequence counting the`): print(`number of unlabeled graphs (according to vertices). For example, try:`): print(`Gseq(10);`): elif nops([args])=1 and op(1,[args])=Gseqx then print(`Gseqx(n,y): the first n terms of a the sequence of `): print(`generating functions`): print(`in y, for the number of unlabeled graphs on n vertices `): print(`according to edges `) : print(`In other words the coeff. of y^m of the i-th entry of the output`): print(`is the number of unlabeled graphs with i vertices`): print(`and n edges `): print(`For example, try:`): print(`Gseqx(10,y);`): elif nops([args])=1 and op(1,[args])=InPer then print(`InPer(pi,k): inputs a permutation pi and outputs the induced`): print(`permutation on k-subsets of {1, ..., n}. For example try:`): print(`InPer([1,3,2],2);`): elif nops([args])=1 and op(1,[args])=NIPVecs then print(`NIPVecs(k,N,a): the set of weakly-decreasing`): print(`vectors of pos. integers <=a of length k`): print(`that add-up to N `): print(` Try:`): print(`NIPVecs(3,4,2);`): elif nops([args])=1 and op(1,[args])=NIVecs then print(`NIVecs(k,N,a): the set of weakly-decreasing`): print(`vectors of non-neg. integers <=a of length k`): print(`that add-up to N `): print(` Try:`): print(`NIVecs(3,4,2);`): elif nops([args])=1 and op(1,[args])=RTseq then print(`RTseq(n): the first n terms of sequence `): print(`for the number of rooted labeled trees`): print(``): elif nops([args])=1 and op(1,[args])=Tseq then print(` Tseq(n): the first n terms of the generating function `): print(` for the number of unlabeled trees `): elif nops([args])=1 and op(1,[args])=UGdeg then print(`UGdeg(L): the number of all (connected or not) unlabeled `): print(`(simple) graphs `): print(`with degree sequence L`): print(`For example, try:`): print(`UGdeg([3$6]);`): elif nops([args])=1 and op(1,[args])=UMGdeg then print(`UMGdeg(L): the number of all (connected or not) unlabeled `): print(`multi-graphs `): print(`with degree sequence L`): print(`For example, try:`): print(`UMGdeg([3$6]);`): elif nops([args])=1 and op(1,[args])=Wtk then print(`Wtk(j,k,s): The weight of a partition j for counting`): print(` k-uniform hypergraphs`): print(`For example, try:`): print(`Wtk([1,1],2,s);`): elif nops([args])=1 and op(1,[args])=WtSiPer then print(`WtSiPer(j,si,s): The weight of a `): print(`partition j followed by a sign-vector`): print(`for counting Boolean functions`): print(`For example, try:`): print(`WtSiPer([1,1],[1,0,1],s);`): else print(`There is no ezra for`,args): fi: end: ez:=proc(): print(`RTac(n), OneStep(f,x), RTx(n,x), `): print(` Pars1(n,k), Pars(n), Wt(j,s), CI(s,n) `): print(`Wt2(j,s), CI2(s,n), Gnx(n,x), Gseq(n) `): print(`Cseq(n), Gseqx(n,x), Cseqx(n,y), MGnx(n,x) `): print(`MGseqx(n,y), MCseqx(n,m,y), ParToCyc(p), Wt2x(j,x) `): print(`theta1(mono,n,x), theta(poly,n,x), Nx(p,x) `): print(`MonoToDeg(mono,x,n), Cx(p,t,x), Wt2xMG(j,x,t,M)`): print(`NxMG(3,x,t,4), UMGdeg(L) `): end: with(numtheory): #RTac(n): the number of rooted unlabeled trees on n vertices RTac:=proc(n) local x,gu,i: option remember: if n=1 then RETURN(1): fi: gu:=x/mul((1-x^i)^RTac(i),i=1..n-1): gu:=taylor(gu,x=0,n+1): coeff(gu,x,n): end: OneStep:=proc(f,x) local gu,k,n: n:=degree(f,x): gu:=x*exp(add(subs(x=x^k,f)/k,k=1..n)): gu:=taylor(gu,x=0,n+2): add(coeff(gu,x,k)*x^k,k=1..n+1): end: #RTx(n,x): the first n terms of the generating function #for the number of rooted unlabeled trees RTx:=proc(n,x) local gu,k: option remember: gu:=x: for k from 1 to n do gu:=OneStep(gu,x): od: gu: end: #RTseq(n): the first n terms of sequence #for the number of rooted labeled trees RTseq:=proc(n) local x,gu,i: gu:=RTx(n,x) : [seq(coeff(gu,x,i),i=1..n)]: end: #Tseq(n): the first n terms of the generating function #for the number of unlabeled trees Tseq:=proc(n) local gu,k,x: gu:=RTx(n,x): gu:=expand(gu-(gu^2-subs(x=x^2,gu))/2): [seq(coeff(gu,x,k),k=1..n)]: end: #Pars1(n,k): all partitions of n with largest part <=k Pars1:=proc(n,k) local gu,r,gu1,g1: option remember: if k=1 then RETURN({[n]}): fi: gu:={}: for r from 0 to trunc(n/k) do gu1:=Pars1(n-r*k,k-1): gu:=gu union {seq([op(g1),r],g1 in gu1)}: od: gu: end: #Pars(n): the integer partitions of n in freq. notation Pars:=proc(n) :Pars1(n,n):end: #Wt(j,s): The weight of a partition j Wt:=proc(j,s) local k: mul((s[k]/k)^j[k]/j[k]!,k=1..nops(j)): end: #Wt0(j): The weight of a partition j Wt0:=proc(j) local k: mul((1/k)^j[k]/j[k]!,k=1..nops(j)): end: #CI(s,n): The cycle-index polynomial of S_n using s[1], ..., s[n] CI:=proc(s,n) local gu,j: gu:=Pars(n): add(Wt(j,s), j in gu): end: #Wt2(j,s): The weight of a partition j for counting graphs Wt2:=proc(j,s) local n,k,gu,r,t: n:=nops(j): #weight gu:=mul((1/k)^j[k]/j[k]!,k=1..nops(j)): #both in the same odd cycle (c1^2, odd) gu:=gu*mul(s[2*k+1]^(k*j[2*k+1]),k=1..trunc((n-1)/2)): #both in the same even cycle (c1^2, even) gu:=gu*mul((s[k]*s[2*k]^(k-1))^(j[2*k]),k=1..trunc(n/2)): #in different cycles of the same length ({c1,c2}, len(c1)=len(c2)) gu:=gu*mul(s[k]^(k*binomial(j[k],2)),k=1..n): #in different cycles of different lengths ({c1,c2}, len(c1)<>len(c2)) gu:=gu*mul(mul(s[lcm(r,t)]^(gcd(r,t)*j[r]*j[t]),r=1..t-1),t=1..n): gu: end: #CI2(s,n): The cycle-index polynomial of S_n using s[1], ..., s[n] CI2:=proc(s,n) local gu,j: gu:=Pars(n): add(Wt2(j,s), j in gu): end: #Gnx(n,x): the generating function of all unlabeled graphs with #n vertices according to the number of edges Gnx:=proc(n,x) local gu,s,i,N: N:=max(seq(seq(lcm(r,t),r=1..t-1),t=1..n)): gu:=CI2(s,n): expand(subs({seq(s[i]=1+x^i,i=1..N)},gu)): end: #Gseq(n): the first n terms of the sequence counting the #number of unlabeled graphs (according to vertices). For example, try: #Gseq(10); Gseq:=proc(n) local i,x: [seq(subs(x=1,Gnx(i,x)),i=1..n)]: end: #Cseq(n): the first n terms of the sequence for counting unlabeled #connected graphs Cseq:=proc(n) local gu,g,a,x,i,d,p: gu:=Gseq(n): g:=log(1+add(gu[i]*x^i,i=1..n)): g:=taylor(g,x=0,n+1): a:=[seq(coeff(g,x,i),i=1..n)]: [seq(add(mobius(d)/d*a[p/d], d in divisors(p)),p=1..n)]: end: #Gseqx(n,y): the first n terms of the sequence of generating functions #in y, for the number of unlabeled graphs on m vertices according to edges #For example, try: #Gseqx(10,y); Gseqx:=proc(n,y) local i: [seq(Gnx(i,y),i=1..n)]: end: #Cseqx(n,x): the first n terms of the sequence for counting unlabeled #connected graphs Cseqx:=proc(n,y) local gu,g,a,i,r,p,q,x,c,b: gu:=Gseqx(n,y): g:=log(1+add(gu[i]*x^i,i=1..n)): g:=taylor(g,x=0,n+1): a:=[seq(coeff(g,x,i),i=1..n)]: for p from 1 to n do for q from 0 to n^2 do b[p,q]:=coeff(a[p],y,q): od: od: for p from 1 to n do for q from 1 to binomial(p,2) do c[p,q]:=add(b[p/r,q/r]*mobius(r)/r,r in divisors(gcd(p,q))): od: od: [1,seq(add(c[p,q]*y^q,q=p-1..binomial(p,2)),p=2..n)]: end: ###starts multi-graphs######### #MGnx(n,x): the generating function of all unlabeled multi-edged #graphs with n vertices according to the number of edges MGnx:=proc(n,x) local gu,s,i,N,r,t: option remember: N:=max(seq(seq(lcm(r,t),r=1..t-1),t=1..n)): gu:=CI2(s,n): normal(subs({seq(s[i]=1/(1-x^i),i=1..N)},gu)): end: #MGseqx(n,y): the first n terms of the sequence of generating functions #in y, for the number of unlabeled multi-graphs #on m vertices according to edges #For example, try: #MGseqx(10,y); MGseqx:=proc(n,y) local i: [seq(MGnx(i,y),i=1..n)]: end: #MCseqx(n,m,y): the first n terms of the sequence for counting unlabeled #connected multi-graphs with at most m edges MCseqx:=proc(n,m,y) local gu,g,a,i,r,p,q,x,c,b,j: gu:=MGseqx(n,y): g:=log(1+add(gu[i]*x^i,i=1..n)): g:=taylor(g,x=0,n+1): a:=[seq(normal(coeff(g,x,i)),i=1..n)]: a:=[seq(taylor(a[i],y=0,m+1),i=1..n)]: a:=[seq(add(coeff(a[i],y,j)*y^j,j=0..m),i=1..n)]: for p from 1 to n do for q from 0 to m do b[p,q]:=coeff(a[p],y,q): od: od: for p from 1 to n do for q from 1 to m do c[p,q]:=add(b[p/r,q/r]*mobius(r)/r,r in divisors(gcd(p,q))): od: od: [1,seq(add(c[p,q]*y^q,q=1..m),p=2..n)]: end: #ParToCyc(p): Given a partition p finds ONE (the lex. smallest) #permutation of n with that cycle structure. For example try: #ParToCyc([3,0,0]); ParToCyc:=proc(p) local n,c,j,r,gu,i,i1: n:=nops(p): if add(p[i]*i,i=1..n)<>n then RETURN(FAIL): fi: c:=0: gu:=[]: for i from 1 to nops(p) do j:=p[i]: for r from 1 to j do gu:=[op(gu),[seq(c+i1,i1=1..i)]]: c:=c+i: od: od: gu: end: #theta1(mono,n,x): applies the sorting operator theta on a monomial #in x[1], ..., x[n]. For example, try theta1(x[2]^3*x[1]^2,2,x); theta1:=proc(mono,n,x) local d,i,coe: d:=[seq(degree(mono,x[i]),i=1..n)]: coe:=normal(mono/mul(x[i]^d[i],i=1..n)): #if not type(coe,integer) then # RETURN(FAIL): #fi: d:=sort(d): d:=[seq(d[n+1-i],i=1..n)]: coe*mul(x[i]^d[i],i=1..n): end: #theta(poly,n,x): applies the sorting operator theta on a polynomial #in x[1], ..., x[n]. For example, try theta(x[1]+x[2],2,x); theta:=proc(pol,n,x) local i: if not type(pol, `+`) then RETURN(theta1(pol,n,x)): else add(theta1(op(i,pol),n,x),i=1..nops(pol)): fi: end: #Wt2x(j,x): The weight according to degrees of #of a partition j for counting graphs Wt2x:=proc(j,x) local p,gu,r,s,i,n,r1,s1: n:=nops(j): p:=ParToCyc(j): gu:=1: for r from 1 to nops(p) do for s from r+1 to nops(p) do r1:=nops(p[r]): s1:=nops(p[s]): gu:=gu*(1+ mul(x[i]^(s1/gcd(r1,s1)),i in p[r])*mul(x[i]^(r1/gcd(r1,s1)),i in p[s])) ^gcd(r1,s1): od: od: for r from 1 to nops(p) do if nops(p[r]) mod 2 =0 then gu:=gu*(1+mul(x[i],i in p[r]))* (1+mul(x[i]^2,i in p[r]))^((nops(p[r])-2)/2): else gu:=gu*(1+mul(x[i]^2,i in p[r]) )^( (nops(p[r])-1)/2 ): fi: od: gu:=expand(gu): theta(gu,n,x): end: #Nx(p,x): The weight-enumerator of simple graphs on p vertices #accorsing to x[1]^degree[1]*x[2]^degree[2]* .. . #For example, try: #Nx(3,x); Nx:=proc(p,x) local mu,j: mu:=Pars(p): expand(add(Wt0(j)*Wt2x(j,x) , j in mu)): end: #MonoToDeg(mono,x,n): converts the monomial to the #degree sequence. For example, try: #MonoToDeg(x[1]^2*x[2]^3,x,2); MonoToDeg:=proc(mono,x,n) local i: [seq(degree(mono,x[i]),i=1..n)]: end: #Cx(p,t,x): The weight-enumerators of simple connected graphs on #up to vertices #accorsing to x[1]^degree[1]*x[2]^degree[2]* .. . #For example, try: #Cx(3,t,x); Cx:=proc(p,t,x) local p1,gu,mu1,gu1,coe,T,i1,i,mu,S,kap,r1,pip,gu11: print(`Wrong methodology, needs more work`): RETURN(FAIL): gu:=add(Nx(p1,x)*t^p1,p1=1..p): gu:=log(1+gu): gu:=taylor(gu,t=0,p+1): gu:=expand(add(expand(coeff(gu,t,i1))*t^i1,i1=1..p)): mu:={}: for p1 from 1 to p do gu1:=coeff(gu,t,p1): for i from 1 to nops(gu1) do gu11:=op(i,gu1): mu1:=[p1,op(MonoToDeg(gu11,x,p))]: mu:=mu union {mu1}: coe:=normal(gu11/mul(x[i1]^mu1[i1+1],i1=1..p)): T[mu1]:=coe: od: od: for mu1 in mu do print(`mu1 is`, mu1): kap:=igcd(op(mu1)): print(`kap is`, kap): S[mu1]:=0: for r1 in divisors(kap) do print(`r1 is`, r1): pip:=[seq(mu1[i1]/r1,i1=1..p+1)]: print(`pip is`, pip): if member(pip,mu) then S[mu1]:=S[mu1]+T[pip]*mobius(r1)/r1: fi: od: od: add(S[mu1]*t^mu1[1]*mul(x[i1]^mu1[i1+1],i1=1..p),mu1 in mu): end: #Wt2xMG(j,x,t,M): The weight accorsing to degrees of #up to 2*M edges #of a partition j for counting graphs for multi-graphs Wt2xMG:=proc(j,x,t,M) local p,gu,r,s,i,n,r1,s1,i1: n:=nops(j): p:=ParToCyc(j): gu:=1: for r from 1 to nops(p) do for s from r+1 to nops(p) do r1:=nops(p[r]): s1:=nops(p[s]): gu:=gu*(1- mul(x[i]^(s1/gcd(r1,s1)),i in p[r])*mul(x[i]^(r1/gcd(r1,s1)),i in p[s])) ^(-gcd(r1,s1)): od: od: for r from 1 to nops(p) do if nops(p[r]) mod 2 =0 then gu:=gu*(1-mul(x[i],i in p[r]))^(-1)* (1-mul(x[i]^2,i in p[r]))^(-(nops(p[r])-2)/2): else gu:=gu*(1-mul(x[i]^2,i in p[r]) )^( -(nops(p[r])-1)/2 ): fi: od: gu:=normal(gu): gu:=subs({seq(x[i1]=t*x[i1],i1=1..n)},gu): gu:=taylor(gu,t=0,2*M+1): gu:=add(expand(coeff(gu,t,i1))*t^i1,i1=0..2*M): add(theta(coeff(gu,t,i1),n,x)*t^i1,i1=0..2*M): end: #NxMG(p,x,t,M): The weight-enumerator of multi-graphs on p vertices #accorsing to x[1]^degree[1]*x[2]^degree[2]* ..*t^edges #For example, try: #NxMG(3,x,t,4); NxMG:=proc(p,x,t,M) local mu,j,lu: option remember: mu:=Pars(p): lu:=expand(add(Wt0(j)*Wt2xMG(j,x,t,M) , j in mu)): lu:=subs(t=t^(1/2),lu): end: #UMGdeg(L): the number of all (connected or not) unlabeled #multi-graphs #with degree sequence L #For example, try: #UMGdeg([3$6]); UMGdeg:=proc(L) local p,gu,x,i,M,t: p:=nops(L): M:=convert(L,`+`)/2: gu:=NxMG(p,x,t,M): gu:=subs(t=1,gu); for i from 1 to p do gu:=coeff(gu,x[i],L[i]): od: gu: end: #UGdeg(L): the number of all (connected or not) unlabeled #simple graphs #with degree sequence L #For example, try: #UGdeg([3$6]); UGdeg:=proc(L) local p,gu,x,i,M,t: p:=nops(L): M:=convert(L,`+`)/2: gu:=Nx(p,x,t,M): gu:=subs(t=1,gu); for i from 1 to p do gu:=coeff(gu,x[i],L[i]): od: gu: end: #NIVecs1(k,a,N): the set of weakly-decreasing #vectors of non-neg. integers of length k #that add-up to N and that start with a # Try: #NIVecs1(3,2,4); NIVecs1:=proc(k,a,N) local gu,gu1,a1,g1: option remember: if a>N then RETURN({}): fi: if k<=0 then RETURN({}): fi: if k=1 then if N=a then RETURN({[a]}): else RETURN({}): fi: fi: gu:={}: for a1 from 0 to a do gu1:=NIVecs1(k-1,a1,N-a): gu:=gu union {seq([a,op(g1)],g1 in gu1)}: od: gu: end: #NIPVecs(k,N,a): the set of weakly-decreasing #vectors of pos. integers <=a of length k #that add-up to N # Try: #NIPVecs(3,4,2); NIPVecs:=proc(k,N,a) local gu,g,i: gu:=NIVecs(k,N-k,a): {seq([seq(g[i]+1,i=1..nops(g))],g in gu)}: end: #NIVecs(k,N,a): the set of weakly-decreasing #vectors of non-neg. integers <=a of length k #that add-up to N # Try: #NIVecs(3,4,2); NIVecs:=proc(k,N,a) local a1: if k=0 then if N=0 then RETURN({[]}): else RETURN({}): fi: fi: {seq(op(NIVecs1(k,a1,N)), a1 =0..min(a,N))}: end: #GrabCycle(pi,i): the cycle belonging to i GrabCycle:=proc(pi,i) local j,gu: gu:=[i]: if pi[i]=i then RETURN(gu): fi: j:=pi[i]: while j<>i do gu:=[op(gu),j]: j:=pi[j]: od: gu: end: #PerToCyc(pi): converts the permutation to cycle structure PerToCyc:=proc(pi) local mu,gu,i,gu1: mu:={op(pi)}: gu:=[]: while mu<>{} do i:=mu[1]: gu1:=GrabCycle(pi,i): mu:=mu minus {op(gu1)}: gu:=[op(gu),gu1]: od: gu: end: #InPer(pi,k): inputs a permutation pi and outputs the induced #permutation on k-subsets of {1, ..., n}. For example try: #InPer([1,3,2],2); InPer:=proc(pi,k) local T,mu,n,mu1,f,g,i: n:=nops(pi): mu:=choose(n,k): for i from 1 to nops(mu) do T[mu[i]]:=sort([seq(pi[mu1],mu1 in mu[i])]): od: for i from 1 to nops(mu) do f[i]:=mu[i]: g[mu[i]]:=i: od: [seq(g[T[mu[i]]],i=1..nops(mu))]: end: #CycToPer(sig): converts from cycle notation to #one-line notation CycToPer:=proc(sig) local T,i,j,n: n:=add(nops(sig[i]),i=1..nops(sig)): for i from 1 to nops(sig) do for j from 1 to nops(sig[i])-1 do T[sig[i][j]]:=sig[i][j+1] : od: T[sig[i][nops(sig[i])]]:=sig[i][1]: od: [seq(T[i],i=1..n)]: end: #Wtk(j,k,s): The weight of a partition j for counting k-uniform hypergraphs #For example, try: #Wtk([1,1],2,s); Wtk:=proc(j,k,s) local gu,k1,i1,i2,i3,co,sig,i,gadol: option remember: gu:=mul((1/k1)^j[k1]/j[k1]!,k1=1..nops(j)): sig:=[]: co:=0: for i1 from 1 to nops(j) do for i2 from 1 to j[i1] do sig:=[op(sig),[seq(i3,i3=co+1..co+i1)]]: co:=co+i1: od: od: sig:=CycToPer(sig): sig:=InPer(sig,k): sig:=PerToCyc(sig): gadol:=max(seq(nops(sig[i]),i=1..nops(sig))): gu*mul(s[nops(sig[i])],i=1..nops(sig)),gadol: end: #CIk(s,k,n): The cycle-index polynomial of S_n using s[1], ..., s[n] #for k-uniform hypergraphs. For example, try: #CIk(s,2,3); CIk:=proc(s,k,n) local gu,j: gu:=Pars(n): add(Wtk(j,k,s)[1], j in gu), max(seq(Wtk(j,k,s)[2], j in gu)): end: #HGnx(n,k,x): the generating function of all unlabeled #k-uniform hypergraphs with #n vertices according to the number of edges. For example, try: #HGnx(5,2,x); HGnx:=proc(n,k,x) local gu,s,i: gu:=CIk(s,k,n): expand(subs({seq(s[i]=1+x^i,i=1..gu[2])},gu[1])): end: #HGn(n,k): the number of all unlabeled #k-uniform hypergraphs with #n vertices according to the number of edges. For example, try: #HGnx(5,3); HGn:=proc(n,k) local gu,s,i: gu:=CIk(s,k,n): expand(subs({seq(s[i]=2,i=1..gu[2])},gu[1])): end: #HGseq(k,n): the first n terms of the sequence counting the #number of unlabeled k-uniform hypergraphs #For example, try: #HGseq(2,10); HGseq:=proc(k,n) local i,x: [seq(HGn(i,k),i=1..n)]: end: #HGseqx(k,n,x): the first n terms of the sequence counting the #number of unlabeled k-uniform hypergraphs #For example, try: #HGseqx(2,10,x); HGseqx:=proc(k,n,x) local i: [seq(HGnx(i,k,x),i=1..n)]: end: #ApplySiPer(v,pi,s): given a signed permutation (pi,s) #applies it to the [0,1] vector v. For example, try: #ApplySiPer([1,0,1],[2,3,1],[1,0,0]) ApplySiPer:=proc(v,pi,s) local i,v1,v2: v1:=[seq(v[pi[i]],i=1..nops(pi))]: v2:=[]: for i from 1 to nops(s) do if s[i]=1 then v2:=[op(v2),v1[i]]: else v2:=[op(v2),1-v1[i]]: fi: od: v2: end: Cube1:=proc(n) local gu,g: option remember: if n=0 then RETURN({[]}): fi: gu:=Cube1(n-1): {seq([op(g),0], g in gu), seq([op(g),1], g in gu)}: end: #InSiPer(pi,s): inputs a signed permutation (pi,s) and outputs the induced #permutation on {0,1}^n (n=nops(pi)) . #For example, try: #InSiPer([1,3,2],[1,0,1]); InSiPer:=proc(pi,s) local T,mu,n,f,g,i: n:=nops(pi): mu:=Cube1(n): for i from 1 to nops(mu) do T[mu[i]]:=ApplySiPer(mu[i],pi,s): od: for i from 1 to nops(mu) do f[i]:=mu[i]: g[mu[i]]:=i: od: [seq(g[T[mu[i]]],i=1..nops(mu))]: end: #WtSiPer(j,si,s): The weight of a #partition j followed by a sign-vector #for counting Boolean functions #For example, try: #WtSiPer([1,1],[1,1,0],s); WtSiPer:=proc(j,si,s) local gu,k1,i1,i2,i3,co,sig,i,gadol,n: option remember: n:=add(i*j[i],i=1..nops(j)): if nops(si)<>n then ERROR(`Bad input`): fi: gu:=mul((1/k1)^j[k1]/j[k1]!,k1=1..nops(j)): sig:=[]: co:=0: for i1 from 1 to nops(j) do for i2 from 1 to j[i1] do sig:=[op(sig),[seq(i3,i3=co+1..co+i1)]]: co:=co+i1: od: od: sig:=CycToPer(sig): sig:=InSiPer(sig,si): sig:=PerToCyc(sig): gadol:=max(seq(nops(sig[i]),i=1..nops(sig))): gu*mul(s[nops(sig[i])],i=1..nops(sig)),gadol: end: #CICube(s,n): The cycle-index polynomial of the group #of signed permutations acting on the Boolean lattice #using using s[1], ..., s[n] #For example try: #CICube(s,3); CICube:=proc(s,n) local gu1,gu2,j,g2,tot,ma: gu1:=Pars(n): gu2:=Cube1(n): ma:=0: tot:=0: for g2 in gu2 do tot:=tot+add(WtSiPer(j,g2,s)[1], j in gu1): ma:=max(ma,seq(WtSiPer(j,g2,s)[2], j in gu1)): od: tot,ma: end: #Bn(n): the number of Boolean functions on n variables #up to symmetry and negation #For example, try: #Bn(3); Bn:=proc(n) local gu,s,i: gu:=CICube(s,n): expand(subs({seq(s[i]=2,i=1..gu[2])},gu[1]))/2^n: end: #Bnx(n,x): the number of Boolean functions on n variables #up to symmetry and negation #For example, try: #Bnx(3,x); Bnx:=proc(n,x) local gu,s,i: gu:=CICube(s,n): expand(subs({seq(s[i]=1+x^i,i=1..gu[2])},gu[1]))/2^n: end: #BnSeq(n): the first #n terms of the sequence for the #number of Boolean functions on n variables #up to symmetry and negation #For example, try: #BnSeq(3); BnSeq:=proc(n) local n1: [seq(Bn(n1),n1=1..n)]: end: #BnxSeq(n,x): the first #n terms of the sequence for the #number of Boolean functions on n variables #up to symmetry and negation #For example, try: #BnxSeq(3,x); BnxSeq:=proc(n,x) local n1: [seq(Bnx(n1,x),n1=1..n)]: end: