A189390 -id:A189390 - cp's OEIS frontend

A189391 The minimum 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.

0, 1, 3, 8, 19, 44, 98, 216, 467, 1004, 2134, 4520, 9502, 19928, 41572, 86576, 179587, 372044, 768398, 1585416, 3263210, 6711176, 13775068, 28255568, 57863214, 118430584, 242061468, 494523536, 1009105372, 2058327344, 4194213448

Offset: 0

Nathaniel Johnston, Apr 20 2011

This is the Riordan transform of A000217 (triangular numbers) with the Riordan matrix (of the Bell type) A053121 (inverse of the Chebyshev S Bell matrix). See the resulting formulae below. - Wolfdieter Lang, Feb 18 2017.

Conjecture: a(n) is also half the sum of the "cuts-resistance" (see A319416, A319420, A319421) of all binary vectors of length n (see Lenormand, page 4). - N. J. A. Sloane, Sep 20 2018

			For n = 4 consider the triangle:
....19
...8  11
..5  3  8
.4  1 2  6
3  1 0 2  4
This triangle has 19 at its apex and no other such triangle with the numbers 0 - 4 on its base has a smaller apex value, so a(4) = 19.

Nathaniel Johnston, Table of n, a(n) for n = 0..1000
F. Disanto and S. Rinaldi, Symmetric convex permutominoes and involutions, PU. M. A., Vol. 22 (2011), No. 1, pp. 39-60. - From _N. J. A. Sloane_, May 04 2012
Steven R. Finch, How far might we walk at random?, arXiv:1802.04615 [math.HO], 2018.
Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003. - _N. J. A. Sloane_, Sep 20 2018

Cf. A066411, A099325, A189390, A189162, A000217, A053121, A281862.

Cf. also A319416, A319420, A319421.

m:=30; R:=PowerSeriesRing(Rationals(), m); [0] cat Coefficients(R!((2*x+Sqrt(1-4*x^2)-1)/(2*(2*x-1)^2))); // G. C. Greubel, Aug 24 2018

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

CoefficientList[Series[(2*x+Sqrt[1-4*x^2]-1) / (2*(2*x-1)^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 16 2014 *)

A189391(n)=sum(i=0,(n-1)\2,(2*n-4*i-1)*binomial(n,i))  \\ M. F. Hasler, Jan 24 2012

If n even, a(n) = (n+1/2)*binomial(n,n/2) - 2^(n-1); if n odd, a(n) = ((n+1)/2)*binomial(n+1,(n+1)/2) - 2^(n-1). - N. J. A. Sloane, Nov 01 2018
a(n) = Sum_{k=0..floor((n-1)/2)} (2*n-4*k-1)*binomial(n,k).
G.f.: (2*x+sqrt(1-4*x^2)-1) / (2*(2*x-1)^2). - Alois P. Heinz, Feb 09 2012
a(n) ~ 2^n * (sqrt(2n/Pi)- 1/2). - Vaclav Kotesovec, Mar 16 2014 (formula simplified by Lewis Chen, May 25 2017)
D-finite with recurrence n*a(n) + (n-5)*a(n-1) + 2*(-5*n+6)*a(n-2) + 4*(-n+8)*a(n-3) + 24*(n-3)*a(n-4) = 0. - R. J. Mathar, Jan 04 2017
From Wolfdieter Lang, Feb 18 2017:(Start)
a(n) = Sum_{m=0..n} A053121(n, m)*A000217(m), n >= 0.
G.f.: c(x^2)*Tri(x*c(x^2)), with c and Tri the g.f. of A000108 and A000217, respectively. See the explicit form of the g.f. given above by Alois P. Heinz.
(End)
2*a(n) = A152548(n)-2^n. - R. J. Mathar, Jun 17 2021

A066411 Form a triangle with the numbers [0..n] on the base, where each number is the sum of the two below; a(n) is the number of different possible values for the apex.

Original entry on oeis.org

1, 1, 3, 5, 23, 61, 143, 215, 995, 2481, 5785, 12907, 29279, 64963, 144289, 158049, 683311, 1471123, 3166531, 6759177, 14404547, 30548713

Offset: 0

Naohiro Nomoto, Dec 25 2001

a(n) is the number of different possible sums of c_k * (n choose k) where the c_k are a permutation of 0 through n. - Joshua Zucker, May 08 2006

			For n = 2 we have three triangles:
..4.......5.......3
.1,3.....2,3.....2,1
0,1,2...0,2,1...2,0,1
with three different values for the apex, so a(2) = 3.

Cf. A062684, A062896, A099325, A189162, A189390 (maximum apex value), A189391 (minimum apex value).

import Data.List (permutations, nub)
a066411 0 = 1
a066411 n = length $ nub $ map
   apex [perm | perm <- permutations [0..n], head perm < last perm] where
   apex = head . until ((== 1) . length)
                       (\xs -> (zipWith (+) xs $ tail xs))
-- Reinhard Zumkeller, Jan 24 2012

for n=0:9
size(unique(perms(0:n)*diag(fliplr(pascal(n+1)))),1)
end % Nathaniel Johnston, Apr 20 2011
(C++)
#include 
#include 
#include 
#include 
using namespace std;
inline long long pascApx(const vector & s)
{
    const int n = s.size() ;
    vector scp(n) ;
    for(int i=0; i s;
        for(int i=0;i apx;
        do
        {
            apx.insert( pascApx(s)) ;
        } while( next_permutation(s.begin(),s.end()) ) ;
        cout << n << " " << apx.size() << endl ;
    }
    return 0 ;
} /* R. J. Mathar, Jan 24 2012 */

g[s_List] := Plus @@@ Partition[s, 2, 1]; f[n_] := Block[{k = 1, lmt = 1 + (n + 1)!, lst = {}, p = Permutations[Range[0, n]]}, While[k < lmt, AppendTo[ lst, Nest[g, p[[k]], n][[1]]]; k++]; lst]; Table[ Length@ Union@ f@ n, {n, 0, 10}] (* Robert G. Wilson v, Jan 24 2012 *)

A066411(n)={my(u=0,o=A189391(n),v,b=vector(n++,i,binomial(n-1,i-1))~);sum(k=1,n!\2,!bittest(u,numtoperm(n,k)*b-o) & u+=1<<(numtoperm(n,k)*b-o))}  \\ M. F. Hasler, Jan 24 2012

from sympy import binomial
def partitionpairs(xlist): # generator of all partitions into pairs and at most 1 singleton, returning the sums of the pairs
    if len(xlist) <= 2:
        yield [sum(xlist)]
    else:
        m = len(xlist)
        for i in range(m-1):
            for j in range(i+1,m):
                rem = xlist[:i]+xlist[i+1:j]+xlist[j+1:]
                y = [xlist[i]+xlist[j]]
                for d in partitionpairs(rem):
                    yield y+d
def A066411(n):
    b = [binomial(n,k) for k in range(n//2+1)]
    return len(set((sum(d[i]*b[i] for i in range(n//2+1)) for d in partitionpairs(list(range(n+1)))))) # Chai Wah Wu, Oct 19 2021

More terms from John W. Layman, Jan 07 2003
a(10) from Nathaniel Johnston, Apr 20 2011
a(11) from Alois P. Heinz, Apr 21 2011
a(12) and a(13) from Joerg Arndt, Apr 21 2011
a(14)-a(15) from Alois P. Heinz, Apr 27 2011
a(0)-a(15) verified by R. H. Hardin Jan 27 2012
a(16) from Alois P. Heinz, Jan 28 2012
a(17)-a(21) from Graeme McRae, Jan 28, Feb 01 2012

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.

Original entry on oeis.org

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

Nathaniel Johnston, Apr 20 2011

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

			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.

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

Cf. A066411, A099325, A189390, A189391.

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

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

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

A049610 a(n) = Sum_{k=0..floor(n/2)} kbinomial(n,2k) = floor(n*2^(n-3)).

Original entry on oeis.org

0, 0, 1, 3, 8, 20, 48, 112, 256, 576, 1280, 2816, 6144, 13312, 28672, 61440, 131072, 278528, 589824, 1245184, 2621440, 5505024, 11534336, 24117248, 50331648, 104857600, 218103808, 452984832, 939524096, 1946157056, 4026531840, 8321499136, 17179869184, 35433480192

Offset: 0

M. F. Hasler, Jan 25 2012

Essentially same as A001792, except for leading zeros, which motivate the existence of this sequence on its own.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Silvana Ramaj, New Results on Cyclic Compositions and Multicompositions, Master's Thesis, Georgia Southern Univ., 2021. See p. 67.
Index entries for linear recurrences with constant coefficients, signature (4,-4).

Cf. A001792, A189162, A189390, A189391.

CoefficientList[Series[x^2*(1 - x)/(1 - 2*x)^2, {x, 0, 40}], x] (* Vincenzo Librandi, Jan 09 2013 *)

PARI
```
a(n)=n<<(n-3)
```

G.f. x^2*(1-x)/(1-2*x)^2. - Sergei N. Gladkovskii, Oct 18 2012
G.f.: x^2*( 1 + 2*x*U(0) ) where U(k) = 1 + (k+1)/(2 - 8*x/(4*x + (k+1)/U(k+1))); (continued fraction, 3-step). - Sergei N. Gladkovskii, Oct 19 2012
E.g.f.: x*(exp(2*x) - 1)/4. - Stefano Spezia, Feb 02 2023
Sum_{n>=2} 1/a(n) = 8*log(2) - 4. - Amiram Eldar, Feb 14 2023

A206603 Maximal apex value of an addition triangle whose base is a permutation of {k-n/2, k=0..n}.

Original entry on oeis.org

0, 0, 1, 4, 13, 36, 94, 232, 557, 1300, 2986, 6744, 15074, 33320, 73116, 159184, 344701, 742068, 1590898, 3395320, 7222550, 15308920, 32362276, 68213424, 143463378, 300999816, 630353764, 1317415792, 2748991012, 5726300880, 11911913912, 24742452128, 51331847709

Offset: 0

Alois P. Heinz, Feb 10 2012

nonn

The base row of the addition triangle contains a permutation of the n+1 integers or half-integers {k-n/2, k=0..n}.  Each number in a higher row is the sum of the two numbers directly below it.  Rows above the base row contain only integers.  The base row consists of integers iff n is even.
Because of symmetry, a(n) is also the absolute value of the minimal apex value of an addition triangle whose base is a permutation of {k-n/2, k=0..n}.
a(n) is odd iff n = 2^m and m > 0.

			a(3) =  4:   max:      4            min:    -4
                    1    3               -1   -3
                -1    2    1           1   -2   -1
            -3/2  1/2  3/2 -1/2    3/2 -1/2 -3/2  1/2
a(4) = 13:   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

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

Cf. A001787, A189390, A189391, A206604.

a:= n-> add (binomial(n, floor(k/2))*(k-n/2), k=0..n):
seq (a(n), n=0..40);
# second Maple program:
a:= proc(n) option remember; `if`(n<3, n*(n-1)/2,
      ((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

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

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

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

a(n) = Sum_{k=0..n} C(n,floor(k/2)) * (k-n/2).
G.f.: (1-sqrt(1-4*x^2)) / (2*(2*x-1)^2).
a(n) = A189390(n)-A001787(n) = A001787(n)-A189391(n) = (A189390(n)-A189391(n))/2 = (A206604(n)-1)/2.

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.

Original entry on oeis.org

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

Alois P. Heinz, Feb 10 2012

nonn

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.

			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.

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

Cf. A189390, A189391, A206603.

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

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

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

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

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

A322291 Triangle T read by rows: T(n, k) = Sum_{i=1..k} binomial(n, floor((n-k)/2)+i).

Original entry on oeis.org

1, 2, 3, 3, 6, 7, 6, 10, 14, 15, 10, 20, 25, 30, 31, 20, 35, 50, 56, 62, 63, 35, 70, 91, 112, 119, 126, 127, 70, 126, 182, 210, 238, 246, 254, 255, 126, 252, 336, 420, 456, 492, 501, 510, 511, 252, 462, 672, 792, 912, 957, 1002, 1012, 1022, 1023, 462, 924, 1254, 1584, 1749, 1914, 1969, 2024, 2035, 2046, 2047

Offset: 1

Stefano Spezia, Aug 28 2019

T(n, k) is a sharp upper bound on the cardinality of a k-antichain in {0, 1}^n due to P. Erdős.

T(n, k) is also the total number of compositions with first part k, n+1 parts, and all differences between adjacent parts in {-1,1}. - John Tyler Rascoe, May 07 2023

			n\k|   1    2    3    4    5    6
---+-----------------------------
1  |   1
2  |   2    3
3  |   3    6    7
4  |   6   10   14   15
5  |  10   20   25   30   31
6  |  20   35   50   56   62   63
...

John Tyler Rascoe, Rows n = 1..141 of the triangle, flattened
P. Erdős, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc., 51 (1945), 898-902.
C. Pelekis and V. Vlasák, On k-antichains in the unit n-cube, arXiv:1908.04727 [math.CA], 2019.

Cf. A000225 (diagonal), A189390 (row sums).

Cf. A000247, A000918, A001405, A006126, A007318, A052515, A052516, A263857, A272352, A306550.

Flat(List([1..11], n->List([1..n], k->Sum([1..k], i->Binomial(n, Int((n-k)/2)+i)))));

a:=(n, k)->sum(binomial(n, floor((1/2)*n-(1/2)*k)+i), i = 1..k): seq(seq(a(n, k), k = 1..n), n = 1..11);

T[n_,k_]:=Sum[Binomial[n,Floor[(n-k)/2]+i],{i,1,k}]; Table[T[n,k],{n,1,11},{k,1,n}]

T(n, k) = sum(i=1, k, binomial(n, floor((n-k)/2)+i));

T(n, n) = A000225(n).
T(n, n-1) = A000918(n).
T(n, n-2) = A000247(n).
T(n, n-3) = A052515(n).
T(n, n-4) = A272352(n+1).
T(n, n-5) = A052516(n).

cp's OEIS Frontend

A189391 The minimum 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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A066411 Form a triangle with the numbers [0..n] on the base, where each number is the sum of the two below; a(n) is the number of different possible values for the apex.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Haskell

MATLAB

Mathematica

PARI

Python

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A049610 a(n) = Sum_{k=0..floor(n/2)} k*binomial(n,2*k) = floor(n*2^(n-3)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A206603 Maximal apex value of an addition triangle whose base is a permutation of {k-n/2, k=0..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A049610 a(n) = Sum_{k=0..floor(n/2)} kbinomial(n,2k) = floor(n*2^(n-3)).