Friday, 11 March 2016

permutations - Flipping odd number array by two numbers in series.

Suppose an array of length $n$(odd number) which is composed with only $0$.



We start to ‘flip’( or ‘change’) numbers with following rules.




  1. [1, 1] → [0, 0]

  2. [0, 0] → [1, 1]

  3. [1, 0] or [0, 1] : do not change.


  4. Change elements sequentially and rotationally(when you reach at the end of the array), and repeat until the array becomes its initial state.



For example, if the length of the array is 3,



0   [0 0 0] #start
1 [1 1 0] #first and second element is [0, 0], by rule 2, it became [1, 1]
2 [1 1 0] #third and first element = [0, 1], by rule 3, just pass.
3 [1 1 0] #second and third = [1, 0], pass
4 [0 0 0] #first and second = [1, 1], by rule 1, change it to [0, 0].



After 4 steps, the array repeats its configuration, so, the period is $4$.



Another example, $n = 5$



0   [0 0 0 0 0]
1 [1 1 0 0 0]
2 [1 1 1 1 0]
3 [1 1 1 1 0]

4 [1 0 0 1 0]
5 [1 0 0 1 0]
6 [1 0 0 1 0]
7 [1 0 0 1 0]
8 [1 0 0 1 0]
9 [1 1 1 1 0]
10 [1 1 1 1 0]
11 [0 0 1 1 0]
12 [0 0 0 0 0]



The period is $12$.



And when $n=7$,



0   [0 0 0 0 0 0 0]
1 [1 1 0 0 0 0 0]
2 [1 1 1 1 0 0 0]
3 [1 1 1 1 1 1 0]
4 [1 1 1 1 1 1 0]

5 [1 0 0 1 1 1 0]
6 [1 0 0 0 0 1 0]
7 [1 0 0 0 0 1 0]
8 [1 0 0 0 0 1 0]
9 [1 0 1 1 0 1 0]
10 [1 0 1 1 0 1 0]
11 [1 0 1 1 0 1 0]
12 [1 0 1 1 0 1 0]
13 [1 0 1 1 0 1 0]
14 [1 0 1 1 0 1 0]

15 [1 0 1 1 0 1 0]
16 [1 0 0 0 0 1 0]
17 [1 0 0 0 0 1 0]
18 [1 0 0 0 0 1 0]
19 [1 1 1 0 0 1 0]
20 [1 1 1 1 1 1 0]
21 [1 1 1 1 1 1 0]
22 [0 0 1 1 1 1 0]
23 [0 0 0 0 1 1 0]
24 [0 0 0 0 0 0 0]



The period is $24$.



It looks like the series of periods follows A046092 (0, 4, 12, 24, 40, 60, 84, 112, 144, 180, 220, 264,… )



How can I prove this?



(If you want to look into more longer cases, refer here )




(Any modification of my English will be appreciated. English is not my mother tongue.)

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...