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

Author

Nathaniel Johnston, Apr 20 2011

Keywords

• easy
• nonn

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).

Examples

			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.
		

Links

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

Crossrefs

Cf. A066411, A099325, A189390, A189391.

Programs

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 *)

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