login
Number of permutations p of [n] whose absolute displacements |p(i)-i| are Fibonacci numbers.
4

%I #10 Mar 25 2021 09:40:38

%S 1,1,2,6,24,78,362,1473,5657,30045,150862,690604,3048236,14043152,

%T 84667280,484698208,2661357616,13753927840,73080151824,374413073328,

%U 1963753297884,10358706625196,69857764331270,447802562823975

%N Number of permutations p of [n] whose absolute displacements |p(i)-i| are Fibonacci numbers.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>

%p g:= proc(n) g(n):= (t-> issqr(t+4) or issqr(t-4))(5*n^2) end:

%p b:= proc(s) option remember; (n-> `if`(n=0, 1, add(`if`(

%p g(abs(n-j)), b(s minus {j}), 0), j=s)))(nops(s))

%p end:

%p a:= n-> b({$1..n}):

%p seq(a(n), n=0..16);

%t g[n_] := With[{t = 5 n^2}, IntegerQ@Sqrt[t + 4] || IntegerQ@Sqrt[t - 4]];

%t b[s_] := b[s] = With[{n = Length[s]}, If[n == 0, 1, Sum[If[g[Abs[n - j]], b[s ~Complement~ {j}], 0], {j, s}]]];

%t a[n_] := b[Range[n]];

%t a /@ Range[0, 16] (* _Jean-François Alcover_, Mar 25 2021, after _Alois P. Heinz_ *)

%Y Cf. A000045, A000142, A324372, A324374, A324375, A324376.

%K nonn

%O 0,3

%A _Alois P. Heinz_, Feb 25 2019