|
|
A189390
|
|
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
|
|
|
0, 1, 5, 16, 45, 116, 286, 680, 1581, 3604, 8106, 18008, 39650, 86568, 187804, 404944, 868989, 1856180, 3950194, 8376056, 17708310, 37329016, 78499620, 164682416, 344789970, 720430216, 1502768996, 3129355120, 6507087396, 13510929104
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
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.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k=0..floor((n-1)/2)} (4*k+1)*C(n,k) + (n+1 mod 2)*n*C(n,n/2).
G.f.: (2*x-sqrt(1-4*x^2)+1) / (2*(2*x-1)^2). - Alois P. Heinz, Feb 09 2012
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
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
a(n) = Sum_{k=1..n} Sum_{i=1..k} C(n,floor((n-k)/2)+i). - Stefano Spezia, Aug 20 2019
|
|
EXAMPLE
|
For n = 4 consider the triangle:
45
21 24
8 13 11
2 6 7 4
0 2 4 3 1
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.
|
|
MAPLE
|
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:
seq(a(n), n=0..50);
|
|
MATHEMATICA
|
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 *)
|
|
PROG
|
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|