# 组合数学 (Fall 2011)/Counting and existence

## Cayley's Formula

We now present a theorem of the number of labeled trees on a fixed number of vertices. It is due to Cayley in 1889. The theorem is often referred by the name Cayley's formula.

 Cayley's formula for trees There are ${\displaystyle n^{n-2}}$ different trees on ${\displaystyle n}$ distinct vertices.

The theorem has several proofs. Classical methods include the bijection which encodes a tree by a Prüfer code, through the Kirchhoff's matrix tree theorem, and by double counting.

### Prüfer code

The Prüfer code encodes a labeled tree to a sequence of labels. This gives a bijections between trees and tuples.

In a tree, the vertices of degree 1 are called leaves. It is easy to see that:

• each tree has at least two leaves; and
• after removing a leaf (along with the edge adjacent to it) from a tree, the resulting graph is still a tree.

The following algorithm transforms a tree ${\displaystyle T}$ of ${\displaystyle n}$ vertices ${\displaystyle 1,2,\ldots ,n}$, to a tuple ${\displaystyle (v_{1},v_{2},\ldots ,v_{n-2})\in \{1,2,\ldots ,n\}^{n-2}}$.

 Prüfer code (encoder) Input: A tree ${\displaystyle T}$ of ${\displaystyle n}$ distinct vertices, labeled by ${\displaystyle 1,2,\ldots ,n}$. let ${\displaystyle T_{1}=T}$; for ${\displaystyle i=1}$ to ${\displaystyle n-1}$, do let ${\displaystyle u_{i}}$ be the leaf in ${\displaystyle T_{i}}$ with the smallest label, and ${\displaystyle v_{i}}$ be its neighbor; let ${\displaystyle T_{i+1}}$ be the new tree obtained from deleting the leaf ${\displaystyle u_{i}}$ from ${\displaystyle T_{i}}$; end return ${\displaystyle (v_{1},v_{2},\ldots ,v_{n-2})}$;

It is trivial to observe the following lemma:

 Lemma 1 For each ${\displaystyle 1\leq i\leq n-1}$, ${\displaystyle T_{i}}$ is a tree of ${\displaystyle n-i+1}$ vertices. In particular, the vertices of ${\displaystyle T_{i}}$ are ${\displaystyle u_{i},u_{i+1},\ldots ,u_{n-1},v_{n-1}}$, and the edges of ${\displaystyle T_{i}}$ are precisely ${\displaystyle \{u_{j},v_{j}\}}$, ${\displaystyle i\leq j\leq n-1}$.

And there is a reason that we do not need to store ${\displaystyle v_{n-1}}$ in the Prüfer code.

 Lemma 2 It always holds that ${\displaystyle v_{n-1}=n}$.
Proof.
 Every tree (of at least two vertices) has at least two leaves. The ${\displaystyle u_{i}}$, ${\displaystyle 1\leq i\leq n-1}$, are the leaf of the smallest label in ${\displaystyle T_{i}}$, which can never be ${\displaystyle n}$, thus ${\displaystyle n}$ is never deleted.
${\displaystyle \square }$

Lemma 1 and 2 together imply that given a Prüfer code ${\displaystyle (v_{1},v_{2},\ldots ,v_{n-2})}$, the only remaining task to reconstruct the tree ${\displaystyle T}$ is to figure out those ${\displaystyle u_{i}}$, ${\displaystyle 1\leq i\leq n-1}$. The following lemma state how to obtain ${\displaystyle u_{i}}$, ${\displaystyle 1\leq i\leq n-1}$, from a Prüfer code ${\displaystyle (v_{1},v_{2},\ldots ,v_{n-2})}$.

 Lemma 3 For ${\displaystyle i=1,2,\ldots ,n-1}$, ${\displaystyle u_{i}}$ is the smallest element of ${\displaystyle \{1,2,\ldots ,n\}}$ not in ${\displaystyle \{u_{1},\ldots ,u_{i-1}\}\cup \{v_{i},\ldots ,v_{n-1}\}}$.
Proof.
 Note that ${\displaystyle u_{1},u_{2},\ldots ,u_{n-1},v_{n-1}}$ is a sequence of distinct vertices, because ${\displaystyle u_{1},u_{2},\ldots ,u_{n-1}}$ are deleted one by one from the tree, and ${\displaystyle v_{n-1}=n}$ is never deleted. Thus, each vertex ${\displaystyle v}$ appears among ${\displaystyle u_{1},u_{2},\ldots ,u_{n-1},v_{n-1}}$ exactly once. And each vertex ${\displaystyle v}$ appears for ${\displaystyle deg(v)}$ times among the edges ${\displaystyle \{u_{i},v_{i}\}}$, ${\displaystyle 1\leq i\leq n-1}$, where ${\displaystyle deg(v)}$ denotes the degree of vertex ${\displaystyle v}$ in the original tree ${\displaystyle T}$. Therefore, each vertex ${\displaystyle v}$ appears among ${\displaystyle v_{1},v_{2},\ldots ,v_{n-2}}$ for ${\displaystyle deg(v)-1}$ times. Similarly, each vertex ${\displaystyle v}$ of ${\displaystyle T_{i}}$ appears among ${\displaystyle v_{i},v_{i+1},\ldots ,v_{n-2}}$ for ${\displaystyle deg_{i}(v)-1}$ times, where ${\displaystyle deg_{i}(v)}$ is the degree of vertex ${\displaystyle v}$ in the tree ${\displaystyle T_{i}}$. In particular, the leaves of ${\displaystyle T_{i}}$ are not among ${\displaystyle \{v_{i},v_{i+1},\ldots ,v_{n-2}\}}$. Recall that the vertices of ${\displaystyle T_{i}}$ are ${\displaystyle u_{i},u_{i+1},\ldots ,u_{n-1},v_{n-1}}$. Then the leaves of ${\displaystyle T_{i}}$ are the elements of ${\displaystyle \{1,2,\ldots ,n\}}$ not in ${\displaystyle \{u_{1},\ldots ,u_{i-1}\}\cup \{v_{i},\ldots ,v_{n-1}\}}$. By definition of Prüfer code, ${\displaystyle u_{i}}$ is the leaf in ${\displaystyle T_{i}}$ of smallest label, hence the smallest element of ${\displaystyle \{1,2,\ldots ,n\}}$ not in ${\displaystyle \{u_{1},\ldots ,u_{i-1}\}\cup \{v_{i},\ldots ,v_{n-1}\}}$.
${\displaystyle \square }$

Applying Lemma 3, we have the following decoder for the Prüfer code:

 Prüfer code (decoder) Input: A tuple ${\displaystyle (v_{1},v_{2},\ldots ,v_{n-2})\in \{1,2,\ldots ,n\}^{n-2}}$. let ${\displaystyle T}$ be empty graph, and ${\displaystyle v_{n-1}=n}$; for ${\displaystyle i=1}$ to ${\displaystyle n-1}$, do let ${\displaystyle u_{i}}$ be the smallest label not in ${\displaystyle \{u_{1},\ldots ,u_{i-1}\}\cup \{v_{i},\ldots ,v_{n-1}\}}$; add an edge ${\displaystyle \{u_{i},v_{i}\}}$ to ${\displaystyle T}$; end return ${\displaystyle T}$;

In other words, the encoding of trees to tuples by the Prüfer code is reversible, thus the mapping is injective (1-1). To see it is also surjective, we need to show that for every possible ${\displaystyle (v_{1},v_{2},\ldots ,v_{n-2})\in \{1,2,\ldots ,n\}^{n-2}}$, the above decoder recovers a tree from it.

It is easy to see that the decoder always returns a graph of ${\displaystyle n-1}$ edges on the ${\displaystyle n}$ vertices. The only thing remaining to verify is that the returned graph has no cycle in it, which can be easily proved by a timeline argument (left as an exercise).

Therefore, the Prüfer code establishes a bijection between the set of trees on ${\displaystyle n}$ distinct vertices and the tuples from ${\displaystyle \{1,2,\ldots ,n\}^{n-2}}$. This proves Cayley's formula.

### Double counting

We now present a proof of the Cayley's formula by double counting, which is considered by the Proofs from THE BOOK "the most beautiful of them all".

Proof of Cayley's formula by double counting
 (Due to Pitman 1999) Let ${\displaystyle T_{n}}$ be the number of different trees defined on ${\displaystyle n}$ distinct vertices. A rooted tree is a tree with a special vertex. That is, one of the ${\displaystyle n}$ vertices is marked as the "root" of the tree. A rooted tree defines a natural direction of all edges, such that an edge ${\displaystyle uv}$ of the tree is directed from ${\displaystyle u}$ to ${\displaystyle v}$ if ${\displaystyle u}$ is before ${\displaystyle v}$ along the unique path from the root. We count the number of different sequences of directed edges that can be added to an empty graph on ${\displaystyle n}$ vertices to form from it a rooted tree. We note that such a sequence can be formed in two ways: Starting with an unrooted tree, choose one of its vertices as root, and fix an total order of edges to specify the order in which the edges are added. Starting from an empty graph, add the edges one by one in steps. In the first method, we pick one of the ${\displaystyle T_{n}}$ unrooted trees, choose one of the ${\displaystyle n}$ vertices as the root, and pick one of the ${\displaystyle (n-1)!}$ total orders of the ${\displaystyle n-1}$ edges. This gives us ${\displaystyle T_{n}n(n-1)!=T_{n}n!}$ ways. In the second method, we consider the number of choices in one step, and multiply the numbers of choices in all steps. This is done as follows. Given a sequence of adding ${\displaystyle n-1}$ edges to an empty graph to form a rooted tree, we reverse this sequence and get a sequence of removing edges one by one from the final rooted tree until no edge left. We observe that: At first, we remove an edge from the rooted tree. Suppose that the root of the tree is ${\displaystyle r}$, and the removed directed edge is ${\displaystyle (u,v)}$. After removing ${\displaystyle (u,v)}$, the original rooted tree is disconnected into two rooted trees, one rooted at ${\displaystyle r}$ and the other rooted at ${\displaystyle v}$. After removing ${\displaystyle k-1}$ edges, there are ${\displaystyle k}$ rooted trees. In the ${\displaystyle k}$th step, a directed edge ${\displaystyle (u,v)}$ in the current forest is removed and the tree containing ${\displaystyle (u,v)}$ is disconnected into two trees, one rooted at the old root of that tree, and the other rooted at ${\displaystyle v}$. We now again reverse the above procedure, and consider the sequence of adding directed edges to an empty graph to form a rooted tree. At first, we have ${\displaystyle n}$ rooted trees, each of 0 edge (${\displaystyle n}$ isolated vertices). After adding ${\displaystyle n-k}$ edges, there are ${\displaystyle k}$ rooted trees. Denoting the directed edge added next as ${\displaystyle (u,v)}$. As observed above, ${\displaystyle u}$ can be any one of the ${\displaystyle n}$ vertices; but ${\displaystyle v}$ must be the root of one of the ${\displaystyle k}$ trees, except the tree which contains ${\displaystyle u}$. There are ${\displaystyle n(k-1)}$ choices of such ${\displaystyle (u,v)}$. Multiplying the numbers of choices in all steps, the number of sequences of adding directed edges to an empty graph to form a rooted tree is given by ${\displaystyle \prod _{k=2}^{n}n(k-1)=n^{n-2}n!}$. By the principle of double counting, counting the same thing by different methods yield the same result. ${\displaystyle T_{n}n!=n^{n-2}n!}$, which gives that ${\displaystyle T_{n}=n^{n-2}}$.
${\displaystyle \square }$

## Existence by Counting

### Shannon's circuit lower bound

This is a fundamental problem in in Computer Science.

A boolean function is a function in the form ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}$.

Boolean circuit is a mathematical model of computation. Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$. A circuit has a unique node with outdegree zero, called the output node. Every other node is a gate. There are three types of gates: AND, OR (both with indegree two), and NOT (with indegree one).

Computations in Turing machines can be simulated by circuits, and any boolean function in P can be computed by a circuit with polynomially many gates. Thus, if we can find a function in NP that cannot be computed by any circuit with polynomially many gates, then NP${\displaystyle \neq }$P.

The following theorem due to Shannon says that functions with exponentially large circuit complexity do exist.

 Theorem (Shannon 1949) There is a boolean function ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}$ with circuit complexity greater than ${\displaystyle {\frac {2^{n}}{3n}}}$.
Proof.
 We first count the number of boolean functions ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}$. There are ${\displaystyle 2^{2^{n}}}$ boolean functions ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}$. Then we count the number of boolean circuit with fixed number of gates. Fix an integer ${\displaystyle t}$, we count the number of circuits with ${\displaystyle t}$ gates. By the De Morgan's laws, we can assume that all NOTs are pushed back to the inputs. Each gate has one of the two types (AND or OR), and has two inputs. Each of the inputs to a gate is either a constant 0 or 1, an input variable ${\displaystyle x_{i}}$, an inverted input variable ${\displaystyle \neg x_{i}}$, or the output of another gate; thus, there are at most ${\displaystyle 2+2n+t-1}$ possible gate inputs. It follows that the number of circuits with ${\displaystyle t}$ gates is at most ${\displaystyle 2^{t}(t+2n+1)^{2t}}$. If ${\displaystyle t=2^{n}/3n}$, then ${\displaystyle {\frac {2^{t}(t+2n+1)^{2t}}{2^{2^{n}}}}=o(1)<1,}$ thus, ${\displaystyle 2^{t}(t+2n+1)^{2t}<2^{2^{n}}.}$ Each boolean circuit computes one boolean function. Therefore, there must exist a boolean function ${\displaystyle f}$ which cannot be computed by any circuits with ${\displaystyle 2^{n}/3n}$ gates.
${\displaystyle \square }$

Note that by Shannon's theorem, not only there exists a boolean function with exponentially large circuit complexity, but almost all boolean functions have exponentially large circuit complexity.

### Double counting

The double counting principle states the following obvious fact: if the elements of a set are counted in two different ways, the answers are the same.

#### Handshaking lemma

The following lemma is a standard demonstration of double counting.

 Handshaking Lemma At a party, the number of guests who shake hands an odd number of times is even.

We model this scenario as an undirected graph ${\displaystyle G(V,E)}$ with ${\displaystyle |V|=n}$ standing for the ${\displaystyle n}$ guests. There is an edge ${\displaystyle uv\in E}$ if ${\displaystyle u}$ and ${\displaystyle v}$ shake hands. Let ${\displaystyle d(v)}$ be the degree of vertex ${\displaystyle v}$, which represents the number of times that ${\displaystyle v}$ shakes hand. The handshaking lemma states that in any undirected graph, the number of vertices whose degrees are odd is even. It is sufficient to show that the sum of odd degrees is even.

The handshaking lemma is a direct consequence of the following lemma, which is proved by Euler in his 1736 paper on Seven Bridges of Königsberg that began the study of graph theory.

 Lemma (Euler 1736) ${\displaystyle \sum _{v\in V}d(v)=2|E|}$
Proof.
 We count the number of directed edges. A directed edge is an ordered pair ${\displaystyle (u,v)}$ such that ${\displaystyle \{u,v\}\in E}$. There are two ways to count the directed edges. First, we can enumerate by edges. Pick every edge ${\displaystyle uv\in E}$ and apply two directions ${\displaystyle (u,v)}$ and ${\displaystyle (v,u)}$ to the edge. This gives us ${\displaystyle 2|E|}$ directed edges. On the other hand, we can enumerate by vertices. Pick every vertex ${\displaystyle v\in V}$ and for each of its ${\displaystyle d(v)}$ neighbors, say ${\displaystyle u}$, generate a directed edge ${\displaystyle (v,u)}$. This gives us ${\displaystyle \sum _{v\in V}d(v)}$ directed edges. It is obvious that the two terms are equal, since we just count the same thing twice with different methods. The lemma follows.
${\displaystyle \square }$

The handshaking lemma is implied directly by the above lemma, since the sum of even degrees is even.

## The Pigeonhole Principle

The pigeonhole principle states the following "obvious" fact:

${\displaystyle n+1}$ pigeons cannot sit in ${\displaystyle n}$ holes so that every pigeon is alone in its hole.

This is one of the oldest non-constructive principles: it states only the existence of a pigeonhole with more than one pigeons and says nothing about how to find such a pigeonhole.

The general form of pigeonhole principle, also known as the averaging principle, is stated as follows.

 Generalized pigeonhole principle If a set consisting of more than ${\displaystyle mn}$ objects is partitioned into ${\displaystyle n}$ classes, then some class receives more than ${\displaystyle m}$ objects.

### Inevitable divisors

The following is one of Erdős' favorite initiation questions to mathematics. The proof uses the Pigeonhole Principle.

 Theorem For any subset ${\displaystyle S\subseteq \{1,2,\ldots ,2n\}}$ of size ${\displaystyle |S|>n\,}$, there are two numbers ${\displaystyle a,b\in S}$ such that ${\displaystyle a|b\,}$.
Proof.
 For every odd number ${\displaystyle m\in \{1,2,\ldots ,2n\}}$, let ${\displaystyle C_{m}=\{2^{k}m\mid k\geq 0,2^{k}m\leq 2n\}}$. It is easy to see that for any ${\displaystyle b from the same ${\displaystyle C_{m}}$, it holds that ${\displaystyle a|b}$. Every number ${\displaystyle a\in S}$ can be uniquely represented as ${\displaystyle a=2^{k}m}$ for some odd number ${\displaystyle m}$, thus belongs to exactly one of ${\displaystyle C_{m}}$, for odd ${\displaystyle m\in \{1,2,\ldots ,2n\}}$. There are ${\displaystyle n}$ odd numbers in ${\displaystyle \{1,2,\ldots ,2n\}}$, thus ${\displaystyle n}$ different ${\displaystyle C_{m}}$, but ${\displaystyle |S|>n}$, thus there must exist distinct ${\displaystyle a,b\in S}$, supposed that ${\displaystyle b, belonging to the same ${\displaystyle C_{m}}$, which implies that ${\displaystyle a|b}$.
${\displaystyle \square }$

### Monotonic subsequences

Let ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ be a sequence of ${\displaystyle n}$ distinct real numbers. A subsequence is a sequence of distinct terms of ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ appearing in the same order in which they appear in ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$. Formally, a subsequence of ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ is an ${\displaystyle (a_{i_{1}},a_{i_{2}},\ldots ,a_{i_{k}})}$, with ${\displaystyle i_{1}.

A sequence ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ is increasing if ${\displaystyle a_{1}, and decreasing if ${\displaystyle a_{1}>a_{2}>\cdots >a_{n}}$.

We are interested in the longest increasing and decreasing subsequences of an ${\displaystyle a_{1}. It is intuitive that the length of both the longest increasing subsequence and the longest decreasing subsequence cannot be small simultaneously. A famous result of Erdős and Szekeres formally justifies this intuition. This is one of the first results in extremal combinatorics, published in the influential 1935 paper of Erdős and Szekeres.

 Theorem (Erdős-Szekeres 1935) A sequence of more than ${\displaystyle mn}$ different real numbers must contain either an increasing subsequence of length ${\displaystyle m+1}$, or a decreasing subsequence of length ${\displaystyle n+1}$.
Proof.
 (due to Seidenberg 1959) Let ${\displaystyle (a_{1},a_{2},\ldots ,a_{N})}$ be the original sequence of ${\displaystyle N>mn}$ distinct real numbers. Associate each ${\displaystyle a_{i}}$ a pair ${\displaystyle (x_{i},y_{i})}$, defined as: ${\displaystyle x_{i}}$: the length of the longest increasing subsequence ending at ${\displaystyle a_{i}}$; ${\displaystyle y_{i}}$: the length of the longest decreasing subsequence starting at ${\displaystyle a_{i}}$. A key observation is that ${\displaystyle (x_{i},y_{i})\neq (x_{j},y_{j})}$ whenever ${\displaystyle i\neq j}$. This is proved as follows: Case 1: If ${\displaystyle a_{i}, then the longest increasing subsequence ending at ${\displaystyle a_{i}}$ can be extended by adding on ${\displaystyle a_{j}}$, so ${\displaystyle x_{i}. Case 2: If ${\displaystyle a_{i}>a_{j}}$, then the longest decreasing subsequence starting at ${\displaystyle a_{j}}$ can be preceded by ${\displaystyle a_{i}}$, so ${\displaystyle y_{i}>y_{j}}$. Now we put ${\displaystyle N}$ "pigeons" ${\displaystyle a_{1},a_{2},\ldots ,a_{N}}$ into "pigeonholes" ${\displaystyle \{1,2,\ldots ,N\}\times \{1,2,\ldots ,N\}}$, such that ${\displaystyle a_{i}}$ is put into hole ${\displaystyle (x_{i},y_{i})}$, with at most one pigeon per each hole (since different ${\displaystyle a_{i}}$ has different ${\displaystyle (x_{i},y_{i})}$). The number of pigeons is ${\displaystyle N>mn}$. Due to pigeonhole principle, there must be a pigeon which is outside the region ${\displaystyle \{1,2,\ldots ,m\}\times \{1,2,\ldots ,n\}}$, which implies that there exists an ${\displaystyle a_{i}}$ with either ${\displaystyle x_{i}>m}$ or ${\displaystyle y_{i}>n}$. Due to our definition of ${\displaystyle (x_{i},y_{i})}$, there must be either an increasing subsequence of length ${\displaystyle m+1}$, or a decreasing subsequence of length ${\displaystyle n+1}$.
${\displaystyle \square }$

### Dirichlet's approximation

Let ${\displaystyle x}$ be an irrational number. We now want to approximate ${\displaystyle x}$ be a rational number (a fraction).

Since every real interval ${\displaystyle [a,b]}$ with ${\displaystyle a contains infinitely many rational numbers, there must exist rational numbers arbitrarily close to ${\displaystyle x}$. The trick is to let the denominator of the fraction sufficiently large.

Suppose however we restrict the rationals we may select to have denominators bounded by ${\displaystyle n}$. How closely we can approximate ${\displaystyle x}$ now?

The following important theorem is due to Dirichlet and his Schubfachprinzip ("drawer principle"). The theorem is fundamental in numer theory and real analysis, but the proof is combinatorial.

 Theorem (Dirichlet 1879) Let ${\displaystyle x}$ be an irrational number. For any natural number ${\displaystyle n}$, there is a rational number ${\displaystyle {\frac {p}{q}}}$ such that ${\displaystyle 1\leq q\leq n}$ and ${\displaystyle \left|x-{\frac {p}{q}}\right|<{\frac {1}{nq}}}$.
Proof.
 Let ${\displaystyle \{x\}=x-\lfloor x\rfloor }$ denote the fractional part of the real number ${\displaystyle x}$. It is obvious that ${\displaystyle \{x\}\in [0,1)}$ for any real number ${\displaystyle x}$. Consider the ${\displaystyle n+1}$ numbers ${\displaystyle \{kx\}}$, ${\displaystyle k=1,2,\ldots ,n+1}$. These ${\displaystyle n+1}$ numbers (pigeons) belong to the following ${\displaystyle n}$ intervals (pigeonholes): ${\displaystyle \left(0,{\frac {1}{n}}\right),\left({\frac {1}{n}},{\frac {2}{n}}\right),\ldots ,\left({\frac {n-1}{n}},1\right)}$. Since ${\displaystyle x}$ is irrational, ${\displaystyle \{kx\}}$ cannot coincide with any endpoint of the above intervals. By the pigeonhole principle, there exist ${\displaystyle 1\leq a, such that ${\displaystyle \{ax\},\{bx\}}$ are in the same interval, thus ${\displaystyle |\{bx\}-\{ax\}|<{\frac {1}{n}}}$. Therefore, ${\displaystyle |(b-a)x-\left(\lfloor bx\rfloor -\lfloor ax\rfloor \right)|<{\frac {1}{n}}}$. Let ${\displaystyle q=b-a}$ and ${\displaystyle p=\lfloor bx\rfloor -\lfloor ax\rfloor }$. We have ${\displaystyle |qx-p|<{\frac {1}{n}}}$ and ${\displaystyle 1\leq q\leq n}$. Dividing both sides by ${\displaystyle q}$, the theorem is proved.
${\displaystyle \square }$

## References

(声明: 资料受版权保护, 仅用于教学.)
(Disclaimer: The following copyrighted materials are meant for educational uses only.)