|
%I #24 Apr 10 2024 18:06:02
%S 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,
%T 120,159,197,257,327,422,539,700,892,1157,1488,1928,2479,3219,4148,
%U 5383,6961,9029,11687,15184,19673,25564,33174,43125,56010,72868,94719,123283
%N Number of unlabeled maximal independent sets in the n-cycle graph.
%C 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.
%C (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
%H G. C. Greubel, <a href="/A127687/b127687.txt">Table of n, a(n) for n = 1..5000</a>
%H R. Bisdorff and J.-L. Marichal, <a href="https://arxiv.org/abs/math/0701647">Counting non-isomorphic maximal independent sets of the n-cycle graph</a>, arXiv:0701647 [math.CO] (2007) and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Marichal/marichal.html">JIS 11 (2008) 08.5.7</a>.
%H P. Flajolet and M. Soria, <a href="http://algo.inria.fr/flajolet/Publications/publist.html">The Cycle Construction</a> In SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
%F a(n) = Sum_{d|n} A113788(d) = 2 * A127685(n) - A127682(n) = (1/n)*(Sum_{d|n} A000010(n/d) * A001608(d)).
%F 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
%p with(numtheory):
%p 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:
%p a:=proc(n) local d,N:d:=divisors(n);N:=nops(d):
%p add(phi(n/d[k])*perrin(d[k]),k=1..N)/n end:
%p seq(a(n),n=1..50);
%p # _Robert FERREOL_, Apr 10 2024
%t (* 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 *)
%o (PARI)
%o N = 66; x = 'x + O('x^N);
%o f(x) = x^2+x^3;
%o gf = 'c0 + sum(n=1,N, eulerphi(n)/n*log(1/(1-f(x^n))) );
%o v = Vec(gf); v[1]-='c0; v /* includes a(0)=0 */
%o /* _Joerg Arndt_, Jan 21 2013 */
%Y Cf. A001608, A113788, A127682, A127685.
%K easy,nonn,changed
%O 1,6
%A Jean-Luc Marichal (jean-luc.marichal(AT)uni.lu), Jan 24 2007
|
