Combinations, Counting Principles, and Discrete Probability Distributions
Combinations and Permutations
Combinations focus on selecting items from a group when the order of selection does not matter, and repetition is not allowed.
In permutation problems, selecting item order matters (for example, the sequence black then white is treated as distinct from white then black).
In combination problems, picking the set is identical to picking because arrangement order is completely disregarded.
Combinations are utilized in statistics when the specific identities of chosen items matter, but the arrangement order does not.
Derivation of Combination Formula from Permutation Formula:
Consider selecting distinguishable objects out of available distinct objects when order matters. The total number of ordered arrangements is given by the permutation formula:
For any selected group of items, there are possible ways to arrange them among themselves.
To eliminate the effect of order and treat all arrangements of the same items as identical, divide the permutation count by :
Example (Selecting Balls):
Suppose there are distinct balls and balls are selected.
If order matters, the number of ways to pick balls out of is:
If order does not matter, the arrangements of the chosen pairs are treated as identical. Dividing by yields the combination:
If choosing balls out of without order, divide by to treat all arrangements of the chosen balls as identical.
Counting Principles and Formulas
Fundamental Counting Principle:
- If one event can occur in distinct ways and a second event can occur in distinct ways, then the total number of ways the two events can occur in sequence is:
Permutations of Distinct Objects Taken at a Time ():
- Used when selecting items from distinct items where order matters and repetition is not allowed:
Permutations with Identical (Indistinguishable) Objects:
- Used when arranging total objects where objects are identical of type 1, objects are identical of type 2, …, and objects are identical of type (such that ):
Combinations of Distinct Objects Taken at a Time:
- Used when selecting items from distinct items where order does not matter and repetition is not allowed:
Probability Applications Using Counting Principles
Example 1: State Department of Transportation Highway Bids:
The Department of Transportation receives a list of bid submissions from companies for a new interstate highway section.
The state plans to hire of these companies with no ranking, hierarchy, or order among them (no first, second, third, or fourth place).
Selection process requires finding the number of combinations of objects taken at a time:
Example 2: Student Advisory Board Position Selection:
A student advisory board consists of total members.
Three members are selected for specific titled positions: Chair, Secretary, and Webmaster.
Because each position has a distinct title and role, order matters.
Number of distinct ways to fill the positions:
Direct sequential reasoning: There are choices for Chair; after choosing the Chair, candidates remain for Secretary; after choosing the Secretary, candidates remain for Webmaster.
Assuming each member is equally likely to serve in any position, the probability of selecting a specific randomly chosen three-member sequence for these positions is:
Example 3: Class Competition Representation:
A class consists of students.
A teacher randomly selects students to represent the class at a competition without any specific order or assigned roles.
Total number of possible student groups (sample space size):
Event: Selecting "you and your two best friends".
There is exactly unique combination corresponding to this specific group of three people.
Probability of this event:
Example 4: Playing Card Probability (Drawing 5 Diamonds):
A standard deck contains playing cards, which includes cards of each suit (Diamonds, Hearts, Clubs, Spades).
Sample Space (): Total ways to randomly draw cards out of without regard to order:
Event (): Selecting Diamond cards.
Number of favorable outcomes (): Total ways to choose Diamonds from the available Diamonds in the deck:
Probability of drawing Diamonds:
Example 5: Jury Selection (US Justice System):
A court needs to select a -member jury from a candidate pool of total people, consisting of men and women.
Sample Space (): Total ways to select jurors from candidates without restrictions or order:
Event (): Selecting a jury consisting of exactly men and women.
Ways to choose men out of available men: .
Ways to choose women out of available women: .
By the Fundamental Counting Principle, total favorable outcomes for Event :
Probability of selecting exactly men and women:
Advanced Counting Taxonomy and Multiset Combinations
Selection Taxonomy for choosing objects from total objects:
With Order, Without Repetition: Permutation
Without Order, Without Repetition: Combination
With Order, With Repetition Allowed:
- Each of the available positions can be filled independently by any of the objects.
- Without Order, With Repetition Allowed: Multiset Combination
Derivation and Logic of Multiset Combination Formula (Stars and Bars Method):
Selecting objects from types with repetition allowed and order ignored.
Example: Choosing items from distinct types () with repetition allowed.
All possible combinations: . Total count = .
Generalization using walls/bars and identical balls/stars:
To partition distinct object types, internal walls (separators) are required.
To represent the selection of objects, identical balls are placed among the compartments.
Total positions needed for both walls and balls:
Selecting locations for the balls among total positions yields:
Evaluating for and :
Random Variables: Discrete vs. Continuous
Definition of Random Variable:
A random variable is a numerical value determined by the outcome of a random process or probability experiment.
Because experiment outcomes are uncertain, the actual value assumed by a random variable remains uncertain until the experiment occurs.
Discrete Random Variables:
Variables that take on countable values (typically integer counting values).
Example 1: . Possible values:
Example 2: . Possible values:
Example 3: Rolling a standard die. Possible values:
Continuous Random Variables:
Variables that can potentially take on any real numerical value within a given interval, constrained only by measurement precision.
Example 1: . Can take any continuous decimal value within a physiological range.
Example 2: . Can take values like , , , etc.
Example 3: Height measurements of individuals.
Discrete Probability Distributions
A discrete probability distribution lists every possible value that a discrete random variable can assume, along with its corresponding probability .
Mandatory Mathematical Conditions:
The probability of every outcome must be between and inclusive:
The sum of all probabilities across all possible outcomes must equal ():
Steps to Construct a Discrete Probability Distribution:
Define the discrete random variable and list all possible outcomes
Create a frequency distribution listing the frequency for each outcome
Calculate the sum of all frequencies:
Determine the probability of each outcome by computing its relative frequency:
Verify that for all and that
Discrete Probability Distribution Examples and Histograms
Example 1: Tossing Two Coins:
Random variable .
Sample space: . Total outcomes = .
Distribution mapping:
(): Frequency ,
(): Frequency ,
(): Frequency ,
Verification: and
Example 2: Personality Inventory Test for Passive-Aggressive Traits:
An industrial psychologist administers a personality inventory test to employees.
Score is an integer from to :
Survey Data and Probability Calculations (Total ):
Score : employees
Score : employees
Score : employees
Score : employees
Score : employees
Verification:
Every probability satisfies
Sum of probabilities:
Geometric Properties of Probability Histograms:
A discrete probability distribution can be visually represented using a histogram where the x-axis contains values and the y-axis represents probabilities .
If the width of each bin interval on the x-axis is set to , then the area of each rectangular bar is given by:
Consequently, the total area of all bars in a discrete probability histogram equals .
This area principle forms the theoretical foundation for continuous probability distributions, where the total area under a continuous probability density curve equals .