Definition
Let
A
{\displaystyle {\mathcal {A}}}
be a family of subsets of the set
A
{\displaystyle A}
and let
x
∈
A
{\displaystyle x\in A}
be a distinguished element of set
A
{\displaystyle A}
. Then suppose there is a predicate
P
(
X
,
x
)
{\displaystyle P(X,x)}
that relates a subset
X
⊆
A
{\displaystyle X\subseteq A}
to
x
{\displaystyle x}
. Denote
A
(
x
)
{\displaystyle {\mathcal {A}}(x)}
to be the set of subsets
X
{\displaystyle X}
from
A
{\displaystyle {\mathcal {A}}}
for which
P
(
X
,
x
)
{\displaystyle P(X,x)}
is true and
A
−
x
{\displaystyle {\mathcal {A}}-x}
to be the set of subsets
X
{\displaystyle X}
from
A
{\displaystyle {\mathcal {A}}}
for which
P
(
X
,
x
)
{\displaystyle P(X,x)}
is false, Then
A
(
x
)
{\displaystyle {\mathcal {A}}(x)}
and
A
−
x
{\displaystyle {\mathcal {A}}-x}
are disjoint sets, so by the method of summation, the cardinalities are additive
|
A
|
=
|
A
(
x
)
|
+
|
A
−
x
|
{\displaystyle |{\mathcal {A}}|=|{\mathcal {A}}(x)|+|{\mathcal {A}}-x|}
Thus the distinguished element allows for a decomposition according to a predicate that is a simple form of a divide and conquer algorithm. In combinatorics, this allows for the construction of recurrence relations. Examples are in the next section.
Examples
- The binomial coefficient
(
n
k
)
{\displaystyle {n \choose k}}
is the number of size-k subsets of a size-n set. A basic identity—one of whose consequences is that the binomial coefficients are precisely the numbers appearing in Pascal's triangle—states that:
(
n
k
−
1
)
+
(
n
k
)
=
(
n
+
1
k
)
.
{\displaystyle {n \choose k-1}+{n \choose k}={n+1 \choose k}.}
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
(
n
k
−
1
)
{\displaystyle {n \choose k-1}}
. 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
(
n
k
)
{\displaystyle {n \choose k}}
.
- The number of subsets of any size-n set is 2n.
Proof: We use
mathematical induction. The basis for induction is the truth of this proposition in case
n = 0. The
empty set has 0 members and 1 subset, and 20 = 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
n. 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
n. Finally, the whole list of subsets of our size-(
n + 1) set contains 2
n + 2
n = 2
n+1 elements.
- Let Bn be the nth Bell number, i.e., the number of partitions of a set of n members. Let Cn 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:
a
b
c
a
/
b
c
b
/
a
c
c
/
a
b
a
/
b
/
c
{\displaystyle {\begin{matrix}abc\\a/bc\\b/ac\\c/ab\\a/b/c\end{matrix}}}
We see 5 partitions, containing 10 blocks, so
B3 = 5 and
C3 = 10. An identity states:
B
n
+
C
n
=
B
n
+
1
.
{\displaystyle B_{n}+C_{n}=B_{n+1}.}
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
Bn 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
Cn such blocks.
See also
References
Petkovšek, Marko; Tomaž Pisanski (November 2002). "Combinatorial Interpretation of Unsigned Stirling and Lah Numbers" (PDF). University of Ljubljana Preprint Series. 40 (837): 1–6. Retrieved 12 July 2013. http://www.imfm.si/preprinti/PDF/00837.pdf