login
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.
8

%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