Schröder–Hipparchus number
In number theory, the Schröder–Hipparchus numbers form an integer sequence that can be used to count the number of plane trees with a given set of leaves, the number of ways of inserting parentheses into a sequence, and the number of ways of dissecting a convex polygon into smaller polygons by inserting diagonals. These numbers begin
They are also called the super-Catalan numbers, the little Schröder numbers, or the Hipparchus numbers, after Eugène Charles Catalan and his Catalan numbers, Ernst Schröder and the closely related Schröder numbers, and the ancient Greek mathematician Hipparchus who appears from evidence in Plutarch to have known of these numbers.
Combinatorial enumeration applications
The Schröder–Hipparchus numbers may be used to count several closely related combinatorial objects:[1][2][3][4]
- The nth number in the sequence counts the number of different ways of subdividing of a polygon with n + 1 sides into smaller polygons by adding diagonals of the original polygon.
- The nth number counts the number of different plane trees with n leaves and with all internal vertices having two or more children.
- The nth number counts the number of different ways of inserting parentheses into a sequence of n symbols, with each pair of parentheses surrounding two or more symbols or parenthesized groups, and without any parentheses surrounding the entire sequence.
- The nth number counts the number of faces of all dimensions of an associahedron Kn + 1 of dimension n − 1, including the associahedron itself as a face, but not including the empty set. For instance, the two-dimensional associahedron K4 is a pentagon; it has five vertices, five faces, and one whole associahedron, for a total of 11 faces.
As the figure shows, there is a simple combinatorial equivalence between these objects: a polygon subdivision has a plane tree as a form of its dual graph, the leaves of the tree correspond to the symbols in a parenthesized sequence, and the internal nodes of the tree other than the root correspond to parenthesized groups. The parenthesized sequence itself may be written around the perimeter of the polygon with its symbols on the sides of the polygon and with parentheses at the endpoints of the selected diagonals. This equivalence provides a bijective proof that all of these kinds of objects are counted by a single integer sequence.[2]
The same numbers also count the number of double permutations (sequences of the numbers from 1 to n, each number appearing twice, with the first occurrences of each number in sorted order) that avoid the permutation patterns 12312 and 121323.[5]
Related sequences
The closely related large Schröder numbers are equal to twice the Schröder–Hipparchus numbers, and may also be used to count several types of combinatorial objects including certain kinds of lattice paths, partitions of a rectangle into smaller rectangles by recursive slicing, and parenthesizations in which a pair of parentheses surrounding the whole sequence of elements is also allowed. The Catalan numbers also count closely related sets of objects including subdivisions of a polygon into triangles, plane trees in which all internal nodes have exactly two children, and parenthesizations in which each pair of parentheses surrounds exactly two symbols or parenthesized groups.[3]
The sequence of Catalan numbers and the sequence of Schröder–Hipparchus numbers, viewed as infinite-dimensional vectors, are the unique eigenvectors for the first two in a sequence of naturally defined linear operators on number sequences.[6][7] More generally, the kth sequence in this sequence of integer sequences is (x1, x2, x3, ...) where the numbers xn are calculated as the sums of Narayana numbers multiplied by powers of k:
Substituting k = 1 into this formula gives the Catalan numbers and substituting k = 2 into this formula gives the Schröder–Hipparchus numbers.[7]
In connection with the property of Schröder–Hipparchus numbers of counting faces of an associahedron, the number of vertices of the associahedron is given by the Catalan numbers. The corresponding numbers for the permutohedron are respectively the ordered Bell numbers and the factorials.
Recurrence
As well as the summation formula above, the Schröder–Hipparchus numbers may be defined by a recurrence relation:
Stanley proves this fact using generating functions[8] while Foata and Zeilberger provide a direct combinatorial proof.[9]
History
According to a line in Plutarch's Table Talk, Hipparchus showed that the number of "affirmative compound propositions" that can be made from ten simple propositions is 103049 and that the number of negative compound propositions that can be made from ten simple propositions is 310952. This statement went unexplained until 1994, when David Hough, a graduate student at George Washington University, observed that there are 103049 ways of inserting parentheses into a sequence of ten items.[1][8][10] A similar explanation can be provided for the other number: it is very close to the average of the tenth and eleventh Schröder–Hipparchus numbers, 310954, and counts bracketings of ten terms together with a negative particle.[10]
The problem of counting parenthesizations was introduced to modern mathematics by Schröder (1870).[11]
References
- 1 2 Stanley, Richard P. (1997, 1999), Enumerative Combinatorics, Cambridge University Press Check date values in:
|date=(help). Exercise 1.45, vol. I, p. 51; vol. II, pp. 176–178 and p. 213. - 1 2 Shapiro, Louis W.; Sulanke, Robert A. (2000), "Bijections for the Schröder numbers", Mathematics Magazine, 73 (5): 369–376, doi:10.2307/2690814, MR 1805263.
- 1 2 Etherington, I. M. H. (1940), "Some problems of non-associative combinations (I)", Edinburgh Mathematical Notes, 32: 1–6, doi:10.1017/S0950184300002639.
- ↑ Holtkamp, Ralf (2006), "On Hopf algebra structures over free operads", Advances in Mathematics, 207 (2): 544–565, arXiv:math/0407074
, doi:10.1016/j.aim.2005.12.004, MR 2271016. - ↑ Chen, William Y. C.; Mansour, Toufik; Yan, Sherry H. F. (2006), "Matchings avoiding partial patterns", Electronic Journal of Combinatorics, 13 (1): Research Paper 112, 17 pp. (electronic), MR 2274327.
- ↑ Bernstein, M.; Sloane, N. J. A. (1995), "Some canonical sequences of integers", Linear Algebra and its Applications, 226/228: 57–72, doi:10.1016/0024-3795(94)00245-9, MR 1344554.
- 1 2 Coker, Curtis (2004), "A family of eigensequences", Discrete Mathematics, 282 (1-3): 249–250, doi:10.1016/j.disc.2003.12.008, MR 2059525.
- 1 2 Stanley, Richard P. (1997), "Hipparchus, Plutarch, Schröder, and Hough" (PDF), American Mathematical Monthly, 104 (4): 344–350, doi:10.2307/2974582, MR 1450667.
- ↑ Foata, Dominique; Zeilberger, Doron (1997), "A classic proof of a recurrence for a very classical sequence", Journal of Combinatorial Theory, Series A, 80 (2): 380–384, arXiv:math/9805015, doi:10.1006/jcta.1997.2814, MR 1485153.
- 1 2 Acerbi, F. (2003), "On the shoulders of Hipparchus: A reappraisal of ancient Greek combinatorics" (PDF), Archive for History of Exact Sciences, 57: 465–502, doi:10.1007/s00407-003-0067-0.
- ↑ Schröder, Ernst (1870), "Vier combinatorische Probleme", Zeitschrift für Angewandte Mathematik und Physik, 15: 361–376.
External links
- The Hipparchus Operad, The n-Category Café, April 1, 2013