login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A127687 Number of unlabeled maximal independent sets in the n-cycle graph. 3
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 (list; graph; refs; listen; history; text; internal format)
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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 6 04:15 EDT 2020. Contains 334859 sequences. (Running on oeis4.)