login
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.
15
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
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
KEYWORD
nonn,tabl
AUTHOR
Joerg Arndt, Jan 06 2011
STATUS
approved