|
%I #36 Nov 20 2018 22:46:33
%S 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,
%T 162,192,84,11,81,245,375,270,42,12,100,352,660,660,264,13,121,486,
%U 1078,1375,891,132,14,144,650,1664,2574,2288,858,15,169,847,2457,4459,5005,3003,429
%N Triangular array of a Catalan number variety: T(n,k) is the number of words consisting of n parentheses containing k well-balanced pairs.
%C 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.
%H Alois P. Heinz, <a href="/A298637/b298637.txt">Rows n = 0..200, flattened</a>
%H Toufik Mansour, Armend Sh. Shabani, <a href="https://doi.org/10.3906/mat-1803-113">Bargraphs in bargraphs</a>, Turkish Journal of Mathematics (2018) Vol. 42, Issue 5, 2763-2773.
%H Marko Riedel et al., <a href="https://math.stackexchange.com/questions/2616354/">Generalisation for Catalan number.</a>
%H Marko Riedel, <a href="/A298637/a298637.maple.txt">Maple code for A298637 including enumeration, generating function, and two closed forms.</a>
%F T(n,k) = ((n+1-2*k)^2/(n+1))*C(n+1,k) where 0 <= k <= floor(n/2).
%F 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.
%F T(2*k,k) = C(k), the k-th Catalan number.
%F T(n,0) = n+1 by construction.
%e The word ))))(()(()))((() contains five well-balanced pairs of parentheses.
%e Triangular array T(n,k) begins:
%e 1;
%e 2;
%e 3, 1;
%e 4, 4;
%e 5, 9, 2;
%e 6, 16, 10;
%e 7, 25, 27, 5;
%e 8, 36, 56, 28;
%e 9, 49, 100, 84, 14;
%e 10, 64, 162, 192, 84;
%e 11, 81, 245, 375, 270, 42;
%e 12, 100, 352, 660, 660, 264;
%p b:= proc(n, i) option remember; expand(`if`(n=0, 1,
%p `if`(i>0, x, 1)*b(n-1, max(0, i-1))+b(n-1, i+1)))
%p end:
%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
%p seq(T(n), n=0..16); # _Alois P. Heinz_, Jan 23 2018
%t 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 *)
%Y Row sums give A000079.
%Y T(2n,n) gives A000108.
%Y T(2n+1,n) gives A068875. T(n,1) gives A000290. T(2n,2) gives A280089.
%Y Cf. A007318, A061554.
%K nonn,tabf
%O 0,2
%A _Marko Riedel_, Jan 23 2018
|
