Chapter 16: Combinatorics

Abstract:

In combinatorics we study the enumeration, combination, and permutations of sets of elements. Furthermore finite or countable discrete structures (for example finite sets, graphs) are studied. Enumerative combinatorics focuses on counting the number of certain combinatorial objects. A bijection of a finite set S onto itself is called a permutation of S. If S consist of n elements then there are n! possible permutations. The fundamental principle of counting tells us that if one event has j ∊ ℕ possible outcomes and a second independent event has k ∊ ℕ possible outcomes, then the number of possible outcomes for the combined events is given by j · k. Let S be a finite set with n elements. Then the number of subsets is 2ⁿ which includes the set S itself and the empty set. Let n ≥ 1, S be a set containing n elements and n₁, …, n_r be positive integers with n₁+ n₂+ … + n_r = n. Then there exist

different ordered partitions of S of the form (S₁, S₂,…, S_r), where S₁ contains n₁ elements, S₂ contains n₂ elements etc. Let A, B be two finite sets. The product set A×B of A and B is given by all ordered pairs (a, b), where a ∊ A and b ∊ B. If A has m elements and B has n elements, then A × B has m · n elements. Let n ≥ 1. The number of combinations C(n, r) of n objects taken r at the time is given by