Permutations and Circular Permutations

Hello everyone! In this post, we will explore permutations and circular permutations. I will be providing example problems with various solutions to approach them! I hope you all enjoy!

We will first start by learning the definition of a permutation.

Permutations:

Let S = {a1, …, an} be a set with n elements. If we arrange the elements of S in order, we get a permutation of S. More generally, if we select r elements from S and arrange them in order, we get an r permutation of S. We’ll use P (n, r) or nPr to denote the number of r- permutations of a set with n elements.

Theorem> P(n, r) = n(n-1)... (n-r+1) = n(n-1)...(n-r+1) [(n-r)(n-r-1)...2*1]/ [(n-r)(n-r-1)...2*1]= n!(n- r)!

        (We are choosing r elements out of n in order. First we have n elements to choose from, then we have n- 1 elements to choose from after choosing element, and after choosing another element, we would have n- 2 elements to select from. If we have to choose a total of r elements, we would end up with the left side of the equation by the multiplication principle.)

Example 1> How many ways can we arrange 5 couples in a row, if the people in each couple are together?

Answer: 5! 2^5 ( 5! Is the number of ways of arranging each of the couples and 2^5 accounts for arranging the people in each couple)

Example 2> Find the number of ways to arrange 6 adults and 4 children in a row if the children must be together.

Solution A> We can consider the 4 children as a single entity and consider each of the adults as a single entity. So in total, we have 7 entities. We would arrange the 7 entities in 7! Ways and within the entity of 4 children, we can arrange the 4 children in 4! ways. By the multiplication principle, the total number of ways would be 7! 4!

Solution B> First, consider the way of lining 6 adults first; this would be 6!. Afterwards, we would be able to place the 4 children in 7 spots (very left, very right, and in between each of the adults would be a total of 7 possible spots). Again, the 4 children can be lined up in 4! ways and by the multiplication principle, the total number of ways would be 6! 74!.

Circular Permutations.

In how many ways can we select r people from a set of n people and arrange them in a circle if all rotations of a given arrangement are considered the same? We can answer this question using the concept of circular permutations. We will denote this case by Q (n, r), the number of circular r- permutations of n objects.

Theorem> Q(n, r) = nPr ( Idea of proof:  P(n, r) = r Q(n, r) since each circular r- permutation corresponds to r regular permutations)

Special Case: Q( n, n)= (n - 1)!

Since Q(n, n) = P (n, n)* n= n!*n= ( n - 1)!

Example 1> Find the number of ways to arrange 6 adults and 4 children in a circle if the children must be together?

Answer: 6! * 4! (6!: number of ways to arrange 7 entities in a circle, 4!: ways of arranging the 4 children).

Example 2> Find the number of ways to arrange 7 people in a circle, if Carol and Tom cannot be together.

Answer: 6! - 5!*2 (6!: Total ways to arrange people, 5!*2: Number of cases in which Carol and Tom sit together)

Example 3> Find the number of ways to seat 5 men and 5 women in a circle, if the men and women alternate?

Solution 1> 4! (ways of seating men) * 5! (ways of seating the women in the gaps)

Solution 2> First seat a women, then there are 4! Ways to seat the other women. Then, the number of ways to seat the men in 5 fixed seats is 5!. Thus with the multiplication principle, the total number of ways to seat the people: 5! * 4!

Solution 3> 5! (pair men and women together) * 4! (arrange 5 entities into a circle).

This is all for today! Please feel free to contact me or comment below if you have any questions :)

Congruence in Modular Arithmetic

Hello! When I hear the word “congruence,” the first thing that pops up in my mind is congruence in geometry. It turns out, however, that there can be congruence in numbers, well specifically in modular arithmetic! In this post, we will explore congruence in modular arithmetic.

Given integers a, b, and n, with n > 0, we say that a is congruent to b modulo n, or a ≡ b (mod n), if the value of (a - b) is visible by n. Two numbers a and b are said to be “congruent to modulo n” if (a mod n) = (b mod n). For example, 73 ≡ 4 (mod 23) since 73 - 23 = 69 is divisible by 23.

    Now that we have an idea about the definition of congruence, we will explore some properties of congruence:

Consider four integers a, b, c, and d and a positive integer m (m >0) such that a ≡ b (mod m) and c ≡ d (mod m). In modular arithmetic, the following properties hold:

1. Addition: a + c ≡ b + d (mod m)
2. Subtraction: a - c ≡ b - d (mod m)
3. Multiplication: ac ≡ bd (mod m)
4. Division: (a/e) ≡ (b/e) {mod m/gcd (m, e)} where e is a positive integer that divides both a and b.
5. Exponentiation: a^e ≡ b^e (mod m) where e is a positive integer
6. a ≡ b (mod n) => b ≡ a (mod m)
7. a ≡ b (mod m) and b ≡ c (mod n) => a ≡ c (mod n)

Some examples of the more advanced properties of congruence relations include the following:

• Fermat's little theorem: If p is prime, then a p – 1 ≡ 1 (mod p) for 0 < a < p
• Wilson's theorem: p is prime if and only if (p − 1)! ≡ −1 (mod p)
• Chinese remainder theorem: If x ≡ a (mod m) and x ≡ b (mod n) such that m and n are co-prime (the only positive integer that divides both of them is 1), then x ≡ b mn–1 m + a nm–1 n (mod mn) where mn−1 is the inverse of m modulo n and nm−1 is the inverse of n modulo m
• Lagrange's theorem: The congruence f (x) ≡ 0 (mod p), where p is prime, and f (x) = a0 xn + ... + an is a polynomial with integer coefficients such that a0 ≠ 0 (mod p), has at most n roots.

This is it for today and I hope you all have a great rest of the day. Also, please feel free to contact me or comment below if you have any questions!

Introduction to Modular Arithmetic

Hello mathletes! In this post, we will be exploring the basics of modular arithmetic. Modular arithmetic is a system of arithmetic for integers, in which numbers "wrap around" upon reaching the modulus (plural moduli). The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

“Modulo n” includes numbers between 0 and n-1. The easiest way to convert numbers in modular arithmetic is by doing Euclidean Division and taking the remainder.

In r = n mod m, we can remove as many multiples of m as possible until we are left with an answer between 0 and m-1. In this case, r would be the remainder and m would be the modulus. So for example, 34 mod 4 = 2 and 19 mod 7 = 5. If n is a negative number, then we add as many multiples of m as needed to have an answer between 0 and -(m-1). Thus, -23 mod 5 = 2 and -78 mod 9 = 3.

Here are some basic properties of Modular Arithmetic:

1> [ (a mod n) + (b mod n) ] mod n = ( a + b) mod n

ex) [(37 mod 6) + (99mod 6)] = 4 mod 6 = 4 and (37 + 99) mod 6 = 136 mod 6 = 4

2> [ (a mod n) - (b mod n) ] mod n = (a - b) mod n

ex) [ (37 mod 6) - (99mod 6)] mod 6 = -2mod 6 = 4 and (37 - 99)mod 6 = -62 mod 6 = 4

3> [ (a mod n)* (b mod n)] mod n = ab mod n

ex) [ (37mod6) * (99mod6)] mod 6 = 3 mod 6 = 3 and (37* 99) mod6 = 3663 mod 6 = 3

Lastly, the set of integers {0, 1, 2, …, n − 1} is called the least residue system modulo n. Any set of n integers, no two of which are congruent modulo n, is called a complete residue system modulo n. It is clear that the least residue system is a complete residue system, and that a complete residue system is simply a set containing precisely one representative of each residue class modulo n. The least residue system modulo 4 is {0, 1, 2, 3}. Some other complete residue systems modulo 4 include {1, 2, 3, 4}, {13, 14, 15, 16}, {−2, −1, 0, 1}, {−13, 4, 17, 18}, {−5, 0, 6, 21} and {27, 32, 37, 42}.

In the next post, we will explore the concept of congruence! Please contact me or comment below if you have any questions and have a great day!

If we replaced our 12 with a 0 in our clock,

the numbers on the clock would show us the way in which we would count in modulo 12.

San Francisco Exploratorium- Buffon's Needle

Today, I visited the Exploratorium in San Francisco. There were various exhibits in the Mathematics section from the parabola- powered calculator to models of various Archimedean solids to the square shaped wheel. One of the exhibits I found interesting was the “Pi(𝜋) Toss,” in which the value of pi would be estimated by tossing chips. I would be given chips and I would randomly toss any number of chips onto the table. According to the instructions, tossing all 22 would be preferable. Then, I had to count how many times the lines on the chips cross the lines on the table and using the calculator, I divided the total number of chips tossed by the number of crossings. This answer would yield an approximation of pi. This value was not very close to pi at first, but with several more rounds of tosses and averaging the results over time, I was able to obtain values closer to the actual value of pi.

    Pi is a famous mathematical constant relating the circumference of a circle to its diameter. More tosses would yield more accurate results; hence, if we were to have the patience to toss chips all day, all week, all year we would obtain an increasingly accurate estimate of pi. This method of calculating pi, also known as Buffon’s Needles, was discovered over 300 years ago by a French mathematician, Count Buffon. Buffon discovered this method in an accident as he had wanted to calculate the odds of winning in a then-popular game of chance, in which one would toss a coin onto a tiled floor and bet on whether it would land entirely within one of the tiles.