MathLabs

第5题

给定序列 0,1,…,n0, 1, \ldots, n 的一个排列 (a0,a1,…,an)(a_0, a_1, \ldots, a_n)。如果对 i>0i > 0 有 ai=0a_i = 0，且 ai−1+1=aja_{i-1} + 1 = a_j，则将 aia_i 与 aja_j 的对换称为合法的。如果排列 (a0,a1,…,an)(a_0, a_1, \ldots, a_n) 经过若干次合法对换后变为 (1,2,…,n,0)(1, 2, \ldots, n, 0)，则称该排列是正则的。问对哪些正整数 nn，排列 (1,n,n−1,…,3,2,0)(1, n, n-1, \ldots, 3, 2, 0) 是正则的？
第 3/5 步：定义分块构型 PrP_r 并在 nn 为奇数时到达 P1P_1
上一步下一步
通俗地说

当 nn 为奇数时，第一轮左移一直跳到 a1=na_1 = n，把每个偶数与紧邻其上的奇数配成长度为 22 的有序块。

Pr=[1:R−1],(0),[N−R:N−1],[N−2R:N−R−1],…,[2R:3R−1],[R:2R−1](R=2r, N=n+1)P_r = [1 : R-1], (0), [N-R : N-1], [N-2R : N-R-1], \ldots, [2R : 3R-1], [R : 2R-1] \quad (R = 2^r,\ N = n+1)
详细分析

对奇数 n≥3n \ge 3，记 N=n+1N = n + 1，R=2rR = 2^r，并用 [a:b]=(a,a+1,…,b)[a : b] = (a, a+1, \ldots, b) 表示连续递增块。设 P0P_0 为初始排列，当 2R∣N2R \mid N 时定义 PrP_r 为 [1:R−1],(0),[N−R:N−1],[N−2R:N−R−1],…,[2R:3R−1],[R:2R−1][1 : R-1], (0), [N-R : N-1], [N-2R : N-R-1], \ldots, [2R : 3R-1], [R : 2R-1]。从 P0P_0 出发的第一轮中，由于 nn 是奇数，00 依次与 3,5,…,n3, 5, \ldots, n 交换，最终停在 11 右侧的下标 11 处，并将其余元素配成二元块 [N−2:N−1],[N−4:N−3],…,[2:3][N-2 : N-1], [N-4 : N-3], \ldots, [2 : 3]，这恰好就是 P1P_1。