A395652 Number of permutations p of [n] whose positive prefix sums Sum_{i=1..k} p(i) avoid Fibonacci numbers.

1, 0, 0, 0, 3, 13, 0, 828, 6364, 73312, 0, 9393172, 137910936, 1657361304, 25306310568, 418509282600, 7401431236896, 123183948152448, 2338344747441216, 47478533220036864, 1006328018528687232, 20917151484073672320, 434695886449471779840, 10694787392361904214400

Offset

0,5

Links

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

Wikipedia, Permutation

Formula

a(n) = 0 <=> n in {1, 2, 3, 6, 10}.

Example

a(4) = 3: 4213, 4231, 4321.
a(5) = 13: 42135, 42153, 42315, 42351, 42513, 42531, 43215, 43251, 43521, 45123, 45213, 45231, 45321.
a(7) = 828: 4213576, 4213675, 4213756, 4213765, ..., 7564213, 7564231, 7564312, 7564321.
a(8) = 6364: 42135768, 42135786, 42135867, 42135876, ..., 78564123, 78564213, 78564231, 78564321.
a(6) = 0 because 6*7/2 = 21 is Fibonacci number.
a(10) = 0 because 10*11/2 = 55 is Fibonacci number.

Maple

q:= proc(n) option remember; (t-> issqr(t+4) or issqr(t-4))(5*n^2) end:
b:= proc(s, p) option remember; `if`(s={}, 1, add(
      `if`(q(p+j), 0, b(s minus {j}, p+j)), j=s))
    end:
a:= n-> b({$1..n}, 0):
seq(a(n), n=0..17);

Crossrefs

Cf. A000045, A000217, A039595, A291504, A395620.

Sequence in context: A167368 A318165 A215240 * A068697 A010258 A363270

Adjacent sequences: A395648 A395649 A395650 * A395653 A395654 A395655

Keyword

nonn

Author

Alois P. Heinz, May 02 2026

Status

approved