|
| |
|
|
A033184
|
|
Catalan triangle A009766 transposed.
|
|
62
| |
|
|
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; 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 (callan(AT)stat.wisc.edu), 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 (wolfdieter.lang(AT)physik.uni-karlsruhe.de), 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 (deutsch(AT)duke.poly.edu), 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 . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Jun 14 2004
Number of Dyck paths of semilength and having k-1 peaks at height 2. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 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 (pbarry(AT)wit.ie), Jun 22 2005
Subtriangle of triangle A106566 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Jan 07 2007
T(n, k) is also the number of order-preserving and order-decreasing full transformations (of an n-chain) with exactly k fixed points. [From A. Umar (aumarh(AT)squ.edu.om), Oct 02 2008]
Triangle read by rows, product of A065600 and A007318 considered as infinite lower triangular arrays ; A033184 = A065600*A007318. [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Dec 07 2009]
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 (qntmpkt(AT)yahoo.com), 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
|
|
|
REFERENCES
| M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.
P. Barry, Invariant number triangles, eigentriangles and Somos-4 sequences, Arxiv preprint arXiv:1107.5490, 2011.
S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142-154.
E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202.
Higgins, Peter M. Combinatorial results for semigroups of order-preserving mappings. Math. Proc. Camb. Phil. Soc. 113 (1993), 281-296. [From A. Umar (aumarh(AT)squ.edu.om), Oct 02 2008]
W. Lang, On polynomials related to powers of the generating function of Catalan numbers, The Fibonacci Quart. 38 (2000) 408-19.
P. J. Larcombe and D. R. French, The Catalan number k-fold self-convolution identity: the original formulation, Journal of Combinatorial Mathematics and Combinatorial Computing 46 (2003) 191-204.
|
|
|
LINKS
| J. L. Arregui, Tangent and Bernoulli numbers related to Motzkin and Catalan numbers by means of numerical triangles.
D. Callan, A recursive bijective approach to counting permutations...
N. T. Cameron, Random walks, trees and extensions of Riordan group techniques
W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
D. Merlini, R. Sprugnoli and M. C. Verri, An algebra for proper generating trees
J. Noonan and D. Zeilberger, [math/9808080] The Enumeration of Permutations With a Prescribed Number of ``Forbidden'' Patterns
J.-C. Novelli and J.-Y. Thibon, Noncommutative Symmetric Functions and Lagrange Inversion
A. Reifegerste, On the diagram of 132-avoiding permutations.
A. Robertson, D. Saracino and D. Zeilberger, Refined restricted permutations.
|
|
|
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 (callan(AT)stat.wisc.edu), 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 (deutsch(AT)duke.poly.edu), Mar 01 2004
T(n,k) = C(2*n-k, n-k)*(k+1)/(n+1). [From Paul D. Hanna (pauldhanna(AT)juno.com), 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.
T(n-1,m-1)=m/n*sum(k=1..n-m+1,k*A000108(k-1)*T(n-k-1,m-2),k,1,n-m+1), n>=m>1;
[From Vladimir Kruchinin, Mar 17 2011]
|
|
|
EXAMPLE
| Triangle begins
\ k..1....2....3....4....5....6
n\
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);
|
|
|
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*)
|
|
|
PROG
| (PARI) T(n, k)=binomial(2*(n-k)+k, n-k)*(k+1)/(n+1) [From Paul D. Hanna (pauldhanna(AT)juno.com), Aug 11 2008]
(Sage) The simplest way to construct the triangle.
def A033184_triangle(n) :
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)]
A033184_triangle(10) # Peter Luschny, Jan 27 2012
|
|
|
CROSSREFS
| Rows of Catalan triangle A009766 read backwards.
a(n, 1)= A000108(n-1). Row sums = A000108(n) (Catalan).
The following are all versions of (essentially) the same Catalan triangle: A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.
Diagonals give A000108 A000245 A002057 A000344 A003517 A000588 A003518 A003519 A001392, ...
Cf. A116364 (row squared sums). [From Paul D. Hanna (pauldhanna(AT)juno.com), Aug 11 2008]
Sequence in context: A141751 A079222 * A171567 A110488 A134379 A108087
Adjacent sequences: A033181 A033182 A033183 * A033185 A033186 A033187
|
|
|
KEYWORD
| nonn,tabl,changed
|
|
|
AUTHOR
| Christian G. Bower (bowerc(AT)usa.net)
|
| |
|
|
