A245377 - OEIS

%I #32 Feb 19 2024 21:49:04

%S 1,1,0,0,1,4,17,80,422,2480,16095,114432,884969,7398464,66502048,

%T 639653632,6556170841,71340409600,821408397105,9977630263296,

%U 127518757153174,1710576547456000,24030971882538671,352843606806499328

%N Number of 2-alternating permutations of 1,2,...,n, that is, a(n) is the number of down/up permutations (A000111) of 1,2,...,n such that any two consecutive terms differ by at least two.

%e For n=5 there are the four permutations 31425, 31524, 52413, 42513.

%p b:= proc(n, s, t) option remember; `if`(s={}, 1, add(

%p      `if`(t*(n-j)>=2, b(j, s minus{j}, -t), 0), j=s))

%p     end:

%p a:= n->`if`(n=0, 1, add(b(j, {$1..j-1, $j+1..n}, 1), j=1..n)):

%p seq(a(n), n=0..16);  # _Alois P. Heinz_, Oct 27 2014

%t b[n_, s_, t_] := b[n, s, t] = If[s == {}, 1, Sum[If[t*(n - j) >= 2, b[j, s ~Complement~ {j}, -t], 0], {j, s}]]; a[n_] := a[n] = If[n == 0, 1, Sum[b[j, DeleteCases[Range[n], j], 1], {j, 1, n}]]; Table[Print[a[n]]; a[n], {n, 0, 16}] (* _Jean-François Alcover_, Oct 24 2016, after _Alois P. Heinz_ *)

%o (C++) #include <iostream>

%o #include <algorithm>

%o #include <vector>

%o using namespace std;

%o bool isA245377(const vector<int> per)

%o {

%o     bool good=true;

%o     for(int i=0 ; i < per.size() -1 && good ;i++)

%o     {

%o         if( abs(per[i]-per[i+1]) < 2 )

%o             good = false;

%o         else

%o         {

%o             if ( i %2 )

%o             {

%o                 if ( per[i+1] > per[i])

%o                     good = false;

%o             }

%o             else

%o             {

%o                 if ( per[i+1] < per[i])

%o                     good = false;

%o             }

%o         }

%o     }

%o     return good ;

%o }

%o int A245377(const int n)

%o {

%o     vector<int> per(n) ;

%o     for(int i=0 ; i < n ; i++)

%o         per[i] = i+1 ;

%o     int a= isA245377(per) ? 1 : 0 ;

%o     while( next_permutation(per.begin(),per.end()) )

%o     {

%o         if ( isA245377(per) )

%o             a++ ;

%o     }

%o     return a;

%o }

%o int main(int argc, char *argv[])

%o {

%o     for (int n=1 ; ; n++)

%o         cout << A245377(n) << endl ;

%o } // _R. J. Mathar_, Oct 25 2014

%Y Cf. A002464.

%K nonn,more

%O 0,6

%A _Richard Stanley_, Jul 19 2014

%E a(11)-a(15) from _R. J. Mathar_, Oct 27 2014

%E a(16)-a(21) from _Alois P. Heinz_, Oct 27 2014

%E a(22) from _Alois P. Heinz_, Feb 18 2024

%E a(23) from _Max Alekseyev_, Feb 19 2024