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.

1, 1, 1, 3, 3, 5, 13, 17, 29, 55, 99, 161, 293, 507, 881, 1561, 2727, 4743, 8337, 14579, 25497, 44675, 78173, 136753, 239437, 419077, 733377, 1283701, 2246823, 3932249, 6882603, 12046313, 21083545, 36901587, 64586887, 113042011, 197851265, 346287829, 606086169

Offset: 0

Author

Jair Taylor, May 13 2012

Keywords

• nonn

Comments

Also known as cyclic Carlitz compositions.

Examples

			The cyclic Carlitz compositions of the n = 1...6 are
1;
2;
12, 21, 3;
13, 31, 4;
14, 23, 32, 41,5;
1212, 123, 132, 15, 2121, 213, 231, 24, 312, 321, 42, 51, 6.
		

References

• Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010, pages 87-88.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 200 terms from Jair Taylor)
• P. Hadjicostas, Cyclic, dihedral and symmetric Carlitz compositions of a positive integer, Journal of Integer Sequences, 20 (2017), Article 17.8.5.
• Jair Taylor, Counting Words with Laguerre Series, Electron. J. Combin., 21 (2014), P2.1.

Crossrefs

Removing restriction on the first and last parts gives the Carlitz compositions, A003242.

Row sums of A293595.

Cf. A106369, A241902.

Programs

Maple

# For getting the first M-1 terms, from N. J. A. Sloane, Apr 26 2014
M:=101:
t1:=add(x^i/(1+x^i),i=1..M):
t2:=add(x^i/(1+x^i)^2,i=1..M):
t3:=add(x^(2*i)/(1+x^i),i=1..M):
t0:=t2/(1-t1)+t3:
series(t0,x,30);
seriestolist(%);

Mathematica

terms = 39;
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;
CoefficientList[gf, x] (* Jean-François Alcover, Dec 30 2017 *)

PARI

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

Sage

for n in range(15):
    Q = []
    for comp in Compositions(n) :
        if len(comp) == 1 or all(comp[k] != comp[k+1] for k in range(-1,len(comp)-1)):
            Q.append(comp)
    print(len(Q))

Formula

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

a(n) ~ c * d^n, where d = 1.750241291718309031249738624639... (see A241902), c = 0.350601274598240344779505805689.... - Vaclav Kotesovec, May 01 2014