login
Triangle, T(n,k) = number of compositions a(1),...,a(j) of n with a(1) = k, such that a(i+1) <= a(i) + 1 for 1 <= i < j.
4

%I #14 Sep 19 2013 19:13:57

%S 1,1,1,2,1,1,3,2,1,1,5,4,2,1,1,9,6,4,2,1,1,15,11,7,4,2,1,1,26,19,12,7,

%T 4,2,1,1,45,33,21,13,7,4,2,1,1,78,57,37,22,13,7,4,2,1,1,135,99,64,39,

%U 23,13,7,4,2,1,1,234,172,112,68,40,23,13,7,4,2,1,1,406,298,194,119,70,41,23,13,7,4,2,1,1

%N Triangle, T(n,k) = number of compositions a(1),...,a(j) of n with a(1) = k, such that a(i+1) <= a(i) + 1 for 1 <= i < j.

%C The definition is a replica of the recursion formula in A005169: T(n,1) = A005169(n). Row sums, central terms and A003116 coincide: sum(T(n,k): k=1..n) = A003116(n); T(2*n-1,n) = A003116(n-1). - _Reinhard Zumkeller_, Sep 13 2013

%H Reinhard Zumkeller, <a href="/A168396/b168396.txt">Rows n=1..120 of triangle, flattened</a>

%e First 16 rows of triangle:

%e . 1: 1

%e . 2: 1 1

%e . 3: 2 1 1

%e . 4: 3 2 1 1

%e . 5: 5 4 2 1 1

%e . 6: 9 6 4 2 1 1

%e . 7: 15 11 7 4 2 1 1

%e . 8: 26 19 12 7 4 2 1 1

%e . 9: 45 33 21 13 7 4 2 1 1

%e . 10: 78 57 37 22 13 7 4 2 1 1

%e . 11: 135 99 64 39 23 13 7 4 2 1 1

%e . 12: 234 172 112 68 40 23 13 7 4 2 1 1

%e . 13: 406 298 194 119 70 41 23 13 7 4 2 1 1

%e . 14: 704 518 337 207 123 71 41 23 13 7 4 2 1 1

%e . 15: 1222 898 586 360 214 125 72 41 23 13 7 4 2 1 1

%e . 16: 2120 1559 1017 626 373 218 126 72 41 23 13 7 4 2 1 1

%p b:= proc(n, k) option remember; `if`(n=0, 1,

%p add(b(n-j, j+1), j=1..min(n, k)))

%p end:

%p T:= (n, k)-> b(n-k, k+1):

%p seq(seq(T(n, k), k=1..n), n=1..14); # _Alois P. Heinz_, Sep 19 2013

%t t[n_, k_] /; k > n = 0; t[n_, n_] = 1; t[n_, k_] := t[n, k] = Sum[ t[n-k, j], {j, 1, k+1}]; Flatten[ Table[ t[n, k], {n, 1, 13}, {k, 1, n}] ](* _Jean-François Alcover_, Feb 17 2012, after Pari *)

%o (PARI) T(n,k)=if(k>=n,k==n,sum(j=1,k+1,T(n-k,j)))

%o (PARI) Tm(n)=local(m);m=matrix(n,n);for(i=1,n,for(j=1,i,m[i,j]=if(i==j,1,sum(k=1,j+1,m[i-j,k]))));m

%o (Haskell)

%o a168396 n k = a168396_tabl !! (n-1) !! (k-1)

%o a168396_row n = a168396_tabl !! (n-1)

%o a168396_tabl = [1] : f [[1]] where

%o f xss = ys : f (ys : xss) where

%o ys = (map sum $ zipWith take [2..] xss) ++ [1] -- _Reinhard Zumkeller_, Sep 13 2013

%Y Cf. A005169 (first column), A003116 (apparently row sums).

%K nonn,tabl

%O 1,4

%A _Franklin T. Adams-Watters_, Nov 24 2009