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.

Rolle's Theorem and the Mean Value Theorem

Hi everyone! I hope you all had a great weekend. Rolle's Theorem and the Mean Value Theorem are two theorems of Calculus that can seem similar in a way, as they share a common hypothesis. Today, we will explore what these theorems state and examine interesting problems that could be approached with these theorems.

First, let's go over what the theorems state!
1> Rolle's Theorem:
If function f is continuous on the closed interval [a, b], differentiable in the open interval (a, b) and
f(a) = f(b), there exists a number c in (a, b) such that f '(c) = 0.

2> Mean Value Theorem (MVT):
If function f is continuous on the closed interval [a, b] and differentiable in the open interval (a, b), there exists a number c in (a, b) such that f '(c) = {f(b) - f(a)} /( b - a)

Now, let's look at some example problems.

Example 1> Prove that x^3 + x - 1 = 0 has exactly one zero.

Solution> First, we have to use the Intermediate value theorem to prove that there is a zero. For those of us who are not familiar with the Intermediate Value Theorem (IVT), the IVT states that if f is continuous on [a, b] and f(a) < w < f(b), there exists a number c between a and b such that f(c) = w. Let f(x) = x^3 + x - 1. Since f is a polynomial function, it is continuous on its domain (-∞, ∞). Thus f is continuous on [0, 1]. Notice f (0) = -1, f (1) = 1. Thus by the IVT, there exists a number c in (0, 1) such that f (c) = 0. Now, we will use proof by contradiction. Suppose that x^3 + x - 1 has two zeros at a and b. Without loss of generality, let a < b. x^3 + x - 1 is continuous on [0, 1] and since f '(x)= 3x^2 + 1 and this is never undefined, f (x) is differentiable in (0, 1). Since a and b are zeros, f(a) = f(b) = 0. Therefore, by Rolle's Theorem, there exists a number d in (0, 1) such that f '(d) = 0. But, f '(x)= 3x^2 + 1 ≥ 1 and this is a contradiction. Therefore, our hypothesis that f has two zeros were incorrect and therefore we have exactly one zero.

Example 2> Suppose that f(0) = -3 and f '(x) ≤ 5 for all values of x. How large can f (2) possibly be?

Solution> Since f is differentiable in (-∞, ∞), f is continuous in (-∞, ∞), and thus f is continuous on [0, 2]. Therefore, by the Mean Value Theorem, there exists a number c in (0, 2) such that f '(c) = {f(2) - f(0)}/2 = ( f(2)+ 3 )/2 ≤ 5. So, f(2) ≤ 2*5 - 3 = 7. Therefore, the largest f (2) can possibly be is 7.

I just wanted to introduce you all to these theorems and set of questions, because I was intimidated by these proof type questions using these theorems when I saw them. I was confused as of when to use the MVT, IVT, or Rolle's Theorem. Familiarity with the theorems are crucial, and it is important that we remember how to approach each of these problems using the theorems. I hope you all have a great rest of the day and please contact me if you do have any questions.

Mean Value Theorem; for a given arc between two endpoints,

there is at least one point at which the tangent to the arc is parallel

to the secant through its endpoints.

Understanding Early Number Systems

Hi! I apologize for not being able to post for the past few weeks; I was a little busy with all the AP testing, but I hope you all had a wonderful weekend and...
In this post, we will be exploring the basic idea and patterns behind some of the earliest number systems!

The Egyptians and the Babylonians are known to have come up with one of the first number conventions. These conventions often used symbols that represented specific numbers, known as “Nodal numbers.” Other numbers would be formed by grouping nodal numbers together in certain way. This system is known as the “Additive System.”

The Egyptians adopted this system in their number conventions. For example, in ancient Egyptian notation, the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 19, 40 would be represented by:

From this notation, we can observe that 1 and 10 were nodal numbers; 1 would be represented by a vertical dash, while 10 would be represented by a symbol that looks like an upside-down U.

The Babylonians used 1, 10 and 60 as their nodal numbers. The Babylonians used a sexagesimal positional number system, in which the value of a particular digit depends both on the digit itself and its position within the number. It has been proposed that 60 was used as the base number, as 60 = 2^2 x 3 x 5, which makes it divisible by 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, and 30.

Other Fun Facts:

• The Babylonians understood the concept of nothingness, but it was not seen as a number. The Babylonians understood “nothingness” as absence of a number, and thus represented nothingness with a space at first. Later on, a placeholding symbol was used to show the nonexistence of a digit in a certain place value.

This is the placeholding symbol

used by the ancient Babylonians to

represent 0.

• Nodal numbers are also used in Roman Numerals, in which many of us are familiar with. In the Roman number system the nodal numbers are 1, 5, 10, 50, 100, 500, 1000, represented respectively by the signs I, V, X, L, C, D, M. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 19, 40 would be represented by I, II, III, IV, V, VI, VII, VIII, IX, X, XIX, XL in Roman numerals.

I hope you all enjoyed this post, and please contact me if you have any questions!

Sources:

https://www.encyclopediaofmath.org/index.php/Numbers,_representations_of

https://en.wikipedia.org/wiki/Babylonian_numerals

The Shoelace Formula- Example Problem

Hello, in this post we will see a very simple example problem using the Shoelace Formula, a topic about which I posted last time. In this example, we will be finding the area of a triangle given the coordinates of its three vertices. I hope that this example will make the usage of this method more clear for you all!