|
|
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.
|
|
6
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * (k-i)^n * A000108(n).
|
|
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
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|