Combinatorics and Probability: Set Theory, Counting Rules, and Principles

Product Rule (Two Groups)

Used to find the number of ways to pick two representatives when one is a mathematics major and the other is a computer science major.

Sum Rule (Single Choice)

Used to find the number of ways one representative can be picked who is either a mathematics major or a computer science major.

Mutually Exclusive Task

The condition where a rule implies doing one of two things that cannot happen simultaneously.

Math & CS Selection

There are 16⋅325 total ways to pick one representative from 16 math majors and one from 325 CS majors.

Math OR CS Selection

There are 325+16 ways to pick one representative who is either a math major or a CS major.

Bit String Rules (Length ≤6)

Both the sum and product rules are used to add the number of strings of each length up to six.

Bit String Formula (Length ≤6)

"The formula (∑j=062j)−1 calculates the number of bit strings of length six or less, excluding the empty string. "

Complementary Counting

"To find strings of four letters containing 'x', subtract the number of strings without 'x' (254) from the total number of strings (264). +1"

Subtraction Rule

"Also known as the principle of inclusion-exclusion, used for bit strings that meet one of two conditions (e.g., starts with 00 or ends with 111). +1"

Sock Selection (Worst Case)

"To ensure 2 black socks from 12 brown and 12 black, 14 must be taken to account for picking all 12 brown first. +1"

Generalized Pigeonhole Principle

"If five balls are picked from two colors, at least ⌈5/2⌉=3 must have the same color. "

Targeted Color Certainty

"To be sure of having 3 blue balls when 10 red balls exist, 13 must be selected so that even if all 10 red are picked, 3 blue remain. "

Pigeonhole Principle (Sum 11)

"By grouping 10 integers into 5 subsets that sum to 11, selecting 7 integers ensures at least two pairs exist. +1"

Specific Bit String Count

"The number of bit strings of length 10 having exactly four 1s is C(10,4). "

"""At Most"" Bit Strings"

"Strings of length 8 with at most four 1s equals C(8,4)+C(8,3)+C(8,2)+C(8,1)+C(8,0). "

"""At Least"" Bit Strings"

"Calculated by subtracting the cases not met from the total (210), such as 210−C(10,3)−C(10,2)−C(10,1)−C(10,0). "

Coin Flip Outcomes

Flipping a coin 11 times results in 211 total possible outcomes.

r-combinations

"The number of r-combinations of a set with n elements equals C(n,r). "

Permutation Substrings (Glued)

"If CAB and BED are substrings, they must form CABED; permuting {CABED, F, G, H} results in 4![citestart]=24. "

Permutation Substrings (Separate)

"To find permutations with BA and FGH, treat (BA) and (FGH) as single items, resulting in 5![citestart]=120. +1"

Combinatorial Proof: k(kn)=n(k−1n−1)

Counts selecting a k-set from n and then choosing a distinguished element from that set.

Disjoint Subset Identity

(rn)(kr)=(kn)(r−kn−k) counts choosing a first subset and then a second subset from the remaining elements. +1

Gender Selection Identity

"(22n)=2(2n)+n2 counts choosing 2 people by picking 2 men, 2 women, or one of each sex. +1"