A106369 -id:A106369 - cp's OEIS frontend

A241902 Decimal expansion of a constant related to Carlitz compositions (A003242).

1, 7, 5, 0, 2, 4, 1, 2, 9, 1, 7, 1, 8, 3, 0, 9, 0, 3, 1, 2, 4, 9, 7, 3, 8, 6, 2, 4, 6, 3, 9, 8, 1, 5, 8, 7, 8, 7, 7, 8, 2, 0, 5, 8, 1, 8, 1, 3, 8, 1, 5, 9, 0, 5, 6, 1, 3, 1, 6, 5, 8, 6, 1, 3, 1, 7, 5, 1, 9, 3, 5, 1, 6, 7, 1, 5, 2, 0, 6, 0, 5, 0, 7, 7, 7, 4, 3, 8, 8, 7, 5, 6, 5, 7, 0, 9, 2, 4, 7, 1, 4, 1, 0, 0, 1

Offset: 1

Vaclav Kotesovec, May 01 2014

			1.7502412917183090312497386246398158787782...

Vaclav Kotesovec, Table of n, a(n) for n = 1..1500
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009, p. 201.
A. Knopfmacher and H. Prodinger, On Carlitz compositions, European Journal of Combinatorics, Vol. 19, 1998, pp. 579-589.

Cf. A003242, A224958, A212322, A106357, A261984, A106369.

RealDigits[r /. FindRoot[Exp[QPolyGamma[0, 1 + Pi*I/Log[r], r]] == r^(3/2)/(1-r), {r, 3/2}, WorkingPrecision -> 120], 10, 110][[1]] (* Vaclav Kotesovec, Jun 19 2023 *)

Equals lim n -> infinity A003242(n)^(1/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.

Original entry on oeis.org

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

A292906 Number of dihedral Carlitz compositions of n.

Original entry on oeis.org

1, 1, 2, 2, 3, 5, 6, 9, 14, 20, 29, 48, 69, 110, 175, 278, 441, 725, 1168, 1928, 3170, 5253, 8710, 14563, 24308, 40798, 68520, 115433, 194611, 328938, 556336, 942659, 1598539, 2714379, 4612681, 7847082, 13358850, 22762311, 38810771, 66223599, 113067441, 193172332

Offset: 1

Petros Hadjicostas, Oct 10 2017

nonn

A cyclic Carlitz composition is a composition of length greater than one where adjacent parts, including the first and the last ones, are distinct. A composition of length one is also considered cyclic and Carlitz. Assume two cyclic Carlitz compositions are considered equivalent iff one can be obtained from the other by a rotation or reversal of order. Each equivalence class obtained is called a dihedral Carlitz composition of n.

			a(6) = 5 because n = 6 has the following dihedral Carlitz compositions: 6, 1+5, 2+4, 1+2+3, 1+2+1+2. (For example, the equivalence class for the dihedral Carlitz composition 1+2+3 is {(1,2,3),(2,3,1), (3,1,2), (3,2,1),(2,1,3),(1,3,2)}.)

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

Cf. A106369, A291941, A292200.

a(n) = (A106369(n) + A292200(n))/2.
a(n) = (2*A106369(n) + A291941(n) + 1)/4.
G.f.: (g.f. of A106369 + g.f. of A292200)/2.

A293595 Triangle read by rows: T(n,k) = number of compositions of n into k parts such that no two cyclically adjacent parts are equal.

Original entry on oeis.org

1, 1, 0, 1, 2, 0, 1, 2, 0, 0, 1, 4, 0, 0, 0, 1, 4, 6, 2, 0, 0, 1, 6, 6, 4, 0, 0, 0, 1, 6, 12, 10, 0, 0, 0, 0, 1, 8, 18, 16, 10, 2, 0, 0, 0, 1, 8, 24, 40, 20, 6, 0, 0, 0, 0, 1, 10, 30, 52, 50, 18, 0, 0, 0, 0, 0, 1, 10, 42, 84, 90, 50, 14, 2, 0, 0, 0, 0

Offset: 1

Andrew Howroyd, Oct 12 2017

Compositions of length 1 are included.

See theorem 4 in Hadjicostas reference for generating function.

			Triangle begins:
  1;
  1,  0;
  1,  2,  0;
  1,  2,  0,  0;
  1,  4,  0,  0,  0;
  1,  4,  6,  2,  0,  0;
  1,  6,  6,  4,  0,  0,  0;
  1,  6, 12, 10,  0,  0,  0,  0;
  1,  8, 18, 16, 10,  2,  0,  0,  0;
  1,  8, 24, 40, 20,  6,  0,  0,  0,  0;
  ...
Case n=6:
The included compositions are:
k=1: 6;                                => T(6,1) = 1
k=2: 15, 24, 42, 51;                   => T(6,2) = 4
k=3: 123, 132, 213, 231, 312, 321;     => T(6,3) = 6
k=4: 1212, 2121;                       => T(6,4) = 2

Andrew Howroyd, Table of n, a(n) for n = 1..1275
P. Hadjicostas, Cyclic, dihedral and symmetric Carlitz compositions of a positive integer, Journal of Integer Sequences, 20 (2017), Article 17.8.5.

Row sums are in A212322.

Cf. A106351, A106369.

max = 10; gf = Sum[x^(2*j)*y^2/(1 + x^j*y), {j, 1, max}] + Sum[x^j*y/(1 + x^j*y)^2, {j, 1, max}]/(1 - Sum[ x^j*y/(1 + x^j*y), {j, 1, max}]) + O[x]^(max+1) + O[y]^(max+1) // Normal // Expand;
T[n_, k_] := SeriesCoefficient[gf, {x, 0, n}, {y, 0, k}];
Table[T[n, k], {n, 1, max}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 19 2018 *)

gf(n,y) = {my(A=sum(j=1, n, x^(2*j)*y^2/(1+x^j*y) + O(x*x^n)),
B=sum(j=1, n, x^j*y/(1+x^j*y)^2 + O(x*x^n)),
C=sum(j=1, n, x^j*y/(1+x^j*y) + O(x*x^n)));
A + B/(1-C)}
for(n=1,10,my(p=polcoeff(gf(n,y),n));for(k=1,n,print1(polcoeff(p,k),", "));print)

G.f.: (Sum_{j>=1} x^(2*j)*y^2/(1+x^j*y)) + (Sum_{j>=1} x^j*y/(1+x^j*y)^2) / (1 - Sum_{j>=1} x^j*y/(1+x^j*y)).

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

A241902 Decimal expansion of a constant related to Carlitz compositions (A003242).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

A292906 Number of dihedral Carlitz compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A293595 Triangle read by rows: T(n,k) = number of compositions of n into k parts such that no two cyclically adjacent parts are equal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula