2026-03-03T08:58:03Z

Etone: Created page with "== Basic Enumeration == The three basic rules for enumeration are: *'''The sum rule''': for any '''''disjoint''''' finite sets <math>S</math> and <math>T</math>, the cardinality of the union <math>|S\cup T|=|S|+|T|</math>. *'''The product rule''': for any finite sets <math>S</math> and <math>T</math>, the cardinality of the Cartesian product <math>|S\times T|=|S|\cdot|T|</math>. *'''The bijection rule''': if there exists a bijection between finite sets <math>S</math> a..."

== Basic Enumeration ==

The three basic rules for enumeration are:
*'''The sum rule''': for any '''''disjoint''''' finite sets <math>S</math> and <math>T</math>, the cardinality of the union <math>|S\cup T|=|S|+|T|</math>.
*'''The product rule''': for any finite sets <math>S</math> and <math>T</math>, the cardinality of the Cartesian product <math>|S\times T|=|S|\cdot|T|</math>.
*'''The bijection rule''': if there exists a bijection between finite sets <math>S</math> and <math>T</math>, then <math>|S|=|T|</math>.

Now we apply these rules to solve some basic enumeration problems.

=== Tuples ===
We count the number of <math>n</math>-tuples of <math>[m]</math>. Formally, we count the number of elements of <math>[m]^n</math>. (Remember that <math>[m]=\{0,1,2,\ldots,m-1\}</math>.)

It is not very hard to see that this number is <math>m^n</math>. That is, <math>|[m]^n|=m^n</math>.

To prove this rigorously, we use ''"the product rule"''.
*'''The product rule''': for any finite sets <math>S</math> and <math>T</math>, the cardinality of the Cartesian product <math>|S\times T|=|S|\cdot|T|</math>.

To count the size of <math>[m]^n\,</math>, we write <math>[m]^n=[m]\times[m]^{n-1}</math>, thus <math>|[m]^n|=m\cdot|[m]^{n-1}|\,</math>. Solving the recursion, we have that <math>|[m]^n|=m^n\,</math>.

=== Functions ===
Consider the problem of counting the number of functions mapping from <math>[n]</math> to <math>[m]</math>, i.e. we count the number of functions in the form <math>f:[n]\rightarrow [m]</math>.

We claim that this is the same as counting the number of <math>n</math>-tuples of <math>[m]</math>. To see this, for any <math>f:[n]\rightarrow [m]</math>, we define a tuple <math>v_f\in[m]^n</math> by letting <math>v_f(i)=f(i-1)</math> for every <math>i=1,2,\ldots,n</math>. It is easy to verify that <math>v</math> defines a '''bijection''' (a 1-1 correspondence) between <math>\{f:[n]\rightarrow [m]\}</math> and <math>[m]^n</math>. (Consider this as an exercise.)

Now we summon the ''"the bijection rule"''.
*'''The bijection rule''': if there exists a bijection between finite sets <math>S</math> and <math>T</math>, then <math>|S|=|T|</math>.

Applying this rule, we have that the number of functions from <math>[n]</math> to <math>[m]</math> equals the number of tuples in <math>[m]^n</math>, which is <math>m^n</math> as we proved previously.

=== Subsets ===
We count the number of subsets of a set.

Let<math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-element set, or '''<math>n</math>-set''' for short.
Let <math>2^S=\{T\mid T\subset S\}</math> denote the set of all subset of <math>S</math>. <math>2^S</math> is called the '''power set''' of <math>S</math>.

We give a combinatorial proof that <math>|2^S|=2^n</math>. We observe that every subset <math>T\in 2^S</math> corresponds to a unique bit-vector <math>v\in\{0,1\}^S</math>, such that each bit <math>v_i</math> indicates whether <math>x_i\in S</math>. Formally, define a map <math>\phi:2^S\rightarrow\{0,1\}^n</math> by <math>\phi(T)=(v_1,v_2,\ldots,v_n)</math>, where
:<math>
v_i=\begin{cases}
1 & \mbox{if }x_i\in T\\
0 & \mbox{if }x_i\not\in T.
\end{cases}
</math>
The map <math>\phi</math> is a bijection. The proof that <math>\phi</math> is a bijection is left as an exercise.

Since there is a bijection between <math>2^S</math> and <math>\{0,1\}^n</math>, it holds that <math>|2^S|=|\{0,1\}^n|=2^n\,</math>.

There are two elements of the proof:
* Find a 1-1 correspondence between subsets of an <math>n</math>-set and <math>n</math>-bit vectors.
: An application of this in Computer Science is that we can use bit-array as a data structure for sets: any set defined over a '''universe''' <math>U</math> can be represented by an array of <math>|U|</math> bits.
* The bijection rule: if there is a 1-1 correspondence between two sets, then their cardinalities are the same.

Many counting problems are solved by establishing a bijection between the set to be counted and some easy-to-count set. This kind of proofs are usually called (non-rigorously) '''combinatorial proofs'''.

----
We give an alternative proof that <math>|2^S|=2^n</math>. The proof needs another basic counting rule: ''"the sum rule"''.
*'''The sum rule''': for any '''''disjoint''''' finite sets <math>S</math> and <math>T</math>, the cardinality of the union <math>|S\cup T|=|S|+|T|</math>.

Define the function <math>f(n)=|2^{S_n}|</math>, where <math>S_n=\{x_1,x_2,\ldots,x_n\}</math> is an <math>n</math>-set. Our goal is to compute <math>f(n)</math>. We prove the following recursion for <math>f(n)</math>.

{{Theorem|Lemma|
:<math>f(n)=2f(n-1)\,</math>.
}}
{{Proof|
Fix an element <math>x_n</math>, let <math>U</math> be the set of subsets of <math>S_n</math> that contain <math>x_n</math> and let <math>V</math> be the set of subsets of <math>S_n</math> that do not contain <math>x_n</math>. It is obvious that <math>U</math> and <math>V</math> are disjoint (i.e. <math>U\cap V=\emptyset</math>) and <math>2^{S_n}=U\cup V</math>, because any subset of <math>S_n</math> either contains <math>x_n</math> or does not contain <math>x_n</math> but not both.

Applying the sum rule,
:<math>f(n)=|U\cup V|=|U|+|V|</math>.

The next observation is that <math>|U|=|V|=f(n-1)</math>, because <math>V</math> is exactly the <math>2^{S_{n-1}}</math>, and <math>U</math> is the set resulting from adding <math>x_n</math> to every member of <math>2^{S_{n-1}}</math>. Therefore,
:<math>f(n)=|U|+|V|=f(n-1)+f(n-1)=2f(n-1)\,</math>.
}}
The elementary case <math>f(0)=1</math>, because <math>\emptyset</math> has only one subset <math>\emptyset</math>. Solving the recursion, we have that <math>|2^S|=f(n)=2^n</math>.

=== Subsets of fixed size ===
We then count the number of subsets of fixed size of a set. Again, let <math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-set. We define <math>{S\choose k}</math> to be the set of all <math>k</math>-elements subsets (or '''<math>k</math>-subsets''') of <math>S</math>. Formally, <math>{S\choose k}=\{T\subseteq S\mid |T|=k\}</math>. The set <math>{S\choose k}</math> is sometimes called the '''<math>k</math>-uniform''' of <math>S</math>.

We denote that <math>{n\choose k}=\left|{S\choose k}\right|</math>. The notation <math>{n\choose k}</math> is read "<math>n</math> choose <math>k</math>".

{{Theorem|Theorem|
:<math>{n\choose k}=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1}=\frac{n!}{k!(n-k)!}</math>.
}}
{{Proof|
The number of '''ordered''' <math>k</math>-subsets of an <math>n</math>-set is <math>n(n-1)\cdots(n-k+1)</math>. Every <math>k</math>-subset has <math>k!=k(k-1)\cdots1</math> ways to order it.
}}

;Some notations
* <math>n!</math>, read "<math>n</math> factorial", is defined as that <math>n!=n(n-1)(n-2)\cdots 1</math>, with the convention that <math>0!=1</math>.
* <math>n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}</math> is usually denoted as <math>(n)_k\,</math>, read "<math>n</math> lower factorial <math>k</math>".

=== Binomial coefficient ===
The quantity <math>{n\choose k}</math> is called a '''binomial coefficient'''.

{{Theorem|Proposition|
# <math>{n\choose k}={n\choose n-k}</math>;
# <math>\sum_{k=0}^n {n\choose k}=2^n</math>.
}}
{{Proof|
1. We give two proofs for the first equation:
:(1) (numerical proof)
::<math>{n\choose k}=\frac{n!}{k!(n-k)!}={n\choose n-k}</math>.
:(2) (combinatorial proof)
::Choosing <math>k</math> elements from an <math>n</math>-set is equivalent to choosing the <math>n-k</math> elements to leave out. Formally, every <math>k</math>-subset <math>T\in{S\choose k}</math> is uniquely specified by its complement <math>S\setminus T\in {S\choose n-k}</math>, and the same holds for <math>(n-k)</math>-subsets, thus we have a bijection between <math>{S\choose k}</math> and <math>{S\choose n-k}</math>.
2. The second equation can also be proved in different ways, but the combinatorial proof is much easier. For an <math>n</math>-element set <math>S</math>, it is obvious that we can enumerate all subsets of <math>S</math> by enumerating <math>k</math>-subsets for every possible size <math>k</math>, i.e. it holds that
:<math>
2^S=\bigcup_{k=0}^n{S\choose k}.
</math>
For different <math>k</math>, <math>{S\choose k}</math> are obviously disjoint. By the sum rule,
:<math>2^n=|2^S|=\left|\bigcup_{k=0}^n{S\choose k}\right|=\sum_{k=0}^n\left|{S\choose k}\right|=\sum_{k=0}^n {n\choose k}</math>.
}}

<math>{n\choose k}</math> is called binomial coefficient for a reason. The following celebrated '''Binomial Theorem''' states that if a power of a binomial is expanded, the coefficients in the resulting polynomial are the binomial coefficients.

{{Theorem|Theorem (Binomial theorem)|
:<math>(1+x)^n=\sum_{k=0}^n{n\choose k}x^k</math>.
}}
{{Proof|
Write <math>(1+x)^n</math> as the product of <math>n</math> factors
:<math>(1+x)(1+x)\cdots (1+x)</math>.
The term <math>x^k</math> is obtained by choosing <math>x</math> from <math>k</math> factors and 1 from the rest <math>(n-k)</math> factors. There are <math>{n\choose k}</math> ways of choosing these <math>k</math> factors, so the coefficient of <math>x^k</math> is <math>{n\choose k}</math>.
}}

The following proposition has an easy proof due to the binomial theorem.
{{Theorem| Proposition|
:For <math>n>0</math>, the numbers of subsets of an <math>n</math>-set of even and of odd cardinality are equal.
}}
{{Proof|
Set <math>x=-1</math> in the binomial theorem.
:<math>
0=(1-1)^n=\sum_{k=0}^n{n\choose k}(-1)^k=\sum_{\overset{0\le k\le n}{k \text{ even}}}{n\choose k}-\sum_{\overset{0\le k\le n}{k \text{ odd}}}{n\choose k},
</math>
therefore
:<math>\sum_{\overset{0\le k\le n}{k \text{ even}}}{n\choose k}=\sum_{\overset{0\le k\le n}{k \text{ odd}}}{n\choose k}.</math>
}}

For counting problems, what we care about are ''numbers''. In the binomial theorem, a formal ''variable'' <math>x</math> is introduced. It looks having nothing to do with our problem, but turns out to be very useful. This idea of introducing a formal variable is the basic idea of some advanced counting techniques, which will be discussed in future classes.

=== Compositions of an integer ===
A '''composition''' of <math>n</math> is an expression of <math>n</math> as an ''ordered'' sum of ''positive'' integers. A '''<math>k</math>-composition''' of <math>n</math> is a composition of <math>n</math> with exactly <math>k</math> positive summands.

Formally, a <math>k</math>-composition of <math>n</math> is a <math>k</math>-tuple <math>(a_1,a_2,\ldots,a_k)\in\{1,2,\ldots,n\}^k</math> such that <math>a_1+a_2+\cdots+a_k=n</math>.

Suppose we have <math>n</math> identical balls in a line. A <math>k</math>-composition partitions these <math>n</math> balls into <math>k</math> ''nonempty'' sets, illustrated as follows.
:<math>
\begin{array}{c|cc|c|c|ccc|cc}
\bigcirc \,&\, \bigcirc \,& \bigcirc \,&\, \bigcirc \,&\, \bigcirc \,&\, \bigcirc &\, \bigcirc &\, \bigcirc \,&\, \bigcirc \,& \bigcirc
\end{array}
</math>
So the number of <math>k</math>-compositions of <math>n</math> equals the number of ways we put <math>k-1</math> bars "<math>|</math>" into <math>n-1</math> slots "<math>\sqcup</math>", where each slot has at most one bar (because all the summands <math>a_i>0</math>):
:<math>
\bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc
</math>
which is equal to the number of ways of choosing <math>k-1</math> slots out of <math>n-1</math> slots, which is <math>{n-1\choose k-1}</math>.

This graphic argument can be expressed as a formal proof. We construct a bijection between the set of <math>k</math>-compositions of <math>n</math> and <math>{\{1,2,\ldots,n-1\}\choose k-1}</math> as follows.

Let <math>\phi</math> be a mapping that given a <math>k</math>-composition <math>(a_1,a_2,\ldots,a_k)</math> of <math>n</math>,
:<math>
\begin{align}
\phi((a_1,a_2,\ldots,a_k))
&=\{a_1,\,\,a_1+a_2,\,\,a_1+a_2+a_3,\,\,\ldots,\,\,a_1+a_2+\cdots+a_{k-1}\}\\
&=\left\{\sum_{i=1}^ja_i\,\,\bigg|\,\, 1\le j<k\right\}.
\end{align}
</math>
<math>\phi</math> maps every <math>k</math>-composition to a <math>(k-1)</math>-subset of <math>\{1,2,\ldots,n-1\}</math>. It is easy to verify that <math>\phi</math> is a bijection, thus the number of <math>k</math>-compositions of <math>n</math> is <math>{n-1\choose k-1}</math>.
----
The number of <math>k</math>-compositions of <math>n</math> is equal to the number of solutions to <math>x_1+x_2+\cdots+x_k=n</math> in ''positive'' integers. This suggests us to relax the constraint and count the number of solutions to <math>x_1+x_2+\cdots+x_k=n</math> in ''nonnegative'' integers. We call such a solution a '''weak <math>k</math>-composition''' of <math>n</math>.

Formally, a weak <math>k</math>-composition of <math>n</math> is a tuple <math>(x_1,x_2,\ldots,x_k)\in[n+1]^k</math> such that <math>x_1+x_2+\cdots+x_k=n</math>.

Given a weak <math>k</math>-composition <math>(x_1,x_2,\ldots,x_k)</math> of <math>n</math>, if we set <math>y_i=x_i+1</math> for every <math>1\le i\le k</math>, then <math>y_i>0</math> and
:<math>
\begin{align}
y_1+y_2+\cdots +y_k
&=(x_1+1)+(x_2+1)+\cdots+(x_k+1)&=n+k,
\end{align}
</math>
i.e., <math>(y_1,y_2,\ldots,y_k)</math> is a <math>k</math>-composition of <math>n+k</math>. It is easy to see that it defines a bijection between weak <math>k</math>-compositions of <math>n</math> and <math>k</math>-compositions of <math>n+k</math>. Therefore, the number of weak <math>k</math>-compositions of <math>n</math> is <math>{n+k-1\choose k-1}</math>.
----
We now count the number of solutions to <math>x_1+x_2+\cdots+x_k\le n</math> in nonnegative integers.

Let <math>x_{k+1}=n-(x_1+x_2+\cdots+x_k)</math>. Then <math>x_{k+1}\ge 0</math> and <math>x_1+x_2+\ldots+x_k+x_{k+1}=n</math>.
The problem is transformed to that counting the number of solutions to the above equation in nonnegative integers. The answer is <math>{n+k\choose k}</math>.

=== Multisets ===
A <math>k</math>-subset of an <math>n</math>-set <math>S</math> is sometimes called a '''<math>k</math>-combination of <math>S</math> without repetitions'''. This suggests the problem of counting the number of <math>k</math>-combinations of <math>S</math> '''''with repetitions'''''; that is, we choose <math>k</math> elements of <math>S</math>, disregarding order and allowing repeated elements.

;Example
:<math>S=\{1,2,3,4\}</math>. All <math>3</math>-combination without repetitions are
::<math>\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\,</math>.
:Allowing repetitions, we also include the following 3-combinations:
::<math>
\begin{align}
&\{1,1,1\},\{1,1,2\},\{1,1,3\},\{1,1,4\},\{1,2,2\},\{1,3,3\},\{1,4,4\},\\
&\{2,2,2\},\{2,2,3\},\{2,2,4\},\{2,3,3\},\{2,4,4\},\\
&\{3,3,3\},\{3,3,4\},\{3,4,4\}\\
&\{4,4,4\}
\end{align}
</math>

Combinations with repetitions can be formally defined as '''multisets'''. A multiset is a set with repeated elements. Formally, a multiset <math>M</math> on a set <math>S</math> is a function <math>m:S\rightarrow \mathbb{N}</math>. For any element <math>x\in S</math>, the integer <math>m(x)\ge 0</math> is the number of repetitions of <math>x</math> in <math>M</math>, called the '''multiplicity''' of <math>x</math>. The sum of multiplicities <math>\sum_{x\in S}m(x)</math> is called the '''cardinality''' of <math>M</math> and is denoted as <math>|M|</math>.

A <math>k</math>-multiset on a set <math>S</math> is a multiset <math>M</math> on <math>S</math> with <math>|M|=k</math>. It is obvious that a <math>k</math>-combination of <math>S</math> with repetition is simply a <math>k</math>-multiset on <math>S</math>.

The set of all <math>k</math>-multisets on <math>S</math> is denoted <math>\left({S\choose k}\right)</math>. Assuming that <math>n=|S|</math>, denote <math>\left({n\choose k}\right)=\left|\left({S\choose k}\right)\right|</math>, which is the number of <math>k</math>-combinations of an <math>n</math>-set with repetitions.

Believe it or not: we have already evaluated the number <math>\left({n\choose k}\right)</math>. If <math>S=\{x_1,x_2,\ldots,x_n\}</math>, let <math>z_i=m(x_i)</math>, then <math>\left({n\choose k}\right)</math> is the number of solutions to <math>z_1+z_2+\cdots+z_n=k</math> in nonnegative integers, which is the number of weak <math>n</math>-compositions of <math>k</math>, which we have seen is <math>{n+k-1\choose n-1}={n+k-1\choose k}</math>.

----

There is a direct combinatorial proof that <math>\left({n\choose k}\right)={n+k-1\choose k}</math>.

Given a <math>k</math>-multiset <math>0\le a_0\le a_1\le\cdots\le a_{k-1}\le n-1</math> on <math>[n]</math>, then defining <math>b_i=a_i+i</math>, we see that <math>\{b_0,b_1,\ldots,b_{k-1}\}</math> is a <math>k</math>-subset of <math>[n+k-1]</math>. Conversely, given a <math>k</math>-subset <math>0\le b_0\le b_1\le\cdots\le b_{k-1}\le n+k-2</math> of <math>[n+k-1]</math>, then defining <math>a_i=b_i-i</math>, we have that <math>\{a_0,a_1,\ldots,a_{k-1}\}</math> is a <math>k</math>-multiset on <math>[n]</math>. Therefore, we have a bijection between <math>\left({[n]\choose k}\right)</math> and <math>{[n+k-1]\choose k}</math>.

=== Multinomial coefficients ===
The binomial coefficient <math>{n\choose k}</math> may be interpreted as follows. Each element of an <math>n</math>-set is placed into two groups, with <math>k</math> elements in Group 1 and <math>n-k</math> elements in Group 2. The binomial coefficient <math>{n\choose k}</math> counts the number of such placements.

This suggests a generalization allowing more than two groups. Let <math>(a_1,a_2,\ldots,a_m)</math> be a tuple of nonnegative integers summing to <math>n</math>. Let <math>{n\choose a_1,a_2,\ldots,a_m}</math> denote the number of ways of assigning each element of an <math>n</math>-set to one of <math>m</math> groups <math>G_1,G_2,\ldots,G_m</math> so that exactly <math>a_i</math> elements are assigned to <math>G_i</math>.

The binomial coefficient is just the case when there are two groups, and <math>{n\choose k}={n\choose k,n-k}</math>. The number <math>{n\choose a_1,a_2,\ldots,a_m}</math> is called a '''multinomial coefficient'''. We can think of it as that <math>n</math> labeled balls are assigned to <math>m</math> labeled bins, and <math>{n\choose a_1,a_2,\ldots,a_m}</math> is the number of assignments such that the <math>i</math>-th bin has <math>a_i</math> balls in it.

The multinomial coefficient can also be interpreted as the number of ''permutations of multisets''. A permutation <math>\pi</math> of an <math>n</math>-set <math>S</math> can be defined in two equivalent ways:
* a bijection <math>\pi:S\rightarrow S</math>;
* a tuple <math>\pi=(x_1,x_2,\ldots,x_n)\in S^n</math> such that all <math>x_i</math> are distinct.
There are <math>n!</math> permutations of an <math>n</math>-set <math>S</math>.

A '''permutation of a multiset''' <math>M</math> is a tuple <math>\pi=(x_1,x_2,\ldots,x_n)</math> such that every <math>x_i\in M</math> appears in <math>\pi</math> for exactly <math>m(x_i)</math> times, where <math>m(x_i)</math> is the multiplicity of <math>x_i</math> in <math>M</math>.

;Example
:We want to enumerate all the ways of reordering the word "multinomial". Note that in this word, the letter "m", "l" and "i" each appears twice. So the problem is to enumerate the permutations of the multiset <math>\{\text{a, i, i, l, l, m, m, n, o, t, u}\}</math>.

Let <math>M</math> be a multiset of <math>m</math> distinct elements <math>x_1,x_2,\ldots,x_m</math> such that <math>x_i</math> has multiplicity <math>a_i</math> in <math>M</math>. A permutation <math>\pi</math> of multiset <math>M</math> assigns <math>n</math> indices <math>1,2,\ldots,n</math> to <math>m</math> groups, where each group corresponds to a distinct element <math>x_i</math>, such that <math>i</math> is assigned to group <math>j</math> if <math>\pi_i=x_j</math>.

Therefore,
<math>{n\choose a_1,a_2,\ldots,a_m}</math> is also the number of permutations of a multiset <math>M</math> with <math>|M|=n</math> such that <math>M</math> has <math>m</math> distinct elements whose multiplicities are given by <math>a_1,a_2,\ldots,a_m</math>.

{{Theorem|Theorem|
:<math>{n\choose a_1,a_2,\ldots,a_m}=\frac{n!}{a_1!a_2!\cdots a_m!}.</math>
}}
{{Proof|
There are <math>n!</math> permutations of <math>n</math> objects. Assume that these <math>n</math> objects are the elements of an multiset <math>M</math> of <math>m</math> distinct elements with <math>|M|=n</math> and multiplicities <math>a_1,a_2,\ldots,a_m</math>. Since <math>a_i!</math> permutations of object <math>i</math> do not change the permutation of the multiset <math>M</math>, every <math>a_1!a_2!\cdots a_m!</math> permutations of these <math>n</math> objects correspond to the same permutation of the multiset <math>M</math>. Thus, the number of permutations of <math>M</math> is <math>\frac{n!}{a_1!a_2!\cdots a_m!}</math>.
}}

We also have the Multinomial Theorem.
{{Theorem|Theorem|
:<math>{n\choose a_1,a_2,\ldots,a_m}</math> is the coefficient of <math>x_1^{a_1}x_2^{a_2}\cdots x_m^{a_m}</math> in <math>(x_1+x_2+\cdots +x_m)^n</math>.
}}
{{Proof|
Write
:<math>(x_1+x_2+\cdots +x_m)^n=(x_1+x_2+\cdots +x_m)\cdots (x_1+x_2+\cdots +x_m)</math>.
Each of the <math>n</math> factors corresponds to a distinct ball, and <math>x_1,x_2,\ldots,x_m</math> correspond to <math>m</math> groups. The coefficient of <math>x_1^{a_1}x_2^{a_2}\cdots x_m^{a_m}</math> equals the number of ways to put <math>n</math>distinct balls to <math>m</math> distinct groups so that group <math>i</math> receives <math>a_i</math> balls, which is exactly our first definition of <math>{n\choose a_1,a_2,\ldots,a_m}</math>.
}}

=== Partitions of a set ===
A '''partition''' of finite set <math>S</math> is a collection <math>P=\{S_1,S_2,\ldots,S_k\}</math> of subsets of <math>S</math> such that:
* <math>S_i\neq\emptyset</math> for every <math>i</math>;
* <math>S_i\cap S_j=\emptyset</math> if <math>i\neq j</math> (also called that blocks are pairwise '''disjoint''');
* <math>S_1\cup S_2\cup\cdots\cup S_k=S</math>.
Each <math>S_i</math> is called a '''block''' of partition <math>P</math>. We call <math>P</math> a '''<math>k</math>-partition''' of <math>S</math> if <math>|P|=k</math>.

Define <math>\left\{{n \atop k}\right\}</math> to be the number of <math>k</math>-partitions of an <math>n</math>-set. Note that since a partition <math>P</math> is a set, the order of blocks <math>S_1,S_2,\ldots,S_k</math> is disregarded when counting <math>k</math>-partitions.

The number <math>\left\{{n \atop k}\right\}</math> is called a '''Stirling number of the second kind'''.
:{|border="1"
|
;Stirling number
: [http://en.wikipedia.org/wiki/Stirling_number Stirling numbers] are named after James Stirling.There are two kinds of Stirling numbers. [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind Stirling number of the first kind] is related to the number of permutations with fixed number of disjoint cycles. And [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind] counts the number of ways of partitioning a set into fixed number of disjoint blocks. Both numbers arise from important combinatorial problems and have various applications in combinatorics and other branches of Mathematics.
|}
Unlike previous identities, it is very difficult to give a determinant for <math>\left\{{n \atop k}\right\}</math>. But we have the following recurrence:
{{Theorem|Theorem|
:<math>\left\{{n \atop k}\right\}=k\left\{{n-1 \atop k}\right\}+\left\{{n-1 \atop k-1}\right\}</math>.
}}
{{Proof|
To partition <math>\{1,2,\ldots,n\}</math> into <math>k</math> blocks,
* we can partition <math>\{1,2,\ldots,{n-1}\}</math> into <math>k</math> blocks and place <math>n</math> into one of the <math>k</math> blocks, which gives us <math>k\left\{{n-1 \atop k}\right\}</math> ways to do so;
* or we can partition <math>\{1,2,\ldots,{n-1}\}</math> into <math>k-1</math> blocks and let <math>\{n\}</math> be a block by itself, which gives us <math>\left\{{n-1 \atop k-1}\right\}</math> ways to do so.

The partitions constructed by these two methods are different, since by the first method, <math>n</math> is always in a block of cardinality <math>>1</math>, and by the second method, <math>\{n\}</math> is always a block. So the cases are disjoint. And any <math>k</math>-partition of an <math>n</math>-set must be constructible by one of the two methods, thus by the sum rule,
:<math>\,\left\{{n \atop k}\right\}=k\left\{{n-1 \atop k}\right\}+\left\{{n-1 \atop k-1}\right\}</math>.
}}

Let <math>B_n=\sum_{k=1}^n \left\{{n \atop k}\right\}</math>, which gives the total number of partitions of an <math>n</math>-set. <math>B(n)</math> is called the '''Bell number'''.

=== Partitions of a number ===
We count the ways of partitioning <math>n</math> ''identical'' objects into <math>k</math> ''unordered'' groups. This is equivalent to counting the ways partitioning a number <math>n</math> into <math>k</math> unordered parts.

A '''<math>k</math>-partition''' of a number <math>n</math> is a multiset <math>\{x_1,x_2,\ldots,x_k\}</math> with <math>x_i\ge 1</math> for every element <math>x_i</math> and <math>x_1+x_2+\cdots+x_k=n</math>.

We define <math>p_k(n)</math> as the number of <math>k</math>-partitions of <math>n</math>.

For example, number 7 has the following partitions:
<div class="center"><math>
\begin{align}
&\{7\}
& p_1(7)=1\\
&\{1,6\},\{2,5\},\{3,4\}
& p_2(7)=3\\
&\{1,1,5\}, \{1,2,4\}, \{1,3,3\}, \{2,2,3\}
& p_3(7)=4\\
&\{1,1,1,4\},\{1,1,2,3\}, \{1,2,2,2\}
& p_4(7)=3\\
&\{1,1,1,1,3\},\{1,1,1,2,2\}
& p_5(7)=2\\
&\{1,1,1,1,1,2\}
& p_6(7)=1\\
&\{1,1,1,1,1,1,1\}
& p_7(7)=1
\end{align}
</math></div>

Equivalently, we can also define that A <math>k</math>-partition of a number <math>n</math> is a <math>k</math>-tuple <math>(x_1,x_2,\ldots,x_k)</math> with:
* <math>x_1\ge x_2\ge\cdots\ge x_k\ge 1</math>;
* <math>x_1+x_2+\cdots+x_k=n</math>.

<math>p_k(n)</math> the number of integral solutions to the above system.

Let <math>p(n)=\sum_{k=1}^n p_k(n)</math> be the total number of partitions of <math>n</math>. The function <math>p(n)</math> is called the '''partition number'''.

We now try to determine <math>p_k(n)</math>. Unfortunately, <math>p_k(n)</math> does not have a nice closed form formula. We now give a recurrence for <math>p_k(n)</math>.

{{Theorem|Proposition|
:<math>p_k(n)=p_{k-1}(n-1)+p_k(n-k)\,</math>.
}}
{{Proof|
Suppose that <math>(x_1,\ldots,x_k)</math> is a <math>k</math>-partition of <math>n</math>. Note that it must hold that
:<math>x_1\ge x_2\ge \cdots \ge x_k\ge 1</math>.
There are two cases: <math>x_k=1</math> or <math>x_k>1</math>.
;Case 1.
:If <math>x_k=1</math>, then <math>(x_1,\cdots,x_{k-1})</math> is a distinct <math>(k-1)</math>-partition of <math>n-1</math>. And every <math>(k-1)</math>-partition of <math>n-1</math> can be obtained in this way. Thus the number of <math>k</math>-partitions of <math>n</math> in this case is <math>p_{k-1}(n-1)</math>.
;Case 2.
:If <math>x_k>1</math>, then <math>(x_1-1,\cdots,x_{k}-1)</math> is a distinct <math>k</math>-partition of <math>n-k</math>. And every <math>k</math>-partition of <math>n-k</math> can be obtained in this way. Thus the number of <math>k</math>-partitions of <math>n</math> in this case is <math>p_{k}(n-k)</math>.
In conclusion, the number of <math>k</math>-partitions of <math>n</math> is <math>p_{k-1}(n-1)+p_k(n-k)</math>, i.e.
:<math>p_k(n)=p_{k-1}(n-1)+p_k(n-k)\,</math>.
}}

Use the above recurrence, we can compute the <math>p_k(n)</math> for some decent <math>n</math> and <math>k</math> by computer simulation.

If we are not restricted ourselves to the precise estimation of <math>p_k(n)</math>, the next theorem gives an asymptotic estimation of <math>p_k(n)</math>. Note that it only holds for '''constant''' <math>k</math>, i.e. <math>k</math> does not depend on <math>n</math>.

{{Theorem|Theorem|
For any fixed <math>k</math>,
:<math>p_k(n)\sim\frac{n^{k-1}}{k!(k-1)!}</math>,
as <math>n\rightarrow \infty</math>.
}}
{{Proof|
Suppose that <math>(x_1,\ldots,x_k)</math> is a <math>k</math>-partition of <math>n</math>. Then <math>x_1+x_2+\cdots+x_k=n</math> and <math>x_1\ge x_2\ge \cdots \ge x_k\ge 1</math>.

The <math>k!</math> permutations of <math>(x_1,\ldots,x_k)</math> yield at most <math>k!</math> many <math>k</math>-compositions (the ''ordered'' sum of <math>k</math> positive integers). There are <math>{n-1\choose k-1}</math> many <math>k</math>-compositions of <math>n</math>, every one of which can be yielded in this way by permuting a partition. Thus,
:<math>k!p_k(n)\ge{n-1\choose k-1}</math>.

Let <math>y_i=x_i+k-i</math>. That is, <math>y_k=x_k, y_{k-1}=x_{k-1}+1, y_{k-2}=x_{k-2}+2,\ldots, y_{1}=x_{1}+k-1</math>. Then, it holds that
* <math>y_1>y_2>\cdots>y_k\ge 1</math>; and
* <math>y_1+y_2+\cdots+y_k=n+\frac{k(k-1)}{2}</math>.
Each permutation of <math>(y_1,y_2,\ldots,y_k)</math> yields a '''distinct''' <math>k</math>-composition of <math>n+\frac{k(k-1)}{2}</math>, because all <math>y_i</math> are distinct.
Thus,
:<math>k!p_k(n)\le {n+\frac{k(k-1)}{2}-1\choose k-1}</math>.

Combining the two inequalities, we have
:<math>\frac{{n-1\choose k-1}}{k!}\le p_k(n)\le \frac{{n+\frac{k(k-1)}{2}-1\choose k-1}}{k!}</math>.
The theorem follows.
}}

=== Ferrers diagram ===
A partition of a number <math>n</math> can be represented as a diagram of dots (or squares), called a '''Ferrers diagram''' (the square version of Ferrers diagram is also called a '''Young diagram''', named after a structured called Young tableaux).

Let <math>(x_1,x_2,\ldots,x_k)</math> with that <math>x_1\ge x_2\ge \cdots x_k\ge 1</math> be a partition of <math>n</math>. Its Ferrers diagram consists of <math>k</math> rows, where the <math>i</math>-th row contains <math>x_i</math> dots (or squares).

<div class="center">
{|border="0"
|
{|border="0"
|[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]
|-
|[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]
|-
|[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]
|-
|[[File:Chess xot45.svg|22px]]
|}
|
[[File:Chess t45.svg|120px]]
|align=center|
{|border="2" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]
|}
|-
|align=center|Ferrers diagram (''dot version'') of (5,4,2,1)||
|align=center|Ferrers diagram (''square version'') of (5,4,2,1)
|}
</div>

;Conjugate partition
The partition we get by reading the Ferrers diagram by column instead of rows is called the '''conjugate''' of the original partition.
<div class="center">
{|border="0"
|align=center|
{|border="2" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]
|}
|
[[File:Chess t45.svg|120px]]
|align=center|
{|border="2" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]
|}
|-
|align=center|<math>(6,4,4,2,1)</math>||
|align=center|conjugate: <math>(5,4,3,3,1,1)</math>
|}
</div>

Clearly,
* different partitions cannot have the same conjugate, and
* every partition of <math>n</math> is the conjugate of some partition of <math>n</math>,
so the conjugation mapping is a permutation on the set of partitions of <math>n</math>. This fact is very useful in proving theorems for partitions numbers.

Some theorems of partitions can be easily proved by representing partitions in Ferrers diagrams.

{{Theorem|Proposition|
# The number of partitions of <math>n</math> which have largest summand <math>k</math>, is <math>p_k(n)</math>.
# The number of <math>n</math> into <math>k</math> parts equals the number of partitions of <math>n-k</math> into at most <math>k</math> parts. Formally,
::<math>p_k(n)=\sum_{j=1}^k p_j(n-k)</math>.
}}
{{Proof|
# For every <math>k</math>-partition, the conjugate partition has largest part <math>k</math>. And vice versa.
# For a <math>k</math>-partition of <math>n</math>, remove the leftmost cell of every row of the Ferrers diagram. Totally <math>k</math> cells are removed and the remaining diagram is a partition of <math>n-k</math> into at most <math>k</math> parts. And for a partition of <math>n-k</math> into at most <math>k</math> parts, add a cell to each of the <math>k</math> rows (including the empty ones). This will give us a <math>k</math>-partition of <math>n</math>. It is easy to see the above mappings are 1-1 correspondences. Thus, the number of <math>n</math> into <math>k</math> parts equals the number of partitions of <math>n-k</math> into at most <math>k</math> parts.
}}

== The twelvfold way ==
We now introduce a general framework for counting problems, called the [http://en.wikipedia.org/wiki/Twelvefold_way twelvefold way]. This framework is introduced by the great mathematician and also a great teacher, [http://en.wikipedia.org/wiki/Gian-Carlo_Rota Gian-Carlo Rota].

Let <math>N</math> and <math>M</math> be finite sets with <math>|N|=n</math> and <math>|M|=m</math>. We count the number of functions <math>f:N\rightarrow M</math> subject to different restrictions. There are three restrictions regarding the mapping <math>f</math> itself:
# <math>f</math> is an '''arbitrary''' function;
# <math>f</math> is an '''injection''' (one-to-one);
# <math>f</math> is a '''surjection''' (onto).

The elements of <math>N</math> and <math>M</math> can be regarded as '''distinguishable''' or '''indistinguishable'''. Think of <math>N</math> as a set of <math>n</math> balls and <math>M</math> as a set of <math>m</math> bins. A function <math>f:N\rightarrow M</math> is an assignment of the <math>n</math> balls into <math>m</math> bins. The balls are ''distinguishable'' if each ball has a distinct label on it, and the balls are ''indistinguishable'' if they are identical. The same also applies to the bins.

Three restrictions on the functions, with two restrictions on each of the domain and the range, together give us twelve counting problems, called the '''Twelvefold Way'''.

The following table gives the solutions to the counting problems.
{|border="2" cellspacing="4" cellpadding="10" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|-
!bgcolor="#A7C1F2" | Elements of <math>N</math>
!bgcolor="#A7C1F2" | Elements of <math>M</math>
!bgcolor="#A7C1F2" | Any <math>f</math>
!bgcolor="#A7C1F2" | Injective (1-1) <math>f</math>
!bgcolor="#A7C1F2" | Surjective (on-to) <math>f</math>
|-
|align="center"| ''distinguishable''
|align="center"| ''distinguishable''
|align="center"| <math>m^n\,</math>
|align="center"| <math>\left(m\right)_n</math>
|align="center"| <math>m!\left\{{n\atop m}\right\}\,</math>
|-
|align="center"| ''indistinguishable''
|align="center"| ''distinguishable''
|align="center"| <math>\left({m\choose n}\right)</math>
|align="center"|<math>{m\choose n}</math>
|align="center"|<math>{n-1\choose m-1}</math>
|-
|align="center"| ''distinguishable''
|align="center"| ''indistinguishable''
|align="center"| <math>\sum_{k=1}^m \left\{{n\atop k}\right\}</math>
|align="center"| <math>\begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n>m\end{cases}</math>
|align="center"| <math>\left\{{n\atop m}\right\}\,</math>
|-
|align="center"| ''indistinguishable''
|align="center"| ''indistinguishable''
|align="center"| <math>\sum_{k=1}^m p_k(n)</math>
|align="center"| <math>\begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n>m\end{cases}</math>
|align="center"| <math>p_m(n)\,</math>
|}

In the Volume 4A of Don Knuth's [http://www-cs-faculty.stanford.edu/~uno/taocp.html TAOCP], the twelvefold way is presented as the problems of counting the ways of assigning <math>n</math> balls into <math>m</math> bins. The domain <math>N</math> corresponds to a set of <math>n</math> balls, the range <math>M</math> corresponds to a set of <math>m</math> bins, and each function corresponds to an assignment of <math>n</math> balls into <math>m</math> bins. Balls (or bins) are distinguishable if they are ''distinct'' and are indistinguishable if they are ''identical''. An injective function corresponds to an assignment with ''at most'' one ball in each bin, and a surjective function corresponds to an assignment with ''at least'' one ball(s) in each bin.

{|border="2" cellspacing="4" cellpadding="10" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|-
!align="center" bgcolor="#A7C1F2" | balls per bin
!align="center" bgcolor="#A7C1F2" | unrestricted
!align="center" bgcolor="#A7C1F2" | ≤ 1
!align="center" bgcolor="#A7C1F2" | ≥ 1
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> distinct balls, <math>m</math> distinct bins
|align="center"| <math>n</math>-tuples of <math>m</math> things
|align="center"| <math>n</math>-permutations of <math>m</math> things
|align="center"| partition of <math>[n]</math> into <math>m</math> ordered parts
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> identical balls, <math>m</math> distinct bins
|align="center"| <math>n</math>-combinations of <math>[m]</math> with repetitions
|align="center"| <math>n</math>-combinations of <math>[m]</math> without repetitions
|align="center"| <math>m</math>-compositions of <math>n</math>
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> distinct balls, <math>m</math> identical bins
|align="center"| partitions of <math>[n]</math> into <math>\le m</math> parts
|align="center"| <math>n</math> pigeons into <math>m</math> holes
|align="center"| partitions of <math>[n]</math> into <math>m</math> parts
|-
!align="center" bgcolor="#A7C1F2" | <math>n</math> identical balls, <math>m</math> identical bins
|align="center"| partitions of <math>n</math> into <math>\le m</math> parts
|align="center"| <math>n</math> pigeons into <math>m</math> holes
|align="center"| partitions of <math>n</math> into <math>m</math> parts
|}

== Reference ==
* ''Stanley,'' Enumerative Combinatorics, Volume 1, Chapter 1.

组合数学 (Spring 2026)

2026-03-03T08:57:28Z

Etone: /* Lecture Notes */

{{Infobox
|name = Infobox
|bodystyle =
|title = 组合数学 
Combinatorics
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = Wednesday, 2pm-4pm 逸B-313
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = Tuesday, 2-3pm 计算机系 804
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11 =
|data11 = van Lint and Wilson. ''A course in Combinatorics, 2nd ed.'', Cambridge Univ Press, 2001.
|header12 =
|label12 =
|data12 = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13 =
|data13 = Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Combinatorics'' class of Spring 2026. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* TBA

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** 丁天行
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-313.
* '''Office hour''': TBA
:* '''QQ群''': 1090691552 (加入时需报姓名、专业、学号)

= Syllabus =

=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）

=== Course materials ===
* [[组合数学 (Spring 2025)/Course materials|教材和参考书清单]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
* TBA

= Lecture Notes =
# [[组合数学 (Spring 2026)/Basic enumeration|Basic enumeration | 基本计数]]

= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox
* [https://yufeizhao.com/pm/ Probabilistic Methods in Combinatorics] and [https://yufeizhao.com/gtacbook/ Graph Theory and Additive Combinatorics] by Yufei Zhao
* [https://www.math.uvic.ca/~noelj/combinatoricsLectures.html Combinatorics Lecture Videos online]
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]

= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
** [https://en.wikipedia.org/wiki/Group_action Group action]
** [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers Orbits]
* [https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Pólya enumeration theorem]
** [https://en.wikipedia.org/wiki/Permutation_group Permutation group]
** [https://en.wikipedia.org/wiki/Cycle_index Cycle index]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [https://en.wikipedia.org/wiki/Sperner%27s_theorem Sperner's theorem]
** [https://en.wikipedia.org/wiki/Sperner_family Sperner system] or '''antichain'''
* [https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma Sauer–Shelah lemma]
** [https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension Vapnik–Chervonenkis dimension]
* [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem Van der Waerden's theorem]
:*[https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Hales–Jewett theorem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
* [https://en.wikipedia.org/wiki/Linear_programming Linear programming]
** [https://en.wikipedia.org/wiki/Dual_linear_program Duality]
** [https://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [https://en.wikipedia.org/wiki/Matroid Matroid]

组合数学 (Spring 2026)

2026-03-03T08:56:46Z

Etone: Created page with "{{Infobox |name = Infobox |bodystyle = |title = 组合数学 Combinatorics |titlestyle = |image = |imagestyle = |caption = |captionstyle = |headerstyle = background:#ccf; |labelstyle = background:#ddf; |datastyle = |header1 =Instructor |label1 = |data1 = |header2 = |label2 = |data2 = 尹一通 |header3 = |label3 = Email |data3 = yinyt@nju.edu.cn |header4 = |label4= office |data4=..."

{{Infobox
|name = Infobox
|bodystyle =
|title = 组合数学 
Combinatorics
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = Wednesday, 2pm-4pm 逸B-313
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = Tuesday, 2-3pm 计算机系 804
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11 =
|data11 = van Lint and Wilson. ''A course in Combinatorics, 2nd ed.'', Cambridge Univ Press, 2001.
|header12 =
|label12 =
|data12 = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13 =
|data13 = Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Combinatorics'' class of Spring 2026. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* TBA

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** 丁天行
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-313.
* '''Office hour''': TBA
:* '''QQ群''': 1090691552 (加入时需报姓名、专业、学号)

= Syllabus =

=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）

=== Course materials ===
* [[组合数学 (Spring 2025)/Course materials|教材和参考书清单]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
* TBA

= Lecture Notes =
#

= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox
* [https://yufeizhao.com/pm/ Probabilistic Methods in Combinatorics] and [https://yufeizhao.com/gtacbook/ Graph Theory and Additive Combinatorics] by Yufei Zhao
* [https://www.math.uvic.ca/~noelj/combinatoricsLectures.html Combinatorics Lecture Videos online]
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]

= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
** [https://en.wikipedia.org/wiki/Group_action Group action]
** [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers Orbits]
* [https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Pólya enumeration theorem]
** [https://en.wikipedia.org/wiki/Permutation_group Permutation group]
** [https://en.wikipedia.org/wiki/Cycle_index Cycle index]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [https://en.wikipedia.org/wiki/Sperner%27s_theorem Sperner's theorem]
** [https://en.wikipedia.org/wiki/Sperner_family Sperner system] or '''antichain'''
* [https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma Sauer–Shelah lemma]
** [https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension Vapnik–Chervonenkis dimension]
* [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem Van der Waerden's theorem]
:*[https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Hales–Jewett theorem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
* [https://en.wikipedia.org/wiki/Linear_programming Linear programming]
** [https://en.wikipedia.org/wiki/Dual_linear_program Duality]
** [https://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [https://en.wikipedia.org/wiki/Matroid Matroid]

Main Page

2026-03-03T07:47:24Z

Etone: /* Home Pages for Courses and Seminars */

This is a course/seminar wiki run by the [http://tcs.nju.edu.cn theory group] in the Department of Computer Science and Technology at Nanjing University.

== Home Pages for Courses and Seminars==
;Current semester
* [[高级算法 (Spring 2026)|高级算法 Advanced Algorithms (Spring 2026, Suzhou)]]

* [[组合数学 (Spring 2026)|组合数学 Combinatorics (Spring 2026)]]

* [[计算复杂性 (Spring 2026)|计算复杂性 Computational Complexity (Spring 2026)]]

* [[计算方法 Numerical method (Spring 2026)|计算方法 Numerical method (Spring 2026)]]

* [[概率论与数理统计 (Spring 2026)|概率论与数理统计 Probability Theory (Spring 2026)]]

;Past courses

* Advanced Algorithms: [[高级算法 (Fall 2025)|Fall 2025]], [[高级算法 (Spring 2025)|Spring 2025(Suzhou)]], [[高级算法 (Fall 2024)|Fall 2024]], [[高级算法 (Fall 2023)|Fall 2023]], [[高级算法 (Fall 2022)|Fall 2022]], [[高级算法 (Fall 2021)|Fall 2021]], [[高级算法 (Fall 2020)|Fall 2020]], [[高级算法 (Fall 2019)|Fall 2019]], [[高级算法 (Fall 2018)|Fall 2018]], [[高级算法 (Fall 2017)|Fall 2017]], [[随机算法 \ 高级算法 (Fall 2016)|Fall 2016]].

*Algorithm Design and Analysis: [https://tcs.nju.edu.cn/shili/courses/2024spring-algo/ Spring 2024]

* Combinatorics: [[组合数学 (Spring 2025)|Spring 2025]], [[组合数学 (Spring 2024)|Spring 2024]], [[组合数学 (Spring 2023)|Spring 2023]], [[组合数学 (Fall 2019)|Fall 2019]], [[组合数学 (Fall 2017)|Fall 2017]], [[组合数学 (Fall 2016)|Fall 2016]], [[组合数学 (Fall 2015)|Fall 2015]], [[组合数学 (Spring 2014)|Spring 2014]], [[组合数学 (Spring 2013)|Spring 2013]], [[组合数学 (Fall 2011)|Fall 2011]], [[Combinatorics (Fall 2010)|Fall 2010]].

* Computational Complexity: [[计算复杂性 (Spring 2025)|Spring 2025]], [[计算复杂性 (Spring 2024)|Spring 2024]], [[计算复杂性 (Spring 2023)|Spring 2023]], [[计算复杂性 (Fall 2019)|Fall 2019]], [[计算复杂性 (Fall 2018)|Fall 2018]].

* Foundations of Data Science: [[数据科学基础 (Fall 2025)|Fall 2025]], [[数据科学基础 (Fall 2024)|Fall 2024]]

* Numerical Method: [[计算方法 Numerical method (Spring 2025)|Spring 2025]], [[计算方法 Numerical method (Spring 2024)|Spring 2024]], [[计算方法 Numerical method (Spring 2023)|Spring 2023]], [https://liuexp.github.io/numerical.html Spring 2022].

* Probability Theory: [[概率论与数理统计 (Spring 2025)|Spring 2025]], [[概率论与数理统计 (Spring 2024)|Spring 2024]], [[概率论与数理统计 (Spring 2023)|Spring 2023]].

* Quantum Computation: [[量子计算 (Spring 2022)|Spring 2022]], [[量子计算 (Spring 2021)|Spring 2021]], [[量子计算 (Fall 2019)|Fall 2019]].

* Randomized Algorithms: [[随机算法 (Fall 2015)|Fall 2015]], [[随机算法 (Spring 2014)|Spring 2014]], [[随机算法 (Spring 2013)|Spring 2013]], [[随机算法 (Fall 2011)|Fall 2011]], [[Randomized Algorithms (Spring 2010)|Spring 2010]].

;Past seminars, workshops and summer schools
*计算理论之美暑期学校: [[计算理论之美 (Summer 2025)|2025]], [[计算理论之美 (Summer 2024)|2024]], [[计算理论之美 (Summer 2023)|2023]], [[计算理论之美 (Summer 2021)|2021]]
*[[Theory Seminar|理论计算机科学讨论班]]
*[[Study Group|理论计算机科学学习小组]]
*[[TCSPhD2020| 理论计算机科学优秀博士生论坛2020]]
*[[Quantum|量子算法与物理实现研讨会]]
*Theory Day: [[Theory@Suzhou 2025 | 2025 (Suzhou)]], [[Theory@Nanjing 2019|2019]], [[Theory@Nanjing 2018|2018]], [[Theory@Nanjing 2017|2017]]
*[[\Delta Seminar on Logic, Philosophy, and Computer Science|Δ Seminar on Logic, Philosophy, and Computer Science]]
*[[近似算法讨论班 (Fall 2011)|近似算法 Approximation Algorithms, Fall 2011.]]

; 其它链接
* [[General Circulation(Fall 2025)|大气环流 General Circulation of the Atmosphere, Fall 2025]]
* [[General Circulation(Fall 2024)|大气环流 General Circulation of the Atmosphere, Fall 2024]]

* [[概率论 (Summer 2014)| 概率与计算 (上海交大 Summer 2014)]]

Main Page

2026-03-03T07:45:59Z

Etone:

This is a course/seminar wiki run by the [http://tcs.nju.edu.cn theory group] in the Department of Computer Science and Technology at Nanjing University.

== Home Pages for Courses and Seminars==
;Current semester
* [[高级算法 (Spring 2026)|高级算法 Advanced Algorithms (Spring 2026, Suzhou)]]

* [[概率论与数理统计 (Spring 2026)|概率论与数理统计 Probability Theory (Spring 2026)]]

* [[计算复杂性 (Spring 2026)|计算复杂性 Computational Complexity (Spring 2026)]]

* [[计算方法 Numerical method (Spring 2026)|计算方法 Numerical method (Spring 2026)]]

;Past courses

* Advanced Algorithms: [[高级算法 (Fall 2025)|Fall 2025]], [[高级算法 (Spring 2025)|Spring 2025(Suzhou)]], [[高级算法 (Fall 2024)|Fall 2024]], [[高级算法 (Fall 2023)|Fall 2023]], [[高级算法 (Fall 2022)|Fall 2022]], [[高级算法 (Fall 2021)|Fall 2021]], [[高级算法 (Fall 2020)|Fall 2020]], [[高级算法 (Fall 2019)|Fall 2019]], [[高级算法 (Fall 2018)|Fall 2018]], [[高级算法 (Fall 2017)|Fall 2017]], [[随机算法 \ 高级算法 (Fall 2016)|Fall 2016]].

*Algorithm Design and Analysis: [https://tcs.nju.edu.cn/shili/courses/2024spring-algo/ Spring 2024]

* Combinatorics: [[组合数学 (Spring 2025)|Spring 2025]], [[组合数学 (Spring 2024)|Spring 2024]], [[组合数学 (Spring 2023)|Spring 2023]], [[组合数学 (Fall 2019)|Fall 2019]], [[组合数学 (Fall 2017)|Fall 2017]], [[组合数学 (Fall 2016)|Fall 2016]], [[组合数学 (Fall 2015)|Fall 2015]], [[组合数学 (Spring 2014)|Spring 2014]], [[组合数学 (Spring 2013)|Spring 2013]], [[组合数学 (Fall 2011)|Fall 2011]], [[Combinatorics (Fall 2010)|Fall 2010]].

* Computational Complexity: [[计算复杂性 (Spring 2025)|Spring 2025]], [[计算复杂性 (Spring 2024)|Spring 2024]], [[计算复杂性 (Spring 2023)|Spring 2023]], [[计算复杂性 (Fall 2019)|Fall 2019]], [[计算复杂性 (Fall 2018)|Fall 2018]].

* Foundations of Data Science: [[数据科学基础 (Fall 2025)|Fall 2025]], [[数据科学基础 (Fall 2024)|Fall 2024]]

* Numerical Method: [[计算方法 Numerical method (Spring 2025)|Spring 2025]], [[计算方法 Numerical method (Spring 2024)|Spring 2024]], [[计算方法 Numerical method (Spring 2023)|Spring 2023]], [https://liuexp.github.io/numerical.html Spring 2022].

* Probability Theory: [[概率论与数理统计 (Spring 2025)|Spring 2025]], [[概率论与数理统计 (Spring 2024)|Spring 2024]], [[概率论与数理统计 (Spring 2023)|Spring 2023]].

* Quantum Computation: [[量子计算 (Spring 2022)|Spring 2022]], [[量子计算 (Spring 2021)|Spring 2021]], [[量子计算 (Fall 2019)|Fall 2019]].

* Randomized Algorithms: [[随机算法 (Fall 2015)|Fall 2015]], [[随机算法 (Spring 2014)|Spring 2014]], [[随机算法 (Spring 2013)|Spring 2013]], [[随机算法 (Fall 2011)|Fall 2011]], [[Randomized Algorithms (Spring 2010)|Spring 2010]].

;Past seminars, workshops and summer schools
*计算理论之美暑期学校: [[计算理论之美 (Summer 2025)|2025]], [[计算理论之美 (Summer 2024)|2024]], [[计算理论之美 (Summer 2023)|2023]], [[计算理论之美 (Summer 2021)|2021]]
*[[Theory Seminar|理论计算机科学讨论班]]
*[[Study Group|理论计算机科学学习小组]]
*[[TCSPhD2020| 理论计算机科学优秀博士生论坛2020]]
*[[Quantum|量子算法与物理实现研讨会]]
*Theory Day: [[Theory@Suzhou 2025 | 2025 (Suzhou)]], [[Theory@Nanjing 2019|2019]], [[Theory@Nanjing 2018|2018]], [[Theory@Nanjing 2017|2017]]
*[[\Delta Seminar on Logic, Philosophy, and Computer Science|Δ Seminar on Logic, Philosophy, and Computer Science]]
*[[近似算法讨论班 (Fall 2011)|近似算法 Approximation Algorithms, Fall 2011.]]

; 其它链接
* [[General Circulation(Fall 2025)|大气环流 General Circulation of the Atmosphere, Fall 2025]]
* [[General Circulation(Fall 2024)|大气环流 General Circulation of the Atmosphere, Fall 2024]]

* [[概率论 (Summer 2014)| 概率与计算 (上海交大 Summer 2014)]]

Assignment 4, Fall 2025

2025-11-30T09:43:35Z

Etone: Created page with "在第四章中，我们从准地转近似下的纬向平均风场、温度场的趋势方程出发，定义了E-P通量。但是该定义下的E-P通量并没有考虑到大气湿过程的影响。如果从第三章介绍的水汽方程出发，我们可以按照以下步骤定义出一个包含大气大尺度运动中湿过程作用的广义的E-P通量。 1）在准地转近似下，如果我们按照对热力学方程的简化方法，将比湿（specific humidity..."

在第四章中，我们从准地转近似下的纬向平均风场、温度场的趋势方程出发，定义了E-P通量。但是该定义下的E-P通量并没有考虑到大气湿过程的影响。如果从第三章介绍的水汽方程出发，我们可以按照以下步骤定义出一个包含大气大尺度运动中湿过程作用的广义的E-P通量。

1）在准地转近似下，如果我们按照对热力学方程的简化方法，将比湿（specific humidity）<math>q</math>，分解成一个标准比湿 <math>q_s</math>（reference specific humidity）和变化量<math>q'</math>，并且同样假设<math> \partial q /\partial p</math>的水平变化很小，请证明在准地转近似下p坐标系下的纬向平均比湿<math>[q]</math>的变化方程为：

<math>\dfrac{\partial [q']}{\partial t} + \dfrac{\partial q_s}{\partial p}[\omega]=-[C-S] -\dfrac{\partial}{\partial y}[v^*q^*]</math>,

其中<math>C-S</math>为水汽方程在准地砖近似下的源汇项，表征由大尺度运动所带来的净凝结率。

2）如果重新定义一个非绝热加热项<math>Q_m</math>，使得<math>Q_m=Q-L[C-S](\frac{p}{p_o})^{R/c_p}</math>，请推导出一个关于<math>[\theta+\frac{L}{c_p}q']</math>的变化方程。

3）根据以上推导出的新方程和准地转近似下<math>[u]</math>的变化方程，请重新定义一个广义的E-P通量<math>\mathcal{F}_m</math>，使得新的E-P通量中包含了eddy对水汽输送的作用；并且证明，在湿绝热<math>(Q_m=0)</math>和无摩擦的情况下，平衡状态下的<math>\mathcal{F}_m</math>满足<math>\nabla \cdot \mathcal{F}_m=0</math>, 并请根据水汽输送的空间分布讨论：在实际大气中，新定义的E-P通量的<math>\nabla \cdot \mathcal{F}_m</math>应该有怎样的变化？eddy 对水汽的输送作用将对维持 Ferrel 环流起到怎样的作用？

4）请根据新定义出的E-P通量，定义出新的剩余环流(residual circulation, <math>[\tilde{v}_m]</math>, <math>[\tilde{\omega}_m]</math>)，并讨论此时剩余环流的含义是什么？相对于新的剩余环流，新的TEM方程(Transformed Eulerian Mean Equations)应该是什么？同时，也请写出，如果用剩余环流来表述，(1)问中推导出的水汽方程将如何改写，eddy强迫项应变为什么？

 作业用到的[http://tcs.nju.edu.cn/yzhang/Chap_5_vq_ver.pdf eddy对水汽输送的空间分布]

General Circulation(Fall 2025)

2025-11-30T09:42:58Z

Etone: /* Assignments */

{{Infobox
|name = Infobox
|bodystyle =
|title = 大气环流 
General Circulation of the Atmosphere
|titlestyle =

|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 张洋
|header3 =
|label3 = Email
|data3 = yangzhang@nju.edu.cn
|header4 =
|label4= office
|data4= 仙林大气楼 B410
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = 周一下午 2:00-4:00，仙II-110
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = 周五下午13:00-2:00 仙林大气楼B410
|header9 = Reference book
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = {{Infobox
|name =
|bodystyle =
|title =
|titlestyle =
|image = [[File:James-Circulating.jpg|border|100px]]
|imagestyle =
|caption = Introduction to Circulating Atmospheres, ''I. James'', Cambridge Press, 1995
|captionstyle = }}
|header11 =
|label11 =
|data11 = {{Infobox
|name =
|bodystyle =
|title =
|titlestyle =
|image = [[File:Oort.jpg|border|100px]]
|imagestyle =
|caption =Physics of Climate, ''Peixoto, J. P.'' and ''A. H. Oort'', Springer-Verlag New York, 1992
|captionstyle =
}}
|header12 =
|label12 =
|data12 = {{Infobox
|name =
|bodystyle =
|title =
|titlestyle =
|image = [[File:geoff.jpg|border|100px]]
|imagestyle =
|caption =Atmospheric and Oceanic Fluid Dynamics: Fundamentals and Large-scale Circulation, ''Vallis, G. K.'', Cambridge University Press, 2006
|captionstyle =
}}
|belowstyle = background:#ddf;
|below =
}}

This is the page for the class ''General Circulation of the Atmosphere (大气环流)'' for the Fall 2025 semester. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* 课程交流QQ群：631262169，请各位选课的同学入群。【2025.9.8】

= Course info =
* '''Instructor ''': 张洋，
:*office: 仙林气象楼 B410
:*email: yangzhang@nju.edu.cn
* '''Class meeting''': 周一下午 2:00-4:00；仙II-110
* '''Office hour''': 周五 下午1:00-2:00，仙林大气楼B410
* '''Prerequisites''': 动力气象，天气学，气候学
* '''Grading''': 平时作业（50％）＋期末考试（50％）
本课程将大致布置4次作业，每次作业一二道题目左右。题目将选择每个课题最具有代表性、需要一定思维强度和动手能力的训练用题目,意在使学生通过顺利完成作业来建立环流系统的物理模型、以对课程内容得到深刻全面地理解和掌握。期末考试题目数量将会比平时作业多,覆盖面更广,但会比作业题目简单,只涉及对基本内容的掌握和对环流理论的直接应用。

= Assignments =
# [[Assignment 1, Fall 2025|Reanalysis data and the earth's climatology]] [Due:2025.10.13]请在本次作业的截止日期前将本次作业的图片部分和文字部分打包作为附件发送至邮箱 circulation_nju@126.com [[Namelist_Assignment_1_2025|上交作业人员名单]]
# [[Assignment 2, Fall 2025|Simple energy balance climate model]][Due:2025.10.27]
# [[Assignment 3, Fall 2025|Hadley Cell]] [Due:2025.11.10]
# [[Assignment 4, Fall 2025|A generalized E-P flux ]][Due:2025.12.15]

= Course intro =
“大气环流”常指地球大气较大空间范围、较长时间尺度上的空气流动，及其对地球大气热量、动量、能量和水汽的全球输送。虽然从十七、十八世纪起人们就开始研究大尺度的大气运动(如Hadley在1735年提出的信风理论)，但大气环流真正发展成为一门较完备的学科方向却是近半个世纪的事情。随着四五十年代探空资料等高空气象要素的取得，以及六十年代卫星等覆盖全球的观测资料的加入，大气环流的空间结构和时间变化开始被系统、全面地揭示。与此同时，大气环流的数值模拟，也开始成为研究大气环流的一个主要方法，并发展至今成为了解和预估未来气候变化的主要手段。随着观测和模拟手段的进步，大气环流的理论研究也在近三十年开始快速地发展，人们对各种环流系统的维持和变化有了更全面、更深刻、也更为现代的理解。

现代的大气环流是大气动力学、天气学和气候学相结合的产物。大气环流，既是各种天气现象产生的背景流场，又是各种气候状态形成的动力机制。大气环流在低频、季节、年际、年代际等时间尺度的变化，不但会引起天气现象的变化，也影响着气候状态的形成。而在大气科学领域面临着诸如全球暖化、气候变化、环流异常等重大科学问题的今天，大气环流研究的重要性被推到了前所未有的高度,大气环流也成为活跃发展又充满挑战的学科方向。

本课程将讲述在过去几十年里大气环流在观测、理论和模拟上取得的进展。希望学生借此课程能熟悉大气环流的基本分布和形态，掌握各主要环流系统的维持和变化机制，建立各环流系统形成的物理模型，了解现阶段的大气环流模式，知道大气环流方向有待解决的科学问题。

作为一门课程，大气环流内容的讲述常可以有两条线索。一条是全球尺度上大气热量、动量、能量和水汽的分布与输送，Lorenz（1967）和 Peixoto and Oort（1992）是按此线索介绍大气环流的优秀教材；另一条线索，是各纬度、各区域内大气环流系统的形成、维持和变化机制，James（1995）和 Vallis（2006）是按此线索介绍大气环流的经典讲义。根据现阶段大气环流方向的研究特点，本课程的讲述将主要按照后一种方式来展开，并辅以介绍各环流系统对大气各要素场的输送。在介绍各环流系统时，本课程将以观测、理论和模拟为顺序，从各大气环流系统的观测事实入手，介绍大气环流系统的分布特征和时空变化特征；着重介绍关于环流系统的各种动力学模型和现阶段对环流系统的理解；辅以对环流系统模拟研究的介绍；最后通过三者的对比，讨论各环流系统有待研究的问题。

= Syllabus =
本课程具体的内容安排如下：第一章为大气环流的概述，介绍大气环流发展的历史、包含的内容以及大气环流研究的常用观测资料和分析方法。第二章介绍大气环流产生的外部强迫：辐射强迫和下界面过程。第三至六章介绍大气环流中的各个环流系统及它们的动力机制。第七章详细介绍各复杂度的大气环流模式。第八章介绍大气环流领域现阶段最大的一个开放课题：全球暖化背景下的大气环流。这一章既是对前几章所介绍的大气环流理论的应用与检验，又是对未来大气环流研究方向的探讨。借此让学生熟悉并理解大气环流领域亟需解决的课题。具体课程安排和参考书目如下。
== Course schedule ==
*大气环流概述 (Introduction) （6课时）
*大气环流的外部强迫（3课时）
**辐射强迫 (Radiative forcing)
**下界面过程 (Surface boundaries)
*经向环流系统 (Zonally-averaged circulations)
**Hadley 环流（4课时）
**Ferrel 环流，急流，中纬度的波流相互作用（8课时）
*纬向环流系统（Non-zonal circulations）（6课时）
**Storm tracks
**Monsoon
**ENSO and Walker circulation
*能量和水汽循环 (Angular momentum, energy and water vapor)（2课时）
*不同复杂度的大气环流模式 (General circulation in a hierarchy of models)（2课时）
*全球暖化背景下的大气环流 (General circulation in the global warming scenario)（2课时）

[[点击此处看详细课程安排 (click for more)]]

== References ==
*观测部分：Peixoto, J. P. and A. H. Oort, 1992: Physics of Climate. Springer-Verlag New York, Inc., 520 pp. 中文译本：气候物理学，1995，吴国雄、刘辉等译校，气象出版社。
*综合介绍：James, I., 1995: Introduction to circulating atmospheres. Cambridge University Press, 448 pp.
*理论部分：Vallis, G. K., 2006: Atmospheric and Oceanic Fluid Dynamics: Fundamentals and Large-scale Circulation. Cambridge University Press. 745 pp.
* [[其它参考书目（点击看详情）]]

Assignment 3, Fall 2025

2025-10-26T15:00:03Z

Etone: Created page with "Held-Hou(1980) 讨论了当外部强迫的经向分布呈二次勒让德多项式，即<math>\dfrac{\Theta_E(\phi,z)}{\Theta_o}=1-\dfrac{2}{3}\Delta_H P_2(\sin \phi)+\Delta_v(\dfrac{z}{H}-\dfrac{1}{2})</math>的情况下，哈德莱环流内的风场、温度场、环流的空间范围等将怎样随纬度和外力强迫的强度而变化。如果将外力强迫的空间分布改为<math>\dfrac{\Theta_E(\phi,z)}{\Theta_o}=1-\Delta_H(\sin \phi -\frac{1}{2})+\Delta_v(\dfra..."

Held-Hou(1980) 讨论了当外部强迫的经向分布呈二次勒让德多项式，即<math>\dfrac{\Theta_E(\phi,z)}{\Theta_o}=1-\dfrac{2}{3}\Delta_H P_2(\sin \phi)+\Delta_v(\dfrac{z}{H}-\dfrac{1}{2})</math>的情况下，哈德莱环流内的风场、温度场、环流的空间范围等将怎样随纬度和外力强迫的强度而变化。如果将外力强迫的空间分布改为<math>\dfrac{\Theta_E(\phi,z)}{\Theta_o}=1-\Delta_H(\sin \phi -\frac{1}{2})+\Delta_v(\dfrac{z}{H}-\dfrac{1}{2})</math>，

#请推导出哈德莱环流内的高空风场和垂直平均位温场<math>\dfrac{\tilde{\Theta}}{\Theta_o} </math>将如何随纬度分布;
#同样利用小角度假设，请推导出环流的空间范围<math>\phi_H </math> 的表达式。如果设 <math>r \equiv \dfrac{gH}{\Omega^2a^2} </math>, 请分别画出当 <math>\Delta_H=1/3</math> 和 <math>\Delta_H=1/6</math> 时, 与Held-Hou的情况相比，<math>\phi_H</math> 怎样随 <math>r</math> 而变化。
#选做题目：在此情况下，近地面风场的分布有怎样变化。

General Circulation(Fall 2025)

2025-10-26T14:59:25Z

Etone: /* Assignments */

{{Infobox
|name = Infobox
|bodystyle =
|title = 大气环流 
General Circulation of the Atmosphere
|titlestyle =

|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 张洋
|header3 =
|label3 = Email
|data3 = yangzhang@nju.edu.cn
|header4 =
|label4= office
|data4= 仙林大气楼 B410
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = 周一下午 2:00-4:00，仙II-110
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = 周五下午13:00-2:00 仙林大气楼B410
|header9 = Reference book
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = {{Infobox
|name =
|bodystyle =
|title =
|titlestyle =
|image = [[File:James-Circulating.jpg|border|100px]]
|imagestyle =
|caption = Introduction to Circulating Atmospheres, ''I. James'', Cambridge Press, 1995
|captionstyle = }}
|header11 =
|label11 =
|data11 = {{Infobox
|name =
|bodystyle =
|title =
|titlestyle =
|image = [[File:Oort.jpg|border|100px]]
|imagestyle =
|caption =Physics of Climate, ''Peixoto, J. P.'' and ''A. H. Oort'', Springer-Verlag New York, 1992
|captionstyle =
}}
|header12 =
|label12 =
|data12 = {{Infobox
|name =
|bodystyle =
|title =
|titlestyle =
|image = [[File:geoff.jpg|border|100px]]
|imagestyle =
|caption =Atmospheric and Oceanic Fluid Dynamics: Fundamentals and Large-scale Circulation, ''Vallis, G. K.'', Cambridge University Press, 2006
|captionstyle =
}}
|belowstyle = background:#ddf;
|below =
}}

This is the page for the class ''General Circulation of the Atmosphere (大气环流)'' for the Fall 2025 semester. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* 课程交流QQ群：631262169，请各位选课的同学入群。【2025.9.8】

= Course info =
* '''Instructor ''': 张洋，
:*office: 仙林气象楼 B410
:*email: yangzhang@nju.edu.cn
* '''Class meeting''': 周一下午 2:00-4:00；仙II-110
* '''Office hour''': 周五 下午1:00-2:00，仙林大气楼B410
* '''Prerequisites''': 动力气象，天气学，气候学
* '''Grading''': 平时作业（50％）＋期末考试（50％）
本课程将大致布置4次作业，每次作业一二道题目左右。题目将选择每个课题最具有代表性、需要一定思维强度和动手能力的训练用题目,意在使学生通过顺利完成作业来建立环流系统的物理模型、以对课程内容得到深刻全面地理解和掌握。期末考试题目数量将会比平时作业多,覆盖面更广,但会比作业题目简单,只涉及对基本内容的掌握和对环流理论的直接应用。

= Assignments =
# [[Assignment 1, Fall 2025|Reanalysis data and the earth's climatology]] [Due:2025.10.13]请在本次作业的截止日期前将本次作业的图片部分和文字部分打包作为附件发送至邮箱 circulation_nju@126.com [[Namelist_Assignment_1_2025|上交作业人员名单]]
# [[Assignment 2, Fall 2025|Simple energy balance climate model]][Due:2025.10.27]
# [[Assignment 3, Fall 2025|Hadley Cell]] [Due:2025.11.10]

= Course intro =
“大气环流”常指地球大气较大空间范围、较长时间尺度上的空气流动，及其对地球大气热量、动量、能量和水汽的全球输送。虽然从十七、十八世纪起人们就开始研究大尺度的大气运动(如Hadley在1735年提出的信风理论)，但大气环流真正发展成为一门较完备的学科方向却是近半个世纪的事情。随着四五十年代探空资料等高空气象要素的取得，以及六十年代卫星等覆盖全球的观测资料的加入，大气环流的空间结构和时间变化开始被系统、全面地揭示。与此同时，大气环流的数值模拟，也开始成为研究大气环流的一个主要方法，并发展至今成为了解和预估未来气候变化的主要手段。随着观测和模拟手段的进步，大气环流的理论研究也在近三十年开始快速地发展，人们对各种环流系统的维持和变化有了更全面、更深刻、也更为现代的理解。

现代的大气环流是大气动力学、天气学和气候学相结合的产物。大气环流，既是各种天气现象产生的背景流场，又是各种气候状态形成的动力机制。大气环流在低频、季节、年际、年代际等时间尺度的变化，不但会引起天气现象的变化，也影响着气候状态的形成。而在大气科学领域面临着诸如全球暖化、气候变化、环流异常等重大科学问题的今天，大气环流研究的重要性被推到了前所未有的高度,大气环流也成为活跃发展又充满挑战的学科方向。

本课程将讲述在过去几十年里大气环流在观测、理论和模拟上取得的进展。希望学生借此课程能熟悉大气环流的基本分布和形态，掌握各主要环流系统的维持和变化机制，建立各环流系统形成的物理模型，了解现阶段的大气环流模式，知道大气环流方向有待解决的科学问题。

作为一门课程，大气环流内容的讲述常可以有两条线索。一条是全球尺度上大气热量、动量、能量和水汽的分布与输送，Lorenz（1967）和 Peixoto and Oort（1992）是按此线索介绍大气环流的优秀教材；另一条线索，是各纬度、各区域内大气环流系统的形成、维持和变化机制，James（1995）和 Vallis（2006）是按此线索介绍大气环流的经典讲义。根据现阶段大气环流方向的研究特点，本课程的讲述将主要按照后一种方式来展开，并辅以介绍各环流系统对大气各要素场的输送。在介绍各环流系统时，本课程将以观测、理论和模拟为顺序，从各大气环流系统的观测事实入手，介绍大气环流系统的分布特征和时空变化特征；着重介绍关于环流系统的各种动力学模型和现阶段对环流系统的理解；辅以对环流系统模拟研究的介绍；最后通过三者的对比，讨论各环流系统有待研究的问题。

= Syllabus =
本课程具体的内容安排如下：第一章为大气环流的概述，介绍大气环流发展的历史、包含的内容以及大气环流研究的常用观测资料和分析方法。第二章介绍大气环流产生的外部强迫：辐射强迫和下界面过程。第三至六章介绍大气环流中的各个环流系统及它们的动力机制。第七章详细介绍各复杂度的大气环流模式。第八章介绍大气环流领域现阶段最大的一个开放课题：全球暖化背景下的大气环流。这一章既是对前几章所介绍的大气环流理论的应用与检验，又是对未来大气环流研究方向的探讨。借此让学生熟悉并理解大气环流领域亟需解决的课题。具体课程安排和参考书目如下。
== Course schedule ==
*大气环流概述 (Introduction) （6课时）
*大气环流的外部强迫（3课时）
**辐射强迫 (Radiative forcing)
**下界面过程 (Surface boundaries)
*经向环流系统 (Zonally-averaged circulations)
**Hadley 环流（4课时）
**Ferrel 环流，急流，中纬度的波流相互作用（8课时）
*纬向环流系统（Non-zonal circulations）（6课时）
**Storm tracks
**Monsoon
**ENSO and Walker circulation
*能量和水汽循环 (Angular momentum, energy and water vapor)（2课时）
*不同复杂度的大气环流模式 (General circulation in a hierarchy of models)（2课时）
*全球暖化背景下的大气环流 (General circulation in the global warming scenario)（2课时）

[[点击此处看详细课程安排 (click for more)]]

== References ==
*观测部分：Peixoto, J. P. and A. H. Oort, 1992: Physics of Climate. Springer-Verlag New York, Inc., 520 pp. 中文译本：气候物理学，1995，吴国雄、刘辉等译校，气象出版社。
*综合介绍：James, I., 1995: Introduction to circulating atmospheres. Cambridge University Press, 448 pp.
*理论部分：Vallis, G. K., 2006: Atmospheric and Oceanic Fluid Dynamics: Fundamentals and Large-scale Circulation. Cambridge University Press. 745 pp.
* [[其它参考书目（点击看详情）]]

Namelist Assignment 1 2025

2025-10-20T02:22:55Z

Etone:

学号姓名

221830009 丁潘宇

221840131 崔亚川

221830192 张梓轩

221830060 梁茗豪

221840001 檀纯芳

221840042 刘鑫磊

221840183 胡峻滔

221840252 徐玘

221830079 余秀蓝

221840217 于步涵

221840063 樊瑾奕

221840226 郑凯容

221840163 周若冰

221840204 张利荣

652025280008 李俊霖

502025280011 苟敏杰

502025280051 吴雨涵

502024280014 何昌霖

502025280038 齐若彤

502025280008 冯英飞

502025280022 蒋妍

502025280062 张艳

502025280049 王彧喆

502025280013 郭浩彬

502025280006 陈俊任

502025280001 边兆洋

502025280060 虞越

502025280032 刘毓晴

502025280041 饶嘉祺

502025280045 汪嘉斌

502025280024 康育恺

502025280035 骆建勋

502025280053 夏瑞阳

502025280010 葛雯菲

502025280005 陈镜宇

502025280026 李博彦

502025280028

502025280029 刘辰昊

502025280052 吴雨杭

502025280002 蔡鸿雨

502025280019 黄奏凯

502025280039 钱福荣

502025280043 宋丹阳

502025280048 王弈博

502025280017 黄扬

502025280033 龙江羽恬

502025280014 郭毅

502025280063 张一鸣

502025280059 尹志刚

502025280020 霍星宏

502025280023 开塞尔·克热米拉

Namelist Assignment 1 2025

2025-10-20T02:22:36Z

Etone: Created page with "学号姓名 221830009 丁潘宇 221840131 崔亚川 221830192 张梓轩 221830060 梁茗豪 221840001 檀纯芳 221840042 刘鑫磊 221840183 胡峻滔 221840252 徐玘 221830079 余秀蓝 221840217 于步涵 221840063 樊瑾奕 221840226 郑凯容 221840163 周若冰 221840204 张利荣 652025280008 李俊霖 502025280011 苟敏杰 502025280051 吴雨涵 502024280014 何昌霖 502025280038 齐若彤 502025280008 冯英飞 502025280022 蒋妍 50202..."

学号姓名
221830009 丁潘宇

221840131 崔亚川

221830192 张梓轩

221830060 梁茗豪

221840001 檀纯芳

221840042 刘鑫磊

221840183 胡峻滔

221840252 徐玘

221830079 余秀蓝

221840217 于步涵

221840063 樊瑾奕

221840226 郑凯容

221840163 周若冰

221840204 张利荣

652025280008 李俊霖

502025280011 苟敏杰

502025280051 吴雨涵

502024280014 何昌霖

502025280038 齐若彤

502025280008 冯英飞

502025280022 蒋妍

502025280062 张艳

502025280049 王彧喆

502025280013 郭浩彬

502025280006 陈俊任

502025280001 边兆洋

502025280060 虞越

502025280032 刘毓晴

502025280041 饶嘉祺

502025280045 汪嘉斌

502025280024 康育恺

502025280035 骆建勋

502025280053 夏瑞阳

502025280010 葛雯菲

502025280005 陈镜宇

502025280026 李博彦

502025280028

502025280029 刘辰昊

502025280052 吴雨杭

502025280002 蔡鸿雨

502025280019 黄奏凯

502025280039 钱福荣

502025280043 宋丹阳

502025280048 王弈博

502025280017 黄扬

502025280033 龙江羽恬

502025280014 郭毅

502025280063 张一鸣

502025280059 尹志刚

502025280020 霍星宏

502025280023 开塞尔·克热米拉

General Circulation(Fall 2025)

2025-10-20T02:08:00Z

Etone: /* Assignments */

{{Infobox
|name = Infobox
|bodystyle =
|title = 大气环流 
General Circulation of the Atmosphere
|titlestyle =

|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 张洋
|header3 =
|label3 = Email
|data3 = yangzhang@nju.edu.cn
|header4 =
|label4= office
|data4= 仙林大气楼 B410
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = 周一下午 2:00-4:00，仙II-110
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = 周五下午13:00-2:00 仙林大气楼B410
|header9 = Reference book
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = {{Infobox
|name =
|bodystyle =
|title =
|titlestyle =
|image = [[File:James-Circulating.jpg|border|100px]]
|imagestyle =
|caption = Introduction to Circulating Atmospheres, ''I. James'', Cambridge Press, 1995
|captionstyle = }}
|header11 =
|label11 =
|data11 = {{Infobox
|name =
|bodystyle =
|title =
|titlestyle =
|image = [[File:Oort.jpg|border|100px]]
|imagestyle =
|caption =Physics of Climate, ''Peixoto, J. P.'' and ''A. H. Oort'', Springer-Verlag New York, 1992
|captionstyle =
}}
|header12 =
|label12 =
|data12 = {{Infobox
|name =
|bodystyle =
|title =
|titlestyle =
|image = [[File:geoff.jpg|border|100px]]
|imagestyle =
|caption =Atmospheric and Oceanic Fluid Dynamics: Fundamentals and Large-scale Circulation, ''Vallis, G. K.'', Cambridge University Press, 2006
|captionstyle =
}}
|belowstyle = background:#ddf;
|below =
}}

This is the page for the class ''General Circulation of the Atmosphere (大气环流)'' for the Fall 2025 semester. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* 课程交流QQ群：631262169，请各位选课的同学入群。【2025.9.8】

= Course info =
* '''Instructor ''': 张洋，
:*office: 仙林气象楼 B410
:*email: yangzhang@nju.edu.cn
* '''Class meeting''': 周一下午 2:00-4:00；仙II-110
* '''Office hour''': 周五 下午1:00-2:00，仙林大气楼B410
* '''Prerequisites''': 动力气象，天气学，气候学
* '''Grading''': 平时作业（50％）＋期末考试（50％）
本课程将大致布置4次作业，每次作业一二道题目左右。题目将选择每个课题最具有代表性、需要一定思维强度和动手能力的训练用题目,意在使学生通过顺利完成作业来建立环流系统的物理模型、以对课程内容得到深刻全面地理解和掌握。期末考试题目数量将会比平时作业多,覆盖面更广,但会比作业题目简单,只涉及对基本内容的掌握和对环流理论的直接应用。

= Assignments =
# [[Assignment 1, Fall 2025|Reanalysis data and the earth's climatology]] [Due:2025.10.13]请在本次作业的截止日期前将本次作业的图片部分和文字部分打包作为附件发送至邮箱 circulation_nju@126.com [[Namelist_Assignment_1_2025|上交作业人员名单]]
# [[Assignment 2, Fall 2025|Simple energy balance climate model]][Due:2025.10.27]

= Course intro =
“大气环流”常指地球大气较大空间范围、较长时间尺度上的空气流动，及其对地球大气热量、动量、能量和水汽的全球输送。虽然从十七、十八世纪起人们就开始研究大尺度的大气运动(如Hadley在1735年提出的信风理论)，但大气环流真正发展成为一门较完备的学科方向却是近半个世纪的事情。随着四五十年代探空资料等高空气象要素的取得，以及六十年代卫星等覆盖全球的观测资料的加入，大气环流的空间结构和时间变化开始被系统、全面地揭示。与此同时，大气环流的数值模拟，也开始成为研究大气环流的一个主要方法，并发展至今成为了解和预估未来气候变化的主要手段。随着观测和模拟手段的进步，大气环流的理论研究也在近三十年开始快速地发展，人们对各种环流系统的维持和变化有了更全面、更深刻、也更为现代的理解。

现代的大气环流是大气动力学、天气学和气候学相结合的产物。大气环流，既是各种天气现象产生的背景流场，又是各种气候状态形成的动力机制。大气环流在低频、季节、年际、年代际等时间尺度的变化，不但会引起天气现象的变化，也影响着气候状态的形成。而在大气科学领域面临着诸如全球暖化、气候变化、环流异常等重大科学问题的今天，大气环流研究的重要性被推到了前所未有的高度,大气环流也成为活跃发展又充满挑战的学科方向。

本课程将讲述在过去几十年里大气环流在观测、理论和模拟上取得的进展。希望学生借此课程能熟悉大气环流的基本分布和形态，掌握各主要环流系统的维持和变化机制，建立各环流系统形成的物理模型，了解现阶段的大气环流模式，知道大气环流方向有待解决的科学问题。

作为一门课程，大气环流内容的讲述常可以有两条线索。一条是全球尺度上大气热量、动量、能量和水汽的分布与输送，Lorenz（1967）和 Peixoto and Oort（1992）是按此线索介绍大气环流的优秀教材；另一条线索，是各纬度、各区域内大气环流系统的形成、维持和变化机制，James（1995）和 Vallis（2006）是按此线索介绍大气环流的经典讲义。根据现阶段大气环流方向的研究特点，本课程的讲述将主要按照后一种方式来展开，并辅以介绍各环流系统对大气各要素场的输送。在介绍各环流系统时，本课程将以观测、理论和模拟为顺序，从各大气环流系统的观测事实入手，介绍大气环流系统的分布特征和时空变化特征；着重介绍关于环流系统的各种动力学模型和现阶段对环流系统的理解；辅以对环流系统模拟研究的介绍；最后通过三者的对比，讨论各环流系统有待研究的问题。

= Syllabus =
本课程具体的内容安排如下：第一章为大气环流的概述，介绍大气环流发展的历史、包含的内容以及大气环流研究的常用观测资料和分析方法。第二章介绍大气环流产生的外部强迫：辐射强迫和下界面过程。第三至六章介绍大气环流中的各个环流系统及它们的动力机制。第七章详细介绍各复杂度的大气环流模式。第八章介绍大气环流领域现阶段最大的一个开放课题：全球暖化背景下的大气环流。这一章既是对前几章所介绍的大气环流理论的应用与检验，又是对未来大气环流研究方向的探讨。借此让学生熟悉并理解大气环流领域亟需解决的课题。具体课程安排和参考书目如下。
== Course schedule ==
*大气环流概述 (Introduction) （6课时）
*大气环流的外部强迫（3课时）
**辐射强迫 (Radiative forcing)
**下界面过程 (Surface boundaries)
*经向环流系统 (Zonally-averaged circulations)
**Hadley 环流（4课时）
**Ferrel 环流，急流，中纬度的波流相互作用（8课时）
*纬向环流系统（Non-zonal circulations）（6课时）
**Storm tracks
**Monsoon
**ENSO and Walker circulation
*能量和水汽循环 (Angular momentum, energy and water vapor)（2课时）
*不同复杂度的大气环流模式 (General circulation in a hierarchy of models)（2课时）
*全球暖化背景下的大气环流 (General circulation in the global warming scenario)（2课时）

[[点击此处看详细课程安排 (click for more)]]

== References ==
*观测部分：Peixoto, J. P. and A. H. Oort, 1992: Physics of Climate. Springer-Verlag New York, Inc., 520 pp. 中文译本：气候物理学，1995，吴国雄、刘辉等译校，气象出版社。
*综合介绍：James, I., 1995: Introduction to circulating atmospheres. Cambridge University Press, 448 pp.
*理论部分：Vallis, G. K., 2006: Atmospheric and Oceanic Fluid Dynamics: Fundamentals and Large-scale Circulation. Cambridge University Press. 745 pp.
* [[其它参考书目（点击看详情）]]

高级算法 (Fall 2025)

2025-10-16T04:18:51Z

Etone: /* Lecture Notes */

{{Infobox
|name = Infobox
|bodystyle =
|title = 高级算法
 Advanced Algorithms
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''尹一通'''
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 =
|label5 =
|data5 = '''栗师'''
|header6 =
|label6 = Email
|data6 = shili@nju.edu.cn
|header7 =
|label7= office
|data7= 计算机系 605
|header8 =
|label8 =
|data8 = '''刘景铖'''
|header9 =
|label9 = Email
|data9 = liu@nju.edu.cn
|header10 =
|label10= office
|data10= 计算机系 516
|header11 = Class
|label11 =
|data11 =
|header12 =
|label12 = Class meetings
|data12 = Monday, 2pm-4pm Thursday (双), 2pm-4pm 仙Ⅰ-320
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = TBD, 计算机系 804 
|header15 = Textbooks
|label15 =
|data15 =
|header16 =
|label16 =
|data16 = [[File:MR-randomized-algorithms.png|border|100px]]
|header17 =
|label17 =
|data17 = Motwani and Raghavan. ''Randomized Algorithms''. Cambridge Univ Press, 1995.
|header18 =
|label18 =
|data18 = [[File:Approximation_Algorithms.jpg|border|100px]]
|header19 =
|label19 =
|data19 = Vazirani. ''Approximation Algorithms''. Springer-Verlag, 2001.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Advanced Algorithms'' class of fall 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/9/10)''' 本周四（9月11日）课程时间地点不变，为第五、六节在仙I-320。从第四周（9月15日）开始，采用新的上课时间：每周一的第五、六节，以及双周四的第五、六节，地点仍在仙I-320。

= Course info =
* '''Instructor '''（授课时间顺序）:
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
:*[https://tcs.nju.edu.cn/shili/ 栗师]：[mailto:shili@nju.edu.cn <shili@nju.edu.cn>]，计算机系 605
* '''Teaching Assistant''':
** 侯哲：houzhe@smail.nju.edu.cn
** 张弈垚：zhangyiyao@smail.nju.edu.cn
* '''Class meeting''':
** Monday, 2pm-4pm, 仙Ⅰ-320
** Thursday (双), 2pm-4pm, 仙Ⅰ-320
* '''Office hour''': Wednesday 2pm-3pm, 计算机系 804
* '''QQ群''': 524141453（加群请注明专业学号姓名）

= Syllabus =
随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。“高级算法”这门课程就是面向计算机算法的这一发展趋势而设立的。课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。

=== 先修课程 Prerequisites ===
* 必须：离散数学，概率论，线性代数。
* 推荐：算法设计与分析。

=== Course materials ===
* [[高级算法 (Fall 2025) / Course materials|教材和参考书]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time.

*[[高级算法 (Fall 2025)/Problem Set 1|Problem Set 1]] 请在 2025/10/30 上课之前(14:00 UTC+8) 提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A1.pdf').

= Lecture Notes =
# [[高级算法 (Fall 2025)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2025/Cut.pdf slides])
#* [[高级算法 (Fall 2025)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2025)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2025/Fingerprinting.pdf slides])
#* [[高级算法 (Fall 2025)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2025)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2025/Hashing.pdf slides])
#* [[高级算法 (Fall 2025)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2025)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2025)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2025/Concentration.pdf slides])
#* [[高级算法 (Fall 2025)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2025)/Dimension Reduction|Dimension Reduction]] ([http://tcs.nju.edu.cn/slides/aa2025/NNS.pdf slides])
#* [https://www.cs.princeton.edu/~hy2/teaching/fall22-cos521/notes/JL.pdf Professor Huacheng Yu's note on Johnson-Lindenstrauss Theorem]
#* [http://people.csail.mit.edu/gregory/annbook/introduction.pdf An introduction of LSH]
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2025/LLL.pdf slides])
#* [https://theory.stanford.edu/~jvondrak/MATH233A-2018/Math233-lec02.pdf Professor Jan Vondrák's Lecture Notes on LLL]
#* [https://www.cc.gatech.edu/~vigoda/6550/Notes/Lec16.pdf Professor Eric Vigoda's Lecture Notes on Algorithmic LLL]

= Related Online Courses=
* [https://www.cs.cmu.edu/~15850/ Advanced Algorithms] by Anupam Gupta at CMU.
* [http://people.csail.mit.edu/moitra/854.html Advanced Algorithms] by Ankur Moitra at MIT.
* [http://courses.csail.mit.edu/6.854/current/ Advanced Algorithms] by David Karger and Aleksander Mądry at MIT.
* [http://web.stanford.edu/class/cs168/index.html The Modern Algorithmic Toolbox] by Tim Roughgarden and Gregory Valiant at Stanford.
* [https://www.cs.princeton.edu/courses/archive/fall18/cos521/ Advanced Algorithm Design] by Pravesh Kothari and Christopher Musco at Princeton.
* [http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/ Linear and Semidefinite Programming (Advanced Algorithms)] by Anupam Gupta and Ryan O'Donnell at CMU.
* [https://www.cs.cmu.edu/~odonnell/papers/cs-theory-toolkit-lecture-notes.pdf CS Theory Toolkit] by Ryan O'Donnell at CMU.
* [https://cs.uwaterloo.ca/~lapchi/cs860/index.html Eigenvalues and Polynomials] by Lap Chi Lau at University of Waterloo.
* The [https://www.cs.cornell.edu/jeh/book.pdf "Foundations of Data Science" book] by Avrim Blum, John Hopcroft, and Ravindran Kannan.

高级算法 (Fall 2025)

2025-10-16T04:03:49Z

Etone: /* Lecture Notes */

{{Infobox
|name = Infobox
|bodystyle =
|title = 高级算法
 Advanced Algorithms
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''尹一通'''
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 =
|label5 =
|data5 = '''栗师'''
|header6 =
|label6 = Email
|data6 = shili@nju.edu.cn
|header7 =
|label7= office
|data7= 计算机系 605
|header8 =
|label8 =
|data8 = '''刘景铖'''
|header9 =
|label9 = Email
|data9 = liu@nju.edu.cn
|header10 =
|label10= office
|data10= 计算机系 516
|header11 = Class
|label11 =
|data11 =
|header12 =
|label12 = Class meetings
|data12 = Monday, 2pm-4pm Thursday (双), 2pm-4pm 仙Ⅰ-320
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = TBD, 计算机系 804 
|header15 = Textbooks
|label15 =
|data15 =
|header16 =
|label16 =
|data16 = [[File:MR-randomized-algorithms.png|border|100px]]
|header17 =
|label17 =
|data17 = Motwani and Raghavan. ''Randomized Algorithms''. Cambridge Univ Press, 1995.
|header18 =
|label18 =
|data18 = [[File:Approximation_Algorithms.jpg|border|100px]]
|header19 =
|label19 =
|data19 = Vazirani. ''Approximation Algorithms''. Springer-Verlag, 2001.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Advanced Algorithms'' class of fall 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/9/10)''' 本周四（9月11日）课程时间地点不变，为第五、六节在仙I-320。从第四周（9月15日）开始，采用新的上课时间：每周一的第五、六节，以及双周四的第五、六节，地点仍在仙I-320。

= Course info =
* '''Instructor '''（授课时间顺序）:
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
:*[https://tcs.nju.edu.cn/shili/ 栗师]：[mailto:shili@nju.edu.cn <shili@nju.edu.cn>]，计算机系 605
* '''Teaching Assistant''':
** 侯哲：houzhe@smail.nju.edu.cn
** 张弈垚：zhangyiyao@smail.nju.edu.cn
* '''Class meeting''':
** Monday, 2pm-4pm, 仙Ⅰ-320
** Thursday (双), 2pm-4pm, 仙Ⅰ-320
* '''Office hour''': Wednesday 2pm-3pm, 计算机系 804
* '''QQ群''': 524141453（加群请注明专业学号姓名）

= Syllabus =
随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。“高级算法”这门课程就是面向计算机算法的这一发展趋势而设立的。课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。

=== 先修课程 Prerequisites ===
* 必须：离散数学，概率论，线性代数。
* 推荐：算法设计与分析。

=== Course materials ===
* [[高级算法 (Fall 2025) / Course materials|教材和参考书]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time.

*[[高级算法 (Fall 2025)/Problem Set 1|Problem Set 1]] 请在 2025/10/30 上课之前(14:00 UTC+8) 提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A1.pdf').

= Lecture Notes =
# [[高级算法 (Fall 2025)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2025/Cut.pdf slides])
#* [[高级算法 (Fall 2025)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2025)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2025/Fingerprinting.pdf slides])
#* [[高级算法 (Fall 2025)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2025)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2025/Hashing.pdf slides])
#* [[高级算法 (Fall 2025)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2025)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2025)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2025/Concentration.pdf slides])
#* [[高级算法 (Fall 2025)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2025)/Dimension Reduction|Dimension Reduction]] ([http://tcs.nju.edu.cn/slides/aa2025/NNS.pdf slides])
#* [https://www.cs.princeton.edu/~hy2/teaching/fall22-cos521/notes/JL.pdf Professor Huacheng Yu's note on Johnson-Lindenstrauss Theorem]
#* [http://people.csail.mit.edu/gregory/annbook/introduction.pdf An introduction of LSH]
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2024/LLL.pdf slides])
#* [https://theory.stanford.edu/~jvondrak/MATH233A-2018/Math233-lec02.pdf Professor Jan Vondrák's Lecture Notes on LLL]
#* [https://www.cc.gatech.edu/~vigoda/6550/Notes/Lec16.pdf Professor Eric Vigoda's Lecture Notes on Algorithmic LLL]

= Related Online Courses=
* [https://www.cs.cmu.edu/~15850/ Advanced Algorithms] by Anupam Gupta at CMU.
* [http://people.csail.mit.edu/moitra/854.html Advanced Algorithms] by Ankur Moitra at MIT.
* [http://courses.csail.mit.edu/6.854/current/ Advanced Algorithms] by David Karger and Aleksander Mądry at MIT.
* [http://web.stanford.edu/class/cs168/index.html The Modern Algorithmic Toolbox] by Tim Roughgarden and Gregory Valiant at Stanford.
* [https://www.cs.princeton.edu/courses/archive/fall18/cos521/ Advanced Algorithm Design] by Pravesh Kothari and Christopher Musco at Princeton.
* [http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/ Linear and Semidefinite Programming (Advanced Algorithms)] by Anupam Gupta and Ryan O'Donnell at CMU.
* [https://www.cs.cmu.edu/~odonnell/papers/cs-theory-toolkit-lecture-notes.pdf CS Theory Toolkit] by Ryan O'Donnell at CMU.
* [https://cs.uwaterloo.ca/~lapchi/cs860/index.html Eigenvalues and Polynomials] by Lap Chi Lau at University of Waterloo.
* The [https://www.cs.cornell.edu/jeh/book.pdf "Foundations of Data Science" book] by Avrim Blum, John Hopcroft, and Ravindran Kannan.

高级算法 (Fall 2025)

Etone: /* Assignments */

{{Infobox
|name = Infobox
|bodystyle =
|title = 大气环流 
General Circulation of the Atmosphere
|titlestyle =

|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 张洋
|header3 =
|label3 = Email
|data3 = yangzhang@nju.edu.cn
|header4 =
|label4= office
|data4= 仙林大气楼 B410
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = 周一下午 2:00-4:00，仙II-110
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = 周五下午13:00-2:00 仙林大气楼B410
|header9 = Reference book
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = {{Infobox
|name =
|bodystyle =
|title =
|titlestyle =
|image = [[File:James-Circulating.jpg|border|100px]]
|imagestyle =
|caption = Introduction to Circulating Atmospheres, ''I. James'', Cambridge Press, 1995
|captionstyle = }}
|header11 =
|label11 =
|data11 = {{Infobox
|name =
|bodystyle =
|title =
|titlestyle =
|image = [[File:Oort.jpg|border|100px]]
|imagestyle =
|caption =Physics of Climate, ''Peixoto, J. P.'' and ''A. H. Oort'', Springer-Verlag New York, 1992
|captionstyle =
}}
|header12 =
|label12 =
|data12 = {{Infobox
|name =
|bodystyle =
|title =
|titlestyle =
|image = [[File:geoff.jpg|border|100px]]
|imagestyle =
|caption =Atmospheric and Oceanic Fluid Dynamics: Fundamentals and Large-scale Circulation, ''Vallis, G. K.'', Cambridge University Press, 2006
|captionstyle =
}}
|belowstyle = background:#ddf;
|below =
}}

This is the page for the class ''General Circulation of the Atmosphere (大气环流)'' for the Fall 2025 semester. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* 课程交流QQ群：631262169，请各位选课的同学入群。【2025.9.8】

= Course info =
* '''Instructor ''': 张洋，
:*office: 仙林气象楼 B410
:*email: yangzhang@nju.edu.cn
* '''Class meeting''': 周一下午 2:00-4:00；仙II-110
* '''Office hour''': 周五 下午1:00-2:00，仙林大气楼B410
* '''Prerequisites''': 动力气象，天气学，气候学
* '''Grading''': 平时作业（50％）＋期末考试（50％）
本课程将大致布置4次作业，每次作业一二道题目左右。题目将选择每个课题最具有代表性、需要一定思维强度和动手能力的训练用题目,意在使学生通过顺利完成作业来建立环流系统的物理模型、以对课程内容得到深刻全面地理解和掌握。期末考试题目数量将会比平时作业多,覆盖面更广,但会比作业题目简单,只涉及对基本内容的掌握和对环流理论的直接应用。

= Assignments =
# [[Assignment 1, Fall 2025|Reanalysis data and the earth's climatology]] [Due:2025.10.13]请在本次作业的截止日期前将本次作业的图片部分和文字部分打包作为附件发送至邮箱 circulation_nju@126.com 
# [[Assignment 2, Fall 2025|Simple energy balance climate model]]

= Course intro =
“大气环流”常指地球大气较大空间范围、较长时间尺度上的空气流动，及其对地球大气热量、动量、能量和水汽的全球输送。虽然从十七、十八世纪起人们就开始研究大尺度的大气运动(如Hadley在1735年提出的信风理论)，但大气环流真正发展成为一门较完备的学科方向却是近半个世纪的事情。随着四五十年代探空资料等高空气象要素的取得，以及六十年代卫星等覆盖全球的观测资料的加入，大气环流的空间结构和时间变化开始被系统、全面地揭示。与此同时，大气环流的数值模拟，也开始成为研究大气环流的一个主要方法，并发展至今成为了解和预估未来气候变化的主要手段。随着观测和模拟手段的进步，大气环流的理论研究也在近三十年开始快速地发展，人们对各种环流系统的维持和变化有了更全面、更深刻、也更为现代的理解。

现代的大气环流是大气动力学、天气学和气候学相结合的产物。大气环流，既是各种天气现象产生的背景流场，又是各种气候状态形成的动力机制。大气环流在低频、季节、年际、年代际等时间尺度的变化，不但会引起天气现象的变化，也影响着气候状态的形成。而在大气科学领域面临着诸如全球暖化、气候变化、环流异常等重大科学问题的今天，大气环流研究的重要性被推到了前所未有的高度,大气环流也成为活跃发展又充满挑战的学科方向。

本课程将讲述在过去几十年里大气环流在观测、理论和模拟上取得的进展。希望学生借此课程能熟悉大气环流的基本分布和形态，掌握各主要环流系统的维持和变化机制，建立各环流系统形成的物理模型，了解现阶段的大气环流模式，知道大气环流方向有待解决的科学问题。

作为一门课程，大气环流内容的讲述常可以有两条线索。一条是全球尺度上大气热量、动量、能量和水汽的分布与输送，Lorenz（1967）和 Peixoto and Oort（1992）是按此线索介绍大气环流的优秀教材；另一条线索，是各纬度、各区域内大气环流系统的形成、维持和变化机制，James（1995）和 Vallis（2006）是按此线索介绍大气环流的经典讲义。根据现阶段大气环流方向的研究特点，本课程的讲述将主要按照后一种方式来展开，并辅以介绍各环流系统对大气各要素场的输送。在介绍各环流系统时，本课程将以观测、理论和模拟为顺序，从各大气环流系统的观测事实入手，介绍大气环流系统的分布特征和时空变化特征；着重介绍关于环流系统的各种动力学模型和现阶段对环流系统的理解；辅以对环流系统模拟研究的介绍；最后通过三者的对比，讨论各环流系统有待研究的问题。

= Syllabus =
本课程具体的内容安排如下：第一章为大气环流的概述，介绍大气环流发展的历史、包含的内容以及大气环流研究的常用观测资料和分析方法。第二章介绍大气环流产生的外部强迫：辐射强迫和下界面过程。第三至六章介绍大气环流中的各个环流系统及它们的动力机制。第七章详细介绍各复杂度的大气环流模式。第八章介绍大气环流领域现阶段最大的一个开放课题：全球暖化背景下的大气环流。这一章既是对前几章所介绍的大气环流理论的应用与检验，又是对未来大气环流研究方向的探讨。借此让学生熟悉并理解大气环流领域亟需解决的课题。具体课程安排和参考书目如下。
== Course schedule ==
*大气环流概述 (Introduction) （6课时）
*大气环流的外部强迫（3课时）
**辐射强迫 (Radiative forcing)
**下界面过程 (Surface boundaries)
*经向环流系统 (Zonally-averaged circulations)
**Hadley 环流（4课时）
**Ferrel 环流，急流，中纬度的波流相互作用（8课时）
*纬向环流系统（Non-zonal circulations）（6课时）
**Storm tracks
**Monsoon
**ENSO and Walker circulation
*能量和水汽循环 (Angular momentum, energy and water vapor)（2课时）
*不同复杂度的大气环流模式 (General circulation in a hierarchy of models)（2课时）
*全球暖化背景下的大气环流 (General circulation in the global warming scenario)（2课时）

[[点击此处看详细课程安排 (click for more)]]

== References ==
*观测部分：Peixoto, J. P. and A. H. Oort, 1992: Physics of Climate. Springer-Verlag New York, Inc., 520 pp. 中文译本：气候物理学，1995，吴国雄、刘辉等译校，气象出版社。
*综合介绍：James, I., 1995: Introduction to circulating atmospheres. Cambridge University Press, 448 pp.
*理论部分：Vallis, G. K., 2006: Atmospheric and Oceanic Fluid Dynamics: Fundamentals and Large-scale Circulation. Cambridge University Press. 745 pp.
* [[其它参考书目（点击看详情）]]