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.

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

Offset: 0

Author

Naohiro Nomoto, Dec 25 2001

Keywords

• nonn
• nice
• more

Comments

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

Examples

			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.
		

Crossrefs

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

Programs

Haskell

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

MATLAB

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

Mathematica

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

PARI

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

Python

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

Extensions

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