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,2

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.

Links

Table of n, a(n) for n=3..30.

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

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

Example

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

Mathematica

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

Crossrefs

Summation uses k=2 row of A046739.

Sequence in context: A120075 A273832 A273848 * A123650 A371003 A122910

Adjacent sequences: A385585 A385586 A385587 * A385589 A385590 A385591

Keyword

nonn,easy

Author

Aurora Hiveley, Jul 03 2025

Status

approved