A189162 -id:A189162 - 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

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.

Original entry on oeis.org

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

Offset: 0

Nathaniel Johnston, Apr 20 2011

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.

			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.

Nathaniel Johnston, Table of n, a(n) for n = 0..1000
Steven Finch, How far might we walk at random?, arXiv:1802.04615 [math.HO], 2018.

Cf. A066411, A099325, A189162, A189391.

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

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

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

from math import comb
def A189390(n): return sum(((k<<2)|1)*comb(n,k) for k in range(n+1>>1))+(0 if n&1 else n*comb(n,n>>1)) # Chai Wah Wu, Oct 28 2024

a(n) = Sum_{k=0..floor((n-1)/2)} (4*k+1)*C(n,k) + (n+1 mod 2)*n*C(n,n/2).
a(n) = n*2^n-A189391(n). - M. F. Hasler, Jan 24 2012
a(n) = Sum_{k=0..n} k * C(n,floor(k/2)) = Sum_{k=0..n} k*A107430(n,k). - Alois P. Heinz, Feb 02 2012
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

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

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

A375659 For 0<=k<=n, T(n,k) = the number of Dyck-type lattice paths of length n, starting at the point (0,k), triangle T read by rows.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 3, 6, 7, 8, 6, 10, 14, 15, 16, 10, 20, 25, 30, 31, 32, 20, 35, 50, 56, 62, 63, 64, 35, 70, 91, 112, 119, 126, 127, 128, 70, 126, 182, 210, 238, 246, 254, 255, 256, 126, 252, 336, 420, 456, 492, 501, 510, 511, 512, 252, 462, 672, 792, 912, 957, 1002, 1012, 1022, 1023, 1024

Offset: 0

Marilena Jianu, Aug 23 2024

A Dyck type lattice path has the steps (1,1) or (1,-1) and never passes below the x-axis.
For k>=n, the number of Dyck-type lattice paths is 2^n.
The sequence completes A322291 by adding a diagonal of powers of 2.

			  n | k=0    1    2    3    4    5    6    7
 ---+---------------------------------------
  0 |  1
  1 |  1    2
  2 |  2    3    4
  3 |  3    6    7    8
  4 |  6   10   14   15   16
  5 | 10   20   25   30   31   32
  6 | 20   35   50   56   62   63   64
  7 | 35   70   92  112  119  126  127  128

John Tyler Rascoe, Rows n = 0..140, flattened

T(n,0) = T(n-1,1) = A001405(n).
T(n,n) = A000079(n).
T(n,n-1) = A000225(n).
T(n,n-2) = A000918(n).
T(n,n-3) = A000247(n).
T(n,n-4) = A052515(n).
Row sums = A189162(n+1).
Cf. A322291, A368175.

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

from math import comb
def A375659(n,k):
    return sum(comb(n,i+(n-k)//2) for i in range(k+1)) # John Tyler Rascoe, Sep 04 2024

T(n,k) = Sum_{i = 0..k} binomial(n, floor((n-k)/2)+i).

T(n,k) = T(n-1,k-1)+T(n-1,k+1), for all n>=2 and 1<=k<=n-2.

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

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

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

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

A375659 For 0<=k<=n, T(n,k) = the number of Dyck-type lattice paths of length n, starting at the point (0,k), triangle T read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Formula

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