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