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 when objects (colours/beads/numbers) are given.

**Procedure A:** *Using multiplication principle*

Step 1: Choose objects from the choices.

Step 2: Arrange the selected objects in a cyclic order.

- 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 and from Step 2, we will get as per the circular permutation formula. Hence we get:

**Procedure B:** *Using division principle*

Step 1: Permute of the objects.

Step 2: Realise the mistake that you counted the permutations 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 and from Step 2 we will get . Hence we get:

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

### Like this:

Like Loading...

*Related*

Hi,

Any use of the “division principle” can be rephrased as an application of the “multiplication principle” (to the number of ways to “overcount”).

Concretely, how do you like this?

“**Procedure B:** *By counting permutations*. We may permute r of the n objects by (1) picking a cycle and (2) picking a starting point. Therefore, . We’ve actually counted nPr already and can solve for the number of cycles…”

LikeLiked by 1 person

I found this better than my way of stating it. Thanks 🙂

LikeLike