逆序对
在计算机科学和离散数学中，一个序列的逆序（inversion）对，是失去自然次序的元素对。 定義 逆序 設\ \pi \ 為一個排列，如果\ i 而且 \ \pi(i) > \pi(j) \ ， 這個位置（有称为“序位”）对 \ (i, j) \ ，或者這个元素对 \ \bigl(\pi(i), \pi(j)\bigr) \ ，被稱為是 \ \pi \ 的一個逆序。 逆序集是所有逆序的集合。一個排列 \ \pi \ 的使用基于位置表示法…
标签：#置换
共 18 篇文章
排列
{{Forceconvert|-{zh-cn:;zh-tw:;}-}} 排列又称置換，是將相異物件或符號根據確定的順序重排，得到的每個順序都稱作一個-{zh-cn:排列; zh-hk:排列; zh-tw:排列或置換;}-。例如，從1到6的數字有720種排列，對應於由這些數字組成的所有不重複亦不闕漏的序列，例如“4, 5, 6, 1, 2, 3”與“1, 3, 5, 2, 4, 6”。 排列的廣義概念在不同語境下有不同的形式定義： 在集合…
约瑟夫斯问题
約瑟夫斯置換是一個出現在計算機科學和數學中的問題。在計算機編程的算法中，類似問題又被稱為約瑟夫環。 人們站在一个等待被處決的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，處刑下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。 问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。 历史 这个问题是以-{zh-hant…
斯特林数
在數學中，史特靈數用於解決各種數學分析和組合數學問題，史特靈數是兩組不同的數，均是18世紀由引入並以其命名，以'和'的稱呼區分。此外，有時候也將'稱爲第三類史特靈數。 第一類史特靈數 定義 '可以定義爲對應遞降階乘展開式的各項係數，即 (x)_n=\sum^{n}_{k=0}s(n,k)x^k\, 其中，s(n,k)\,（0\leq k\leq n\,）即爲第一類史特靈數。例如： :(x)_3=x(x-1)(x-2)\, 則 :(x)_…
列維-奇維塔符號
列維-奇維塔符號（），又稱列維-奇維塔ε，為一在線性代數，張量分析和微分幾何等數學範疇中常見到的符號。對於正整數 ，它以 所形成排列的奇偶性來定義。它以義大利數學家和物理學家图利奥·列维-齐维塔命名。其他名稱包括排列符號、反對稱符號與交替符號。這些名稱與它排列和反對稱的性質有關。 列維-奇維塔符號的標準記號是希臘小寫字母 或 ，較不常見的也有以拉丁文小寫 記號。下標符能與張量分析兼容的方式來顯示排列： :\varepsilon_{a_1…
超排列
在组合数学中，n个符号的超排列（）是一个字符串，使得n个符号的所有排列均为它的子串。这些子串可以互相重叠。对于任意一个指定的n，超排列的长度存在一个最小值，最短的超排列称为最小超排列。 在1≤n≤5时，n个符号的最小超排列的长度是1!+2!+...+n!，分别是1、3、9、33和153，与之对应的字符串分别是1、121、123121321、123412314231243121342132413214321，以及： 12345123415…
对称函数环
代数组合学中，对称函数环是n趋近于无穷大时，n元对称多项式环的特定极限。此环是一种通用结构，其中对称多项式间的关系可用一种与n无关的方式表达（但其元素不是多项式也不是函数）。此环也在对称群表示论中起着重要作用。 对称函数环可给出余积和双线性形式，使其成为正定自伴分次霍普夫代数，其是交换的也是余交换的。 对称多项式 对称函数研究以对称多项式为基础。多项式环中，在变量的某有限集中，若变量的顺序不会影响多项式的值，则称多项式是对称的。更形式地…
顺序统计量
在统计学中，样本的第k顺序统计量（）即它从小到大排列时的第k个值，常用于非参数估计与推断中。常见的顺序统计量包括样本的最大值、最小值、中位数等。 记号 任给样本x_1, x_2, \cdots, x_n，将其从小到大排成一列，记为：x_{(1)}, x_{(2)}, \cdots, x_{(n)}.则其第一顺序统计量（即最小值）为x_{(1)}，第n顺序统计量（即最大值）为x_{(n)}。 概率 随机变量X_{(k)}的累积分布函数F_…
百囚問題
百囚問題（）是一個概率论和组合数学中的数学問題。在這個問題中，100名有編號的囚犯必須在100個抽屜中找到各自的號碼才能生存下來。規則規定，每位囚犯只能開啟50個抽屜，且不能與其他囚犯溝通。乍看之下，這種情況似乎無望，但一個巧妙的策略為囚犯們提供了一個現實的生存機會。 丹麥計算機科學家Peter Bro Miltersen於2003年首次提出了這個問題。 問題 百囚問題在文獻中有不同的呈現版本。以下版本是由和罗伯特·塞奇威克提出的： :…
循环数
循环数（），是一类特殊的整数，其包含的各个数字的循环排列恰为该数的连续倍数 ; 一個n位的循环数的性質是它乘以1至n都是各个数字的循环排列 , 乘以(n+1)會出現純位數 , 純位數每個位都是9。例如，最知名的循环数是142857： :142857 × 1 = 142857 :142857 × 2 = 285714 :142857 × 3 = 428571 :142857 × 4 = 571428 :142857 × 5 = 71428…
错排问题
错排问题是组合数学中的问题之一。考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D_n或!n。 研究一个排列错排个数的问题，叫做错排问题或称为更列问题。 最早研究错排问题的是尼古拉·伯努利和欧拉，因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本，如在写信时将n封信装到n个不同的信封里，有多少种全部装错信封的情况？又比如四人各写一张贺…
黎曼级数定理
黎曼级数定理（亦称黎曼重排定理），是一个有关於无穷级数性质的数学定理，得名于19世纪德国著名数学家波恩哈德·黎曼。黎曼级数定理说明，如果一个实数项无穷级数若是条件收敛的，它的项在重新排列後，重新排列後的级数收敛的值可以收斂到任何一个给定的值，甚至发散。 许多有限项级数具有的性質，在一般的无穷级数不一定滿足，例如一般的有限项级数可以重新排列各項，其級數和不會改變，但在无穷级数中，只有绝对收敛的无穷级数才可以重新排列各項而不改變收斂值。 相…
置换矩阵
在数学中的矩阵论裡，置换矩阵（）是一种系数只由0和1组成的方块矩阵。置换矩阵的每一行和每一列都恰好有一个1，其余元素都是0。在线性代数中，每个n阶的置换矩阵都代表了一个对n个元素（n维空间的基）的置换。当一个矩阵乘上一个置换矩阵时，所得到的是原来矩阵的横行（置换矩阵在左）或纵列（置换矩阵在右）经过置换后得到的矩阵。 严格定义 每个n元置换都对应着唯一的一个置换矩阵。设π 为一个n元置换： :\pi : \lbrace 1, \ldots…
凱萊定理
在群論中，凱萊定理（）聲稱所有群 G 都與在 G 上的對稱群 S_G 的一個子群同構。這代表我們可以將 G 的群運算視為在 G 的元素上的群作用。該定理以英國數學家阿瑟·凱萊命名。 集合 G 的置換是任何從 G 到 G 的雙射函數。由所有置合構成集合與函數複合共同構成了一個群，稱為「 G 上的對稱群」，并記為 \text{Sym}(G)。 凱萊定理通過把任何群（包括無限群，如 (\mathbb{R}, +)）都當作某個底層集合的置換群，…
卡塔兰数
《割圜密率捷法》卷三 “卡塔兰数”书影]] 卡塔兰数（）是組合數學中一個常在各種計數問題中出現的數列，以比利時數學家欧仁·夏尔·卡塔兰命名。历史上，清朝数学家明安图在其《割圜密率捷法》中最先发明这种计数方式，早于卡塔兰。有中国学者建议将此数命名为“明安图数”或“明安图-卡塔兰数”。 卡塔兰数的一般項公式為 C_n = \frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{(n+1)!n!} 第0項到第19…
P盒
在密碼學中，一個P盒（Permutation-box，置換盒）是一個透過置換和轉置將替換盒（S-boxes）輸入進行位元洗牌的方法，在轉置的過程中保持一定程度的擴散。 塊密碼大量使用S盒和P盒來使明文和密文之間的關係難以被看懂——參考夏農的混淆與擴散理論。置換盒通常分為三類： 壓縮性的——輸出位元數比輸入少 擴張性的——輸出位元數比輸入多 平直性的——輸出位元數等於輸入位元數 其中只有平直性的置換盒是可逆的。 相關條目 S盒 替換式密碼…
曼特尔检验
曼特尔检验（Mantel test）是一种验证两个矩阵的相关性的统计检验方法，由美国统计学家于1967年提出。 参考来源 外部链接 *[http://www.nceas.ucsb.edu/files/scicomp/doc/SpatialEcologyMantelTest.pdf The Mantel test in ecology]
置换的奇偶性
Permutations of 4 elements Odd permutations have a green or orange background. The numbers in the right column are the inversion numbers , which have the same parity as the permutation.]] 在数学中，当X是一个至少有两个元素的有限集合时，X的置换（即从X…