The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #19 May 26 2023 08:36:41
%S 1,0,2,2,16,36,288,1152,10368,57600,604800,4320000,51840000,453600000,
%T 6147187200,63605606400,962415820800,11500218777600,192255565824000,
%U 2605984690176000,47721518530560000,723526168780800000,14407079038894080000,241602987041095680000
%N Number of permutations p of [n] such that each element in p has at least one neighbor with opposite parity.
%H Alois P. Heinz, <a href="/A363236/b363236.txt">Table of n, a(n) for n = 0..465</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>
%F a(n) ~ phi^n * n! / (5^(1/4) * 2^(n-1)), where phi = A001622 is the golden ratio. - _Vaclav Kotesovec_, May 26 2023
%e a(0) = 1: (), the empty permutation.
%e a(1) = 0.
%e a(2) = 2: 12, 21.
%e a(3) = 2: 123, 321.
%e a(4) = 16: 1234, 1243, 1423, 1432, 2134, 2143, 2314, 2341, 3214, 3241, 3412, 3421, 4123, 4132, 4312, 4321.
%e a(5) = 36: 12345, 12354, 12534, 12543, 14325, 14352, 14523, 14532, 21345, 21543, 23145, 23541, 25143, 25341, 32145, 32154, 32514, 32541, 34125, 34152, 34512, 34521, 41325, 41523, 43125, 43521, 45123, 45321, 52134, 52143, 52314, 52341, 54123, 54132, 54312, 54321.
%Y Cf. A001622, A092186, A363180, A363181.
%K nonn
%O 0,3
%A _Alois P. Heinz_, May 22 2023