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,2

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]

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

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

Prog

(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
(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

Crossrefs

Cf. A112850, A260878.

Sequence in context: A149241 A149242 A149243 * A149244 A149245 A054105

Adjacent sequences: A112846 A112847 A112848 * A112850 A112851 A112852

Keyword

easy,nonn

Author

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

Status

approved