Cycle Polynomial

Author

Eric W. Weisstein
December 29, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/CyclePolynomial.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/CyclePolynomial.html.

©2023 Wolfram Research, Inc. except for portions noted otherwise

Parametrized families

Andrasfai

(poly=Factor@Table[GraphData[{"Andrasfai",n},"CyclePolynomial"][x],{n,k0=1,kmax=10}])//Column

Antelope n×n

(poly=Factor[Table[GraphData[{"Antelope",{n,n}},"CyclePolynomial"],{n,k0=1,kmax=10}]/.f_Function:>f[x]])//Column

Antiprism

A296542

Have linear recurrence but not closed form

Entity["Graph",{"Antiprism",n}]["CycleCount"]

Entity["Graph",{"Antiprism",n}]["CyclePolynomial"]

(poly=Factor@Table[GraphData[{"Antiprism",n},"CyclePolynomial"],{n,k0=3,kmax=25}]/.f_Function:>f[x])//Column

(c=CoefficientList[Take[poly/x^3,7],x])//Column

Flatten[c]

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

CoefficientList[LinearRecurrence[{2+2 x+3 (x^2),-1-4 x-7 (x^2)-4 (x^3)-(x^4),-x (-2-5 x-8 (x^2)-4 (x^3)-2 (x^4)+2 (x^5)),(x^2) (-1-4 x-5 (x^2)-4 (x^3)+3 (x^4)),(x^4) (2+2 x+(x^6)),-(x^6) (1+2 (x^4)),(x^10)},{8 (x^3)+15 (x^4)+24 (x^5)+16 (x^6),8 (x^3)+10 (x^4)+24 (x^5)+52 (x^6)+56 (x^7)+29 (x^8),10 (x^3)+10 (x^4)+12 (x^5)+35 (x^6)+100 (x^7)+160 (x^8)+140 (x^9)+56 (x^10),12 (x^3)+12 (x^4)+12 (x^5)+14 (x^6)+48 (x^7)+177 (x^8)+388 (x^9)+498 (x^10)+348 (x^11)+110 (x^12),14 (x^3)+14 (x^4)+14 (x^5)+14 (x^6)+16 (x^7)+63 (x^8)+294 (x^9)+833 (x^10)+1428 (x^11)+1470 (x^12)+854 (x^13)+225 (x^14),16 (x^3)+16 (x^4)+16 (x^5)+16 (x^6)+16 (x^7)+18 (x^8)+80 (x^9)+464 (x^10)+1632 (x^11)+3532 (x^12)+4848 (x^13)+4176 (x^14)+2080 (x^15)+469 (x^16),18 (x^3)+18 (x^4)+18 (x^5)+18 (x^6)+18 (x^7)+18 (x^8)+20 (x^9)+99 (x^10)+702 (x^11)+2979 (x^12)+7848 (x^13)+13545 (x^14)+15534 (x^15)+11493 (x^16)+5004 (x^17)+991 (x^18)},10]/x^3,x]//Flatten

Take[poly,7]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

soln=RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n]

(simp=Simplify[%,n∈Integers&&n>2&&x∈Reals])//Timing

Table[-((2 n (x^3))/(-1+x))+((2 n (x^(1+2 n)))/(-1+x))-GraphData[{"Antiprism",n},"CyclePolynomial"][x],{n,3,6}]//Factor//Expand//Column

(fullsimp=FullSimplify[simp,n∈Integers&&n>2&&x∈Reals])//Timing

Table[((x^5) ((Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,2])^(-3+n)) ((x^2) (1+x) (-2+x (-15+x (21+x (133+x (33+x (-349+x (-551+x (88+x (730+x (571+149 x))))))))))+x (2+x (28+x (29+x (-148+x (-446+x (-288+x (802+x (1784+x (1612+3 x (240+43 x)))))))))) Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,2]+(2+x (17+x (-2+x (-118+x (-162+x (68+x (504+x (580+x (298+61 x))))))))) Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,1] Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,3]))/(((((x^2)-Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,2]))^2) (((-1+Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,2]))^2) (-(x^2)+2 (x^4)+((Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,2])^2)+2 Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,1] Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,3]))+((x^5) ((Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,3])^(-3+n)) ((x^5) (2+x (8+x (-12+x (-72+x (-19+x (108+x (202+x (124+27 x))))))))+2 x (1+x) (-1+x (-3+x (11+x (34+x (-36+x (-95+2 x (-21+x (51+x (58+17 x))))))))) Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,3]+(2+x (17+x (-2+x (-118+x (-162+x (68+x (504+x (580+x (298+61 x))))))))) ((Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,3])^2)))/(((((x^2)-Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,3]))^2) (((-1+Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,3]))^2) (-Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,1]+Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,3]) (-Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,2]+Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,3]))+((x^5) ((Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,1])^(-3+n)) (Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,2] (-x (2+x (28+x (29+x (-148+x (-446+x (-288+x (802+x (1784+x (1612+3 x (240+43 x))))))))))+(2+x (17+x (-2+x (-118+x (-162+x (68+x (504+x (580+x (298+61 x))))))))) Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,3])+x (x (2+x (41+x (92+x (-113+x (-874+x (-1338+x (416+x (3907+x (5826+x (4353+2 x (849+139 x)))))))))))-(2+x (28+x (29+x (-148+x (-446+x (-288+x (802+x (1784+x (1612+3 x (240+43 x)))))))))) Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,3])))/(((((x^2)-Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,1]))^2) (((-1+Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,1]))^2) (Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,1]-Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,2]) (Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,1]-Root[-(x^6)+((x^2)-2 (x^4)) #1+(-2 x-(x^2)) ((#1)^2)+((#1)^3)&,3])),{n,3,3}]//FullSimplify[#,x∈Reals&&n∈Integers&&n>0]&

(gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]])//Head//Timing

SeriesCoefficient[gf,{z,0,n}]

Apollonian

(poly=Factor@Table[GraphData[{"Apollonian",n},"CyclePolynomial"],{n,k0=1,kmax=6}]/.f_Function:>f[x])//Column

Barbell

(poly=Factor@Table[GraphData[{"Barbell",n},"CyclePolynomial"][x],{n,k0=3,20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,10]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>1]

Bishop

(l=Select[Table[GraphData[{"Bishop",{n,n}},"CyclePolynomial"][x],{n,3,20}],FreeQ[#,Missing|GraphData]&])//Quiet//Column

FindLinearRecurrence[l]

coef=FindPolynomialRecurrence[Drop[l,0],2]

FindGeneratingFunction[l,z]

(Subscript[c, 3])

c3=Table[System`FindCycle[GraphData[{"Bishop",{n,n}}],{3},All]//Length,{n,2,10}]

FindSequenceFunction[c3,n-1]//Factor

Table[(1/6) (-2+n) (((-1+n))^2) n,{n,2,10}]

(Subscript[c, 4])

c4=Table[System`FindCycle[GraphData[{"Bishop",{n,n}}],{4},All]//Length,{n,2,10}]

FindSequenceFunction[c4,n-1]//Factor

Table[(1/30) (-2+n) (-1+n) n (11-11 n+3 (n^2)),{n,2,10}]

(Subscript[c, 5])

c5=Table[System`FindCycle[GraphData[{"Bishop",{n,n}}],{5},All]//Length,{n,2,10}]

(c5=Table[System`FindCycle[BishopGraph[n],{5},All]//Length,{n,16}])//Timing

FindSequenceFunction[Drop[c5,2],n-3]//Factor

FindGeneratingFunction[Drop[c5,3],x]

FindGeneratingFunction[Drop[c5,3][[1;;All;;2]],x]

FindGeneratingFunction[Drop[c5,3][[2;;All;;2]],x]

FindGeneratingFunction[Drop[c5,3][[1;;All;;2]],x]

FindGeneratingFunction[Drop[c5,3][[2;;All;;2]],x]

FindLinearRecurrence[Drop[c5,3]]

(Subscript[c, 6])

c6=Table[System`FindCycle[GraphData[{"Bishop",{n,n}}],{6},All]//Length,{n,2,10}]

c5=Table[System`FindCycle[BishopGraph[n],{6},All]//Length,{n,14}]

FindSequenceFunction[Drop[c6,2],n]//Factor

FindGeneratingFunction[Drop[c6,2],x]

FindLinearRecurrence[Drop[c6,2]]

Table[(1/840)(n (n-1) (40 n^5-289 n^4+887 n^3-2193 n^2+3792 n-1934)-210 (n^2-12 n+26)Floor[n/2]),{n,10}]

BlackBishop n×n

(poly=Table[GraphData[{"BlackBishop",{n,n}},"CyclePolynomial"],{n,k0=1,10}]/.f_Function:>f[x])//Column

Book

(poly=Factor@Table[GraphData[{"Book",n},"CyclePolynomial"][x],{n,k0=3,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Bruhat

(poly=Factor[Table[GraphData[{"Bruhat",n},"CyclePolynomial"],{n,k0=1,kmax=6}]/.f_Function:>f[x]])//Column

CocktailParty

A167986

https://oeis.org/A167986

(poly=Table[GraphData[{"CocktailParty",n},"CyclePolynomial"]/.f_Function:>f[x],{n,k0=1,20}])//Column

Take[poly,4]//Column

T[n_,k_]:=Sum[(-1)^j*Binomial[n,j]*Binomial[2*(n-j),k-2*j]*2^j*(k-j-1)!/2,{j,0,Floor[k/2]}]

T[n,k]

T[n_]:=Sum[x^k T[n,k],{k,3,2n}]

Sum[(x^k)(1/2) Binomial[2 n,k] (-1+k)! HypergeometricPFQ[{(1/2)-(k/2),-(k/2)},{1-k,(1/2)-n},-2],{k,3,2n}]

Table[T[n,k],{n,5},{k,3,2 n}]//Column

Table[T[n],{n,4}]//Column

Table[Sum[Binomial[2 n,k] (k-1)! HypergeometricPFQ[{(1/2)-(k/2),-(k/2)},{1-k,(1/2)-n},-2](x^k)/2,{k,3,2n}],{n,5}]//Column

Table[Sum[Binomial[2 n,k] (k-1)! HypergeometricPFQ[{(1/2)-(k/2),-(k/2)},{1-k,(1/2)-n},-2](x^k)/2,{k,3,2n}],{n,14}]===Take[poly,14]

FullSimplify[Binomial[2 n,k] (k-1)! HypergeometricPFQ[{(1/2)-(k/2),-(k/2)},{1-k,(1/2)-n},-2]/2,]

Table[Binomial[2 n,k] Gamma[k]HypergeometricPFQ[{(1-k)/2,-(k/2)},{1-k,(1/2)-n},-2]/2,{n,7},{k,3,2n}]//Flatten

Do[Print[Head@FindLinearRecurrence[DeleteMissing@Drop[poly,k]]]//Timing,{k,0,3}]

coef=Factor/@FindPolynomialRecurrence[poly,7]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Complete

Entity["Graph",{"Complete",n}]["CyclePolynomial"][x]

A144151

(poly=Factor@Table[GraphData[{"Complete",n},"CyclePolynomial"][x],{n,k0=1,20}])//Column

CoefficientList[Take[poly,7]/x^3,x]

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,9]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"CyclePolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

poly=Table[GraphData[{"Complete",n},"CyclePolynomial"][x],{n,3,20}]//Factor

coef=Factor/@FindLinearRecurrence[poly]

(1/2)Sum[Binomial[n,k]((((k-1)!x))^k),{k,3,n}]

l=Table[(1/2)Sum[Binomial[n,k](k-1)!(x^k),{k,3,n}],{n,10}]//Expand

bug(331160)

Gave PFQ in V6

Drop[CoefficientList[#,x],3]&/@l//Column

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["CyclePolynomial"]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["CyclePolynomial"][x]

A291909

Table[n^2 x^2 (HypergeometricPFQ[{1,1,1-n,1-n},{2},x^2]-1)/2,{n,10}]//Expand//Column

(poly=DeleteMissing@Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"CyclePolynomial"],{n,k0=1,20}]/.f_Function:>f[x])//Column

Length/@poly

CoefficientList[Take[poly,5],x]//Column

coef=Factor/@FindLinearRecurrence[poly]

(1/2)Sum[((Binomial[n,k])^2)k!(k-1)!(x^(2k)),{k,2,n}]

Table[(1/2)Sum[((Binomial[n,k])^2)k!(k-1)!(x^(2k)),{k,2,n}],{n,5}]//Factor

Take[poly,5]

CoefficientList[Table[Sum[((Binomial[n,k])^2)k!(k-1)!(x^k),{k,2,n}]/2,{n,10}],x]//Flatten

Table[(1/2)Sum[((Binomial[n,k])^2)k!(k-1)!(x^(2k)),{k,2,n}],{n,5}]//Expand//Column

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["CyclePolynomial"]

CompleteTripartite n×n×n

Activate@Table[Evaluate[Entity["Graph",{"CompleteTripartite",{n,n,n}}]["CycleCount"]],{n,10}]

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["CycleCount"]

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["CyclePolynomial"]

Entity["Graph",{"Complete",n}]["CyclePolynomial"][x]

Entity["Graph",{"CompleteBipartite",{n,n}}]["CyclePolynomial"][x]

Table[Sum[(x^(3k))((Binomial[n,k])^3)(k+1)!k!(k-1)!,{k,n}]/2,{n,5}]//Column

A296546

(poly=Table[GraphData[{"CompleteTripartite",{n,n,n}},"CyclePolynomial"],{n,k0=1,kmax=10}]/.f_Function:>f[x])//Column

CoefficientList[Take[poly,5]/x^3,x]//Flatten

Table[Tally[Length/@FindCycle[CompleteGraph[{n,n,n}],Infinity,All]][[All,2]],{n,4}]

%//Column

%%//Flatten

CoefficientList[DeleteMissing@poly,x]//Column

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@poly/x^3,k]]//Head//Timing}],{k,0,3}]

Coefficient[#,x,3]&/@poly

FindSequenceFunction[%,n]

Coefficient[#,x,4]&/@poly

FindSequenceFunction[%,n]//Factor

Coefficient[#,x,5]&/@poly

FindSequenceFunction[%,n]//Factor

Coefficient[#,x,6]&/@DeleteMissing@poly

FindSequenceFunction[%,n]//Factor

FindLinearRecurrence[%]

coef=Factor/@FindPolynomialRecurrence[DeleteMissing@poly,5]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

Factor[(z^(k0-1))FindGeneratingFunction[DeleteMissing@poly,z]]//Head//Timing

SeriesCoefficient[gf,{z,0,n}]

CrossedPrism

(poly=Factor@Table[GraphData[{"CrossedPrism",n},"CyclePolynomial"][x],{n,k0=4,20,2}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

Crown

(poly=Table[GraphData[{"Crown",n},"CyclePolynomial"]/.f_Function:>f[x],{n,20}])//Column

CoefficientList[Take[poly,6],x]//Column

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@poly,k]]//Head//Timing}],{k,2,8}]

coef=Factor/@FindPolynomialRecurrence[Drop[l,0],5]

(Subscript[c, 3])

c3=Table[System`FindCycle[GraphData[{"Crown",n}],{3},All]//Length,{n,3,10}]

(Subscript[c, 4])

c4=Table[System`FindCycle[GraphData[{"Crown",n}],{4},All]//Length,{n,3,12}]

FindSequenceFunction[c4,n-2]//Factor

Table[%,{n,3,12}]

(Subscript[c, 5])

c4=Table[System`FindCycle[GraphData[{"Crown",n}],{5},All]//Length,{n,3,12}]

(Subscript[c, 6])

c6=Table[System`FindCycle[GraphData[{"Crown",n}],{6},All]//Length,{n,3,12}]

FindSequenceFunction[c6,n-2]//Factor

Table[%,{n,3,12}]

(Subscript[c, 7])

c7=Table[System`FindCycle[GraphData[{"Crown",n}],{7},All]//Length,{n,3,12}]

(Subscript[c, 8])

c8=Table[System`FindCycle[GraphData[{"Crown",n}],{8},All]//Length,{n,3,9}]

c8=Table[Coefficient[GraphData[{"Crown",n},"CyclePolynomial"][x],x,8],{n,3,13}]

FindSequenceFunction[c8,n-2]//Factor

Table[%,{n,3,13}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["CyclePolynomial"]

(poly=Factor@Table[GraphData[{"CubeConnectedCycle",n},"CyclePolynomial"],{n,k0=3,8}]/.f_Function:>f[x])//Column

Cycle

Entity["Graph",{"Cycle",n}]["CyclePolynomial"][x]

(poly=Factor@Table[GraphData[{"Cycle",n},"CyclePolynomial"][x],{n,k0=3,20}])

CycleComplement

(poly=Factor@Table[GraphData[{"CycleComplement",n},"CyclePolynomial"],{n,k0=3,20}]/.f_Function:>f[x])//Column

CoefficientList[Take[poly,6],x]//Column

Do[Print[{k,FindLinearRecurrence[Drop[poly,k]]//Head//Timing}],{k,2,6}]

Do[Print[{k,FindSequenceFunction[Drop[poly,k],n-2-k]//Head//Timing}],{k,2,6}]

Do[Print[{k,FindGeneratingFunction[Drop[poly,k],z]//Head//Timing}],{k,2,6}]

DiagonalIntersection

(poly=Factor@Table[GraphData[{"DiagonalIntersection",n},"CyclePolynomial"],{n,k0=3,14}]/.f_Function:>f[x])//Column

seq=Drop[#,3]&/@CoefficientList[DeleteMissing[poly],x]

Flate

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

Dipyramid

(poly=Factor@Table[GraphData[{"Dipyramid",n},"CyclePolynomial"],{n,k0=3,20}]/.f_Function:>f[x])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

soln=RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n]

(simp=Simplify[%,n∈Integers&&n>2&&x∈Reals])//Timing

(gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]])//Head//Timing

SeriesCoefficient[gf,{z,0,n}]

DorogovtsevGoltsevMendes

(poly=Factor@Table[GraphData[{"DorogovtsevGoltsevMendes",n},"CyclePolynomial"],{n,k0=0,7}]/.f_Function:>f[x])//Column

Do[Print[{{"DorogovtsevGoltsevMendes",n},CyclePolynomial[DorogovtsevGoltsevMendesGraph[n],x,Debug->False,Method->"FindCycle"]//Timing}],{n,5}];

Do[Print[{{"DorogovtsevGoltsevMendes",n},CyclePolynomial[DorogovtsevGoltsevMendesGraph[n],x,Debug->False,Method->"FindPath"]//Timing}],{n,5}];

Do[Print[{{"DorogovtsevGoltsevMendes",n},CyclePolynomial[DorogovtsevGoltsevMendesGraph[n],x,Debug->True,Method->"FindPath"]//Timing}],{n,{5}}];

Empty

Entity["Graph",{"Empty",n}]["CyclePolynomial"][x]

(poly=Factor@Table[GraphData[{"Empty",n},"CyclePolynomial"][x],{n,k0=3,10}])

FibonacciCube

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"CyclePolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

CoefficientList[poly,x^2]

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Fiveleaper n×n

(poly=Factor[Table[GraphData[{"Fiveleaper",{n,n}},"CyclePolynomial"],{n,k0=1,kmax=10}]/.f_Function:>f[x]])//Column

FoldedCube

(poly=Factor@Table[GraphData[{"FoldedCube",n},"CyclePolynomial"][x],{n,k0=2,5}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Gear

(poly=Factor@Table[GraphData[{"Gear",n},"CyclePolynomial"][x],{n,k0=3,20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["CyclePolynomial"]

Grid n×n

A302337

Entity["Graph",{"Grid",{n,n}}]["CyclePolynomial"]

Entity["Graph",{"Grid",{n,n}}]["Circumference"]

Table[Floor[n^2/2],{n,10}]

(poly=Factor@Table[GraphData[{"Grid",{n,n}},"CyclePolynomial"],{n,k0=1,kmax=10}]/.f_Function:>f[x])//Column

(coef=Factor/@FindLinearRecurrence[DeleteMissing@poly])//Head

CoefficientList[Rest@DeleteMissing@poly,x][[All,5;;;;2]]//Column

Length/@%

Flatten[%]

Flatten[Table[Tally[Length/@FindCycle[GridGraph[{n,n}],Infinity,All]][[All,2]],{n,6}]]

Sums

A140517

DeleteMissing[poly]/.x->1

Coefficients

(polys=Table[FindSequenceFunction[Table[Length[System`FindCycle[System`GridGraph[{k,k}],{2n},All]],{k,n,n+3}],x-n+1],{n,9}]/.x->n//Expand)//Column//Timing

polys//InputForm

Do[Print[{nn,Expand[FindSequenceFunction[Table[Length[System`FindCycle[System`GridGraph[{k,k}],{2nn},All]],{k,nn,nn+3}],n-nn+1]]//Timing,MaxMemoryUsed[]/10^9. GB}],{nn,11}]

data={{1,{0.001`,0},0.578847664` GB},{2,{0.002`,1-2 n+(n^2)},0.578847664` GB},{3,{0.002`,4-6 n+2 (n^2)},0.578847664` GB},{4,{0.004999`,26-28 n+7 (n^2)},0.578847664` GB},{5,{0.013998`,164-140 n+28 (n^2)},0.578847664` GB},{6,{0.070989`,1046-740 n+124 (n^2)},0.578847664` GB},{7,{0.455931`,6672-4056 n+588 (n^2)},0.578847664` GB},{8,{3.335493`,42790-22904 n+2938 (n^2)},0.578847664` GB},{9,{25.074187`,275888-132344 n+15268 (n^2)},1.4063546640000002` GB},{10,{187.172547`,1787624-778832 n+81826 (n^2)},8.939197096000001` GB},{11,{1532.032096`,11634704-4652404 n+449572 (n^2)},60.758706848` GB}};

polys=data[[All,2,2]]

Constant:

A302335

coef0=Coefficient[polys,n,0]

FindGeneratingFunction[coef0,x]//Head//Timing

Linear:

A302336

coef1=-Coefficient[polys,n,1]

FindGeneratingFunction[coef1,x]//Head//Timing

Quadratic:

A002931

coef2=Coefficient[polys,n,2]

coef2={0,1,2,7,28,124,588,2938,15268,81826,449572,2521270,14385376,83290424,488384528,2895432660,17332874364,104653427012,636737003384,3900770002646,24045500114388,149059814328236,928782423033008,5814401613289290,36556766640745936};

FindGeneratingFunction[coef2,x]//Head//Timing

(Subscript[c, -1])

A301648

Coefficient[#,x,Exponent[#,x]]&/@DeleteMissing[poly]

(Subscript[c, -1]) for n even

A003763

Coefficient[#,x,Exponent[#,x]]&/@DeleteMissing[poly][[2;;;;2]]

(Subscript[c, 4])==1-2 n+(n^2)

Table[System`FindCycle[System`GridGraph[{n,n}],{4},All]//Length,{n,12}]

c[[All,1]]

Table[n^2,{n,5}]

(Subscript[c, 6])==4-6 n+2 (n^2)

A046092(n-2)

Table[System`FindCycle[System`GridGraph[{n,n}],{6},All]//Length,{n,12}]

Table[2(n-1)(n-2),{n,12}]

Rest[c][[All,2]]

2(n-1)(n-2)/.n->3

Table[2(n-1)(n-2),{n,8}]

(Subscript[c, 8])==({{{, ({{0, n<3}, {26-28 n+7 (n^2), True}})}})

Expand[7(n-2)^2-2]

Drop[c,1][[All,3]]

Table[System`FindCycle[System`GridGraph[{n,n}],{8},All]//Length,{n,2,12}]

Factor[7n^2-2/.n->n-2]

Table[7(n-2)^2-2,{n,2,12}]

Table[Piecewise[{{0,n==2}},7(n-2)^2-2],{n,2,12}]

(Subscript[c, 10])==({{{, ({{0, n<4}, {164-140 n+28 (n^2), True}})}})

(c10=Table[System`FindCycle[System`GridGraph[{n,n}],{10},All]//Length,{n,12}])//Timing

FindLinearRecurrence[Drop[c10,4]]

FindGeneratingFunction[{52,164,332,556,836,1172,1564,2012,2516},x]

Factor[28 x^2+28 x−4]

Factor[28 x^2+28 x−4/.x->n-3]

Table[4 (-1-7 n+7 (n^2)),{n,2,12}]

Table[Piecewise[{{0,n<4}},4 (41-35 n+7 (n^2))],{n,12}]

Table[Piecewise[{{0,n<4}},4(7(n-3)^2+7(n-3)-1)],{n,12}]

(Subscript[c, 10])==Piecewise[{{0,n<4}},4 (41-35 n+7 (n^2))]

(Subscript[c, 12])==({{{, ({{0, n<4}, {76, n==4}, {1046-740 n+124 (n^2), True}})}})

(c12=Table[System`FindCycle[System`GridGraph[{n,n}],{12},All]//Length,{n,16}])//Timing

FindLinearRecurrence[Drop[c12,4]]

FindGeneratingFunction[%128,x]//Factor

FindGeneratingFunction[{446,1070,1942,3062,4430,6046,7910,10022,12382,14990,17846,20950},x]

SeriesCoefficient[%,{x,0,n}]

Series[((2 (-38-109 x+20 (x^2)+3 (x^3))x^4)/(((-1+x))^3)),{x,0,10}]

SeriesCoefficient[((2 (-38-109 x+20 (x^2)+3 (x^3))x^4)/(((-1+x))^3)),{x,0,n}]

2 (523-370 n+62 (n^2))/.n->4

Table[Piecewise[{{0,n<4},{76,n==4}},2 (523-370 n+62 (n^2))],{n,2,16}]

(Subscript[c, 12])==Piecewise[{{0,n<4},{76,n==4}},2 (523-370 n+62 (n^2))]

Factor[523-370 n+62 (n^2)/.n->n+4]

Factor[35+126 n+62 (n^2)/.n->n-4]

Table[Factor[523-370 n+62 (n^2)/.n->n+k],{k,-5,5}]

FunctionExpand@FindSequenceFunction[%128,n]//FullSimplify

RSolve[{268+624 \[FormalN]+(1-\[FormalN]) \[FormalY][\[FormalN]]+(-3+\[FormalN]) \[FormalY][1+\[FormalN]]==0,\[FormalY][1]==76,\[FormalY][2]==446,\[FormalY][3]==1070,\[FormalY][4]==1942}, \[FormalY][\[FormalN]], \[FormalN]]

(Subscript[c, 14])==({{{, ({{0, n<4}, {32, n==4}, {1100, n==5}, {6672-4056 n+588 (n^2), True}})}})

(c14=Table[System`FindCycle[System`GridGraph[{n,n}],{14},All]//Length,{n,14}])//Timing

FindLinearRecurrence[Drop[c14,5]]

gf=FindGeneratingFunction[c,x]//Factor

Series[gf,{x,0,10}]

SeriesCoefficient[gf,{x,0,n}]

Factor[12 (-12+54 n+49 (n^2))/.n->n-4]

Table[Piecewise[{{0,n<4},{32,n==4},{1100,n==5}},12 (556-338 n+49 (n^2))],{n,2,14}]

(Subscript[c, 14])==Piecewise[{{0,n<4},{32,n==4},{1100,n==5}},12 (556-338 n+49 (n^2))]

(Subscript[c, 16])==({{{, ({{0, n<4}, {6, n==4}, {2102, n==5}, {11144, n==6}, {42790-22904 n+2938 (n^2), True}})}})

(c18=Table[System`FindCycle[System`GridGraph[{n,n}],{16},All]//Length,{n,14}])//Timing

FindLinearRecurrence[Drop[c18,6]]

gf=FindGeneratingFunction[c,x]//Factor

Series[gf,{x,0,10}]

SeriesCoefficient[gf,{x,0,n}]

Factor[-1818+600 n+2938 (n^2)/.n->n-4]

Table[Piecewise[{{0,n<4},{6,n==4},{2102,n==5},{11144,n==6}},2 (21395-11452 n+1469 (n^2))],{n,2,14}]

(Subscript[c, 16])==Piecewise[{{0,n<4},{6,n==4},{2102,n==5},{11144,n==6}},2 (21395-11452 n+1469 (n^2))]

Table[Factor[-1818+600 n+2938 (n^2)/.n->n+k],{k,-5,5}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["CyclePolynomial"]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["CyclePolynomial"]

(poly=Factor@Table[GraphData[{"Grid",{n,n,n}},"CyclePolynomial"],{n,k0=1,kmax=10}]/.f_Function:>f[x])//Column

Flatten[Table[Tally[Length/@FindCycle[GridGraph[{n,n,n}],Infinity,All]][[All,2]],{n,3}]]

HalvedCube

(poly=Factor@Table[GraphData[{"HalvedCube",n},"CyclePolynomial"][x],{n,k0=2,5}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Hanoi

(poly=Factor@Table[GraphData[{"Hanoi",n},"CyclePolynomial"]/.f_Function:>f[x],{n,k0=1,5}])//Column

Helm

(poly=Factor@Table[GraphData[{"Helm",n},"CyclePolynomial"][x],{n,k0=3,20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

HexagonalGrid n×n×n

(poly=Factor@Table[GraphData[{"HexagonalGrid",{n,n,n}},"CyclePolynomial"]/.f_Function:>f[x],{n,k0=1,5}])

CoefficientList[Take[poly,3],x]//Column

Hypercube

A085452

https://oeis.org/A085452

Entity["Graph",{"Hypercube",n}]["CyclePolynomial"]

Column[l=Table[GraphData[{"Hypercube",n},"CyclePolynomial"]/.f_Function:>f[x],{n,10}]]

Table[Table[Length[FindCycle[HypercubeGraph[n],{k},All]],{k,4,2^n,2}],{n,4}]//Column

c[4]=2^(n-2) Binomial[n,2]
c[6]=2^(n+1) Binomial[n,3]
c[8]=3 2^(n-3) Binomial[n,3] (27 n-79)

FindPolynomialRecurrence[Drop[l,1],8]

Drop[CoefficientList[#,x],4]&/@Rest@l//Column

Length[{24,128,696,2112,5024,5376,1344}]

Length[{80,640,6720,68736,591200,4652160,32146800,185285120,865894848,3136412160,8315531200,14800412160,15448366080,7413471744,906545760}]

{80,640,6720,68736,591200,4652160,32146800,185285120,865894848,3136412160,8315531200,14800412160,15448366080,7413471744,906545760}.x^Range[4,32,2]

GraphData[{"Hypercube",5},"CyclePolynomial"]

(Subscript[c, 3])

c3=Table[System`FindCycle[GraphData[{"Hypercube",n}],{3},All]//Length,{n,10}]

(Subscript[c, 4])

c4=Table[System`FindCycle[GraphData[{"Hypercube",n}],{4},All]//Length,{n,10}]

FindGeneratingFunction[{0,1,6,24,80,240,672,1792,4608,11520},x]

FindSequenceFunction[c4,n]//Factor

2^(n-2) Binomial[n,2]

Table[%,{n,10}]

(Subscript[c, 5])

c4=Table[System`FindCycle[GraphData[{"Hypercube",n}],{5},All]//Length,{n,10}]

(Subscript[c, 6])

c6=Table[System`FindCycle[GraphData[{"Hypercube",n}],{6},All]//Length,{n,10}]

FindGeneratingFunction[{0,0,16,128,640,2560,8960,28672,86016,245760},x]

FindSequenceFunction[c6,n]//Factor

2^(n+1) Binomial[n,3]

Table[%,{n,10}]

(Subscript[c, 8])

(c8=Table[System`FindCycle[HypercubeGraph[n],{8},All]//Length,{n,9}])//Timing

(c8=Table[System`FindCycle[HypercubeGraph[n],{8},All]//Length,{n,10}])//Timing

(c8=Table[System`FindCycle[HypercubeGraph[n],{8},All]//Length,{n,11}])//Timing

c8={0,0,6,696,6720,39840,184800,736512,2644992,8801280,27624960};

Table[GraphData[{"Hypercube",n},"CyclePolynomial"][x],{n,10}]

c8=Table[Coefficient[GraphData[{"Hypercube",n},"CyclePolynomial"][x],x,8],{n,10}]

FindSequenceFunction[c8,n]//Factor

Table[%,{n,11}]

3 2^(n-3) Binomial[n,3](27n-79)

Table[3 2^(n-3) Binomial[n,3](27n-79),{n,11}]

(Subscript[c, 10])

(c10=Table[System`FindCycle[HypercubeGraph[n],{10},All]//Length,{n,7}])//Timing

(c10=Table[System`FindCycle[HypercubeGraph[n],{10},All]//Length,{n,8}])//Timing

(c10=Table[System`FindCycle[HypercubeGraph[n],{10},All]//Length,{n,9}])//Timing

c10={0,0,0,2112,68736,698112,4591104,23697408,104509440};

FindSequenceFunction[Drop[c10,3],n]//Factor

FindGeneratingFunction[Drop[c10,3],x]

FindLinearRecurrence[Drop[c10,3]]

Keller

Entity["Graph",{"Keller",n}]["CyclePolynomial"]

(poly=Factor@Table[GraphData[{"Keller",n},"CyclePolynomial"]/.f_Function:>f[x],{n,k0=1,5}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

King n×n

(l=Select[Table[GraphData[{"King",{n,n}},"CyclePolynomial"][x],{n,20}],FreeQ[#,Missing|GraphData]&]//Quiet)//Column

coef=Factor/@FindPolynomialRecurrence[Drop[l,0],3]

(Subscript[c, 3])

(c3=Table[System`FindCycle[KingGraph[n],{3},All]//Length,{n,12}])//Timing

FindGeneratingFunction[c3,x]

SeriesCoefficient[-((4 (x+(x^2))x)/(((-1+x))^3)),{x,0,n}]

FindSequenceFunction[c3,n]//Factor

Table[%,{n,12}]

(Subscript[c, 4])

(c4=Table[System`FindCycle[KingGraph[n],{4},All]//Length,{n,12}])//Timing

FindGeneratingFunction[c4,x]

Series[((-3 x-20 (x^2)-(x^3))/(((-1+x))^3))x,{x,0,5}]

SeriesCoefficient[((-3 x-20 (x^2)-(x^3))/(((-1+x))^3))x,{x,0,n}]//Factor

Factor[23-34 n+12 (n^2)/.n->n+1]

Table[Piecewise[{{0,n==1}},1-10 (n-1)+12 (((n-1))^2)],{n,12}]

Table[Piecewise[{{0,n==1}},23-34 n+12 (n^2)],{n,12}]

(Subscript[c, 5])

(c5=Table[System`FindCycle[KingGraph[n],{5},All]//Length,{n,12}])//Timing

FindGeneratingFunction[c5,x]

Series[% x,{x,0,5}]

SeriesCoefficient[((52 (1+((5 x)/13)) (x^2))/(((1-x))^3))x,{x,0,n}]//Factor

Factor[4 (28-32 n+9 (n^2))]

Table[Piecewise[{{0,n<3}},4 (28-32 n+9 (n^2))],{n,12}]

Table[Piecewise[{{0,n<3}},4 (-2+n)(9n-14)],{n,12}]

(Subscript[c, 6])

(c6=Table[System`FindCycle[KingGraph[n],{6},All]//Length,{n,12}])//Timing

FindSequenceFunction[c6,n]

FindGeneratingFunction[c6,x]

Series[((2 (x^2) (-41-92 x+7 (x^2)))/(((-1+x))^3)) x,{x,0,5}]

SeriesCoefficient[((2 (x^2) (-41-92 x+7 (x^2)))/(((-1+x))^3)) x,{x,0,n}]

Factor[550-534 n+126 (n^2)]

Factor[(275-267 n+63 (n^2))/.n->n+2]

Table[Piecewise[{{0,n<3}},2(-7-15 (n-2)+63 (((n-2))^2))],{n,12}]

Table[Piecewise[{{0,n<3}},2 (275-267 n+63 (n^2))],{n,12}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["CyclePolynomial"]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["CyclePolynomial"]

(l=Select[Table[GraphData[{"Knight",{n,n}},"CyclePolynomial"][x],{n,20}],FreeQ[#,Missing|GraphData]&]//Quiet)//Column

coef=Factor/@FindPolynomialRecurrence[Drop[l,0],2]

(Subscript[c, 3])

(c3=Table[System`FindCycle[KnightGraph[n],{3},All]//Length,{n,12}])//Timing

(Subscript[c, 4])

(c4=Table[System`FindCycle[KnightGraph[n],{4},All]//Length,{n,12}])//Timing

FindGeneratingFunction[c4,x]

FindGeneratingFunction[{4,22,52,94,148,214,292,382,484},x]

Series[((2 (-2-5 x+(x^2)))/(((-1+x))^3))(x^4),{x,0,10}]

SeriesCoefficient[((2 (-2-5 x+(x^2)))/(((-1+x))^3))(x^4),{x,0,n}]

Factor[52-36 n+6 (n^2)]

(Subscript[c, 5])

(c5=Table[System`FindCycle[KnightGraph[n],{5},All]//Length,{n,12}])//Timing

(Subscript[c, 6])

(c6=Table[System`FindCycle[KnightGraph[n],{6},All]//Length,{n,12}])//Timing

FindGeneratingFunction[Drop[c6,3],x]

Series[(20+((4 x (-41+x (-31+2 x (1+x))))/(((-1+x))^3)))(x^4),{x,0,10}]

SeriesCoefficient[(20+((4 x (-41+x (-31+2 x (1+x))))/(((-1+x))^3)))(x^4),{x,0,n}]

Factor[4 (484-259 n+34 (n^2))]

(Subscript[c, 8])

(c8=Table[System`FindCycle[KnightGraph[n],{8},All]//Length,{n,12}])//Timing

FindGeneratingFunction[Drop[c8,2],x]

Series[%(x^4),{x,0,10}]

FindSequenceFunction[{32,892,5244,16680,35604,61350,93884,133206,179316},n]

Ladder

Entity["Graph",{"Ladder",n}]["CyclePolynomial"][x]

(poly=Factor@Table[GraphData[{"Ladder",n},"CyclePolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

FullSimplify[Subtract@@{-(((x^4) (1-(x^(2 n))+n (-1+(x^2))))/(((-1+(x^2)))^2)),-(((x^4) (1-(x^(2 n))+n (-1+(x^2))))/(((-1+(x^2)))^2))}]

Table[-(((x^4) (1-(x^(2 n))+n (-1+(x^2))))/(((-1+(x^2)))^2)),{n,10}]//Factor//Expand//Column

LadderRung

(poly=Factor@Table[GraphData[{"LadderRung",n},"CyclePolynomial"][x],{n,k0=1,10}])

MengerSponge

(poly=Factor@Table[GraphData[{"MengerSponge",n},"CyclePolynomial"][x],{n,k0=1,3}])//Column

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["CyclePolynomial"][x]

(poly=Factor@Table[GraphData[{"MoebiusLadder",n},"CyclePolynomial"],{n,k0=3,kmax=25}]/.f_Function:>f[x])//Column

CoefficientList[Take[poly,5],x]//Column

Position[poly,_Missing]

coef=Factor/@FindLinearRecurrence[Take[DeleteMissing[poly],19]]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

FullSimplify[Subtract@@{(x^(2 n))-(((-(-1+x) x))^n)+(((x (1+x)))^n)+((n (-(x^4)+(x^(2+2 n))))/(-1+(x^2))),(x^(2 n))-(((-(x-1) x))^n)+(((x (x+1)))^n)+((n (x^2)((x^(2n))-(x^2)))/((x^2)-1))}]

Table[(x^(2 n))-(((-(x-1) x))^n)+(((x (x+1)))^n)+((n (x^2)((x^(2n))-(x^2)))/((x^2)-1)),{n,3,10}]//Factor//Expand//Column

Take[poly,8]//Column

gf=Factor[(z^k0)FindGeneratingFunction[Take[poly,19],z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>2]

Mycielski

Entity["Graph",{"Mycielski",n}]["CyclePolynomial"]

(poly=Factor@Table[GraphData[{"Mycielski",n},"CyclePolynomial"],{n,k0=1,11}]/.f_Function:>f[x])//Column

Odd

Entity["Graph",{"Odd",n}]["CyclePolynomial"]

(poly=Factor@Table[GraphData[{"Odd",n},"CyclePolynomial"],{n,k0=1,7}]/.f_Function:>f[x])//Column

Path

Entity["Graph",{"Path",n}]["CyclePolynomial"][x]

(poly=Factor@Table[GraphData[{"Path",n},"CyclePolynomial"]/.f_Function:>f[x],{n,k0=1,20}])

PathComplement

(poly=Factor@Table[GraphData[{"PathComplement",n},"CyclePolynomial"],{n,k0=1,20}]/.f_Function:>f[x])//Column

CoefficientList[Take[poly,10],x]//Column

Do[Print[{k,FindLinearRecurrence[Drop[poly,k]]//Head//Timing}],{k,4,8}]

Do[Print[{k,FindSequenceFunction[Drop[poly,k],n-4-k]//Head//Timing}],{k,4,8}]

Do[Print[{k,FindGeneratingFunction[Drop[poly,k],z]//Head//Timing}],{k,4,8}]

PermutationStar

(poly=Factor@Table[GraphData[{"PermutationStar",n},"CyclePolynomial"],{n,k0=1,6}]/.f_Function:>f[x])//Column

Prism

Entity["Graph",{"Prism",n}]["CyclePolynomial"][x]

(poly=Table[GraphData[{"Prism",n},"CyclePolynomial"],{n,3,25}]/.f_Function:>f[x])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

FindGeneratingFunction[poly,z]

FullSimplify[RSolve[Prepend[Table[p[k+2,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

Table[((n (-(x^4)+(x^(2+2 n)))+(-1+(x^2)) ((((x-(x^2)))^n)+(((x+(x^2)))^n)))/(-1+(x^2))),{n,3,5}]//Factor//Expand

Table[((n (x^4)((x^(2 n-2))-1)+(-1+(x^2)) (x^n)((((1-x))^n)+(((1+x))^n)))/(-1+(x^2))),{n,3,20}]//Factor//Expand//Column

Subtract@@{((n (x^4)((x^(2 n-2))-1)+(-1+(x^2)) (x^n)((((1-x))^n)+(((1+x))^n)))/(-1+(x^2)))/.n->20,l[[-1]]}//Together//Expand

Subtract@@{((n (x^4)(-1+(x^(n-1))) (1+(x^(n-1)))+(-1+(x^2)) (x^n)((((1-x))^n)+(((1+x))^n)))/(-1+(x^2)))/.n->20,l[[-1]]}//Together//Expand

Queen n×n

(l=Select[Table[GraphData[{"Queen",{n,n}},"CyclePolynomial"][x],{n,20}],FreeQ[#,Missing|GraphData]&]//Quiet)//Column

coef=Factor/@FindPolynomialRecurrence[Drop[l,0],3]

(Subscript[c, 3])

(c3=Table[System`FindCycle[QueenGraph[n],{3},All]//Length,{n,12}])//Timing

FindGeneratingFunction[c3,x]

FindSequenceFunction[c3,n]//Factor

FindLinearRecurrence[c3]

Rook n×n

(poly=Table[GraphData[{"Rook",{n,n}},"CyclePolynomial"],{n,20}]/.f_Function:>f[x])//Column

CoefficientList[Take[poly,5],x]//Column

FindLinearRecurrence[DeleteMissing@Rest@poly]//Head//Timing

FindGeneratingFunction[DeleteMissing@Rest@poly,z]//Head//Timing

RookComplement n×n

(poly=Table[GraphData[{"RookComplement",{n,n}},"CyclePolynomial"],{n,20}]/.f_Function:>f[x])//Column

CoefficientList[Take[poly,5],x]//Column

FindLinearRecurrence[DeleteMissing@Rest@poly]//Head//Timing

FindGeneratingFunction[DeleteMissing@poly,z]

SierpinskiCarpet

(poly=Factor@Table[GraphData[{"SierpinskiCarpet",n},"CyclePolynomial"],{n,k0=1,4}]/.f_Function:>f[x])//Column

SierpinskiSieve

(poly=Table[GraphData[{"SierpinskiSieve",n},"CyclePolynomial"],{n,5}]/.f_Function:>f[x])//Column

seq=l[[All,2]]

FindSequenceFunction[seq,n]

SierpinskiTetrahedron

(poly=Table[GraphData[{"SierpinskiTetrahedron",n},"CyclePolynomial"],{n,6}]/.f_Function:>f[x])//Column

CoefficientList[DeleteMissing[poly],x]//Column

A292540

With[{n=3},poly/.{p_Plus:>Coefficient[p,x,n],Missing[_,l_List]:>FirstCase[l,{n,x_}:>x]}]

Table[5 4^(n-1),{n,6}]

A292542

With[{n=4},poly/.{p_Plus:>Coefficient[p,x,n],Missing[_,l_List]:>FirstCase[l,{n,x_}:>x]}]

Table[39 4^(n-2),{n,6}]

A292543

With[{n=5},poly/.{p_Plus:>Coefficient[p,x,n],Missing[_,l_List]:>FirstCase[l,{n,x_}:>x]}]

Table[6 4^n,{n,6}]

A292545

With[{n=6},poly/.{p_Plus:>Coefficient[p,x,n],Missing[_,l_List]:>FirstCase[l,{n,x_}:>x]}]

Table[219 4^(n-2),{n,6}]

With[{n=7},poly/.{p_Plus:>Coefficient[p,x,n],Missing[_,l_List]:>FirstCase[l,{n,x_}:>x]}]

Do[Print[{n,CycleCount[GraphData[{"SierpinskiTetrahedron",n}],7]//Timing}],{n,4,6}]

Do[Print[{n,CycleCount[GraphData[{"SierpinskiTetrahedron",n}],8]//Timing}],{n,4,6}]

Star

Entity["Graph",{"Star",n}]["CyclePolynomial"][x]

(poly=Factor@Table[GraphData[{"Star",n},"CyclePolynomial"][x],{n,k0=3,10}])

Sun

(poly=Table[GraphData[{"Sun",n},"CyclePolynomial"]/.f_Function:>f[x],{n,k0=3,20}])//Column

CoefficientList[Take[poly,4],x]//Column

Attempt to turn formula for counts:

Table[(2-Binomial[n+1,2]+Sum[(k-1)!(Binomial[n,k]+Sum[Sum[n (2^j)Binomial[n-j-i-1,j-1]Binomial[i+j-1,i]Binomial[n-2j-i,k-j],{i,0,n-j-k}]/j,{j,k}]),{k,n}])/2,{n,10}]

into a formula for polynomial terms:

Sum[n (2^j)Binomial[n-j-i-1,j-1]Binomial[i+j-1,i]Binomial[n-2j-i,k-j],
{i,0,n-j-k}]

Table[(2-Binomial[n+1,2]+Sum[(k-1)!(Binomial[n,k]+Sum[(2^j) n Binomial[-2 j+n,-j+k] Binomial[-1-j+n,-1+j] Hypergeometric2F1[j,j+k-n,1+j-n,1]/j,{j,k}]),{k,n}])/2,{n,10}]

Table[x^3((2-Binomial[n+1,2])+
Sum[(k-1)!(Binomial[n,k]+
Sum[
Sum[(x^(i+j+k+1))n (2^j)Binomial[n-j-i-1,j-1]Binomial[i+j-1,i]Binomial[n-2j-i,k-j],
{i,0,n-j-k}]/j,
{j,k}]),
{k,n}]),{n,3,5}]//Expand//Column

Do[Print[{k,FindLinearRecurrence[DeleteMissing@Drop[poly,k]]//Head//Timing}],{k,0,5}]

Do[Print[{k,FindSequenceFunction[DeleteMissing@Drop[poly,k],n-2]//Head//Timing}],{k,0,5}]

Do[Print[{k,FindGeneratingFunction[DeleteMissing@Drop[poly,k],z]//Head//Timing}],{k,0,5}]

coef=Factor/@FindPolynomialRecurrence[poly,7]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

With[{n=3},poly/.{p_Plus:>Coefficient[p,x,n],Missing[_,l_List]:>FirstCase[l,{n,x_}:>x]}]

FindSequenceFunction[%,n-2]//Factor

Table[(1/6) n (8-3 n+(n^2)),{n,3,20}]

Table[Binomial[n,3]+Binomial[n,2]+Binomial[n,1]+Binomial[n,0],{n,3,20}]

With[{n=4},poly/.{p_Plus:>Coefficient[p,x,n],Missing[_,l_List]:>FirstCase[l,{n,x_}:>x]}]

FindSequenceFunction[%,n-2]//Factor

With[{n=5},poly/.{p_Plus:>Coefficient[p,x,n],Missing[_,l_List]:>FirstCase[l,{n,x_}:>x]}]

FindSequenceFunction[%,n-2]//Factor

With[{n=6},poly/.{p_Plus:>Coefficient[p,x,n],Missing[_,l_List]:>FirstCase[l,{n,x_}:>x]}]

FindSequenceFunction[Rest[%],n-3]//Factor

Table[(1/12) (-3+n) n (16-7 n+(n^2)) (10-5 n+(n^2)),{n,3,20}]

Sunlet

(poly=Factor@Table[GraphData[{"Sunlet",n},"CyclePolynomial"][x],{n,k0=3,14}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Tetrahedral

(poly=Table[GraphData[{"Tetrahedral",n},"CyclePolynomial"]/.f_Function:>f[x],{n,k0=6,kmax=10}])//Column

CoefficientList[Take[poly,4],x]//Column

TorusGrid n×n

(poly=Table[GraphData[{"TorusGrid",{n,n}},"CyclePolynomial"],{n,3,20}]/.f_Function:>f[x])//Column

Transposition

Entity["Graph",{"Transposition",n}]["CyclePolynomial"]

(poly=Factor@Table[GraphData[{"Transposition",n},"CyclePolynomial"][x],{n,k0=1,4}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Triangular

(poly=Factor@Table[GraphData[{"Triangular",n},"CyclePolynomial"]/.f_Function:>f[x],{n,k0=2,10}])//Column

CoefficientList[Take[poly,6],x]//Column

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

TriangularHoneycombBishop

(poly=Table[GraphData[{"TriangularHoneycombBishop",n},"CyclePolynomial"]/.f_Function:>f[x],{n,k0=1,20}])//Column

FindGeneratingFunction[Drop[DeleteMissing@poly,4],z]//Head//Timing

TriangularHoneycombAcuteKnight

(poly=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"CyclePolynomial"]/.f_Function:>f[x],{n,k0=20}])//Column

FindGeneratingFunction[Drop[DeleteMissing@poly,4],z]//Head//Timing

TriangularHoneycombObtuseKnight

(poly=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"CyclePolynomial"]/.f_Function:>f[x],{n,k0=1,20}])//Column

FindGeneratingFunction[Drop[DeleteMissing@poly,4],z]//Head//Timing

TriangularHoneycombQueen

(poly=Table[GraphData[{"TriangularHoneycombQueen",n},"CyclePolynomial"]/.f_Function:>f[x],{n,k0=20}])//Column

FindGeneratingFunction[Drop[DeleteMissing@poly,4],z]//Head//Timing

TriangularHoneycombRook

(poly=Table[GraphData[{"TriangularHoneycombRook",n},"CyclePolynomial"]/.f_Function:>f[x],{n,k0=1,20}])//Column

FindGeneratingFunction[Drop[DeleteMissing@poly,4],z]//Head//Timing

TriangularSnake

(poly=Factor@Table[GraphData[{"TriangularSnake",n},"CyclePolynomial"]/.f_Function:>f[x],{n,k0=1,20,2}])

TriangularGrid

(poly=Table[GraphData[{"TriangularGrid",n},"CyclePolynomial"]/.f_Function:>f[x],{n,k0=1,20}])//Column

CoefficientList[Take[poly,6],x]//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

Web

(poly=Factor@Table[GraphData[{"Web",n},"CyclePolynomial"][x],{n,k0=3,15}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Wheel

Entity["Graph",{"Wheel",n}]["CyclePolynomial"][x]

(poly=Factor@Table[GraphData[{"Wheel",n},"CyclePolynomial"][x],{n,4,20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

FullSimplify[RSolve[Prepend[Table[p[k+3,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

(x^(n-1))+(n-1)Sum[x^k,{k,3,n}]

FullSimplify[Factor@Expand[(x^(n-1))+(n-1)Sum[x^k,{k,3,n}]]]

eqns=coef.Table[a[n-i],{i,4}]

Table[((-(-1+n) (x^4)+(x^n) (-1+x+(-1+n) (x^2)))/((-1+x) x)),{n,4,20}]//Factor//Expand//Column

WhiteBishop n×n

(poly=Table[GraphData[{"WhiteBishop",{n,n}},"CyclePolynomial"],{n,2,10}]/.f_Function:>f[x])//Column

Algorithms

<<MathWorld`Graphs`

Automatic

DeleteCases[
Monitor[
{gn=#,GraphData[#,"CyclePolynomial"][x],CyclePolynomial[GraphData[#],x]}&/@GraphData[;;10],
gn
],{_,x_,x_}]//Timing

"FindCycle"

DeleteCases[
Monitor[
{gn=#,GraphData[#,"CyclePolynomial"][x],CyclePolynomial[GraphData[#],x,Method->"FindCycle"]}&/@GraphData[;;10],
gn
],{_,x_,x_}]//Timing

"FindCycles"

DeleteCases[
Monitor[
{gn=#,GraphData[#,"CyclePolynomial"][x],CyclePolynomial[GraphData[#],x,Method->"FindCycles"]}&/@GraphData[;;10],
gn
],{_,x_,x_}]//Timing

"FindPath"

DeleteCases[
Monitor[
{gn=#,GraphData[#,"CyclePolynomial"][x],CyclePolynomial[GraphData[#],x,Method->"FindPath"]}&/@GraphData[;;10],
gn
],{_,x_,x_}]//Timing