cp's OEIS Frontend

A174469 Number of permutations p of {1,...,n} satisfying p(1)=1 and, if n>1, |p(i)-p((i mod n)+1)| is in {2,3} for i from 1 to n.

%I A174469 #20 Feb 16 2025 08:33:12
%S A174469 1,0,0,0,2,0,0,0,0,2,2,2,2,2,4,6,8,10,12,16,22,30,40,52,68,90,120,160,
%T A174469 212,280,370,490,650,862,1142,1512,2002,2652,3514,4656,6168,8170,
%U A174469 10822,14336,18992,25160,33330,44152,58488,77480,102640,135970
%N A174469 Number of permutations p of {1,...,n} satisfying p(1)=1 and, if n>1, |p(i)-p((i mod n)+1)| is in {2,3} for i from 1 to n.
%C A174469 Also the number of directed Hamiltonian cycles in the graph on n vertices {1,...,n}, with i adjacent to j iff 2 <= |i-j| <= 3.
%H A174469 Alois P. Heinz, <a href="/A174469/b174469.txt">Table of n, a(n) for n = 1..1000</a>
%H A174469 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>
%H A174469 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,0,1).
%F A174469 G.f.: (3*x^5-2*x^4+x-1)*x / (x^5+x-1).
%F A174469 a(n) = 2*A017899(n-5) for n>=5.
%e A174469 For n = 10 the a(10) = 2 permutations are (1,3,6,9,7,10,8,5,2,4), (1,4,2,5,8,10,7,9,6,3).
%p A174469 a:= n-> `if`(n<2, n, (Matrix (5, (i,j)-> `if`(j-i=1 or i=5 and j in {1,5}, 1, 0))^n. <<2, -2, (0$3)>>)[1,1]): seq(a(n), n=1..60);
%t A174469 Join[{1}, LinearRecurrence[{1, 0, 0, 0, 1}, {0, 0, 0, 2, 0}, 60]] (* _Jean-François Alcover_, Oct 28 2021 *)
%Y A174469 Cf. A017899.
%K A174469 nonn,easy
%O A174469 1,5
%A A174469 _Alois P. Heinz_, Nov 28 2010