login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #4 Mar 31 2012 10:29:16

%S 1,2,5,17,61,226,841,3137,11705,43682,163021,608401,2270581,8473922,

%T 31625105,118026497,440480881,1643897026,6135107221,22896531857,

%U 85451020205,318907548962,1190179175641,4441809153601,16577057438761

%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 if j-i is either 1 or 2. For n+1<=i<j<=2n, create a directed edge from vertex j to vertex i if j-i is either 1 or 2. 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.

%C For n>=0, the set {A112832(2n+1)} is the intersection of the set of numbers of the form a^2+(a+1)^2 and the set of numbers of the form b^2+5(b+1)^2. - _Kieren MacMillan_, Dec 19 2007

%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-2*x-3*x^2+x^3)/(1-4*x+4*x^3-x^4)

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

%p f:=n->transpose(ToeplitzMatrix([seq(0,i=1..n-3),-1,-1,2,seq(fibonacci(i), i=2..n)])); A:=[1,2,5,seq(det(f(i)),i=3..25)];

%Y See also A112831.

%K easy,nonn

%O 0,2

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