Tag Archives: cycle

Counting Cycles

Standard

During one of my reading projects in 2015, I read about the Enigma cipher machine. While reading about it, I came to know that the number of possible keys of this machine is 7, 156, 755, 732, 750, 624, 000. One can see the counting procedure at pp. 22 of this document. But the counting procedure was not found to be satisfactory by most members of the audience (during my presentation). My failure to convince the audience that the counting procedure was correct, lead to my distrust in the counting arguments in general. Many times, I still, find the counting procedures controversial.

So, in an attempt to regain the trust, I will present two counting procedures for counting the number of cycles of length r when n objects (colours/beads/numbers) are given.

Procedure A: Using multiplication principle
Step 1: Choose r objects from the n choices.
Step 2: Arrange the selected r objects in a cyclic order.

  1. Since the Step 1 and Step 2 are independent of each other but should be performed together, we will multiply the results (i.e. use the multiplication principle). From Step 1 we will get \binom{n}{r} and from Step 2, we will get (r-1)! as per the circular permutation formula. Hence we get:

\displaystyle{\# r-\text{cycles from } n \text{ objects} =\binom{n}{r}\times(r-1)! = \frac{n!}{r (n-r)!}}

Procedure B: Using division principle
Step 1: Permute r of the n objects.
Step 2: Realise the mistake that you counted the permutations r extra times because these circular permutations of objects are equivalent since the circle can be rotated.

Since in Step 2 we want to correct the overcounting mistake of Step 1 performed for different objects simultaneously, we will divide the result of Step 1 by the result of Step 2. From Step 1 we will get ^n P_r and from Step 2 we will get r. Hence we get:

\displaystyle{\# r-\text{cycles from } n \text{ objects} =\frac{^n P_r}{r} = \frac{n!}{r (n-r)!}}

I am still not happy with the Procedure B, so if you have a better way of stating it please let me know.

Advertisements

Recursion and Periodicity

Standard

One of the simplest recursive formula that I can think of is the one which generates the Fibonacci sequence, F_{n+1} = F_n +F_{n-1}, n\geq 1 with F_0 = F_1=1. So, I will illustrate a following general concept about recursions using Fibonacci sequence.

A sequence generated by a recursive formula is periodic modulo k, for any positive integer k greater than 1.

I find this fact very interesting because it means that a sequence which is strictly increasing when made bounded using the modulo operation (since it will allow only limited numbers as the output of recursion relation), will lead to a periodic cycle.

Following are the first 25 terms of the Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025.

And here are few examples modulo k, for k=2,3,4,5,6,7,8

table110

As you can see, the sequence repeats as soon as 1,0 appears. And from here actually one can see why there should be a periodicity.

For the sequence to repeat, what we need is a repetition of two consecutive values (i.e. the number of terms involved in the recursive formula) in the sequence of successive pairs. And for mod k, the choices are limited, namely k^2.  Now, all we have to ensure is that “1,0” should repeat. But since consecutive pairs can’ repeat (as per recursive formula) the repetition of “1,0” must occur within the first k^2.

For rigorous proofs and its relation to number theory, see: http://math.stanford.edu/~brianrl/notes/fibonacci.pdf