A257198 Number of permutations of length n having exactly one descent such that the first element of the permutation is an odd number.

0, 0, 2, 6, 16, 36, 78, 162, 332, 672, 1354, 2718, 5448, 10908, 21830, 43674, 87364, 174744, 349506, 699030, 1398080, 2796180, 5592382, 11184786, 22369596, 44739216, 89478458, 178956942, 357913912, 715827852, 1431655734, 2863311498, 5726623028

Offset: 1

Author

Ran Pan, Apr 18 2015

Keywords

• nonn
• easy

Examples

			a(3)=2: (1 3 2, 3 1 2).
a(4)=6: (1 2 4 3, 1 3 2 4, 1 4 2 3, 1 3 4 2, 3 1 2 4, 3 4 1 2).
		

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,2).

Crossrefs

Cf. A178420, A000295, A000975, A167030 (first differences).

Programs

Magma

[2*Floor((2*2^n-3*n-1)/6): n in [1..40]]; // Vincenzo Librandi, Apr 18 2015

Mathematica

Table[2 Floor[(2 2^n - 3 n - 1) / 6], {n, 50}] (* Vincenzo Librandi, Apr 18 2015 *)

PARI

concat([0,0], Vec(-2*x^3/((x-1)^2*(x+1)*(2*x-1)) + O(x^100))) \\ Colin Barker, Apr 19 2015

PARI

a(n)=(2<Charles R Greathouse IV, Apr 21 2015

Formula

a(n) = 2*floor((2*2^n-3*n-1)/6).

a(n) = 2*A178420(n-1).

a(n) = A000295(n)-A000975(n-1).

From Colin Barker, Apr 19 2015: (Start)

a(n) = (-3-(-1)^n+2^(2+n)-6*n)/6.

a(n) = 3*a(n-1)-a(n-2)-3*a(n-3)+2*a(n-4).

G.f.: -2*x^3 / ((x-1)^2*(x+1)*(2*x-1)).

(End)