A245377 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.

1, 1, 0, 0, 1, 4, 17, 80, 422, 2480, 16095, 114432, 884969, 7398464, 66502048, 639653632, 6556170841, 71340409600, 821408397105, 9977630263296, 127518757153174, 1710576547456000, 24030971882538671, 352843606806499328

Offset

0,6

Links

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

Example

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

Maple

b:= proc(n, s, t) option remember; `if`(s={}, 1, add(
     `if`(t*(n-j)>=2, b(j, s minus{j}, -t), 0), j=s))
    end:
a:= n->`if`(n=0, 1, add(b(j, {$1..j-1, $j+1..n}, 1), j=1..n)):
seq(a(n), n=0..16);  # Alois P. Heinz, Oct 27 2014

Mathematica

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 *)

Prog

(C++) #include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool isA245377(const vector<int> per)
{
    bool good=true;
    for(int i=0 ; i < per.size() -1 && good ; i++)
    {
        if( abs(per[i]-per[i+1]) < 2 )
            good = false;
        else
        {
            if ( i %2 )
            {
                if ( per[i+1] > per[i])
                    good = false;
            }
            else
            {
                if ( per[i+1] < per[i])
                    good = false;
            }
        }
    }
    return good ;
}
int A245377(const int n)
{
    vector<int> per(n) ;
    for(int i=0 ; i < n ; i++)
        per[i] = i+1 ;
    int a= isA245377(per) ? 1 : 0 ;
    while( next_permutation(per.begin(), per.end()) )
    {
        if ( isA245377(per) )
            a++ ;
    }
    return a;
}
int main(int argc, char *argv[])
{
    for (int n=1 ; ; n++)
        cout << A245377(n) << endl ;
} // R. J. Mathar, Oct 25 2014

Crossrefs

Cf. A002464.

Sequence in context: A056096 A257084 A371915 * A351150 A204326 A151250

Adjacent sequences: A245374 A245375 A245376 * A245378 A245379 A245380

Keyword

nonn,more

Author

Richard Stanley, Jul 19 2014

Extensions

a(11)-a(15) from R. J. Mathar, Oct 27 2014

a(16)-a(21) from Alois P. Heinz, Oct 27 2014

a(22) from Alois P. Heinz, Feb 18 2024

a(23) from Max Alekseyev, Feb 19 2024

Status

approved