A385588 Number of non-derangements of length n with 2 excedances.

0, 4, 45, 251, 1078, 4054, 14115, 46837, 150612, 474200, 1471561, 4520959, 13792002, 41867242, 126649983, 382177817, 1151251648, 3463715980, 10412118981, 31280396611, 93933463950, 281993329214, 846382640155, 2539986780541, 7621705171308, 22868739391744, 68613734367105, 205856772356807

Offset: 3

Author

Aurora Hiveley, Jul 03 2025

Keywords

• nonn
• easy

Comments

Number of permutations of length n guessed by a cyclic shifting strategy in 3 guesses such that the first correct entry occurs on guess 1. In other words, non-derangements guessable by cyclic shift in 3 guesses.

Examples

			For n=4, the non-derangements with 2 excedances are 1342, 2314, 2431, and 3241.
		

Links

• Aurora Hiveley, Experimenting with Permutation Wordle, arXiv:2506.23452 [math.CO], 2025.
• Index entries for linear recurrences with constant coefficients, signature (10,-40,82,-91,52,-12).

Crossrefs

Summation uses k=2 row of A046739.

Programs

Mathematica

LinearRecurrence[{10, -40, 82, -91, 52, -12}, {0, 4, 45, 251, 1078, 4054}, 28] (* Hugo Pfoertner, Jul 03 2025 *)

Formula

a(n) = 1 - 2^(n+1) + 3^n + n^2/2 + 5*n/2 - n*2^n.

a(n) = Sum_{k=1..n-3} binomial(n,k)*(2^(n-k) - 2*n + 2*k - 1).

G.f.: x^4 * (4 + 5*x - 39*x^2 + 40*x^3 - 12*x^4) / ((1 - x)^3 * (1 - 2*x)^2 * (1 - 3*x)). - Stefano Spezia, Jul 03 2025