Offensive Security Researcher & Quantum Cryptography Analyst

Counting and Probability: A Complete Guide to Combinatorics and Probability Theory

Abdul Wahab Junaid
Counting and Probability: A Comprehensive Guide

I use counting and probability whenever I need to reason about how many ways something can happen and how likely each outcome is. I think of combinatorics as the mathematics of counting arrangements, selections, and structures, while probability builds on top of that counting to assign likelihoods to events. I find this pairing important because it underlies algorithm analysis (expected running time), statistics, cryptography, machine learning, and everyday decision-making under uncertainty.

History and Background

I trace combinatorics back to ancient civilizations — Indian mathematicians studied permutations and combinations as early as the 6th century BCE in relation to Sanskrit prosody, and the Chinese and Arab mathematicians independently developed binomial coefficients. I see probability theory formally emerge much later, in the 17th century, through correspondence between Blaise Pascal and Pierre de Fermat in 1654, prompted by gambling problems posed by the Chevalier de Méré. I note that Jacob Bernoulli’s Ars Conjectandi (published posthumously in 1713) formalized the law of large numbers, and Pierre-Simon Laplace’s Théorie Analytique des Probabilités (1812) unified much of classical probability. In the 20th century, I see Andrey Kolmogorov’s 1933 axiomatization giving probability its modern, rigorous measure-theoretic foundation.

Problem Statement

I use counting techniques to answer questions like “how many ways can I arrange these objects?” or “how many subsets satisfy this property?” I use probability to answer “how likely is this event, given the space of possible outcomes?” Both fields exist to let me reason precisely about uncertainty and combinatorial structure rather than relying on intuition, which I find frequently misleads people (as in the famous birthday paradox).

Core Concepts

I rely on the following foundational ideas:

How It Works

When I approach a counting or probability problem, I follow this general process:

  1. I identify the sample space or the set of objects being arranged/selected.
  2. I determine whether order matters (permutation) or not (combination).
  3. I check whether repetition is allowed.
  4. I apply the appropriate counting formula or the multiplication/addition principle.
  5. For probability, I define the event of interest as a subset of the sample space.
  6. I compute the probability as the ratio of favorable outcomes to total outcomes (for equally likely outcomes), or I use conditional/Bayesian reasoning for dependent events.

Working Principle

I understand the internal logic of counting through two foundational principles: the rule of sum (if two events cannot occur together, the number of ways either can happen is the sum of the individual ways) and the rule of product (if one event can happen in $m$ ways and a second, independent event in $n$ ways, both can happen together in $m \times n$ ways). Probability builds directly on this counting foundation: once I know how many total outcomes exist and how many satisfy my event, I express probability as a ratio, then use axiomatic rules (additivity over disjoint events, complement rule) to combine probabilities of composite events.

Mathematical Foundation

I define the number of permutations of $n$ distinct objects taken $r$ at a time as:

$$ P(n, r) = \frac{n!}{(n-r)!} $$

I define the number of combinations as:

$$ C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!} $$

I state the binomial theorem as:

$$ (x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k $$

I define probability using Kolmogorov’s axioms: for a sample space $S$ and event $A \subseteq S$,

$$ 0 \le P(A) \le 1, \quad P(S) = 1, \quad P\left(\bigcup_i A_i\right) = \sum_i P(A_i) \text{ for disjoint } A_i $$

I define conditional probability as:

$$ P(A \mid B) = \frac{P(A \cap B)}{P(B)}, \quad P(B) > 0 $$

I state Bayes’ theorem as:

$$ P(A \mid B) = \frac{P(B \mid A) P(A)}{P(B)} $$

I define the expected value of a discrete random variable $X$ as:

$$ E[X] = \sum_{i} x_i P(X = x_i) $$

and variance as:

$$ \text{Var}(X) = E[(X – E[X])^2] = E[X^2] – (E[X])^2 $$

I prove the addition rule for non-disjoint events using inclusion-exclusion:

$$ P(A \cup B) = P(A) + P(B) – P(A \cap B) $$

which follows because summing $P(A) + P(B)$ double-counts the overlap $P(A \cap B)$, so I subtract it once to correct the count.

Diagrams

flowchart TD
    A[Define the problem] --> B{Counting or Probability?}
    B -->|Counting| C{Order matters?}
    C -->|Yes| D[Use Permutation formula]
    C -->|No| E[Use Combination formula]
    B -->|Probability| F[Define sample space S and event A]
    F --> G{Events independent?}
    G -->|Yes| H[Multiply individual probabilities]
    G -->|No| I[Apply conditional probability / Bayes theorem]
    D --> J[Return result]
    E --> J
    H --> J
    I --> J

Pseudocode

I write pseudocode for computing combinations efficiently (avoiding factorial overflow) below:

function COMBINATION(n, r):
    if r > n - r:
        r = n - r          // exploit symmetry C(n, r) = C(n, n-r)

    result = 1
    for i from 0 to r - 1:
        result = result * (n - i)
        result = result / (i + 1)

    return result

Step-by-Step Example

I compute the probability of drawing 2 aces from a standard 52-card deck when drawing 5 cards without replacement.

I first compute the total number of 5-card hands:

$$ \binom{52}{5} = 2{,}598{,}960 $$

I then compute the number of favorable hands (2 aces from 4, and 3 non-aces from 48):

$$ \binom{4}{2} \times \binom{48}{3} = 6 \times 17{,}296 = 103{,}776 $$

I compute the probability as:

$$ P(\text{exactly 2 aces}) = \frac{103{,}776}{2{,}598{,}960} \approx 0.0399 $$

I conclude there is roughly a 3.99% chance of this event.

Time Complexity

I compute $n!$ or $\binom{n}{r}$ using an iterative approach in $O(r)$ time when I use the incremental multiplication formula rather than computing full factorials, which would cost $O(n)$ each and risk overflow. For probability calculations involving enumeration of a sample space, I note that complexity depends heavily on the structure — enumerating all subsets is $O(2^n)$, while computing conditional probabilities from a precomputed table is $O(1)$. Best, average, and worst cases for combination computation are all $O(r)$ since the loop always runs a fixed number of iterations.

Space Complexity

I require only $O(1)$ auxiliary space for the iterative combination formula, since I maintain a running result rather than storing a full factorial table. If I precompute Pascal’s Triangle up to row $n$ for repeated queries, I require $O(n^2)$ space, though I can reduce this to $O(n)$ by keeping only the current and previous rows.

Correctness Analysis

I justify the permutation formula by noting that I have $n$ choices for the first position, $n-1$ for the second, and so on down to $n – r + 1$ for the $r$-th position, and multiplying these together gives $\frac{n!}{(n-r)!}$. I justify the combination formula by observing that each combination of $r$ objects corresponds to exactly $r!$ permutations (since order does not matter within the selection), so I divide the permutation count by $r!$. For probability, correctness follows directly from Kolmogorov’s axioms, from which I derive all further identities like the addition rule and Bayes’ theorem through pure logical/algebraic manipulation.

Advantages

Disadvantages

Applications

I use counting and probability in:

Implementation in C

I implement a function to compute combinations and use it to calculate a hypergeometric probability, with comments:

#include stdio.h>

// I compute C(n, r) iteratively to avoid overflow from large factorials
double combination(int n, int r) {
    if (r > n - r) {
        r = n - r; // I exploit symmetry to reduce iterations
    }
    double result = 1.0;
    for (int i = 0; i  r; i++) {
        result *= (n - i);
        result /= (i + 1);
    }
    return result;
}

int main() {
    // I compute the probability of drawing exactly 2 aces in a 5-card hand
    double totalHands = combination(52, 5);
    double favorableHands = combination(4, 2) * combination(48, 3);

    double probability = favorableHands / totalHands;

    printf("Total hands: %.0f\n", totalHands);
    printf("Favorable hands: %.0f\n", favorableHands);
    printf("Probability of exactly 2 aces: %.4f\n", probability);

    return 0;
}

Sample Input and Output

I run the program with the fixed values (n=52, r=5, aces=4, non-aces=48) hardcoded, producing:

Total hands: 2598960
Favorable hands: 103776
Probability of exactly 2 aces: 0.0399

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version