Prev: Orthogonal distance regression of parabolic data
Next: train neural network with wavelet feature
From: Bill Sinclair on 22 May 2010 13:07
Math question:

Given 2^n possible arrangements of N 0s and 1s,
how many of those are unique under cyclic permutations?

For example, with N=3, we have (111,000,100,110), so the answer is 4.

I'm not sure such a formula has ever been discovered. It certainly is NOT a trivial one.
From: Walter Roberson on 22 May 2010 13:16
Bill Sinclair wrote:
> Math question:
>
> Given 2^n possible arrangements of N 0s and 1s,
> how many of those are unique under cyclic permutations?
>
> For example, with N=3, we have (111,000,100,110), so the answer is 4.
>
> I'm not sure such a formula has ever been discovered. It certainly is
> NOT a trivial one.

N+1 of them are unique -- 0 bits set, 1 bit set, 2 bits set ... N bits
set. The rest are reorderings of these.
From: Roger Stafford on 22 May 2010 16:08
"Bill Sinclair" <billsincl(a)aol.com> wrote in message <ht92vp$j12$1(a)fred.mathworks.com>...
> Math question:
>
> Given 2^n possible arrangements of N 0s and 1s,
> how many of those are unique under cyclic permutations?
>
> For example, with N=3, we have (111,000,100,110), so the answer is 4.
>
> I'm not sure such a formula has ever been discovered. It certainly is NOT a trivial one.

There are several definitions floating around of "cyclic permutations". The only one I can think of that makes your posed problem non-trivial is one for which the word 'unique' is not quite the right word. Are you asking for the number of equivalence classes in the 2^n binary numbers in which two numbers are considered equivalent if and only if one can be changed to the other by a cyclic rotation of its binary digits, as for example, 1001 -> 1100 -> 0110 -> 0011? In that case there are indeed four such equivalence classes for n = 3. For n = 6 there are fourteen. Is that what you are asking?

Roger Stafford
From: Walter Roberson on 22 May 2010 16:51
Roger Stafford wrote:
> "Bill Sinclair" <billsincl(a)aol.com> wrote in message
> <ht92vp$j12$1(a)fred.mathworks.com>...

>> Given 2^n possible arrangements of N 0s and 1s,
>> how many of those are unique under cyclic permutations?

> There are several definitions floating around of "cyclic
> permutations". The only one I can think of that makes your posed
> problem non-trivial is one for which the word 'unique' is not quite the
> right word. Are you asking for the number of equivalence classes in the
> 2^n binary numbers in which two numbers are considered equivalent if and
> only if one can be changed to the other by a cyclic rotation of its
> binary digits, as for example, 1001 -> 1100 -> 0110 -> 0011? In that
> case there are indeed four such equivalence classes for n = 3. For n =
> 6 there are fourteen.

Sounds like your cyclic rotations are pairwise, Roger. If you were to
use the more general definition of "cyclic permutations" that allows for
arbitrary permutations, then because any bit string can be permuted
directly into any other bit string of the same length and same number of
bits set, the only difference between the possibilities would be the
number of bits set.
From: Roger Stafford on 22 May 2010 20:24
Walter Roberson <roberson(a)hushmail.com> wrote in message <ktXJn.2273$mj4.2101(a)newsfe08.iad>...
> Sounds like your cyclic rotations are pairwise, Roger. If you were to
> use the more general definition of "cyclic permutations" that allows for
> arbitrary permutations, then because any bit string can be permuted
> directly into any other bit string of the same length and same number of
> bits set, the only difference between the possibilities would be the
> number of bits set.

They aren't *my* cyclic permutations, Walter. I am aware of the several standard definitions. What I suggested was the only way I could make sense out of the request. Can you think of another way that is consistent with Bill's example and that is non-trivial? Anyway, let's wait and see what he has to say about it.

Roger Stafford
 |  Next  |  Last
Pages: 1 2 3 4
Prev: Orthogonal distance regression of parabolic data
Next: train neural network with wavelet feature