Skip to main content
added 103 characters in body
Source Link
kodlu
  • 10.4k
  • 2
  • 36
  • 55

What you can use is Polya's theory of counting, for alphabet size $k=2.$

An $(n, k)−$necklace is an equivalence class of words of length $n$ over an alphabet of size $k$ under rotation. The basic enumeration problem is:

For a given $n$ and $k,$ how many $(n, k)-$necklaces are there? Equivalently, we are asking how many orbits the cyclic group $C_n$ has on the set of all words of length $n$ over an alphabet of size $k.$ Denote this value by $a(n, k).$

Theorem:

$$a(n,k)=\frac{1}{n}\sum_{d|n} \phi(d) k^{n/d}.$$

Have fun!

Edit: In case it is unclear, you want the orbit sizes of each one of these equivalence classes.

What you can use is Polya's theory of counting, for alphabet size $k=2.$

An $(n, k)−$necklace is an equivalence class of words of length $n$ over an alphabet of size $k$ under rotation. The basic enumeration problem is:

For a given $n$ and $k,$ how many $(n, k)-$necklaces are there? Equivalently, we are asking how many orbits the cyclic group $C_n$ has on the set of all words of length $n$ over an alphabet of size $k.$ Denote this value by $a(n, k).$

Theorem:

$$a(n,k)=\frac{1}{n}\sum_{d|n} \phi(d) k^{n/d}.$$

Have fun!

What you can use is Polya's theory of counting, for alphabet size $k=2.$

An $(n, k)−$necklace is an equivalence class of words of length $n$ over an alphabet of size $k$ under rotation. The basic enumeration problem is:

For a given $n$ and $k,$ how many $(n, k)-$necklaces are there? Equivalently, we are asking how many orbits the cyclic group $C_n$ has on the set of all words of length $n$ over an alphabet of size $k.$ Denote this value by $a(n, k).$

Theorem:

$$a(n,k)=\frac{1}{n}\sum_{d|n} \phi(d) k^{n/d}.$$

Have fun!

Edit: In case it is unclear, you want the orbit sizes of each one of these equivalence classes.

Source Link
kodlu
  • 10.4k
  • 2
  • 36
  • 55

What you can use is Polya's theory of counting, for alphabet size $k=2.$

An $(n, k)−$necklace is an equivalence class of words of length $n$ over an alphabet of size $k$ under rotation. The basic enumeration problem is:

For a given $n$ and $k,$ how many $(n, k)-$necklaces are there? Equivalently, we are asking how many orbits the cyclic group $C_n$ has on the set of all words of length $n$ over an alphabet of size $k.$ Denote this value by $a(n, k).$

Theorem:

$$a(n,k)=\frac{1}{n}\sum_{d|n} \phi(d) k^{n/d}.$$

Have fun!