Combinatory Theory: Permutations, Combinations and Probabilities
Combinatory Theory Lab Script: Permutations, Combinations and Probabilities. An Interdisciplinary Lab Script for Chemistry, EMarketing Strategies, Math and Statistics Courses.
Instructions
To the Instructor
- Discuss with students all theory relevant to the experiment.
- Feel free to modify the experiment title, description and any required observation.
- Use results to perform any statistical analysis or further computations.
Theory
The factorial of a number q is q!, where "!" is the factorial operator. Thus for q = 4 its factorial value is q! = 4x3x2x1. By definition 0! = 1.
A permutation is an arrangement of a group of n items taken r at a time in which sequence plays a role (order is of significance). The number of possible permutations is given by
p(n, r) = n!/(n - r)! = n!/(d)!, where d = n - r.
In the special case where r = n, we have p(n, r) = n!
EXAMPLE 1: JUNE consists of four letters. These letters are painted on four marbles, one on each marble. How many pairs of letters can be formed?
ANSWER: Since we are taken two items at a time r = 2 and n = 4. Therefore,
d = 4 - 2 = 2 and p(n, r) = p(4, 2) = 4!/2! = 12 arrangements. The arrangements are shown here » JU NE JN JE UN UE UJ EN NJ EJ NU EU
A combination is an arrangement of a group of n items taken r at a time in which sequence plays no role (order is of no significance). The number of possible combinations is given by
c(n, r) = n!/(r!(n - r)!) = n!/(r!(d!))
In the special case where r = n, we have c(n, r) = n!/r! = n!/n! = 1
EXAMPLE 2: How many straight lines are required to equally interconnect six points (nodes) distributed on a graph?
ANSWER: Since two points per line are required, we need to take r = 2 items at a time from a pool of n = 6 items. Therefore,
d = 6 - 2 = 4 and c(n, r) = c(6, 2) = 6!/(2!4!) = 15 lines. Check here » 
A circular permutation is a circular arrangement of a group of n items taken r at a time in which their relative sequence plays a role (relative order is of significance). The number of possible circular permutations is given by
cp(n, r) = n!/(r(n - r)!) = n!/(r(d!))
In the special case where r = n, we have cp(n, r) = n!/r = n!/n
EXAMPLE 3: A group consists of 7 individuals. Three individuals will be selected at random and seated at a round table. How many seating arrangements can be devised?
ANSWER: Since we are only interested in the relative order and 3 individuals are taken at a time, r = 3 and n = 7. Therefore,
d = 7 - 3 = 4 and cp(n, r) = cp(7, 3) = 7!/(3!4!) = 70 arrangements. A sample arrangement is shown here » 
Notes
Probability values can be obtained from the ratio of permutations or combinations.
EXAMPLE 4: A batch of 50 articles contains 5 defective articles. A quality control (QC) tranfer scientist inspects this batch by taking 3 articles at random. What is the probability that the selected articles are not defective?
ANSWER: 45 articles are not defective and 5 are. The number of possible ways of selecting 3 articles out of the batch is c(n, r) = c(50, r) = 50!/(3!45!) = 19,600 ways. The number of ways of selecting the 3 articles from the 45 articles without defects is c(n, r) = c(45, 3) = 45!/(3!42!) = 14,190. Thus, the probability that the selected articles are not defective is 14,190/19,600 = 0.72398 or about 72%.
Possible Experiments
- Chemistry: Quality Control of Batch Samples
- Statistics: Statistics and Game Theory
- Math: Trigonometry and Probability
Suggested Exercises
- Chemistry A batch of 100 manufactured chemical samples is checked by a QC chemistry inspector, who examines 10 chemical samples selected at random. If none of the 10 chemical samples is defective, he accepts the whole batch. Otherwise, the batch is subjected to further inspection. What is the probability that a batch containing 10 defective chemical samples will be accepted?
- Crystallography and Symmetry How many edges are in polyhedral entities (crystals, molecules) consisting of n = 4, n = 7 and n = 8 vertices. What is the chemical signifcance of your answer? Could combinatory theory breakdown in some cases? Explain.
- Quantum Chemistry Suggest equations describing a relationship between combinatory theory and microstate theory.
- Statistics:Three cards are drawn at random from a full deck. What is the probability of getting a three, a seven and an ace?
- Math: What is the probability of being able to form a triangle from three segments chosen at random from five line segments of lengths 1, 3, 5, 7 and 9? Hint. A triangle cannot be formed if one segment is longer than the sum of the other two.
Advanced Exercises on EMarketing Strategies and Link Connectivity
To answer these exercises you must be familiarized with conditional probability, link connectivity and the so-called "page rank" metric.
- In EXAMPLE 2, assume that each node represents a web page (or a web site) and that each straight line represents a reciprocal link mechanism; that is, a link from a page A is pointing to a page B and a link from a page B is pointing to a page A. Thus the network of sites is fully cross-pollinated through 15 reciprocal link mechanisms. Assuming these are the only in/out links present in this "island" network, calculate the so-called "page rank" metric for each page. If a user visits a web page A, what is the probability that he/she will visit another page B from the network? What is the probability that after visiting page B, he/she will visit another page C from the network? Note that users can "click back", a fact ignored by the "page rank" metric.
- An "island" network consisting of 10 web pages is fully interconnected by links. Any 9 sites point to a given site, at least once. Thus the network is fully cross-pollinated. These are the only in/out links present in the network. How many reciprocal link mechanisms are required to equally distribute the "page rank" metric across the network? Under these idealized conditions, suggest equations describing a relationship between an equalized distribution of "page rank" values and combinatory theory. Could these observations be used to detect "link farms"? Why or why not?
- In EXAMPLE 3, assume that each node represents a web page (or a web site) and that each line represents a reciprocal link mechanism. Thus the network forms a prepatterned link structure known as a Web Ring. These are the only in/out links present in the network. Calculate the "page rank" metric of each site. If a user visits a web page A, what is the probability that he/she will visit another page B from the network? What is the probability that after visiting page B, he/she will visit another page C from the network? Note that users can "click back", a fact ignored by the "page rank" metric.
References
- Handbook of Applied Mathematics for Engineers and Scientists Max Kurtz; McGraw Hill, 1991.
- Random Processes in Physical Systems Charles A. Whitney; Wiley, 1990.
- Probability Theory: A Concise Course Y. A. Rozanov; Dover, 1969.
