A256061 Number T(n,k) of 2n-length strings of balanced parentheses of exactly k different types; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 2, 4, 0, 5, 30, 30, 0, 14, 196, 504, 336, 0, 42, 1260, 6300, 10080, 5040, 0, 132, 8184, 71280, 205920, 237600, 95040, 0, 429, 54054, 774774, 3603600, 7207200, 6486480, 2162160, 0, 1430, 363220, 8288280, 58378320, 180180000, 273873600, 201801600, 57657600

Offset: 0

Author

Alois P. Heinz, Mar 13 2015

Keywords

• nonn
• tabl

Comments

Also number of binary trees with n inner nodes of exactly k different dimensions. T(2,2) = 4:

: balanced parentheses : ([]) : [()] : ()[] : []() :

:----------------------:-------:-------:-------:-------:

: trees : (1) : [2] : (1) : [2] :

: : / \ : / \ : / \ : / \ :

: : [2] : (1) : [2] : (1) :

: : / \ : / \ : / \ : / \ :

Examples

			A(3,2) = 30: (())[], (()[]), (([])), ()()[], ()([]), ()[()], ()[[]], ()[](), ()[][], ([()]), ([[]]), ([]()), ([])(), ([])[], ([][]), [(())], [()()], [()[]], [()](), [()][], [([])], [[()]], [[]()], [[]](), [](()), []()(), []()[], []([]), [][()], [][]().
Triangle T(n,k) begins:
  1;
  0,   1;
  0,   2,     4;
  0,   5,    30,     30;
  0,  14,   196,    504,     336;
  0,  42,  1260,   6300,   10080,    5040;
  0, 132,  8184,  71280,  205920,  237600,   95040;
  0, 429, 54054, 774774, 3603600, 7207200, 6486480, 2162160;
  ...
		

Links

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

Crossrefs

Columns k=0-1 give: A000007, A000108 (for n>0).

Main diagonal gives A001761.

Cf. A253180, A255982, A258427, A290605.

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*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..10);

Mathematica

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

Formula

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

T(n,k) = k! * A253180(n,k).

T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * A290605(n,k-i). - Alois P. Heinz, Oct 28 2019