A189162 The maximum possible value for the apex of a triangle of numbers whose base consists of a permutation of the numbers 1 to n, and each number in a higher row is the sum of the two numbers directly below it.

1, 3, 9, 24, 61, 148, 350, 808, 1837, 4116, 9130, 20056, 43746, 94760, 204188, 437712, 934525, 1987252, 4212338, 8900344, 18756886, 39426168, 82693924, 173071024, 361567186, 753984648, 1569877860, 3263572848, 6775522852, 14047800016, 29091783096, 60175932320

Offset

1,2

Comments

The maximum is attained by the triangle with base 1, 3, 5, ..., 2*ceiling(n/2)-1, 2*floor(n/2), ..., 6, 4, 2 (i.e., odd numbers increasing, followed by even numbers decreasing).

Links

Nathaniel Johnston, Table of n, a(n) for n = 1..1000

Formula

a(n) = 2^(n-1) + A189390(n-1).

D-finite with recurrence (-n+1)*a(n) +4*(n-1)*a(n-1) -12*a(n-2) +16*(-n+4)*a(n-3) +16*(n-4)*a(n-4)=0. - R. J. Mathar, Jun 17 2021

Example

For n = 5 consider the triangle:
         61
       29  32
     12  17  15
    4   8   9   6
  1   3   5   4   2
This triangle has 61 at its apex and no other such triangle with the numbers 1 - 5 on its base has a larger apex value, so a(5) = 61.

Maple

a:=proc(n)return 2^(n-1) + add((4*k+1)*binomial(n-1, k), k=0..floor(n/2)-1) + `if`(n mod 2=1, (n-1)*binomial(n-1, (n-1)/2), 0):end:
seq(a(n), n=1..50);

Mathematica

a[n_] := a[n] = Switch[n, 1, 1, 2, 3, 3, 9, 4, 24, _, (1/(n-1))*(4((4n-16)a[n-4] - (4n-16)a[n-3] - 3a[n-2] + (n-1)a[n-1]))];
Table[a[n], {n, 1, 50}] (* Jean-François Alcover, May 09 2023, after R. J. Mathar *)

Crossrefs

Cf. A066411, A099325, A189390, A189391.

Sequence in context: A228820 A335470 A003262 * A079282 A117585 A317474

Adjacent sequences: A189159 A189160 A189161 * A189163 A189164 A189165

Keyword

easy,nonn

Author

Nathaniel Johnston, Apr 20 2011

Status

approved