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

Author

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

Keywords

• nonn
• more

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.

Examples

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

Links

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

Crossrefs

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

Programs

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

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