|
|
A033184
|
|
Catalan triangle A009766 transposed.
|
|
87
|
|
|
1, 1, 1, 2, 2, 1, 5, 5, 3, 1, 14, 14, 9, 4, 1, 42, 42, 28, 14, 5, 1, 132, 132, 90, 48, 20, 6, 1, 429, 429, 297, 165, 75, 27, 7, 1, 1430, 1430, 1001, 572, 275, 110, 35, 8, 1, 4862, 4862, 3432, 2002, 1001, 429, 154, 44, 9, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Triangle read by rows: T(n,k) = number of Dyck n-paths (A000108) containing k returns to ground level. E.g., the paths UDUUDD, UUDDUD each have 2 returns; so T(3,2)=2. Row sums over even-indexed columns are the Fine numbers A000957. - David Callan, Jul 25 2005
Triangular array of numbers a(n,k) = number of linear forests of k planted planar trees and n non-root nodes.
Catalan convolution triangle; with offset [0,0]: a(n,m)=(m+1)*binomial(2*n-m,n-m)/(n+1), n >= m >= 0, else 0. G.f. for column m: c(x)*(x*c(x))^m with c(x) g.f. for A000108 (Catalan). - Wolfdieter Lang, Sep 12 2001
a(n+1,m+1), n >= m >= 0, a(n,m) := 0, n<m, has inverse matrix A030528(n,m)*(-1)^(n-m).
a(n,k)=number of Dyck paths of semilength n and having k returns to the axis. Also number of Dyck paths of semilength n and having first peak at height k. Also number of ordered trees with n edges and root degree k. Also number of ordered trees with n edges and having the leftmost leaf at level k. Also number of parallelogram polyominoes of semiperimeter n+1 and having k cells in the leftmost column. - Emeric Deutsch, Mar 01 2004
Triangle T(n,k) with 1<=k<=n given by [0, 1, 1, 1, 1, 1, 1, 1, ...] DELTA [1, 0, 0, 0, 0, 0, 0, 0, ...] = 1; 0, 1; 0, 1, 1; 0, 2, 2, 1; 0, 5, 5, 3, 1; 0, 14, 14, 9, 4, 1; ... where DELTA is the operator defined in A084938; essentially the same triangle as A059365. - Philippe Deléham, Jun 14 2004
Number of Dyck paths of semilength and having k-1 peaks at height 2. - Emeric Deutsch, Aug 31 2004
Riordan array (c(x),x*c(x)), c(x) the g.f. of A000108. Inverse of Riordan array (1-x,x*(1-x)). - Paul Barry, Jun 22 2005
T(n, k) is also the number of order-preserving and order-decreasing full transformations (of an n-chain) with exactly k fixed points. - Abdullahi Umar, Oct 02 2008
The formula stating "Column k is the k-fold convolution of column 1" is equivalent to repeatedly applying M to [1,0,0,0,...], where M is an upper triangular matrix of all 1's with an additional single subdiagonal of 1's. - Gary W. Adamson, Jun 06 2011
4^(n-1) = (n-th row terms) dot (first n terms in A001792), where A001792 = binomial transform of the natural numbers: (1, 3, 8, 20, 48, 112, ...). Example: 4^4 = 256 = (14, 14, 9, 4, 1) dot (1, 3, 8, 20, 48) = (42 + 42 + 28 + 14 + 5 + 1) = 256. - Gary W. Adamson, Jun 17 2011
The e.g.f. for the n-th subdiagonal of the triangle has the form exp(x)*P(n,x), where P(n,x) is the e.g.f. for row n of triangle A039599. For example, the third row of A039599 is [5, 9, 5, 1] and so the third subdiagonal sequence of this triangle [5, 14, 28, 48, 75, ...] has the e.g.f. exp(x)*(5 + 9*x + 5*x^2/2! + x^3/3!). - Peter Bala, Oct 15 2019
Antidiagonals of convolution matrix of Table 1.3, p. 397, of Hoggatt and Bicknell. - Tom Copeland, Dec 25 2019
|
|
LINKS
|
José Agapito, Ângela Mestre, Maria M. Torres, and Pasquale Petrullo, On One-Parameter Catalan Arrays, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.1.
|
|
FORMULA
|
Column k is the k-fold convolution of column 1. The triangle is also defined recursively by (i) entries outside triangle are 0, (ii) top left entry is 1, (iii) every other entry is sum of its east and northwest neighbor. - David Callan, Jul 25 2005
G.f.: t*x*c/(1-t*x*c), where c=(1-sqrt(1-4*x))/(2*x) is the g.f. of the Catalan numbers (A000108). - Emeric Deutsch, Mar 01 2004
T(n+1,k+1) = C(2*n-k, n-k)*(k+1)/(n+1). - Paul D. Hanna, Aug 11 2008
T((m+1)*n+r-1,m*n+r-1)*r/(m*n+r) = Sum_{k=1..n} (k/n)*T((m+1)*n-k-1,m*n-1)*T(r+k,r), n >= m > 1. - Vladimir Kruchinin, Mar 17 2011
G.f.: 2*x*y / (1 + sqrt(1 - 4*x) - 2*x*y) = Sum_{n >= k > 0} T(n, k) * x^n * y^k. - Michael Somos, Jun 06 2016
|
|
EXAMPLE
|
Triangle begins:
---+-----------------------------------
n\k| 1 2 3 4 5 6 7
---+-----------------------------------
1 | 1
2 | 1 1
3 | 2 2 1
4 | 5 5 3 1
5 | 14 14 9 4 1
6 | 42 42 28 14 5 1
7 | 132 132 90 48 20 6 1
|
|
MAPLE
|
a := proc(n, k) if k<=n then k*binomial(2*n-k, n)/(2*n-k) else 0 fi end: seq(seq(a(n, k), k=1..n), n=1..10);
# Uses function PMatrix from A357368. Adds row and column for n, k = 0.
PMatrix(10, n -> binomial(2*(n-1), n-1) / n); # Peter Luschny, Oct 07 2022
|
|
MATHEMATICA
|
nn = 10; c = (1 - (1 - 4 x)^(1/2))/(2 x); f[list_] := Select[list, # > 0 &]; Map[f, Drop[CoefficientList[Series[y x c/(1 - y x c), {x, 0, nn}], {x, y}], 1]] //Flatten (* Geoffrey Critzer, Jan 31 2012 *)
Flatten[Reverse /@ NestList[Append[Accumulate[#], Last[Accumulate[#]]] &, {1}, 9]] (* Birkas Gyorgy, May 19 2012 *)
|
|
PROG
|
(PARI) T(n, k)=binomial(2*(n-k)+k, n-k)*(k+1)/(n+1) \\ Paul D. Hanna, Aug 11 2008
(Sage) # The simplest way to construct the triangle.
T = [0 for i in (0..n)]
for k in (1..n) :
T[k] = 1
for i in range(k-1, 0, -1) :
T[i] = T[i-1] + T[i+1]
print([T[i] for i in (1..k)])
(Haskell)
a033184 n k = a033184_tabl !! (n-1) !! (k-1)
a033184_row n = a033184_tabl !! (n-1)
a033184_tabl = map reverse a009766_tabl
(Magma) /* As triangle: */ [[Binomial(2*n-k, n)*k/(2*n-k): k in [1..n]]: n in [1.. 15]]; // Vincenzo Librandi, Oct 12 2015
|
|
CROSSREFS
|
Rows of Catalan triangle A009766 read backwards.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|