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

Comments

Also known as cyclic Carlitz compositions.

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.

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

Example

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.

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

Prog

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

Crossrefs

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

Row sums of A293595.

Cf. A106369, A241902.

Sequence in context: A320176 A298478 A144419 * A367005 A226921 A133190

Adjacent sequences: A212319 A212320 A212321 * A212323 A212324 A212325

Keyword

nonn

Author

Jair Taylor, May 13 2012

Status

approved