A127697 Number of permutations of {1,2,...,n} where adjacent elements differ in value by 3 or more.

1, 1, 0, 0, 0, 0, 2, 32, 368, 3984, 44304, 521606, 6564318, 88422296, 1272704694, 19521035238, 318120059458, 5491779703870, 100150978723568, 1924351621839740, 38864316540425434, 823161467837784388

Offset

0,7

Comments

Equivalently, number of permutations of {1,2,...,n} where elements that differ by 1 in value are neither in positions i and i+1 (adjacent), nor i and i+2.

Links

Table of n, a(n) for n=0..21.

Robert P. P. McKone, The permutations n=6 to n=10.

Example

Valid permutations of {1,...,6} are 415263 and 362514.

Mathematica

Clear[permCount]; permCount[s_, last_] := permCount[s, last] = Module[{n, j}, n = Length[s]; If[n == 0, 1, Total[Table[If[Abs[last - j] >= 3, permCount[DeleteCases[s, j], j], 0], {j, s}]]]]; Table[permCount[Range[n], -2], {n, 0, 12}] (* Robert P. P. McKone, Mar 01 2025 *)

Crossrefs

Cf. A002464 (stride >= 2), A179957 (stride >= 4), A179958 (stride >=5).

Sequence in context: A350138 A270445 A199019 * A191467 A370828 A282881

Adjacent sequences: A127694 A127695 A127696 * A127698 A127699 A127700

Keyword

nonn,more

Author

Richard Forster (gbrl01(AT)yahoo.co.uk), Apr 11 2007, Apr 26 2007

Extensions

Jul 01 2010: Zak Seidov corrected a(10) and a(11). R. H. Hardin then computed a(12) through a(18).

Corrected first term to 1 (was 0).

a(0), a(19)-a(20) from Alois P. Heinz, Oct 27 2014

a(21) from Alois P. Heinz, Feb 09 2025

Status

approved