

A114300


Number of nonintersecting cycle systems in a particular directed graph.


1



1, 2, 5, 17, 40, 101, 260, 677, 1768, 4625, 12104, 31685, 82948, 217157, 568520, 1488401, 3896680, 10201637, 26708228, 69923045, 183060904, 479259665, 1254718088, 3284894597, 8599965700, 22515002501, 58945041800
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Define a graph with 2n vertices. Vertices 1 through n will be on the top half, vertices n+1 through 2n will be on the bottom half. For 1 <= i < j <=n, create a directed edge from vertex i to vertex j whenever j=i+2. For n+1<=i<j<=2n, create a directed edge from vertex j to vertex i whenever j=i+2. Create a directed edge from vertex 1 to vertex 2, from vertex n1 to vertex n, from vertex n+2 to vertex n+1 and from vertex 2n to vertex 2n1. Lastly, create a directed edge from i to n+i and vice versa for 1 <= i <= n. (A graph of this general type is called a hamburger.) The value a(n) gives the number of vertexdisjoint unions of directed cycles in this graph. Also calculable as the determinant of an n X n matrix.


REFERENCES

C. Hanusa (2005). A GesselViennotType Method for Cycle Systems with Applications to Aztec Pillows. PhD Thesis. University of Washington, Seattle, USA.


LINKS

Table of n, a(n) for n=0..26.


FORMULA

G.f.: A(x) = (1xx^2+5*x^36*x^46*x^5+3*x^6)/(13*x+3*x^3x^4)


EXAMPLE

The number of nonintersecting cycle systems in the particular directed graph of order 4 is 40.


MAPLE

A114300 := n>coeff(series((1xx^2+5*x^36*x^46*x^5+3*x^6)/(13*x+3*x^3x^4), x=0, n+1), x, n);


MATHEMATICA

CoefficientList[Series[(3x^66x^56x^4+5x^3x^2x+1)/ (x^4+3x^33x+1), {x, 0, 30}], x] (* Harvey P. Dale, Apr 19 2011 *)


CROSSREFS

See also A112831 and A112832.
Sequence in context: A118727 A183906 A042361 * A099207 A197918 A122566
Adjacent sequences: A114297 A114298 A114299 * A114301 A114302 A114303


KEYWORD

easy,nonn


AUTHOR

Christopher Hanusa (chanusa(AT)math.binghamton.edu), Nov 21 2005


STATUS

approved



