A241701 -id:A241701 - 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

A129715 Number of runs in all Fibonacci binary words of length n. A Fibonacci binary word is a binary word having no 00 subword. A run is a maximal sequence of consecutive identical letters.

Original entry on oeis.org

0, 2, 5, 11, 22, 43, 81, 150, 273, 491, 874, 1543, 2705, 4714, 8173, 14107, 24254, 41555, 70977, 120894, 205401, 348187, 589010, 994511, 1676257, 2820818, 4739861, 7953515, 13328998, 22310971, 37304049, 62307558, 103968225, 173324939

Offset: 0

Emeric Deutsch, May 12 2007

nonn

a(n) = Sum(k*A129714(n,k), k=0..n).

a(n) = A241701(3n+1,n) for n>0. - Alois P. Heinz, Apr 27 2014

			a(3)=11 because in the Fibonacci binary words 011, 111, 101, 010 and 110 we have a total of 2+1+3+3+2=11 runs.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
W. Kuszmaul, Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations, arXiv preprint arXiv:1509.08216, 2015
Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Cf. A129714.

with(combinat): a[0]:=0: a[1]:=2: a[2]:=5: for n from 3 to 40 do a[n]:=a[n-1]+a[n-2]+2*fibonacci(n) od: seq(a[n],n=0..40);

CoefficientList[Series[x (2 + x - x^2 - x^3)/(1 - x - x^2)^2, {x, 0, 30}], x] (* Vincenzo Librandi, Apr 28 2014 *)
LinearRecurrence[{2,1,-2,-1},{0,2,5,11,22},40] (* Harvey P. Dale, Nov 09 2022 *)

G.f.: z(2+z-z^2-z^3)/(1-z-z^2)^2. Rec. rel.: a(n)=a(n-1)+a(n-2)+2F(n) for n>=3, where F(n) is a Fibonacci number (F(0)=0,F(1)=1).

A241691 Number of Carlitz compositions of n with exactly one descent.

Original entry on oeis.org

1, 2, 4, 8, 13, 21, 33, 50, 73, 106, 150, 209, 289, 393, 529, 707, 935, 1227, 1601, 2072, 2666, 3413, 4344, 5501, 6937, 8707, 10883, 13554, 16815, 20787, 25617, 31465, 38532, 47056, 57302, 69596, 84320, 101907, 122875, 147833, 177471, 212608, 254201, 303335

Offset: 3

Alois P. Heinz, Apr 27 2014

nonn

No two adjacent parts of a Carlitz composition are equal.

			a(3) = 1: [2,1].
a(4) = 2: [3,1], [1,2,1].
a(5) = 4: [4,1], [3,2], [2,1,2], [1,3,1].
a(6) = 8: [4,2], [5,1], [3,1,2], [1,3,2], [1,4,1], [2,3,1], [2,1,3], [1,2,1,2].
a(7) = 13: [4,3], [6,1], [5,2], [2,1,4], [4,1,2], [1,4,2], [2,3,2], [3,1,3], [1,5,1], [2,4,1], [1,2,3,1], [1,3,1,2], [1,2,1,3].

Alois P. Heinz, Table of n, a(n) for n = 3..1000

Column k=1 of A241701.

b:= proc(n, i) option remember; `if`(n=0, 1,
       convert(series(add(`if`(i=j, 0, b(n-j, j)*
      `if`(j coeff(b(n, 0), x, 1):
seq(a(n), n=3..50);

A241692 Number of Carlitz compositions of n with exactly two descents.

Original entry on oeis.org

2, 5, 12, 27, 53, 98, 174, 296, 486, 781, 1222, 1874, 2827, 4195, 6138, 8873, 12675, 17918, 25095, 34832, 47954, 65529, 88911, 119842, 160552, 213841, 283266, 373318, 489601, 639149, 830750, 1075292, 1386313, 1780572, 2278703, 2906137, 3694123, 4680892

Offset: 6

Alois P. Heinz, Apr 27 2014

nonn

No two adjacent parts of a Carlitz composition are equal.

Alois P. Heinz, Table of n, a(n) for n = 6..1000

Column k=2 of A241701.

b:= proc(n, i) option remember; `if`(n=0, 1,
       convert(series(add(`if`(i=j, 0, b(n-j, j)*
      `if`(j coeff(b(n, 0), x, 2):
seq(a(n), n=6..50);

A241693 Number of Carlitz compositions of n with exactly three descents.

Original entry on oeis.org

3, 11, 31, 78, 175, 363, 715, 1342, 2421, 4237, 7208, 11971, 19473, 31083, 48787, 75437, 115046, 173263, 257972, 380039, 554400, 801452, 1148805, 1633699, 2306108, 3232635, 4501745, 6230400, 8572442, 11729536, 15965001, 21621202, 29141879, 39100192, 52233835

Offset: 9

Alois P. Heinz, Apr 27 2014

nonn

No two adjacent parts of a Carlitz composition are equal.

Alois P. Heinz, Table of n, a(n) for n = 9..1000

Column k=3 of A241701.

b:= proc(n, i) option remember; `if`(n=0, 1,
       convert(series(add(`if`(i=j, 0, b(n-j, j)*
      `if`(j coeff(b(n, 0), x, 3):
seq(a(n), n=9..50);

A241694 Number of Carlitz compositions of n with exactly four descents.

Original entry on oeis.org

5, 22, 72, 204, 510, 1168, 2516, 5140, 10054, 18976, 34707, 61776, 107374, 182697, 304982, 500455, 808462, 1287499, 2023697, 3142604, 4825797, 7333862, 11037829, 16462497, 24345385, 35716339, 52005295, 75186849, 107973181, 154071381, 218524581, 308162131

Offset: 12

Alois P. Heinz, Apr 27 2014

nonn

No two adjacent parts of a Carlitz composition are equal.

Alois P. Heinz, Table of n, a(n) for n = 12..1000

Column k=4 of A241701.

b:= proc(n, i) option remember; `if`(n=0, 1,
       convert(series(add(`if`(i=j, 0, b(n-j, j)*
      `if`(j coeff(b(n, 0), x, 4):
seq(a(n), n=12..50);

A241695 Number of Carlitz compositions of n with exactly five descents.

Original entry on oeis.org

8, 43, 159, 497, 1365, 3412, 7959, 17529, 36820, 74341, 145037, 274632, 506546, 912668, 1610174, 2787338, 4742439, 7942378, 13109810, 21351242, 34344574, 54611144, 85907033, 133783286, 206382165, 315561476, 478474684, 719778651, 1074701635, 1593288000

Offset: 15

Alois P. Heinz, Apr 27 2014

nonn

No two adjacent parts of a Carlitz composition are equal.

Alois P. Heinz, Table of n, a(n) for n = 15..1000

Column k=5 of A241701.

b:= proc(n, i) option remember; `if`(n=0, 1,
       convert(series(add(`if`(i=j, 0, b(n-j, j)*
      `if`(j coeff(b(n, 0), x, 5):
seq(a(n), n=15..50);

A241696 Number of Carlitz compositions of n with exactly six descents.

Original entry on oeis.org

13, 81, 336, 1151, 3437, 9286, 23271, 54846, 122857, 263680, 545412, 1092394, 2126688, 4036767, 7490050, 13614573, 24287970, 42592752, 73525406, 125089010, 209962350, 348026885, 570159824, 923885796, 1481735623, 2353522164, 3704254256, 5780115565, 8945915366

Offset: 18

Alois P. Heinz, Apr 27 2014

nonn

No two adjacent parts of a Carlitz composition are equal.

Alois P. Heinz, Table of n, a(n) for n = 18..1000

Column k=6 of A241701.

b:= proc(n, i) option remember; `if`(n=0, 1,
       convert(series(add(`if`(i=j, 0, b(n-j, j)*
      `if`(j coeff(b(n, 0), x, 6):
seq(a(n), n=18..50);

A241697 Number of Carlitz compositions of n with exactly seven descents.

Original entry on oeis.org

21, 150, 688, 2561, 8253, 23930, 64030, 160539, 381379, 865676, 1889308, 3984311, 8151834, 16234161, 31554397, 59999259, 111824744, 204629354, 368190175, 652238928, 1138836325, 1961870558, 3337496363, 5611246209, 9330350788, 15353900381, 25019429935

Offset: 21

Alois P. Heinz, Apr 27 2014

nonn

No two adjacent parts of a Carlitz composition are equal.

Alois P. Heinz, Table of n, a(n) for n = 21..1000

Column k=7 of A241701.

b:= proc(n, i) option remember; `if`(n=0, 1,
       convert(series(add(`if`(i=j, 0, b(n-j, j)*
      `if`(j coeff(b(n, 0), x, 7):
seq(a(n), n=21..50);

A241698 Number of Carlitz compositions of n with exactly eight descents.

Original entry on oeis.org

34, 273, 1374, 5523, 19085, 59043, 167822, 445485, 1117320, 2671007, 6126303, 13552203, 29036088, 60461206, 122706950, 243312768, 472343731, 899329583, 1681962056, 3094108766, 5605224314, 10010276920, 17640174861, 30699341690, 52802429497, 89820432080

Offset: 24

Alois P. Heinz, Apr 27 2014

nonn

No two adjacent parts of a Carlitz composition are equal.

Alois P. Heinz, Table of n, a(n) for n = 24..1000

Column k=8 of A241701.

b:= proc(n, i) option remember; `if`(n=0, 1,
       convert(series(add(`if`(i=j, 0, b(n-j, j)*
      `if`(j coeff(b(n, 0), x, 8):
seq(a(n), n=24..50);

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

A129715 Number of runs in all Fibonacci binary words of length n. A Fibonacci binary word is a binary word having no 00 subword. A run is a maximal sequence of consecutive identical letters.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A241691 Number of Carlitz compositions of n with exactly one descent.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A241692 Number of Carlitz compositions of n with exactly two descents.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A241693 Number of Carlitz compositions of n with exactly three descents.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A241694 Number of Carlitz compositions of n with exactly four descents.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A241695 Number of Carlitz compositions of n with exactly five descents.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A241696 Number of Carlitz compositions of n with exactly six descents.

Views

Author

Keywords

Comments

Links