Suites "sans doublons" — Les-mathematiques.net The most powerful custom community solution in the world

Suites "sans doublons"

Modifié (August 2023) dans Combinatoire et Graphes
Bonjour tout le monde.
Je me suis intéressé il y a quelques temps au dénombrement des permutations $\sigma\{1..n\}\to \{1..n\}$ sans "doublons", c'est à dire telles que, pour tout $i\in\{1..n-1\}$, $\sigma(i\!+\!1)\!\not=\!\sigma(i)\!\pm\!1$.
C'est en fait la suite A002464 de OEIS ( https://oeis.org/A002464 ) et ils donnent une formule récursive (d'ordre 4) permettant le calculs des termes de la suite.
Après pas mal d'efforts, j'ai réussi à démontrer la formule, mais en passant par le calcul explicite des termes (via une double somme : la formule provient du principe d'inclusion/exclusion et, en fait,  elle est aussi sur le site de l'OEIS).

D'un autre coté, j'avais aussi obtenu des formules de récurrence en dénombrant le nombre de permutations avec $k$ doublons et en les scindant en deux selon que $\sigma(n)\!=\!\sigma(n\!-\!1)\!\pm\!1$ ou pas. 
Sauf que, en procédant de la sorte, je n'arrive pas à conclure (i.e. retrouver la formule de récurrence de l'OEIS).

Est-ce que quelqu'un connait une méthode pour démontrer cette formule de récurrence sans passer par la formule explicite ?
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!