Combinatorics and Graph Theory · Problem 2.2.3

Inclusion-Exclusion — David Guichard

Mathematics — Combinatorics · forbidden-consecutive-permutations

Problem

Provide the missing details for example 2.2.1 (the number of permutations of

[n]

that contain no instance of

i

followed by

i+1

, given by

Q_n = n! \sum_{k=0}^{n-1} (-1)^k \frac{1}{k!} + (n-1)! \sum_{k=1}^{n-1} (-1)^{k-1} \frac{1}{(k-1)!}

). What is

\lim_{n \to \infty} \frac{Q_n}{n!}