A064094 Triangle composed of generalized Catalan numbers.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 5, 3, 1, 1, 1, 14, 13, 4, 1, 1, 1, 42, 67, 25, 5, 1, 1, 1, 132, 381, 190, 41, 6, 1, 1, 1, 429, 2307, 1606, 413, 61, 7, 1, 1, 1, 1430, 14589, 14506, 4641, 766, 85, 8, 1, 1, 1, 4862, 95235, 137089, 55797, 10746, 1279, 113, 9, 1, 1

Offset: 0

Author

Wolfdieter Lang, Sep 13 2001

Keywords

• nonn
• easy
• tabl

Comments

The column m sequence (without leading zeros and the first 1) appears in the Derrida et al. 1992 reference as Z_{N}=Y_{N}(N+1), N >=0, for alpha = m, beta = 1 (or alpha = 1, beta = m). In the Derrida et al. 1993 reference the formula in eq. (39) gives Z_{N}(alpha,beta)/(alpha*beta)^N for N>=1.

Examples

			Triangle begins:
  1;
  1,    1;
  1,    1,     1;
  1,    2,     1,     1;
  1,    5,     3,     1,    1;
  1,   14,    13,     4,    1,   1;
  1,   42,    67,    25,    5,   1,   1;
  1,  132,   381,   190,   41,   6,   1,   1;
  1,  429,  2307,  1606,  413,  61,   7,   1,   1;
  1, 1430, 14589, 14506, 4641, 766,  85,   8,   1,   1;
		

Links

• G. C. Greubel, Rows n = 0..50 of the triangle, flattened
• B. Derrida, E. Domany, and D. Mukamel, An exact solution of a one-dimensional asymmetric exclusion model with open boundaries, J. Stat. Phys. 69, 1992, 667-687; eqs. (20), (21), p. 672.
• B. Derrida, M. R. Evans, V. Hakim, and V. Pasquier, Exact solution of a 1D asymmetric exclusion model using a matrix formulation, J. Phys. A 26, 1993, 1493-1517; eq. (39), p. 1501, also appendix A1, (A12) p. 1513.

Crossrefs

Diagonals: A000012, A000012, A000027, A001844, A064096, A064302, A064303, A064304, A064305.

Columns (without leading zeros): A000012 (k=0), A000108 (k=1), A064062 (k=2), A064063 (k=3), A064087 (k=4), A064088 (k=5), A064089 (k=6), A064090 (k=7), A064091 (k=8), A064092 (k=9), A064093 (k=10).

Cf. A064095 (row sums).

Programs

Magma

function A064094(n,k)
  if k eq 0 or k eq n then return 1;
  else return (&+[(n-k-j)*Binomial(n-k-1+j, j)*k^j: j in [0..n-k-1]])/(n-k);
  end if;
end function;
[A064094(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Sep 27 2024

Mathematica

T[n_, 0] = 1; T[n_, 1] := CatalanNumber[n - 1]; T[n_, n_] = 1; T[n_, m_] := (1/(1 - m))^(n - m)*(1 - m*Sum[ CatalanNumber[k]*(m*(1 - m))^k, {k, 0, n - m - 1}]); Table[ T[n, m], {n, 0, 10}, {m, 0, n}] // Flatten (* Jean-François Alcover, Jul 05 2013 *)

SageMath

def A064094(n,k):
    if (k==0 or k==n): return 1
    else: return sum((n-k-j)*binomial(n-k-1+j,j)*k^j for j in range(n-k))//(n-k)
flatten([[A064094(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Sep 27 2024

Formula

G.f. for column m: (x^m)/(1-x*c(m*x)) = (x^m)*((m-1)+m*x*c(m*x))/(m-1+x) with the g.f. c(x) of Catalan numbers A000108.

T(n, m) = Sum_{j=0..n-m-1} (n-m-j)*binomial(n-m-1+j, j)*(m^j)/(n-m) or T(n, m) = (1/(1-m))^(n-m)*(1 - m*Sum_{j=0..n-m-1} C(j)*(m*(1-m))^j ), for n - m >= 1, T(n, n) = 1, T(n, m) = 0 if nA000108(k) (Catalan).