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 {A, B, C}\text{\{A, B, C\}} is identical to picking {C, B, A}\text{\{C, B, A\}} 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 rr distinguishable objects out of nn available distinct objects when order matters. The total number of ordered arrangements is given by the permutation formula:     P(n,r)=n!(n−r)!P(n, r) = \frac{n!}{(n - r)!}

    • For any selected group of rr items, there are r!r! possible ways to arrange them among themselves.

    • To eliminate the effect of order and treat all arrangements of the same rr items as identical, divide the permutation count by r!r!:     C(n,r)=P(n,r)r!=n!(n−r)!r!C(n, r) = \frac{P(n, r)}{r!} = \frac{n!}{(n - r)! r!}

  • Example (Selecting Balls):

    • Suppose there are 55 distinct balls and 22 balls are selected.

    • If order matters, the number of ways to pick 22 balls out of 55 is:     P(5,2)=5!(5−2)!=5×4=20P(5, 2) = \frac{5!}{(5 - 2)!} = 5 \times 4 = 20

    • If order does not matter, the 2!2! arrangements of the chosen pairs are treated as identical. Dividing by 2!2! yields the combination:     C(5,2)=P(5,2)2!=202=10C(5, 2) = \frac{P(5, 2)}{2!} = \frac{20}{2} = 10

    • If choosing 33 balls out of 55 without order, divide by 3!3! to treat all arrangements of the 33 chosen balls as identical.

Counting Principles and Formulas

  • Fundamental Counting Principle:

    • If one event can occur in mm distinct ways and a second event can occur in nn distinct ways, then the total number of ways the two events can occur in sequence is:     m×nm \times n
  • Permutations of nn Distinct Objects Taken rr at a Time (r≤nr \le n):

    • Used when selecting rr items from nn distinct items where order matters and repetition is not allowed:     P(n,r)=n!(n−r)!P(n, r) = \frac{n!}{(n - r)!}
  • Permutations with Identical (Indistinguishable) Objects:

    • Used when arranging nn total objects where n1n_1 objects are identical of type 1, n2n_2 objects are identical of type 2, …, and nkn_k objects are identical of type kk (such that n1+n2+⋯+nk=nn_1 + n_2 + \dots + n_k = n):     n!n1!n2!…nk!\frac{n!}{n_1! n_2! \dots n_k!}
  • Combinations of nn Distinct Objects Taken rr at a Time:

    • Used when selecting rr items from nn distinct items where order does not matter and repetition is not allowed:     C(n,r)=P(n,r)r!=n!(n−r)!r!C(n, r) = \frac{P(n, r)}{r!} = \frac{n!}{(n - r)! r!}

Probability Applications Using Counting Principles

  • Example 1: State Department of Transportation Highway Bids:

    • The Department of Transportation receives a list of 1616 bid submissions from companies for a new interstate highway section.

    • The state plans to hire 44 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 1616 objects taken 44 at a time:     C(16,4)=16!(16−4)!4!=16!12!4!=16×15×14×134×3×2×1=1820C(16, 4) = \frac{16!}{(16 - 4)! 4!} = \frac{16!}{12! 4!} = \frac{16 \times 15 \times 14 \times 13}{4 \times 3 \times 2 \times 1} = 1820

  • Example 2: Student Advisory Board Position Selection:

    • A student advisory board consists of 7070 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:     P(70,3)=70!(70−3)!=70!67!=70×69×68=328,440P(70, 3) = \frac{70!}{(70 - 3)!} = \frac{70!}{67!} = 70 \times 69 \times 68 = 328{,}440

    • Direct sequential reasoning: There are 7070 choices for Chair; after choosing the Chair, 6969 candidates remain for Secretary; after choosing the Secretary, 6868 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:     P(Specific 3 Members in Specific Roles)=1P(70,3)=1328,440P(\text{Specific 3 Members in Specific Roles}) = \frac{1}{P(70, 3)} = \frac{1}{328{,}440}

  • Example 3: Class Competition Representation:

    • A class consists of 3030 students.

    • A teacher randomly selects 33 students to represent the class at a competition without any specific order or assigned roles.

    • Total number of possible student groups (sample space size):     C(30,3)=30!(30−3)!3!=30×29×283×2×1=4060C(30, 3) = \frac{30!}{(30 - 3)! 3!} = \frac{30 \times 29 \times 28}{3 \times 2 \times 1} = 4060

    • Event: Selecting "you and your two best friends".

    • There is exactly 11 unique combination corresponding to this specific group of three people.

    • Probability of this event:     P(You and Two Best Friends)=1C(30,3)=14060P(\text{You and Two Best Friends}) = \frac{1}{C(30, 3)} = \frac{1}{4060}

  • Example 4: Playing Card Probability (Drawing 5 Diamonds):

    • A standard deck contains 5252 playing cards, which includes 1313 cards of each suit (Diamonds, Hearts, Clubs, Spades).

    • Sample Space (SS): Total ways to randomly draw 55 cards out of 5252 without regard to order:     N(S)=C(52,5)=52!(52−5)!5!=52!47!5!=2,598,960N(S) = C(52, 5) = \frac{52!}{(52 - 5)! 5!} = \frac{52!}{47! 5!} = 2{,}598{,}960

    • Event (AA): Selecting 55 Diamond cards.

    • Number of favorable outcomes (N(A)N(A)): Total ways to choose 55 Diamonds from the 1313 available Diamonds in the deck:     N(A)=C(13,5)=13!(13−5)!5!=13!8!5!=1287N(A) = C(13, 5) = \frac{13!}{(13 - 5)! 5!} = \frac{13!}{8! 5!} = 1287

    • Probability of drawing 55 Diamonds:     P(5 Diamonds)=N(A)N(S)=C(13,5)C(52,5)=12872,598,960P(\text{5 Diamonds}) = \frac{N(A)}{N(S)} = \frac{C(13, 5)}{C(52, 5)} = \frac{1287}{2{,}598{,}960}

  • Example 5: Jury Selection (US Justice System):

    • A court needs to select a 1212-member jury from a candidate pool of 7575 total people, consisting of 4040 men and 3535 women.

    • Sample Space (SS): Total ways to select 1212 jurors from 7575 candidates without restrictions or order:     N(S)=C(75,12)=75!(75−12)!12!=75!63!12!N(S) = C(75, 12) = \frac{75!}{(75 - 12)! 12!} = \frac{75!}{63! 12!}

    • Event (AA): Selecting a jury consisting of exactly 77 men and 55 women.

    • Ways to choose 77 men out of 4040 available men: C(40,7)C(40, 7).

    • Ways to choose 55 women out of 3535 available women: C(35,5)C(35, 5).

    • By the Fundamental Counting Principle, total favorable outcomes for Event AA:     N(A)=C(40,7)×C(35,5)N(A) = C(40, 7) \times C(35, 5)

    • Probability of selecting exactly 77 men and 55 women:     P(7 Men and 5 Women)=C(40,7)×C(35,5)C(75,12)P(\text{7 Men and 5 Women}) = \frac{C(40, 7) \times C(35, 5)}{C(75, 12)}

Advanced Counting Taxonomy and Multiset Combinations

  • Selection Taxonomy for choosing rr objects from nn total objects:

    1. With Order, Without Repetition: Permutation P(n,r)=n!(n−r)!P(n, r) = \frac{n!}{(n - r)!}

    2. Without Order, Without Repetition: Combination C(n,r)=n!(n−r)!r!C(n, r) = \frac{n!}{(n - r)! r!}

    3. With Order, With Repetition Allowed: π(n,r)=nr\pi(n, r) = n^r

    • Each of the rr available positions can be filled independently by any of the nn objects.
    1. Without Order, With Repetition Allowed: Multiset Combination H(n,r)=C(n+r−1,r)H(n, r) = C(n + r - 1, r)
  • Derivation and Logic of Multiset Combination Formula H(n,r)H(n, r) (Stars and Bars Method):

    • Selecting rr objects from nn types with repetition allowed and order ignored.

    • Example: Choosing r=2r = 2 items from n=3n = 3 distinct types (A,B,CA, B, C) with repetition allowed.

    • All possible combinations: {AA, AB, AC, BB, BC, CC}\text{\{AA, AB, AC, BB, BC, CC\}}. Total count = 66.

    • Generalization using walls/bars and identical balls/stars:

    • To partition nn distinct object types, n−1n - 1 internal walls (separators) are required.

    • To represent the selection of rr objects, rr identical balls are placed among the compartments.

    • Total positions needed for both walls and balls: (n−1)+r(n - 1) + r

    • Selecting locations for the rr balls among (n+r−1)(n + r - 1) total positions yields:       C(n+r−1,r)=(n+r−1)!(n−1)!r!C(n + r - 1, r) = \frac{(n + r - 1)!}{(n - 1)! r!}

    • Evaluating for n=3n = 3 and r=2r = 2:       C(3+2−1,2)=C(4,2)=4!2!2!=244=6C(3 + 2 - 1, 2) = C(4, 2) = \frac{4!}{2! 2!} = \frac{24}{4} = 6

Random Variables: Discrete vs. Continuous

  • Definition of Random Variable:

    • A random variable XX 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: X=number of asthma attacks experienced by a patient in one monthX = \text{number of asthma attacks experienced by a patient in one month}. Possible values: 0,1,2,3,…0, 1, 2, 3, \dots

    • Example 2: Y=number of correct answers on a 20-question quizY = \text{number of correct answers on a 20-question quiz}. Possible values: 0,1,2,…,200, 1, 2, \dots, 20

    • Example 3: Rolling a standard die. Possible values: 1,2,3,4,5,61, 2, 3, 4, 5, 6

  • Continuous Random Variables:

    • Variables that can potentially take on any real numerical value within a given interval, constrained only by measurement precision.

    • Example 1: A=systolic blood pressureA = \text{systolic blood pressure}. Can take any continuous decimal value within a physiological range.

    • Example 2: B=amount of time spent studying for an examB = \text{amount of time spent studying for an exam}. Can take values like 1 h1\,\text{h}, 0.5 h0.5\,\text{h}, 2.67 h2.67\,\text{h}, etc.

    • Example 3: Height measurements of individuals.

Discrete Probability Distributions

  • A discrete probability distribution lists every possible value xx that a discrete random variable XX can assume, along with its corresponding probability P(x)P(x).

  • Mandatory Mathematical Conditions:

    1. The probability of every outcome xx must be between 00 and 11 inclusive:      0≤P(x)≤10 \le P(x) \le 1

    2. The sum of all probabilities across all possible outcomes must equal 11 (100%100\%):      ∑P(x)=1\sum P(x) = 1

  • Steps to Construct a Discrete Probability Distribution:

    1. Define the discrete random variable XX and list all possible outcomes x1,x2,…,xnx_1, x_2, \dots, x_n

    2. Create a frequency distribution listing the frequency ff for each outcome xx

    3. Calculate the sum of all frequencies: ∑f\sum f

    4. Determine the probability P(x)P(x) of each outcome by computing its relative frequency:      P(x)=f∑fP(x) = \frac{f}{\sum f}

    5. Verify that 0≤P(x)≤10 \le P(x) \le 1 for all xx and that ∑P(x)=1\sum P(x) = 1

Discrete Probability Distribution Examples and Histograms

  • Example 1: Tossing Two Coins:

    • Random variable X=number of headsX = \text{number of heads}.

    • Sample space: {TT, TH, HT, HH}\text{\{TT, TH, HT, HH\}}. Total outcomes = 44.

    • Distribution mapping:

    • X=0X = 0 (TT\text{TT}): Frequency f=1f = 1, P(0)=14=0.25P(0) = \frac{1}{4} = 0.25

    • X=1X = 1 (TH, HT\text{TH, HT}): Frequency f=2f = 2, P(1)=24=0.50P(1) = \frac{2}{4} = 0.50

    • X=2X = 2 (HH\text{HH}): Frequency f=1f = 1, P(2)=14=0.25P(2) = \frac{1}{4} = 0.25

    • Verification: P(x)∈[0,1]P(x) \in [0, 1] and ∑P(x)=0.25+0.50+0.25=1.00\sum P(x) = 0.25 + 0.50 + 0.25 = 1.00

  • Example 2: Personality Inventory Test for Passive-Aggressive Traits:

    • An industrial psychologist administers a personality inventory test to 150150 employees.

    • Score XX is an integer from 11 to 55:

    • 1=extremely passive1 = \text{extremely passive}

    • 3=neutral3 = \text{neutral}

    • 5=extremely aggressive5 = \text{extremely aggressive}

    • Survey Data and Probability Calculations (Total N=∑f=150N = \sum f = 150):

    • Score x=1x = 1: f=24f = 24 employees   ⟹  P(1)=24150=0.16\implies P(1) = \frac{24}{150} = 0.16

    • Score x=2x = 2: f=33f = 33 employees   ⟹  P(2)=33150=0.22\implies P(2) = \frac{33}{150} = 0.22

    • Score x=3x = 3: f=42f = 42 employees   ⟹  P(3)=42150=0.28\implies P(3) = \frac{42}{150} = 0.28

    • Score x=4x = 4: f=30f = 30 employees   ⟹  P(4)=30150=0.20\implies P(4) = \frac{30}{150} = 0.20

    • Score x=5x = 5: f=21f = 21 employees   ⟹  P(5)=21150=0.14\implies P(5) = \frac{21}{150} = 0.14

    • Verification:

    • Every probability P(x)P(x) satisfies 0≤P(x)≤10 \le P(x) \le 1

    • Sum of probabilities: 0.16+0.22+0.28+0.20+0.14=1.000.16 + 0.22 + 0.28 + 0.20 + 0.14 = 1.00

  • Geometric Properties of Probability Histograms:

    • A discrete probability distribution can be visually represented using a histogram where the x-axis contains values xx and the y-axis represents probabilities P(x)P(x).

    • If the width of each bin interval on the x-axis is set to 11, then the area of each rectangular bar is given by:     Area=Width×Height=1×P(x)=P(x)\text{Area} = \text{Width} \times \text{Height} = 1 \times P(x) = P(x)

    • Consequently, the total area of all bars in a discrete probability histogram equals ∑P(x)=1\sum P(x) = 1.

    • This area principle forms the theoretical foundation for continuous probability distributions, where the total area under a continuous probability density curve equals 11.