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

Comments

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

Links

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.

Formula

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

Maple

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

Mathematica

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

Prog

(PARI)
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 */

Crossrefs

Cf. A001608, A113788, A127682, A127685.

Sequence in context: A058768 A127682 A127685 * A024156 A241316 A241312

Adjacent sequences: A127684 A127685 A127686 * A127688 A127689 A127690

Keyword

easy,nonn

Author

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

Status

approved