和所有的人交朋友

realnumber

1.n个互不认识的学生,围坐在一个圆桌边(初始算1次),假设每人可以和相邻的认识,试着重新把所有的座位重新安排一次,又可以使得相邻的互相认识,问最少重新安排座位几次,使得所有人都互相认识.
比如n=2,3,就一次
n=4,5就2次
n=6,7就3次




2.n个人排成一排(记住相邻的人),若重新排成一排,要求每个人都与之前的人不相邻,问有几种排法?(n>3)

Czhang271828

第一问: 即, 如何用数量最少的大小为 $n$ 的回路 $C_n$ 覆盖完全图 $K_n$.

那么 $n=2k+1$ 为奇数时, $K_n$ 的 Hamiltonian decomposition 是熟知的. 换言之, $K_{2k+1}$ 能被分作 $k$ 个 $C_{2k+1}$ 的并, 使得每条边仅被一个 $C_{2k+1}$ 覆盖.

构造如下: 先用长度为 $2k$ 的路覆盖 $K_{2k}$, 见MSE 现成的图. 然后借用 $K_{n}$ 中没用上的那个顶点将刚才的路变成回路, 见Wiki 英文页现成的图.

所以对 $n=2k+1$, 答案是至少需要 $k$ 次就坐.

对 $n=2k$, 可以证明至少需要 $k$ 次就坐, 由于 $k$ 对 $n=2k+1$ 成立, 那自然对 $n=2k$ 成立.

Czhang271828

第二个问题是在 $P_n$ 的补图中找 $P_n$ 的数量 (区分首尾). 写了一个 sage 算法.

展开代码.

1. from sage.all import *
3. # 定義函數, 以計數 $\overline {P_n}$ 中的 $P_n$.
4. def count_pn_subgraphs_complement(n):
5. # 創建 $P_n$ 圖.
6. P_n = graphs.PathGraph(n)
8. # 獲取 $P_n$ 之補圖 $\overline{P_n}$.
9. complement_P_n = P_n.complement()
11. # 於 $\overline{P_n}$ 中查尋一切之 $P_n$-子圖.
12. subgraphs = list(complement_P_n.subgraph_search_iterator(P_n, induced=False))
14. # 計數以上尋得之 $P_n$-子圖.
15. subgraph_count = len(subgraphs)
17. # 返回.
18. return subgraph_count
20. # 依次輸出 $4\leq n < 10$ 時之答案.
21. for n in range(4,10):
22. print("n = ",n,"時, 結果爲",count_pn_subgraphs_complement(n),";")
23. # 演算法運行完畢.
24. print("運行完畢.")

复制代码

粘贴至如下窗口即可运行:

在 OEIS 上搜索, 得到 A002464. 该数列从 $a_0$ 开始, $a_n$ ($n\geq 4$) 是第二题的结果. 后面的渐进是 $a_n\approx \frac{n!}{e^2}\cdot (1 - \frac{2}{n^2} - \frac{10}{3n^3} + O(n^{-4}) )$.

Jelly (省字版)

Try it online!

Czhang271828

Czhang271828 发表于 2024-7-8 15:00
第二个问题是在 $P_n$ 的补图中找 $P_n$ 的数量 (区分首尾). 写了一个 sage 算法.

在 OEIS 上搜索, 得到 A ...

第二个问题的生成函数计算如下.

注: 我们区分队伍与其倒序. 往后将长为 $j$ 的队伍视作数组 $(1,2,\ldots, j)$​, 并将置换
$$
(1,2,3,\ldots, n)\mapsto (\sigma_1,\sigma_2,\sigma_3\ldots, \sigma_n)\quad [n]\xleftrightarrow[\sigma]{\text{双射}} [n]
$$
简化地记作 $(\sigma_1,\sigma_2,\sigma_3\ldots, \sigma_n)$.

继而定义一些名词:

• (置换的区段划分) 记 $\sigma_i\mid \sigma_{i+1}$, 若两者不相邻, 例如 $(3,2,4,5,1)$ 可以合法地划分作 $(3,2\mid 4,5\mid 1)$ 或者 $(3\mid 2\mid 4,5\mid 1)$, 但不能划分作 $(1,3\mid 5,4\mid 2)$. 等价的规则是其逆否命题: 接连出现的数字必须用逗号而非杠隔开.
  
• (段数) 置换的段数也就是 $\mid$ 的数量 $+1$.
  

$n$ 元置换中, 段数为 $m$ 的置换有几个? 改变问题表述: $m$ 段置换能生成几种 $n$ 元置换? $m$ 段 $n$​ 元置换数是
$$
m!\cdot (x+2x^2+2x^3+2x^4+\cdots )^m
$$
中 $x^n$​ 项的系数. 证明很简单, 先忘却数字只看分段, 那么通过隔板法知生成函数为
$$
(x+x^2+x^3+x^4+\cdots )^m
$$

• 考虑数字, 则系数需要乘上 $m$ 个数字的全排列 $m!$.
• 之所以给长度 $\geq 2$ 的置换加上 $2\cdot(-)$, 是因为 $(a,b)$ 与 $(b,a)$​ 不一样.
  

综上, 记 $n$ 元 $m$ 段置换的数量为 $a_{m,n}$, 则
$$
m!\cdot (x+2x^2+2x^3+2x^4+\cdots )^m=\sum_{n\geq 0}a_{m,n} x^n.
$$
此时生成函数 $\sum_{n\geq m\geq 1}a_{m,n}x^ny^m$​ 等于
$$
f(x,y)=\sum_{m\geq 0}m!(x+2x^2+2x^3+\cdots )^my^m=\sum _{m\geq 0}m!\left(\frac{1+x}{1-x}\right)^m(xy)^m.
$$
我们需要挑出那些没有将继数的分段置换. 对于有相继数的分段置换全体, 定义双射为改变最后一对相继数的 $\{(-,-),(-\mid- )\}$ 状态, 例如
$$
(2\mid 4,5,6\mid 3\mid 1)\to (2\mid 4,5\mid 6\mid 3\mid 1).
$$
这一双射对应也改变了段数的奇偶性. 从而 $f(x,-1)$ 消去了关于 $m<n$-段的计数, 该一元多项式的第 $n$ 项系数的绝对值就是答案. 消去绝对值的函数是
$$
f(-x,-1)=\sum _{m\geq 0}m!\left(\frac{x-x^2}{1+x}\right)^m
$$
收敛半径是 $0$, 从而只能是形式幂级数. 以上也可以写作
$$
\cfrac{x+1}{{1+x^2}- \cfrac{(x(x-1))^2}{{1-2x+3x^2} - \cfrac{(2x(x-1))^2}{{1-4x+5x^2} - \cfrac{(3x(x-1))^2}{1-6x+7x^2 - \cfrac{(4x(x-1))^2}{{1-8x+9x^2} - \cdots}}}}}.
$$
最后尝试把求出的 $g(x)$ 代入形式微分方程, 得递推式
$$
a_n=(n+1)a_{n-1} - (n-2)a_{n-2} - (n-5)a_{n-3} + (n-3)a_{n-4}.
$$