|
|
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.
|
|
7
|
|
|
1, 1, 3, 5, 23, 61, 143, 215, 995, 2481, 5785, 12907, 29279, 64963, 144289, 158049, 683311, 1471123, 3166531, 6759177, 14404547, 30548713
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
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
|
|
LINKS
|
|
|
EXAMPLE
|
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.
|
|
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 *)
|
|
PROG
|
(MATLAB)
for n=0:9
size(unique(perms(0:n)*diag(fliplr(pascal(n+1)))), 1)
(C++)
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
inline long long pascApx(const vector<int> & s)
{
const int n = s.size() ;
vector<long long> scp(n) ;
for(int i=0; i<n; i++)
scp[i] = s[i] ;
for(int i=1; i<n; i++)
for(int acc=0 ; acc < n-i ; acc++)
scp[acc] += scp[acc+1] ;
return scp[0] ;
}
int main(int argc, char *argv[])
{
for(int n=1 ; ; n++)
{
vector<int> s;
for(int i=0; i<n; i++)
s.push_back(i) ;
set<long long> apx;
do
{
apx.insert( pascApx(s)) ;
} while( next_permutation(s.begin(), s.end()) ) ;
cout << n << " " << apx.size() << endl ;
}
return 0 ;
(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
(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))
(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
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|