Tag Archives: combinatorics

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.

Combinatorial Puzzle

Standard

This is a continuation of previous post:

How many distinct numbers can be formed by using four 2s and the four arithmetic operations +,-,\times, \div.

For example:
1 = \frac{2+2}{2+2}=\frac{2}{2}\times\frac{2}{2}
2 = 2+\frac{2-2}{2}=\frac{2}{2}+\frac{2}{2}
3 = 2+2 - \frac{2}{2}
4 = 2+2+2-2 = (2\times 2) + (2-2)
(note that some binary operations do not make sense without parenthesis)

I have no idea about how to approach this problem (since I am not very comfortable with combinatorics). So any help will be appreciated.

Edit[29 May 2017]: This problem has been solved in the comments below. 

Intra-mathematical Dependencies

Standard

Recently I completed all of my undergraduate level maths courses, so wanted to sum up my understanding of mathematics in the following dependency diagram:

mat-dependency (1)

I imagine this like a wall, where each topic is a brick. You can bake different bricks at different times (i.e. follow your curriculum to learn these topics), but finally, this is how they should be arranged (in my opinion) to get the best possible understanding of mathematics.

As of now, I have an “elementary” knowledge of Set Theory, Algebra, Analysis, Topology, Geometry, Probability Theory, Combinatorics and Arithmetic. Unfortunately, in India, there are no undergraduate level courses in Mathematical Logic and Category Theory.

This post can be seen as a sequel of my “Mathematical Relations” post.

Cross Diagonal Cover – VI

Standard

The problem has finally been solved by Matthew Scroggs.

{\text{\# filled squares} = (\mathrm{lcm}(m-1,n-1)+1 )- \frac12\left(\frac{\mathrm{lcm}(m-1,n-1)}{m-1}-1\right)\left(\frac{\mathrm{lcm}(m-1,n-1)}{n-1}-1\right)}

He and I, independently,  found a counterexample  for the conjecture by replacing lowest common multiple by greatest common factor using the relation: ab=\mathrm{lcm}(a,b)\gcd(a,b).

In 15×5, there are 26 filled squares and gcd(15,5)=5, so 15×5 is a counterexample to the conjecture!

As it turns out, SAGE is giving float(26/5) = 5.0 when I run it inside the program, but return 5.2 when I run it independently. Leading to wrong conjecture.

The solution is pretty beautiful and  this is the outline:

There are 3 levels of simplifications of the problem:

Original Grid –> Dual Grid –> Mirror Grid –> Inner-point Grid

Counting the “Corners visited twice” (the subtracted term) was something I wasn’t able to do. Corners visited was essentially what I called “number of steps needed for algorithm to stop“. So, his mirror argument provides a proof without words of that result.

Cross Diagonal Cover – V

Standard

This has been an exciting week! Prof. Sukanta Pati proved an interesting theorem that enables us to get decomposition of 2m-1\times n grids into simpler grids, hence simplifying counting to large extent (note that m=n is also allowed). It enables us to surpass the difficulty posed by “more than two crosses in one square”, thus supporting the idea of colouring (i.e. not giving importance to two crosses in a square).

Given m\times n grid which has consisting of m rows and n columns such that the terminating corner square lie in m^{th} row. Let the number of covered squares in m\times n grid be C(m,n) . Then for  2m-1\times n grid we have C(2m-1, n)= 2C(m,n)-\beta(m,n)  where \beta(m,n) is the number of covered squares in m^{th} row of m\times n grid.

Instead of giving its proof, I will give an  example when m=5, n=10.

New Doc 26_1

I omitted the repetitions of crosses (x) since the number of x in each square doesn’t matter. Note that if we reflect 5×10 about the middle of 5th row we will get 9×10.

Here, C(5,10) = 25 and C(9,10) = 2\times 25 - 5 = 45. Using this example you can easily prove the generalized statement by exploiting the bilateral symmetry of grid and x about ythe dotted line.

Though  I suspected that least common multiple of m-1, n-1 determine the number of steps my algorithm evaluates, Pritam Laskar  found the exact formula.

Given a m\times n grid, the Cross Diagonal Cover algorithm terminates after  lcm(m-1, n-1) + 1  steps.

For proof, follow the arguments of grant93jr in his/her comment (he/she mistakenly called their lcm to be their gcd).

Using the SageMath Program, about which I wrote in previous post, I am pretty sure that \gcd(m,n) always divides the number of filled squares. So, now the question is

Why the greatest common divisor of m and n always divides the number of filled squares?

 

Bringing Maths out of Marriage

Standard

I will consider following definition of marriage:

the legally or formally recognized union of a man and a woman as partners in a relationship.

It can be difficult, due to the emotions we have, to find suitable partner. But mathematicians have tried to solve this problem. Pretty cool, huh!

(1) Hall’s Marriage Theorem:  We have n boys, each of whom has several girlfriends, under what conditions can we marry off the boys in such a way that each boy marries one of his girlfriends?

We claim that this problem has a solution if and only if for every k, 1\leq k\leq n, every set of k boys has collectively at least k girlfriends.

hall

The connecting lines indicate whether this man and woman like each other. (boyfriend-girlfriend relationship) [By Greg Graviton , Applications of Measure, Integration and Banach Spaces to Combinatorics]

Mathematically, we can restate it in graph theoretic language as

Let G be a bipartite graph with bipartition V = X \cup Y. Then G contains a matching that saturates every vertex in X if and only if |N(S)| \geq |S| for every subset S of X

where, N(S) is defined to be the set of all vertices adjacent to any set S of vertices in graph G and |.| denotes “the number of elements in”.

The proof of this theorem is by Induction on n. See this Cut the Knot article for proof. 

 

(2) Stable Marriage Problem:  There are n women and n men in a community. Each woman ranks each man in accordance with her preference for that man as a spouse. No ties are allowed, so that if a woman is indifferent between two men, we nonetheless require that she express some preference. The preferences are to be purely ordinal, and thus each woman ranks the men in order 1,2, …, n. Similarly, each man ranks the woman in the order 1,2,…, n.

We would like to arrange marriages between the men and women so that there is not a man and a woman who prefer one another to their spouses. Such marriages are  called stable. Does there always exist a stable marriage?

We claim that the answer to this question is YES! We just need to follow Gale–Shapley algorithm.  Watch this awesome Numberphile video explaining this

 

Other articles in same spirit: 

 

Interesting Diagonal Discovery

Standard

Yesterday (while doodling in my Number Theory class) I was just playing with diagonals of polygons and something interesting appeared on my notebook. For the first time in my life I have discovered a theorem and its proof on my own (it’s original!). In this blog-post I will share it with you all!

Consider an n-sided polygon, and start drawing diagonals from each vertex one-by-one. While doing so count the number of new diagonals contributed by each vertex. Here is the “Experiment” done for n=4,5,6,7,8.

Number written near each vertex indicate the number of new diagonals contributed by that vertex (following anti-clockwise order and starting with the red one)

Number written near each vertex indicate the number of new diagonals contributed by that vertex (following anti-clockwise order and starting with the red one)

Based on above experiment, I observed:

The number of new diagonals contributed by each vertex of a n-sided polygon follows the sequence: (n-3),(n-3),(n-4),\ldots, 1,0,0

Now let’s try to  prove this observation:

Since we can’t draw diagonals to the adjacent vertices, each vertex will have (n-1)-2 = (n-3) diagonals.

Now, let’s count the new contribution of each vertex by considering restrictions on the maximum possible contribution (which is (n-3)).

For first vertex, we have no restriction, so it will contribute (n-3) diagonals.

Also, since second vertex in adjacent to first one and both can’t affect each-other’s contribution, it will also contribute (n-3) diagonals.

But, starting with third vertex we observe that first vertex has already taken one of the diagonals from its maximum contribution (second vertex can’t affect its contribution count since it’s adjacent vertex), thus it contributes (new) (n-3)-1 = (n-4) diagonals.

Continuing same way, for k^{th} vertex, consider the restriction to contribution caused by 1^{st} to (k-2)^{th} vertices. Thus for 1<k<n we get the number of new diagonals contributed by k^{th} vertex equal to (n-3)-(k-2) = (n-k-1).

Since new contribution can’t be negative and for (n-1)^{th} vertex we end up with zero (new) contribution, n^{th} vertex will also contribute zero diagonals.

Combining all of the above arguments I complete the proof of my observation and call it “New Diagonal Contribution Theorem” (NDCT).