Examples

• The binomial coefficient
  Binomial coefficient
  In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the binomial coefficient indexed by n and k is usually written \tbinom nk , and it is the coefficient of the x k term in...
  
    is the number of size-k subsets of a size-n set. A basic identity, one of whose consequences is that these are precisely the numbers appearing in Pascal's triangle
  Pascal's triangle
  In mathematics, Pascal's triangle is a triangular array of the binomial coefficients in a triangle. It is named after the French mathematician, Blaise Pascal...
  
  , states that:

Proof: In a size-(n + 1) set, choose one distinguished element. The set of all size-k subsets contains: (1) all size-k subsets that do contain the distinguished element, and (2) all size-k subsets that do not contain the distinguished element. If a size-k subset of a size-(n + 1) set does contain the distinguished element, then its other k − 1 elements are chosen from among the other n elements of our size-(n + 1) set. The number of ways to choose those is therefore . If a size-k subset does not contain the distinguished element, then all of its k members are chosen from among the other n "non-distinguished" elements. The number of ways to choose those is therefore .

• The number of subsets of any size-n set is 2ⁿ.

Proof: We use mathematical induction

Mathematical induction

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...

. The basis for induction is the truth of this proposition in case n = 0. The empty set

Empty set

In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...

 has 0 members and 1 subset, and 2⁰ = 1. The induction hypothesis is the proposition in case n; we use it to prove case n + 1. In a size-(n + 1) set, choose a distinguished element. Each subset either contains the distinguished element or does not. If a subset contains the distinguished element, then its remaining elements are chosen from among the other n elements. By the induction hypothesis, the number of ways to do that is 2ⁿ. If a subset does not contain the distinguished element, then it is a subset of the set of all non-distinguished elements. By the induction hypothesis, the number of such subsets is 2ⁿ. Finally, the whole list of subsets of our size-(n + 1) set contains 2ⁿ + 2ⁿ = 2ⁿ⁺¹ elements.

• Let B_n be the nth Bell number
  Bell number
  In combinatorics, the nth Bell number, named after Eric Temple Bell, is the number of partitions of a set with n members, or equivalently, the number of equivalence relations on it...
  
  , i.e., the number of partitions of a set
  Partition of a set
  In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
  
   of n members. Let C_n be the total number of "parts" (or "blocks", as combinatorialists often call them) among all partitions of that set. For example, the partitions of the size-3 set {a, b, c} may be written thus:

We see 5 partitions, containing 10 blocks, so B₃ = 5 and C₃ = 10. An identity states:

Proof: In a size-(n + 1) set, choose a distinguished element. In each partition of our size-(n + 1) set, either the distinguished element is a "singleton", i.e., the set containing only the distinguished element is one of the blocks, or the distinguished element belongs to a larger block. If the distinguished element is a singleton, then deletion of the distinguished element leaves a partition of the set containing the n non-distinguished elements. There are B_n ways to do that. If the distinguished element belongs to a larger block, then its deletion leaves a block in a partition of the set containing the n non-distinguished elements. There are C_n such blocks.

See also

• Combinatorial principles
  Combinatorial principles
  In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used.The rule of sum, rule of product, and inclusion-exclusion principle are often used for enumerative purposes. Bijective proofs are utilized to demonstrate that two sets...
  
  
• Combinatorial proof
  Combinatorial proof
  In mathematics, the term combinatorial proof is often used to mean either of two types of proof of an identity in enumerative combinatorics that either states that two sets of combinatorial configurations, depending on one or more parameters, have the same number of elements , or gives a formula...