|
| |
|
|
A112832
|
|
Number of non-intersecting cycle systems in a particular directed graph.
|
|
3
|
|
|
|
1, 2, 5, 17, 61, 226, 841, 3137, 11705, 43682, 163021, 608401, 2270581, 8473922, 31625105, 118026497, 440480881, 1643897026, 6135107221, 22896531857, 85451020205, 318907548962, 1190179175641, 4441809153601, 16577057438761
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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 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.
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
|
|
|
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
|
|
|
|
FORMULA
|
G.f.: A(x) = (1-2*x-3*x^2+x^3)/(1-4*x+4*x^3-x^4)
|
|
|
EXAMPLE
|
The number of non-intersecting cycle systems in the particular directed graph of order 4 is 61.
|
|
|
MAPLE
|
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)];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
Christopher Hanusa (chanusa(AT)math.binghamton.edu), Sep 21 2005
|
|
|
STATUS
|
approved
|
| |
|
|
