

A298637


Triangular array of a Catalan number variety: T(n,k) is the number of words consisting of n parentheses containing k wellbalanced pairs.


1



1, 2, 3, 1, 4, 4, 5, 9, 2, 6, 16, 10, 7, 25, 27, 5, 8, 36, 56, 28, 9, 49, 100, 84, 14, 10, 64, 162, 192, 84, 11, 81, 245, 375, 270, 42, 12, 100, 352, 660, 660, 264, 13, 121, 486, 1078, 1375, 891, 132, 14, 144, 650, 1664, 2574, 2288, 858, 15, 169, 847, 2457, 4459, 5005, 3003, 429
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

A wellbalanced run in a word of parentheses is a maximal run where every initial segment of the run has at least as many left parentheses as right ones and the number of open parentheses is the same as that of closed ones. The variable k in the sequence definition is the sum of the count of balanced pairs in all maximal runs in the word and n is the length of the word. Runs are maximal substrings counted by ordinary Catalan numbers.


LINKS

Toufik Mansour, Armend Sh. Shabani, Bargraphs in bargraphs, Turkish Journal of Mathematics (2018) Vol. 42, Issue 5, 27632773.


FORMULA

T(n,k) = ((n+12*k)^2/(n+1))*C(n+1,k) where 0 <= k <= floor(n/2).
Bivariate o.g.f. is C(u*z^2)/(1z*C(u*z^2))^2 with u counting pairs of parentheses and z counting total word length where C(z) = (1sqrt(14*z))/(2*z) is the o.g.f. of the Catalan numbers.
T(2*k,k) = C(k), the kth Catalan number.
T(n,0) = n+1 by construction.


EXAMPLE

The word ))))(()(()))((() contains five wellbalanced pairs of parentheses.
Triangular array T(n,k) begins:
1;
2;
3, 1;
4, 4;
5, 9, 2;
6, 16, 10;
7, 25, 27, 5;
8, 36, 56, 28;
9, 49, 100, 84, 14;
10, 64, 162, 192, 84;
11, 81, 245, 375, 270, 42;
12, 100, 352, 660, 660, 264;


MAPLE

b:= proc(n, i) option remember; expand(`if`(n=0, 1,
`if`(i>0, x, 1)*b(n1, max(0, i1))+b(n1, i+1)))
end:
T:= n> (p> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):


MATHEMATICA

Table[((n + 1  2 k)^2/(n + 1)) Binomial[n + 1, k], {n, 0, 17}, {k, 0, Floor[n/2]}] // Flatten (* Michael De Vlieger, Jan 23 2018 *)


CROSSREFS



KEYWORD

nonn,tabf


AUTHOR



STATUS

approved



