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

Author

R. H. Hardin, Jun 06 2013

Keywords

• nonn

Examples

			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
		

Links

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

Crossrefs

Column 2 of A226441.

Programs

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

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

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

Extensions

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