Dependency graph

Legend

Boxes: definitions
Ellipses: theorems and lemmas
Blue border: the statement of this result is ready to be formalized; all prerequisites are done
Orange border: the statement of this result is not ready to be formalized; the blueprint needs more work
Blue background: the proof of this result is ready to be formalized; all prerequisites are done
Green border: the statement of this result is formalized
Green background: the proof of this result is formalized
Dark green background: the proof of this result and all its ancestors are formalized

Corollary 7.7

Let \(X_n = \{ 1, 2, \ldots , n\} \) and let \(F : \mathcal{P}(X_n) \to \Re \) be a function defined on the subsets of \(X_n\). Let \(G : \mathcal{P}(X_n) \to \Re \) be the function defined by

\[ G(K) = \sum _{L \subseteq K} F(L), \quad (K \subseteq X_n). \]

Then

\[ F(K) = \sum _{L \subseteq K} (-1)^{|K| - |L|} G(L), \quad (K \subseteq X_n). \]

LaTeX

Corollary 11.3

Let \(n\) be a prime number. Then each nonzero integer in \(Z_n\) has a multiplicative inverse.

LaTeX

Corollary 11.5

In a BIBD, we have

\[ bk=vr. \]

LaTeX

Corollary 11.6

In a BIBD, we have

\[ \lambda {\lt} r. \]

LaTeX

Corollary 11.19

Let \(n \geq 2\) be an integer that is not twice an odd number. Then there exists a pair of orthogonal Latin squares of order \(n\).

LaTeX

Corollary 12.12

A graph of order \(n \geq 3\), in which each vertex has degree at least \(n/2\), has a Hamilton cycle.

LaTeX

Corollary 13.2

Let \(G\) be a graph and let \(H\) be a subgraph of \(G\). Then \(\chi (G) \geq \chi (H)\). If \(G\) has a subgraph equal to a complete graph \(K_p\) of order \(p\), then

\[ \chi (G) \geq p \]

LaTeX

Corollary 13.3

Let \(G=(V, E)\) be a graph of order \(n\) and let \(q\) be the largest order of an induced subgraph of \(G\) equal to a null graph \(N_q\). Then

\[ \chi (G) \geq \left\lceil \frac{n}{q}\right\rceil . \]

LaTeX

Corollary 13.25

Every interval graph is a perfect graph.

LaTeX

Corollary 13.36

Let \(G\) be a graph with at least three vertices. Then \(G\) is \(2\)-connected if and only if, for each pair \(a, b\) of distinct vertices, there are two paths joining \(a\) and \(b\) whose only common vertices are \(a\) and \(b\).

LaTeX

Corollary 14.8

Let \(X\) be a set of \(n\) elements and let \(f: X \rightarrow X\) be a one-to-one function. Let \(D_f=\left(X, A_f\right)\) be the digraph whose set of arcs is

\[ A_f=\{ (x, f(x)): x \text{ in } X\} \]

Then the arcs of \(D_f\) can be partitioned into directed cycles with each vertex belonging to exactly one directed cycle.

LaTeX

Corollary 15.2

Let \(\mathbf{c}\) be a coloring in \(\mathcal{C}\). The number

\[ \mid \{ f * \mathbf{c}: f \text{ in } G\} \mid \]

of different colorings that are equivalent to \(\mathbf{c}\) equals the number

\[ \frac{|G|}{|G(\mathbf{c})|} \]

obtained by dividing the number of permutations in \(G\) by the number of permutations in the stabilizer of \(\mathbf{c}\).

LaTeX

Corollary 3.8

For \(0 \leq r \leq n\),

\[ \binom {n}{r} = \binom {n}{n-r}. \]

LaTeX

Corollary 4.3

Let \(n\) and \(r\) be positive integers. If \(n(r-1) + 1\) objects are distributed into \(n\) boxes, then at least one of the boxes contains \(r\) or more of the objects.

LaTeX

Corollary 6.4

For \( n \) a positive integer, the largest of the binomial coefficients

\[ \binom {n}{0}, \binom {n}{1}, \binom {n}{2}, \ldots , \binom {n}{n} \]

\[ \binom {n}{\lfloor n/2 \rfloor } = \binom {n}{\lceil n/2 \rceil }. \]

LaTeX

Corollary 7.2

The number of objects of \(S\) which have at least one of the properties \(P_1, P_2, \ldots , P_m\) is given by

\begin{align*} |A_1 \cup A_2 \cup \cdots \cup A_m| = & \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \\ & \cdots + (-1)^{m+1} |A_1 \cap A_2 \cap \cdots \cap A_m|, \tag {6.3} \end{align*}

where the summations are as specified in Theorem 6.1.1.

LaTeX

Corollary 9.23

The large and small Schroder numbers are related by

\[ R_n = 2s_{n+1}, \qquad (n \geq 1). \]

LaTeX

Corollary 10.7

In the women-optimal stable complete marriage, each man is paired with the woman he ranks lowest among all the partners that are possible for him in a stable complete marriage.

LaTeX

Lemma 14.7

Let \(D\) be a digraph in which each vertex has outdegree at least \(l\). Then there is a directed cycle in \(D\).

LaTeX

Lemma 14.10

Let \(f\) be a flow in the network \(N=(V, A, s, t, c)\) and let \(U\) be a set of vertices containing the source \(s\) but not the target \(t\). Then

\[ \sum \limits _{\alpha \in \vec{U}} f(\alpha )-\sum \limits _{\alpha \in \overleftarrow {U}} f(\alpha )=\sum \limits _{\iota (\alpha )=s} f(\alpha )-\sum \limits _{\tau (\alpha )=s} f(\alpha ) \]

LaTeX

Lemma 14.11

Let \(N=(V, A, s, t, c)\) be a network with \(C\) a minimal cut. Let U be the set of all vertices \(x\) for which there exists a path from the source \(s\) to \(x\) thal contains no arc in \(C\). Then \(\vec{U}\) is a cut and \(C=\vec{U}\).

LaTeX

Theorem 11.1

The preceding algorithm terminates and computes the GCD of \(a\) and \(b\) correctly.

LaTeX

Theorem 11.2

Let \(n\) be an integer with \(n \geq 2\) and let \(a\) be a nonzero integer in \(Z_n = \{ O,1 ,\ldots , n - 1\} \). Then \(a\) has a multiplicative inverse in \(Z_n\) if and only if the GCD of \(a\) and \(n\) is \(1\). If \(a\) has a multiplicative inverse, then it is unique.

LaTeX

Theorem 11.4

In a BIBD, each variety is contained in

\[ r = \frac{\lambda (v-1)}{k-1} \]

blocks.

LaTeX

Theorem 11.7

In a BIBD, \(b \geq v.\)

LaTeX

Theorem 11.8

Let \(B\) be a subset of \(k {\lt} v\) elements of \(Z_v\) that forms a difference set mod \(v\). Then the blocks developed from \(B\) as a starter block form an SBIBD with index

\[ \lambda = \frac{k(k-1)}{v-1} \]

LaTeX

Theorem 11.9

Let \(\mathcal{B}\) be a Steiner triple system with pammeters \(b, v, k = 3, r, \lambda \). Then

\begin{equation} \label{10.4} r = \frac{\lambda (v-1)}{2} \end{equation}

and

\begin{equation} \label{10.5} b = \frac{\lambda v(v-1)}{6} \end{equation}

If the index is \(\lambda = 1\), then there is a nonnegative integer \(n\) such that \(v = 6n +1\) or \(v = 6n +3\).

LaTeX

Theorem 11.10

If there are Steiner triple systems of index \(\lambda = 1\) with \(v\) and \(w\) varieties, respectively, then there is a Steiner triple system of index \(\lambda = 1\) with \(vw\) varieties.

LaTeX

Theorem 11.11

Let \(n\) be a positive integer. Let \(A\) be the \(n\)-by-\(n\) array whose entry \(a_{ij}\) in row \(i\) and column \(j\) is

\[ a_{i j}=i+j(\text{addition mod} \hspace{0.5em} n),(i, j=0,1, \ldots , n-1) \]

Then \(A\) is a Latin square of order \(n\) based on \(Z_n\).

LaTeX

Theorem 11.20

Let \(n \geq 2\) be an integer. If there exist \(n-1\) MOLS of order \(n\), then there exists a resolvable BIBD with parameters

\begin{equation} \label{10.18} b=n^2+n, v=n^2, k=n^{\prime }, r=n+1, \lambda =1 \end{equation}

Conversely, if there exists a resolvable BIBD with parameters (10.18), then there exist \(n-1\) MOLS of order \(n\).

LaTeX

Theorem 11.21

Let \(L\) be an \(m\)-by-\(n\) Latin rectangle based on \(Z_n\) with \(m {\lt} n\). Then \(L\) has a completion.

LaTeX

Theorem 11.22

Let \(L\) be a semi-Latin square of order \(n\) and index \(m\), where \(m {\lt} n\). Then \(L\) has a completion.

LaTeX

Theorem 11.12

Let \(n\) be a positive integer and let \(r\) be a nonzero integer in \(Z_n\) such that the GCD of rand \(n\) is \(1\). Let \(A\) be the \(n\)-by-\(n\) array whose entry \(a_{ij}\) in row \(i\) and column \(j\) is

\[ a_{i j}=r \times i+j(\text{addition mod} \hspace{0.5em} n),(i, j=0,1, \ldots , n-1) \]

Then \(A\) is a Latin square of order \(n\) based on \(Z_n\).

LaTeX

Theorem 11.13

Let \(n\) be a prime number. Then \(L_n^1, L_n^2, \ldots , L_n^{n-1}\) are \(n - 1\) MOLS of order \(n\).

LaTeX

Theorem 11.14

Let \(n = p^k\) be an integer that is a power of a prime number \(p\). Then there exist \(n - 1\) MOLS of order \(n\). In fact, the \(n - 1\) Latin squares (10.12) of order \(n\) constructed from a finite field with \(n = p^k\) elements are \(n - 1\) MOLS of order \(n\).

LaTeX

Theorem 11.15

Let \(n \geq 2\) be an integer, and let \(A_1, A_2,\ldots , A_k\) be \(k\) MOLS of order \(n\). Then \(k \leq n - 1\); that is, the largest number of MOLS of order \(n\) is at most \(n - 1\).

LaTeX

Theorem 11.16

\(N(n) \geq 2\) for each odd integer \(n\).

LaTeX

Theorem 11.17

If there is a pair of MOLS of order \(m\) and there is a pair of MOLS of order \(k\), then there is a pair of MOLS of order \(mk\). More generally,

\[ N(mk) \geq \min \{ N(m), N(k)\} \]

LaTeX

Theorem 11.18

Let \(n \geq 2\) be an integer and let

\[ n=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k} \]

be the factorization of \(n\) into distinct prime numbers \(p_1, p_2, \ldots , p_k\). Then

\[ N(n) \geq \min \left\{ p_i^{e_2}-1: i=1,2, \ldots , k\right\} \]

LaTeX

Theorem 12.1

Let \(G\) be a general graph. The sum

\[ d_1 + d_2 + \cdots + d_n \]

of the degrees of all the vertices of \(G\) is an even number, and, consequently, the number of vertices of \(G\) with odd degree is even.

LaTeX

Theorem 12.2

Two isomorphic general graphs have the same degree sequence, but two graphs with the same degree sequence need not be isomorphic.

LaTeX

Theorem 12.3

Let \(G=(V, E)\) be a general graph. Then the vertex set \(V\) can be uniquely partitioned into nonempty parts \(V_1, V_2, \ldots , V_k\) so that the following conditions are satisfied: (1) The general subgraphs \(G_1=\left(V_1, E_1\right), G_2=\left(V_2, E_2\right), \ldots , G_k= \left(V_k, E_k\right)\) induced by \(V_1, V_2, \ldots , V_k\), respectively, are connected.
(2) For each \(i \neq j\) and each pair of vertices \(x\) in \(V_i\) and \(y\) in \(V_j\), there is no walk that joins \(x\) and \(y\).

LaTeX

Theorem 12.4

Let \(G\) and \(G^{\prime }\) be two general graphs. Then the following are necessary conditions for \(G\) and \(G^{\prime }\) to be isomorphic: (1) If \(G\) is a graph, so is \(G^{\prime }\).
(2) If \(G\) is connected, so is \(G^{\prime }\). More generally, \(G\) and \(G^{\prime }\) have the same number of connected components.
(3) If \(G\) has a cycle of length equal to some integer \(k\), then so does \(G^{\prime }\).
(4) If \(G\) has an (induced) general subgraph that is a complete graph \(K_m\) of order \(m\), so does \(G^{\prime }\).

LaTeX

Theorem 12.5

Let \(G = (V, E)\) be a general graph and assume that the degree of each vertex is even. Then each edge of \(G\) belongs to a closed trail and hence to a cycle.

LaTeX

Theorem 12.6

Let \(G\) be a connected general gmph. Then \(G\) has a closed Eulerian trail if and only if the degree of each vertex is even.

LaTeX

Theorem 12.7

Let \(G\) be a connected general graph. Then \(G\) has an open Eulerian trail if and only if there are exactly two vertices \(u\) and \(v\) of odd degree. Every open Eulerian trail in \(G\) joins \(u\) and \(v\).

LaTeX

Theorem 12.8

Let \(G\) be a connected general graph and suppose that the number of vertices of \(G\) with odd degree is \(m {\gt} O\). Then the edges of \(G\) can be partitioned into \(m/2\) open trails. It is impossible to partition the edges of \(G\) into fewer than \(m/2\) open trails.

LaTeX

Theorem 12.9

Let \(G\) be a connected general graph having \(K\) edges. Then there is a closed walk in \(G\) of length \(2K\) in which the number of times an edge is used equals twice its multiplicity.

LaTeX

Theorem 12.10

A connected graph of order \(n \geq 3\) with a bridge does not have a Hamilton cycle.

LaTeX

Theorem 12.11

Let \(G\) be a graph of order \(n \geq 3\) that satisfies the Ore property. Then \(G\) has a Hamilton cycle.

LaTeX

Theorem 12.13

A graph of order \(n\), in which the sum of the degrees of each pair of nonadjacent vertices is at least \(n - 1\), has a Hamilton path.

LaTeX

Theorem 12.14

A multigraph is bipartite if and only if each of its cycles has even length.

LaTeX

Theorem 12.15

Let \(G\) be a bipartite graph with bipartition \(X, Y\). If \(|X| \neq |Y|\), then \(G\) does not have a Hamilton cycle. If \(|X|=|Y|\), then \(G\) does not have a Hamilton path that begins at a vertex in \(X\) and ends at a vertex in \(X\). If \(X\) and \(Y\) differ by at least 2 , then \(G\) does not have a Hamilton path. If \(|X|=|Y|+1\), then \(G\) does not have a Hamilton path that begins at \(X\) and ends at \(Y\), or vice versa.

LaTeX

Theorem 12.16

A connected graph of order \(n\) has at least \(n - 1\) edges. Moreover, for each positive integer \(n\), there exist connected graphs with exactly \(n - 1\) edges. Removing any edge from a connected graph of order \(n\) with exactly \(n-1\) edges leaves a disconnected graph, and hence each edge is a bridge.

LaTeX

Theorem 12.17

A connected graph of order \(n \geq 1\) is a tree if and only if it has exactly \(n - 1\) edges.

LaTeX

Theorem 12.18

Let \(G\) be a connected graph and let \(\alpha = \{ x,y\} \) be an edge of \(G\). Then \(\alpha \) is a bridge if and only if there does not exist a cycle of \(G\) containing \(\alpha \).

LaTeX

Theorem 12.19

Let \(G\) be a connected graph of order \(n\). Then \(G\) is a tree if and only if \(G\) does not have any cycles.

LaTeX

Theorem 12.20

A graph \(G\) is a tree if and only if every pair of distinct vertices \(x\) and \(y\) is joined by a unique path. This path is necessarily a shortest path joining \(x\) and \(y\); that is, a path of length \(d(x, y)\).

LaTeX

Theorem 12.21

Let \(G\) be a tree of order \(n \geq 2\). Then \(G\) has at least two pendent vertices.

LaTeX

Theorem 12.22

Every connected graph has a spanning tree.

LaTeX

Theorem 12.23

Let \(T\) be a spanning tree of a connected graph \(G\). Let \(\alpha = \{ a,b\} \) be an edge of \(G\) that is not an edge of \(T\). Then there is an edge \(\beta \) of \(T\) such that the graph \(T^{\prime }\) obtained from \(T\) by inserting \(\alpha \) and deleting \(\beta \) is also a spanning tree of \(G\).

LaTeX

Theorem 12.24

Let \(T_1\) and \(T_2\) be spanning trees of a connected graph \(G\). Let \(\beta \) be an edge of \(T_1\). Then there is an edge \(\alpha \) of \(T_2\) such that the graph obtained from \(T_1\) by inserting \(\alpha \) and deleting \(\beta \) is a spanning tree of \(G\).

LaTeX

Theorem 12.25

A neutral game is converted into a positive game if a new edge joining the distinguished vertices \(u\) and \(v\) is added to the multigraph of the game.

LaTeX

Theorem 12.26

The game determined by a multigraph \(G = (V, E)\) with distinguished vertices \(u\) and \(v\) is a positive game if and only if there is a subset \(U\) containing \(u\) and \(v\) of the vertex set \(V\) such that the induced multisubgraph \(G_U\) has two spanning trees, \(T_1\) and \(T_2\), with no common edges.

LaTeX

Theorem 12.27

Let \(G = (V, E)\) be a graph. Then \(G\) is connected if and only if the graph \(T = (U, F)\) constructed by carrying out the preceding algorithm is a spanning tree of \(G\).

LaTeX

Theorem 12.28

Let \(G = (V, E)\) be a graph and let \(u\) be any vertex of \(G\). Then \(G\) is connected if and only if the graph \(T = (U, F)\) constructed by carrying out the BF-algorithm is a spanning tree of \(G\). If \(G\) is connected, then, for each vertex \(y\) of \(G\), the distance in \(G\) between \(u\) and \(y\) equals \(D(y)\); and this is the same as the distance between \(u\) and \(y\) in \(T\).

LaTeX

Theorem 12.29

Let \(G = (V, E)\) be a graph and let \(u\) be any vertex of \(G\). Then \(G\) is connected if and only if the graph \(T = (U, F)\), constructed by carrying out the preceding DF-algorithm, is a spanning tree of \(G\).

LaTeX

Theorem 12.30

Let \(G = (V, E)\) be a weighted graph and let \(u\) be any vertex of \(G\). Then \(G\) is connected if and only if the graph \(T = (U, F)\) obtained by carrying out the preceding algorithm is a spanning tree of \(G\). If G is connected, then for each vertex \(y\) of \(G\), the weighted distance between \(u\) and \(y\) equals \(D(y)\), and this is the same as thf weighted distance between \(u\) and \(y\) in the weighted tree \(T\).

LaTeX

Theorem 12.31

Let \(G = (V, E)\) be a weighted connected graph with weight function \(c\). Then the preceding greedy algorithm constructs a minimum weight spanning tree \(T = (V, F)\) of \(G\).

LaTeX

Theorem 12.32

Let \(G = (V, E)\) be a weighted graph with weight function \(c\). Then Prim’s algorithm constructs a minimum weight spanning tree \(T = (V, F)\) of \(G\).

LaTeX

Theorem 13.1

Let \(G\) be a graph of order \(n \geq 1\). Then

\[ 1 \leq \chi (G) \leq n \]

Moreover, \(\chi (G)=n\) if and only if \(G\) is a complete graph, and \(\chi (G)=1\) if and only if \(G\) is a null graph.

LaTeX

Theorem 13.10

Let \(U\) be an articulation set of \(G\) and suppose that the induced subgraph \(G_U\) is a complete graph \(K_r\). Let the connected components of \(G_{V-U}\) be the induced subgraphs \(G_{U_1}, \ldots , G_{U_t}\). For \(i=1, \ldots , t\), let \(H_i=G_{U \cup U_i}\) be the subgraph of \(G\) induced by \(U \cup U_i\). Then

\[ p_G(k)=\frac{p_{H_1}(k) \times \cdots \times p_{H_t}(k)}{\left([k]_r\right)^{t-1}} \]

In particular, the chromatic number of \(G\) is the largest of the chromatic numbers of \(H_1, \ldots , H_t\).

LaTeX

Theorem 13.4

Let \(G\) be a graph with at least one edge. Then \(\chi (G) = 2\) if and only if \(G\) is bipartite.

LaTeX

Theorem 13.5

Let \(G\) be a graph for which the maximum degree of a vertex is \(\Delta \). Then the greedy algorithm produces a \((\Delta +1)\)-coloring of the vertices of \(G\), and hence

\[ \chi (G) \leq \Delta +1 \]

LaTeX

Theorem 13.6

Let \(G\) be a connected graph for which the maximum degree of a vertex is \(\Delta \). If \(G\) is neither a complete graph \(K_n\) nor an odd cycle graph \(C_n\), then \(\chi (G) \leq \Delta \).

LaTeX

Theorem 13.7

Let \(T\) be a tree of order \(n\). Then

\[ p_T(k) = k(k-1)^{n-1}. \]

LaTeX

Theorem 13.8

Let \(G\) be a graph of order \(n \geq 1\). Then the number of \(k\)-colorings of \(G\) is a polynomial in \(k\) of degree equal to \(n\) (with leading coefficient equal to \(1\)) and this polynomial-the chromatic polynomial of \(G\)-is computed correctly by the preceding algorithm.

LaTeX

Theorem 13.9

Let \(G\) be a graph and assume that \(G\) contains a subgraph \(H\) equal to a complete graph \(K_r\). Then the chromatic polynomial of \(G\) is divisible by the chromatic polynomial \([k]_r\) of \(K_r\).

LaTeX

Theorem 13.11

Let \(G\) be a plane-graph of order \(n\) with \(e\) edge-curves and assume that \(G\) is connected. Then the number \(r\) of regions into which \(G\) divides the planr satisfies

\begin{equation} \label{12.4} r=e-n+2 \end{equation}

LaTeX

Theorem 13.12

Let \(G\) be a connected planar graph. Then there is a vertex of \(G\) whose degree is at most \(5\).

LaTeX

Theorem 13.13

A graph \(G\) is planar if and only if it does not have a subgraph that is a subdivision of a \(K_5\) or of a \(K_{3,3}\).

LaTeX

Theorem 13.14

A graph \(G\) is planar if and only if it does not contain a subgraph that contracts to a \(K_5\) or a \(K_{3,3}\).

LaTeX

Theorem 13.15

Let there be given a \(k\)-coloring of the vertices of a graph \(H=(U, F)\). Let two of the colors be red and blue, and let \(W\) be the subset of vertices in \(U\) that are assigned either the color red or the color blue. Let \(H_{r, b}\) be the subgraph of \(H\) induced by the vertices in \(W\) and let \(C_{r, b}\) be a connected component of \(H_{r, b}\). Interchanging the colors red and blue assigned to the vertices of \(C_{r, b}\), we obtain another \(k\)-coloring of \(H\).

LaTeX

Theorem 13.16

The chromatic number of a planar graph is at most \(5\).

LaTeX

Theorem 13.17

Hadwiger’s conjecture holds for \(p = 5\) if and only if every planar graph has a \(4\)-coloring.

LaTeX

Theorem 13.18

Let \(p \leq 3\). If \(G\) is a connected graph with chromatic number \(\chi (G) \geq p\), then \(G\) can be contracted to a \(K_p\).

LaTeX

Theorem 13.19

Let \(G\) be a connected graph of order \(n \geq 2\). Then

\[ \text{dom}(G) \leq \left\lfloor \frac{n}{2} \right\rfloor . \]

LaTeX

Theorem 13.20

A graph \(G\) is \(\chi \)-perfect if and only if it is \(\theta \)-perfect. Equivalently, \(G\) is \(\chi \)-perfect if and only if \(\bar{G}\) is \(\chi \)-perfect.

LaTeX

Theorem 13.21

Every interval graph is a chordal graph.

LaTeX

Theorem 13.22

Let \(G=(V, E)\) be a connected graph and let \(U\) be an articulation set of \(G\) such that the subgraph \(G_U\) induced by \(U\) is a complete graph. Let the connected components of the induced subgraph \(G_{V-U}\) be \(G_1=\left(U_1, E_1\right), \ldots , G_t=\left(U_t, E_t\right)\). Assume that the induced graphs \(G_{U_2 \cup U}\) satisfy

\[ \chi \left(G_{U_2 \cup U}\right)=\omega \left(G_{U_2 \cup U}\right) \quad (i=1,2, \ldots , t) \]

Then

\[ \chi (G)=\omega (G) \]

LaTeX

Theorem 13.23

Let \(G = (V, E)\) be a connected chordal graph and let \(U\) be a minimal articulation set of \(G\). Then the subgraph \(G_U\) induced by \(U\) is a complete graph.

LaTeX

Theorem 13.24

Every chordal graph is perfect.

LaTeX

Theorem 13.26

Let \(G=(V, E)\) be a bipartite graph with bipartition \(X, Y\) with as sociated family \(\mathcal{A}_G\) of subsets of \(Y\). Let \(t\) be a positive integer. Then from a subfamily

\begin{equation} \label{12.10} \left(A_{i_1}, A_{i_2}, \ldots , A_{i_t}\right) \text{ of } t \text{ sets of } \mathcal{A}_G \text{ with an } S D R\left(e_{i_1}, e_{i_2}, \ldots , e_{i_t}\right) \end{equation}

we obtain a matching

\begin{equation} \label{12.11} \left\{ x_{i_1}, e_{i_1}\right\} ,\left\{ x_{i_2}, e_{i_2}\right\} , \ldots ,\left\{ x_{i_t}, e_{i_t}\right\} \text{ of } G \text{ of } t \text{ edges. } \end{equation}

Conversely, from a matching (12.11) of \(G\) of \(t\) edges, we get a subfamily (12.10) of \(\mathcal{A}_G\) of \(t\) sets with \(\left(e_{i_1}, e_{i_2}, \ldots , e_{i_t}\right)\) as \(S D R\). Thus the largest number of sets in a subfamily of \(\mathcal{A}_G\) with an \(S D R\) equals thr matching number \(\rho (G)\) of \(G\).

LaTeX

Theorem 13.27

Let \(G = (V, E)\) be a graph. Then a subset \(W\) of the set \(V\) of vertices is a cover if and only if the complementary set of vertices \(V \setminus W\) is an independent set.

LaTeX

Theorem 13.28

Let \(G=(V, E)\) be a bipartite graph. Then

\begin{equation} \label{12.13} \rho (G)=c(G) \end{equation}

that is, the largest number of edges in a matching equals the smallest number of vertices in a cover.

LaTeX

Theorem 13.29

Let \(G=(V, E)\) be a graph. Then \(G\) has a perfect matching if and only if

\begin{equation} \label{12.15} \text{ oc }\left(G_{V \backslash U}\right) \leq |U| \text{ for every } U \subseteq V \end{equation}

that is, removing a set of vertices does not create more odd components than the number of vertices removed.

LaTeX

Theorem 13.30

Let \(G(V, E)\) be a graph with \(n\) vertices. Then

\[ \rho (G)=\min \left\{ n-\left(o c\left(G_{V \backslash U}\right)-|U|\right)\right\} \]

where the minimum is taken over all \(U \subseteq V\).

LaTeX

Theorem 13.31

Let \(G\) be a graph of order \(n\). Then

\[ 0 \leq \kappa (G) \leq n-1 \]

with equality on the left if and only if \(G\) is disconnected and with equality on the right if and only if \(G\) is a complete graph.

LaTeX

Theorem 13.32

For each graph \(G\), we have

\[ \kappa (G) \leq \lambda (G) \leq \delta (G) \]

LaTeX

Theorem 13.33

Let \(G\) be a graph of order \(n \geq 3\). Then the following three assertions are equivalent: (1) \(G\) is 2-connected. (2) \(G\) is connected and does not have an articulation vertex. (3) For each triple of vertices \(a, b, c\), there is a path joining a and b that does not contain \(c\).

LaTeX

Theorem 13.34

Let \(G=(V, E)\) be a connected graph of order \(n \geq 2\), and let

\[ G_{U_1}=\left(U_1, E_1\right), G_{U_2}=\left(U_2, E_2\right), \ldots , G_{U_r}=\left(U_r, E_r\right) \]

be the blocks of \(G\). Then \(E_1, E_2, \ldots , E_r\) is a partition of the set \(E\) of edges of \(G\), and each pair of blocks has at most one vertex in common.

LaTeX

Theorem 13.35

Let \(G = (V, E)\) be a graph of order \(n \geq 3\). Then \(G\) is \(2\)-connected if and only if, for each pair \(a, b\) of distinct vertices, there is a cycle containing both \(a\) and \(b\).

LaTeX

Theorem 13.37

Let \(k\) be a positive integer and let \(G\) be a graph of order \(n \geq k +1\). Then \(G\) is \(k\)-connected if and only if, for each pair \(a, b\) of distinct vertices, there are \(k\) paths joining \(a\) and \(b\) such that each pair of paths has only the vertices \(a\) and \(b\) in common.

LaTeX

Theorem 14.1

In a general digraph the sum of the indegrees of the vertices equals the sum of the outdegrees, and each is equal to the number of arcs.

LaTeX

Theorem 14.2

Let \(D\) be a connected digraph. Then \(D\) has a closed Eulerian directed trail if and only if the indegree of each vertex equals the outdegree.

LaTeX

Theorem 14.3

Let \(D\) be a connected digraph and let \(x\) and \(y\) be distinct vertices of \(D\). Then there is a directed Eulerian trail from \(x\) to \(y\) if and only if (i) the outdegree of \(x\) exceeds its indegree by 1 ; (ii) the indegree of \(y\) exceeds its outdegree by 1 ; (iii) for each vertex \(z \neq x, y\), the indegree of \(z\) equals its outdegree.

LaTeX

Theorem 14.4

Let \(D\) be a strongly connected digraph without any loops. If, for each vertex \(x\), we have

\[ (\text{ outdegree of } x)+(\text{ indegree of } x) \geq n, \]

then \(D\) has a directed Hamilton cycle.

LaTeX

Theorem 14.5

Every tournament has a Hamilton path.

LaTeX

Theorem 14.6

Let \(G = (V, E)\) be a connected graph. Then \(G\) has a strongly connected orientation if and only if \(G\) does not have any bridges.

LaTeX

Theorem 14.9

Every trading problem has a core allocation.

LaTeX

Theorem 14.12

Let \(N=(V, A, s, t, c)\) be a network. Then the maximum value of a flow in \(N\) equals the minimum capacity of a cut in \(N\). In other words, the value of a maximum flow equals the capacity of a minimum cut. If the capacities of all the arcs are integers, then there is a maximum flow all of whose values are integers as well.

LaTeX

Theorem 14.13

Let \(s\) and \(t\) be distinct vertices of a digraph \(D = (V, A)\). Then the maximum number of pairwise arc-disjoint paths from \(s\) to \(t\) equals the minimum number of arcs in an st-separating set.

LaTeX

Theorem 14.14

Let \(G\) be a bipartite graph. Then \(\rho (G) =c(G)\).

LaTeX

Theorem 14.15

Let \(M\) be a matching in the bipartite graph \(G\). Then \(M\) is a max-matching if and only if there does not exist an \(M\)-alternating path.

LaTeX

Theorem 14.16

Assume that nonbreakthrough has occured in the matching algorithm. Let \(X^{u n}\) consist of all the unlabeled vertices of \(X\), let \(Y^{\text{lab }}\) consist of all the labeled vertices of \(Y\), and let \(S=X^{u n} \cup Y^{l a b}\). Then both of the following hold: (i) \(S\) is a min-cover of the bipartite graph \(G\); (ii) \(|M|=|S|\) and \(M\) is a max-matching.

LaTeX

Theorem 15.1

For each coloring \(\mathbf{c}\), the stabilizer \(G(\mathbf{c})\) of \(\mathbf{c}\) is a permutation group. Moreover, for any permutations \(f\) and \(g\) in \(G, g * \mathbf{c}=f * \mathbf{c}\) if and only if \(f^{-1} \circ g\) is in \(G(\mathbf{c})\).

LaTeX

Theorem 15.3

Let \(G\) be a group of permutations of \(X\) and let \(\mathcal{C}\) be a set of colorings of \(X\) such that \(f * \mathbf{c}\) is in \(\mathcal{C}\) for all \(f\) in \(G\) and all \(\mathbf{c}\) in \(\mathcal{C}\). Then the number \(N(G, \mathcal{C})\) of nonequivalent colorings in \(\mathcal{C}\) is given by

\begin{equation} \label{14.7} N(G, \mathcal{C})=\frac{1}{|G|} \sum _{f \in G}|\mathcal{C}(f)| \end{equation}

In words, the number of nonequivalent colorings in \(\mathcal{C}\) equals the average of the number of colorings fixed by the permutations in \(G\).

LaTeX

Theorem 15.4

Let \(f\) be a permutation of a set \(X\). Suppose we have \(k\) colors available with which to color the elements of \(X\). Let \(\mathcal{C}\) be the set of all colorings of \(X\). Then the number of colorings that are fixed by \(f\) satisfies

\[ |\mathcal{C}(f)|=k^{\# (f)} \]

LaTeX

Theorem 15.5

Let \(X\) be a set of \(n\) elements, and suppose we have a set of \(k\) colors available with which to color the elements of \(X\). Let \(\mathcal{C}\) be the set of all \(k^n\) colorings of \(X\). Let \(G\) be a group of permutations of \(X\). Then the number of nonequivalent colorings is the number

\[ N(G, \mathcal{C})=P_G(k, k, \ldots , k) \]

obtained by substituting \(z_i=k,(i=1,2, \ldots , n)\) into the cycle index of \(G\).

LaTeX

Theorem 15.6

Let \(X\) be a set of elements and let \(G\) be a group of permutations of \(X\). Let \(\left\{ u_1, u_2, \ldots , u_k\right\} \) be a set of \(k\) colors, and let \(\mathcal{C}\) be a set of all colorings of \(X\). Then the generating function for the number of nonequivalent colorings of \(\mathcal{C}\) according to the number of colors of each kind is the expression

\begin{equation} \label{14.20} P_G\left(u_1+\cdots +u_k, u_1^2+\cdots +u_k^2, \ldots , u_1^n+\cdots +u_k^n\right) \end{equation}

obtained from the cycle index \(P_G\left(z_1, z_2, \ldots , z_n\right)\) by making the substitutions

\[ z_j=u_1^j+\cdots +u_k^j \quad (j=1,2, \ldots , n) \]

In other words, the coefficient of

\[ u_1^{p_1} u_2^{p_2} \cdots u_k^{p_k} \]

in (14.20) equals the number of nonequivalent colorings in \(\mathcal{C}\) with \(p_1\) elements of \(X\) colored \(u_1, p_2\) elements colored \(u_2, \ldots , p_k\) elements colored \(u_k\).

LaTeX

Theorem 3.1

Suppose that a set \(S\) is partitioned into pairwise disjoint parts \(S_1,S_2, \ldots , S_m\). The number of objects in \(S\) can be determined by finding the number of objects in each of the parts, and adding the numbers so obtained:

\[ |S| = |S_1| + |S_2| + \cdots + |S_m| \]

LaTeX

Theorem 3.2

Let \(S\) be a set of ordered pairs \((a, b)\) of objects, where the first object \(a\) comes from a set of size \(p\), and for each choice of object a there are \(q\) choices for object \(b\). Then the size of \(S\) is \(p \times q\).

LaTeX

Theorem 3.3

Let \(A\) be a set and let \(U\) be a larger set containing \(A\). Let \(\overline{A} = U \setminus A = \{ x \in U : x \notin A \} \) be the complement of \(A\) in \(U\). Then the number \(|A|\) of objects in \(A\) is given by the rule: \(|A| = |U| - |\overline{A}|\).

LaTeX

Theorem 3.4

Let \(S\) be a finite set that is partitioned into \(k\) parts in such a way that each part contains the same number of objects. Then the number of parts in the partition is given by the rule: \(k = \frac{|S|}{\text{number of objects in a part}}\).

LaTeX

Theorem 3.5

For \(n\) and \(r\) positive integers with \(r\leq n\),

\[ P(n,r) = n\times (n-1)\times \cdots \times (n-r+1). \]

LaTeX

Theorem 3.6

The number of circular r-permutations of a set of \(n\) elements is given by

\[ \frac{P(n,r)}{r}=\frac{n!}{r\cdot (n-r)!}. \]

In particular, the number of circular permutations of \(n\) elements is \((n - 1)!\).

LaTeX

Theorem 3.7

For \(0\leq r \leq n\),

\[ P(n,r)=r!\binom {n}{r} \]

Hence,

\[ \binom {n}{r} = \frac{n!}{r! (n-r)!}. \]

LaTeX

Theorem 3.9

(Pascal’s formula) For all integers \(n\) and \(k\) with \(1 \leq k \leq n-1\),

\[ \binom {n}{k} = \binom {n-1}{k} + \binom {n-1}{k-1}. \]

LaTeX

Theorem 3.10

For \(n \geq 0\),

\[ \binom {n}{0} + \binom {n}{1} + \binom {n}{2} + \cdots + \binom {n}{n} = 2 ^{n}, \]

and the common value equals the number of subsets of an n-element set.

LaTeX

Theorem 3.11

Let \(S\) be a multiset with objects of \(k\) different types, where each object has an infinite repetition number. Then the number of r-permutations of \(S\) is \(k^{r}\).

LaTeX

Theorem 3.12

Let \(S\) be a multiset with objects of \(k\) different types with finite repetition numbers \(n_1, n_2, ... , n_k\), respectively. Let the size of \(S\) be \(n = n_1 + n_2 + ... + n_k\). Then the number of permutations of \(S\) equals

\[ \frac{n!}{n_1!n_2!\dots n_k!}. \]

LaTeX

Theorem 3.13

Let \(n\) be a positive integer and let \(n_1, n_2, ... ,n_k\) be positive integers with \(n = n_1 + n_2 + ... + n_k\). The number of ways to partition a set of \(n\) objects into \(k\) labeled boxes in which Box 1 contains \(n_1\) objects, Box 2 contains \(n_2\) objects, ..., Box k contains \(n_k\) objects equals

\[ \frac{n!}{n_1!n_2!\dots n_k!}. \]

If the boxes are not labeled, and \(n_1 = n_2 = ... = n_k\), then the number of partitions equals

\[ \frac{n!}{k!n_1!n_2!\dots n_k!}. \]

LaTeX

Theorem 3.14

There are \(n\) rooks of \(k\) colors with \(n_1\) rooks of the first color, \(n_2\) rooks of the second color, . . . , and \(n_k\) rooks of the kth color. The number of ways to arrange these rooks on an n-by-n board so that no rook can attack another

\[ n!\frac{n!}{n_1!n_2!\cdots n_k!}=\frac{(n!)^2}{n_1!n_2!\cdots n_k!}. \]

LaTeX

Theorem 3.15

Let \(S\) be a multiset with objects of \(k\) types, each with an infinite repetition number. Then the number of r-combinations of \(S\) equals

\[ \binom {r+k-1}{r}=\binom {r+k-1}{k-1} \]

LaTeX

Theorem 4.1

If \(n + 1\) objects are distributed into \(n\) boxes, then at least one box contains two or more of the objects.

LaTeX Lean

Theorem 4.2

Let \(q_1, q_2, . .. ,q_n\) be positive integers. If

\[ q_1 + q_2 + \cdots + q_n - n + 1 \]

objects are distributed into \(n\) boxes, then either the first box contains at least \(q_1\) objects, or the second box contains at least \(q_2\) objects, \(\dots \), or the \(n\)th box contains at least \(q_n\) objects.

LaTeX

Theorem 4.4

If \(m \geq 2\) and \(n \geq 2\) are integers, then there is a positive integer \(p\) such that

\[ K_p \rightarrow K_m, K_n. \]

LaTeX

Theorem 5.1

Let \(b_1, b_2, \dots , b_n\) be a sequence of integers satisfying

\[ 0 \leq b_1 \leq n-1, \quad 0 \leq b_2 \leq n-2,\quad \dots \quad 0 \leq b_{n-1} \leq 1, \quad b_n = 0. \]

Then there exists a unique permutation of \(\{ 1, 2, \dots , n\} \) whose inversion sequence is \(b_1, b_2, \dots , b_n\).

LaTeX

Theorem 5.2

The preceding algorithm for generating the \(n\)-tuples of 0s and 1s produces the reflected Gray code of order \(n\) for each positive integer \(n\).

LaTeX

Theorem 5.3

Let \(a_1, a_2 \cdots a_r\) be an \(r\)-subset of \(\{ 1, 2, \dots , n\} \). The first \(r\)-subset in the lexicographic ordering is \(1 2 \cdots r\). The last \(r\)-subset in the lexicographic ordering is \((n-r+1)(n-r+2) \cdots n\). Assume that \(a_1a_2 \cdots a_r \neq (n-r+1)(n-r+2) \cdots n\). Let \(k\) be the largest integer such that \(a_k {\lt} n\) and \(a_k + 1\) is different from each of \(a_{k+1}, \dots , a_r\). Then the \(r\)-subset that is the immediate successor of \(a_1a_2 \cdots a_r\) in the lexicographic ordering is

\[ a_1 \cdots a_{k-1}(a_k + 1)(a_k + 2) \cdots (a_k + r - k + 1). \]

LaTeX

Theorem 5.4

The \(r\)-subset \(a_1a_2 \cdots a_r\) of \(\{ 1, 2, \dots , n\} \) occurs in place number

\[ \binom {n}{r} - \binom {n - a_1}{r} - \binom {n - a_2}{r-1} - \cdots - \binom {n - a_{r-1}}{2} - \binom {n - a_r}{1} \]

in the lexicographic order of the \(r\)-subsets of \(\{ 1, 2, \dots , n\} \).

LaTeX

Theorem 5.5

Let \(X\) be a finite set with \(n\) elements. Then there is a one-to-one correspondence between the total orders on \(X\) and the permutations of \(X\). In particular, the number of different total orders on \(X\) is \(n!\).

LaTeX

Theorem 5.6

Let \((X, \leq )\) be a finite partially ordered set. Then there is a linear extension of \((X, \leq )\).

LaTeX

Theorem 5.7

Let \(\sim \) be an equivalence relation on a set \(X\). Then the distinct equivalence classes partition \(X\) into nonempty parts. Conversely, given any partition of \(X\) into nonempty parts, there is an equivalence relation on \(X\) whose equivalence classes are the parts of the partition.

LaTeX

Theorem 6.1

Let \( n \) be a positive integer. Then, for all \( x \) and \( y \),

\[ (x+y)^{n}=x^{n}+\binom {n}{1}x^{n-1}y+\binom {n}{2}x^{n-2}y^{2}+\cdots +\binom {n}{n-1}x^{1}y^{n-1}+y^{n}. \]

In summation notation,

\[ (x+y)^n=\sum _{k=0}^n\binom {n}{k} x^{n-k} y^k. \]

LaTeX

Theorem 6.2

Let \( n \) be a positive integer. Then, for all \( x \),

\[ (1+x)^n = \sum _{k=0}^n \binom {n}{k} x^k = \sum _{k=0}^n \binom {n}{n-k} x^k. \]

LaTeX

Theorem 6.3

Let \( n \) be a positive integer. The sequence of binomial coefficients

\[ \binom {n}{0}, \binom {n}{1}, \binom {n}{2}, \ldots , \binom {n}{n} \]

is a unimodal sequence. More precisely, if \( n \) is even,

\begin{align*} \binom {n}{0} & {\lt} \binom {n}{1} {\lt} \cdots {\lt} \binom {n}{n/2}, \\ \binom {n}{n/2} & {\gt} \cdots {\gt} \binom {n}{n-1} {\gt} \binom {n}{n}, \end{align*}

and if \( n \) is odd,

\begin{align*} \binom {n}{0} & {\lt} \binom {n}{1} {\lt} \cdots {\lt} \binom {n}{(n-1)/2} = \binom {n}{(n+1)/2}, \\ & \binom {n}{(n+1)/2} {\gt} \cdots {\gt} \binom {n}{n-1} {\gt} \binom {n}{n}. \end{align*}

LaTeX

Theorem 6.5

Let \( S \) be a set of \( n \) elements. Then an antichain on \( S \) contains at most \( \binom {n}{\lfloor \frac{n}{2} \rfloor } \) sets.

LaTeX

Theorem 6.6

Let \( n \) be a positive integer. For all \( x_1, x_2, \ldots , x_t \), \( (x_1 + x_2 + \cdots + x_t)^n = \sum \binom {n}{n_1n_2\ldots n_t} x_1^{n_1} x_2^{n_2} \cdots x_t^{n_t}, \) where the summation extends over all nonnegative integral solutions is \( n_1, n_2, \ldots , n_t \) of \( n_1 + n_2 + \cdots + n_t = n \).

LaTeX

Theorem 6.7

Let \( \alpha \) be a real number. Then, for all \( x \) and \( y \) with \( 0 \leq |x| {\lt} |y| \),

\[ (x + y)^\alpha = \sum _{k=0}^{\infty } \binom {\alpha }{k} x^k y^{\alpha -k}, \]

where

\[ \binom {\alpha }{k} = \frac{\alpha (\alpha - 1) \cdots (\alpha - k + 1)}{k!}. \]

LaTeX

Theorem 6.8

Let \((X, \leq )\) be a finite partially ordered set, and let \( r \) be the largest size of a chain. Then \( X \) can be partitioned into \( r \) but no fewer antichains.

LaTeX

Theorem 6.9

Let \((X, \leq )\) be a finite partially ordered set, and let \(m\) be the largest size of an antichain. Then \(X\) can be partitioned into \(m\) but no fewer chains.

LaTeX

Theorem 7.1

The number of objects of the set \(S\) that have none of the properties \(P_1, P_2, \ldots , P_m\) is given by the alternating expression

\begin{align*} |\overline{A}_1 \cap \overline{A}_2 \cap \cdots \cap \overline{A}_m| = & |S| - \sum |A_i| + \sum |A_i \cap A_j| - \sum |A_i \cap A_j \cap A_k| + \\ & \cdots + (-1)^m |A_1 \cap A_2 \cap \cdots \cap A_m|, \tag {6.2} \end{align*}

where the first sum is over all 1-subsets \(\{ i\} \) of \(\{ 1,2,\ldots ,m\} \), the second sum is over all 2-subsets \(\{ i,j\} \) of \(\{ 1,2,\ldots ,m\} \), the third sum is over all 3-subsets \(\{ i,j,k\} \) of \(\{ 1,2,\ldots ,m\} \), and so on until the \(m\)th sum over all \(m\)-subsets of \(\{ 1,2,\ldots ,m\} \) of which the only one is itself.

LaTeX

Theorem 7.3

For \(n \geq 1\),

\[ D_n = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n \frac{1}{n!} \right). \]

LaTeX

Theorem 7.4

The number of ways to place \(n\) nonattacking, indistinguishable rooks on an \(n\)-by-\(n\) board with forbidden positions equals

\[ n! - r_1 (n-1)! + r_2 (n-2)! - \cdots + (-1)^k r_k (n-k)! + \cdots + (-1)^n r_n. \]

LaTeX

Theorem 7.5

For \(n \geq 1\),

\begin{align*} Q_n = \quad & n! - \binom {n-1}{1}(n-1)! + \binom {n-1}{2}(n-2)! \\ & - \binom {n-1}{3}(n-3)! + \cdots + (-1)^{n-1} \binom {n-1}{n-1}1!. \end{align*}

LaTeX

Theorem 7.6

Let \((X, \leq )\) be a partially ordered set with a smallest element \(0\). Let \(\mu \) be its Möbius function, and let \(F : X \to \Re \) be a real-valued function defined on \(X\). Let the function \(G : X \to \Re \) be defined by

\[ G(x) = \sum _{\{ z : z \leq x\} } F(z), \quad (x \in X). \]

Then

\[ F(x) = \sum _{\{ y : y \leq x\} } G(y) \mu (y, x), \quad (x \in X). \]

LaTeX

Theorem 7.8

Let \((X, \leq _1)\) and \((Y, \leq _2)\) be two finite partially ordered sets with Möbius functions \(\mu _1\) and \(\mu _2\), respectively. Let \(\mu \) be the Möbius function of the direct product of \((X, \leq _1)\) and \((Y, \leq _2)\). Then

\[ \mu \big((x, y), (x', y')\big) = \mu (x, x') \mu (y, y'), \quad \big((x, y), (x', y') \in X \times Y\big). \tag {6.29} \]

LaTeX

Theorem 7.9

Let \(F\) be a real-valued function defined on the set of positive integers. Define a real-valued function \(G\) on the positive integers by

\[ G(n) = \sum _{k : k \mid n} F(k). \]

Then, for each positive integer \(n\), we have

\[ F(n) = \sum _{k : k \mid n} \mu \left(n/k \right) G(k), \]

where we write \(\mu (n/k)\) for \(\mu (1, n/k)\).

LaTeX

Theorem 8.1

The Fibonacci numbers satisfy the formula:

\[ f_n = \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^n - \frac{1}{\sqrt{5}} \left( \frac{1 - \sqrt{5}}{2} \right)^n, \quad (n \geq 0).\tag {7.8} \]

LaTeX

Theorem 8.2

The sums of the binomial coefficients along the diagonals of Pascal’s triangle running upward from the left are Fibonacci numbers. More precisely, the \(n\)th Fibonacci number \(f_n\) satisfies

\[ f_n = \binom {n-1}{0} + \binom {n-2}{1} + \binom {n-3}{2} + \cdots + \binom {n-t}{t-1}, \]

where \(t = \left\lfloor \frac{n+1}{2} \right\rfloor \) is the floor of \(\frac{n+1}{2}\).

LaTeX

Theorem 8.3

Let \(n\) be a positive integer. Then

\[ g_n(x) = 1(1 + x)(1 + x + x^2)(1 + x + x^2 + x^3) \cdots (1 + x + x^2 + \cdots + x^{n-1}) \]

\[ = \frac{\prod _{j=1}^n (1 - x^j)}{(1 - x)^n}.\tag {7.14} \]

LaTeX

Theorem 8.4

Let \(S\) be the multiset \(\{ n_1 \cdot a_1, n_2 \cdot a_2, \dots , n_k \cdot a_k\} \), where \(n_1, n_2, \dots , n_k\) are nonnegative integers. Let \(h_n\) be the number of \(n\)-permutations of \(S\). Then the exponential generating function \(g^{(e)}(x)\) for the sequence \(h_0, h_1, h_2, \dots , h_n, \dots \) is given by

\[ g^{(e)}(x) = f_{n_1}(x) f_{n_2}(x) \cdots f_{n_k}(x), \tag {7.18} \]

where, for \(i = 1, 2, \dots , k\),

\[ f_{n_i}(x) = 1 + x + \frac{x^2}{2!} + \cdots + \frac{x^n}{{n_i}!}. \]

LaTeX

Theorem 8.5

Let \(q\) be a nonzero number. Then \(h_n = q^n\) is a solution of the linear homogeneous recurrence relation

\[ h_n - a_1 h_{n-1} - a_2 h_{n-2} - \cdots - a_k h_{n-k} = 0, \quad (a_k \neq 0, n \geq k) \tag {7.29} \]

with constant coefficients if and only if \(q\) is a root of the polynomial equation

\[ x^k - a_1 x^{k-1} - a_2 x^{k-2} - \cdots - a_k = 0. \tag {7.30} \]

If the polynomial equation has \(k\) distinct roots \(q_1, q_2, \dots , q_k\), then

\[ h_n = c_1 q_1^n + c_2 q_2^n + \cdots + c_k q_k^n. \tag {7.31} \]

is the general solution of (7.29) in the following sense: No matter what initial values for \(h_0, h_1, \dots , h_{k-1}\) are given, there are constants \(c_1, c_2, \dots , c_k\) so that (7.31) is the unique sequence which satisfies both the recurrence relation (7.29) and the initial values.

LaTeX

Theorem 8.6

Let \(q_1, q_2, \dots , q_t\) be the distinct roots of the following characteristic equation of the linear homogeneous recurrence relation with constant coefficients:

\[ h_n = a_1 h_{n-1} + a_2 h_{n-2} + \cdots + a_k h_{n-k}, \quad a_k \neq 0, \quad (n \geq k). \tag {7.39} \]

If \(q_i\) is an \(s_i\)-fold root of the characteristic equation of (7.39), the part of the general solution of this recurrence relation corresponding to \(q_i\) is

\[ H_n^{(i)} = c_1 q_i^n + c_2 n q_i^n + \cdots + c_{s_i} n^{s_i-1} q_i^n, \]

\[ = (c_1 + c_2 n + \cdots + c_{s_i} n^{s_i-1}) q_i^n. \]

The general solution of the recurrence relation is

\[ h_n = H_n^{(1)} + H_n^{(2)} + \cdots + H_n^{(t)}. \]

LaTeX

Theorem 8.7

Let

\[ h_0, h_1, h_2, \dots , h_n, \dots \]

be a sequence of numbers that satisfies the linear homogeneous recurrence relation

\[ h_n + c_1 h_{n-1} + \cdots + c_k h_{n-k} = 0, \quad c_k \neq 0, \quad (n \geq k). \tag {7.42} \]

of order \(k\) with constant coefficients. Then its generating function \(g(x)\) is of the form

\[ g(x) = \frac{p(x)}{q(x)}, \tag {7.43} \]

LaTeX

Theorem 8.8

Let \(h_n\) denote the number of ways of dividing a convex polygonal region with \(n+1\) sides into triangular regions by inserting diagonals that do not intersect in the interior. Define \(h_1 = 1\). Then \(h_n\) satisfies the recurrence relation

\begin{align} h_n & = h_1 h_{n-1} + h_2 h_{n-2} + \cdots + h_{n-1} h_1 \\ & = \sum _{k=1}^{n-1} h_k h_{n-k}, \quad (n \geq 2). \tag {7.54} \end{align}

The solution of this recurrence relation is

\[ h_n = \frac{1}{n} \binom {2n-2}{n-1}, \quad (n = 1, 2, 3, \dots ). \]

LaTeX

Theorem 9.1

The number of sequences

\begin{equation} \label{8.1} a_1, a_2, \ldots , a_{2n} \end{equation}

of \(2n\) terms that can be formed by using exactly \(n\) +1s and exactly \(n\) -1s whose partial sums are always positive:

\begin{equation} \label{8.2} a_1 + a_2 + \cdots + a_{k} \geq 0, \qquad (k = 1, 2, \ldots , 2n) \end{equation}

equals the nth Catalan number

\begin{align*} C_n = \frac{1}{n+1} \binom {2n}{n}, \qquad (n \geq 0). \end{align*}

LaTeX

Theorem 9.2

Let the geneml term of a sequence be a polynomial of degree \(p\) in \(n\):

\[ h_n = a_pn^p + a_{p-1}n^{p-1} + \cdots + a_1n + a_0, \qquad (n \geq 0). \]

Then \(\Delta ^{p+1}h_n = 0\) for all \(n \geq 0\).

LaTeX

Theorem 9.3

The geneml term of the sequence whose difference table has its Oth diagonal equal to

\[ c_0, c_1, c_2, \ldots , c_p, 0, 0, 0, \ldots , \qquad \text{where} c_p \neq 0 \]

is a polynomial in n of degree \(p\) satisfying

\begin{equation} \label{8.12} h_n = c_0\binom {n}{0} + c_1\binom {n}{1} + c_2\binom {n}{2} + \cdots + c_p\binom {n}{p}. \end{equation}

LaTeX

Theorem 9.4

Assume that the sequence \(h_0, h_1, h_2, \ldots , h_n, \ldots \) has a difference .table whose Oth diagonal equals

\[ c_0, c_1, c_2, \ldots , c_p, 0, 0, 0, \ldots . \]

Then

\begin{equation} \sum \limits _{k = 0}^{n}h_k = c_0\binom {n+1}{1} + c_1\binom {n+1}{2} + c_2\binom {n+1}{3} + \cdots + c_p\binom {n+1}{p+1}. \end{equation}

LaTeX

Theorem 9.5

If \(1 \leq k \leq p- 1\), then

\[ S(p, k) = kS(p-1, k) + S(p-1, k-1) \]

LaTeX

Theorem 9.6

The Stirling number of the second kind \(S(p, k)\) counts the number of partitions of a set of \(p\) elements into \(k\) indistinguishable boxes in which no box is empty.

LaTeX

Theorem 9.7

For each integer \(k\) with \(0 \leq k \leq p\), we have

\[ S^{\# }(p, k) = \sum \limits _{t = 0}^{k} (-1)^t \binom {k}{t}(k-t)^p \]

hence,

\[ S(p, k) = \frac{1}{k!}\sum \limits _{t = 0}^{k} (-1)^t \binom {k}{t}(k-t)^p \]

LaTeX

Theorem 9.8

If \(p \geq 1\), then

\[ B_p = \binom {p-1}{0}B_0 + \binom {p-1}{1}B_1 + \cdots + \binom {p-1}{p-1}B_{p-1}. \]

LaTeX

Theorem 9.9

If \(1 \leq k \leq p- 1\), then

\[ s(p, k) = (p-1)s(p-1, k) + s(p-1, k-1). \]

LaTeX

Theorem 9.10

The Stirling number \(s(p, k)\) of the first kind counts the number of arrangements of \(p\) objects into \(k\) nonempty circular permutations.

LaTeX

Theorem 9.11

Let \(n\) be a positive integer. Let \(p_n^s\) equal the number of self-conjugate partitions of \(n\), and let \(p_n^t\) be the number of partitions of \(n\) into distinct odd parts. Then

\[ p_n^s = p_n^t. \]

LaTeX

Theorem 9.12

Let \(n\) be a positive integer. Let \(p_n^{\textbf{o}}\) be the number of partitions of \(n\) into odd parts, and let \(p_n^{\textbf{d}}\) be the number of partitions of \(n\) into distinct parts. Then

\[ p_n^{\textbf{o}} = p_n^{\textbf{d}}. \]

LaTeX

Theorem 9.13

\[ \sum \limits _{n=0}^{\infty }p_nx^n = \prod \limits _{k=1}^{\infty }(1-x^k)^{-1} \]

LaTeX

Theorem 9.14

Lexicographic order is a linear extension of the partial order of majorization on the set \(\mathcal{P}_n\) of partitions of a positive integer \(n\).

LaTeX

Theorem 9.15

Let \(n\) be a positive integer. Let \(p_n^{\prime }\) be the number of partitions of \(n\) into an even number of distinct parts, and let \(p_n^{\prime \prime }\) be the number of partitions of \(n\) into an odd number of distinct parts. Then

\[ p_n^{\prime } = p_n^{\prime \prime } \]

where \(e_n\) is an error term given by \(e_n = (-1)^j\) if \(n\) is of the form \(j(3j\pm 1)/2\), and 0 otherwise.

LaTeX

Theorem 9.16

The number of rectangular lattice paths from \((r, s)\) to \((p, q)\) equals the binomial coefficient

\[ \binom {p-r+q-s}{p-r} = \binom {p-r+q-s}{q-s} \]

LaTeX

Theorem 9.17

Let \(n\) be a nonnegative integer. Then the number of subdiagonal rectangular lattice paths from \((0,0)\) to \((n, n)\) equals the \(n\)th Catalan number

\[ C_n = \frac{1}{n+1}\binom {2n}{n}. \]

LaTeX

Theorem 9.18

Let \(p\) and \(q\) be positive integers with \(p \geq q\). Then the number of subdiagonal rectangular lattice paths from \((0,0)\) to \((p, q)\) equals

\[ \frac{p-q+1}{p+1}\binom {p+q}{q}. \]

LaTeX

Theorem 9.19

Let \(r \leq \min \{ p, q\} \). Then

\[ K(p, q : rD) = \begin{pmatrix} & p+q-r & \\ p-r & q-r & r \end{pmatrix} = \frac{(p+q-r)!}{(p-r)!(q-r)!r!}, \]

and

\[ K(p,q) = \sum \limits _{r=0}^{\min \{ p, q\} }\frac{(p+q-r)!}{(p-r)!(q-r)!r!}. \]

LaTeX

Theorem 9.20

Let \(p\) and \(q\) be positive integers with \(p \geq q\), and let \(r\) be a nonnegative integer with \(r \leq q\). Then

\begin{align*} R(p, q : rD) & = \frac{p-q+1}{p-r+1}\frac{(p+q-r)!}{r!(p-r)!(q-r)!} \\ & = \frac{p-q+1}{p-r+1} \begin{pmatrix} & p+q-r & \\ r & (p-r) & (q-r) \end{pmatrix}\end{align*}

and

\[ R(p, q)=\sum \limits _{r=0}^q \frac{p-q+1}{p-r+1} \frac{(p+q-r)!}{r!(p-r)!(q-r)!} \]

LaTeX

Theorem 9.21

The generating function for the sequence (\(s_n: n \geq 1\)) of small Schroder numbers is

\[ \sum \limits _{n=1}^{\infty } s_n x^n=\frac{1}{4}\left(1+x-\sqrt{x^2-6 x+1}\right). \]

LaTeX

Theorem 9.22

The generating function for the sequence (\(R_n: n \geq 0\)) of large Schroder numbers is

\[ \sum \limits _{n=0}^{\infty } R_n x^n=\frac{1}{2x}\left(-(x - 1)-\sqrt{x^2-6 x+1}\right). \]

LaTeX

Theorem 9.24

Let \(n\) be a positive integer. Then the number of dissections of a convex polygonal region of \(n + 1\) sides equals the small Schroder number \(s_n\).

LaTeX

Theorem 10.1

In order for the family \(\mathcal{A} = (A_1, A_2 ,\ldots , A_n)\) of sets to have an \(SDR\), it is necessary that the following condition hold:
(MC): For each \(k=1,2, \ldots , n\) and each choice of \(k\) distinct indices \(i_1, i_2, \ldots , i_k\) from \(\{ 1,2, \ldots , n\} \),

\begin{equation} \label{9.1} \left|A_{i_1} \cup A_{i_2} \cup \cdots \cup A_{i_k}\right| \geq k \end{equation}

in short, every \(k\) sets of the family collectively contain at least \(k\) elements.

LaTeX

Theorem 10.2

The family \(\mathcal{A} = (A_1, A_2 ,\ldots , A_n)\) of subsets of a set \(Y\) has an SDR if and only if the marriage condition MC holds.

LaTeX

Theorem 10.3

Let \(\mathcal{A} = (A_1, A_2 ,\ldots , A_n)\) be a family of subsets of a finite set \(Y\). Let \(t\) be an integer with \(0 \leq t \leq n\). Then there exists a subfamily of \(t\) sets of \(\mathcal{A}\) that has an SDR if and only if

\begin{equation} \label{9.2} \left|A_{i_1} \cup A_{i_2} \cup \cdots \cup A_{i_k}\right| \geq k - (n -t) \end{equation}

for all \(k\) with \(k \geq n-t\) and all choices of \(k\) distinct indices \(i_1, i_2, \ldots , i_k\) from \(\{ 1,2, \ldots , n\} \).

LaTeX

Theorem 10.4

Let \(\mathcal{A} = (A_1, A_2 ,\ldots , A_n)\) be a family of subsets of a finite set \(Y\). Then the largest number of sets in a subfamily of \(\mathcal{A}\) with an SDR equals the smallest value taken by the expression

\begin{equation} \label{9.4} \left|A_{i_1} \cup A_{i_2} \cup \cdots \cup A_{i_k}\right| + n -k \end{equation}

over all choices of \(k = 1,2, \ldots ,n\) and all choices of \(k\) indices \(i_1, i_2, \ldots , i_k\) with \(1 \leq i_1 {\lt} i_2 {\lt}\ldots {\lt} i_k \leq n\).

LaTeX

Theorem 10.5

For each preferential ranking matrix, there exists a stable complete marriage.

LaTeX

Theorem 10.6

The stable complete marriage obtained from the deferred acceptance algorithm, with the women choosing the men, is women-optimal. If the men choose the women in the deferred acceptance algorithm, the resulting complete marriage is men-optimal.

LaTeX