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