A155038 Triangle read by rows: T(n,k) is the number of compositions of n with first part k.

1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 8, 4, 2, 1, 1, 16, 8, 4, 2, 1, 1, 32, 16, 8, 4, 2, 1, 1, 64, 32, 16, 8, 4, 2, 1, 1, 128, 64, 32, 16, 8, 4, 2, 1, 1, 256, 128, 64, 32, 16, 8, 4, 2, 1, 1, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 1, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 1, 2048, 1024, 512

Offset

1,4

Comments

Previous name was: Matrix inverse of A154990.

Apart from first term essentially the same as A057728.

A011782 appears in the columns.

Riordan array ((1-x)/(1-2x), x). - Philippe Deléham, Jan 24 2010

Indexing the triangle from n=0 and k=0, T(n,k) is the number of binary words of length n that begin with a run of exactly k 0's. O.g.f.: 1/((1-y*x)*(1-x/(1-x))). - Geoffrey Critzer, Feb 15 2012

Links

Reinhard Zumkeller, Rows n = 1..100 of table, flattened

Jean-Luc Baril, Javier F. González, and José L. Ramírez, Last symbol distribution in pattern avoiding Catalan words, Univ. Bourgogne (France, 2022).

Emeric Deutsch, L. Ferrari and S. Rinaldi, Production Matrices and Riordan arrays, arXiv:math/0702638 [math.CO], 2007.

Formula

T(j,k) = A011782(j-k), j>=1, k>=1. - Omar E. Pol, Feb 14 2013

T(n,k) = 2^{n-k-1} if k<n; T(n,n) = 1; T(n,k) = 0 if k>n. - Emeric Deutsch, Jan 12 2018

G.f.: G(t,x) = (1-2x+tx^2)/(1-2x)(1-tx)). - Emeric Deutsch, Jan 19 2018

Example

T(5,2) = 4 because the compositions of 5 with first part 2 are: [2,3], [2,2,1], [2,1,2], and [2,1,1,1]. - Emeric Deutsch, Jan 12 2018
Table begins:
   1,
   1,  1,
   2,  1,  1,
   4,  2,  1,  1,
   8,  4,  2,  1,  1,
  16,  8,  4,  2,  1,  1,
  32, 16,  8,  4,  2,  1,  1,
  64, 32, 16,  8,  4,  2,  1,  1,
Production matrix begins:
  1, 1
  1, 0, 1
  1, 0, 0, 1
  1, 0, 0, 0, 1
  1, 0, 0, 0, 0, 1
  1, 0, 0, 0, 0, 0, 1
  1, 0, 0, 0, 0, 0, 0, 1
  1, 0, 0, 0, 0, 0, 0, 0, 1
  ... - Philippe Deléham, Oct 04 2014

Maple

T := proc(n, k) if k = n then 1 elif k < n then 2^(n-k-1) else 0 end if end proc: for n to 13 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form - Emeric Deutsch, Jan 12 2018
G:= (1-2*x+t*x^2)/((1-2*x)*(1-t*x)): Gser := simplify(series(G, x = 0, 15)): for n to 14 do P[n] := coeff(Gser, x, n) end do: for n to 14 do seq(coeff(P[n], t, j), j = 1 .. n) end do; # yields sequence in triangular form - Emeric Deutsch, Jan 19 2018

Mathematica

nn = 15; a = 1/(1 - y x); f[list_] := Select[list, # > 0 &]; Map[f, CoefficientList[Series[ a/(1 - x/(1 - x)), {x, 0, nn}], {x, y}]] // Flatten (* Geoffrey Critzer, Feb 15 2012 *)

Prog

(Haskell)
a155038 n k = a155038_tabl !! (n-1) !! (k-1)
a155038_row n = a155038_tabl !! (n-1)
a155038_tabl = iterate
   (\row -> zipWith (+) (row ++ [0]) (init row ++ [0, 1])) [1]
-- Reinhard Zumkeller, Aug 08 2013

Crossrefs

Cf. A011782, A057728, A154990, A155033, A155039.

Sequence in context: A140996 A141020 A152568 * A057728 A176463 A098050

Adjacent sequences: A155035 A155036 A155037 * A155039 A155040 A155041

Keyword

nonn,tabl

Author

Mats Granvik, Jan 19 2009

Extensions

New name from Joerg Arndt, May 04 2014

Status

approved