|
Search: id:A135547
|
|
|
| A135547 |
|
Number of connected components of Arnold's graph G_n associated with the "first differences" operator on the 2^n binary vectors of length n. |
|
+0
1
|
|
| 1, 1, 2, 1, 2, 4, 10, 1, 6, 10, 4, 24, 6, 298, 1096, 1, 260, 526, 28
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
G_n has 2^n vertices, one for each binary vector x. Each node x has a single directed edge which goes from x to y, where y_1 = x_2-x_1, y_2 = x_3-x_2, ..., y_{n-1} = x_n-x_{n-1}, y_n = x_1-x_n. (Of course since the vectors are binary, we could use sums here instead of differences.)
|
|
REFERENCES
|
V. I. Arnold, Complexity of finite sequences of zeros and ones and geometry of finite spaces of function, Funct. Anal. Other Math., 1 (2006), 1-15.
|
|
LINKS
|
V. I. Arnold, Complexity of finite sequences of zeros and ones and geometry of finite spaces of function, Funct. Anal. Other. Math vol 1 iss 1 (2006) pp 1-15.
|
|
PROGRAM
|
(C++) #include <iostream> #include <set> #include <vector> using namespace std ; int inComp( const vector< set<unsigned> > & comps, const int n) { for(int i=0; i < comps.size() ; i++) if ( comps[i].find(n) != comps[i].end() ) return i; return -1 ; } int firstd(const unsigned i, const int len, const unsigned allbu1, const unsigned hibit) { unsigned d= i ^ (i>>1) ; if ( (i&1) != (i & hibit) >> (len-1) ) d |= hibit ; else d &= allbu1 ; return d ; } int main(int argc, char*argv[]) { for(int n=1; ; n++) { vector< set<unsigned> > comps ; unsigned allbu1 = 0 ; for(int i=0 ; i < n-1 ; i++) allbu1 |= (1 << i) ; const unsigned hibit = 1 <<(n-1) ; for(int i=0; i < 1<<n; i++) { set<unsigned> trac ; for(int ider=i; ; ) { int c ; if ( ( c=inComp(comps, ider) ) != -1) { comps[c].insert(ider) ; for(set<unsigned>::const_iterator j=trac.begin() ; j != trac.end() ; j++) comps[c].insert(*j) ; break ; } else if ( trac.find(ider) != trac.end() ) { comps.push_back(trac) ; break ; } else trac.insert(ider) ; ider= firstd(ider, n, allbu1, hibit) ; } } cout << n << " " << comps.size() <<endl ; } } - a(13)-a(19) from R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Apr 17 2008
|
|
CROSSREFS
|
Sequence in context: A024739 A024959 A029728 this_sequence A146307 A063894 A024500
Adjacent sequences: A135544 A135545 A135546 this_sequence A135548 A135549 A135550
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com), Feb 24 2008
|
|
EXTENSIONS
|
a(13)-a(19) from R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Apr 17 2008
|
|
|
Search completed in 0.002 seconds
|
