Factorial
The factorial of a positive integer "n", denoted by n!, is defined as: $n!=n(n-1)(n-2).....1$
For example,
$2!=2*1=2$
$3!=3*2*1=6$
$4!=4*3*2*1=24$
Permutations
A permutation is any distinct ordered arrangement of ALL the elements of a given set.
For example, the set of letters A, B and C has 6 possible permutations:
Permutation 1: A, B, C
Permutation 2: A, C, B
Permutation 3: B, A, C
Permutation 4: B, C, A
Permutation 5: C, A, B
Permutation 6: C, B, A
For a set of "n" elements the number of permutations can be calculated by the formula:
$P=n*(n-1)*(n-2)....(1)=n!$
In our previous example, the set had 3 elements, and the number of permutations was $P=3!=6$
If a set has 4 elements it will have $P=4!=24$ permutations.
Arrangements with Repetition
Let's consider a set B, with "n" elements. We want to form a set C, with "p" elements (p < n), extracted from set B, with repetition. How many different arrangements of "p" elements are there?
For the first element of set C, we have "n" possible elements to pick from set B;
For the second element of set C, we have (since repetition is allowed) "n" possible elements to pick from set B;
....
For the last element of set C, we have, again, "n" possible elements to pick from set B.
Therefore, the number of possible arrangements with repetition is $N=n*n*.....*n=n^p$.
For example, let's consider the set B={2, 3, 5}. How many arrangements with 2 elements with repetition are there?
These are the arrangements: (2, 2), (2, 3), (2, 5), (3, 2), (3, 3), (3, 5), (5, 2), (5, 3) and (5, 5), that is, 9 arrangements.
Using the formula: $N=n^p=3^2=9$.
Arrangements without Repetition
Let's consider a set B, with "n" elements. Now we want to form a set C, with "p" elements (p < n), extracted from set B, WITHOUT repetition. How many different arrangements of "p" elements are there?
For the first element of set C, we have "n" possible elements to pick from set B;
For the second element of set C, we have "n-1" possible elements to pick from set B;
....
For the last element of set C, we have "n-(p-1)" possible elements to pick from set B.
Therefore, the number of possible arrangements without repetition is $A_{n,p}=n.(n-1).(n-2)....(n-(p-1))$. Using the factorial notation $A_{n,p}=\frac{n!}{(n-p)!}$.
For example, let's consider the set A={2, 3, 5}. How many arrangements with 2 elements WITHOUT repetition are there?
These are the arrangements: (2, 3), (2, 5), (3, 2), (3, 5), (5, 2), and (5, 3), that is, 6 arrangements.
Using the formula: $A_{n,p}=\frac{n!}{(n-p)!}=\frac{3!}{(3-2)!}=\frac{3!}{1!}=6$.
Combinations
In Arrangements, as seen before, the order of the elements is important. The set B={2, 3, 5}, for example, has the following 9 arrangements with 2 elements: (2, 2), (2, 3), (2, 5), (3, 2), (3, 3), (3, 5), (5, 2), (5, 3) e (5, 5). Note that the arrangements (2, 3) and (3, 2) are considered distinct.
In Combinations we consider (2, 3) and (3, 2) one single set.
The formula for the number of arrangements was: $A_{n,p}=\frac{n!}{(n-p)!}$.
In order to calculate the number of Combinations, we have to divide this formula by the number of possible permutations within each arrangement, that is, $p!$. Thus, the number of Combinations is given by the formula:
$C_{n,p}=\frac{A_{n,p}}{p!}=\frac{n!}{p!(n-p)!}$.
Back to our example, the set A={2, 3, 5} has 9 distinct arrangements with 2 elements: (2, 2), (2, 3), (2, 5), (3, 2), (3, 3), (3, 5), (5, 2), (5, 3) and (5, 5). Removing duplicities, it remains the following sets (2, 3), (2, 5) and (3, 5). Thus, the set A={2, 3, 5} has 3 Combinations of 2 elements each.
Using the formula:
$C_{n,p}=\binom{n}{p}=\frac{3!}{2!(3-2)!}=\frac{3!}{2!(1)!}=3$.
Ordered Pairs from Distinct Sets
Consider sets A (with "r" elements) and B (with "s" elements), so that A={$a_1, a_2, ..., a_r$} and B={$b_1, b_2, ..., b_s$}. How many ordered pairs ($a_i, b_j$) are there?
There are
"s" elements with $a_1$: ($a_1, b_1$), ($a_1, b_2$), ..., ($a_1, b_s$)
"s" elements with $a_2$: ($a_2, b_1$), ($a_2, b_2$), ..., ($a_2, b_s$)
....
"s" elements with $a_r$: ($a_r, b_1$), ($a_r, b_2$), ..., ($a_r, b_s$)
Since there are "r" elements in set A, there will be "r" lines with "s" elements each. Thus the total number of ordered pairs is $N=r.s$.
Ordered Pairs with distinct elements from one single set
Consider now set C={$c_1, c_2, ..., c_n$}. How many ordered pairs ($c_i, c_j$) are there, so that $i\neq{j}$?
Each element in set C will be combined with all other elements in set C. There are:
"n-1" elements with $c_1$: ($c_1, c_2$), ($c_1, c_3$), ..., ($c_1, c_n$)
"n-1" elements with $c_2$: ($c_2, c_1$), ($c_2, c_3$), ..., ($c_2, c_n$)
....
"n-1" elements with $c_n$: ($c_n, c_1$), ($c_n, c_2$), ..., ($c_n, c_{n-1}$)
Since there are "n" elements in set C, there are "n" lines with "n-1" elements each. The total number of ordered pairs is $N=n.(n-1)$.
Solved SAT Practice Tests
Find Practice Tests in the following link: Additional Practice Tests - Combinatorial Analysis
No comments:
Post a Comment