A241902 -id:A241902 - cp's OEIS frontend

A003242 Number of compositions of n such that no two adjacent parts are equal (these are sometimes called Carlitz compositions).

1, 1, 1, 3, 4, 7, 14, 23, 39, 71, 124, 214, 378, 661, 1152, 2024, 3542, 6189, 10843, 18978, 33202, 58130, 101742, 178045, 311648, 545470, 954658, 1670919, 2924536, 5118559, 8958772, 15680073, 27443763, 48033284, 84069952, 147142465, 257534928, 450748483, 788918212

Offset: 0

E. Rodney Canfield

			From _Joerg Arndt_, Oct 27 2012:  (Start)
The 23 such compositions of n=7 are
[ 1]  1 2 1 2 1
[ 2]  1 2 1 3
[ 3]  1 2 3 1
[ 4]  1 2 4
[ 5]  1 3 1 2
[ 6]  1 3 2 1
[ 7]  1 4 2
[ 8]  1 5 1
[ 9]  1 6
[10]  2 1 3 1
[11]  2 1 4
[12]  2 3 2
[13]  2 4 1
[14]  2 5
[15]  3 1 2 1
[16]  3 1 3
[17]  3 4
[18]  4 1 2
[19]  4 2 1
[20]  4 3
[21]  5 2
[22]  6 1
[23]  7
(End)

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 191.

Alois P. Heinz, Table of n, a(n) for n = 0..4100 (first 501 terms from Christian G. Bower)
L. Carlitz, Restricted Compositions, Fibonacci Quarterly, 14 (1976) 254-264.
Sylvie Corteel, Paweł Hitczenko, Generalizations of Carlitz Compositions, Journal of Integer Sequences, Vol. 10 (2007), Article 07.8.8
Steven R. Finch, Errata and Addenda to Mathematical Constants, arXiv:2001.00578 [math.HO], 2020-2022, p. 42 and 117.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 201
F. Harary & R. W. Robinson, The number of achiral trees, Jnl. Reine Angewandte Mathematik 278 (1975), 322-335. (Annotated scanned copy)
A. Knopfmacher and H. Prodinger, On Carlitz compositions, European Journal of Combinatorics, Vol. 19, 1998, pp. 579-589.
E. Munarini, M. Poneti, S. Rinaldi, Matrix compositions, JIS 12 (2009) 09.4.8, Chapter 8.

Cf. A106351, A114900, A114902.
Cf. A096568, A011782, A106356. - Franklin T. Adams-Watters, May 27 2010
Row sums of A232396, A241701.
Cf. A241902.
Column k=1 of A261960.
Cf. A048272.
Compositions with adjacent parts coprime are A167606.
The complement is counted by A261983.
Cf. A000740, A005251, A032020, A114901, A178470, A261041, A274174, A329738, A329863.

a003242 n = a003242_list !! n
a003242_list = 1 : f [1] where
   f xs = y : f (y : xs) where
          y = sum $ zipWith (*) xs a048272_list
-- Reinhard Zumkeller, Nov 04 2015

b:= proc(n, i) option remember; `if`(n=0, 1,
      add(`if`(j=i, 0, b(n-j, `if`(j<=n-j, j, 0))), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Mar 27 2014

A048272[n_] := Total[If[OddQ[#], 1, -1]& /@ Divisors[n]]; a[n_] := a[n] = Sum[A048272[k]*a[n-k], {k, 1, n}]; a[0] = 1; Table[a[n], {n, 0, 38}](* Jean-François Alcover, Nov 25 2011, after Vladeta Jovovic *)
nmax = 50; CoefficientList[Series[1/(1 - Sum[x^k/(1 + x^k), {k, 1, nmax}]), {x, 0, nmax}], x] (* Vaclav Kotesovec, Jul 07 2020 *)
Table[Count[Flatten[Permutations/@IntegerPartitions[n],1],?(FreeQ[Differences[#],0]&)],{n,0,20}] (* The program generates the first 21 terms of the sequence. *) (* _Harvey P. Dale, Nov 23 2024 *)

N = 66;  x = 'x + O('x^N);  p=2;
gf = 1/(1-sum(k=1,N, x^k/(1-x^k)-p*x^(k*p)/(1-x^(k*p))));
Vec(gf)  /* Joerg Arndt, Apr 28 2013 */

a(n) = Sum_{k=1..n} A048272(k)*a(n-k), n>1, a(0)=1. - Vladeta Jovovic, Feb 05 2002
G.f.: 1/(1 - Sum_{k>0} x^k/(1+x^k)).
a(n) ~ c r^n where c is approximately 0.456387 and r is approximately 1.750243. (Formula from Knopfmacher and Prodinger reference.) - Franklin T. Adams-Watters, May 27 2010. With better precision: r = 1.7502412917183090312497386246398158787782058181381590561316586... (see A241902), c = 0.4563634740588133495321001859298593318027266156100046548066205... - Vaclav Kotesovec, Apr 30 2014
G.f. is the special case p=2 of 1/(1 - Sum_{k>0} (z^k/(1-z^k) - p*z^(k*p)/(1-z^(k*p)))), see A129922. - Joerg Arndt, Apr 28 2013
G.f.: 1/(1 - x * (d/dx) log(Product_{k>=1} (1 + x^k)^(1/k))). - Ilya Gutkovskiy, Oct 18 2018
Moebius transform of A329738. - Gus Wiseman, Nov 27 2019
For n>=2, a(n) = A128695(n) - A091616(n). - Vaclav Kotesovec, Jul 07 2020

More terms from David W. Wilson

A224958 Number of compositions [p(1), p(2), ..., p(k)] of n such that p(j) != p(j-2).

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 18, 29, 53, 91, 162, 277, 495, 855, 1508, 2625, 4618, 8049, 14130, 24675, 43255, 75621, 132475, 231697, 405751, 709887, 1242824, 2174763, 3806989, 6662291, 11661737, 20409409, 35723307, 62521919, 109431810, 191527623, 335225350, 586717615

Offset: 0

Joerg Arndt, Apr 21 2013

nonn

			The a(6) = 18 such compositions of 6 are
01:  [ 1 1 2 2 ]
02:  [ 1 1 4 ]
03:  [ 1 2 2 1 ]
04:  [ 1 2 3 ]
05:  [ 1 3 2 ]
06:  [ 1 5 ]
07:  [ 2 1 1 2 ]
08:  [ 2 1 3 ]
09:  [ 2 2 1 1 ]
10:  [ 2 3 1 ]
11:  [ 2 4 ]
12:  [ 3 1 2 ]
13:  [ 3 2 1 ]
14:  [ 3 3 ]
15:  [ 4 1 1 ]
16:  [ 4 2 ]
17:  [ 5 1 ]
18:  [ 6 ]

Alois P. Heinz, Table of n, a(n) for n = 0..500

Cf. A000726 (partitions such that p(j) != p(j-2)), A003242, A241902.

b:= proc(n, i, j) option remember; `if`(n=0, 1, add(`if`(k=j, 0,
      b(n-k, `if`(n-k b(n, 0, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, May 02 2013

b[n_, i_, j_] := b[n, i, j] = If[n==0, 1, Sum[If[k==j, 0, b[n-k, If[n-k < k, 0, k], If[n-k < i, 0, i]]], {k, 1, n}]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Apr 08 2015, after Alois P. Heinz *)

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

A106369 Number of circular compositions of n such that no two adjacent parts are equal.

Original entry on oeis.org

1, 1, 2, 2, 3, 6, 7, 11, 18, 29, 42, 73, 111, 183, 299, 491, 796, 1333, 2188, 3652, 6073, 10155, 16959, 28500, 47813, 80508, 135621, 228967, 386749, 654535, 1108353, 1879478, 3189495, 5418556, 9212099, 15676275, 26694509, 45493327, 77580915

Offset: 1

Christian G. Bower, Apr 29 2005

nonn

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. - Petros Hadjicostas, Oct 15 2017

			a(6) = 6 because the 6 circular compositions of 6: 6, 5+1, 4+2, 3+2+1, 3+1+2, 2+1+2+1.

Vaclav Kotesovec, Table of n, a(n) for n = 1..1000
P. Hadjicostas, Cyclic, dihedral and symmetric Carlitz compositions of a positive integer, Journal of Integer Sequences, 20 (2017), Article 17.8.5.
Petros Hadjicostas, Proof of an explicit formula for Bower's CycleBG transform
Index entries for sequences related to necklaces

Cf. A000031, A008965, A212322, A292906.

nmax = 40; Rest[CoefficientList[Series[x/(1-x) - Sum[EulerPhi[s]/s*(Log[1 - Sum[x^(s*n)/(1 + x^(s*n)), {n, 1, nmax}]] + Sum[Log[1 + x^(s*n)], {n, 1, nmax}]), {s, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Sep 06 2017, after Petros Hadjicostas *)

CycleBG transform of (1, 1, 1, 1, ...).
CycleBG transform T(A) = invMOEBIUS(invEULER(Carlitz(A)) + A(x^2) - A) + A.
Carlitz transform T(A(x)) has g.f. 1/(1 - Sum_{k>0} (-1)^(k+1)*A(x^k)).
G.f.: x/(1-x) - Sum_{s>=1} (phi(s)/s)*f(x^s), where f(x) = log(1 - Sum_{n>=1} x^n/(1 + x^n)) + Sum_{n>=1} log(1 + x^n) and phi(s)=A000010 is Euler's totient function. - Petros Hadjicostas, Sep 06 2017
Conjecture: a(n) ~ A241902^n / n. - Vaclav Kotesovec, Sep 06 2017
General formula for the CycleBG transform: T(A)(x) = A(x) - Sum_{k>=0} A(x^(2k+1)) + Sum_{k>=1} (phi(k)/k)*log(Carlitz(A)(x^k)). For a proof, see the links above. (For this sequence, A(x) = x/(1-x).) - Petros Hadjicostas, Oct 08 2017
G.f.: -Sum_{s>=1} x^(2s+1)/(1-x^(2s+1)) - Sum_{s>=1} (phi(s)/s)*g(x^s), where g(x) = log(1 + Sum_{n>=1} (-x)^n/(1 - x^n)). (This formula can be proved from the general formula for the CycleBG transform given above.) - Petros Hadjicostas, Oct 10 2017

Name clarified by Andrew Howroyd, Oct 12 2017

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

A106357 Number of compositions of n with exactly 1 adjacent equal pair of parts.

Original entry on oeis.org

1, 0, 3, 6, 7, 20, 42, 72, 141, 280, 516, 976, 1853, 3420, 6361, 11844, 21819, 40192, 73942, 135452, 247828, 452776, 825252, 1501998, 2730159, 4954890, 8981360, 16261568, 29408708, 53130154, 95894384, 172917788, 311538169, 560831286

Offset: 2

Christian G. Bower, Apr 29 2005

nonn

Alois P. Heinz, Table of n, a(n) for n = 2..1000
A. Knopfmacher and H. Prodinger, On Carlitz compositions, European Journal of Combinatorics, Vol. 19, 1998, pp. 579-589.

Column 1 of A106356. Cf. A003242.

Cf. A241902.

b:= proc(n, v) option remember; `if`(n=0, [1, 0],
      add((p-> `if`(i=v, [0, p[1]], p))(b(n-i, i)), i=1..n))
    end:
a:= n-> b(n, 0)[2]:
seq(a(n), n=2..45);  # Alois P. Heinz, May 09 2014

b[n_, v_] := b[n, v] = If[n == 0, {1, 0}, Sum[Function[p, If[i == v, {0, p[[1]]}, p]][b[n - i, i]], {i, 1, n}]];
a[n_] := b[n, 0][[2]];
a /@ Range[2, 45] (* Jean-François Alcover, Nov 02 2020, after Alois P. Heinz *)

C_x(N)={my(g=1/(1 - sum(k=1, N, x^k/(1+x^k))));g}
A_x(N)={my(x='x+O('x^N), h=sum(i=1,N,(C_x(N)*x^(2*i))/(1+x^i)^2 )/(1-sum(i=1,N,(x^i)/(1+x^i)))); Vec(h)}
A_x(40) \\ John Tyler Rascoe, May 16 2024

a(n) ~ c * d^n * n, where d = A241902 = 1.750241291718309031249738624639..., c = 0.04826600476992825168367... . - Vaclav Kotesovec, Sep 05 2014

G.f.: (Sum_{i>0} C(x)*x^(2*i)/(1+x^i)^2)/(1 - Sum_{i>0} x^i/(1+x^i)) where C(x) is the g.f. for A003242. - John Tyler Rascoe, May 16 2024

Replaced broken link, Vaclav Kotesovec, May 01 2014

A304778 Number of Carlitz compositions c of n such that the sequence of ascents and descents of c forms a Dyck path.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 6, 9, 15, 23, 38, 62, 100, 163, 267, 441, 725, 1198, 1986, 3291, 5472, 9116, 15204, 25399, 42494, 71183, 119396, 200507, 337090, 567318, 955749, 1611672, 2720212, 4595198, 7768975, 13145109, 22258264, 37716358, 63953853, 108515011

Offset: 0

Alois P. Heinz, May 18 2018

nonn

			a(6) = 4: 132, 141, 231, 6.
a(7) = 6: 12121, 142, 151, 232, 241, 7.
a(8) = 9: 12131, 13121, 143, 152, 161, 242, 251, 341, 8.
a(9) = 15: 12132, 12141, 12321, 13131, 14121, 153, 162, 171, 23121, 243, 252, 261, 342, 351, 9.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, Counting lattice paths

Cf. A003242, A303287, A304777.

b:= proc(n, l, c) option remember; `if`(c<0 and l>0, 0,
      `if`(n=0, `if`(l<0 or c=0, 1, 0), add(`if`(i=l, 0,
       b(n-i, i, c+`if`(i>l, 1, -1))), i=1..n)))
    end:
a:= n-> b(n, -1$2):
seq(a(n), n=0..50);

b[n_, l_, c_] := b[n, l, c] = If[c<0 && l>0, 0, If[n==0, If[l<0 || c==0, 1, 0], Sum[If[i==l, 0, b[n-i, i, c + If[i>l, 1, -1]]], {i, 1, n}]]];
a[n_] := b[n, -1, -1];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, May 31 2018, from Maple *)

a(n) ~ c * d^n / n^(3/2), where d = A241902 = 1.7502412917183090312497386246... and c = 7.0142545527132612683043468956... - Vaclav Kotesovec, May 22 2018

A106358 Number of compositions of n with exactly 2 adjacent equal parts (2 pairs or 1 triple.).

Original entry on oeis.org

1, 0, 2, 8, 10, 22, 58, 112, 219, 466, 920, 1787, 3600, 7025, 13532, 26315, 50625, 96775, 185000, 351714, 665942, 1258649, 2371219, 4454004, 8348735, 15612146, 29128863, 54245790, 100828939, 187074952, 346527510, 640878692, 1183480187

Offset: 3

Christian G. Bower, Apr 29 2005

nonn

Alois P. Heinz, Table of n, a(n) for n = 3..1000
A. Knopfmacher and H. Prodinger, On Carlitz compositions, European Journal of Combinatorics, Vol. 19, 1998, pp. 579-589.

Column 2 of A106356. Cf. A003242.

Cf. A241902.

b:= proc(n, v) option remember; `if`(n=0, [1, 0$2], add((
      p->`if`(i=v, [0, p[1..2][]], p))(b(n-i, i)), i=1..n))
    end:
a:= n-> b(n, 0)[3]:
seq(a(n), n=3..45);  # Alois P. Heinz, Jun 24 2014

b[n_, v_] := b[n, v] = If[n==0, {1, 0, 0}, Sum[If[i==v, Prepend[#[[1;;2]], 0], #]&[b[n-i, i]], {i, 1, n}]];
a[n_] := b[n, 0][[3]];
a /@ Range[3, 45] (* Jean-François Alcover, Nov 18 2020, after Alois P. Heinz *)

a(n) ~ c * d^n * n^2, where d = 1.7502412917183090312497386246... (see A241902), c = 0.0025523594118210599072896951... . - Vaclav Kotesovec, Aug 25 2014

A246952 Decimal expansion of sigma, a constant appearing in the asymptotic expression of the number a(n) of Carlitz compositions of size n.

Original entry on oeis.org

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

Offset: 0

Jean-François Alcover, Sep 08 2014

			0.571349793158087643112217904891974600336176224937534145...

Steven R. Finch, Errata and Addenda to Mathematical Constants, p. 38.
A. Knopfmacher and H. Prodinger, On Carlitz compositions, European Journal of Combinatorics, Vol. 19, 1998, pp. 579-589.

Cf. A003242, A241902.

digits = 103; F[x_?NumericQ] := NSum[(-1)^(j - 1)*(x^j/(1 - x^j)), {j, 1, Infinity}, WorkingPrecision -> digits+5]; sigma = x /. FindRoot[F[x] == 1, {x, 2/5, 1/2}, WorkingPrecision -> digits+5]; RealDigits[sigma, 10, digits] // First

Sigma is the unique solution of the equation F(x)=1, 0 <= x <= 1, where F(x) = sum_{j>=1} (-1)^(j - 1)*(x^j/(1 - x^j)).

a(n) ~ 1/(sigma*F'(sigma))*(1/sigma)^n = c*r^n, where c = 0.456387... and r = A241902 = 1.750243...

cp's OEIS Frontend

A003242 Number of compositions of n such that no two adjacent parts are equal (these are sometimes called Carlitz compositions).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A224958 Number of compositions [p(1), p(2), ..., p(k)] of n such that p(j) != p(j-2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A106369 Number of circular compositions of n such that no two adjacent parts are equal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

A106357 Number of compositions of n with exactly 1 adjacent equal pair of parts.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A304778 Number of Carlitz compositions c of n such that the sequence of ascents and descents of c forms a Dyck path.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A106358 Number of compositions of n with exactly 2 adjacent equal parts (2 pairs or 1 triple.).

Views

Author