Multiplying by irrational numbers in combinatorial problems

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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