login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A298637 Triangular array of a Catalan number variety: T(n,k) is the number of words consisting of n parentheses containing k well-balanced 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 well-balanced 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, 2763-2773.
FORMULA
T(n,k) = ((n+1-2*k)^2/(n+1))*C(n+1,k) where 0 <= k <= floor(n/2).
Bivariate o.g.f. is C(u*z^2)/(1-z*C(u*z^2))^2 with u counting pairs of parentheses and z counting total word length where C(z) = (1-sqrt(1-4*z))/(2*z) is the o.g.f. of the Catalan numbers.
T(2*k,k) = C(k), the k-th Catalan number.
T(n,0) = n+1 by construction.
EXAMPLE
The word ))))(()(()))((() contains five well-balanced 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(n-1, max(0, i-1))+b(n-1, i+1)))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..16); # Alois P. Heinz, Jan 23 2018
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
Row sums give A000079.
T(2n,n) gives A000108.
T(2n+1,n) gives A068875. T(n,1) gives A000290. T(2n,2) gives A280089.
Sequence in context: A354265 A324336 A324752 * A034867 A323893 A329721
KEYWORD
nonn,tabf
AUTHOR
Marko Riedel, Jan 23 2018
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 18 16:22 EDT 2024. Contains 371780 sequences. (Running on oeis4.)