College Mathematics Archives - Page 29 of 30

Introduction to Combinations

January 2, 2010 GB College Mathematics, Combinatorics, High School Algebra

Introduction to Combinations

In my Introduction to Permutations post, we have learned that the number of permutations (or arrangements) of $n$ objects taken at $n$ at a time written as $P(n,n)$ is equal to $n! = n(n-1)(n-2) \cdots (3)(2)(1)$ , and we have also learned that the number of permutations of $n$ objects taken $k$ at a time written as $P(n,k)$ is equal to $\displaystyle\frac{n!}{(n - k)!}$ .

In Figure 1, shown are the permutations of $4$ letters, A, B, C and D taken $4$ at a time. From the figure, we can see that there are indeed $4!= (4)(3)(2)(1) = 24$ of such arrangement. In Figure 2, shown are the permutations of $4$ letters taken $3$ at a time, and we have shown that the number of permutations is equal to $\displaystyle\frac{4!}{ (4 - 3)!} = \frac{4!}{1!} = (4)(3)(2)(1) = 24$ . In Figure 3, we have again listed the permutations of $4$ letters taken $2$ at a time, and have shown that the number of permutations is equal to $\displaystyle\frac{4!}{(4-2)!} =12$ .

Figure 1 – Permutations of ABCD, taken 4 at a time.

Figure 2 – Permutations of ABCD, taken 3 at a time.

Figure 3 – Permutations of ABCD, taken 2 at a time.

If we talk about combinations, however, the arrangement of objects does not matter. For example, if we want to buy a milk shake and we are allowed to choose to combine any $3$ flavors from Apple, Banana, Cherry and Durian*, then the combination of Apple, Banana and Cherry is the same as the combination Cherry, Apple, Banana.

Try to list all the possible combinations of $3$ flavors taken from $4$ before proceeding.

If we choose to shorten the name the fruits by selecting the first letter of their names, we only have $4$ possible combinations for question above: ABC, ABD, ACD, and BCD. Notice that these are the only possible combinations. Also, observe that if we list the permutations of ABC, we have ACB, BAC,BCA, CAB and CBA. This means that in permutations, we have counted each combination of $3$ flavors from $4$ flavors $6$ times (or $3!$ times instead of one.

In other words, a combination is just like a subgroup of a group. For instance, if we want to find the number of subgroups containing $3$ objects taken from $4$ objects (or the combination of $4$ objects taken $3$ at a time), it is the same as asking “how many possible groups of $3$ objects can be taken from $4$ objects?” In Figure 4, all the possible subgroups of $3$ letters taken from $4$ letters are displayed by the orange border. You also would have realized that the number of permutations is an overcounting of the number of combinations.

Figure 4 – The combinations of 4 objects taken 3 at a time is the same as the number of subgroups of 3 objects taken from 4 objects.

In Figure 2, ABC, ACB, BAC, BCA, CAB and CBA are permutations of Apples, Banana and Cherry. For each subgroup of $3$ , we realized that we counted $3! = 6$ times. So, to get the number of combinations, we divide our number of permutations $P(4,3)$ by the number of permutations of our subgroup $P(3,3) = 3!$ . Therefore, we can say that the number of combinations of $4$ objects taken $3$ at a time is equal to

$\displaystyle\frac{P(4,3)}{P(3,3)} = \frac{\frac{4!}{(4-3)!}}{3!} = \frac {4!}{(4-3)! 3!}$

In general, to get the number of combinations of $n$ objects taken $k$ at a time, we have to divide the number of permutations of $P(n,k)$ by the number of permutations of the subgroup $P(k,k)$ .

$\displaystyle\frac{P(n,k)}{P(k,k)} = \frac{\frac{n!}{(n-k)!}}{n!} = \frac {n!}{(n-k)! k!}$

The combinations of $n$ objects taken $k$ is usually denoted by $C(n,k)$ or $\displaystyle n \choose k$

_____________________________________________________________

*Durian is a fruit which can be found in the Philippines. It looks like a jackfruit.

Leave a comment combination math help, combinations tutorial, introduction to combinations, permutations and combinations, what is combinations

Proof Tutorial 1: Introduction to Mathematical Proofs

December 30, 2009 GB College Mathematics, High School Mathematics, Problem Solving and Proofs

Introduction

Routine problems in mathematics usually require one or many answers . If we are asked to find the smallest of the three consecutive integers whose sum is 18, then our answer would be 5. If we are asked to find the equation of a line passing through (2,3), we can have many answers.

Proofs, however, is different. It requires us to think more and to reason with valid arguments. It requires us to be explicit and logical. It requires us to convince our readers and most of all ourselves.

Unless a proof problem is already given, finding mathematical statements to prove requires us to see patterns, generalize, and make conjectures about them. The problem stated above about consecutive integers does not require us to reason much or generalize at all.

The success of proof writing requires intuition, mathematical maturity, and experience. Contrary to mathematical proofs written in books, the ideas behind arriving at a proof are not “cut and dried” and elegant. Mathematicians do not reveal the process they go through, or the ideas behind their proofs. This is also a skill that mathematicians and persons who are good in mathematics possess: they are able to read proofs. The skills of reading proofs may be achieved by learning how to write them.

Proving in higher mathematics, on the other hand, requires formal training. For instance, we have to know how to use logical connectives like and, or, not, and must understand how conditional and biconditional connectives work. Basic set theory concepts are also important. Moreover, we also have to learn proof strategies like direct proof and proof by contradiction to name some.

For now, we will not be discussing these things . Most of the proofs in basic mathematics only require a little intuition and good reasoning.

In the tutorial below, I tried to recreate (amateurishly) the process on how mathematicians see patterns, arrive at a conjecture, and how they prove their conjectures. Of course, in reality, problems mathematicians encounter are a lot harder. In fact, some of the hardest problems take hundreds of years to be solved. For example, no mathematician has proved the Fermat’s Last Theorem for more than 300 years, and the mathematician who proved it solved it for eight years.

The proof that we are about to do below is very elementary. For now, we will highlight the process and not the difficulty. The titles of the processes below are not necessarily in order.

Recognizing Patterns and Making Conjectures

Before mathematicians prove theorems, they usually first see patterns. This happens when they read books, solve problems, or prove other theorems. For example, what do we see when we add two even integers? Let’s add some: 2 + 8 = 10, – 24 + 6 = -18, and – 4 + – 8 = -12. We can easily see that if we add two even integers, then their sum is always even.

From here, we might be tempted to say that if we add two integers, then their sum would always be even. In mathematics, this kind of statement or hypothesis is called a conjecture: an educated and reasonable guess based on patterns observed. Rewriting our guess, we have

Conjecture: The sum of two even integers is always even.

If we want to disprove a conjecture, we only need one counterexample — an example that can make the conjecture false. (Can you think of one?). Note that we only need one counterexample to disprove a conjecture. If we want to prove it, however, we might be tempted to pair a few more integers and say that “oh, their sum is even, so it must be true”. No matter how many integers we pair, if we can’t exhaust all the pairs, then it cannot be considered as a proof. When we say the sum of two even integers above, we mean ALL even integers. Of course, there is no way that we can list all pairs of even integers since there are infinitely many of them.

Generalizing Patterns

Since it is impossible to enumerate all pairs of even integers, we need a representation, algebraic expression in particular, that will represent any even integer. If we can find this expression, then all the even integers would be represented. This process is called generalizing. Like what we have done above, we generalized by representing all members of the set by a single expression. In our case, the members of our set are all even integers.

From the definition, we know that all even integers are divisible by 2. That means that if m is an even integer, then, when we divide m by 2, we can find a quotient which is also an integer. For instance, since 18 is an integer, we are sure that there exists an integer such that 18 divided by 2 is equal to that integer.

In general, suppose that quotient of m/2 is q, then it follows that m/2 = q, for any even integer m. Multiplying both sides of the equation by 2, we have m = 2q. That means that if m is an even integer, then there exists an integer q such that m = 2q. Hence, we may represent any even integer m with 2q for some integer q*. Note that q here is a generalized number, which means that an even integer can also be represented by 2x, 2y, 2z or any variable with the condition that they are integers.

Connecting the ideas

Proving is making logical and relevant statements from definitions, facts, assumptions and other theorems to come to a desired conclusion. Before coming up with an elegant proof, mathematicians usually have scratch work, connecting their ideas to arrive at what they want to prove.

Scratch work

From the statement above, we have shown that any even integer m, there exists an integer q, such that m = 2q. That means, that if we can show that the sum of two even integers is in the form 2q (or that the sum is divisible by 2), then we can be sure that it is always an even integer.

Since we need two integers, we let m and n are the two integers that we will add. Since both of them are even integers, then we can represent them as 2q and 2r respectively for some integers q and r. Adding both of them, we have m + n = 2q + 2r = 2(q + r). Now, q + r is an integer since q is an integer and r is an integer from our definition above. This means that 2(q + r) isof the form 2x for some integer x. This means that m + n is of the form 2x for some integer x. Therefore, m + n is even.

Writing (elegantly) the final proof

Here, we write our proof in a shorter and more elegant way. Conjectures that are proven are called theorems. So let us write the proof of our first theorem.

Theorem 1: The sum of two even integers is always even.

Proof. Let m, n be even integers. Then m = 2q for some integer q and n = 2r for some integer r. Now, m + n = 2q + 2r = 2(q + r). Since q + r is an integer, clearly, 2(r + s) = m + n is divisible by 2. Therefore, the sum of two even integers is even.

Most proofs are written in a concise way, leaving some details for the reader to fill in. For example, the statement “Since q + r is an integer” did not really state the reason why this is so. This is stated in our scratch work, but not in the proof.

Going Further

If m is an even integer, then m – 1 and m + 1 are odd integers. Since m = 2r, then 2r – 1 and 2r + 1 are also odd integers. In our example below, we will use 2r + 1, to prove that the sum of two odd integers is always even. As an exercise, use 2r – 1 in your proof.

Theorem 2: The sum of two odd integers is always even.

Let p, q be odd integers. Then p = 2a + 1 and q = 2b + 1 for some integers a and b. Now, adding we have p + q = 2r + 1 + 2s + 1 = 2r + 2s + 2 = 2(r + s + 1). Since r + s + 1 is an integer, then 2(r + s + 1) is divisible by 2. Hence, p + q is divisible by 2. Therefore, the sum of two odd integers is even.

Math and Hardwork

Being good in math requires hard work. Andrew Wiles worked on the Fermat’s Last Theorem for seven years, have given up several times thinking that it was impossible. In 1995, he finally thought he had proved it, and presented it in a conference. A month later, his reviewer thought that there is a part of the proof which was vague (or wrong), so he had to review his work and found out that there was a part which was actually wrong. He almost gave up. He worked more than a year to correct the error.

Now, he has carved his place in history.

*In technical language, the word “for some” is equivalent to the word “there exists”.

Exercises:

Prove that the sum of an even number and an odd number is always odd.
Prove that the difference of two odd integers is always even.
Prove that the product of two even integers is always even.
Prove that the product of two odd integers is always odd.
Prove that the product of an even number and an odd number is always even.

Leave a comment Andrew Wiles, Fermat's Last Theorem, how to write proofs, introduction to proofs, mathematical proofs, proof basics, proof tutorial, sum of even numbers

An Intuitive Introduction to Limits

December 22, 2009 GB Calculus and Analysis, College Mathematics, High School Calculus

Limits is one of the most fundamental concepts of calculus. The foundation of calculus was not entirely solid during the time of Leibniz and Newton, but later developments on the concept, particularly the $\epsilon-\delta$ definition by Cauchy, Weierstrass and other mathematicians established its firm foundation. In the discussion below, I shall introduce the concept of limits intuitively as it appears in common problems. For a more rigorous discussion, you can read the post article titled “An extensive explanation about the $\epsilon-\delta$ definition of limits”.

Circumference and Limits

If we are going to approximate the circumference of a circle using the perimeter of an inscribed polygon, even without computation, we can observe that as the number of sides of the polygon increases, the better the approximation. In fact, we can make the perimeter of the polygon as close as we please to the circumference of the circle by choosing a sufficiently large number of sides. Notice that no matter how large the number of sides our polygon has, its perimeter will never exceed or equal the circumference of the circle.

Figure 1 – As the number of side of the polygons increases, its perimeter gets closer to the circumference of the circle.

In a more technical term, we say that the limit of the perimeter of the inscribed polygon as the number of its sides increases without bound (or as the number of sides of the inscribed polygon approaches infinity) is equal to the circumference of the circle. In symbol, if we let $n$ be the number of sides of the inscribed polygon, $P_n$ be the perimeter of a polygon with $n$ sides, and $C$ be the circumference of the circle, we can say that the limit of $P_n$ as $n \to \infty$ is equal to $C$ . Compactly, we can write $\lim_{n \to \infty} P_n = C$ .

Functions and Limits

Consider the function $f(x) = \frac{1}{x}$ where $x$ is a natural number. Calculating the values of the function using the first 20 natural numbers and plotting the points in the $xy$ -plane, we arrive at the table and the graph in Figure 2.

Figure 2 – As x increases, f(x) gets closer and closer to 0.

First, we see that as the value of $x$ increases, the value of $f(x)$ decreases and approaches $0$ . Furthermore, we can make the value of $f(x)$ as close to $0$ as we please by choosing a sufficiently large $x$ . We also notice that no matter how large the value of $x$ is, the value of $f(x)$ will never reach $0$ .

Hence, we say that the limit of $f(x) = \frac{1}{x}$ as the value of $x$ increases without bound is equal to $0$ , or equivalently the limit of $f(x) = \frac{1}{x}$ as $x$ approaches infinity is equal to $0$ . In symbol, we write the limit of $f(x) \to \infty$ as $x \to 0$ or more compactly the $\lim_{x \to \infty} \frac{1}{x} = 0$ .

Tangent line and Limits

Recall that the slope of a line is its “rise” over its “run”. The formula of slope $m$ of a line is $m = \displaystyle\frac{y_2 - y_1}{x_2 - x_1}$ , given two points with coordinates $(x_1,y_1)$ and $(x_2,y_2)$ . One of the famous ancient problems in mathematics was the tangent problem, which is getting the slope of a line tangent to a function at a point. In the Figure 3, line $n$ is tangent to the function $f$ at point $P$ .

Figure 3 – Line n is tangent to the function f at point P.

If we are going to compute for the slope of the line tangent line, we have a big problem because we only have one point, and the slope formula requires two points. To deal with this problem, we select a point $Q$ on the graph of $f$ , draw the secant line $PQ$ and move $Q$ along the graph of $f$ towards $P$ . Notice that as $Q$ approaches $P$ (shown as $Q'$ and $Q''$ ), the secant line gets closer and closer to the tangent line. This is the same as saying that the slope the secant line is getting closer and closer to the slope of the tangent line. Similarly, we can say that as the distance between the x-coordinates of $P$ and $Q$ is getting closer and closer to $0$ , the slope of the secant line is getting closer and closer to the slope of the tangent line.

Figure 4 – As point Q approaches P, the slope of the secant line is getting closer and closer to the slope of the tangent line.

If we let $h$ be the distance between the x-coordinates of $P$ and $Q$ , $m_s$ be the slope of the secant line $PQ$ and $m_t$ be the slope of the tangent line, we can say that the limit of the slope of secant line as $h$ approaches $0$ is equal to the slope of the tangent line. Concisely, we can write $\lim_{h \to 0}m_s = m_t$ .

Area and Limits

Another ancient problem is about finding the area under a curve as shown in the leftmost graph in Figure 5. During the ancient time, finding the area of a curved plane was impossible.

Figure 5 – As the number of rectangles increases, the sum of the area of the rectangles is getting closer and closer to the area of the bounded plane under the curve.

We can approximate the area above in the first graph in Figure 5 by constructing rectangles under the curve such that one of the corners of the rectangle touches the graph as shown in the second and third graph in Figure 5. We can see that as we increase the number of rectangles, the better is our approximation of the area under the curve. We can also see that no matter how large the number of rectangles is, the sum its areas will never exceed (or equal) the area of the plane under the curve. Hence, we say that as the number of rectangles increases without bound, the sum of the areas of the rectangles is equal to the area under the curve; or the limit of the sum of the areas of the rectangles as the number of rectangles approaches infinity is equal to the area of the plane under the curve.

If we let $A$ be the area under the curve, $S_n$ be the sum of the areas of $n$ rectangles, then we can say that the limit of $S_n$ as n approaches infinity is equal to $A$ . Concisely, we can write $\lim_{n \to\infty} S_n = A$ .

Numbers and Limits

We end with a more familiar example usually found in books. What if we want to find the limit of $2x + 1$ as $x$ approaches $3$ ?

To answer the question, we must find the value $2x + 1$ where $x$ is very close to $3$ . Those values would be numbers that are very close to $3$ – some slightly greater than $3$ and some slightly less than $3$ . Place the values in a table we have

Figure 6 – As x approaches 3, 2x + 1 approaches 7.

From the table, we can clearly see that as the value of $x$ approaches $3$ , the value of $2x + 1$ approaches $7$ . Concisely, we can write the $\lim_{x \to 3} 2x + 1 =7$ .

Mr. Jayson Dyer, author of The Number Warrior has another excellent explanation on the concept of limits in his blog Five intuitive approaches to teaching the infinitely small.

******

The area under the curve problem and the tangent problem are the ancient problems which gave birth to calculus. Calculus was independently invented by Gottfried Leibniz and Isaac Newton in the 17^th century.

10 comments an intuitive introduction to limits, calculus limit, integer limit, limit continuity, limit theorem, limits math, what is limits

« 1 … 27 28 29 30 »