A168396 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.

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

Offset

1,4

Comments

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

Links

Reinhard Zumkeller, Rows n=1..120 of triangle, flattened

Example

First 16 rows of triangle:
.   1:     1
.   2:     1    1
.   3:     2    1    1
.   4:     3    2    1   1
.   5:     5    4    2   1   1
.   6:     9    6    4   2   1   1
.   7:    15   11    7   4   2   1   1
.   8:    26   19   12   7   4   2   1  1
.   9:    45   33   21  13   7   4   2  1  1
.  10:    78   57   37  22  13   7   4  2  1  1
.  11:   135   99   64  39  23  13   7  4  2  1  1
.  12:   234  172  112  68  40  23  13  7  4  2  1 1
.  13:   406  298  194 119  70  41  23 13  7  4  2 1 1
.  14:   704  518  337 207 123  71  41 23 13  7  4 2 1 1
.  15:  1222  898  586 360 214 125  72 41 23 13  7 4 2 1 1
.  16:  2120 1559 1017 626 373 218 126 72 41 23 13 7 4 2 1 1

Maple

b:= proc(n, k) option remember; `if`(n=0, 1,
      add(b(n-j, j+1), j=1..min(n, k)))
    end:
T:= (n, k)-> b(n-k, k+1):
seq(seq(T(n, k), k=1..n), n=1..14); # Alois P. Heinz, Sep 19 2013

Mathematica

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

Prog

(PARI) T(n, k)=if(k>=n, k==n, sum(j=1, k+1, T(n-k, j)))
(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
(Haskell)
a168396 n k = a168396_tabl !! (n-1) !! (k-1)
a168396_row n = a168396_tabl !! (n-1)
a168396_tabl = [1] : f [[1]] where
   f xss = ys : f (ys : xss) where
     ys = (map sum $ zipWith take [2..] xss) ++ [1] -- Reinhard Zumkeller, Sep 13 2013

Crossrefs

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

Sequence in context: A318805 A175331 A098805 * A049286 A308477 A079216

Adjacent sequences: A168393 A168394 A168395 * A168397 A168398 A168399

Keyword

nonn,tabl

Author

Franklin T. Adams-Watters, Nov 24 2009

Status

approved