数列变换

realnumber

已知$N$为偶数,给定数列$a_1,a_2,\cdots ,a_N$,记为$A_0$,对$A_0$作如下变换:
  ①将$A_0$中的奇数项取出,按原顺序构成新数列的前$\frac{N}{2}$项;
  ②将$A_0$中的偶数项取出,按原顺序构成新数列的第$\frac{N}{2}+1$项到第$N$项.
称上述操作为$T$变换,构成的新数列为$A_1$,记$A_1=T(A_0)$,定义$A_k$为操作$k$次后得到的新数列,即
$A_k=T(A_{k-1})=T^k(A_0),k=1,2,\cdots ,$其中$A_k(i)$表示数列$A_k$中的第$i$项.
(1)若$a_n=n,(n=1,2,\cdots ,8)$,求$A_1(2),A_2(2),A_3(2)$;
(2)令$N=2^m(m\in N^*)$,其中数列$A_0$的各项互不相同,记$C_i=\{{ A_k(i)│k\in N^* \}}$,规定$│C_i│$为集合$C_i$的元素个数;
(i)求$│C_2│$
(ii)求不超过10的最大正整数$m$,满足$│C_2│=│C_3│=\cdots =│C_{2^m-1}│$.

最后一问小伙得到的更一般结论是,$m$是素数,就是"满足$│C_2│=│C_3│=\cdots =│C_{2^m-1}│$"的充要条件,做得有些麻烦,想确认一下,以及有没简单的做法.而我还没头绪,得慢慢想.

kuing

挺有趣的题，我先写一点我的理解（未涉及具体证明，旨在引起大家的兴趣（所以我还会加些图😁））。

我更喜欢将原题的 `T` 逆向操作，即：`\{a_1,a_2,\dots,a_{2k}\}\to\{a_1,a_{k+1},a_2,a_{k+2},\dots,a_k,a_{2k}\}`。

这对第二问来说显然是没区别的，而这样就可以很形象地称其为“完美洗牌”。

（更准确说，是外洗法的完美洗牌，引用这里的图：

中间的那种就是外洗法，这种洗法头尾两张牌始终不动）

`\abs{C_i}` 指的就是洗牌过程中，排在第 `i` 位的出现过几张不同的牌。

由于洗牌方式固定，而牌的排列有限，洗牌次数足够多肯定会还原，因此每个位置出现的牌必构成循环。

举个例子，对于标记为 1~16 的牌，用置换群的写法，就是
\[\sigma = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\
1 & 9 & 2 & 10 & 3 & 11 & 4 & 12 & 5 & 13 & 6 & 14 & 7 & 15 & 8 & 16
\end{pmatrix},\]
它就可以写成
\[(1)(2,9,5,3)(4,10,13,7)(6,11)(8,12,14,15)(16),\]
也就是洗四次牌就还原，且 2、9、5、3 这四张牌构成一个循环组，其他类似。
而这就不满足最后一问的 `\abs{C_2}=\abs{C_3}=\cdots=\abs{C_{15}}`，因为 6、11 这两张牌是对换的，与其他的不同。

问题就是求所有的 `2^m` 张牌，使得置换群除头尾外的所有循环节长度都相等，而楼主小伙得出充要条件是 `m` 为素数。

我暂时不会，反正这题其实不是数列题，大概是数论或者群论……😳

kuing

@hbghlyj 你能不能找到相关资源，数论/群论我不熟🥺

hbghlyj

kuing 发表于 2025-3-18 14:05
$\{a_1,a_2,\dots,a_{2k}\}\to\{a_1,a_{k+1},a_2,a_{k+2},\dots,a_k,a_{2k}\}$

去除末尾的$a_{2k}$得$$\{a_1,a_2,\dots,a_{2k-1}\}\to\{a_1,a_{k+1},a_2,a_{k+2},\dots,a_k\}$$
将$\{a_1,a_2,\dots,a_{2k-1}\}$的位置记为$\{0,1,\dots,2k-2\}$得，第$i$个元素移到第$2i\bmod 2k-1$个元素
即，模 $2k-1$ 下的乘 2 运算

hbghlyj

kuing 发表于 2025-3-18 14:05
求所有的 `2^m` 张牌，使得置换群除头尾外的所有循环节长度都相等，而楼主小伙得出充要条件是 `m` 为素数。

$\forall i\in\{0,1,\dots,2^m-2\},$第 $i$ 个元素所在的循环长度为$$l=\min\{l\inN_+:2^m-1\mid i(2^l-1)\}$$
当 $i=1$ 时显然 $l=m$.
于是，“对所有$i$循环长度都相等”等价于对所有$i$循环长度都等于$m$.
由结论 $\gcd(2^a - 1, 2^b - 1) = 2^{\gcd(a,b)} - 1,$
$$l=\min\{l\inN_+:\frac{2^m-1}{2^{\gcd(m,l)}-1}\mid i\}$$
若 $m$ 为素数，显然 $i<2^m-1$ 不能 $\gcd(m,l)=1$，只能 $\gcd(m,l)=m$，即 $l=m$.

若 $m$ 为合数，取 $d\mid m,1<d<m,i=\frac{2^m-1}{2^{\gcd(m,d)}-1}$ 则
$$\frac{2^m-1}{2^{\gcd(m,d)}-1}\mid i$$
因此 $l\le d<m$. 证毕

hbghlyj

根据上面，当 $m$ 为素数则循环的长度均为 $m$，所以长度为 $m$ 的循环的个数为 $\frac{2^m-1}m$.
一般地，当 $m$ 为任意正整数，长度为 $m$ 的循环的个数是 A001037，通项为$$\frac1m\sum_{d \mid m} \mu\left(\frac{m}{d}\right)2^d\tag1\label1$$其中 \( \mu \) 是 Möbius 函数。
检验一下，当 $m$ 为素数，上式的值为 $\frac{2^m-1}m$，与已知相符。

---

证明：
对每个因数 $d\mid m$，$i$ 所在的循环长度整除 $d$ 等价于 $2^d i\equiv i\pmod{2^m-1}$
等价于 $2^m-1\mid i(2^d-1)$
等价于 $\frac{2^m-1}{2^d-1}\mid i$
在 $i=0,\dots,2^m-2$ 中，这样的 $i$ 的个数为 $2^d-1$

现在，对每个因数 $d\mid m$我们知道了 $i$ 所在的循环长度整除 $d$ 的 $i$ 的个数，怎么求 $i$ 所在的循环长度等于 $m$ 的 $i$ 的个数呢？用Möbius反演（由容斥原理可证明Möbius反演）
$$\sum_{d \mid m} \mu\left(\frac{m}{d}\right)(2^d-1)=\sum_{d \mid m} \mu\left(\frac{m}{d}\right)2^d$$
因为它们可划分为长度为 $m$ 的循环，将这样的 $i$ 的个数除以 $m$ 就得到长度为 $m$ 的循环的个数\eqref{1}

hbghlyj

同样的方法可计算 \( \mathrm{GF}(2^m)\) 中不属于任何真子域 \( \mathrm{GF}(2^d) \) 的元素，其中 \( d \mid m \) 为因数。这些元素对应于 \( \mathrm{GF}(2) \) 上次数为 \( m \) 的不可约多项式的根。每个不可约多项式有 \( m \) 个不同的根，因此除以 \( m \) 得到这样的多项式的数量
\[
\frac{1}{m} \sum_{d \mid m} \mu\left(\frac{m}{d}\right) 2^d
\]