A106351 Triangle read by rows: T(n,k) = number of compositions of n into k parts such that no two adjacent parts are equal.

1, 1, 0, 1, 2, 0, 1, 2, 1, 0, 1, 4, 2, 0, 0, 1, 4, 7, 2, 0, 0, 1, 6, 9, 6, 1, 0, 0, 1, 6, 15, 14, 3, 0, 0, 0, 1, 8, 21, 24, 15, 2, 0, 0, 0, 1, 8, 28, 46, 30, 10, 1, 0, 0, 0, 1, 10, 35, 66, 68, 30, 4, 0, 0, 0, 0, 1, 10, 46, 100, 119, 76, 24, 2, 0, 0, 0, 0, 1, 12, 54, 138, 204, 168, 69, 14, 1, 0, 0, 0, 0

Offset: 1

Author

Christian G. Bower, Apr 29 2005

Keywords

• nonn
• tabl

Examples

			T(6,3) = 7 because the compositions of 6 into 3 parts with no adjacent equal parts are 3+2+1, 3+1+2, 2+3+1, 2+1+3, 1+3+2, 1+2+3, 1+4+1.
Triangle begins:
  1;
  1, 0;
  1, 2,  0;
  1, 2,  1,  0;
  1, 4,  2,  0,  0;
  1, 4,  7,  2,  0, 0;
  1, 6,  9,  6,  1, 0, 0;
  1, 6, 15, 14,  3, 0, 0, 0;
  1, 8, 21, 24, 15, 2, 0, 0, 0;
  ...
		

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.

Crossrefs

Row sums: A003242. Columns 3-6: A106352, A106353, A106354, A106355.

Cf. A131044 (at least two adjacent parts are equal).

T(2n,n) gives A221235.

Programs

Maple

b:= proc(n, h, t) option remember;
      if n b(n, -1, k):
seq(seq(T(n, k), k=1..n), n=1..15); # Alois P. Heinz, Oct 23 2011

Mathematica

nn=10;CoefficientList[Series[1/(1-Sum[y x^i/(1+y x^i),{i,1,nn}]),{x,0,nn}],{x,y}]//Grid (* Geoffrey Critzer, Nov 23 2013 *)

PARI

gf(n,y)={1/(1 - sum(k=1, n, (-1)^(k+1)*x^k*y^k/(1-x^k) + O(x*x^n)))}
for(n=1, 10, my(p=polcoeff(gf(n,y),n)); for(k=1, n, print1(polcoeff(p,k), ", ")); print); \\ Andrew Howroyd, Oct 12 2017

Formula

G.f.: 1/(1 - Sum_{k>0} (-1)^(k+1)*x^k*y^k/(1-x^k)).