|
| |
|
|
A010683
|
|
Let S(x,y) = number of lattice paths from (0,0) to (x,y) that use the step set { (0,1), (1,0), (2,0), (3,0), ....} and never pass below y = x. Sequence gives S(n-1,n) = number of `Schroeder' trees with n+1 leaves and root of deg. 2.
|
|
9
| |
|
|
1, 2, 7, 28, 121, 550, 2591, 12536, 61921, 310954, 1582791, 8147796, 42344121, 221866446, 1170747519, 6216189936, 33186295681, 178034219986, 959260792775, 5188835909516, 28167068630713, 153395382655222
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| a(n) = number of compound propositions "on the negative side" that can be made from n simple propositions.
Convolution of A001003 (the little Schroeder numbers) with itself. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 27 2003
Number of dissections of a convex polygon with n+3 sides that have a triangle over a fixed side (the base) of the polygon. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 27 2003
a(n-1) = number of royal paths from (0,0) to (n,n), A006318, with exactly one diagonal step on the line y=x. - David Callan (callan(AT)stat.wisc.edu), Mar 14 2004
Number of short bushes (i.e. ordered trees with no vertices of outdegree 1) with n+2 leaves and having root of degree 2. Example: a(2)=7 because, in addition to the five binary trees with 6 edges (they do have 4 leaves) we have (i) two edges rb, rc hanging from the root r with three edges hanging from vertex b and (ii) two edges rb, rc hanging from the root r with three edges hanging from vertex c. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 16 2004
|
|
|
REFERENCES
| Habseiger et al., On the second number of Plutarch, Am. Math. Monthly, 105 446 1998.
H. Kwong, On recurrences of Fahr and Ringel ..., Fib. Quart., 48 (2010), 363-365; see p. 364.
D. G. Rogers and L. W. Shapiro, "Deques, trees and lattice paths", in Combinatorial Mathematics VIII: Proceedings of the Eighth Australian Conference. Lecture Notes in Mathematics, Vol. 884 (Springer, Berlin, 1981), pp. 293-303. Math. Rev., 83g, 05038; Zentralblatt, 469(1982), 05005. See Figs. 7a and 8b.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..200
E. Pergola and R. A. Sulanke, Schroeder Triangles, Paths and Parallelogram Polyominoes, J. Integer Sequences, 1 (1998), #98.1.7.
R. P. Stanley, Hipparchus, Plutarch, Schr"oder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
Index entries for sequences related to trees
|
|
|
FORMULA
| G.f.: ((1-t)^2-(1+t)*sqrt(1-6*t+t^2))/(8*t^2) = (A(t)^2)/x^2, with o.g.f. A(t) of A001003.
a(n)=(2/n)*sum(binomial(n, k)*binomial(n+k+1, k-1), k=1..n) = 2*hypergeom([1-n, n+3], [2], -1), n>=1. a(0)=1. W. Lang (wolfdieter.lang_AT_physik_DOT_uni-karlsruhe_DOT_de), Sep 12 2005.
G.f.: ((1-t)^2-(1+t)*sqrt(1-6*t+t^2))/(8*t^2) = A(t)^2, with o.g.f. A(t) of A001003.
a(n) = ((2*n+1)*LegendreP(n+1,3) - (2*n+3)*LegendreP(n,3)) / (4*n*(n+2)) for n>0 [From Mark van Hoeij (hoeij(AT)math.fsu.edu), Jul 02 2010]
Let M = the production matrix:
1, 2, 0, 0, 0, 0,...
1, 2, 1, 0, 0, 0,...
1, 2, 1, 2, 0, 0,...
1, 2, 1, 2, 1, 0,...
1, 2, 1, 2, 1, 2,...
...
a(n) = upper entry in the vector (M(T))^n * [1,0,0,0,...]; where T is the transpose operation.
- Gary W. Adamson, Jul 08 2011
|
|
|
MATHEMATICA
| f[ x_, y_ ] := f[ x, y ] = Module[ {return}, If[ x == 0, return = 1, If[ y == x-1, return = 0, return = f[ x, y-1 ] + Sum[ f[ k, y ], {k, 0, x-1} ] ] ]; return ]; Do[ Print[ Table[ f[ k, j ], {k, 0, j} ] ], {j, 10, 0, -1} ]
|
|
|
CROSSREFS
| Cf. A001003.
Right-hand column 2 of triangle A011117.
Second column of convolution triangle A011117.
A177010 has a closely-related g.f.
Sequence in context: A150657 A150658 A026770 * A150659 A150660 A150661
Adjacent sequences: A010680 A010681 A010682 * A010684 A010685 A010686
|
|
|
KEYWORD
| nonn,nice,easy
|
|
|
AUTHOR
| Robert Sulanke (sulanke(AT)diamond.idbsu.edu), N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
