Counting Methods

• Counting helps us determine the number of outcomes in a sample space

Permutations

• A permutation is an ordered sequence of distinguishable objects
  • Each such permutation is called a $k$-permutation, where you fix $k$ to be the number of objects in each permutation
  • $(n)_k$: the number of possible $k$-permutations for $n$ distinguishable objects

Application: Sampling Without Replacement (With Ordering)

• Permutations are really useful when evaluating the number of ways you can sample a group of objects without replacement
  • This is because counting the number of arrangements is always without replacement, since no two objects can exist in the same place at the same time, and you’re assuming all the objects are distinguishable to begin with

Combinations

• A combination is an unordered set of objects taken from the sample space
  • Similar to permutations, the $k$-combination would be sets of length $k$
  • The unordered property is important! It means that all sets containing the same elements are identical, no matter what order they’re in
  • $n \choose k$: denotes the number of $k$-combinations for a collection of $n$ objects; also called “$n$ choose $k$”
• Different than permutation because the order doesn’t matter!
  • Also has a fewer number (for any fixed $n$ and $k$) than permutation, since you’re overcounting the number of sets that are the same in permutation (specifically by a factor of $k!$)

Application: Sampling Without Replacement (And Without Ordering)

• Similar to permutation, combination is also good for sampling without replacement, but with the caveat that the order doesn’t matter
  • So, you could observe some sequence of events or objects, but ultimately, as long as they were the same objects, they are considered the same under the combination POV

Binomial Coefficients

• Combinations are also very useful in mathematics; we will show this in more detail below
• “$n$ choose $k$” is also called a Binomial coefficient (and is only defined for $k, n \gt 0$), and is written as: $\binom{n}{k}$
  • Also has this property: $\binom{n}{k} = \binom{n}{n-k}$
  • This is basically indicative of the symmetry of the combination formula; if you fix the number of objects in the experiment and iterate over $k$, you’ll notice that the values of $\binom{n}{k}$ will start to “mirror” the first half (before $n/2$)

Independent Trials

• Sampling with replacement means you select an object, replace it, then repeat
• Each repetition is the same subexperiment
• The repetitions are independent trials

• Notation
  • $x_i$ outcome of trial $i$
  • Observation sequence $x_1x_2\cdots x_n$
  • Sample space $S$ is the set of all length $n$ observation sequences

Application

• Laptop has USB slots $A$ and $B$

• Each slot uses one device type from $\{m,c,p\}$

• With replacement across slots since the same device type may be used twice

• Outcomes written as ordered pairs

  • First entry for slot $A$
  • Second entry for slot $B$

• Sample space

• $|S|=9$

Proof. Each position in the ordered sample has $m$ choices Apply the multiplication principle across $n$ positions

Binary Sequences

• For a binary alphabet $\{0,1\}$
• Number of length $n$ sequences

• Example
  • $2^{10}=1024$

Alphabet Words

• For letters $A$ through $Z$
• Number of length $n$ words

• Example
  • $26^4=456{,}976$

Repeated Testing Example

• Subexperiment sample space

• Record $x_i=0$ for failure and $x_i=1$ for success
• Testing four microprocessors gives a length $4$ observation sequence
• Sample space size

Proof. Each trial contributes one symbol from $m$ possibilities Apply the multiplication principle across $n$ trials

Grouping Outcomes by Counts

• Often the order in the observation sequence is not the object of interest
• The counts of each symbol is the object of interest
• Group sequences by how many times each symbol appears

Binary Case

• Subexperiment sample space

• Run $n$ trials
• Let $n_0$ be the number of zeros
• Let $n_1$ be the number of ones
• Constraint

• Example
  • Five trials
  • $n_0=2$
  • $n_1=3$
  • The sequences are the length $5$ strings with two zeros and three ones

Proof. Choose the $n_1$ trial indices where a $1$ appears The remaining indices contain $0$

Multigroup Case

• Subexperiment sample space

• Run $n$ trials
• Let $n_i$ be the number of occurrences of symbol $s_i$
• Constraint

Proof. Start with $n!$ permutations of $n$ labeled positions Symbols of the same type are indistinguishable in the final sequence Divide by $n_i!$ for each subgroup of identical symbols

Multinomial Coefficient

• The multigroup counting formula appears repeatedly
• Use a single notation for it

• Interpretation

  • Number of permutations of $n$ objects grouped into $m$ subgroups
  • Subgroup $i$ has size $n_i$
  • Objects inside a subgroup are treated as identical

• Same formula as multigroup sequence counting

  • Both count arrangements of $n$ slots filled with repeated types
  • The only input is the subgroup sizes $n_i$

Example

• Ten students
• Grade set $S_{\text{sub}}=\{A,B,C,F\}$
• A grade list for the class is an observation sequence of length $10$
• Total number of grade lists

• Curved distribution
  • $n_A=2$
  • $n_B=3$
  • $n_C=3$
  • $n_F=2$
• Number of grade lists matching the curve

$$ \binom{10}{2,3,3,2}

\frac{10!}{2!,3!,3!,2!} $$

Independent Trials With Probabilities

• Counting gives the number of sequences
• Probability assigns weight to each sequence
• For independent trials, multiply trial probabilities along the sequence

Binary Outcome Trials

• Success probability

• Failure probability

• For a fixed sequence with $n_1$ successes and $n_0$ failures

• Example
  • Five trials
  • Two failures and three successes
  • Each such sequence has probability

• Number of such sequences

• Add the probabilities of all such sequences

Proof. Each sequence with $n_1$ successes has probability $p^{n_1}(1-p)^{n_0}$ The number of such sequences is $\binom{n}{n_1}$ Multiply

Binomial Coefficients as Counts

• $\binom{n}{n_1}$ counts the number of sequences with $n_1$ successes
• The probability formula is a count times a per-sequence probability
• When $p\ne \tfrac12$, outcomes with the same count still share the same probability
  • independence gives the same product for each arrangement of the same counts

Information Bit Repetition Example

• Transmit one bit five times
  • $0$ sent as $00000$
  • $1$ sent as $11111$
• Receiver decides correct bit if at least three of the five received symbols match
• Let $q$ be symbol error probability
• Let $p=1-q$ be symbol correct probability
• Error event occurs when number of correct symbols is less than $3$
  • $E_{5,0}$
  • $E_{4,1}$
  • $E_{3,2}$
• Error probability

$$ P[E]

P[E_{5,0}]+P[E_{4,1}]+P[E_{3,2}]

\binom{5}{5}q^5+\binom{5}{4}q^4p+\binom{5}{3}q^3p^2 $$

Multigroup Independent Trials

• Subexperiment sample space

• Trial probabilities

• In $n$ independent trials
  • count vector $(n_0,\dots,n_{m-1})$
  • with $\sum n_i=n$

Proof. Each fixed sequence with counts $(n_0,\dots,n_{m-1})$ has probability $\prod p_i^{n_i}$ The number of such sequences is the multinomial coefficient Multiply

Equal Probability Grade Example

• Grades $A,B,C,F$ equally likely

• Event $E_{2,3,3,2}$

$$ P[E_{2,3,3,2}]

\binom{10}{2,3,3,2} \left(\tfrac14\right)^{10} $$

Binomial Theorem

• Binomial coefficients appear in counting
• The same coefficients appear in algebraic expansions

Proof. Expand $(x+y)^n$ as a product of $n$ factors A term $x^{n-k}y^k$ arises from choosing $k$ factors to contribute $y$ The number of such choices is $\binom{n}{k}$

Link to Independent Trials

• Substitute $x=1-p$ and $y=p$

• Expansion

• Terms match probabilities of $k$ successes in $n$ trials
• Sum over $k$ gives total probability $1$

Binary Outcomes With $n$ Successes and $k$ Failures

• Total trials

• Event
  • successes $n$
  • failures $k$
• Probability

$$ P[E_{k,n}]

\binom{n+k}{n}(1-p)^k p^n

\binom{n+k}{k}(1-p)^k p^n $$

References

• Course lecture slides 7
• Course lecture slides 8
• Course lecture slides 9–10