A130783 Maximum value of the n-th difference of a permutation of 0..n.

0, 1, 3, 10, 25, 66, 154, 372, 837, 1930, 4246, 9516, 20618, 45332, 97140, 210664, 447661, 960858, 2028478, 4319100, 9070110, 19188796, 40122028, 84438360, 175913250, 368603716, 765561564, 1598231992, 3310623412, 6889682280, 14238676712, 29551095248

Offset: 0

Author

R. H. Hardin, Aug 19 2007

Keywords

• nonn
• easy

Comments

For n>1, a(n) is also the maximum value of the n-th difference of a permutation of 1..n. - Michel Marcus, Apr 15 2017

Examples

			a(1)=1 because 0 1 has a first difference of 1;
a(2)=3 because 2 0 1 has a second difference of 3.
		

Links

• Fung Lam, Table of n, a(n) for n = 0..3000
• F. Disanto, A. Frosini, and S. Rinaldi, Square involutions, J. Int. Seq. 14 (2011) # 11.3.5.

Crossrefs

Cf. A000346, A033504.

Programs

Maple

A130783:=n->(n+1)*(2^n-binomial(n,floor(n/2)))/2; seq(A130783(n), n=0..50); # Wesley Ivan Hurt, Nov 25 2013

Mathematica

Table[(n + 1) (2^n - Binomial[n, Floor[n/2]])/2, {n, 0, 50}] (* Wesley Ivan Hurt, Nov 25 2013 *)

PARI

a(n)=(n+1)*(2^n-binomial(n,n\2))/2 \\ Charles R Greathouse IV, Jan 30 2012

Python

from math import comb
def A130783(n): return (n+1)*((1<>1))>>1 # Chai Wah Wu, Jun 04 2024

Formula

a(n) = (n+1)*(2^(n-1)-binomial(n-1,n/2)) if n is even else ((n+1)/2)*(2^n-binomial(n,(n+1)/2)). - Vladeta Jovovic, Aug 23 2007

a(n) = (n+1)*(2^n-binomial(n,[n/2]))/2, where [x] is floor. - Graeme McRae, Jan 30 2012

G.f.: (1-sqrt((1-2*x)/(1+2*x)))/(2*(1-2*x)^2). - Vladeta Jovovic, Aug 24 2007

Asymptotics: a(n) ~ 2^(n-1)*(n+1-sqrt(2*n/Pi)). - Fung Lam, Mar 28 2014

D-finite with recurrence (n-1)*n*a(n) = 2*(n-1)*(n+1)*a(n-1) + 4*(n-2)*n*a(n-2) - 8*(n-1)*n*a(n-3). - Vaclav Kotesovec, Mar 28 2014

a(2n) = A303602(n). a(2n+1) = A033504(n). - R. J. Mathar, Nov 20 2020