Plutarch reports that Hipparchus counted 103,049 compound propositions "on the affirmative side" and...

combinatorics/plutarch.numbers New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Plutarch reports that Hipparchus counted 103,049 compound propositions
"on the affirmative side" and 310,952 "on the negative side" that can be
made from ten simple propositions.  What was Hipparchus counting?

The passage, from Plutarch's Table-Talk (VIII.9, 732), as quoted by
R. P. Stanley:

   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.)

[ Editor: problem statement reconstructed from the paper. ]

Show solution

Richard P. Stanley, "Hipparchus, Plutarch, Schröder and Hough",
Department of
Mathematics, Massachusetts Institute of Technology.  [ Editor: the
copy in the collection is an undated preprint; the paper appeared as
"Hipparchus, Plutarch, Schröder, and Hough", American Mathematical
Monthly 104 (1997), 344-350. ]

The central passage (section 3, "Hough"):

   In January 1994 David Hough (1949- ), a graduate student at George
   Washington University (who decided only in 1992 that he would
   pursue a career in mathematics), noticed that the mysterious number
   103,049 of Plutarch, i.e., the number of compound propositions that
   can be formed from ten simple propositions, is just the tenth
   Schröder number!

and its conclusion:

   The number 310,952 in Plutarch's statement, i.e., the number of
   compound propositions that can be formed from ten simple
   propositions "on the negative side," remains an enigma. [...] Thus
   the mystery of Plutarch's statement remains at most half solved.

-- Richard P. Stanley

[ Editor: summary.  The paper first surveys the failed attempts to
explain Plutarch's numbers (Heath, Neugebauer, the Kneales, Biggs and
others).  It then describes Schröder's "bracketing problems": a
bracketing of a string of n letters is either a single letter or a
sequence of k >= 2 bracketings, e.g. there are eleven bracketings of
xxxx.  The number b(n) of binary bracketings is the Catalan number
C(n-1) = (1/n)*binomial(2n-2, n-1); the total number s(n) of
bracketings (also the number of dissections of a convex (n+1)-gon by
diagonals, of plane trees with n endpoints and no vertex of degree
one, and of certain Lukasiewicz words) has generating function
sum s(n) x^n = (1 + x - sqrt(1 - 6x + x^2))/4, with values

   s(1), ..., s(10) = 1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049

and the recurrence (n+2)s(n+2) - 3(2n+1)s(n+1) + (n-1)s(n) = 0 for
n >= 1.  Stanley suggests Hipparchus more probably used the "obvious"
recurrence s(n) = sum of s(i1)...s(ik) over all ordered sums
i1+...+ik = n with k >= 2, whose 511 terms for n = 10 group into the
41 partitions of 10 into at least two parts.  Neil Sloane found
neither 310,952 nor 103,049 + 310,952 = 414,001 in his tables. ]

[ Editor: the second number was explained after this paper: L.
Habsieger, M. Kazarian and S. Lando, "On the second number of
Plutarch", American Mathematical Monthly 105 (1998), 446, gave an
explanation of 310,952 in terms of bracketings as well. ]

[ Editor: the full paper was in the TODO collection as Math/hip.ps. ]