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

1, 2, 5, 17, 74, 365, 1889, 9938, 52565, 278513, 1476506, 7828925, 41513921, 220137122, 1167334565, 6190107857, 32824743914, 174062236685, 923012961569, 4894530600818, 25954597551605, 137631407453873, 729828474212666

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. For n+1<=i<j<=2n, create a directed edge from vertex j to vertex i. 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 Toeplitz 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..22.

Index entries for linear recurrences with constant coefficients, signature (7, -9).

Formula

G.f.: A(x) = (1-5*x)/(9*x^2-7*x+1)

a(0)=1, a(1)=2, a(n)=7*a(n-1)-9*a(n-2). - Harvey P. Dale, Jun 08 2013

Example

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

Maple

h:=n->transpose(ToeplitzMatrix([seq(-1, i=1..n-3), -1, -1, 2, seq(2^(i-2), i=2..n)])); B:=[1, 2, 5, seq(det(h(i)), i=3..25)];

Mathematica

CoefficientList[Series[(1-5x)/(9x^2-7x+1), {x, 0, 30}], x] (* or *) LinearRecurrence[{7, -9}, {1, 2}, 30] (* Harvey P. Dale, Jun 08 2013 *)

Crossrefs

See also A112832.

Sequence in context: A217944 A007868 A136726 * A081046 A000774 A260948

Adjacent sequences: A112828 A112829 A112830 * A112832 A112833 A112834

Keyword

easy,nonn

Author

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

Status

approved