Multiplying by irrational numbers in combinatorial problems

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

• 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." – Sam Hopkins Sep 17 '13 at 23:34
• 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}$. – Qiaochu Yuan Sep 18 '13 at 0:26
• This is the kind of question that would normally be a big-list/"community wiki" question, except that so far your big list has zero entries... – Noam D. Elkies Sep 18 '13 at 2:26
• 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. – Timothy Chow Sep 18 '13 at 2:26
• 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)$. – Ira Gessel Sep 18 '13 at 13:40

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

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.

• Interesting. Does anybody know the value of that number? – Michael Hardy Oct 19 '13 at 20:44
• Just added more info about A. – anonymous Oct 19 '13 at 21:40
• See the earlier question, "Integer dynamics hitting infinitely many primes," which includes the value $A \approx 1.3063778838630806904686144926...$ – Joseph O'Rourke Oct 20 '13 at 0:49

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

• @JAS, it is not that different. Since the floor of $x$ is equal to the nearest integer to $x - 1/2$ – Woett Sep 18 '13 at 12:03
• 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. – Noam D. Elkies Sep 18 '13 at 14:26

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

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