login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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.
15
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,5
COMMENTS
In general, column k>0 is asymptotic to (4*k)^n / (k!*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jun 01 2015
LINKS
FORMULA
T(n,k) = A256061(n,k)/k! = Sum_{i=0..k} (-1)^i * C(k,i) * (k-i)^n * A000108(n) / A000142(n).
EXAMPLE
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;
...
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 *)
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.
Sequence in context: A277295 A254749 A129936 * A295214 A221408 A221396
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Mar 23 2015
STATUS
approved