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

%I #66 Oct 05 2024 14:47:38

%S 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,

%T 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,

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

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

%C Previous name was: Matrix inverse of A154990.

%C Apart from first term essentially the same as A057728.

%C A011782 appears in the columns.

%C Riordan array ((1-x)/(1-2x), x). - _Philippe Deléham_, Jan 24 2010

%C 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

%H Reinhard Zumkeller, <a href="/A155038/b155038.txt">Rows n = 1..100 of table, flattened</a>

%H Jean-Luc Baril, Javier F. González, and José L. Ramírez, <a href="http://jl.baril.u-bourgogne.fr/BGR.pdf">Last symbol distribution in pattern avoiding Catalan words</a>, Univ. Bourgogne (France, 2022).

%H Emeric Deutsch, L. Ferrari and S. Rinaldi, <a href="http://arxiv.org/abs/math/0702638">Production Matrices and Riordan arrays</a>, arXiv:math/0702638 [math.CO], 2007.

%F T(j,k) = A011782(j-k), j>=1, k>=1. - _Omar E. Pol_, Feb 14 2013

%F 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

%F G.f.: G(t,x) = (1-2*x+t*x^2)/((1-2*x)*(1-t*x)). - _Emeric Deutsch_, Jan 19 2018

%e 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

%e Table begins:

%e 1,

%e 1, 1,

%e 2, 1, 1,

%e 4, 2, 1, 1,

%e 8, 4, 2, 1, 1,

%e 16, 8, 4, 2, 1, 1,

%e 32, 16, 8, 4, 2, 1, 1,

%e 64, 32, 16, 8, 4, 2, 1, 1,

%e Production matrix begins:

%e 1, 1

%e 1, 0, 1

%e 1, 0, 0, 1

%e 1, 0, 0, 0, 1

%e 1, 0, 0, 0, 0, 1

%e 1, 0, 0, 0, 0, 0, 1

%e 1, 0, 0, 0, 0, 0, 0, 1

%e 1, 0, 0, 0, 0, 0, 0, 0, 1

%e ... - _Philippe Deléham_, Oct 04 2014

%p 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

%p 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

%t 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 *)

%o (Haskell)

%o a155038 n k = a155038_tabl !! (n-1) !! (k-1)

%o a155038_row n = a155038_tabl !! (n-1)

%o a155038_tabl = iterate

%o (\row -> zipWith (+) (row ++ [0]) (init row ++ [0,1])) [1]

%o -- _Reinhard Zumkeller_, Aug 08 2013

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

%K nonn,tabl

%O 1,4

%A _Mats Granvik_, Jan 19 2009

%E New name from _Joerg Arndt_, May 04 2014