|
|
Riffle shuffle permutation| $n$ 元集的 riffle shuffle 是将$n$个元素分成两组然后将两组交错放置(interleave)。例如，每次从一组底部或另一组底部抽出一个元素移动到已排序元素的顶部。 |
|
riffle shuffle 排列是可以经过一次riffle shuffle得到的排列。从一个上升序列开始，$n$ 元有序集的riffle shuffle排列是可分为 2 个上升序列的排列。特别地，对于非负整数 $p$ 和 $q$ 且 $p + q = n$ 的 $(p,q)$-shuffle 是一个 riffle shuffle，其中第一组有 $p$ 个元素，第二组有 $q$ 个元素。由于 $(p,q)$-shuffle 完全由第一组 $p$ 个元素的位置决定，因此 $(p,q)$-shuffle 的数量是
\[\binom{p+q}p\]
然而，不同的 riffle 的数量并不完全是这个公式对所有满足$p+q=n$的非负整数 $p,q$的总和（这将是 $2^n$），因为 恒等排列 可以 对于 $p$ 和 $q$ 的不同值，以$n+1$种方式表示为 $(p,q)$-shuffle，所以需要减去$n$。因此$n$个元素的不同 riffle shuffle 排列的数量是 $2^n-n$。
1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, ...
例如，一副 52 张牌的牌有 4503599627370444 种riffle shuffle排列。
既是 riffle shuffle 排列又是 riffle shuffle 逆排列的排列数是
\[\binom {n+1}{3}+1\]
For $n = 1 , 2 , 3 , …$, this is
1, 2, 5, 11, 21, 36, 57, 85, 121, 166, 221, ...
and for $n = 52$ there are exactly 23427 invertible shuffles. |
|
