28
$\begingroup$

This is getting no attention on stackexchange.

Everybody knows that the number of derangements of a set of size $n$ is the nearest integer to $n!/e$.

It had escaped my attention until last week, when I wrote this answer, that the number of sequences of distinct elements of a set of size $n$ (including sequences of length $0$) is the nearest integer to $n!e$, provided $n\ge2$. The sequence whose $n$th term is the nearest integer to $n!e$ satifies the recurrence $x_{n+1} = (n+1)x_n + 1$.

How widespread is this operation of mulitplying by an irrational number and then rounding, in combinatorial problems? Are there other standard examples? Is there some general theory accounting for this? And, while I'm at it, where is this in "the literature"?

(I'm not sure whether we should include things like Fibonacci numbers or solutions of Pell's equation as examples of the same thing.)

$\endgroup$
7
  • 4
    $\begingroup$ Perhaps not a direct answer to your question, but this quote is from Chapter 1 of Stanley's Enumerative Combinatorics, Volume 1: "We also remark that it follows easily from (1.1) that f(n) is the nearest integer to n!/e. This is certainly a simple explicit formula, but it has the disadvantage of being “non-combinatorial”; that is, dividing by e and rounding off to the nearest integer has no direct combinatorial significance." $\endgroup$ Sep 17, 2013 at 23:34
  • 1
    $\begingroup$ Quadratic surds and $e$ have rational approximations with simple recurrences. Perhaps particular values of Bessel functions or hypergeometric functions would be good candidates. $\endgroup$ Sep 18, 2013 at 0:14
  • 3
    $\begingroup$ Perhaps you want to say "transcendental" to rule out examples like the Fibonacci numbers (there we have irrational but algebraic numbers coming from a well-understood source, namely the poles of the generating function). But while I'm talking about generating functions, $e$ is a very special number because of its relationship to exponential generating functions, and the appearance of $e$ in the derangement problem is a reflection of this. A similar observation is that the probability that a permutation of $n$ elements has no $k$-cycles for $k \le r$ is asymptotically $e^{-H_r}$. $\endgroup$ Sep 18, 2013 at 0:26
  • 4
    $\begingroup$ This is not a very precise comment, but when the phenomenon you describe occurs, it typically leads to a proof that the irrational number in question is indeed irrational. Irrationality proofs, especially of transcendental numbers, tend to be scarce, so your phenomenon tends to be scarce. Your uncertainty about quadratic irrationals is related, I think, to the fact that the proof of their irrationality is "too easy." If you allow algebraic irrationals, then I think you'll get more examples. $\endgroup$ Sep 18, 2013 at 2:26
  • 7
    $\begingroup$ One reason why the $n$th derangement number is very close to $n!/e$ is that the exponential generating function for the derangement numbers is $$\frac{e^{-z}}{1-z} = \frac{e^{-1}}{1-z} + g(z)$$ where $g(z)$ is an entire function, and therefore $g(z)$ has coefficients that are very small compared to the coefficients of $e^{-z}/(1-z)$. By the same reasoning, if $f(z)$ is an entire function, or even a function with radius of convergence greater than 1, then the coefficients of $f(z)/(1-z)$ will be very close to $f(1)$. $\endgroup$
    – Ira Gessel
    Sep 18, 2013 at 13:40

6 Answers 6

13
$\begingroup$

This is related to Noam Elkies's answer but is not exactly the same. Rayleigh's theorem, a.k.a. Beatty's theorem, says that if $a$ and $b$ are positive irrational numbers such that $1/a + 1/b=1$, then the sets $\lbrace \lfloor na\rfloor : n\in \mathbb{N}\rbrace$ and $\lbrace \lfloor nb\rfloor : n\in \mathbb{N}\rbrace$ comprise a partition of $\mathbb N$ into two disjoint sets. There are connections between this theorem and various combinatorial topics, such as Wythoff's game as Noam mentioned, and combinatorics on words (Sturmian sequences).

$\endgroup$
8
$\begingroup$

A result due to W. H. Mills (1950) mentioned in Apostol's Introduction to Analytic Number Theory (in the Historical Introduction section) states: there is a positive number $A$, which is not an integer, such that $\left\lfloor{A^{3^x}}\right\rfloor$ is a prime for all $x = 1,2,3,\ldots$. (It is probably not known if $A$ has to be irrational, but I thought this result may be of interest.)

The original reference is Bull. Amer. Math. Soc. Volume 53, Number 6 (1947), 604 (Mathematical Reviews number (MathSciNet): MR0020593) and an errata Bull. Amer. Math. Soc. Volume 53, Number 12 (1947), 1196. According to the paper $A = \lim_{n\rightarrow \infty} P_n^{3^{-n}}$, where $P_n$ is the $n$'th prime. The 1-page paper is available on Project Euclid: http://projecteuclid.org/euclid.bams/1183510803.

$\endgroup$
3
  • $\begingroup$ Interesting. Does anybody know the value of that number? $\endgroup$ Oct 19, 2013 at 20:44
  • $\begingroup$ Just added more info about A. $\endgroup$
    – sanjshakun
    Oct 19, 2013 at 21:40
  • 1
    $\begingroup$ See the earlier question, "Integer dynamics hitting infinitely many primes," which includes the value $A \approx 1.3063778838630806904686144926...$ $\endgroup$ Oct 20, 2013 at 0:49
5
$\begingroup$

The mutual Zugzwangs in Wythoff's game are $(\lfloor \phi k \rfloor, \lfloor \phi^2 k \rfloor)$ and $(\lfloor \phi^2 k \rfloor, \lfloor \phi k \rfloor)$ where $k=0,1,2,\ldots$ and $\phi$ is the golden ratio $(1 + \sqrt 5)/2$ .

$\endgroup$
2
  • 2
    $\begingroup$ @JAS, it is not that different. Since the floor of $x$ is equal to the nearest integer to $x - 1/2$ $\endgroup$
    – Woett
    Sep 18, 2013 at 12:03
  • 3
    $\begingroup$ Actually no, there can't be such examples. As long as $x$ is irrational, any time $\lfloor x \rfloor$ appears in a formula it could be written equally as round$(x - \frac12)$. So I could have singled out the base Zugzwang $(0,0)$, required $k>0$, and written $(\lfloor \phi k \rfloor, \lfloor \phi^2 k \rfloor)$ as $(\text{round}(\phi k-\frac12), \text{round}(\phi^2 k - \frac12))$ etc. But I trusted that the OP (though perhaps not every MO reader...) would recognize that the more compact form I game is easily equivalent to a formula with rounding. $\endgroup$ Sep 18, 2013 at 14:26
3
$\begingroup$

Multiplying by $e$ or $1/e$ (and rounding to an integer) shows up in various applications of the local lemma.

$\endgroup$
2
$\begingroup$

A remarkable paper by Colin Defant, Troupes, Cumulants, and Stack-Sorting, uncovers another surprising combinatorial appearance of $e$. Let $s$ denote the stack-sorting map (for the definition, see Defant's paper) and let $\mathrm{des}(\pi)$ denote the number of descents of a permutation $\pi$. If $\sigma$ is a permutation of $\{1, 2,\ldots, n-1\}$ chosen uniformly at random, then the expected value of $\mathrm{des}(s(\sigma))+1$ is $$\biggl(3 - \sum_{i=0}^n {1\over i!}\biggr)n.$$ Multiplying the above number by $n!$ yields the integer $\lceil n!(3 - e)n\rceil$. You might expect that there is some simple connection to derangements, but no combinatorial connection to derangements is known (as of 2021).

$\endgroup$
1
$\begingroup$

The answer to a combinatorial enumeration problem (compute $a_n:=\mathrm{card}(A_n)$ for any $n\in\mathbb{N}$, with respect to a given sequence of sets $A_n$ defined by some combinatorial rule) may have an efficient form in terms of analytic objects. These essentially consist in translating the combinatorial rule of formation of the sets $A_n$ into some analytic relation (differential or functional equations &c) on the sequence $(a_n)$, seen e.g. by means of a generating function or other. In a sense, the key point is that a limit process, which consists in the description of the whole family $\{A_n\}_n$ as a single object, is done before performing the enumeration of the cardinalities. Limit processes naturally produce irrational objects, so that it shouldn't be surprising (yet, it is always surprising and amusing) to get closed enumeration formulae in terms of irrational numbers. So you have the examples of the derangement numbers that you quoted, Fibonacci numbers, the Bell numbers formula, the partition numbers and so on. The fact that the final answer is an integer number is an independent additional information, that allow the rounding operation (e.g. you do not need to compute $B_n:=\frac{1}{e} \sum_{k=0}^\infty\frac{k^n}{k!}$ with precision better than $1/2$, since you know that the result is an integer number).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.