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,3

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

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.

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

Example

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.

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

Prog

(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<<n)-comb(n, n>>1))>>1 # Chai Wah Wu, Jun 04 2024

Crossrefs

Cf. A000346, A033504.

Sequence in context: A089117 A176610 A026965 * A026975 A296668 A026985

Adjacent sequences: A130780 A130781 A130782 * A130784 A130785 A130786

Keyword

nonn,easy

Author

R. H. Hardin, Aug 19 2007

Status

approved