已知正整数 $n,k$，对于一个 $n$ 顶点的树 $T$，标记它的顶点为 $1,2\cdots,n$ 序列 $(a_1,a_2,\cdots,a_k),1\leqslant a_i\leqslant n,1\leqslant i\leqslant k$．若 $a_i$ 与 $a_{i+1}(1\leqslant i\leqslant k-1')$ 在 $T$ 中相连，则可交换 $a_i$ 与 $a_{i+1}$ 称交换前后的两个序列为等价的，若两个序列可以通过若干步操作得到，称它们是等价的，记 $f(T)$ 为序列中等价类的个数，求 $f(T)$ 的可能值．
【难度】
【出处】
2019北大数学科学夏令营
【标注】
【答案】
略
【解析】
若 $n = 2$，则 $ f(T)$ 的所有可能值为 $k + 1$．若 $n > 2$，$f(T)$ 的所有可能值为 $\dfrac{(n−1)^(k+1)−1}{n-2}$．
对于正整数 $ m$．假设所有长度为 $m$ 的等价类构成的集合为 $A_m$，设 $|A_m| = t_m$．
设 $X_i$ 为所有 $i$ 开头的长度为 $ m + 1$ 序列的等价类构成的集合 $(1 \leqslant
i \leqslant n)$．
对于任意两个长度为 $m$ 的序列，$a =(a_1,\cdots,a_m),b =(b_1,\cdots,b_m)$．
若有 $a$ 与 $b$ 等价，则一定有 $(i,a_1,\cdots,a_m)$ 与 $(i,b_1,\cdots,b_m)$ 等价．
若 $(i,a_1,\cdots,a_m)$ 与 $(i,b_1,\cdots,b_m)$ 等价，我们下面证明 $a$ 与 $ b$ 等价．
考虑将 $(i,a_1,\cdots,a_m)$ 操作到 $(i,b_1,\cdots
,b_m)$ 的操作过程，记作 $ F$．在 $ F$ 中去掉所有交换 $i$ 的操作变为操作过程 $F^\prime$．由于交换 $i$ 和其它元素不改变除 $ i$ 以外的相对顺序．故对序列 $(i,a_1,\cdots,a_m)$ 按 $F^\prime$，操作可始终固定 $ i$ 不动得到 $(i,b_1,\cdots,b_m)$，这告诉我们 $a$ 与 $ b$ 等价．所以两个 $ i(1 \leqslant i \leqslant n)$ 开头的长度为 $m + 1$ 的序列等价当且仅当去掉开头得到的两个长度为 $ m$ 的序列等价．由此我们可用去掉第一个元素的方法得到从 $X_i$ 到 $A_m$ 的双射．
至此，我们证明了 $ |X_i| = t_m$．下面来计算 $|X_i \bigcap X_j|,i \ne j$．
对 $i \ne j$，如果 $X_i$ 中某个元素的代表元 $ c =(c_1,\cdots,c_{m+1})$ 与 $ X_j$ 中某个元素的代表元 $d =(d_1,\cdots,d_{m+1})$ 等价．
考虑 $d_1 $ 在 $ c =(c_1,\cdots,c_{m+1})$ 中的初始位置，它在 $ c_1$ 的后方，经操作后，它变到 $ c_1$ 的前方．
由离散介值原理知存在一次操作交换 $c_1 $ 与 $d_1$，则有 $i,j$ 在 $T$ 中相连．
同理可知，若 $d_1$ 在 $c$ 中的对应项是 $ c_p(p \geqslant 2),c_1$ 在 $d$ 中的对应项是 $d_q(q \geqslant 2)$，则 $d_1$ 与 $ c_1,\cdots,c_{p−1}$ 均有边相连，$c_1$ 与 $d_1,\cdots,d_{q−1}$ 均有边相连．所以可以进行操作，
把 $(c_1,\cdots,c_{m+1})$ 变成 $(c_1,d_1,c_2,\cdots,c_{p−1},c_{p+1},\cdots,c_{m+1})$．
同理可将 $(d_1,\cdots,d_{m+1})$ 变成 $(d_1,c_1,d_2,\cdots,d_{q−1},d_{q+1},\cdots,d_{m+1})$，再交换 $c_1$ 与 $d_1$，
可知 $(c_1,d_1,c_2,\cdots,c_{p−1},c_{p+1},\cdots,c_{m+1})$ 与 $(d_1,c_1,d_2,\cdots,d_{q−1},d_{q+1},\cdots,d_{m+1})$ 等价．
只要 $m \geqslant 2$，就可再去掉开头的两位 $ c_1,d_1$，
可知 $(c_2,\cdots,c_{p−1},c_{p+1},\cdots,c_{m+1})$ 与 $(d_2,\cdots,d_{q−1},d_{q+1},\cdots,d_{m+1})$ 等价．
而对于在 $T$ 中有边的 $ i,j$，可以在 $ A_{m−1 }$ 任意一个等价类的元素可以在前面分别添加 $ i,j$ 和 $ j,i$，可分别得到开头为 $ i,j$ 的两个序列，且它们等价．由此得到 $X_i \bigcap X_j$ 到 $A_{m−1}$ 的一个双射．
至此，我们证明了：若 $m \geqslant 2,i \ne j$，若 $i,j$ 在 $T$ 中相连，则 $|X_i \bigcap X_j| = t_{m−1}$，若 $i,j$ 不在 $T$ 中相连，则 $|X_i \bigcap X_j| = 0$．
对于 $m \geqslant 2$，由于 $T$ 是树，$T$ 中不存在 $3$ 点两两相连，即 $\forall 1 \leqslant i < j < k \leqslant m + 1$，有 $|X_i \bigcap X_j \bigcap X_k| = 0$．由容斥原理，结合树有 $n − 1$ 条边，
$\displaystyle t_{m+1} =|\bigcup\limits_{i=1}^m X_i| = \sum\limits_{i=1}^m|X_i| − \sum_{1\leqslant i<j\leqslant m}|X_i \bigcap X_j| = nt_m −(n − 1)t_{m−1}$
而 $ t_1 = n,t_2 = n^2 − n + 1$，递推可得
$f(T)= t_k= \begin{cases}k + 1&,&若 n =2\\
\dfrac{(n−1)^{k+1}−1}{n-2}& ,&若 n \geqslant 3
\end{cases}$
对于正整数 $ m$．假设所有长度为 $m$ 的等价类构成的集合为 $A_m$，设 $|A_m| = t_m$．
设 $X_i$ 为所有 $i$ 开头的长度为 $ m + 1$ 序列的等价类构成的集合 $(1 \leqslant
i \leqslant n)$．
对于任意两个长度为 $m$ 的序列，$a =(a_1,\cdots,a_m),b =(b_1,\cdots,b_m)$．
若有 $a$ 与 $b$ 等价，则一定有 $(i,a_1,\cdots,a_m)$ 与 $(i,b_1,\cdots,b_m)$ 等价．
若 $(i,a_1,\cdots,a_m)$ 与 $(i,b_1,\cdots,b_m)$ 等价，我们下面证明 $a$ 与 $ b$ 等价．
考虑将 $(i,a_1,\cdots,a_m)$ 操作到 $(i,b_1,\cdots
,b_m)$ 的操作过程，记作 $ F$．在 $ F$ 中去掉所有交换 $i$ 的操作变为操作过程 $F^\prime$．由于交换 $i$ 和其它元素不改变除 $ i$ 以外的相对顺序．故对序列 $(i,a_1,\cdots,a_m)$ 按 $F^\prime$，操作可始终固定 $ i$ 不动得到 $(i,b_1,\cdots,b_m)$，这告诉我们 $a$ 与 $ b$ 等价．所以两个 $ i(1 \leqslant i \leqslant n)$ 开头的长度为 $m + 1$ 的序列等价当且仅当去掉开头得到的两个长度为 $ m$ 的序列等价．由此我们可用去掉第一个元素的方法得到从 $X_i$ 到 $A_m$ 的双射．
至此，我们证明了 $ |X_i| = t_m$．下面来计算 $|X_i \bigcap X_j|,i \ne j$．
对 $i \ne j$，如果 $X_i$ 中某个元素的代表元 $ c =(c_1,\cdots,c_{m+1})$ 与 $ X_j$ 中某个元素的代表元 $d =(d_1,\cdots,d_{m+1})$ 等价．
考虑 $d_1 $ 在 $ c =(c_1,\cdots,c_{m+1})$ 中的初始位置，它在 $ c_1$ 的后方，经操作后，它变到 $ c_1$ 的前方．
由离散介值原理知存在一次操作交换 $c_1 $ 与 $d_1$，则有 $i,j$ 在 $T$ 中相连．
同理可知，若 $d_1$ 在 $c$ 中的对应项是 $ c_p(p \geqslant 2),c_1$ 在 $d$ 中的对应项是 $d_q(q \geqslant 2)$，则 $d_1$ 与 $ c_1,\cdots,c_{p−1}$ 均有边相连，$c_1$ 与 $d_1,\cdots,d_{q−1}$ 均有边相连．所以可以进行操作，
把 $(c_1,\cdots,c_{m+1})$ 变成 $(c_1,d_1,c_2,\cdots,c_{p−1},c_{p+1},\cdots,c_{m+1})$．
同理可将 $(d_1,\cdots,d_{m+1})$ 变成 $(d_1,c_1,d_2,\cdots,d_{q−1},d_{q+1},\cdots,d_{m+1})$，再交换 $c_1$ 与 $d_1$，
可知 $(c_1,d_1,c_2,\cdots,c_{p−1},c_{p+1},\cdots,c_{m+1})$ 与 $(d_1,c_1,d_2,\cdots,d_{q−1},d_{q+1},\cdots,d_{m+1})$ 等价．
只要 $m \geqslant 2$，就可再去掉开头的两位 $ c_1,d_1$，
可知 $(c_2,\cdots,c_{p−1},c_{p+1},\cdots,c_{m+1})$ 与 $(d_2,\cdots,d_{q−1},d_{q+1},\cdots,d_{m+1})$ 等价．
而对于在 $T$ 中有边的 $ i,j$，可以在 $ A_{m−1 }$ 任意一个等价类的元素可以在前面分别添加 $ i,j$ 和 $ j,i$，可分别得到开头为 $ i,j$ 的两个序列，且它们等价．由此得到 $X_i \bigcap X_j$ 到 $A_{m−1}$ 的一个双射．
至此，我们证明了：若 $m \geqslant 2,i \ne j$，若 $i,j$ 在 $T$ 中相连，则 $|X_i \bigcap X_j| = t_{m−1}$，若 $i,j$ 不在 $T$ 中相连，则 $|X_i \bigcap X_j| = 0$．
对于 $m \geqslant 2$，由于 $T$ 是树，$T$ 中不存在 $3$ 点两两相连，即 $\forall 1 \leqslant i < j < k \leqslant m + 1$，有 $|X_i \bigcap X_j \bigcap X_k| = 0$．由容斥原理，结合树有 $n − 1$ 条边，
$\displaystyle t_{m+1} =|\bigcup\limits_{i=1}^m X_i| = \sum\limits_{i=1}^m|X_i| − \sum_{1\leqslant i<j\leqslant m}|X_i \bigcap X_j| = nt_m −(n − 1)t_{m−1}$
而 $ t_1 = n,t_2 = n^2 − n + 1$，递推可得
$f(T)= t_k= \begin{cases}k + 1&,&若 n =2\\
\dfrac{(n−1)^{k+1}−1}{n-2}& ,&若 n \geqslant 3
\end{cases}$
答案
解析
备注
