%I #55 Oct 28 2024 14:49:24
%S 0,1,5,16,45,116,286,680,1581,3604,8106,18008,39650,86568,187804,
%T 404944,868989,1856180,3950194,8376056,17708310,37329016,78499620,
%U 164682416,344789970,720430216,1502768996,3129355120,6507087396,13510929104
%N The maximum possible value for the apex of a triangle of numbers whose base consists of a permutation of the numbers 0 to n, and each number in a higher row is the sum of the two numbers directly below it.
%C The maximal value is reached when the largest numbers are placed in the middle and the smallest numbers at the border of the first row, i.e., [0,2,...,n,...,3,1]. Since the value of the apex is given as sum(c_k binomial(n,k)), one can compute this maximal value directly.
%H Nathaniel Johnston, <a href="/A189390/b189390.txt">Table of n, a(n) for n = 0..1000</a>
%H Steven Finch, <a href="https://arxiv.org/abs/1802.04615">How far might we walk at random?</a>, arXiv:1802.04615 [math.HO], 2018.
%F a(n) = Sum_{k=0..floor((n-1)/2)} (4*k+1)*C(n,k) + (n+1 mod 2)*n*C(n,n/2).
%F a(n) = n*2^n-A189391(n). - _M. F. Hasler_, Jan 24 2012
%F a(n) = Sum_{k=0..n} k * C(n,floor(k/2)) = Sum_{k=0..n} k*A107430(n,k). - _Alois P. Heinz_, Feb 02 2012
%F G.f.: (2*x-sqrt(1-4*x^2)+1) / (2*(2*x-1)^2). - _Alois P. Heinz_, Feb 09 2012
%F D-finite with recurrence n*a(n) -4*n*a(n-1) +12*a(n-2) +16*(n-3)*a(n-3) +16*(-n+3)*a(n-4)=0. - _R. J. Mathar_, Jul 28 2016
%F D-finite with recurrence n*(2*n-3)*a(n) +2*(-2*n^2-n+5)*a(n-1) +4*(-2*n^2+9*n-5)*a(n-2) +8*(2*n-1)*(n-2)*a(n-3)=0. - _R. J. Mathar_, Jul 28 2016
%F a(n) = Sum_{k=1..n} Sum_{i=1..k} C(n,floor((n-k)/2)+i). - _Stefano Spezia_, Aug 20 2019
%e For n = 4 consider the triangle:
%e 45
%e 21 24
%e 8 13 11
%e 2 6 7 4
%e 0 2 4 3 1
%e This triangle has 45 at its apex and no other such triangle with the numbers 0 through 4 on its base has a larger apex value, so a(4) = 45.
%p a:= proc(n) return add((4*k+1)*binomial(n,k), k=0..floor((n-1)/2)) + `if`(n mod 2=0, n*binomial(n,n/2), 0):end:
%p seq(a(n), n=0..50);
%t a[n_] := Sum[(4k+1)*Binomial[n, k], {k, 0, Floor[(n-1)/2]}] + If[EvenQ[n], n*Binomial[n, n/2], 0]; Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Feb 18 2017, translated from Maple *)
%o (PARI) A189390(n)=sum(i=0, (n-1)\2, (4*i+1)*binomial(n, i), if(!bittest(n,0),n*binomial(n, n\2))) \\ - _M. F. Hasler_, Jan 24 2012
%o (Python)
%o from math import comb
%o def A189390(n): return sum(((k<<2)|1)*comb(n,k) for k in range(n+1>>1))+(0 if n&1 else n*comb(n,n>>1)) # _Chai Wah Wu_, Oct 28 2024
%Y Cf. A066411, A099325, A189162, A189391.
%K easy,nonn,changed
%O 0,3
%A _Nathaniel Johnston_, Apr 20 2011