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

%I #37 Jul 17 2024 18:36:14

%S 1,1,2,6,22,90,422,2226,13102,85170,606542,4697946,39330982,353985450,

%T 3408792662,34975509666,380947661662,4390028664930,53368010874782,

%U 682564606249386,9162253729773142,128794752680027610,1892150024227428902,28998220554100469106

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

%H Alois P. Heinz, <a href="/A226435/b226435.txt">Table of n, a(n) for n = 0..484</a> (terms n = 1..210 from R. H. Hardin)

%F E.g.f. (conjecture): (sec(x) + tan(x)) - (sec(x) + tan(x))^2 + (sec(x) + tan(x))^3. - _Sergei N. Gladkovskii_, Jun 11 2015

%F a(n) ~ n! * 2^(n+4) * n / Pi^(n+2). - _Vaclav Kotesovec_, Jun 11 2015

%F 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

%e Some solutions for n=9:

%e ..1...9...4...3...2...6...1...4...2...7...3...3...2...6...5....6

%e ..7...2...7...1...5...3...7...1...5...2...8...1...3...1...4....3

%e ..2...3...5...6...6...9...2...6...3...8...6...9...1...4...8....8

%e ..4...1...6...4...3...1...5...5...1...6...9...4...5...3...1....1

%e ..9...6...1...7...7...7...3...8...9...5...1...8...4...5...2....7

%e ..5...5...9...9...4...5...9...3...6...9...5...5...9...7...9....4

%e ..8...7...2...2...8...8...8...2...7...1...2...2...6...2...3....5

%e ..3...4...8...8...1...4...4...9...4...4...7...7...8...9...7....9

%e ..6...8...3...5...9...2...6...7...8...3...4...6...7...8...6....2

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

%t {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 *)

%o (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 */

%Y Column 2 of A226441.

%K nonn

%O 0,3

%A _R. H. Hardin_, Jun 06 2013

%E a(0)=1 prepended by _Alois P. Heinz_, Jul 17 2024