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

A128695 Number of compositions of n with parts in N which avoid the adjacent pattern 111.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 24, 46, 89, 170, 324, 618, 1183, 2260, 4318, 8249, 15765, 30123, 57556, 109973, 210137, 401525, 767216, 1465963, 2801115, 5352275, 10226930, 19541236, 37338699, 71345449, 136324309, 260483548, 497722578, 951030367

Offset: 0

Ralf Stephan, May 08 2007

nonn

			From _Gus Wiseman_, Jul 06 2020: (Start)
The a(0) = 1 through a(5) = 13 compositions:
  ()  (1)  (2)    (3)    (4)      (5)
           (1,1)  (1,2)  (1,3)    (1,4)
                  (2,1)  (2,2)    (2,3)
                         (3,1)    (3,2)
                         (1,1,2)  (4,1)
                         (1,2,1)  (1,1,3)
                         (2,1,1)  (1,2,2)
                                  (1,3,1)
                                  (2,1,2)
                                  (2,2,1)
                                  (3,1,1)
                                  (1,1,2,1)
                                  (1,2,1,1)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
S. Heubach and T. Mansour, Enumeration of 3-letter patterns in compositions, arXiv:math/0603285 [math.CO], 2006
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Column k=0 of A232435.
Cf. A091616, A232432.
The matching version is A335464.
Contiguously (1,1)-avoiding compositions is A003242.
Contiguously (1,1)-matching compositions are A261983.
Compositions with some part > 2 are A008466
Compositions by number of adjacent equal parts are A106356.
Compositions where each part is adjacent to an equal part are A114901.
Compositions with adjacent parts coprime are A167606.
Compositions with equal parts contiguous are A274174.
Patterns contiguously matched by compositions are A335457.
Patterns contiguously matched by a given partition are A335516.
Cf. A005251, A032020, A131044, A178470, A242882, A333175, A335455.

b:= proc(n, t) option remember; `if`(n=0, 1, add(`if`(abs(t)<>j,
       b(n-j, j), `if`(t=-j, 0, b(n-j, -j))), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Nov 23 2013

nn=33;CoefficientList[Series[1/(1-Sum[(x^i+x^(2i))/(1+x^i+x^(2i)),{i,1,nn}]),{x,0,nn}],x] (* Geoffrey Critzer, Nov 23 2013 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,x_,x_,_}]&]],{n,13}] (* Gus Wiseman, Jul 06 2020 *)

G.f.: 1/(1-Sum(i>=1, x^i*(1+x^i)/(1+x^i*(1+x^i)) ) ).
a(n) ~ c * d^n, where d is the root of the equation Sum_{k>=1} 1/(d^k + 1/(1 + d^k)) = 1, d=1.9107639262818041675000243699745706859615884029961947632387839..., c=0.4993008137128378086219448701860326113802027003939127932922782... - Vaclav Kotesovec, May 01 2014, updated Jul 07 2020
For n>=2, a(n) = A091616(n) + A003242(n). - Vaclav Kotesovec, Jul 07 2020

A091613 Triangle: T(n,k) = number of compositions (ordered partitions) of n such that some part is repeated consecutively k times and no part is repeated consecutively more than k times.

Original entry on oeis.org

1, 1, 1, 3, 0, 1, 4, 3, 0, 1, 7, 6, 2, 0, 1, 14, 10, 5, 2, 0, 1, 23, 23, 11, 4, 2, 0, 1, 39, 50, 22, 10, 4, 2, 0, 1, 71, 99, 48, 22, 9, 4, 2, 0, 1, 124, 200, 105, 46, 21, 9, 4, 2, 0, 1, 214, 404, 223, 101, 46, 20, 9, 4, 2, 0, 1, 378, 805, 468, 218, 98, 45, 20, 9, 4, 2, 0, 1, 661, 1599, 979, 466, 213, 98, 44, 20, 9, 4, 2, 0, 1

Offset: 1

Christian G. Bower, Jan 23 2004

Cf. A232294 - A128695 = column 3. - Geoffrey Critzer, Mar 24 2014

			Triangle starts:
    1;
    1,   1;
    3,   0,   1;
    4,   3,   0,  1;
    7,   6,   2,  0,  1;
   14,  10,   5,  2,  0, 1;
   23,  23,  11,  4,  2, 0, 1;
   39,  50,  22, 10,  4, 2, 0, 1;
   71,  99,  48, 22,  9, 4, 2, 0, 1;
  124, 200, 105, 46, 21, 9, 4, 2, 0, 1;
  ...
In the partition 3+3+2+2+2+1+3+3+1, 2 is repeated consecutively 3 times, no part is repeated consecutively more than 3 times. (3 appears 4 times nonconsecutively.)

Alois P. Heinz, Rows n = 1..100, flattened

Row sums: A000079(n-1) (2^(n-1)).
Inverse: A091614.
Square: A091615.
Columns 1-6: A003242, A091616, A091617, A091618, A091619, A091620.
Convergent of columns: A034007.

b:= proc(n, l, k) option remember; `if`(n=0, 1, add(`if`(
      i=l, 0, add(b(n-i*j, i, k), j=1..min(k, n/i))), i=1..n))
    end:
T:= (n, k)-> b(n, 0, k)-b(n, 0, k-1):
seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Feb 08 2017

nn=15;Table[Take[Drop[Transpose[Map[PadRight[#,nn+1]&,Table[ CoefficientList[Series[1/(1-Sum[Sum[x^(j i),{i,1,k}]/Sum[x^(j i),{i,0,k}],{j,1,nn}])-1/(1-Sum[Sum[x^(j i),{i,1,k-1}]/Sum[x^(j i),{i,0,k-1}],{j,1,nn}]),{x,0,nn}],x],{k,1,nn}]]],1][[n]],n],{n,1,nn}]//Grid
(* or *)
Needs["Combinatorica`"];Table[Distribution[Map[Max,Map[Length,Map[Split, Level[Map[Permutations,IntegerPartitions[n,n]],{2}]],{2}]],Range[1,n]],{n,1,15}]//Grid (* Geoffrey Critzer, Mar 24 2014 *)
b[n_, l_, k_] := b[n, l, k] = If[n == 0, 1, Sum[If[i == l, 0,
     Sum[b[n - i*j, i, k], {j, 1, Min[k, n/i]}]], {i, 1, n}]];
T[n_, k_] := b[n, 0, k] - b[n, 0, k - 1];
Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 04 2021, after Alois P. Heinz *)

G.f. for column k: 1/(1 - Sum_{i>=1} (x^i + x^(2*i) + ... + x^(k*i))/( 1 + x^i + x^(2*i) + ... + x^(k*i)) ) - 1/(1 - Sum_{i>=1} (x^i + x^(2*i) + ... + x^((k-1)*i))/( 1 + x^i + x^(2*i) + ... + x^((k-1)*i))). - Geoffrey Critzer, Mar 24 2014

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

A128695 Number of compositions of n with parts in N which avoid the adjacent pattern 111.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A091613 Triangle: T(n,k) = number of compositions (ordered partitions) of n such that some part is repeated consecutively k times and no part is repeated consecutively more than k times.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula