A122538 Riordan array (1, x*f(x)) where f(x)is the g.f. of A006318.

1, 0, 1, 0, 2, 1, 0, 6, 4, 1, 0, 22, 16, 6, 1, 0, 90, 68, 30, 8, 1, 0, 394, 304, 146, 48, 10, 1, 0, 1806, 1412, 714, 264, 70, 12, 1, 0, 8558, 6752, 3534, 1408, 430, 96, 14, 1, 0, 41586, 33028, 17718, 7432, 2490, 652, 126, 16, 1, 0, 206098, 164512, 89898, 39152, 14002, 4080, 938, 160, 18, 1

Offset: 0

Author

Philippe Deléham, Sep 18 2006

Keywords

• nonn
• tabl

Comments

Triangle T(n,k), 0<=k<=n, read by rows, given by [0, 2, 1, 2, 1, 2, 1, ...] DELTA [1, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938 . Inverse is Riordan array (1, x*(1-x)/(1+x)).

T(n, r) gives the number of [0,r]-covering hierarchies with n segments terminating at r (see Kreweras work). - Michel Marcus, Nov 22 2014

Examples

			Triangle begins:
  1;
  0,    1:
  0,    2,    1;
  0,    6,    4,    1;
  0,   22,   16,    6,    1;
  0,   90,   68,   30,    8,   1;
  0,  394,  304,  146,   48,  10,  1;
  0, 1806, 1412,  714,  264,  70, 12,  1;
  0, 8558, 6752, 3534, 1408, 430, 96, 14, 1;
Production matrix is:
  0...1
  0...2...1
  0...2...2...1
  0...2...2...2...1
  0...2...2...2...2...1
  0...2...2...2...2...2...1
  0...2...2...2...2...2...2...1
  0...2...2...2...2...2...2...2...1
  0...2...2...2...2...2...2...2...2...1
  ... - _Philippe Deléham_, Feb 09 2014
		

Links

• G. C. Greubel, Rows n = 0..100 of the triangle, flattened
• G. Kreweras, Sur les hiérarchies de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973), see page 15.

Crossrefs

Another version : A080247, A080245, A033877.

Columns: A000007, A006318, A006319, A006320, A006321.

Diagonals: A000012, A005843, A054000.

Sums include: A001003 (row and alternating sign), A006603 (diagonal).

Cf. A103885.

Programs

Magma

function T(n,k) // T = A122538
  if k eq 0 then return 0^n;
  elif k eq n then return 1;
  else return T(n-1,k-1) + T(n-1,k) + T(n,k+1);
  end if;
end function;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Oct 27 2024

Mathematica

T[n_, n_]= 1; T[, 0]= 0; T[n, k_]:= T[n, k]= T[n-1, k-1] + T[n-1, k] + T[n, k+1];
Table[T[n,k], {n,0,12}, {k,0,n}]//Flatten (* Jean-François Alcover, Jun 13 2019 *)

Sage

def A122538_row(n):
    @cached_function
    def prec(n, k):
        if k==n: return 1
        if k==0: return 0
        return prec(n-1,k-1)-2*sum(prec(n,k+i-1) for i in (2..n-k+1))
    return [(-1)^(n-k)*prec(n, k) for k in (0..n)]
for n in (0..12): print(A122538_row(n)) # Peter Luschny, Mar 16 2016

Formula

T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n,k+1) if k > 0, with T(n, 0) = 0^n, and T(n, n) = 1.

Sum_{k=0..n} T(n, k) = A001003(n).

From G. C. Greubel, Oct 27 2024: (Start)

T(2*n, n) = A103885(n).

Sum_{k=0..n} (-1)^k*T(n, k) = -A001003(n-1).

Sum_{k=0..floor(n/2)} T(n-k, k) = [n=0] + 0*[n=1] + A006603(n-2)*[n>1]. (End)