看似复杂的计数题

力工

看似复杂但较简单的。
某人在斗地主时，手中还剩扑克牌 $J、Q、K、A、小王、大王$ 共 6 张乱序排列，此人每次调整其中两张牌的顺序，用五次将手中的牌按从小到大调整成 $J、Q、K、A、小王、大王$ 的顺序，问原来乱序牌的排法有多少种可能？

tommywong

唔識喎...咁樣得唔得㗎？

$\displaystyle \left[{6\atop 5}\right]+\left[{6\atop 3}\right]+\left[{6\atop 1}\right]=15+225+120=360$

en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind

Czhang271828

对二楼的计算以及文献给一个详细一点的补充.

事实 如果调整 $k$ 次可以复原, 那么调整 $k+2$ 次也可以复原. 实际上,
$$
\text{复原数}=\text{最小复原数}+2p\quad (p\in \mathbb N).
$$

证明

一方面, 根据线性代数对置换群的粗浅介绍(逆序数之类的), 复原所需的调整次数的奇偶性是不变的. 另一方面, 两次对换之复合为恒等.

从而我们仅需找到最小调整数 $\in\{1,3,5\}$ 之情形. 此处还得补充一个事实.

事实 任意置换可以唯一地对应不交轮换之复合

证明

一组对象 $(a_i)_{i=1}^n$ 的轮换是指将每个 $a_i$ 移动至 $a_{i+1}$, 其中约定 $a_{n+1}=a_1$. 我们将这一 $n$ 轮换记作 $(1\,2\,3\,\cdots \,n)$.

例如 $(1\,3\,5)$ 在 $(a_1,a_2,a_3,a_4,a_5,a_6)$ 上的作用结果为 $(a_5,a_2,a_1,a_4,a_3,a_6)$.

因此, 我们考察任意置换在对象上的作用, 则每个元素的轨迹会有最小正周期. 归纳可知, 任意置换(在对象上的作用)等价于若干不交轮换的复合(在对象上的作用). 从而任意置换可以唯一地对应不交轮换之复合.

下面开始解答原来的问题: 找到最小调整数 $\in\{1,3,5\}$ 之乱牌数

• 若最少调整数为 $1$, 则对应 $(i\, j)$-型置换: 乱牌种数就是 $\binom{6}{2}=15$.
• 若最少调整数为 $3$, 则对应 $(a\,b)(c\,d)(e\,f)$, $(a\,b\,c)(d\,e)$, $(a\,b\,c\,d)$ 型置换, 乱牌种数共计
     $$
     \dfrac{\binom{6}{2}\binom{4}{2}\binom{2}{2}}{3!}+2!\cdot\binom{6}{3}\binom{3}{2}\binom{1}{1}+\dfrac{3!\binom{6}{4}\binom{2}{1}\binom{1}{1}}{2!}=225.
     $$
• 若最少调整数为 $3$, 则对应 $(a\,b\,c\,d\,e\,f)$ 型置换, 乱牌综述共计
     $$
     5!\cdot \binom{6}{6}=120.
     $$

综上, 共计 $435$ 种. 若将以上运算归纳一下, 结果就是第一类 Stirling 数.

再来个看似复杂问题: 如果原题中 '对换任意两张牌' 改作 '对换左右相邻的两张牌' 呢? 我觉得是 $105$ 种.

Czhang271828

Czhang271828 发表于 2023-6-3 19:34
再来个看似复杂问题: 如果原题中 '对换任意两张牌' 改作 '对换左右相邻的两张牌' 呢? 我觉得是 $105$ 种.

公布一下解答. 这显然就是 $\displaystyle\prod_{k=1}^6\dfrac{q^k-1}{q-1}$ 中 $1$, $3$, $5$ 次项系数和.

对 $n$ 张乱牌的对应的排列 $w$, 记 $\ell(w)$ 为 '仅通过对换相邻牌复原' 的最小次数, $c_{\ell_0}$ 为 $\{w\mid \ell(w)=\ell_0\}$ 大小, 则
\[
\sum_{k\geq 0}c_kq^k=\prod_{l=1}^n\dfrac{q^l-1}{q-1}.
\]

力工

请教原题是否可以构造计数呢？