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,5

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) :

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

Links

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

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

Example

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;
  ...

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 *)

Crossrefs

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

Main diagonal gives A001761.

Cf. A253180, A255982, A258427, A290605.

Sequence in context: A269011 A274086 A255982 * A323099 A002652 A202541

Adjacent sequences: A256058 A256059 A256060 * A256062 A256063 A256064

Keyword

nonn,tabl

Author

Alois P. Heinz, Mar 13 2015

Status

approved