A114300 - OEIS

%I #11 Nov 21 2013 12:48:46

%S 1,2,5,17,40,101,260,677,1768,4625,12104,31685,82948,217157,568520,

%T 1488401,3896680,10201637,26708228,69923045,183060904,479259665,

%U 1254718088,3284894597,8599965700,22515002501,58945041800

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

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

%F 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)

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

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

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

%Y See also A112831 and A112832.

%K easy,nonn

%O 0,2

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