cp's OEIS Frontend

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.

%I A256061 #30 Sep 28 2023 05:27:17
%S A256061 1,0,1,0,2,4,0,5,30,30,0,14,196,504,336,0,42,1260,6300,10080,5040,0,
%T A256061 132,8184,71280,205920,237600,95040,0,429,54054,774774,3603600,
%U A256061 7207200,6486480,2162160,0,1430,363220,8288280,58378320,180180000,273873600,201801600,57657600
%N 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.
%C A256061 Also number of binary trees with n inner nodes of exactly k different dimensions.  T(2,2) = 4:
%C A256061 : balanced parentheses :  ([]) :  [()] : ()[]  : []()  :
%C A256061 :----------------------:-------:-------:-------:-------:
%C A256061 :                trees :   (1) :   [2] : (1)   : [2]   :
%C A256061 :                      :   / \ :   / \ : / \   : / \   :
%C A256061 :                      : [2]   : (1)   :   [2] :   (1) :
%C A256061 :                      : / \   : / \   :   / \ :   / \ :
%H A256061 Alois P. Heinz, <a href="/A256061/b256061.txt">Rows n = 0..140, flattened</a>
%F A256061 T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * (k-i)^n * A000108(n).
%F A256061 T(n,k) = k! * A253180(n,k).
%F A256061 T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * A290605(n,k-i). - _Alois P. Heinz_, Oct 28 2019
%e A256061 A(3,2) = 30: (())[], (()[]), (([])), ()()[], ()([]), ()[()], ()[[]], ()[](), ()[][], ([()]), ([[]]), ([]()), ([])(), ([])[], ([][]), [(())], [()()], [()[]], [()](), [()][], [([])], [[()]], [[]()], [[]](), [](()), []()(), []()[], []([]), [][()], [][]().
%e A256061 Triangle T(n,k) begins:
%e A256061   1;
%e A256061   0,   1;
%e A256061   0,   2,     4;
%e A256061   0,   5,    30,     30;
%e A256061   0,  14,   196,    504,     336;
%e A256061   0,  42,  1260,   6300,   10080,    5040;
%e A256061   0, 132,  8184,  71280,  205920,  237600,   95040;
%e A256061   0, 429, 54054, 774774, 3603600, 7207200, 6486480, 2162160;
%e A256061   ...
%p A256061 ctln:= proc(n) option remember; binomial(2*n, n)/(n+1) end:
%p A256061 A:= proc(n, k) option remember; k^n*ctln(n) end:
%p A256061 T:= (n, k)-> add(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k):
%p A256061 seq(seq(T(n, k), k=0..n), n=0..10);
%t A256061 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 *)
%Y A256061 Columns k=0-1 give: A000007, A000108 (for n>0).
%Y A256061 Main diagonal gives A001761.
%Y A256061 Cf. A253180, A255982, A258427, A290605.
%K A256061 nonn,tabl
%O A256061 0,5
%A A256061 _Alois P. Heinz_, Mar 13 2015