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
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
KEYWORD
easy,nonn
AUTHOR
Jean-Luc Marichal (jean-luc.marichal(AT)uni.lu), Jan 24 2007
STATUS
approved