A106356 Triangle T(n,k) 0<=k<n : Number of compositions of n with k adjacent equal parts.

1, 1, 1, 3, 0, 1, 4, 3, 0, 1, 7, 6, 2, 0, 1, 14, 7, 8, 2, 0, 1, 23, 20, 10, 8, 2, 0, 1, 39, 42, 22, 13, 9, 2, 0, 1, 71, 72, 58, 28, 14, 10, 2, 0, 1, 124, 141, 112, 72, 33, 16, 11, 2, 0, 1, 214, 280, 219, 150, 92, 36, 18, 12, 2, 0, 1, 378, 516, 466, 311, 189, 112, 40, 20, 13, 2, 0, 1

Offset

1,4

Comments

For n > 0, also the number of compositions of n with k + 1 maximal anti-runs (sequences without adjacent equal terms). - Gus Wiseman, Mar 23 2020

Links

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

A. Knopfmacher and H. Prodinger, On Carlitz compositions, European Journal of Combinatorics, Vol. 19, 1998, pp. 579-589.

Example

T(4,1) = 3 because the compositions of 4 with 1 adjacent equal part are 1+1+2, 2+1+1, 2+2.
Triangle begins:
1;
1,   1;
3,   0,  1;
4,   3,  0, 1;
7,   6,  2, 0, 1;
14,  7,  8, 2, 0, 1;
23, 20, 10, 8, 2, 0, 1;
From Gus Wiseman, Mar 23 2020 (Start)
Row n = 6 counts the following compositions (empty column shown by dot):
  (6)     (33)    (222)    (11112)  .  (111111)
  (15)    (114)   (1113)   (21111)
  (24)    (411)   (1122)
  (42)    (1131)  (2211)
  (51)    (1221)  (3111)
  (123)   (1311)  (11121)
  (132)   (2112)  (11211)
  (141)           (12111)
  (213)
  (231)
  (312)
  (321)
  (1212)
  (2121)
(End)

Maple

b:= proc(n, h, t) option remember;
      if n=0 then `if`(t=0, 1, 0)
    elif t<0 then 0
    else add(b(n-j, j, `if`(j=h, t-1, t)), j=1..n)
      fi
    end:
T:= (n, k)-> b(n, -1, k):
seq(seq(T(n, k), k=0..n-1), n=1..15); # Alois P. Heinz, Oct 23 2011

Mathematica

b[n_, h_, t_] := b[n, h, t] = If[n == 0, If[t == 0, 1, 0], If[t<0, 0, Sum[b[n-j, j, If [j == h, t-1, t]], {j, 1, n}]]]; T[n_, k_] := b[n, -1, k]; Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 15}] // Flatten (* Jean-François Alcover, Feb 20 2015, after Alois P. Heinz *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], n==0||Length[Split[#, #1!=#2&]]==k+1&]], {n, 0, 12}, {k, 0, n}] (* Gus Wiseman, Mar 23 2020 *)

Crossrefs

Row sums: 2^(n-1)=A000079(n-1). Columns 0-4: A003242, A106357-A106360.

The version counting adjacent unequal parts is A238279.

The k-th composition in standard-order has A124762(k) adjacent equal parts and A333382(k) adjacent unequal parts.

The k-th composition in standard-order has A124767(k) maximal runs and A333381(k) maximal anti-runs.

The version for ascents/descents is A238343.

The version for weak ascents/descents is A333213.

Cf. A064113, A066099, A233564, A333214, A333216.

Sequence in context: A256987 A048963 A119458 * A091613 A039727 A137176

Adjacent sequences: A106353 A106354 A106355 * A106357 A106358 A106359

Keyword

nonn,tabl

Author

Christian G. Bower, Apr 29 2005

Status

approved