cp's OEIS Frontend

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.

%I A131044 #32 Oct 04 2022 08:15:44
%S A131044 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,
%T A131044 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,
%U A131044 142,222,206,120,45,10,1,1,1,9,65,211,386,438,328,165,55,11,1
%N 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.
%C A131044 Condition is void for compositions into 1 part (there is one such composition).
%C A131044 Triangle = Pascal's triangle (A007318) -  A106351, except for first column.
%H A131044 Alois P. Heinz, <a href="/A131044/b131044.txt">Rows n = 1..141, flattened</a>
%e A131044 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:
%e A131044 [ 3 1*1 ], [ 2*2 1 ], [ 1 3 1 ], [ 2 1 2 ], [ 1 2*2 ], [ 1*1 3 ].
%e A131044 Triangle begins:
%e A131044   1;
%e A131044   1, 1;
%e A131044   1, 0, 1;
%e A131044   1, 1, 2,  1;
%e A131044   1, 0, 4,  4,  1;
%e A131044   1, 1, 3,  8,  5,  1;
%e A131044   1, 0, 6, 14, 14,  6, 1;
%e A131044   1, 1, 6, 21, 32, 21, 7, 1;
%e A131044   ...
%p A131044 b:= proc(n, h, t) option remember;
%p A131044       if n<t then 0 elif n=0 then `if`(t=0, 1, 0)
%p A131044     else add(`if`(h=j, 0, b(n-j, j, t-1)), j=1..n) fi
%p A131044     end:
%p A131044 T:= (n, k)-> `if`(k=1, 1, binomial(n-1, k-1) -b(n, -1, k)):
%p A131044 seq(seq(T(n, k), k=1..n), n=1..12); # _Alois P. Heinz_, Feb 13 2013
%t A131044 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_ *)
%o A131044 (Sage)
%o A131044 def A131044_r(n,k):
%o A131044     allowed = lambda x: len(x) <= 1 or 0 in differences(x)
%o A131044     return len([c for c in Compositions(n,length=k) if allowed(c)])
%o A131044 # [_D. S. McNeil_, Jan 06 2011]
%Y A131044 Cf. A106351 (no two adjacent parts are equal).
%K A131044 nonn,tabl
%O A131044 1,9
%A A131044 _Joerg Arndt_, Jan 06 2011