cp's OEIS Frontend

A212322 Number of compositions of n such that no two adjacent parts are equal, and the first part is not equal to the last part if there is more than one part.

%I A212322 #49 Mar 07 2020 08:49:55
%S A212322 1,1,1,3,3,5,13,17,29,55,99,161,293,507,881,1561,2727,4743,8337,14579,
%T A212322 25497,44675,78173,136753,239437,419077,733377,1283701,2246823,
%U A212322 3932249,6882603,12046313,21083545,36901587,64586887,113042011,197851265,346287829,606086169
%N A212322 Number of compositions of n such that no two adjacent parts are equal, and the first part is not equal to the last part if there is more than one part.
%C A212322 Also known as cyclic Carlitz compositions.
%D A212322 Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010, pages 87-88.
%H A212322 Alois P. Heinz, <a href="/A212322/b212322.txt">Table of n, a(n) for n = 0..1000</a> (first 200 terms from Jair Taylor)
%H A212322 P. Hadjicostas, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Hadjicostas/hadji5.html">Cyclic, dihedral and symmetric Carlitz compositions of a positive integer</a>, Journal of Integer Sequences, 20 (2017), Article 17.8.5.
%H A212322 Jair Taylor, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p1">Counting Words with Laguerre Series</a>, Electron. J. Combin., 21 (2014), P2.1.
%F A212322 G.f.: 1 + sum(k>0: x^k/(1+x^k)^2)/(1-sum(k>0, x^k/(1+x^k))) + sum(k>0, x^(2k)/(1+x^k)).
%F A212322 a(n) ~ c * d^n, where d = 1.750241291718309031249738624639... (see A241902), c = 0.350601274598240344779505805689.... - _Vaclav Kotesovec_, May 01 2014
%e A212322 The cyclic Carlitz compositions of the n = 1...6 are
%e A212322 1;
%e A212322 2;
%e A212322 12, 21, 3;
%e A212322 13, 31, 4;
%e A212322 14, 23, 32, 41,5;
%e A212322 1212, 123, 132, 15, 2121, 213, 231, 24, 312, 321, 42, 51, 6.
%p A212322 # For getting the first M-1 terms, from _N. J. A. Sloane_, Apr 26 2014
%p A212322 M:=101:
%p A212322 t1:=add(x^i/(1+x^i),i=1..M):
%p A212322 t2:=add(x^i/(1+x^i)^2,i=1..M):
%p A212322 t3:=add(x^(2*i)/(1+x^i),i=1..M):
%p A212322 t0:=t2/(1-t1)+t3:
%p A212322 series(t0,x,30);
%p A212322 seriestolist(%);
%t A212322 terms = 39;
%t A212322 gf = 1 + Sum[x^k/(1 + x^k)^2, {k, 1, terms}]/(1 - Sum[x^k/(1 + x^k), {k, 1, terms}]) + Sum[x^(2 k)/(1 + x^k), {k, 1, terms}] + O[x]^terms;
%t A212322 CoefficientList[gf, x] (* _Jean-François Alcover_, Dec 30 2017 *)
%o A212322 (Sage)
%o A212322 for n in range(15):
%o A212322     Q = []
%o A212322     for comp in Compositions(n) :
%o A212322         if len(comp) == 1 or all(comp[k] != comp[k+1] for k in range(-1,len(comp)-1)):
%o A212322             Q.append(comp)
%o A212322     print(len(Q))
%o A212322 (PARI)
%o A212322 a(n) = { polcoeff(1 + sum(k=1, n, x^k/(1+x^k)^2 + O(x*x^n))/(1-sum(k=1, n, x^k/(1+x^k) + O(x*x^n))) + sum(k=1, n, x^(2*k)/(1+x^k) + O(x*x^n)), n) } \\ _Andrew Howroyd_, Oct 14 2017
%Y A212322 Removing restriction on the first and last parts gives the Carlitz compositions, A003242.
%Y A212322 Row sums of A293595.
%Y A212322 Cf. A106369, A241902.
%K A212322 nonn
%O A212322 0,4
%A A212322 _Jair Taylor_, May 13 2012