A112849 Number of congruence classes (epimorphisms/vertex partitionings induced by graph endomorphisms) of undirected cycles of even length: |C(C_{2*n})|.

1, 4, 11, 36, 127, 463, 1717, 6436, 24311, 92379, 352717, 1352079, 5200301, 20058301, 77558761, 300540196, 1166803111, 4537567651, 17672631901, 68923264411, 269128937221, 1052049481861, 4116715363801, 16123801841551, 63205303218877, 247959266474053, 973469712824057, 3824345300380221, 15033633249770521

Offset: 1

Author

Martin Alexander Michels (martinmichels(AT)t-online.de), Sep 24 2005

Keywords

• easy
• nonn

References

• M. A. Michels, About The Structure of Graph Endomorphisms, Diploma thesis, University of Oldenburg, Germany, 2005.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
• Guo-Niu Han, Enumeration of Standard Puzzles. [Cached copy]
• M. A. Michels and U. Knauer, The congruence classes of paths and cycles, Discrete Math., 309 (2009), 5352-5359. [_N. J. A. Sloane_, Sep 15 2009]

Crossrefs

Cf. A112850, A260878.

Programs

Magma

[1] cat [1 + (1/2)*Binomial(2*n-1, n-1) + (1/2)*Binomial(2*n-1, n): n in [2..30]]; // Vincenzo Librandi, Feb 26 2017

Maple

egf := n->exp(exp(x)*(1-(GAMMA(n,x)/GAMMA(n)))):
a := n->`if`(n=1,1,(2*n)!*coeff(series(egf(n),x,2*n+1),x,2*n)):
seq(a(n),n=1..29); # Peter Luschny, Apr 05 2011

Mathematica

Join[{1}, Table[1 + (1/2) Binomial[2 n - 1, n - 1] + (1/2)Binomial[2 n - 1, n], {n, 2, 30}]] (* Vincenzo Librandi, Feb 26 2017 *)

PARI

a(n) = if (n==1, 1, 1 + (binomial(2*n-1, n-1) + binomial(2*n-1, n))/2); \\ Michel Marcus, Feb 26 2017

Formula

|C(C_2n)| = 1 + (1/2)*binomial(2*n-1, n-1) + (1/2)*binomial(2*n-1, n), n > 1.

a(n) = A260878(n) for n >= 2. - Alois P. Heinz, Aug 06 2015

Conjecture: n*(3*n - 5)*a(n) + (-15*n^2 + 31*n - 12)*a(n-1) + 2*(3*n - 2)*(2*n - 3)*a(n-2) = 0. - R. J. Mathar, Aug 07 2015