Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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