Tutte Polynomial

Author

Eric W. Weisstein
March 6, 2021

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

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

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

Properties

From http://www.math.fau.edu/locke/Graphmin.htm#TuttePoly:

The number of spanning trees of a connected graph G is T(G;1,1).
The number of maximal forests of a graph G is T(G;1,1).
The number of acyclic subgraphs (forests) of a graph G is T(G;2,1).
The number of spanning edge induced subgraphs of a graph G is T(G;1,2).

T(G;2,2)= 2^|E(G)|.
T(G;0,0)=0, if G has an edge.

Spanning Trees

Select[GraphData["TuttePolynomial","Defined"],GraphData[#,"SpanningTreeCount"]=!=GraphData[#,"TuttePolynomial"][1,1]&]

EdgeCount

Select[GraphData["TuttePolynomial","Defined"],GraphData[#,"TuttePolynomial"][2,2]=!=2^GraphData[#,"E"]&]

Has an edge

Select[GraphData["TuttePolynomial","Defined"],GraphData[#,"E"]>0&&GraphData[#,"TuttePolynomial"][0,0]=!=0&]

Computation Checks

known=Sort[GraphData[#,{"V","#"}]&/@GraphData["TuttePolynomial","Defined"]];

Take[known,-10]

Select[GraphData["TuttePolynomial","Defined"],Expand[GraphData[g=#,"TuttePolynomial"][x,y]]-TuttePolynomial[GraphData[#],{x,y}]≠0&]//Timing

Monitor[If[Expand[GraphData[g=#,"TuttePolynomial"][x,y]]-TuttePolynomial[GraphData[#],{x,y}]≠0,Print[#]]&/@known[[All,2]],g];//Timing//AbsoluteTiming

Co-Tutte Graphs

Counts

From GraphData

Table[Total[DeleteCases[Tally[Sort[GraphData[#,"TuttePolynomial"][x,y]&/@GraphData[n]]],{_,1}][[All,2]]],{n,7}]

From Pre-Computation

SetDirectory["/Users/eww/Documents/Mathematica/Paclets/GraphData/Nodes/TuttePolynomial"];

FileNames["*.m"]

FileByteCount/@%/10^6.

co-Tutte

A243048

(counts=Table[Total[DeleteCases[Tally[Sort[ReadList["TuttePolynomial_"<>If[n<10,"0",""]<>ToString[n]<>".m","String"]]],{_,1}][[All,2]]],{n,9}])//Timing

(counts=Table[Total[DeleteCases[Tally[Sort[ReadList["TuttePolynomial_"<>If[n<10,"0",""]<>ToString[n]<>".m","String"]]],{_,1}][[All,2]]],{n,10}])//Timing

Tutte-unique

A243049

Table[NumberOfGraphs[n],{n,Length[counts]}]-counts

From Computation

Table[Total[DeleteCases[Tally[Sort[Expand[TuttePolynomial[#,{x,y}]]&/@Graphs[n]]],{_,1}][[All,2]]],{n,7}]//Timing

Table[Total[DeleteCases[Tally[Sort[Expand[TuttePolynomial[#,{x,y}]]&/@Graphs[n]]],{_,1}][[All,2]]],{n,8}]//Timing

Table[Total[DeleteCases[Tally[Sort[Expand[TuttePolynomial[#,{x,y}]]&/@Graphs[n]]],{_,1}][[All,2]]],{n,9}]//Timing

Table[Total[DeleteCases[Tally[Sort[Expand[TuttePolynomial[#,{x,y}]]&/@Graphs[n]]],{_,1}][[All,2]]],{n,10,10}]//Timing

Table

Grid[Table[{#[[1,1]],#[[All,2]]}&/@Select[SplitBy[Sort[{GraphData[#,"TuttePolynomial"][x,y],#}&/@GraphData[n]],First],Length[#]>1&],{n,4,5}],Dividers->All,Alignment->Left]

l=Monitor[Sort[{GetGraphData[#,"TuttePolynomial"][x,y],g=#}&/@GetGraphData[All]],g];//Timing

Length[co=Select[Split[l,First[#1]==First[#2]&],Length[#]>1&]]

ll=Sort[Function[f,{Union[GetGraphData[#,"V"]&/@f[[All,2]]],f[[1,1]],f[[All,2]]}]/@co];

TableForm[Take[Most[ll],-5],TableDepth->2]

ll[[1]]

TableForm[Take[ll,30],TableDepth->2]

Parametrized families

Andrasfai

Select[GraphData[class="Andrasfai"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

GraphData[class]

poly=Table[GraphData[{class,n},"TuttePolynomial"][x,y],{n,n0=3,20}]

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Antiprism

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

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=3,15}]

r=Factor/@FindLinearRecurrence[Take[poly,All]]

Length[r]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

LinearRecurrence[r,Take[poly,Length[r]],Length[poly]]-poly//Expand

poly[[1]]

Factor/@LinearRecurrence[r,Take[poly,Length[r]],{-2,3}]

LinearRecurrence[r,Take[poly,Length[r]],{-2,1}]

Apollonian

Barbell

Select[GraphData[class="Barbell"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

GraphData[class]

Subtract@@@Table[{
x GraphData[{"Complete",n},"TuttePolynomial"]/.f_Function:>f[x,y]^2,
GraphData[{"Barbell",n},"TuttePolynomial"]/.f_Function:>f[x,y]
},{n,3,10}]

Book

Select[GraphData[class="Book"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

GraphData[class]

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=3,20}],(_GraphData|_Missing)[_]]//Quiet

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Factor[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Centipede

Select[GraphData[class="Centipede"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

GraphData[class]

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=4,20}]

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

CocktailParty

(poly=DeleteMissing@Table[GraphData[{"CocktailParty",n},"TuttePolynomial"],{n,20}]/.f_Function:>f[x,y])//Column

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

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

Complete

Entity["Graph",{"Complete",n}]["TuttePolynomial"]

poly=Table[GraphData[{"Complete",n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,20}],_Missing[__]]

Pak

http://www.math.ucla.edu/~pak/papers/Pak_Computation_Tutte_polynomial_complete_graphs.pdf

Table[GraphData[{"Complete",n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,3}]

Sum[y^i,{i,k-1}]//FullSimplify

Gessel and Sagan

http://www.combinatorics.org/ojs/index.php/eljc/article/download/v3i2r9/pdf

F[n_,{x_,y_}]:=Sum[Binomial[n-1,k-1](x+((-y+(y^k))/(-1+y)))F[k-1,{1,y}]F[n-k,{x,y}],{k,n}]

Sum[y^Binomial[n,2](((y-1))^(-n))((u^n)/(n!)),{n,∞}]

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

Series[(1/(x-1))(((Sum[y^Binomial[n,2](((y-1))^(-n))((u^n)/(n!)),{n,6}])^((x-1)(y-1)))-1),{x,0,3},{y,0,3}]

Coboundary Polynomial

http://mathoverflow.net/questions/86066/how-many-tutte-polynomials-of-complete-graphs-are-known

ser=(Series[((Sum[t^Binomial[n,2]((x^n)/(n!)),{n,0,4}])^q),{x,0,4}]-1)/q

SeriesCoefficient[ser,{x,0,3}]

c3=Coefficient[ser,x,3]3!//Factor

http://www.math.umn.edu/~reiner/Papers/cyclotomic.pdf

Expand[Factor[(c/(((t-1))^(3-1)))/.{q->(x-1)(y-1),t->y}]]

TuttePolynomial[CompleteGraph[3],{x,y}]//Factor

c4=Coefficient[ser,x,4]4!

TuttePolynomial[CompleteGraph[4],{x,y}]//Factor

Expand[Factor[(c4/(((t-1))^(4-1)))/.{q->(x-1)(y-1),t->y}]]

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

Sum[y^Binomial[k,2]((x^k)/(k!)),{k,0,5}]

CompleteGraphTuttePolynomials[n_,{x_,y_}]:=Module[{q,ser},
ser=Series[(((Sum[y^Binomial[k,2]((x^k)/(k!)),{k,0,n}])^q)-1)/q,{x,0,n}];
Together[MapIndexed[((#2[[1]]!#)/(((y-1))^(#2[[1]]-1)))&,Rest[CoefficientList[ser,x]]/.q->(x-1)(y-1)]]
]

CompleteGraphTuttePolynomial[6,{x,y}]

Table[TuttePolynomial[CompleteGraph[n],{x,y}],{n,6}]

CompleteGraphTuttePolynomial[4,{x,y}]

CompleteGraphTuttePolynomial[5,{x,y}]

t13=CompleteGraphTuttePolynomial[13,{x,y}];//Timing

t13==GraphData["K13","TuttePolynomial"]/.f_Function:>f[x,y]

t14=CompleteGraphTuttePolynomial[14,{x,y}];//Timing

t14==GraphData["K14","TuttePolynomial"]/.f_Function:>f[x,y]

t15=CompleteGraphTuttePolynomial[15,{x,y}];//Timing

GraphData["K15","TuttePolynomial"]/.f_Function:>f[x,y]//Head

http://www.math.umn.edu/~reiner/Papers/cyclotomic.pdf

CompleteBipartite

ser=With[{max=5},Normal[(Series[((Sum[((t^(m ))^n)(((x^m)(y^n))/(m!n!)),{m,0,max},{n,0,max}])^q),{x,0,max},{y,0,max}]-1)/q]];//Timing

With[{m=2,n=2},Factor[m!n!((Coefficient[ser,x^m y^n])/(((t-1))^(m+n-1)))/.{q->(x-1)(y-1),t->y}]]

GraphData[{"CompleteBipartite",{2,2}},"TuttePolynomial"]/.f_Function:>f[x,y]

With[{m=3,n=3},Factor[m!n!((Coefficient[ser,x^m y^n])/(((t-1))^(m+n-1)))/.{q->(x-1)(y-1),t->y}]]

GraphData[{"CompleteBipartite",{3,3}},"TuttePolynomial"]/.f_Function:>f[x,y]

With[{m=2,n=4},Factor[m!n!((Coefficient[ser,x^m y^n])/(((t-1))^(m+n-1)))/.{q->(x-1)(y-1),t->y}]]

GraphData[{"CompleteBipartite",{2,4}},"TuttePolynomial"]/.f_Function:>f[x,y]

With[{m=4,n=5},Factor[Coefficient[m!n!ser,x^m y^n]]]

With[{m=4,n=5},Factor[(1/(((y-1))^(m+n-1)))Factor[Coefficient[m!n!ser,x^m y^n]/.t->y]/.q->(x-1)(y-1)]]

With[{m=5,n=5},Factor[((Coefficient[m!n!ser,x^m y^n])/(((t-1))^(m+n-1)))/.{q->(x-1)(y-1),t->y}]]

GraphData[{"CompleteBipartite",{5,5}},"TuttePolynomial"]/.f_Function:>f[x,y]

Select[GraphData["CompleteBipartite"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

Default

max=3;

sum=Sum[t^(m n) (x^m y^n)/(m! n!),{m,0,max},{n,0,max}]

ser=(Series[sum^q,{x,0,max},{y,0,max}]-1)/q

max

Factor[Expand@Factor[(max!^2SeriesCoefficient[(sum^q-1)/q,{x,0,max},{y,0,max}]/.t->y)/(y-1)^(2max-1)/.q->(x-1) (y-1)]]

With[{m=max,n=max},Factor[(Coefficient[m! n! ser,x^m y^n]/.t->y)/(y-1)^(m+n-1)/.q->(x-1) (y-1)]]

Try Normaling then powering

max=3;

sum=Sum[t^(m n) (x^m y^n)/(m! n!),{m,0,max},{n,0,max}];//Timing

ser0=(Normal[Series[sum,{x,0,max},{y,0,max}]]-1)/q;//Timing

ser1=(ser0^q-1)/q//Timing

Series[ser1,{q,0,max}]

CrossedPrism

Select[GraphData[class="CrossedPrism"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

GraphData[class]

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=4,20,2}],(_GraphData|_Missing)[_]]//Quiet

{11 x+32 (x^2)+40 (x^3)+29 (x^4)+15 (x^5)+5 (x^6)+(x^7)+11 y+46 x y+52 (x^2) y+24 (x^3) y+6 (x^4) y+25 (y^2)+39 x (y^2)+12 (x^2) (y^2)+20 (y^3)+8 x (y^3)+7 (y^4)+(y^5),85 x+321 (x^2)+570 (x^3)+652 (x^4)+547 (x^5)+358 (x^6)+189 (x^7)+81 (x^8)+28 (x^9)+7 (x^10)+(x^11)+85 y+466 x y+861 (x^2) y+868 (x^3) y+567 (x^4) y+258 (x^5) y+83 (x^6) y+18 (x^7) y+3 (x^8) y+230 (y^2)+634 x (y^2)+645 (x^2) (y^2)+342 (x^3) (y^2)+102 (x^4) (y^2)+15 (x^5) (y^2)+252 (y^3)+370 x (y^3)+187 (x^2) (y^3)+36 (x^3) (y^3)+3 (x^4) (y^3)+151 (y^4)+105 x (y^4)+18 (x^2) (y^4)+54 (y^5)+12 x (y^5)+11 (y^6)+(y^7),521 x+2401 (x^2)+5401 (x^3)+8040 (x^4)+8976 (x^5)+8052 (x^6)+6060 (x^7)+3929 (x^8)+2221 (x^9)+1091 (x^10)+459 (x^11)+161 (x^12)+45 (x^13)+9 (x^14)+(x^15)+521 y+3624 x y+9248 (x^2) y+13740 (x^3) y+14120 (x^4) y+10984 (x^5) y+6848 (x^6) y+3552 (x^7) y+1556 (x^8) y+564 (x^9) y+160 (x^10) y+32 (x^11) y+4 (x^12) y+1744 (y^2)+7044 x (y^2)+11902 (x^2) (y^2)+11966 (x^3) (y^2)+8212 (x^4) (y^2)+4184 (x^5) (y^2)+1684 (x^6) (y^2)+556 (x^7) (y^2)+142 (x^8) (y^2)+22 (x^9) (y^2)+2540 (y^3)+6668 x (y^3)+7420 (x^2) (y^3)+4716 (x^3) (y^3)+1940 (x^4) (y^3)+568 (x^5) (y^3)+136 (x^6) (y^3)+24 (x^7) (y^3)+4 (x^8) (y^3)+2159 (y^4)+3613 x (y^4)+2433 (x^2) (y^4)+833 (x^3) (y^4)+164 (x^4) (y^4)+24 (x^5) (y^4)+1186 (y^5)+1156 x (y^5)+396 (x^2) (y^5)+48 (x^3) (y^5)+4 (x^4) (y^5)+434 (y^6)+206 x (y^6)+24 (x^2) (y^6)+104 (y^7)+16 x (y^7)+15 (y^8)+(y^9),2869 x+15643 (x^2)+42273 (x^3)+76223 (x^4)+103750 (x^5)+114364 (x^6)+106959 (x^7)+87629 (x^8)+64154 (x^9)+42351 (x^10)+25218 (x^11)+13468 (x^12)+6388 (x^13)+2653 (x^14)+946 (x^15)+281 (x^16)+66 (x^17)+11 (x^18)+(x^19)+2869 y+24458 x y+79140 (x^2) y+151960 (x^3) y+205375 (x^4) y+214284 (x^5) y+183465 (x^6) y+134530 (x^7) y+86745 (x^8) y+49630 (x^9) y+25037 (x^10) y+10960 (x^11) y+4070 (x^12) y+1240 (x^13) y+295 (x^14) y+50 (x^15) y+5 (x^16) y+11684 (y^2)+62391 x (y^2)+144985 (x^2) (y^2)+207445 (x^3) (y^2)+211290 (x^4) (y^2)+167215 (x^5) (y^2)+109415 (x^6) (y^2)+61700 (x^7) (y^2)+30405 (x^8) (y^2)+12885 (x^9) (y^2)+4535 (x^10) (y^2)+1265 (x^11) (y^2)+255 (x^12) (y^2)+30 (x^13) (y^2)+21565 (y^3)+81950 x (y^3)+139840 (x^2) (y^3)+147100 (x^3) (y^3)+109635 (x^4) (y^3)+63500 (x^5) (y^3)+30655 (x^6) (y^3)+12780 (x^7) (y^3)+4500 (x^8) (y^3)+1260 (x^9) (y^3)+270 (x^10) (y^3)+40 (x^11) (y^3)+5 (x^12) (y^3)+24030 (y^4)+65655 x (y^4)+80275 (x^2) (y^4)+59275 (x^3) (y^4)+30415 (x^4) (y^4)+12080 (x^5) (y^4)+4065 (x^6) (y^4)+1145 (x^7) (y^4)+240 (x^8) (y^4)+35 (x^9) (y^4)+17967 (y^5)+34226 x (y^5)+28356 (x^2) (y^5)+13456 (x^3) (y^5)+4241 (x^4) (y^5)+1040 (x^5) (y^5)+220 (x^6) (y^5)+30 (x^7) (y^5)+5 (x^8) (y^5)+9439 (y^6)+11785 x (y^6)+5995 (x^2) (y^6)+1535 (x^3) (y^6)+240 (x^4) (y^6)+35 (x^5) (y^6)+3540 (y^7)+2610 x (y^7)+680 (x^2) (y^7)+60 (x^3) (y^7)+5 (x^4) (y^7)+940 (y^8)+340 x (y^8)+30 (x^2) (y^8)+170 (y^9)+20 x (y^9)+19 (y^10)+(y^11),15017 x+94749 (x^2)+298029 (x^3)+626561 (x^4)+994793 (x^5)+1279472 (x^6)+1398080 (x^7)+1343678 (x^8)+1164130 (x^9)+923117 (x^10)+674573 (x^11)+454514 (x^12)+281418 (x^13)+159243 (x^14)+81789 (x^15)+37809 (x^16)+15561 (x^17)+5618 (x^18)+1742 (x^19)+449 (x^20)+91 (x^21)+13 (x^22)+(x^23)+15017 y+152348 x y+594996 (x^2) y+1386944 (x^3) y+2285328 (x^4) y+2918682 (x^5) y+3071472 (x^6) y+2785272 (x^7) y+2246904 (x^8) y+1642870 (x^9) y+1095432 (x^10) y+664092 (x^11) y+363172 (x^12) y+177354 (x^13) y+76422 (x^14) y+28620 (x^15) y+9120 (x^16) y+2394 (x^17) y+492 (x^18) y+72 (x^19) y+6 (x^20) y+72616 (y^2)+482090 x (y^2)+1414266 (x^2) (y^2)+2582730 (x^3) (y^2)+3395475 (x^4) (y^2)+3503535 (x^5) (y^2)+3016704 (x^6) (y^2)+2266398 (x^7) (y^2)+1525377 (x^8) (y^2)+926271 (x^9) (y^2)+503784 (x^10) (y^2)+242004 (x^11) (y^2)+100995 (x^12) (y^2)+35895 (x^13) (y^2)+10566 (x^14) (y^2)+2460 (x^15) (y^2)+411 (x^16) (y^2)+39 (x^17) (y^2)+162990 (y^3)+810160 x (y^3)+1847212 (x^2) (y^3)+2655060 (x^3) (y^3)+2766198 (x^4) (y^3)+2282148 (x^5) (y^3)+1591114 (x^6) (y^3)+977980 (x^7) (y^3)+537112 (x^8) (y^3)+260612 (x^9) (y^3)+109304 (x^10) (y^3)+38720 (x^11) (y^3)+11294 (x^12) (y^3)+2624 (x^13) (y^3)+470 (x^14) (y^3)+60 (x^15) (y^3)+6 (x^16) (y^3)+225580 (y^4)+859695 x (y^4)+1518132 (x^2) (y^4)+1690404 (x^3) (y^4)+1365801 (x^4) (y^4)+880983 (x^5) (y^4)+486600 (x^6) (y^4)+237828 (x^7) (y^4)+101718 (x^8) (y^4)+36780 (x^9) (y^4)+10863 (x^10) (y^4)+2523 (x^11) (y^4)+426 (x^12) (y^4)+48 (x^13) (y^4)+214539 (y^5)+621522 x (y^5)+831372 (x^2) (y^5)+694176 (x^3) (y^5)+418626 (x^4) (y^5)+203130 (x^5) (y^5)+85548 (x^6) (y^5)+31512 (x^7) (y^5)+9642 (x^8) (y^5)+2310 (x^9) (y^5)+420 (x^10) (y^5)+48 (x^11) (y^5)+6 (x^12) (y^5)+147731 (y^6)+316699 x (y^6)+308458 (x^2) (y^6)+182854 (x^3) (y^6)+77145 (x^4) (y^6)+26433 (x^5) (y^6)+7992 (x^6) (y^6)+1998 (x^7) (y^6)+363 (x^8) (y^6)+51 (x^9) (y^6)+75578 (y^7)+114660 x (y^7)+76356 (x^2) (y^7)+29252 (x^3) (y^7)+7698 (x^4) (y^7)+1704 (x^5) (y^7)+330 (x^6) (y^7)+36 (x^7) (y^7)+6 (x^8) (y^7)+28989 (y^8)+29064 x (y^8)+11943 (x^2) (y^8)+2463 (x^3) (y^8)+330 (x^4) (y^8)+48 (x^5) (y^8)+8295 (y^9)+4934 x (y^9)+1040 (x^2) (y^9)+72 (x^3) (y^9)+6 (x^4) (y^9)+1733 (y^10)+507 x (y^10)+36 (x^2) (y^10)+252 (y^11)+24 x (y^11)+23 (y^12)+(y^13),76717 x+550511 (x^2)+1972925 (x^3)+4723001 (x^4)+8524337 (x^5)+12432815 (x^6)+15363978 (x^7)+16669104 (x^8)+16316801 (x^9)+14695125 (x^10)+12322783 (x^11)+9671099 (x^12)+7105046 (x^13)+4873506 (x^14)+3108808 (x^15)+1835984 (x^16)+998861 (x^17)+497766 (x^18)+225655 (x^19)+92256 (x^20)+33629 (x^21)+10760 (x^22)+2955 (x^23)+673 (x^24)+120 (x^25)+15 (x^26)+(x^27)+76717 y+904734 x y+4131400 (x^2) y+11275040 (x^3) y+21753536 (x^4) y+32500048 (x^5) y+39929757 (x^6) y+42190264 (x^7) y+39680109 (x^8) y+34038942 (x^9) y+27003690 (x^10) y+19897682 (x^11) y+13590129 (x^12) y+8559698 (x^13) y+4941246 (x^14) y+2597168 (x^15) y+1233813 (x^16) y+525056 (x^17) y+197869 (x^18) y+65016 (x^19) y+18221 (x^20) y+4214 (x^21) y+763 (x^22) y+98 (x^23) y+7 (x^24) y+430940 (y^2)+3418269 x (y^2)+12061847 (x^2) (y^2)+26590991 (x^3) (y^2)+42301609 (x^4) (y^2)+52835818 (x^5) (y^2)+54994303 (x^6) (y^2)+49922558 (x^7) (y^2)+40834892 (x^8) (y^2)+30643704 (x^9) (y^2)+21188678 (x^10) (y^2)+13438019 (x^11) (y^2)+7753732 (x^12) (y^2)+4034821 (x^13) (y^2)+1876350 (x^14) (y^2)+771512 (x^15) (y^2)+276563 (x^16) (y^2)+84728 (x^17) (y^2)+21525 (x^18) (y^2)+4312 (x^19) (y^2)+616 (x^20) (y^2)+49 (x^21) (y^2)+1140223 (y^3)+6992174 x (y^3)+19851244 (x^2) (y^3)+35796208 (x^3) (y^3)+47051823 (x^4) (y^3)+49072884 (x^5) (y^3)+43226561 (x^6) (y^3)+33675824 (x^7) (y^3)+23831444 (x^8) (y^3)+15419964 (x^9) (y^3)+9058007 (x^10) (y^3)+4773692 (x^11) (y^3)+2230543 (x^12) (y^3)+913360 (x^13) (y^3)+323358 (x^14) (y^3)+97216 (x^15) (y^3)+24227 (x^16) (y^3)+4844 (x^17) (y^3)+749 (x^18) (y^3)+84 (x^19) (y^3)+7 (x^20) (y^3)+1886528 (y^4)+9226763 x (y^4)+21204617 (x^2) (y^4)+31151624 (x^3) (y^4)+33566379 (x^4) (y^4)+29001315 (x^5) (y^4)+21476434 (x^6) (y^4)+14233338 (x^7) (y^4)+8563079 (x^8) (y^4)+4636275 (x^9) (y^4)+2220890 (x^10) (y^4)+925995 (x^11) (y^4)+331002 (x^12) (y^4)+99645 (x^13) (y^4)+24626 (x^14) (y^4)+4809 (x^15) (y^4)+686 (x^16) (y^4)+63 (x^17) (y^4)+2179933 (y^5)+8520512 x (y^5)+15717331 (x^2) (y^5)+18549552 (x^3) (y^5)+16125886 (x^4) (y^5)+11373110 (x^5) (y^5)+6980736 (x^6) (y^5)+3856258 (x^7) (y^5)+1907164 (x^8) (y^5)+824250 (x^9) (y^5)+303947 (x^10) (y^5)+93702 (x^11) (y^5)+23583 (x^12) (y^5)+4676 (x^13) (y^5)+707 (x^14) (y^5)+70 (x^15) (y^5)+7 (x^16) (y^5)+1860194 (y^6)+5741904 x (y^6)+8344455 (x^2) (y^6)+7725648 (x^3) (y^6)+5281997 (x^4) (y^6)+2967895 (x^5) (y^6)+1471743 (x^6) (y^6)+653170 (x^7) (y^6)+251622 (x^8) (y^6)+80934 (x^9) (y^6)+21119 (x^10) (y^6)+4319 (x^11) (y^6)+637 (x^12) (y^6)+70 (x^13) (y^6)+1208596 (y^7)+2880928 x (y^7)+3203355 (x^2) (y^7)+2242836 (x^3) (y^7)+1158494 (x^4) (y^7)+498632 (x^5) (y^7)+191549 (x^6) (y^7)+64316 (x^7) (y^7)+17668 (x^8) (y^7)+3780 (x^9) (y^7)+616 (x^10) (y^7)+56 (x^11) (y^7)+7 (x^12) (y^7)+607471 (y^8)+1081325 x (y^8)+880922 (x^2) (y^8)+440363 (x^3) (y^8)+160916 (x^4) (y^8)+49868 (x^5) (y^8)+13937 (x^6) (y^8)+3164 (x^7) (y^8)+511 (x^8) (y^8)+70 (x^9) (y^8)+237524 (y^9)+300846 x (y^9)+168217 (x^2) (y^9)+54488 (x^3) (y^9)+12558 (x^4) (y^9)+2590 (x^5) (y^9)+469 (x^6) (y^9)+42 (x^7) (y^9)+7 (x^8) (y^9)+71995 (y^10)+60459 x (y^10)+20902 (x^2) (y^10)+3633 (x^3) (y^10)+434 (x^4) (y^10)+63 (x^5) (y^10)+16688 (y^11)+8330 x (y^11)+1477 (x^2) (y^11)+84 (x^3) (y^11)+7 (x^4) (y^11)+2877 (y^12)+707 x (y^12)+42 (x^2) (y^12)+350 (y^13)+28 x (y^13)+27 (y^14)+(y^15),387425 x+3118097 (x^2)+12534897 (x^3)+33618449 (x^4)+67833185 (x^5)+110261361 (x^6)+151245825 (x^7)+181353472 (x^8)+195524224 (x^9)+193805560 (x^10)+179462872 (x^11)+156742180 (x^12)+129626868 (x^13)+101494500 (x^14)+75057932 (x^15)+52254977 (x^16)+34126993 (x^17)+20832349 (x^18)+11841565 (x^19)+6241851 (x^20)+3036563 (x^21)+1355611 (x^22)+551435 (x^23)+202545 (x^24)+66377 (x^25)+19093 (x^26)+4709 (x^27)+961 (x^28)+153 (x^29)+17 (x^30)+(x^31)+387425 y+5213392 x y+27224976 (x^2) y+84954624 (x^3) y+187203824 (x^4) y+318712832 (x^5) y+444549136 (x^6) y+530676920 (x^7) y+561365952 (x^8) y+540838288 (x^9) y+483805520 (x^10) y+406140304 (x^11) y+320959344 (x^12) y+238362096 (x^13) y+165694168 (x^14) y+107317472 (x^15) y+64465760 (x^16) y+35747736 (x^17) y+18206112 (x^18) y+8465864 (x^19) y+3568520 (x^20) y+1351200 (x^21) y+454160 (x^22) y+133344 (x^23) y+33432 (x^24) y+6920 (x^25) y+1120 (x^26) y+128 (x^27) y+8 (x^28) y+2482720 (y^2)+22891320 x (y^2)+94198904 (x^2) (y^2)+242431800 (x^3) (y^2)+450068552 (x^4) (y^2)+654453256 (x^5) (y^2)+789355804 (x^6) (y^2)+825703388 (x^7) (y^2)+775886008 (x^8) (y^2)+671327488 (x^9) (y^2)+541877408 (x^10) (y^2)+409193176 (x^11) (y^2)+288090952 (x^12) (y^2)+188018864 (x^13) (y^2)+113070440 (x^14) (y^2)+62297856 (x^15) (y^2)+31259612 (x^16) (y^2)+14187724 (x^17) (y^2)+5775636 (x^18) (y^2)+2085892 (x^19) (y^2)+658480 (x^20) (y^2)+177912 (x^21) (y^2)+39848 (x^22) (y^2)+7016 (x^23) (y^2)+876 (x^24) (y^2)+60 (x^25) (y^2)+7565864 (y^3)+55129248 x (y^3)+186825392 (x^2) (y^3)+403171104 (x^3) (y^3)+634499840 (x^4) (y^3)+790095400 (x^5) (y^3)+826100360 (x^6) (y^3)+759845384 (x^7) (y^3)+635858088 (x^8) (y^3)+492935808 (x^9) (y^3)+355298072 (x^10) (y^3)+236881728 (x^11) (y^3)+144933768 (x^12) (y^3)+80761344 (x^13) (y^3)+40700744 (x^14) (y^3)+18417232 (x^15) (y^3)+7419448 (x^16) (y^3)+2632648 (x^17) (y^3)+811400 (x^18) (y^3)+213224 (x^19) (y^3)+46616 (x^20) (y^3)+8208 (x^21) (y^3)+1120 (x^22) (y^3)+112 (x^23) (y^3)+8 (x^24) (y^3)+14559104 (y^4)+86880060 x (y^4)+245196860 (x^2) (y^4)+444444348 (x^3) (y^4)+591775158 (x^4) (y^4)+629648166 (x^5) (y^4)+570350526 (x^6) (y^4)+461225854 (x^7) (y^4)+342355148 (x^8) (y^4)+234901564 (x^9) (y^4)+148003264 (x^10) (y^4)+84713456 (x^11) (y^4)+43616180 (x^12) (y^4)+20028804 (x^13) (y^4)+8131756 (x^14) (y^4)+2888276 (x^15) (y^4)+885190 (x^16) (y^4)+229758 (x^17) (y^4)+49158 (x^18) (y^4)+8326 (x^19) (y^4)+1032 (x^20) (y^4)+80 (x^21) (y^4)+19791548 (y^5)+97483664 x (y^5)+228747504 (x^2) (y^5)+346183624 (x^3) (y^5)+387197192 (x^4) (y^5)+349979592 (x^5) (y^5)+273558248 (x^6) (y^5)+193373544 (x^7) (y^5)+125628048 (x^8) (y^5)+74524472 (x^9) (y^5)+39779712 (x^10) (y^5)+18852272 (x^11) (y^5)+7847296 (x^12) (y^5)+2838640 (x^13) (y^5)+880664 (x^14) (y^5)+230224 (x^15) (y^5)+49504 (x^16) (y^5)+8440 (x^17) (y^5)+1096 (x^18) (y^5)+96 (x^19) (y^5)+8 (x^20) (y^5)+20142640 (y^6)+81550280 x (y^6)+157650524 (x^2) (y^6)+196858252 (x^3) (y^6)+182759100 (x^4) (y^6)+138952100 (x^5) (y^6)+92875780 (x^6) (y^6)+56569284 (x^7) (y^6)+31371084 (x^8) (y^6)+15537764 (x^9) (y^6)+6741984 (x^10) (y^6)+2525624 (x^11) (y^6)+805928 (x^12) (y^6)+215352 (x^13) (y^6)+47032 (x^14) (y^6)+8112 (x^15) (y^6)+1020 (x^16) (y^6)+92 (x^17) (y^6)+15869512 (y^7)+52191864 x (y^7)+81845368 (x^2) (y^7)+82824216 (x^3) (y^7)+62696464 (x^4) (y^7)+39468488 (x^5) (y^7)+22176920 (x^6) (y^7)+11337000 (x^7) (y^7)+5164112 (x^8) (y^7)+2035792 (x^9) (y^7)+679544 (x^10) (y^7)+188672 (x^11) (y^7)+42560 (x^12) (y^7)+7520 (x^13) (y^7)+1016 (x^14) (y^7)+80 (x^15) (y^7)+8 (x^16) (y^7)+9870431 (y^8)+25885461 x (y^8)+32198437 (x^2) (y^8)+25728229 (x^3) (y^8)+15465369 (x^4) (y^8)+7861009 (x^5) (y^8)+3606937 (x^6) (y^8)+1484553 (x^7) (y^8)+525444 (x^8) (y^8)+153988 (x^9) (y^8)+36488 (x^10) (y^8)+6760 (x^11) (y^8)+888 (x^12) (y^8)+96 (x^13) (y^8)+4897822 (y^9)+9979160 x (y^9)+9540792 (x^2) (y^9)+5794200 (x^3) (y^9)+2655456 (x^4) (y^9)+1047096 (x^5) (y^9)+375016 (x^6) (y^9)+116736 (x^7) (y^9)+29360 (x^8) (y^9)+5736 (x^9) (y^9)+864 (x^10) (y^9)+64 (x^11) (y^9)+8 (x^12) (y^9)+1945892 (y^10)+2971996 x (y^10)+2088228 (x^2) (y^10)+908772 (x^3) (y^10)+297204 (x^4) (y^10)+85484 (x^5) (y^10)+22424 (x^6) (y^10)+4696 (x^7) (y^10)+684 (x^8) (y^10)+92 (x^9) (y^10)+617344 (y^11)+672520 x (y^11)+324952 (x^2) (y^11)+91784 (x^3) (y^11)+19088 (x^4) (y^11)+3728 (x^5) (y^11)+640 (x^6) (y^11)+48 (x^7) (y^11)+8 (x^8) (y^11)+154938 (y^12)+112070 x (y^12)+33510 (x^2) (y^12)+5062 (x^3) (y^12)+552 (x^4) (y^12)+80 (x^5) (y^12)+30212 (y^13)+13000 x (y^13)+1992 (x^2) (y^13)+96 (x^3) (y^13)+8 (x^4) (y^13)+4436 (y^14)+940 x (y^14)+48 (x^2) (y^14)+464 (y^15)+32 x (y^15)+31 (y^16)+(y^17),Missing["NotAvailable"][x,y],Missing["NotAvailable"]/.f_Function:>f[x,y]}

r=Factor/@FindLinearRecurrence[poly]

FindLinearRecurrence[{11 x+32 (x^2)+40 (x^3)+29 (x^4)+15 (x^5)+5 (x^6)+(x^7)+11 y+46 x y+52 (x^2) y+24 (x^3) y+6 (x^4) y+25 (y^2)+39 x (y^2)+12 (x^2) (y^2)+20 (y^3)+8 x (y^3)+7 (y^4)+(y^5),85 x+321 (x^2)+570 (x^3)+652 (x^4)+547 (x^5)+358 (x^6)+189 (x^7)+81 (x^8)+28 (x^9)+7 (x^10)+(x^11)+85 y+466 x y+861 (x^2) y+868 (x^3) y+567 (x^4) y+258 (x^5) y+83 (x^6) y+18 (x^7) y+3 (x^8) y+230 (y^2)+634 x (y^2)+645 (x^2) (y^2)+342 (x^3) (y^2)+102 (x^4) (y^2)+15 (x^5) (y^2)+252 (y^3)+370 x (y^3)+187 (x^2) (y^3)+36 (x^3) (y^3)+3 (x^4) (y^3)+151 (y^4)+105 x (y^4)+18 (x^2) (y^4)+54 (y^5)+12 x (y^5)+11 (y^6)+(y^7),521 x+2401 (x^2)+5401 (x^3)+8040 (x^4)+8976 (x^5)+8052 (x^6)+6060 (x^7)+3929 (x^8)+2221 (x^9)+1091 (x^10)+459 (x^11)+161 (x^12)+45 (x^13)+9 (x^14)+(x^15)+521 y+3624 x y+9248 (x^2) y+13740 (x^3) y+14120 (x^4) y+10984 (x^5) y+6848 (x^6) y+3552 (x^7) y+1556 (x^8) y+564 (x^9) y+160 (x^10) y+32 (x^11) y+4 (x^12) y+1744 (y^2)+7044 x (y^2)+11902 (x^2) (y^2)+11966 (x^3) (y^2)+8212 (x^4) (y^2)+4184 (x^5) (y^2)+1684 (x^6) (y^2)+556 (x^7) (y^2)+142 (x^8) (y^2)+22 (x^9) (y^2)+2540 (y^3)+6668 x (y^3)+7420 (x^2) (y^3)+4716 (x^3) (y^3)+1940 (x^4) (y^3)+568 (x^5) (y^3)+136 (x^6) (y^3)+24 (x^7) (y^3)+4 (x^8) (y^3)+2159 (y^4)+3613 x (y^4)+2433 (x^2) (y^4)+833 (x^3) (y^4)+164 (x^4) (y^4)+24 (x^5) (y^4)+1186 (y^5)+1156 x (y^5)+396 (x^2) (y^5)+48 (x^3) (y^5)+4 (x^4) (y^5)+434 (y^6)+206 x (y^6)+24 (x^2) (y^6)+104 (y^7)+16 x (y^7)+15 (y^8)+(y^9),2869 x+15643 (x^2)+42273 (x^3)+76223 (x^4)+103750 (x^5)+114364 (x^6)+106959 (x^7)+87629 (x^8)+64154 (x^9)+42351 (x^10)+25218 (x^11)+13468 (x^12)+6388 (x^13)+2653 (x^14)+946 (x^15)+281 (x^16)+66 (x^17)+11 (x^18)+(x^19)+2869 y+24458 x y+79140 (x^2) y+151960 (x^3) y+205375 (x^4) y+214284 (x^5) y+183465 (x^6) y+134530 (x^7) y+86745 (x^8) y+49630 (x^9) y+25037 (x^10) y+10960 (x^11) y+4070 (x^12) y+1240 (x^13) y+295 (x^14) y+50 (x^15) y+5 (x^16) y+11684 (y^2)+62391 x (y^2)+144985 (x^2) (y^2)+207445 (x^3) (y^2)+211290 (x^4) (y^2)+167215 (x^5) (y^2)+109415 (x^6) (y^2)+61700 (x^7) (y^2)+30405 (x^8) (y^2)+12885 (x^9) (y^2)+4535 (x^10) (y^2)+1265 (x^11) (y^2)+255 (x^12) (y^2)+30 (x^13) (y^2)+21565 (y^3)+81950 x (y^3)+139840 (x^2) (y^3)+147100 (x^3) (y^3)+109635 (x^4) (y^3)+63500 (x^5) (y^3)+30655 (x^6) (y^3)+12780 (x^7) (y^3)+4500 (x^8) (y^3)+1260 (x^9) (y^3)+270 (x^10) (y^3)+40 (x^11) (y^3)+5 (x^12) (y^3)+24030 (y^4)+65655 x (y^4)+80275 (x^2) (y^4)+59275 (x^3) (y^4)+30415 (x^4) (y^4)+12080 (x^5) (y^4)+4065 (x^6) (y^4)+1145 (x^7) (y^4)+240 (x^8) (y^4)+35 (x^9) (y^4)+17967 (y^5)+34226 x (y^5)+28356 (x^2) (y^5)+13456 (x^3) (y^5)+4241 (x^4) (y^5)+1040 (x^5) (y^5)+220 (x^6) (y^5)+30 (x^7) (y^5)+5 (x^8) (y^5)+9439 (y^6)+11785 x (y^6)+5995 (x^2) (y^6)+1535 (x^3) (y^6)+240 (x^4) (y^6)+35 (x^5) (y^6)+3540 (y^7)+2610 x (y^7)+680 (x^2) (y^7)+60 (x^3) (y^7)+5 (x^4) (y^7)+940 (y^8)+340 x (y^8)+30 (x^2) (y^8)+170 (y^9)+20 x (y^9)+19 (y^10)+(y^11),15017 x+94749 (x^2)+298029 (x^3)+626561 (x^4)+994793 (x^5)+1279472 (x^6)+1398080 (x^7)+1343678 (x^8)+1164130 (x^9)+923117 (x^10)+674573 (x^11)+454514 (x^12)+281418 (x^13)+159243 (x^14)+81789 (x^15)+37809 (x^16)+15561 (x^17)+5618 (x^18)+1742 (x^19)+449 (x^20)+91 (x^21)+13 (x^22)+(x^23)+15017 y+152348 x y+594996 (x^2) y+1386944 (x^3) y+2285328 (x^4) y+2918682 (x^5) y+3071472 (x^6) y+2785272 (x^7) y+2246904 (x^8) y+1642870 (x^9) y+1095432 (x^10) y+664092 (x^11) y+363172 (x^12) y+177354 (x^13) y+76422 (x^14) y+28620 (x^15) y+9120 (x^16) y+2394 (x^17) y+492 (x^18) y+72 (x^19) y+6 (x^20) y+72616 (y^2)+482090 x (y^2)+1414266 (x^2) (y^2)+2582730 (x^3) (y^2)+3395475 (x^4) (y^2)+3503535 (x^5) (y^2)+3016704 (x^6) (y^2)+2266398 (x^7) (y^2)+1525377 (x^8) (y^2)+926271 (x^9) (y^2)+503784 (x^10) (y^2)+242004 (x^11) (y^2)+100995 (x^12) (y^2)+35895 (x^13) (y^2)+10566 (x^14) (y^2)+2460 (x^15) (y^2)+411 (x^16) (y^2)+39 (x^17) (y^2)+162990 (y^3)+810160 x (y^3)+1847212 (x^2) (y^3)+2655060 (x^3) (y^3)+2766198 (x^4) (y^3)+2282148 (x^5) (y^3)+1591114 (x^6) (y^3)+977980 (x^7) (y^3)+537112 (x^8) (y^3)+260612 (x^9) (y^3)+109304 (x^10) (y^3)+38720 (x^11) (y^3)+11294 (x^12) (y^3)+2624 (x^13) (y^3)+470 (x^14) (y^3)+60 (x^15) (y^3)+6 (x^16) (y^3)+225580 (y^4)+859695 x (y^4)+1518132 (x^2) (y^4)+1690404 (x^3) (y^4)+1365801 (x^4) (y^4)+880983 (x^5) (y^4)+486600 (x^6) (y^4)+237828 (x^7) (y^4)+101718 (x^8) (y^4)+36780 (x^9) (y^4)+10863 (x^10) (y^4)+2523 (x^11) (y^4)+426 (x^12) (y^4)+48 (x^13) (y^4)+214539 (y^5)+621522 x (y^5)+831372 (x^2) (y^5)+694176 (x^3) (y^5)+418626 (x^4) (y^5)+203130 (x^5) (y^5)+85548 (x^6) (y^5)+31512 (x^7) (y^5)+9642 (x^8) (y^5)+2310 (x^9) (y^5)+420 (x^10) (y^5)+48 (x^11) (y^5)+6 (x^12) (y^5)+147731 (y^6)+316699 x (y^6)+308458 (x^2) (y^6)+182854 (x^3) (y^6)+77145 (x^4) (y^6)+26433 (x^5) (y^6)+7992 (x^6) (y^6)+1998 (x^7) (y^6)+363 (x^8) (y^6)+51 (x^9) (y^6)+75578 (y^7)+114660 x (y^7)+76356 (x^2) (y^7)+29252 (x^3) (y^7)+7698 (x^4) (y^7)+1704 (x^5) (y^7)+330 (x^6) (y^7)+36 (x^7) (y^7)+6 (x^8) (y^7)+28989 (y^8)+29064 x (y^8)+11943 (x^2) (y^8)+2463 (x^3) (y^8)+330 (x^4) (y^8)+48 (x^5) (y^8)+8295 (y^9)+4934 x (y^9)+1040 (x^2) (y^9)+72 (x^3) (y^9)+6 (x^4) (y^9)+1733 (y^10)+507 x (y^10)+36 (x^2) (y^10)+252 (y^11)+24 x (y^11)+23 (y^12)+(y^13),76717 x+550511 (x^2)+1972925 (x^3)+4723001 (x^4)+8524337 (x^5)+12432815 (x^6)+15363978 (x^7)+16669104 (x^8)+16316801 (x^9)+14695125 (x^10)+12322783 (x^11)+9671099 (x^12)+7105046 (x^13)+4873506 (x^14)+3108808 (x^15)+1835984 (x^16)+998861 (x^17)+497766 (x^18)+225655 (x^19)+92256 (x^20)+33629 (x^21)+10760 (x^22)+2955 (x^23)+673 (x^24)+120 (x^25)+15 (x^26)+(x^27)+76717 y+904734 x y+4131400 (x^2) y+11275040 (x^3) y+21753536 (x^4) y+32500048 (x^5) y+39929757 (x^6) y+42190264 (x^7) y+39680109 (x^8) y+34038942 (x^9) y+27003690 (x^10) y+19897682 (x^11) y+13590129 (x^12) y+8559698 (x^13) y+4941246 (x^14) y+2597168 (x^15) y+1233813 (x^16) y+525056 (x^17) y+197869 (x^18) y+65016 (x^19) y+18221 (x^20) y+4214 (x^21) y+763 (x^22) y+98 (x^23) y+7 (x^24) y+430940 (y^2)+3418269 x (y^2)+12061847 (x^2) (y^2)+26590991 (x^3) (y^2)+42301609 (x^4) (y^2)+52835818 (x^5) (y^2)+54994303 (x^6) (y^2)+49922558 (x^7) (y^2)+40834892 (x^8) (y^2)+30643704 (x^9) (y^2)+21188678 (x^10) (y^2)+13438019 (x^11) (y^2)+7753732 (x^12) (y^2)+4034821 (x^13) (y^2)+1876350 (x^14) (y^2)+771512 (x^15) (y^2)+276563 (x^16) (y^2)+84728 (x^17) (y^2)+21525 (x^18) (y^2)+4312 (x^19) (y^2)+616 (x^20) (y^2)+49 (x^21) (y^2)+1140223 (y^3)+6992174 x (y^3)+19851244 (x^2) (y^3)+35796208 (x^3) (y^3)+47051823 (x^4) (y^3)+49072884 (x^5) (y^3)+43226561 (x^6) (y^3)+33675824 (x^7) (y^3)+23831444 (x^8) (y^3)+15419964 (x^9) (y^3)+9058007 (x^10) (y^3)+4773692 (x^11) (y^3)+2230543 (x^12) (y^3)+913360 (x^13) (y^3)+323358 (x^14) (y^3)+97216 (x^15) (y^3)+24227 (x^16) (y^3)+4844 (x^17) (y^3)+749 (x^18) (y^3)+84 (x^19) (y^3)+7 (x^20) (y^3)+1886528 (y^4)+9226763 x (y^4)+21204617 (x^2) (y^4)+31151624 (x^3) (y^4)+33566379 (x^4) (y^4)+29001315 (x^5) (y^4)+21476434 (x^6) (y^4)+14233338 (x^7) (y^4)+8563079 (x^8) (y^4)+4636275 (x^9) (y^4)+2220890 (x^10) (y^4)+925995 (x^11) (y^4)+331002 (x^12) (y^4)+99645 (x^13) (y^4)+24626 (x^14) (y^4)+4809 (x^15) (y^4)+686 (x^16) (y^4)+63 (x^17) (y^4)+2179933 (y^5)+8520512 x (y^5)+15717331 (x^2) (y^5)+18549552 (x^3) (y^5)+16125886 (x^4) (y^5)+11373110 (x^5) (y^5)+6980736 (x^6) (y^5)+3856258 (x^7) (y^5)+1907164 (x^8) (y^5)+824250 (x^9) (y^5)+303947 (x^10) (y^5)+93702 (x^11) (y^5)+23583 (x^12) (y^5)+4676 (x^13) (y^5)+707 (x^14) (y^5)+70 (x^15) (y^5)+7 (x^16) (y^5)+1860194 (y^6)+5741904 x (y^6)+8344455 (x^2) (y^6)+7725648 (x^3) (y^6)+5281997 (x^4) (y^6)+2967895 (x^5) (y^6)+1471743 (x^6) (y^6)+653170 (x^7) (y^6)+251622 (x^8) (y^6)+80934 (x^9) (y^6)+21119 (x^10) (y^6)+4319 (x^11) (y^6)+637 (x^12) (y^6)+70 (x^13) (y^6)+1208596 (y^7)+2880928 x (y^7)+3203355 (x^2) (y^7)+2242836 (x^3) (y^7)+1158494 (x^4) (y^7)+498632 (x^5) (y^7)+191549 (x^6) (y^7)+64316 (x^7) (y^7)+17668 (x^8) (y^7)+3780 (x^9) (y^7)+616 (x^10) (y^7)+56 (x^11) (y^7)+7 (x^12) (y^7)+607471 (y^8)+1081325 x (y^8)+880922 (x^2) (y^8)+440363 (x^3) (y^8)+160916 (x^4) (y^8)+49868 (x^5) (y^8)+13937 (x^6) (y^8)+3164 (x^7) (y^8)+511 (x^8) (y^8)+70 (x^9) (y^8)+237524 (y^9)+300846 x (y^9)+168217 (x^2) (y^9)+54488 (x^3) (y^9)+12558 (x^4) (y^9)+2590 (x^5) (y^9)+469 (x^6) (y^9)+42 (x^7) (y^9)+7 (x^8) (y^9)+71995 (y^10)+60459 x (y^10)+20902 (x^2) (y^10)+3633 (x^3) (y^10)+434 (x^4) (y^10)+63 (x^5) (y^10)+16688 (y^11)+8330 x (y^11)+1477 (x^2) (y^11)+84 (x^3) (y^11)+7 (x^4) (y^11)+2877 (y^12)+707 x (y^12)+42 (x^2) (y^12)+350 (y^13)+28 x (y^13)+27 (y^14)+(y^15),387425 x+3118097 (x^2)+12534897 (x^3)+33618449 (x^4)+67833185 (x^5)+110261361 (x^6)+151245825 (x^7)+181353472 (x^8)+195524224 (x^9)+193805560 (x^10)+179462872 (x^11)+156742180 (x^12)+129626868 (x^13)+101494500 (x^14)+75057932 (x^15)+52254977 (x^16)+34126993 (x^17)+20832349 (x^18)+11841565 (x^19)+6241851 (x^20)+3036563 (x^21)+1355611 (x^22)+551435 (x^23)+202545 (x^24)+66377 (x^25)+19093 (x^26)+4709 (x^27)+961 (x^28)+153 (x^29)+17 (x^30)+(x^31)+387425 y+5213392 x y+27224976 (x^2) y+84954624 (x^3) y+187203824 (x^4) y+318712832 (x^5) y+444549136 (x^6) y+530676920 (x^7) y+561365952 (x^8) y+540838288 (x^9) y+483805520 (x^10) y+406140304 (x^11) y+320959344 (x^12) y+238362096 (x^13) y+165694168 (x^14) y+107317472 (x^15) y+64465760 (x^16) y+35747736 (x^17) y+18206112 (x^18) y+8465864 (x^19) y+3568520 (x^20) y+1351200 (x^21) y+454160 (x^22) y+133344 (x^23) y+33432 (x^24) y+6920 (x^25) y+1120 (x^26) y+128 (x^27) y+8 (x^28) y+2482720 (y^2)+22891320 x (y^2)+94198904 (x^2) (y^2)+242431800 (x^3) (y^2)+450068552 (x^4) (y^2)+654453256 (x^5) (y^2)+789355804 (x^6) (y^2)+825703388 (x^7) (y^2)+775886008 (x^8) (y^2)+671327488 (x^9) (y^2)+541877408 (x^10) (y^2)+409193176 (x^11) (y^2)+288090952 (x^12) (y^2)+188018864 (x^13) (y^2)+113070440 (x^14) (y^2)+62297856 (x^15) (y^2)+31259612 (x^16) (y^2)+14187724 (x^17) (y^2)+5775636 (x^18) (y^2)+2085892 (x^19) (y^2)+658480 (x^20) (y^2)+177912 (x^21) (y^2)+39848 (x^22) (y^2)+7016 (x^23) (y^2)+876 (x^24) (y^2)+60 (x^25) (y^2)+7565864 (y^3)+55129248 x (y^3)+186825392 (x^2) (y^3)+403171104 (x^3) (y^3)+634499840 (x^4) (y^3)+790095400 (x^5) (y^3)+826100360 (x^6) (y^3)+759845384 (x^7) (y^3)+635858088 (x^8) (y^3)+492935808 (x^9) (y^3)+355298072 (x^10) (y^3)+236881728 (x^11) (y^3)+144933768 (x^12) (y^3)+80761344 (x^13) (y^3)+40700744 (x^14) (y^3)+18417232 (x^15) (y^3)+7419448 (x^16) (y^3)+2632648 (x^17) (y^3)+811400 (x^18) (y^3)+213224 (x^19) (y^3)+46616 (x^20) (y^3)+8208 (x^21) (y^3)+1120 (x^22) (y^3)+112 (x^23) (y^3)+8 (x^24) (y^3)+14559104 (y^4)+86880060 x (y^4)+245196860 (x^2) (y^4)+444444348 (x^3) (y^4)+591775158 (x^4) (y^4)+629648166 (x^5) (y^4)+570350526 (x^6) (y^4)+461225854 (x^7) (y^4)+342355148 (x^8) (y^4)+234901564 (x^9) (y^4)+148003264 (x^10) (y^4)+84713456 (x^11) (y^4)+43616180 (x^12) (y^4)+20028804 (x^13) (y^4)+8131756 (x^14) (y^4)+2888276 (x^15) (y^4)+885190 (x^16) (y^4)+229758 (x^17) (y^4)+49158 (x^18) (y^4)+8326 (x^19) (y^4)+1032 (x^20) (y^4)+80 (x^21) (y^4)+19791548 (y^5)+97483664 x (y^5)+228747504 (x^2) (y^5)+346183624 (x^3) (y^5)+387197192 (x^4) (y^5)+349979592 (x^5) (y^5)+273558248 (x^6) (y^5)+193373544 (x^7) (y^5)+125628048 (x^8) (y^5)+74524472 (x^9) (y^5)+39779712 (x^10) (y^5)+18852272 (x^11) (y^5)+7847296 (x^12) (y^5)+2838640 (x^13) (y^5)+880664 (x^14) (y^5)+230224 (x^15) (y^5)+49504 (x^16) (y^5)+8440 (x^17) (y^5)+1096 (x^18) (y^5)+96 (x^19) (y^5)+8 (x^20) (y^5)+20142640 (y^6)+81550280 x (y^6)+157650524 (x^2) (y^6)+196858252 (x^3) (y^6)+182759100 (x^4) (y^6)+138952100 (x^5) (y^6)+92875780 (x^6) (y^6)+56569284 (x^7) (y^6)+31371084 (x^8) (y^6)+15537764 (x^9) (y^6)+6741984 (x^10) (y^6)+2525624 (x^11) (y^6)+805928 (x^12) (y^6)+215352 (x^13) (y^6)+47032 (x^14) (y^6)+8112 (x^15) (y^6)+1020 (x^16) (y^6)+92 (x^17) (y^6)+15869512 (y^7)+52191864 x (y^7)+81845368 (x^2) (y^7)+82824216 (x^3) (y^7)+62696464 (x^4) (y^7)+39468488 (x^5) (y^7)+22176920 (x^6) (y^7)+11337000 (x^7) (y^7)+5164112 (x^8) (y^7)+2035792 (x^9) (y^7)+679544 (x^10) (y^7)+188672 (x^11) (y^7)+42560 (x^12) (y^7)+7520 (x^13) (y^7)+1016 (x^14) (y^7)+80 (x^15) (y^7)+8 (x^16) (y^7)+9870431 (y^8)+25885461 x (y^8)+32198437 (x^2) (y^8)+25728229 (x^3) (y^8)+15465369 (x^4) (y^8)+7861009 (x^5) (y^8)+3606937 (x^6) (y^8)+1484553 (x^7) (y^8)+525444 (x^8) (y^8)+153988 (x^9) (y^8)+36488 (x^10) (y^8)+6760 (x^11) (y^8)+888 (x^12) (y^8)+96 (x^13) (y^8)+4897822 (y^9)+9979160 x (y^9)+9540792 (x^2) (y^9)+5794200 (x^3) (y^9)+2655456 (x^4) (y^9)+1047096 (x^5) (y^9)+375016 (x^6) (y^9)+116736 (x^7) (y^9)+29360 (x^8) (y^9)+5736 (x^9) (y^9)+864 (x^10) (y^9)+64 (x^11) (y^9)+8 (x^12) (y^9)+1945892 (y^10)+2971996 x (y^10)+2088228 (x^2) (y^10)+908772 (x^3) (y^10)+297204 (x^4) (y^10)+85484 (x^5) (y^10)+22424 (x^6) (y^10)+4696 (x^7) (y^10)+684 (x^8) (y^10)+92 (x^9) (y^10)+617344 (y^11)+672520 x (y^11)+324952 (x^2) (y^11)+91784 (x^3) (y^11)+19088 (x^4) (y^11)+3728 (x^5) (y^11)+640 (x^6) (y^11)+48 (x^7) (y^11)+8 (x^8) (y^11)+154938 (y^12)+112070 x (y^12)+33510 (x^2) (y^12)+5062 (x^3) (y^12)+552 (x^4) (y^12)+80 (x^5) (y^12)+30212 (y^13)+13000 x (y^13)+1992 (x^2) (y^13)+96 (x^3) (y^13)+8 (x^4) (y^13)+4436 (y^14)+940 x (y^14)+48 (x^2) (y^14)+464 (y^15)+32 x (y^15)+31 (y^16)+(y^17),Missing["NotAvailable"][x,y],Missing["NotAvailable"]/.f_Function:>f[x,y]}]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

LinearRecurrence[r,Take[poly,Length[r]],Length[poly]]-poly//Expand

Crown

poly=DeleteMissing@Table[GraphData[{"Crown",n},"TuttePolynomial"],{n,3,20}]/.f_Function:>f/.f_Function:>f[x,y]

Head/@Table[FindLinearRecurrence[Drop[poly,k]],{k,0,2}]//Union

CubeConnectedCycle

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

Cycle

Entity["Graph",{"Cycle",n}]["TuttePolynomial"]

l=Table[GraphData[{"Cycle",n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,3,20}]

r=FindLinearRecurrence[l]

RSolve[{p[n]==(1+x)p[n-1]-x p[n-2],p[3]==l[[1]],p[4]==l[[2]]},p[n],n]//FullSimplify

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

Empty

Entity["Graph",{"Empty",n}]["TuttePolynomial"]

p=Table[GraphData[{"Empty",n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,4}]

FibonacciCube

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"TuttePolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f/.f_Function:>f[x,y]])//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)FindGeneratingFunction[poly,z]]

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

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

FullSimplify[poly2-poly]

FoldedCube

Forest

Select[GraphData["Forest"],GraphData[#,"TuttePolynomial"]/.f_Function:>f[x,y]=!=x^GraphData[#,"E"]&]

Gear

Select[GraphData[class="Gear"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=3,20}],(_GraphData|_Missing)[_]]//Quiet

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Table[With[{t=(Sqrt[-4 (x^2) y+(((1+x+(x^2)+y))^2)])},
(2^(-n)) (-(2^n)-(2^n) x-(2^n) y+(2^n) x y+(((1+x+(x^2)+y-t))^n)+(((1+x+(x^2)+y+t))^n))
],{n,3,5}]//Expand

Take[poly,3]

Grid n×n

p=Table[GraphData[{"Grid",{n,n}},"TuttePolynomial"]/.f_Function:>f[x,y],{n,4}]

FindLinearRecurrence[p]

Grid n×n×n

p=Table[GraphData[{"Grid",{n,n,n}},"TuttePolynomial"]/.f_Function:>f[x,y],{n,3}]

{1,11 x+32 (x^2)+40 (x^3)+29 (x^4)+15 (x^5)+5 (x^6)+(x^7)+11 y+46 x y+52 (x^2) y+24 (x^3) y+6 (x^4) y+25 (y^2)+39 x (y^2)+12 (x^2) (y^2)+20 (y^3)+8 x (y^3)+7 (y^4)+(y^5),Missing["NotAvailable"][x,y]}

FindLinearRecurrence[p]

{-1,11 x+32 (x^2)+40 (x^3)+29 (x^4)+15 (x^5)+5 (x^6)+(x^7)+11 y+46 x y+52 (x^2) y+24 (x^3) y+6 (x^4) y+25 (y^2)+39 x (y^2)+12 (x^2) (y^2)+20 (y^3)+8 x (y^3)+7 (y^4)+(y^5)+Missing["NotAvailable"][x,y]}

HalvedCube

Select[GraphData[class="HalvedCube"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

GraphData[class]

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=1,20}]

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Hanoi

Select[GraphData[class="Hanoi"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

GraphData[class]

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=1,20}]

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Helm

Select[GraphData[class="Helm"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

GraphData[class]

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=3,20}]

r=Factor/@FindLinearRecurrence[poly]

Length[r]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

With[{t=(x+y+1)^2-4x y},Subtract@@{(((1+x))^2)-2 (-1+x) y+(y^2),t}]//Expand

FullSimplify[soln[[1,1,2]]/.(Sqrt[(((1+x))^2)-2 (-1+x) y+(y^2)]) ->t]

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Expand[(-1+x (-1+y)-y)]

Table[With[{t=(Sqrt[(((1+x))^2)-2 (-1+x) y+(y^2)])},x^n(-1-x-y+x y+ (2^(-n))((((1-t+x+y))^n)+(((1+t+x+y))^n)))],{n,3,5}]//Expand

Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,3,5}]//Expand

Hypercube

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

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=1,20}]

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

King

Ladder

Entity["Graph",{"Ladder",n}]["TuttePolynomial"]

poly=Table[GraphData[{"Ladder",n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,10}]

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[{p[n,x]==(1+x+(x^2)+y)p[n-1,x]-(x^2) y p[n-2,x],p[1,x]==poly[[1]],p[2,x]==poly[[2]]},p[n,x],n]//FullSimplify

Table[soln[[1,1,2]],{n,3}]//FullSimplify

FullSimplify[soln[[1,1,2]]/.{(Sqrt[-4 (x^2) y+(((1+x+(x^2)+y))^2)])->s,(1/(Sqrt[-4 (x^2) y+(((1+x+(x^2)+y))^2)]))->1/s}]

poly[[{1,2}]]

Table[With[{s=(Sqrt[-4 (x^2) y+(((1+x+(x^2)+y))^2)])},
(((2^(-1-n)) ((((1+s+x+(x^2)+y))^n) (1+s (-1+x)+(x^3)+y-x y)-(((1-s+x+(x^2)+y))^n) (1+s-s x+(x^3)+y-x y)))/(s (x^2)))
],{n,4}]//Factor

(((2^(-n-1)) ((s (x-1)+(x^3)-x y+y+1) (((s+(x^2)+x+y+1))^n)-(-s x+s+(x^3)-x y+y+1) (((-s+(x^2)+x+y+1))^n)))/(s (x^2)))

Table[GraphData[{"Ladder",n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,4}]

A035607

Factor/@Series[(1+x)/(1-x-x*y-x^2*y),{x,0,5}]

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

FullSimplify[(1/(Sqrt[1+6 y+(y^2)]))(2^(-1-n)) ((((1+y-(Sqrt[1+6 y+(y^2)])))^n) (-3-y+(Sqrt[1+6 y+(y^2)]))+(((1+y+(Sqrt[1+6 y+(y^2)])))^n) (3+y+(Sqrt[1+6 y+(y^2)]))),n>0&&n∈Integers]

LadderRung

Select[GraphData[class="LadderRung"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

GraphData[class]

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=1,20}],(_GraphData|_Missing)[_]]//Quiet

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["TuttePolynomial"]

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=3,20}]

(r=Factor/@FindLinearRecurrence[Take[poly,All]])//Timing

Length[r]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

LinearRecurrence[r,Take[poly,Length[r]],Length[poly]]-poly//Expand

Mycielski

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

Odd

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

Pan

Select[GraphData[class="Pan"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

GraphData[class]

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=3,20}],(_GraphData|_Missing)[_]]//Quiet

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Factor[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Path

Entity["Graph",{"Path",n}]["TuttePolynomial"]

poly=Table[GraphData[{"Path",n},"TuttePolynomial"]/.f_Function:>f/.f_Function:>f[x,y],{n,n0=1,20}]

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

PathComplement

poly=Table[GraphData[{"PathComplement",n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,20}]

Head/@poly

r=Factor/@FindLinearRecurrence[Take[poly,15]]//Head//Timing

PermutationStar

Prism

Entity["Graph",{"Prism",n}]["TuttePolynomial"]

poly=Table[GraphData[{"Prism",n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=2,20}]

(r=Factor/@FindLinearRecurrence[poly])//Timing

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

LinearRecurrence[r,Take[poly,Length[r]],Length[poly]]-poly//Expand

Queen n×n

poly=DeleteMissing@Table[GraphData[{"Queen",{n,n}},"TuttePolynomial"],{n,10}]/.f_Function:>f/.f_Function:>f[x,y]

Table[FindLinearRecurrence[Drop[poly,k]],{k,0,2}]

Rook n×n

poly=DeleteMissing@Table[GraphData[{"Rook",{n,n}},"TuttePolynomial"],{n,10}]/.f_Function:>f/.f_Function:>f[x,y]

Table[FindLinearRecurrence[Drop[poly,k]],{k,0,2}]

RookComplement n×n

poly=DeleteMissing@Table[GraphData[{"RookComplement",{n,n}},"TuttePolynomial"],{n,10}]/.f_Function:>f/.f_Function:>f[x,y]

Table[FindLinearRecurrence[Drop[poly,k]],{k,0,2}]

SierpinskiCarpet

SierpinskiSieve

Star

Entity["Graph",{"Star",n}]["TuttePolynomial"]

poly=Table[GraphData[{"Star",n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=2,20}],(_GraphData|_Missing)[_]]//Quiet

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Sun

ByteCount/@Table[GraphData[{"Sun",n},"TuttePolynomial"],{n,3,14}]

Select[GraphData[class="Sun"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

(poly=Table[GraphData[{"Sun",n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=3,8}])//Column

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

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

Sunlet

Select[GraphData[class="Sunlet"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

GraphData[class]

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=3,20}]

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Factor[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Tetrahedral

TorusGrid

Triangular

Select[GraphData[class="Triangular"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

GraphData[class]

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=1,20}]

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

TriangularGrid

Select[GraphData[class="TriangularGrid"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

GraphData[class]

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=1,20}]

(r=Factor/@FindLinearRecurrence[poly])//Timing

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

TriangularHoneycombRook

Select[GraphData[class="TriangularHoneycombRook"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

GraphData[class]

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=1,20}]

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Web

Select[GraphData[class="Web"],Head[GraphData[#,"TuttePolynomial"]]===Missing&]

GraphData["Web"]

poly=Table[GraphData[{class,n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=3,15}],(_GraphData|_Missing)[_]]//Quiet

r=Factor/@FindLinearRecurrence[poly]

Length[r]

(Subscript[p, n])[x]==r.Table[(Subscript[p, n-k])[x],{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1,x]==poly[[n]],{n,Length[r]}],p[n,x]==r.Table[p[n-k,x],{k,Length[r]}]],p[n,x],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

LinearRecurrence[r,Take[poly,Length[r]],Length[poly]]-poly//Expand

Wheel

Entity["Graph",{"Wheel",n}]["TuttePolynomial"]

poly=Table[GraphData[{"Wheel",n},"TuttePolynomial"]/.f_Function:>f[x,y],{n,n0=4,20}],(_GraphData|_Missing)[_]]//Quiet

r=Factor/@FindLinearRecurrence[poly]

(Subscript[p, n])==r.Table[(Subscript[p, n-k]),{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1]==poly[[n]],{n,Length[r]}],p[n]==r.Table[p[n-k],{k,Length[r]}]],p[n],n]//FullSimplify

Factor[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Subtract@@{(x^2)-2 x (-1+y)+(((1+y))^2),(((1+x))^2)-2 (-1+x) y+(y^2)}//Expand

FullSimplify[soln[[1,1,2]]/.{(Sqrt[(((1+x))^2)-2 (-1+x) y+(y^2)])->t,(Sqrt[(x^2)-2 x (-1+y)+(((1+y))^2)])->t}]

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

{2 x+3 (x^2)+(x^3)+2 y+4 x y+3 (y^2)+(y^3),3 x+6 (x^2)+4 (x^3)+(x^4)+3 y+9 x y+((4 )^2) y+6 (y^2)+4 x (y^2)+4 (y^3)+(y^4)}

TuttePolynomial[GraphData[{"Wheel",4}],{x,y}]

TuttePolynomial[GraphData[{"Wheel",5}],{x,y}]

Take[poly,2]