On a generalization of the recurrence defining the number of derangements
Volume 161 / 2020
Colloquium Mathematicum 161 (2020), 89-109
MSC: 11B50, 11B83.
DOI: 10.4064/cm7510-4-2019
Published online: 5 March 2020
Abstract
The sequence of derangements is given by the formula $D_0 = 1$, $D_n = nD_{n-1} + (-1)^n$, $n \gt 0$. It is a classical object in combinatorics and number theory. We extend results on $(D_{n})_{n\in \mathbb N }$ to a more general class of sequences given by the recurrence $a_0 = h_1(0)$, $a_n = f(n)a_{n-1} + h_1(n)h_2(n)^n$, $n \gt 0$, where $f,h_1,h_2 \in \mathbb Z [X]$. We study arithmetic properties of these sequences, such as periodicity modulo $d\in \mathbb N _+$, $p$-adic valuations, rate of growth, periodicity, recurrence relations and prime divisors.
