Schröder–Hipparchus number
   HOME

TheInfoList



OR:

In
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
, the Schröder–Hipparchus numbers form an
integer sequence In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers. An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. For ...
that can be used to count the number of
plane tree ''Platanus'' is a genus consisting of a small number of tree species native to the Northern Hemisphere. They are the sole living members of the family Platanaceae. All mature members of ''Platanus'' are tall, reaching in height. All except f ...
s 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 :1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, ... . They are also called the super-Catalan numbers, the little Schröder numbers, or the Hipparchus numbers, after
Eugène Charles Catalan Eugène Charles Catalan (30 May 1814 – 14 February 1894) was a French and Belgian mathematician who worked on continued fractions, descriptive geometry, number theory and combinatorics. His notable contributions included discovering a periodic ...
and his
Catalan number In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Cata ...
s, Ernst Schröder and the closely related
Schröder number In mathematics, the Schröder number S_n, also called a ''large Schröder number'' or ''big Schröder number'', describes the number of lattice paths from the southwest corner (0,0) of an n \times n grid to the northeast corner (n,n), using only ...
s, and the ancient Greek mathematician
Hipparchus Hipparchus (; el, Ἵππαρχος, ''Hipparkhos'';  BC) was a Greek astronomer, geographer, and mathematician. He is considered the founder of trigonometry, but is most famous for his incidental discovery of the precession of the equi ...
who appears from evidence in
Plutarch Plutarch (; grc-gre, Πλούταρχος, ''Ploútarchos''; ; – after AD 119) was a Greek Middle Platonist philosopher, historian, biographer, essayist, and priest at the Temple of Apollo in Delphi. He is known primarily for his ''P ...
to have known of these numbers.


Combinatorial enumeration applications

The Schröder–Hipparchus numbers may be used to count several closely related combinatorial objects:.. *The ''n''th 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 ''n''th number counts the number of different
plane tree ''Platanus'' is a genus consisting of a small number of tree species native to the Northern Hemisphere. They are the sole living members of the family Platanaceae. All mature members of ''Platanus'' are tall, reaching in height. All except f ...
s with ''n'' leaves and with all internal vertices having two or more children. *The ''n''th number counts the number of different ways of inserting parentheses into a sequence of ''n'' + 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 number of faces of all dimensions of an
associahedron In mathematics, an associahedron is an -dimensional convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a string of letters, and the edges correspond to single application of ...
''K''''n'' + 1 of dimension ''n'' − 1, including the associahedron itself as a face, but not including the empty set. For instance, the two-dimensional associahedron ''K''4 is a
pentagon In geometry, a pentagon (from the Greek πέντε ''pente'' meaning ''five'' and γωνία ''gonia'' meaning ''angle'') is any five-sided polygon or 5-gon. The sum of the internal angles in a simple pentagon is 540°. A pentagon may be simpl ...
; 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 In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop ...
, 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 In combinatorics, bijective proof is a proof technique for proving that two sets have equally many elements, or that the sets in two combinatorial classes have equal size, by finding a bijective function that maps one set one-to-one onto the other ...
that all of these kinds of objects are counted by a single integer sequence. The same numbers also count the number of
double permutation A double is a look-alike or doppelgänger; one person or being that resembles another. Double, The Double or Dubble may also refer to: Film and television * Double (filmmaking), someone who substitutes for the credited actor of a character * ...
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 In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the p ...
s 12312 and 121323.


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 number In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Cata ...
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. The sequence of Catalan numbers and the sequence of Schröder–Hipparchus numbers, viewed as infinite-dimensional
vector Vector most often refers to: *Euclidean vector, a quantity with a magnitude and a direction *Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism Vector may also refer to: Mathematic ...
s, are the unique
eigenvector In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
s for the first two in a sequence of naturally defined linear operators on number sequences... More generally, the ''k''th sequence in this sequence of integer sequences is (''x''1, ''x''2, ''x''3, ...) where the numbers ''xn'' are calculated as the sums of
Narayana number In combinatorics, the Narayana numbers \operatorname(n, k), n \in \mathbb^+, 1 \le k \le n form a triangular array of natural numbers, called the Narayana triangle, that occur in various counting problems. They are named after Canadian mathemati ...
s multiplied by powers of ''k''. This can be expressed as a hypergeometric function: :x_n = \sum_^n N(n,i)\, k^ = \sum_^n \frac k^=_2F_1(1-n,-n;2;k). Substituting ''k'' = 1 into this formula gives the Catalan numbers and substituting ''k'' = 2 into this formula gives the Schröder–Hipparchus numbers. 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 In mathematics, the permutohedron of order ''n'' is an (''n'' − 1)-dimensional polytope embedded in an ''n''-dimensional space. Its vertex coordinates (labels) are the permutations of the first ''n'' natural numbers. The edges ident ...
are respectively the
ordered Bell number In number theory and enumerative combinatorics, the ordered Bell numbers or Fubini numbers count the number of weak orderings on a set of ''n'' elements (orderings of the elements into a sequence allowing ties, such as might arise as the outcome o ...
s and the
factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \t ...
s.


Recurrence

As well as the summation formula above, the Schröder–Hipparchus numbers may be defined by a
recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
: :x_n=\frac\left((6n-9)x_-(n-3)x_\right). Stanley proves this fact using
generating function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
s. while Foata and Zeilberger provide a direct combinatorial proof.


History

Plutarch's Plutarch (; grc-gre, Πλούταρχος, ''Ploútarchos''; ; – after AD 119) was a Greek Middle Platonist philosopher, historian, biographer, essayist, and priest at the Temple of Apollo in Delphi. He is known primarily for his ...
dialogue 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.) This statement went unexplained until 1994, when David Hough, a graduate student at
George Washington University , mottoeng = "God is Our Trust" , established = , type = Private federally chartered research university , academic_affiliations = , endowment = $2.8 billion (2022) , preside ...
, observed that there are 103049 ways of inserting parentheses into a sequence of ten items. 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.. The historian of mathematics Fabio Acerbi (
CNRS The French National Centre for Scientific Research (french: link=no, Centre national de la recherche scientifique, CNRS) is the French state research organisation and is the largest fundamental science agency in Europe. In 2016, it employed 31,637 ...
) 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. The problem of counting parenthesizations was introduced to modern mathematics by .. Plutarch's recounting of Hipparchus's two numbers records a disagreement between Hipparchus and the earlier Stoic philosopher
Chrysippus Chrysippus of Soli (; grc-gre, Χρύσιππος ὁ Σολεύς, ; ) was a Greek Stoic philosopher. He was a native of Soli, Cilicia, but moved to Athens as a young man, where he became a pupil of the Stoic philosopher Cleanthes. When Clean ...
, who had claimed that the number of compound propositions that can be made from 10 simple propositions exceeds a million. Contemporary philosopher has argued that Chrysippus's calculation was the correct one, based on her analysis of
Stoic logic Stoic logic is the system of propositional logic developed by the Stoic philosophers in ancient Greece. It was one of the two great systems of logic in the classical world. It was largely built and shaped by Chrysippus, the third head of the Stoi ...
. 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..


References


External links

*
The Hipparchus Operad
The n-Category Café, April 1, 2013 {{DEFAULTSORT:Schroder-Hipparchus number Integer sequences Enumerative combinatorics