意味
レーマー コードは、デリック レーマーのものとされていますが、少なくとも 1888 年から知られており、次の要素を関連付けています。
$$ {\scriptstyle\ [\![1,n]\!]\ } $$
で定義されたアプリケーション
ƒ=L(σ) $$ {\scriptstyle\ [\![1,n]\!]\ } $$
による
$$ {f(i)=\text{Card}\left\{j\ |\ 1\le j\le i\text{ et }\sigma(j)\le\sigma(i)\right\}=L(\sigma,i).} $$
アプリケーションƒ 、エンコード順列
$$ {\scriptstyle\ \mathfrak{S}_n,\ } $$
結果として特定できる
$$ {\scriptstyle\ \left(f(i)\right)_{1\le i\le n}.\ } $$
として
$$ {1\le f(i)\le i,} $$
レーマー コードは、集合間の対応関係Lを確立します。
$$ {\scriptstyle\ \mathfrak{S}_n\ } $$
そしてデカルト積
$$ {[\![1,1]\!]\times[\![1,2]\!]\times[\![1,3]\!]\times\dots\times[\![1,n]\!].} $$
組み合わせ論と確率への応用
相対的なランクの独立性
これらのアプリケーションは、整数のシーケンスとして見られるレーマー コードL(σ)の即時特性から生じます。
財産—に関する統一法に基づく
$$ {\scriptstyle\ \mathfrak{S}_n,\ } $$
L は独立した一様変数のシーケンスです。
L(i) は次の統一法則に従います。
$$ {\scriptstyle\ [\![1,i]\!]\ } $$
。
言い換えれば、ランダムに順列ω を描画すると、
$$ {\scriptstyle\ \mathfrak{S}_n,\ } $$
等確率 (各順列が選択される確率は
1/n!です) の場合、そのレーマー コード
ƒ=L(ω)=(L(1,ω), L(2,ω), L(3,ω )、 … , L(n,ω)) は、一連の独立した一様確率変数です。
Lの成分の独立性は、デカルト積の一様確率変数に関する一般原則から生じます。
レコード数
定義—シーケンスu=(uk k ) 1≤k≤nでは、 u kが各項u iより厳密に小さい (または厳密に大きい) 場合に、ランクkにレコードが下にあります (または上にあります)。 。
B(k) (またはH(k) ) を「ランクkでダウン (またはアップ) のレコードがある」というイベントとします。つまり、 B(k) は次の順列のセットです。
$$ {\scriptstyle\ \mathfrak{S}_n\ } $$
これはランク
kまでのレコードを示します。私たちは明らかに持っています
$$ {\{\omega\in B(k)\}\Leftrightarrow\{L(k,\omega)=1\}\quad\text{et}\quad\{\omega\in H(k)\}\Leftrightarrow\{L(k,\omega)=k\}.} $$
したがって、順列ωの下向き (または上向き) のレコードの数N b (ω) (特にN h (ω) ) は、それぞれのパラメータ1/kを持つ独立したベルヌーイ変数の合計として書き込まれます。
$$ {N_b(\omega)=\sum_{1\le k\le n}\ 1\!\!1_{B(k)}\quad\text{et}\quad N_b(\omega)=\sum_{1\le k\le n}\ 1\!\!1_{H(k)}.} $$
実際、 L(k) は次の統一法則に従います。
$$ {\scriptstyle\ [\![1,k]\!],\ } $$
$$ {\mathbb{P}(B(k))=\mathbb{P}(L(k)=1)=\mathbb{P}(H(k))=\mathbb{P}(L(k)=k)=\frac1k.} $$
ベルヌーイ変数の母関数
$$ {1\!\!1_{B(k)}} $$
東
$$ {G_k(s)=\frac{k-1+s}k,} $$
したがって、 N bの母関数は次のようになります。
$$ {G(s)=\prod_{k=1}^nG_k(s)\ =\ \frac{(s)_{\uparrow n}}{n!},} $$
これにより、生成される第 1種スターリング数列 (符号なし) の積形式を見つけることが可能になります。
サイクル数
Foata の基本的な対応関係は、 N bの確率法則が、ランダムに抽出された順列の分解のサイクル数の法則でもあるという事実につながります。
秘書問題
これは、決定理論、統計学、応用確率の古典的な最適停止問題であり、レーマー コードの最初の項を通じてランダムな順列が徐々に明らかになり、 σ(kとなるような値kで正確に停止する必要がある) )=nですが、利用可能な唯一の情報 (レーマー コードの最初のk値) ではσ(k)を計算できません。あまり数学的用語ではなく、一連のn人の候補者が次々と採用担当者に提示され、採用担当者は最も優れた人材を採用する必要がありますが、候補者が採用された時点で決定 ( 「合格する」か「採用する」 ) を下さなければなりません。次の候補者を見るのを待たずに（すべての候補者を見ることなく）彼に提示されました。したがって、採用担当者は、すでに見たk 人の候補者のうちk番目に提示された候補者の順位を知っています。したがって、 k番目の決定 ( 「合格する」または「採用する」 ) を行うとき、採用担当者は最初の決定を知っています。レーマー コードのk項を知っている必要がありますが、順列を知る必要があります。採用担当者は、十分な情報に基づいた意思決定を行うために、レーマー コードのすべての項を知っている必要があります。最適な戦略(勝利確率の最適化) を決定するには、レーマー コードの統計的特性が重要です。ヨハネス・ケプラーは、11 人の妻候補の中から2 番目の妻を選ぶことにしたとき、友人に秘書の問題を明確に説明したと言われています (彼は非常に細心の注意を払って選びたかったのですが、彼の最初の結婚は不幸で、彼なしで取り決められたものでした)相談されました）。
