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

Author

Joerg Arndt, Jan 06 2011

Keywords

• nonn
• tabl

Comments

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

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

Examples

			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;
  ...
		

Links

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

Crossrefs

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

Programs

Maple

b:= proc(n, h, t) option remember;
      if n `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[nJean-François Alcover, Feb 18 2015, after Alois P. Heinz *)

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]