A127685 -id:A127685 - cp's OEIS frontend

A127687 Number of unlabeled maximal independent sets in the n-cycle graph.

0, 1, 1, 1, 1, 2, 1, 2, 2, 3, 2, 4, 3, 5, 6, 7, 7, 11, 11, 16, 19, 24, 28, 39, 46, 60, 75, 97, 120, 159, 197, 257, 327, 422, 539, 700, 892, 1157, 1488, 1928, 2479, 3219, 4148, 5383, 6961, 9029, 11687, 15184, 19673, 25564, 33174, 43125, 56010, 72868, 94719, 123283

Offset: 1

Jean-Luc Marichal (jean-luc.marichal(AT)uni.lu), Jan 24 2007

Number of unlabeled (i.e., defined up to a rotation) maximal independent sets in the n-cycle graph. Also: Number of cyclic compositions of n in which each term is either 2 or 3.

(a(n)*n - A001608(n)) mod 2 is a binary sequence of period 14: [0,0,0,0,0,1,0,0,0,1,0,1,0,1]. - Richard Turk, Aug 25 2017

G. C. Greubel, Table of n, a(n) for n = 1..5000
R. Bisdorff and J.-L. Marichal, Counting non-isomorphic maximal independent sets of the n-cycle graph, arXiv:0701647 [math.CO] (2007) and JIS 11 (2008) 08.5.7.
P. Flajolet and M. Soria, The Cycle Construction In SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.

Cf. A001608, A113788, A127682, A127685.

with(numtheory):
perrin:=proc(n) option remember: if n=0 then 3 elif n=1 then 0 elif n=2 then 2 else perrin(n-2)+perrin(n-3) fi end:
a:=proc(n) local d,N:d:=divisors(n);N:=nops(d):
add(phi(n/d[k])*perrin(d[k]),k=1..N)/n end:
seq(a(n),n=1..50);
# Robert FERREOL, Apr 10 2024

(* p = A001608 *) p[n_] := p[n] = p[n - 2] + p[n - 3]; p[0] = 3; p[1] = 0; p[2] = 2; A113788[n_] := (1/n)*Sum[MoebiusMu[n/d]*p[d], {d, Divisors[n]}]; a[n_] := Sum[A113788[d], {d, Divisors[n]}]; Table[a[n], {n, 1, 56}] (* Jean-François Alcover, Jul 16 2012, from formula *)

N = 66;  x = 'x + O('x^N);
f(x) = x^2+x^3;
gf = 'c0 + sum(n=1,N, eulerphi(n)/n*log(1/(1-f(x^n)))  );
v = Vec(gf); v[1]-='c0; v  /* includes a(0)=0 */
/* Joerg Arndt, Jan 21 2013 */

a(n) = Sum_{d|n} A113788(d) = 2 * A127685(n) - A127682(n) = (1/n)*(Sum_{d|n} A000010(n/d) * A001608(d)).

G.f.: Sum_{k>=1} (phi(k)/k) * log( 1/(1-B(x^k)) ) where B(x) = x^2 + x^3. - Joerg Arndt, Jan 21 2013

A127686 Number of non-isomorphic maximal independent sets of the n-cycle graph having no symmetry axis.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 2, 2, 5, 4, 8, 9, 15, 16, 27, 30, 46, 55, 80, 96, 139, 168, 237, 293, 403, 503, 687, 864, 1164, 1477, 1974, 2516, 3348, 4282, 5668, 7284, 9604, 12374, 16279, 21022, 27597, 35718, 46819, 60693, 79480, 103174

Offset: 1

Jean-Luc Marichal (jean-luc.marichal(AT)uni.lu), Jan 24 2007

Number of non-isomorphic (i.e. defined up to a rotation and a reflection) maximal independent sets of the n-cycle graph having no symmetry axis. Also: Number of cyclic and non-palindromic compositions of n in which each term is either 2 or 3, where a clockwise writing is not distinguished from its counterclockwise counterpart.

R. Bisdorff and J.-L. Marichal, Counting non-isomorphic maximal independent sets of the n-cycle graph, arXiv:0701647 (2007) and JIS 11 (2008) 08.5.7.

Cf. A127682, A127683, A127685.

a(n) = Sum(d divides n) A127683(d) = A127685(n) - A127682(n)

cp's OEIS Frontend

A127687 Number of unlabeled maximal independent sets in the n-cycle graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula