A114300 Number of non-intersecting cycle systems in a particular directed graph.

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

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 n-1 to vertex n, from vertex n+2 to vertex n+1 and from vertex 2n to vertex 2n-1. 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 vertex-disjoint unions of directed cycles in this graph. Also calculable as the determinant of an n X n matrix.

References

C. Hanusa (2005). A Gessel-Viennot-Type 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) = (1-x-x^2+5*x^3-6*x^4-6*x^5+3*x^6)/(1-3*x+3*x^3-x^4)

Example

The number of non-intersecting cycle systems in the particular directed graph of order 4 is 40.

Maple

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

Mathematica

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

Crossrefs

See also A112831 and A112832.

Sequence in context: A118727 A183906 A042361 * A099207 A320102 A197918

Adjacent sequences: A114297 A114298 A114299 * A114301 A114302 A114303

Keyword

easy,nonn

Author

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

Status

approved