A226435 Number of permutations of {1..n} with fewer than 2 interior elements having values lying between the values of their neighbors.

1, 1, 2, 6, 22, 90, 422, 2226, 13102, 85170, 606542, 4697946, 39330982, 353985450, 3408792662, 34975509666, 380947661662, 4390028664930, 53368010874782, 682564606249386, 9162253729773142, 128794752680027610, 1892150024227428902, 28998220554100469106

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..484 (terms n = 1..210 from R. H. Hardin)

Formula

E.g.f. (conjecture): (sec(x) + tan(x)) - (sec(x) + tan(x))^2 + (sec(x) + tan(x))^3. - Sergei N. Gladkovskii, Jun 11 2015

a(n) ~ n! * 2^(n+4) * n / Pi^(n+2). - Vaclav Kotesovec, Jun 11 2015

a(n) = Sum_{i=0..(n-2)/2}((n-2*i-1)*Sum_{j=0..2*i}((-1)^(j+i)*2^(-n-j+2*i+2)*Stirling2(n,n+j-2*i)*binomial(n+j-2*i-1,n-2*i-1)*(n+j-2*i)!)), n > 1, a(1)=1. - Vladimir Kruchinin, Apr 08 2016

Example

Some solutions for n=9:
..1...9...4...3...2...6...1...4...2...7...3...3...2...6...5....6
..7...2...7...1...5...3...7...1...5...2...8...1...3...1...4....3
..2...3...5...6...6...9...2...6...3...8...6...9...1...4...8....8
..4...1...6...4...3...1...5...5...1...6...9...4...5...3...1....1
..9...6...1...7...7...7...3...8...9...5...1...8...4...5...2....7
..5...5...9...9...4...5...9...3...6...9...5...5...9...7...9....4
..8...7...2...2...8...8...8...2...7...1...2...2...6...2...3....5
..3...4...8...8...1...4...4...9...4...4...7...7...8...9...7....9
..6...8...3...5...9...2...6...7...8...3...4...6...7...8...6....2

Mathematica

CoefficientList[Series[Sec[x]+Tan[x] - (Sec[x]+Tan[x])^2 + (Sec[x]+Tan[x])^3, {x, 0, 20}], x] * Range[0, 20]! (* Vaclav Kotesovec, Jun 11 2015 after Sergei N. Gladkovskii, all 210 terms match those in the b-file *)
{1}~Join~Table[Sum[(n - 2 i - 1) Sum[(-1)^(j + i)*2^(-n - j + 2 i + 2) StirlingS2[n, n + j - 2 i] Binomial[n + j - 2 i - 1, n - 2 i - 1] (n + j - 2 i)!, {j, 0, 2 i}], {i, 0, (n - 2)/2}], {n, 2, 22}] (* Michael De Vlieger, Apr 08 2016 *)

Prog

(Maxima) a(n):=sum((n-2*i-1)*sum((-1)^(j+i)*2^(-n-j+2*i+2)*stirling2(n, n+j-2*i)*binomial(n+j-2*i-1, n-2*i-1)*(n+j-2*i)!, j, 0, 2*i), i, 0, (n-2)/2); /* Vladimir Kruchinin, Apr 08 2016 */

Crossrefs

Column 2 of A226441.

Sequence in context: A264601 A374551 A308564 * A292318 A150271 A150272

Adjacent sequences: A226432 A226433 A226434 * A226436 A226437 A226438

Keyword

nonn

Author

R. H. Hardin, Jun 06 2013

Extensions

a(0)=1 prepended by Alois P. Heinz, Jul 17 2024

Status

approved