A324631 Number of permutations p of [n] such that four is the maximum of the number of elements in any integer interval [p(i)..i+n*[i<p(i)]].

15, 31, 60, 113, 215, 406, 763, 1431, 2676, 4993, 9299, 17290, 32103, 59535, 110292, 204137, 377535, 697742, 1288763, 2379167, 4390148, 8097681, 14931075, 27522586, 50719103, 93444207, 172125100, 316999057, 583718215, 1074702870, 1978430491, 3641722423

Offset

4,1

Links

Alois P. Heinz, Table of n, a(n) for n = 4..2000

Index entries for linear recurrences with constant coefficients, signature (2,1,-1,-2,-1).

Formula

G.f.: -x^4*(10*x^4+23*x^3+17*x^2-x-15)/((x^2+x-1)*(x^3+x^2+x-1)).

Example

a(4) = 15: 1243, 1324, 1342, 2134, 2143, 2314, 2341, 2413, 2431, 3142, 3241, 3421, 4231, 4312, 4321.
a(5) = 31: 12534, 12543, 14235, 14325, 14523, 14532, 15342, 31245, 31524, 31542, 32145, 32514, 34125, 34215, 34512, 35124, 35142, 35214, 41523, 41532, 42315, 42513, 45132, 45213, 45312, 51342, 52314, 54123, 54132, 54213, 54312.

Maple

a:= n-> `if`(n<4, 0, (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>,
        <0|0|0|0|1>, <-1|-2|-1|1|2>>^n. <<4, 1, 3, 10, 15>>)[1$2]):
seq(a(n), n=4..40);

Mathematica

LinearRecurrence[{2, 1, -1, -2, -1}, {15, 31, 60, 113, 215}, 40] (* Vincenzo Librandi, Jun 06 2019 *)

Prog

(Magma) I:=[15, 31, 60, 113, 215]; [n le 5 select I[n] else 2*Self(n-1)+Self(n-2)-Self(n-3)-2*Self(n-4)+Self(n-5): n in [1..40]]; // Vincenzo Librandi, Jun 06 2019

Crossrefs

Column k=4 of A324563.

Sequence in context: A045135 A283122 A195046 * A346897 A102955 A041444

Adjacent sequences: A324628 A324629 A324630 * A324632 A324633 A324634

Keyword

nonn,easy

Author

Alois P. Heinz, Mar 09 2019

Status

approved