A253180 Number T(n,k) of 2n-length strings of balanced parentheses of exactly k different types that are introduced in ascending order; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 2, 2, 0, 5, 15, 5, 0, 14, 98, 84, 14, 0, 42, 630, 1050, 420, 42, 0, 132, 4092, 11880, 8580, 1980, 132, 0, 429, 27027, 129129, 150150, 60060, 9009, 429, 0, 1430, 181610, 1381380, 2432430, 1501500, 380380, 40040, 1430, 0, 4862, 1239810, 14707550, 37777740, 33795762, 12864852, 2246244, 175032, 4862

Offset: 0

Author

Alois P. Heinz, Mar 23 2015

Keywords

• nonn
• tabl

Comments

In general, column k>0 is asymptotic to (4*k)^n / (k!*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jun 01 2015

Examples

			T(3,1) = 5: ()()(), ()(()), (())(), (()()), ((())).
T(3,2) = 15: ()()[], ()[](), ()[][], ()([]), ()[()], ()[[]], (())[], ([])(), ([])[], (()[]), ([]()), ([][]), (([])), ([()]), ([[]]).
T(3,3) = 5: ()[]{}, ()[{}], ([]){}, ([]{}), ([{}]).
Triangle T(n,k) begins:
  1;
  0,   1;
  0,   2,     2;
  0,   5,    15,      5;
  0,  14,    98,     84,     14;
  0,  42,   630,   1050,    420,    42;
  0, 132,  4092,  11880,   8580,  1980,  132;
  0, 429, 27027, 129129, 150150, 60060, 9009, 429;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened

Crossrefs

Columns k=0-10 give: A000007, A000108 (for n>0), A258390, A258391, A258392, A258393, A258394, A258395, A258396, A258397, A258398.

Main diagonal gives A000108.

First lower diagonal gives A002740(n+2).

T(2n,n) gives A258399.

Row sums give A064299.

Cf. A000142, A256061.

Programs

Maple

ctln:= proc(n) option remember; binomial(2*n, n)/(n+1) end:
A:= proc(n, k) option remember; k^n*ctln(n) end:
T:= (n, k)-> add(A(n, k-i)*(-1)^i/((k-i)!*i!), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..10);

Mathematica

A[n_, k_] := A[n, k] = k^n*CatalanNumber[n]; T[0, 0] = 1; T[n_, k_] := Sum[A[n, k-i]*(-1)^i/((k-i)!*i!), {i, 0, k}]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 11 2017, adapted from Maple *)

Formula

T(n,k) = A256061(n,k)/k! = Sum_{i=0..k} (-1)^i * C(k,i) * (k-i)^n * A000108(n) / A000142(n).