View source for Schröder–Hipparchus number

{{Short description|Number in combinatorics}}
{{Infobox integer sequence
| named_after = [[Ernst Schröder (mathematician)|Ernst Schröder]], [[Hipparchus]], [[Eugène Charles Catalan]]
| publication_year = 1870 (Schröder)
| terms_number = [[infinity]]
| formula = <math>x_n = \sum_{i=1}^n \frac{1}{n}{n\choose i}{n\choose i-1} k^{i-1}</math>
| first_terms = [[1]], [[1]], [[3]], [[11 (number)|11]], [[45 (number)|45]], [[197 (number)|197]], [[903 (number)|903]]
| OEIS = A001003
| OEIS_name = Little Schroeder numbers,<br/>Super Catalan
}}
[[File:Pentagon subdivisions.svg|thumb|260px|Eleven subdivisions of a pentagon]]
In [[combinatorics]], the '''Schröder–Hipparchus numbers''' form an [[integer sequence]] that can be used to count the [[Tree (graph theory)|plane tree]]s with a given set of leaves, the ways of inserting parentheses into a sequence, and the ways of dissecting a convex polygon into smaller polygons by inserting diagonals. These numbers begin
:1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, ... {{OEIS|A001003}}.
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 number]]s, [[Ernst Schröder (mathematician)|Ernst Schröder]] and the closely related [[Schröder number]]s, and the ancient Greek mathematician [[Hipparchus]] who appears from evidence in [[Plutarch]] to have known of these numbers.

==Combinatorial enumeration applications==
[[File:Tree-polygon-paren equivalence.svg|thumb|240px|Combinatorial equivalence between subdivisions of a polygon, plane trees, and parenthesizations]]
The Schröder–Hipparchus numbers may be used to count several closely related combinatorial objects:<ref name="stan-ec"/><ref name="ss">{{citation
 | last1 = Shapiro | first1 = Louis W. |authorlink1=Louis Shapiro (mathematician)
 | last2 = Sulanke | first2 = Robert A.
 | doi = 10.2307/2690814
 | issue = 5
 | journal = [[Mathematics Magazine]]
 | mr = 1805263
 | pages = 369–376
 | title = Bijections for the Schröder numbers
 | volume = 73
 | year = 2000| jstor = 2690814 }}.</ref><ref name="eth">{{citation
 | last = Etherington | first = I. M. H. | author-link = Ivor Malcolm Haddon Etherington
 | doi = 10.1017/S0950184300002639
 | journal = [[Edinburgh Mathematical Notes]]
 | pages = 1–6
 | title = Some problems of non-associative combinations (I)
 | volume = 32
 | year = 1940| doi-access = free
 }}.</ref><ref>{{citation
 | last = Holtkamp | first = Ralf
 | arxiv = math/0407074
 | doi = 10.1016/j.aim.2005.12.004
 | issue = 2
 | journal = [[Advances in Mathematics]]
 | mr = 2271016
 | pages = 544–565
 | title = On Hopf algebra structures over free operads
 | volume = 207
 | year = 2006| s2cid = 15908662
 }}.</ref>
*The ''n''th number in the sequence counts the different ways of subdividing a polygon with ''n''&nbsp;+&nbsp;1 sides into smaller polygons by adding diagonals of the original polygon.
*The ''n''th number counts the different [[Tree (graph theory)|plane tree]]s with ''n'' leaves and with all internal vertices having two or more children.
*The ''n''th number counts the different ways of inserting parentheses into a sequence of ''n''&nbsp;+&nbsp;1 symbols, with each pair of parentheses surrounding two or more symbols or parenthesized groups, and without any parentheses surrounding the entire sequence.
*The ''n''th number counts the faces of all dimensions of an [[associahedron]] ''K''<sub>''n''&nbsp;+&nbsp;1</sub> of dimension ''n''&nbsp;&minus;&nbsp;1, including the associahedron itself as a face, but not including the empty set. For instance, the two-dimensional associahedron ''K''<sub>4</sub> 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.<ref name="ss"/>

The same numbers also count the [[double permutation]]s (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 pattern]]s 12312 and 121323.<ref>{{citation
 | last1 = Chen | first1 = William Y. C.
 | last2 = Mansour | first2 = Toufik
 | last3 = Yan | first3 = Sherry H. F.
 | issue = 1
 | journal = [[Electronic Journal of Combinatorics]]
 | mr = 2274327
 | page = Research Paper 112, 17 pp. (electronic)
 | title = Matchings avoiding partial patterns
 | url = http://www.combinatorics.org/Volume_13/Abstracts/v13i1r112.html
 | volume = 13
 | year = 2006| doi = 10.37236/1138
 | doi-access = free
 }}.</ref>

==Related sequences==
The closely related [[Schröder number|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 number]]s 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.<ref name="eth"/>

The sequence of Catalan numbers and the sequence of Schröder–Hipparchus numbers, viewed as infinite-dimensional [[Row vector|vector]]s, are the unique [[eigenvector]]s for the first two in a sequence of naturally defined linear operators on number sequences.<ref name="bs">{{citation
 | last1 = Bernstein | first1 = M.
 | last2 = Sloane | first2 = N. J. A. | author2-link = Neil Sloane
 | doi = 10.1016/0024-3795(94)00245-9
 | journal = Linear Algebra and Its Applications
 | mr = 1344554
 | pages = 57–72
 | title = Some canonical sequences of integers
 | volume = 226/228
 | year = 1995| arxiv = math/0205301
 | s2cid = 14672360
 }}.</ref><ref name="coker">{{citation
 | last = Coker | first = Curtis
 | doi = 10.1016/j.disc.2003.12.008
 | issue = 1–3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 2059525
 | pages = 249–250
 | title = A family of eigensequences
 | volume = 282
 | year = 2004| doi-access = free
 }}.</ref> More generally, the ''k''th sequence in this sequence of integer sequences is  (''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>, ...) where the numbers ''x<sub>n</sub>'' are calculated as the sums of [[Narayana number]]s multiplied by powers of&nbsp;''k''. This can be expressed as a [[hypergeometric function]]:
:<math>x_n = \sum_{i=1}^n N(n,i)\, k^{i-1} = \sum_{i=1}^n \frac{1}{n}{n\choose i}{n\choose i-1} k^{i-1}={}_2F_1(1-n,-n;2;k).</math>
Substituting ''k''&nbsp;=&nbsp;1 into this formula gives the Catalan numbers and substituting ''k''&nbsp;=&nbsp;2 into this formula gives the Schröder–Hipparchus numbers.<ref name="coker"/>

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 number]]s and the [[factorial]]s.

==Recurrence==
As well as the summation formula above, the Schröder–Hipparchus numbers may be defined by a [[recurrence relation]]:
:<math>x_n=\frac{1}{n}\left((6n-9)x_{n-1}-(n-3)x_{n-2}\right).</math>
Stanley proves this fact using [[generating function]]s<ref name="stan-amm">{{citation
 | last = Stanley | first = Richard P. | authorlink = Richard P. Stanley
 | doi = 10.2307/2974582
 | issue = 4
 | journal = [[American Mathematical Monthly]]
 | mr = 1450667
 | pages = 344–350
 | title = Hipparchus, Plutarch, Schröder, and Hough
 | url = http://www-math.mit.edu/~rstan/papers/hip.pdf
 | volume = 104
 | year = 1997| jstor = 2974582 }}.</ref> while Foata and Zeilberger provide a direct combinatorial proof.<ref>{{citation
 | last1 = Foata | first1 = Dominique | author1-link = Dominique Foata
 | last2 = Zeilberger | first2 = Doron | author2-link = Doron Zeilberger
 | arxiv = math/9805015
 | doi = 10.1006/jcta.1997.2814
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]] | series = Series A
 | mr = 1485153
 | pages = 380–384
 | title = A classic proof of a recurrence for a very classical sequence
 | volume = 80
 | year = 1997| s2cid = 537142 }}.</ref>

==History==

[[Plutarch's]] dialogue [[Table Talk (Plutarch)|Table Talk]] contains the line:

:Chrysippus says that the number of compound propositions that can be made from only ten simple propositions exceeds a million. (Hipparchus, to be sure, refuted this by showing that on the affirmative side there are 103,049 compound statements, and on the negative side 310,952.)<ref name=stan-amm/>

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.<ref name="stan-ec"><!-- Do not use citation templates unless they get fixed to properly handle the double year -->[[Richard P. Stanley|Stanley, Richard P.]] (1997, 1999), ''Enumerative Combinatorics'', Cambridge University Press. Exercise 1.45, vol. I, p. 51; vol. II, pp. 176–178 and p. 213.</ref><ref name="stan-amm"/><ref name="acerbi">{{citation

 |last        = Acerbi
 |first       = F.
 |journal     = [[Archive for History of Exact Sciences]]
 |pages       = 465–502
 |title       = On the shoulders of Hipparchus: A reappraisal of ancient Greek combinatorics
 |url         = http://stl.recherche.univ-lille3.fr/sitespersonnels/acerbi/acerbipub5.pdf
 |volume      = 57
 |year        = 2003
 |doi         = 10.1007/s00407-003-0067-0
 |s2cid = 122758966
 |url-status     = dead
 |archiveurl  = https://web.archive.org/web/20110721023220/http://stl.recherche.univ-lille3.fr/sitespersonnels/acerbi/acerbipub5.pdf
 |archivedate = 2011-07-21
}}.</ref> The historian of mathematics Fabio Acerbi ([[CNRS]]) has shown that 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.<ref name="acerbi"/>

The problem of counting parenthesizations was introduced to modern mathematics by {{harvtxt|Schröder|1870}}.<ref>{{citation
 | last = Schröder | first = Ernst | author-link = Ernst Schröder (mathematician)
 | journal = [[Zeitschrift für Mathematik und Physik]]
 | pages = 361–376
 | title = Vier kombinatorische Probleme
 | volume = 15
 | year = 1870}}.</ref>

Plutarch's recounting of Hipparchus's two numbers records a disagreement between Hipparchus and the earlier Stoic philosopher [[Chrysippus]], who had claimed that the number of compound propositions that can be made from 10 simple propositions exceeds a million.  Contemporary philosopher {{harvs|first=Susanne|last=Bobzien|authorlink=Susanne Bobzien|year=2011|txt}} has argued that Chrysippus's calculation was the correct one, based on her analysis of [[Stoic logic]].  Bobzien reconstructs the calculations of both Chrysippus and Hipparchus, and says that showing how Hipparchus got his mathematics correct but his Stoic logic wrong can cast new light on the Stoic notions of conjunctions and assertibles.<ref name=Bobzien>{{citation
 | last = Bobzien | first = Susanne | author-link = Susanne Bobzien
 | title = The Combinatorics of Stoic Conjunction: Hipparchus refuted, Chrysippus vindicated
 | journal = Oxford Studies in Ancient Philosophy
 | volume = XL
 | date = Summer 2011
 | url = http://ancphil.lsa.umich.edu/-/downloads/osap/40-Bobzien.pdf
 | pages = 157–188}}.</ref>

==References==
{{reflist}}

==External links==
*{{mathworld|title=Super Catalan Number|urlname=SuperCatalanNumber|mode=cs2}}
*[http://golem.ph.utexas.edu/category/2013/04/permutations_polynomials_and_p.html The Hipparchus Operad], The n-Category Café, April 1, 2013

{{Classes of natural numbers}}

{{DEFAULTSORT:Schroder-Hipparchus number}}
[[Category:Integer sequences]]
[[Category:Enumerative combinatorics]]