A112831 - OEIS

%I #6 Jul 31 2015 18:06:50

%S 1,2,5,17,74,365,1889,9938,52565,278513,1476506,7828925,41513921,

%T 220137122,1167334565,6190107857,32824743914,174062236685,

%U 923012961569,4894530600818,25954597551605,137631407453873,729828474212666

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

%C 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.

%D C. Hanusa (2005). A Gessel-Viennot-Type Method for Cycle Systems with Applications to Aztec Pillows. PhD Thesis. University of Washington, Seattle, USA.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (7, -9).

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

%F a(0)=1, a(1)=2, a(n)=7*a(n-1)-9*a(n-2). - _Harvey P. Dale_, Jun 08 2013

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

%p 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)];

%t 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 *)

%Y See also A112832.

%K easy,nonn

%O 0,2

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