A108891 Triangle read by rows: T(n,k) = number of Schroeder (or royal) n-paths (A006318) containing k returns to the diagonal y=x. (A northeast step lying on y=x contributes a return.)

2, 2, 4, 6, 8, 8, 22, 28, 24, 16, 90, 112, 96, 64, 32, 394, 484, 416, 288, 160, 64, 1806, 2200, 1896, 1344, 800, 384, 128, 8558, 10364, 8952, 6448, 4000, 2112, 896, 256, 41586, 50144, 43392, 31616, 20160, 11264, 5376, 2048, 512

Offset

1,1

Links

Michael De Vlieger, Table of n, a(n) for n = 1..11325 (rows n = 1..150, flattened)

Scott Balchin, Ethan MacBrough, and Kyle Ormsby, The combinatorics of N_oo operads for C_qp^n and D_p^n, arXiv:2209.06992 [math.AT], 2022.

Formula

Column k is the k-fold convolution of column 1.

T(n, k) = A104219(n-1, k-1)*2^k. - Philippe Deléham, Jul 31 2005

Triangle T(n,k), 1 <= k <= n, read by rows given by (0, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, ...) DELTA (1, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 02 2013

Example

Table begins
  n\k  1    2    3    4    5    6
  -------------------------------
  1 |  2
  2 |  2    4
  3 |  6    8    8
  4 | 22   28   24   16
  5 | 90  112   96   64   32
  6 |394  484  416  288  160   64
The paths DD, END, DEN, ENEN each have 2 returns (E=east, N=north, D=northeast); so T(2,2)=4.
From Philippe Deléham, Nov 02 2013: (Start)
Triangle (0, 1, 2, 1, 2, 1, 2, ...) DELTA (1, 0, 0, 0, ...) begins:
  1;
  0,   2;
  0,   2,   4;
  0,   6,   8,   8;
  0,  22,  28,  24,  16;
  0,  90, 112,  96,  64,  32;
  0, 394, 484, 416, 288, 160,  64; (End)

Mathematica

T[n_, k_] := (-1)^(n - k) Binomial[n, k] Hypergeometric2F1[k - n, n + 1, k + 2, 2]; Table[T[n - 1, k - 1]*2^k, {n, 9}, {k, n}] // Flatten (* Michael De Vlieger, Sep 21 2022, after Peter Luschny at A104219 *)

Crossrefs

Row sums are the large Schroeder numbers A006318. Column k=1 is twice the little Schroeder numbers A001003. The main diagonal consists of powers of 2, A000079. The first subdiagonal is A036289. The analogous Catalan triangle is A009766 (with rows reversed).

Sequence in context: A194693 A308841 A176528 * A147570 A049625 A202102

Adjacent sequences: A108888 A108889 A108890 * A108892 A108893 A108894

Keyword

nonn,tabl

Author

David Callan, Jul 25 2005

Status

approved