A206604 Number of integers in the smallest interval containing both minimal and maximal possible apex values of an addition triangle whose base is a permutation of n+1 consecutive integers.

1, 1, 3, 9, 27, 73, 189, 465, 1115, 2601, 5973, 13489, 30149, 66641, 146233, 318369, 689403, 1484137, 3181797, 6790641, 14445101, 30617841, 64724553, 136426849, 286926757, 601999633, 1260707529, 2634831585, 5497982025, 11452601761, 23823827825, 49484904257

Offset: 0

Author

Alois P. Heinz, Feb 10 2012

Keywords

• nonn

Comments

For n>0 the base row of the addition triangle may contain a permutation of any set {b+k, k=0..n} where b is an integer or a half-integer. Each number in a higher row is the sum of the two numbers directly below it. Rows above the base row contain only integers.

a(n) = 3 (mod 4) if n = 2^m with m > 0 and a(n) = 1 (mod 4) else.

Examples

			a(3) =  9:   max:   20          min:   12
                  9   11             7   5
                3   6   5          5   2   3
             1/2 5/2 7/2 3/2    7/2 3/2 1/2 5/2
[12, 13, ..., 20] contains 20-12+1 = 9 integers.
a(4) = 27:   max:   13          min:  -13
                   5  8              -5 -8
                 0  5  3            0 -5 -3
              -2  2  3  0         2 -2 -3  0
            -2  0  2  1 -1      2  0 -2 -1  1
[-13, -12, ..., 13] contains 13-(-13)+1 = 27 integers.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A189390, A189391, A206603.

Programs

Maple

a:= n-> 1 +add(binomial(n, floor(k/2))*(2*k-n), k=0..n):
seq(a(n), n=0..40);
# second Maple program
a:= proc(n) option remember; `if`(n<3, 1+n*(n-1),
      (3*n^2-6*n+6+(2*n^2-6)*a(n-1)+4*(n-1)*(n-4)*a(n-2)
      -8*(n-1)*(n-2)*a(n-3)) / (n*(n-2)))
    end:
seq(a(n), n=0..40); # Alois P. Heinz, Apr 25 2013

Mathematica

a = DifferenceRoot[Function[{y, n}, {(-2n^2 - 12n - 12) y[n+2] - 3n^2 + 8(n+1)(n+2) y[n] - 4(n-1)(n+2) y[n+1] + (n+1)(n+3) y[n+3] - 12n - 15 == 0, y[0] == 1, y[1] == 1, y[2] == 3, y[3] == 9}]];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Dec 20 2020, after Alois P. Heinz *)

PARI

a(n) = 1 + sum(k=0, n, binomial(n, k\2)*(2*k-n)); \\ Michel Marcus, Dec 20 2020

Python

from math import comb
def A206604(n): return sum(comb(n,k>>1)*((k<<1)-n) for k in range(n+1))+1 # Chai Wah Wu, Oct 28 2024

Formula

a(n) = 1 + Sum_{k=0..n} C(n,floor(k/2)) * (2*k-n).

G.f.: 1/(1-x) + (1-sqrt(1-4*x^2)) / (2*x-1)^2.

a(n) = 1 + 2*A206603(n).

a(n) = 1 + A189390(n)-A189391(n).

a(n) ~ n*2^n * (1-2*sqrt(2)/sqrt(Pi*n)). - Vaclav Kotesovec, Mar 15 2014