A072373 Complexity of doubled cycle (regarding case n = 2 as a graph).

1, 4, 75, 384, 1805, 8100, 35287, 150528, 632025, 2620860, 10759331, 43804800, 177105253, 711809364, 2846259375, 11330543616, 44929049777, 177540878700, 699402223099, 2747583822720, 10766828545725, 42095796462852, 164244726238343, 639620518118400, 2486558615814025

Offset: 1

Author

Michael Somos, Jul 19 2002

Keywords

• nonn
• easy

Links

• Stefano Spezia, Table of n, a(n) for n = 1..1700
• Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212.
• Index entries for linear recurrences with constant coefficients, signature (10,-35,52,-35,10,-1).

Crossrefs

Apart from a(2) coincides with A006235.

Programs

PARI

/* prism (or doubled cycle) graph with n vertices */ prism(n)=if(n%2,[;],matrix(n,n,i,j,i!=j && ((abs(i-j)==1 && (i+j)!=n+1) || (abs(i-j)==n/2-1 && (i+j)%n==n/2+1) || abs(i-j)==n/2)))

PARI

/* treenumber (or complexity) of a graph */ treenumber(m)=local(n); n=matdim(m); if(n,matdet(adj2laplace(m)+matone(n))/n^2)

PARI

/* convert adjacency matrix to laplacian matrix */ adj2laplace(m)=local(l,n); n=matdim(m); matdiagonal(m*vectorv(n,i,1))-m

PARI

/* matrix J of all ones */ matone(n)=matrix(n,n,i,j,1) /* dimension of a square matrix */ matdim(m)=matsize(m)[1]

PARI

a(n)=treenumber(prism(2*n))

PARI

a(n)=if(n<0,0,polcoeff(-8*x^2+x*(1+2*x-10*x^2+2*x^3+x^4)/((1-x)*(1-4*x+x^2))^2+x*O(x^n),n))

Formula

G.f.: -8*x^2+x*(1+2*x-10*x^2+2*x^3+x^4)/((1-x)*(1-4*x+x^2))^2.

a(n) = 10*a(n-1)-35*a(n-2)+52*a(n-3)-35*a(n-4)+10*a(n-5)-a(n-6), n>8.