A131044 Triangle T(n,k) read by rows: T(n,k) is the number of compositions of n into k parts such that at least two adjacent parts are equal.

1, 1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 0, 4, 4, 1, 1, 1, 3, 8, 5, 1, 1, 0, 6, 14, 14, 6, 1, 1, 1, 6, 21, 32, 21, 7, 1, 1, 0, 7, 32, 55, 54, 28, 8, 1, 1, 1, 8, 38, 96, 116, 83, 36, 9, 1, 1, 0, 10, 54, 142, 222, 206, 120, 45, 10, 1, 1, 1, 9, 65, 211, 386, 438, 328, 165, 55, 11, 1

Offset

1,9

Comments

Condition is void for compositions into 1 part (there is one such composition).

Triangle = Pascal's triangle (A007318) - A106351, except for first column.

Links

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

Example

T(5,3) = 4 because among the 6 compositions of 5 into 3 parts there are 4 with one part repeated, marked by (*) between the parts:
[ 3 1*1 ], [ 2*2 1 ], [ 1 3 1 ], [ 2 1 2 ], [ 1 2*2 ], [ 1*1 3 ].
Triangle begins:
  1;
  1, 1;
  1, 0, 1;
  1, 1, 2,  1;
  1, 0, 4,  4,  1;
  1, 1, 3,  8,  5,  1;
  1, 0, 6, 14, 14,  6, 1;
  1, 1, 6, 21, 32, 21, 7, 1;
  ...

Maple

b:= proc(n, h, t) option remember;
      if n<t then 0 elif n=0 then `if`(t=0, 1, 0)
    else add(`if`(h=j, 0, b(n-j, j, t-1)), j=1..n) fi
    end:
T:= (n, k)-> `if`(k=1, 1, binomial(n-1, k-1) -b(n, -1, k)):
seq(seq(T(n, k), k=1..n), n=1..12); # Alois P. Heinz, Feb 13 2013

Mathematica

b[n_, h_, t_] := b[n, h, t] = Which[n<t, 0, n == 0, If[t == 0, 1, 0], True, Sum[If[h == j, 0, b[n-j, j, t-1]], {j, 1, n}]]; T[n_, k_] := If[k == 1, 1, Binomial[n-1, k-1] - b[n, -1, k]]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Feb 18 2015, after Alois P. Heinz *)

Prog

(Sage)
def A131044_r(n, k):
    allowed = lambda x: len(x) <= 1 or 0 in differences(x)
    return len([c for c in Compositions(n, length=k) if allowed(c)])
# [D. S. McNeil, Jan 06 2011]

Crossrefs

Cf. A106351 (no two adjacent parts are equal).

Sequence in context: A238125 A062507 A238750 * A246027 A077875 A198237

Adjacent sequences: A131041 A131042 A131043 * A131045 A131046 A131047

Keyword

nonn,tabl

Author

Joerg Arndt, Jan 06 2011

Status

approved