組合せ論(数学の一部)の概念
数学の 組合せ論 の分野 において 、 q ポッホハマー記号は q シフト階乗 とも呼ばれ、
との 積です。
これは 、 という意味で
ポッホハマー記号 の q 類似体 です。q ポッホハマー
記号は、 q 類似体の構築における主要な構成要素です 。 たとえば、 基本超幾何級数の理論では、 一般化超幾何級数 の理論で通常のポッホハマー記号が果たす役割を果たします 。
(
1つの
;
q
)
ん
=
∏
け
=
0
ん
−
1
(
1
−
1つの
q
け
)
=
(
1
−
1つの
)
(
1
−
1つの
q
)
(
1
−
1つの
q
2
)
⋯
(
1
−
1つの
q
ん
−
1
)
、
{\displaystyle (a;q)_{n}=\prod _{k=0}^{n-1}(1-aq^{k})=(1-a)(1-aq)(1- aq^{2})\cdots (1-aq^{n-1}),}
(
1つの
;
q
)
0
=
1.
{\displaystyle (a;q)_{0}=1.}
(
x
)
ん
=
x
(
x
+
1
)
…
(
x
+
ん
−
1
)
{\displaystyle (x)_{n}=x(x+1)\dots (x+n-1)}
リム
q
→
1
(
q
x
;
q
)
ん
(
1
−
q
)
ん
=
(
x
)
ん
。
{\displaystyle \lim _{q\to 1}{\frac {(q^{x};q)_{n}}{(1-q)^{n}}}=(x)_{n}.}
通常のポッホハマー記号とは異なり、 q -ポッホハマー記号は無限積に拡張できます。
これは、 単位円 の内部における q の 解析関数であり、 q の 形式的な冪級数 と見なすこともできます 。この特殊なケースは
オイラー関数
として知られ 、 組合せ論 、 数論 、 モジュラー形式 の理論で重要です。
(
1つの
;
q
)
∞
=
∏
け
=
0
∞
(
1
−
1つの
q
け
)
。
{\displaystyle (a;q)_{\infty }=\prod _{k=0}^{\infty }(1-aq^{k}).}
ϕ
(
q
)
=
(
q
;
q
)
∞
=
∏
け
=
1
∞
(
1
−
q
け
)
{\displaystyle \phi (q)=(q;q)_{\infty }=\prod _{k=1}^{\infty }(1-q^{k})}
アイデンティティ
有限積は、無限積を使って表現できます。
これは、負の整数 n
に定義を拡張します。したがって、非負の n に対して
、
および
が 成り立ちます
。あるいは、
これは、パーティション関数の生成関数の一部に役立ちます。
(
1つの
;
q
)
ん
=
(
1つの
;
q
)
∞
(
1つの
q
ん
;
q
)
∞
、
{\displaystyle (a;q)_{n}={\frac {(a;q)_{\infty }}{(aq^{n};q)_{\infty }}},}
(
1つの
;
q
)
−
ん
=
1
(
1つの
q
−
ん
;
q
)
ん
=
∏
け
=
1
ん
1
(
1
−
1つの
/
q
け
)
{\displaystyle (a;q)_{-n}={\frac {1}{(aq^{-n};q)_{n}}}=\prod _{k=1}^{n}{\frac {1}{(1-a/q^{k})}}}
(
1つの
;
q
)
−
ん
=
(
−
q
/
1つの
)
ん
q
ん
(
ん
−
1
)
/
2
(
q
/
1つの
;
q
)
ん
。
{\displaystyle (a;q)_{-n}={\frac {(-q/a)^{n}q^{n(n-1)/2}}{(q/a;q)_{n}}}.}
∏
け
=
ん
∞
(
1
−
1つの
q
け
)
=
(
1つの
q
ん
;
q
)
∞
=
(
1つの
;
q
)
∞
(
1つの
;
q
)
ん
、
{\displaystyle \prod _{k=n}^{\infty }(1-aq^{k})=(aq^{n};q)_{\infty }={\frac {(a;q) _{\infty }}{(a;q)_{n}}},}
qポッホハマー記号は、数多くの q 級数の恒等式、特に無限級数展開
の対象であり
、
これらは両方とも q 二項定理
の特殊なケースです 。Fridrikh
Karpelevich は次の恒等式 を 発見しました (証明については Olshanetsky と Rogov (1995) を参照)。
(
x
;
q
)
∞
=
∑
ん
=
0
∞
(
−
1
)
ん
q
ん
(
ん
−
1
)
/
2
(
q
;
q
)
ん
x
ん
{\displaystyle (x;q)_{\infty }=\sum _{n=0}^{\infty }{\frac {(-1)^{n}q^{n(n-1)/2 }}{(q;q)_{n}}}x^{n}}
1
(
x
;
q
)
∞
=
∑
ん
=
0
∞
x
ん
(
q
;
q
)
ん
、
{\displaystyle {\frac {1}{(x;q)_{\infty }}}=\sum _{n=0}^{\infty }{\frac {x^{n}}{(q;q)_{n}}},}
(
a
x
;
q
)
∞
(
x
;
q
)
∞
=
∑
n
=
0
∞
(
a
;
q
)
n
(
q
;
q
)
n
x
n
.
{\displaystyle {\frac {(ax;q)_{\infty }}{(x;q)_{\infty }}}=\sum _{n=0}^{\infty }{\frac {(a;q)_{n}}{(q;q)_{n}}}x^{n}.}
(
q
;
q
)
∞
(
z
;
q
)
∞
=
∑
n
=
0
∞
(
−
1
)
n
q
n
(
n
+
1
)
/
2
(
q
;
q
)
n
(
1
−
z
q
−
n
)
,
|
z
|
<
1.
{\displaystyle {\frac {(q;q)_{\infty }}{(z;q)_{\infty }}}=\sum _{n=0}^{\infty }{\frac {(-1)^{n}q^{n(n+1)/2}}{(q;q)_{n}(1-zq^{-n})}},\ |z|<1.}
組み合わせ解釈
q -ポッホハマー記号 は、分割の列挙的組合せ論と密接に関係しています。 の係数は 、
m を最大で n 個の 部分に
分割する数です。 分割の共役により、これは m を最大で n 個 のサイズの部分へ分割する数と同じであるため、生成級数の同一視により
、上記のセクションのように
恒等式が得られます
。
q
m
a
n
{\displaystyle q^{m}a^{n}}
(
a
;
q
)
∞
−
1
=
∏
k
=
0
∞
(
1
−
a
q
k
)
−
1
{\displaystyle (a;q)_{\infty }^{-1}=\prod _{k=0}^{\infty }(1-aq^{k})^{-1}}
(
a
;
q
)
∞
−
1
=
∑
k
=
0
∞
(
∏
j
=
1
k
1
1
−
q
j
)
a
k
=
∑
k
=
0
∞
a
k
(
q
;
q
)
k
{\displaystyle (a;q)_{\infty }^{-1}=\sum _{k=0}^{\infty }\left(\prod _{j=1}^{k}{\frac {1}{1-q^{j}}}\right)a^{k}=\sum _{k=0}^{\infty }{\frac {a^{k}}{(q;q)_{k}}}}
また、の
係数は、 mを n 個 または n -1 個の異なる部分
に
分割する数であることもわかります。
q
m
a
n
{\displaystyle q^{m}a^{n}}
(
−
a
;
q
)
∞
=
∏
k
=
0
∞
(
1
+
a
q
k
)
{\displaystyle (-a;q)_{\infty }=\prod _{k=0}^{\infty }(1+aq^{k})}
このような分割から n − 1 個の部分を持つ三角分割を取り除くと、最大で n個の部分を持つ任意の分割が残る。これにより、 n 個または n − 1 個の異なる部分への分割の集合と、 n − 1個の部分を持つ三角分割 と最大で n 個の部分を持つ分割のペアの集合との間に、重み保存一対一の関係が成立する。生成級数を識別することにより、これ
も上の節で説明した 恒等式につながる
。関数の逆数は同様に、 分割関数 の生成関数 として生じ 、 これも以下に示す 2 番目の 2 つの q 級数 展開によって展開される。 [1]
(
−
a
;
q
)
∞
=
∏
k
=
0
∞
(
1
+
a
q
k
)
=
∑
k
=
0
∞
(
q
(
k
2
)
∏
j
=
1
k
1
1
−
q
j
)
a
k
=
∑
k
=
0
∞
q
(
k
2
)
(
q
;
q
)
k
a
k
{\displaystyle (-a;q)_{\infty }=\prod _{k=0}^{\infty }(1+aq^{k})=\sum _{k=0}^{\infty }\left(q^{k \choose 2}\prod _{j=1}^{k}{\frac {1}{1-q^{j}}}\right)a^{k}=\sum _{k=0}^{\infty }{\frac {q^{k \choose 2}}{(q;q)_{k}}}a^{k}}
(
q
)
∞
:=
(
q
;
q
)
∞
{\displaystyle (q)_{\infty }:=(q;q)_{\infty }}
p
(
n
)
{\displaystyle p(n)}
1
(
q
;
q
)
∞
=
∑
n
≥
0
p
(
n
)
q
n
=
∑
n
≥
0
q
n
(
q
;
q
)
n
=
∑
n
≥
0
q
n
2
(
q
;
q
)
n
2
.
{\displaystyle {\frac {1}{(q;q)_{\infty }}}=\sum _{n\geq 0}p(n)q^{n}=\sum _{n\geq 0}{\frac {q^{n}}{(q;q)_{n}}}=\sum _{n\geq 0}{\frac {q^{n^{2}}}{(q;q)_{n}^{2}}}.}
q 二 項定理 自体も、同様の趣旨の、もう少し複雑な組み合わせ論的議論によって扱うことができます (次のサブセクションに示す展開も参照してください)。
同様に、
(
q
;
q
)
∞
=
1
−
∑
n
≥
0
q
n
+
1
(
q
;
q
)
n
=
∑
n
≥
0
q
n
(
n
+
1
)
2
(
−
1
)
n
(
q
;
q
)
n
.
{\displaystyle (q;q)_{\infty }=1-\sum _{n\geq 0}q^{n+1}(q;q)_{n}=\sum _{n\geq 0}q^{\frac {n(n+1)}{2}}{\frac {(-1)^{n}}{(q;q)_{n}}}.}
複数引数の規則
q -ポッホハマー記号を含む恒等式には 多くの記号の積が含まれることが多いため、積を複数の引数を持つ単一の記号として記述するのが標準的な規則です。
(
a
1
,
a
2
,
…
,
a
m
;
q
)
n
=
(
a
1
;
q
)
n
(
a
2
;
q
)
n
…
(
a
m
;
q
)
n
.
{\displaystyle (a_{1},a_{2},\ldots ,a_{m};q)_{n}=(a_{1};q)_{n}(a_{2};q)_{n}\ldots (a_{m};q)_{n}.}
q -シリーズ
q 級数とは、係数が q の関数、典型的には の表現である級数である 。 [ 2 ] 初期 の 結果は オイラー 、 ガウス 、 コーシー によるものである 。体系的な研究は エドゥアルト・ハイネ (1843)から始まった。 [3]
(
a
;
q
)
n
{\displaystyle (a;q)_{n}}
他者との関係 q -機能
n の q 類似体 、 つまり q 括弧または n の q 数とは 、 次 の よう に 定義 さ れ ます。
これから、 階乗 のq 類似体である q 階乗を 次のように定義できます。
[
n
]
q
=
1
−
q
n
1
−
q
.
{\displaystyle [n]_{q}={\frac {1-q^{n}}{1-q}}.}
[
n
]
!
q
=
∏
k
=
1
n
[
k
]
q
=
[
1
]
q
⋅
[
2
]
q
⋯
[
n
−
1
]
q
⋅
[
n
]
q
=
1
−
q
1
−
q
1
−
q
2
1
−
q
⋯
1
−
q
n
−
1
1
−
q
1
−
q
n
1
−
q
=
1
⋅
(
1
+
q
)
⋯
(
1
+
q
+
⋯
+
q
n
−
2
)
⋅
(
1
+
q
+
⋯
+
q
n
−
1
)
=
(
q
;
q
)
n
(
1
−
q
)
n
{\displaystyle {\begin{aligned}\left[n\right]!_{q}&=\prod _{k=1}^{n}[k]_{q}=[1]_{q}\cdot [2]_{q}\cdots [n-1]_{q}\cdot [n]_{q}\\&={\frac {1-q}{1-q}}{\frac {1-q^{2}}{1-q}}\cdots {\frac {1-q^{n-1}}{1-q}}{\frac {1-q^{n}}{1-q}}\\&=1\cdot (1+q)\cdots (1+q+\cdots +q^{n-2})\cdot (1+q+\cdots +q^{n-1})\\&={\frac {(q;q)_{n}}{(1-q)^{n}}}\\\end{aligned}}}
これらの数字は
、
lim
q
→
1
[
n
]
q
=
n
,
{\displaystyle \lim _{q\rightarrow 1}[n]_{q}=n,}
lim
q
→
1
[
n
]
!
q
=
n
!
.
{\displaystyle \lim _{q\rightarrow 1}[n]!_{q}=n!.}
極限値 n !は、 n 要素の集合 S の 順列 を数えます。同様に、 ちょうど i 個の要素を含む入れ子集合のシーケンスの数を数えます 。 [4] 比較すると、 q が素数冪で、 V が q 個の要素を持つ体上の n 次元ベクトル空間である場合 、 q 類似体は V 内の 完全なフラグ の数、つまり、 i 次元を持つ 部分空間の シーケンスの数です 。 [4] これまでの考察から、入れ子集合のシーケンスを、 1 つの要素を持つ推測体 上のフラグと見なすことができることがわかります。
E
1
⊂
E
2
⊂
⋯
⊂
E
n
=
S
{\displaystyle E_{1}\subset E_{2}\subset \cdots \subset E_{n}=S}
E
i
{\displaystyle E_{i}}
[
n
]
!
q
{\displaystyle [n]!_{q}}
V
1
⊂
V
2
⊂
⋯
⊂
V
n
=
V
{\displaystyle V_{1}\subset V_{2}\subset \cdots \subset V_{n}=V}
V
i
{\displaystyle V_{i}}
負の整数q 括弧の積は q 階乗
で次のように表すことができます。
∏
k
=
1
n
[
−
k
]
q
=
(
−
1
)
n
[
n
]
!
q
q
n
(
n
+
1
)
/
2
{\displaystyle \prod _{k=1}^{n}[-k]_{q}={\frac {(-1)^{n}\,[n]!_{q}}{q^{n(n+1)/2}}}}
q 階乗から q 二項係数( ガウス二項係数 とも呼ばれる)を次のように定義することができます 。
[
n
k
]
q
=
[
n
]
!
q
[
n
−
k
]
!
q
[
k
]
!
q
,
{\displaystyle {\begin{bmatrix}n\\k\end{bmatrix}}_{q}={\frac {[n]!_{q}}{[n-k]!_{q}[k]!_{q}}},}
ここで、これらの係数の三角形が対称的であることは容易に分かる。
[
n
m
]
q
=
[
n
n
−
m
]
q
{\displaystyle {\begin{bmatrix}n\\m\end{bmatrix}}_{q}={\begin{bmatrix}n\\n-m\end{bmatrix}}_{q}}
すべてについて 。
0
≤
m
≤
n
{\displaystyle 0\leq m\leq n}
[
n
+
1
k
]
q
=
[
n
k
]
q
+
q
n
−
k
+
1
[
n
k
−
1
]
q
=
[
n
k
−
1
]
q
+
q
k
[
n
k
]
q
.
{\displaystyle {\begin{aligned}{\begin{bmatrix}n+1\\k\end{bmatrix}}_{q}&={\begin{bmatrix}n\\k\end{bmatrix}}_{q}+q^{n-k+1}{\begin{bmatrix}n\\k-1\end{bmatrix}}_{q}\\&={\begin{bmatrix}n\\k-1\end{bmatrix}}_{q}+q^{k}{\begin{bmatrix}n\\k\end{bmatrix}}_{q}.\end{aligned}}}
前述の再帰関係から、 -二項定理の次の変形がこれらの係数に関して次のように展開されること も分かる。 [5]
q
{\displaystyle q}
(
z
;
q
)
n
=
∑
j
=
0
n
[
n
j
]
q
(
−
z
)
j
q
(
j
2
)
=
(
1
−
z
)
(
1
−
q
z
)
⋯
(
1
−
z
q
n
−
1
)
(
−
q
;
q
)
n
=
∑
j
=
0
n
[
n
j
]
q
2
q
j
(
q
;
q
2
)
n
=
∑
j
=
0
2
n
[
2
n
j
]
q
(
−
1
)
j
1
(
z
;
q
)
m
+
1
=
∑
n
≥
0
[
n
+
m
n
]
q
z
n
.
{\displaystyle {\begin{aligned}(z;q)_{n}&=\sum _{j=0}^{n}{\begin{bmatrix}n\\j\end{bmatrix}}_{q}(-z)^{j}q^{\binom {j}{2}}=(1-z)(1-qz)\cdots (1-zq^{n-1})\\(-q;q)_{n}&=\sum _{j=0}^{n}{\begin{bmatrix}n\\j\end{bmatrix}}_{q^{2}}q^{j}\\(q;q^{2})_{n}&=\sum _{j=0}^{2n}{\begin{bmatrix}2n\\j\end{bmatrix}}_{q}(-1)^{j}\\{\frac {1}{(z;q)_{m+1}}}&=\sum _{n\geq 0}{\begin{bmatrix}n+m\\n\end{bmatrix}}_{q}z^{n}.\end{aligned}}}
さらに、を満たす非負の整数引数を
持つ q 多項式係数
を定義することもできます。上記の係数は、 となる q 個の要素を持つ体上の n 次元ベクトル空間
内の部分空間の 旗の数を数えます
。
[
n
k
1
,
…
,
k
m
]
q
=
[
n
]
!
q
[
k
1
]
!
q
⋯
[
k
m
]
!
q
,
{\displaystyle {\begin{bmatrix}n\\k_{1},\ldots ,k_{m}\end{bmatrix}}_{q}={\frac {[n]!_{q}}{[k_{1}]!_{q}\cdots [k_{m}]!_{q}}},}
k
1
,
…
,
k
m
{\displaystyle k_{1},\ldots ,k_{m}}
∑
i
=
1
m
k
i
=
n
{\displaystyle \sum _{i=1}^{m}k_{i}=n}
V
1
⊂
⋯
⊂
V
m
{\displaystyle V_{1}\subset \dots \subset V_{m}}
dim
V
i
=
∑
j
=
1
i
k
j
{\displaystyle \dim V_{i}=\sum _{j=1}^{i}k_{j}}
極限は 通常の多項係数を与え 、これは n 個 の異なるシンボル内の 各 が回 出現する単語を数えます 。
q
→
1
{\displaystyle q\to 1}
(
n
k
1
,
…
,
k
m
)
{\displaystyle {n \choose k_{1},\dots ,k_{m}}}
{
s
1
,
…
,
s
m
}
{\displaystyle \{s_{1},\dots ,s_{m}\}}
s
i
{\displaystyle s_{i}}
k
i
{\displaystyle k_{i}}
また、 ガンマ関数 のq 類似 体である q- ガンマ関数 も得られ、次のように定義されます
。これは 、単位円の内側から
q が 1 に近づく
につれて、通常のガンマ関数に収束します。任意の x
に対して 、および
負でない整数値の nに対してであることに注意してください。あるいは、これは q 階乗関数の実数系へ
の拡張として考えることができます。
Γ
q
(
x
)
=
(
1
−
q
)
1
−
x
(
q
;
q
)
∞
(
q
x
;
q
)
∞
{\displaystyle \Gamma _{q}(x)={\frac {(1-q)^{1-x}(q;q)_{\infty }}{(q^{x};q)_{\infty }}}}
Γ
q
(
x
+
1
)
=
[
x
]
q
Γ
q
(
x
)
{\displaystyle \Gamma _{q}(x+1)=[x]_{q}\Gamma _{q}(x)}
Γ
q
(
n
+
1
)
=
[
n
]
!
q
{\displaystyle \Gamma _{q}(n+1)=[n]!_{q}}
参照
参考文献
^ Berndt, BC「q シリーズとは何か?」 (PDF) 。
^ Bruce C. Berndt、「q 級数とは何か?」、Ramanujan Rediscovered: Proceedings of a Conference on Elliptic Functions, Partitions, and q-Series in memory of K. Venkatachaliengar: Bangalore、2009 年 6 月 1 日~5 日、ND Baruah、BC Berndt、S. Cooper、T. Huber、MJ Schlosser 編、Ramanujan Mathematical Society、マイソール、2010 年、31~51 頁。
^ ハイネ、E.「Untersuhungen über die Reihe」。 J. Reine Angew.数学34(1847)、285–328。
^ ab スタンレー、リチャード P. (2011)、 列挙的組合せ論 、第 1 巻 (第 2 版)、ケンブリッジ大学出版局 、セクション1.10.2。
^ Olver; et al. (2010). 「セクション 17.2」。NIST 数学関数ハンドブック。p. 421。
George Gasper と Mizan Rahman 、 「Basic Hypergeometric Series、第 2 版」 、 (2004)、Encyclopedia of Mathematics and Its Applications、 96 、Cambridge University Press、Cambridge。ISBN 0-521-83357-4 。
Roelof Koekoek と Rene F. Swarttouw、 「直交多項式の Askey スキームとその q 類似体」 、セクション 0.2。
エクストン、H. (1983)、 q-超幾何関数とその応用 、ニューヨーク:ハルステッドプレス、チチェスター:エリスホーウッド、1983、 ISBN 0853124914 、 ISBN 0470274530 、 ISBN 978-0470274538
MA Olshanetsky と VBK Rogov (1995)、「修正 q-ベッセル関数と q-ベッセル-マクドナルド関数」、arXiv:q-alg/9509013。
外部リンク