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

%I #72 Oct 20 2021 00:31:37

%S 1,1,3,5,23,61,143,215,995,2481,5785,12907,29279,64963,144289,158049,

%T 683311,1471123,3166531,6759177,14404547,30548713

%N 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.

%C 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

%e For n = 2 we have three triangles:

%e ..4.......5.......3

%e .1,3.....2,3.....2,1

%e 0,1,2...0,2,1...2,0,1

%e with three different values for the apex, so a(2) = 3.

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

%o (MATLAB)

%o for n=0:9

%o size(unique(perms(0:n)*diag(fliplr(pascal(n+1)))),1)

%o end % _Nathaniel Johnston_, Apr 20 2011

%o (C++)

%o #include <iostream>

%o #include <vector>

%o #include <set>

%o #include <algorithm>

%o using namespace std;

%o inline long long pascApx(const vector<int> & s)

%o {

%o const int n = s.size() ;

%o vector<long long> scp(n) ;

%o for(int i=0; i<n; i++)

%o scp[i] = s[i] ;

%o for(int i=1; i<n; i++)

%o for(int acc=0 ; acc < n-i ; acc++)

%o scp[acc] += scp[acc+1] ;

%o return scp[0] ;

%o }

%o int main(int argc, char *argv[])

%o {

%o for(int n=1 ; ;n++)

%o {

%o vector<int> s;

%o for(int i=0;i<n;i++)

%o s.push_back(i) ;

%o set<long long> apx;

%o do

%o {

%o apx.insert( pascApx(s)) ;

%o } while( next_permutation(s.begin(),s.end()) ) ;

%o cout << n << " " << apx.size() << endl ;

%o }

%o return 0 ;

%o } /* _R. J. Mathar_, Jan 24 2012 */

%o (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

%o (Haskell)

%o import Data.List (permutations, nub)

%o a066411 0 = 1

%o a066411 n = length $ nub $ map

%o apex [perm | perm <- permutations [0..n], head perm < last perm] where

%o apex = head . until ((== 1) . length)

%o (\xs -> (zipWith (+) xs $ tail xs))

%o -- _Reinhard Zumkeller_, Jan 24 2012

%o (Python)

%o from sympy import binomial

%o def partitionpairs(xlist): # generator of all partitions into pairs and at most 1 singleton, returning the sums of the pairs

%o if len(xlist) <= 2:

%o yield [sum(xlist)]

%o else:

%o m = len(xlist)

%o for i in range(m-1):

%o for j in range(i+1,m):

%o rem = xlist[:i]+xlist[i+1:j]+xlist[j+1:]

%o y = [xlist[i]+xlist[j]]

%o for d in partitionpairs(rem):

%o yield y+d

%o def A066411(n):

%o b = [binomial(n,k) for k in range(n//2+1)]

%o 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

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

%K nonn,nice,more

%O 0,3

%A _Naohiro Nomoto_, Dec 25 2001

%E More terms from _John W. Layman_, Jan 07 2003

%E a(10) from _Nathaniel Johnston_, Apr 20 2011

%E a(11) from _Alois P. Heinz_, Apr 21 2011

%E a(12) and a(13) from _Joerg Arndt_, Apr 21 2011

%E a(14)-a(15) from _Alois P. Heinz_, Apr 27 2011

%E a(0)-a(15) verified by _R. H. Hardin_ Jan 27 2012

%E a(16) from _Alois P. Heinz_, Jan 28 2012

%E a(17)-a(21) from _Graeme McRae_, Jan 28, Feb 01 2012