Combinatorics

Multiplication principle:
  If task A has m ways and task B has n ways,
  doing both (in sequence) has m × n ways.

Addition principle:
  If task A has m ways and task B has n ways (mutually exclusive),
  doing one OR the other has m + n ways.

Complement principle:
  Count of "at least one" = Total - Count of "none"
  |A| = |U| - |A'|

Example (passwords):
  8-character password, lowercase letters only:
  26^8 = 208,827,064,576 possibilities

  Add digits (36 chars): 36^8 = 2,821,109,907,456
  Add uppercase + symbols (72 chars): 72^8 = 722,204,136,308,736

Permutation: arrangement where ORDER MATTERS

n! = n × (n-1) × (n-2) × ... × 1    (n factorial)
0! = 1    (by convention)

P(n, r) = n! / (n-r)!    (r items chosen from n, order matters)

Examples:
  Arrange 5 books on shelf: 5! = 120
  Choose president, VP, secretary from 10: P(10,3) = 10×9×8 = 720
  Arrange letters of "HELLO": 5!/2! = 60 (repeated L)

n items with groups of identical items:
  n! / (n1! × n2! × ... × nk!)

Example: arrangements of "MISSISSIPPI"
  11 letters: M(1), I(4), S(4), P(2)
  11! / (1! × 4! × 4! × 2!) = 34,650

Circular permutations (seating around a table):
  (n-1)!    (fix one position, arrange the rest)
  10 people around a table: 9! = 362,880

Combination: selection where ORDER DOES NOT MATTER

C(n, r) = n! / (r! × (n-r)!)    (also written as "n choose r")

Properties:
  C(n, 0) = C(n, n) = 1
  C(n, 1) = C(n, n-1) = n
  C(n, r) = C(n, n-r)           (symmetry)
  C(n, r) = C(n-1, r-1) + C(n-1, r)   (Pascal's identity)

Examples:
  Choose 3 from 10: C(10,3) = 120
  Poker hand (5 from 52): C(52,5) = 2,598,960
  Lottery (6 from 49): C(49,6) = 13,983,816

Row 0:                 1
Row 1:               1   1
Row 2:             1   2   1
Row 3:           1   3   3   1
Row 4:         1   4   6   4   1
Row 5:       1   5  10  10   5   1

Entry at row n, position r = C(n, r)
Each number = sum of two numbers above it
Row n sums to 2^n

IP subnet combinations:
  /24 network: 2^8 - 2 = 254 usable hosts
  /16 network: 2^16 - 2 = 65,534 usable hosts

ACL rule combinations:
  10 source networks, 5 destinations, 3 protocols:
  10 × 5 × 3 = 150 possible rules

Password entropy (bits):
  H = log_2(N^L) = L × log_2(N)
  8 chars, 72 symbols: 8 × log_2(72) ≈ 49.4 bits
  12 chars, 72 symbols: 12 × log_2(72) ≈ 74.0 bits
  20 chars, lowercase: 20 × log_2(26) ≈ 94.0 bits (passphrase wins)

Key space:
  AES-128: 2^128 ≈ 3.4 × 10^38 possible keys
  AES-256: 2^256 ≈ 1.2 × 10^77 possible keys

Binary strings of length n:        2^n
Subsets of n elements:             2^n
Bit masks for n flags:             2^n
Paths in binary tree (depth d):    2^d leaves
Binary search steps:               log_2(n) = O(log n)

Handshake problem (complete graph):
  n people, each shakes hands with everyone else:
  C(n, 2) = n(n-1)/2 edges

TCP connections between n hosts:
  C(n, 2) = n(n-1)/2 possible connections
  100 hosts: 4,950 possible connections

If n items are put into m containers and n > m,
then at least one container has more than one item.

Generalized: at least one container has ⌈n/m⌉ items.

Examples:
  13 people → at least 2 share a birth month
  367 people → at least 2 share a birthday (366 + 1)
  n+1 numbers from {1,...,2n} → at least 2 are consecutive

CS application:
  Hash table with m slots, n > m keys → collisions are guaranteed
  Lossless compression: cannot compress ALL files (pigeonhole on mappings)