|
| |
|
|
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, 2, 1, 2, 4, 10, 1, 6, 10, 4, 24, 6, 298, 1096, 1, 260, 526, 28
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
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
|
Table of n, a(n) for n=1..19.
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.
|
|
|
PROG
|
(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, Apr 17 2008
|
|
|
CROSSREFS
|
Sequence in context: A024739 A024959 A029728 * A146307 A063894 A024500
Adjacent sequences: A135544 A135545 A135546 * A135548 A135549 A135550
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
N. J. A. Sloane, Feb 24 2008
|
|
|
EXTENSIONS
|
a(13)-a(19) from R. J. Mathar, Apr 17 2008
|
|
|
STATUS
|
approved
|
| |
|
|
