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

%I #48 Jun 05 2024 01:25:05

%S 0,1,3,10,25,66,154,372,837,1930,4246,9516,20618,45332,97140,210664,

%T 447661,960858,2028478,4319100,9070110,19188796,40122028,84438360,

%U 175913250,368603716,765561564,1598231992,3310623412,6889682280,14238676712,29551095248

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

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

%H Fung Lam, <a href="/A130783/b130783.txt">Table of n, a(n) for n = 0..3000</a>

%H F. Disanto, A. Frosini, and S. Rinaldi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Rinaldi/square.html">Square involutions</a>, J. Int. Seq. 14 (2011) # 11.3.5.

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

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

%F G.f.: (1-sqrt((1-2*x)/(1+2*x)))/(2*(1-2*x)^2). - _Vladeta Jovovic_, Aug 24 2007

%F Asymptotics: a(n) ~ 2^(n-1)*(n+1-sqrt(2*n/Pi)). - _Fung Lam_, Mar 28 2014

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

%F a(2n) = A303602(n). a(2n+1) = A033504(n). - _R. J. Mathar_, Nov 20 2020

%e a(1)=1 because 0 1 has a first difference of 1;

%e a(2)=3 because 2 0 1 has a second difference of 3.

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

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

%o (PARI) a(n)=(n+1)*(2^n-binomial(n,n\2))/2 \\ _Charles R Greathouse IV_, Jan 30 2012

%o (Python)

%o from math import comb

%o def A130783(n): return (n+1)*((1<<n)-comb(n,n>>1))>>1 # _Chai Wah Wu_, Jun 04 2024

%Y Cf. A000346, A033504.

%K nonn,easy

%O 0,3

%A _R. H. Hardin_, Aug 19 2007