仅供看一乐。
\(L_n\) is the number of permutations of \(\{1,1,\ldots,n,n\}\) such that there are exact \(i\) numbers between two \(i\)s. Reverse regard as the same one.
Graph Algebra
If \(G=(V,E)\) is any graph, its complement \(\overline{G}=(V,\overline E)\) is obtained by letting
\[u-v \text{ in } \overline G \iff u\ne v \text{ and } u\not - v \text{ in } G \]Given two graphs \(G=(U,E)\) and \(H=(V,F)\), their union is the graph \((U\cup V,E\cup F)\). In the special case where \(U\) and \(V\) are disjoint, this case is called direct sum, donate it by \(G \oplus H\).
Another way to combine disjoint graph is join \(G - H\), which consist of \(G\oplus H\) together with all edges \(u-v\) for \(u\in U\) and \(v\in V\).
Cartesian product operation forms a graph \(G\Box H\) of order \(mn\) from a graph \(G=(U,E)\) of order \(m\) and a graph \(H=(V,F)\) of order \(n\). The vertices of \(G\square H\) are ordered pairs \((u,v)\), where \(u\in U\) and \(v\in V\); the edges are \((u,v)-(u',v)\) when \(u-u'\) in \(G\), together with \((u,v)-(u,v')\) when \(v-v'\) in \(H\).
The direct product \(G\otimes H\), also called "conjunction" or "categorical product", has \((u,v)-(u',v')\) when \(u-u'\) in \(G\) and \(v-v'\) in \(H\).
The strong product \(G\boxtimes H\) combines the edges of \(G\Box H\) and \(G\otimes H\).
The odd product \(G\triangle H\) has \((u,v)-(u',v')\) when either \(u-u'\) in \(G\) or \(v-v'\) in \(H\), but not both.
The lexicographic product \(G\circ H\), also called "composition", has \((u,v)-(u',v')\) when \(u-u'\) in \(G\), and has \((u,v)-(u,v')\) when \(v-v'\) in \(H\).
Exercise 7
-
\([\mathcal{M28}]\) Let \(f(x_1,\ldots,x_{2n})=\prod_{k=1}^n(x_kx_{n+k} \sum_{j=1}^{2n-k-1} x_jx_{j+k+1})\).
(a) Prove that \(\sum_{x_1,\ldots,x_{2n}\in \{-1,+1\}} f(x_1,\ldots,x_{2n})=2^{2n+1} L_n\).
展开 \(f\) 的多项式，其为 \(2n\) 次齐次多项式，注意到所有 \(x_1^2\cdots x_n^2\) 项对应了一个满足条件的排列，其他项至少有一个 \(i\) 满足 \(x_i\) 指数为奇数。所有 \(x_i\) 以及左右翻转给出了系数 \(2^{2n+1}\)。
(b) Explain how to evaluate this sum in \(O(4^nn)\) steps. How many bits of precision are needed for the arithmetic?
按 Gray-Code 顺序枚举所有 \(x_i\)。可以模大质数计算。
(c) Gain a factor of eight by exploiting the identities
\[f(x_1,\ldots,x_{2n})=f(-x_1,\ldots,-x_{2n})=f(x_{2n},\ldots,x_{1})=f(x_1,-x_2,\ldots,x_{2n-1},-x_{2n}) \]利用第 1,3 个等号，即得
\[2^{2n-1}L_n=\sum_{x_2,\ldots,x_{2n-1}\in \{-1,+1\}} f(1,x_2,\ldots,x_{2n-1},1) \]考虑 \(x_2\) 和 \(x_{2n-1}\) 是否相同，若不同，记 \(s_2=\sum_{x_3,\ldots,x_{2n-1}\in \{-1,+1\}} f(1,1,x_3,\ldots,x_{2n-1},1)\)。若相同，记 \(d=\sum_{x_2,\ldots,x_{2n-2}\in \{-1,+1\}} f(1,x_2,\ldots,x_{2n-2},x_2,1)\)。利用第 2 个等号，得到
\[2^{2n-1}L_n=2s_2+d \]重复如上操作，记 \(s_i=\sum_{x_2,\ldots,x_{i-1},x_{i+1},\ldots,x_{2n-i+1}\in \{-1,+1\}} f(1,x_2,\dots,x_{i-1},1,x_{i+1},\ldots,x_{2n-i+1},1,x_{i-1},\ldots,x_{n-1},1)\)。得到
\[2^{2n-2}L_n=s_n/2+\sum_{i=2}^{n-1} s_i \] -
\([\mathcal{M22}]\) Prove that every Langford pairing of \(\{1,1,\ldots,16,16\}\) must have seven uncompleted pairs at some point, when read from left to right.
令 \(n=16\)。对于一个合法的序列 \(a_1,\ldots,a_{2n}\)，设长为 \(2n\) 的序列 \(b\) 满足，每个 \(i\)，记 \(a_x=a_y=i,x<y\)，则 \(b_x=1,b_y=-1\)。定义序列 \(s\) 满足 \(s_0=0,s_i=s_{i-1}+b_i\)。考虑 \(\sum_{i=0}^{2n} s_i\)，由 Langford pairing 性质给出其等于 \(\sum_{i=1}^n (i+1)=152\)。若 \(\forall i, s_i\le 6\)，满足 \(|s_i-s_{i-1}|=1\) 最大可能的 \(\sum_{i=0}^{2n} s_i\) 在 \(\{s_i\}\) 为 \(0,1,2,3,4,5,6,5,6,\ldots,5,6,5,4,3,2,1,0\) 时得到，其值为 \(146\)，矛盾。
-
\([\mathcal{M21}]\) Let \(L_{ij}=(i+j) \bmod n\) for \(0 \le i, j < n\) be the addition table for integers mod \(n\). Prove that a latin square orthogonal to \(L\) exists if and only if \(n\) is odd.
如果 \(n\) 为偶数，若存在解 \(M\)，取 \(\{p_i\}\) 使得 \(M_{i,p_i}=0\)，则 \(\{t_i=L_{i,p_i}\}\) 应为排列。然而 $\sum_{i=0}^n (i+p_i) \bmod n \not\equiv \sum_{k=0}^n k \pmod n $，矛盾。
如果 \(n\) 为奇数，取 \(M_{ij}=(i-j)\bmod n\) 即可。
-
\([\mathcal{M25}]\) The string \(x_1x_2 \ldots x_N\) is called "\(n\)-ary" if each element \(x_j\) belongs to the set \(\{0, 1, \ldots , n−1\}\) of \(n\)-ary digits. Two strings \(x_1x_2 \ldots x_N\) and \(y_1y_2 \ldots y_N\) are said to be orthogonal if the \(N\) pairs \((x_j , y_j)\) are distinct for \(1 \le j \le N\). An \(n\)-ary matrix with \(m\) rows and \(n^2\) columns whose rows are orthogonal to each other is called an orthogonal array of order \(n\) and depth \(m\).
Prove that an orthogonal array of order \(n > 1\) and depth \(m\) is possible only if \(m \le n + 1\). Show that this upper limit is achievable when \(n\) is a prime number \(p\). Write out an example when \(p = 5\).
不妨设第一行为 \(0^n1^n\cdots(n-1)^n\)，剩下 \(m-1\) 行前 \(n\) 个均为 \(0,1,\ldots,n-1\)，这意味着 \(m-1\) 行中其他所有位置之中两两不同，于是给出了 \(m\) 的上界 \(n-1\)。
当 \(p=5\) 时，一个解为
\[\left(\begin{matrix} 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 \\ 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 \\ 0 1 2 3 4 2 3 4 0 1 4 0 1 2 3 1 2 3 4 0 3 4 0 1 2 \\ 0 1 2 3 4 3 4 0 1 2 1 2 3 4 0 4 0 1 2 3 2 3 4 0 1 \\ 0 1 2 3 4 4 0 1 2 3 3 4 0 1 2 2 3 4 0 1 1 2 3 4 0 \\ \end{matrix}\right) \] -
\([\mathcal{M21}]\) A geometric net is a system of points and lines that obeys three axioms:
i) Each line is a set of points.
ii) Distinct lines have at most one point in common.
iii) If \(p\) is a point and \(L\) is a line with \(p \not \in L\), then there is exactly one line \(M\) such that \(p \in M\) and \(L \cap M = \varnothing\).
If \(L \cap M = \varnothing\) we say that \(L\) is parallel to \(M\), and write \(L\ ||\ M\).
(a) Prove that the lines of a geometric net can be partitioned into equivalence classes, with two lines in the same class if and only if they are equal or parallel.
传递性利用反证法和 (iii) 即得，自反性显然成立。
(b) Show that if there are at least two classes of parallel lines, every line contains the same number of points as the other lines in its class.
利用 (ii) 两次即得双射。
(c) Furthermore, if there are at least three classes, there are numbers \(m\) and \(n\) such that all points belong to exactly \(m\) lines and all lines contain exactly \(n\) points.
利用 (ii) 可得每条线上点的双射，即得每条线都包含 \(n\) 个点。而 \(m\) 即为等价类个数。
-
\([\mathcal{M22}]\) Show that every orthogonal array can be regarded as a geometric net. Is the converse also true?
对于一个 orthogonal array with order \(n\) and depth \(m\)，可以构造一个 geometric net with \(m\) classes and \(n^2\) point，设 point 编号为 \(1,\ldots,n^2\)，orthogonal array 的每行对应一个 class，对于一行 \(\{a_i\}\)，其对应的 class 包含 \(n\) 条直线 \(\{\{j\ |\ a_j=k\}\ |\ 0\le k<n\}\)。容易验证其满足三条公理。
若 \(m\ge 3\)，利用 21(c) 可证点数为 \(n^2\)，其确实可以对应到一个 orthogonal array with order \(n\) and depth \(m\)。当 \(m=1,2\) 时显然不能。
-
\([\mathcal{M22}]\) Given a geometric net as described in exercise 21, construct the bipartite graph whose vertices are the points \(p\) and the lines \(L\) of the net, with \(p-L\) if and only if \(p \in L\). What is the girth(the length of the shortest circle) of this graph?
四元环存在将与公理 (ii) 矛盾，所以答案 \(\ge 6\)。
记 geometric net with \(m\) classes and \(n\) point，若 \(m=1\)，则无环。若 \(m=2\)，若 \(n\ge n'\ge 2\)，答案为 \(8\)，否则无环。若 \(n\ge 3\)，答案为 \(6\)。
-
\([\mathcal{M22}]\) Let \(u\) be a vertex of greatest out-degree in a tournament, and let \(v\) be any other vertex. Prove that \(d(u,v) \le 2\).
对于所有 \(v\) 满足 \(u \rightarrow v\) 直接得到。对于其他所有 \(v\) 满足 \(u \leftarrow v\) 若不存在 \(w\) 使得 \(u \rightarrow w \rightarrow v\)，则有 \(v\) 的出度大于 \(u\)，与题设矛盾。
-
\([\mathcal{M23}]\) Let \(G\) be a graph of girth \(g\) in which every vertex has at least \(d\) neighbors. Prove that \(G\) has at least \(N\) vertices, where
\[N= \begin{cases} 1+\sum_{0\le k<t} d(d-1)^k, & \text{if } g=2t+1 \\ 1+(d-1)^t+\sum_{0\le k<t} d(d-1)^k, & \text{if } g=2t+2 \end{cases} \]若 \(g=2t+1\)，设 \(u\) 为 \(G\) 中任意一点，则满足 \(d(u,v)=k(1\le k \le t)\) 的 \(v\) 至少有 \(d(d-1)^{k-1}\) 个。据此即得 \(N=1+\sum_{0\le k <t} d(d-1)^k\)。
若 \(g=2t+2\)，设 \(u\) 为 \(G\) 中任意一点，则满足 \(d(u,v)=k(1\le k \le t)\) 的 \(v\) 至少有 \(d(d-1)^{k-1}\) 个。再取一点 \(u'\) 满足 \(d(u,u')=1\)，则满足 \(d(u,v)=t+1\) 且 \(d(u',v)=t\) 的 \(v\) 至少有 \((d-1)^t\) 个。据此即得 \(N=1+(d-1)^t+\sum_{0\le k<t} d(d-1)^k\)。
-
\([\mathcal{M21}]\) Continuing exercise 63, show that there’s a unique graph of girth \(4\), minimum degree \(d\), and order \(2d\), for each \(d \ge 2\).
\(N=2d\) 即为 63 中的下界，为此，每个点的度必须恰好为 \(d\)。即得唯一解为 \(K_{d,d}\)。
-
\([\mathcal{HM31}]\) Suppose graph \(G\) has girth \(5\), minimum degree \(d\), and \(N = d^2+ 1\) vertices.
(a) Prove that the adjacency matrix \(A\) of \(G\) satisfies the equation \(A^2+A = (d−1)I+J\).
利用 63 中的下界，\(G\) 中每个点度数均为 \(d\)，对于任意 \(u\ne v\)，恰有一条路径长度 \(\le 2\)。所以 \(A^2+A = (d−1)I+J\) 成立。
(b) Since \(A\) is a symmetric matrix, it has \(N\) orthogonal eigenvectors \(x_j\) , with corresponding eigenvalues \(\lambda_j\) , such that \(Ax_j = \lambda_jx_j\) for \(1 \le j \le N\). Prove that each \(\lambda_j\) is either \(d\) or \((-1 \pm \sqrt{4d-3})/2\).
特征值 \(\lambda_1=d\) 对应特征向量 \(x_1=(1,\ldots,1)^T\)。利用 (a) 中结论 \(A^2+A = (d−1)I+J\)，得到对于 \(2\le j \le N\)，\((\lambda_j^2+\lambda_j-d+1)x_j=Jx_j\)，注意到这意味着 \(Jx_j=(0,\ldots,0)^T\)，所以 \(\lambda_j^2+\lambda_j-d+1=0\)，明所欲证。
(c) Show that if \(\sqrt{4d − 3}\) is irrational, then \(d = 2\).
注意到 \(\sum_{i=1}^N \lambda_i=\operatorname{trace} A=0\)，设特征值 \(\lambda=(-1 - \sqrt{4d-3})/2\) 为 \(m\) 重，则有 \(\lambda=(-1 + \sqrt{4d-3})/2\) 为 \(N-m-1\) 重。利用 \(\sqrt{4d − 3}\) 为无理数的性质，得到 \(m=N-m-1\)，即 \(m=d^2/2\)。所以 \(d-d^2/2=0\)，据此 \(d=2\) 成立。
(d) And if \(\sqrt{4d − 3}\) is rational, \(d \in \{3, 7, 57\}\).
做 (c) 中相同假设，得到 \(\sum_{i=1}^N \lambda_i\) 为
\[\frac{15}{32} + \frac{s}{32} (9 - 32m + s (2 + s (6 + s(-1 + s)))) \]这给出 \(s\) 为 \(15\) 的约数，明所欲证。
-
\([\mathcal{M25}]\) Find all connected graphs \(G\) and \(H\) such that \(G\Box H \cong G \otimes H\).
分析度数最大和最小的点，得到 \(d_u+d_v=d_ud_v\)，所以要么 \(G=H=K_1\)，要么 \(G=C_n,H=C_m\)。
显然 \(G\Box H\) 是联通的，所以 \(G,H\) 不全为二分图。所以 \(G\Box H\) 不为二分图，所以 \(G,H\) 均不为二分图。这意味着 \(n,m\) 均为奇数。
分析最小奇环长，\(C_n\Box C_m\) 的最小奇环长为 \(\min(n,m)\)，\(C_n\otimes C_m\) 的最小奇环长至少为 \(\max(n,m)\)，这意味着 \(n=m\)。
同时 \(C_n\Box C_n \cong C_n \otimes C_n\) 确实成立，仅需映 \(C_n\Box C_n\) 中的 \((x,y)(0\le x,y<n)\) 至 \(C_n\otimes C_n\) 中的 \(((x+y)\bmod n,(x-y)\bmod n)\) 即可。
-
\([\mathcal{M25}]\) Let \(A\) be any matrix with \(m > 1\) distinct rows, and \(n \ge m\) columns. Prove that at least one column of \(A\) can be deleted, without making any two rows equal.
考虑反证法，若不存在这样的列，则得到存在至少两个完全相同的行，矛盾。