A293595 -id:A293595 - 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.

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

Jair Taylor, May 13 2012

nonn

Also known as cyclic Carlitz compositions.

			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.

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

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.

Removing restriction on the first and last parts gives the Carlitz compositions, A003242.
Row sums of A293595.
Cf. A106369, A241902.

# 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(%);

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

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

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

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

A296167 Triangle read by rows: T(n,k) is the number of circular compositions of n with length k such that no two adjacent parts are equal (1 <= k <= n).

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 2, 0, 0, 0, 1, 2, 2, 1, 0, 0, 1, 3, 2, 1, 0, 0, 0, 1, 3, 4, 3, 0, 0, 0, 0, 1, 4, 6, 4, 2, 1, 0, 0, 0, 1, 4, 8, 11, 4, 1, 0, 0, 0, 0, 1, 5, 10, 13, 10, 3, 0, 0, 0, 0, 0, 1, 5, 14, 22, 18, 10, 2, 1, 0, 0, 0, 0, 1, 6, 16, 29, 32, 20, 6, 1, 0, 0, 0, 0, 0, 1, 6, 20, 44, 50, 40, 18, 4, 0, 0, 0, 0, 0, 0

Offset: 1

Petros Hadjicostas, Dec 07 2017

By "circular compositions" here we mean equivalence classes of compositions with parts on a circle such that two compositions are equivalent if one is a cyclic shift of the other. We may call them "circular Carlitz compositions".
The formula below for T(n,k) involves indicator functions of conditions because unfortunately circular compositions of length 1 are considered Carlitz by most authors (even though, strictly speaking, they are not since the single number in such a composition is "next to itself" if we go around the circle).
To prove that the two g.f.'s below are equal to each other, use the geometric series formula, change the order of summations where it is necessary, and use the result Sum_{n >= 1} (phi(n)/n)*log(1 + x^n) = Sum_{n >= 1} (phi(n)/n)*log(1 - x^(2*n)) - Sum_{n >= 1} (phi(n)/n)*log(1 - x^n) = -x^2/(1 - x^2) + x/(1 - x) = x/(1 - x^2).

			Triangle T(n,k) (with rows n >= 1 and columns k = 1..n) begins:
  1;
  1,  0;
  1,  1,  0;
  1,  1,  0,  0;
  1,  2,  0,  0,  0;
  1,  2,  2,  1,  0,  0;
  1,  3,  2,  1,  0,  0,  0;
  1,  3,  4,  3,  0,  0,  0,  0;
  1,  4,  6,  4,  2,  1,  0,  0,  0;
  1,  4,  8, 11,  4,  1,  0,  0,  0,  0;
  ...
Case n=6:
The included circular compositions are:
k=1: 6;                                => T(6,1) = 1
k=2: 15, 24;                           => T(6,2) = 2
k=3: 123, 321;                         => T(6,3) = 2
k=4: 1212;                             => T(6,4) = 1
k=5: none;                             => T(6,5) = 0
k=6: none;                             => T(6,6) = 0

P. Hadjicostas, Cyclic, dihedral and symmetrical Carlitz compositions of a positive integer, Journal of Integer Sequences, 20 (2017), Article 17.8.5.

Row sums are in A106369.

Cf. A003242, A239327, A291941, A293595.

nmax = 14; gf (* of A293595 *) = Sum[x^(2j) y^2/(1 + x^j y), {j, 1, nmax}] + Sum[x^j y/(1 + x^j y)^2, {j, 1, nmax}]/(1 - Sum[x^j y/(1 + x^j y), {j, 1, nmax}]) + O[x]^(nmax + 1) + O[y]^(nmax + 1) // Normal // Expand;
A293595[n_, k_] := SeriesCoefficient[gf, {x, 0, n}, {y, 0, k}];
T[n_, k_] := Boole[k == 1] + (1/k) Sum[EulerPhi[d] A293595[n/d, k/d]* Boole[k/d != 1], {d, Divisors[GCD[n, k]]}];
Table[T[n, k], {n, 1, nmax}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 26 2020 *)

T(n,k) = [k = 1] + (1/k)*Sum_{d | gcd(n,k)} phi(d)*A293595(n/d, k/d) * [k/d <> 1], where [ ] is the Iverson Bracket.
G.f.: Sum_{n,k >= 1} T(n,k)*x^n*y^k = x*y/(1-x) - Sum_{s>=1} (phi(s)/s)*f(x^s,y^s), where f(x,y) = log(1 - Sum_{n >= 1} x^n*y/(1 + x^n*y)) + Sum_{n >= 1} log(1 + x^n*y).
G.f.: -Sum_{s >= 1} (x*y)^(2*s + 1)/(1-x^(2*s + 1)) - Sum_{s >= 1} (phi(s)/s)*g(x^s,y^s), where g(x,y) = log(1 + Sum_{n >= 1} (-x*y)^n/(1 - x^n)).

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula