Skip to content →

q類似

\(\mathbb{F}_q\) 上の \(n\) 次元ベクトル空間 \(V_n\) の部分空間がなす鎖
\(0 = V_0 \subset V_1 \subset \cdots \subset V_n\)
を取る方法は
\begin{align}
[n!]_q &=\frac{(q^n-1)(q^{n-1}-1)\cdots(q-1)}{(q-1)^n}\\
&=\frac{(q^n-1)(q^n-q)\cdots(q^n-q^{n-1})}{(q-1)^nq^{n \choose 2}} \\
&= \frac{\gamma_n}{(q-1)^n q^{n \choose 2}}
\end{align} 通りある。\((q-1)^nq^{n \choose 2}\) は鎖を保つ変換の個数である。\(V_n\) の \(k\) 次元部分空間の個数を \(\boldsymbol{ n \choose k}\) と置く。極大鎖に \(k\) 次元部分空間は必ず含まれる。各 \(k\) 次元部分空間 \(V_k\) に対して、\(V_k\) を終点とする極大鎖は \(\boldsymbol {k}!\) 個、\(W\) を始点とする極大鎖は \(V_n / V_k \cong V_{n – k}\) より \(\boldsymbol {(n-k)!}\) 個ある。従って、$$\boldsymbol{ n \choose k} = \frac{\boldsymbol{n}!}{\boldsymbol{k}!\boldsymbol{(n-k)}!}$$である。
\(m \) \((\leq n)\) 個の独立なベクトルを選ぶ方法は \((q^{n}-1)(q^n – q) \cdots (q^n-q^{m-1}) = q^{{m-1 \choose 2}} \frac{\boldsymbol{n}!}{\boldsymbol{(n-m)}!}\) 通りある。\(m \) \((\geq n)\) 個のベクトルが \(V_n\) を張るような選び方は \((q^{m}-1)(q^{m} – q) \cdots (q^m-q^{n-1})\) 通りある。これは、ランク \(n\) の \(n \times m\) 行列の個数を数えている(ARC139F)。

\((\mathbb{Z}/p^k\mathbb{Z})^n\) の自由 \(\mathbb{Z} / p^k \mathbb{Z}\) 加群

\((\mathbb{Z}/p^k\mathbb{Z})^n\) の自由 \(\mathbb{Z} / p^k \mathbb{Z}\) 加群の部分自由加群が包含関係に関してなす束の極大鎖は \begin{align}
& \prod_{i=1}^n (p^{ik}-p^{i(k-1)}) \\
& \prod_{i=1}^n p^{i(k-1)}(p^i-1) \\
=& p^{(k-1){n + 1 \choose 2}} \boldsymbol{n}_p!\\
\end{align}
個ある(2桁目以降は自由に決められるとも解釈できる)。従って、階数 \(k\) の部分自由加群は\begin{align}
\frac{p^{(k-1){n + 1 \choose 2}} \boldsymbol{n}_p!}{p^{(k-1){k + 1 \choose 2}} \boldsymbol{n}_p!p^{(k-1){n – k + 1 \choose 2}} \boldsymbol{n}_p!}=
{\boldsymbol{n} \choose \boldsymbol{k}}_p p^{k(k-1)(n-k)}
\end{align} 個ある。

q二項展開

\begin{align}
f(x,q)=&\prod_{i \geq 1}\frac{1}{1-xq^i} \\
=&\sum_{k \geq 0} (xq)^k\prod_{i = 1}^k\frac{1}{1-q^i} \\
\end{align}
全要素からあらかじめ1を引いておくと上の式が得られる。
\begin{align}
&f(qx,q) = f(x,q)(1-xq)\\
\iff&[x^nq^m]f(qx,q)=[x^nq^m]f(x,q)(1-xq) \\
\iff&[(qx)^nq^{m-n}]f(qx,x)=[x^nq^m]f(x,q)-[x^{n-1}q^{m-1}]f(x,q) \\
\iff&[x^{n}q^{m-n}]f(x,q)=[x^nq^m]f(x,q)-[x^{n-1}q^{m-1}]f(x,q) \\
\iff&[x^nq^m]f(x,q)=[x^{n}q^{m-n}]f(x,q)+[x^{n-1}q^{m-1}]f(x,q) \\
\end{align}
\(f(qx,q)=f(x,q)(1-xq)\) をテイラー展開しても同様の式が得られる。

\begin{align}
\prod_{i \geq 1} (1+xq^i) = \sum_{k \geq 0}x^kq^{{k \choose 2}}\prod_{i = 1}^k\frac{1}{1-q^i}
\end{align}

\(1,2,\ldots,k\) をあらかじめ引いておくと上の式が得られる。

非負整数の集合と多重集合の直積のOGFは\(\prod\frac{1+xq^i}{1-xq^i} = \sum_{n\geq 0}\frac{x^n(q+q)\cdots(q+q^{n})}{(1-q)\cdots(1-q^n)}\)となる。集合と多重集合の要素を一緒に一列に並べる。\(q+q^i\) のうち \(q^i\) を掛けるのは、集合と多重集合の要素を混ぜてソートしたときに、後ろから \(i\) 番目に多重集合の要素がある場合を表している。

各整数が高々 \(M\) 回しか使われない多重集合のOGFは\(\prod\frac{1+(xq^i)^{1+M}}{1-xq^i}\)となる。\(a(n,m)\) を \(x^nq^m\) の係数とする。最小要素が2以上か否かで場合分けする(熨斗袋さん)と \(a(n,m)=a(n,m-n)+a(n-1,m-1)-a(n-1-M,m-n)\) が成り立つが、上のような和で書くことはできなかった。

q微分

\(\mathrm{D}_q f := \frac{f(qx)-f(x)}{qx-x}\) とする。\(f^*\) と略記することもある。

連鎖律
\begin{align}
\mathrm{D}_q(fg) &= \frac{f(qx)g(qx)-f(x)g(x)}{qx-x} \\
&=\frac{(f(qx)-f(x))g(qx)+f(x)(g(qx)-g(x))}{qx-x} \\
&=f^*(x)g(qx)+f(x)g^*(x) \\
&=f^*(x)g(x)+f(qx)g^*(x) \\
\end{align}

\begin{align}
\mathrm{D}_q(1/f) &= \frac{\frac{1}{f(qx)}-\frac{1}{f(x)}}{qx-x}\\
&= \frac{f(x)-f(qx)}{f(qx)f(x)(qx-x)}\\
&= -\frac{f^*(x)}{f(qx)f(x)}\\
\end{align}

\begin{align}
\mathrm{D}_q(f/g) &= f^*(x)/g(qx)+f(x)(1/g(x))^* \\
&= f^*(x)/g(qx)-f(x)g^*(x)/(g(qx)g(x)) \\
&= \frac{f^*(x)g(x)-f(x)g^*(x)}{g(qx)g(x)} \\
\end{align}
\(\mathrm{D}_qx^n=[n]_qx^{n-1}\) より exp の q類似を \(e_q(x) := \sum_{n \geq 0} \frac{x^n}{[n!]_q}\) と定義する。
\(\mathrm{D}_qe_q=e_q\) が成り立つ。また、逆元のq微分は
\begin{align}
(1/e_q(x))^* &= – \frac{e^*_q(x)}{e_q(qx)e_q(x)} \\
&=-1/e_q(qx)
\end{align}となる。係数比較により、\(\left[\frac{x^n}{[n!]}_q\right] 1/e_q = (-1)^{n}q^{n \choose 2}\) が得られる。

  • \(\gamma_n := \#\mathrm{GL}(n,q) = (q^n-1)(q^{n}-q)\cdots(q^n-q^{n-1})=q^{{n \choose 2}}(-1)^n(q-1)^nn!_q\)
  • \(\#\mathrm{SL}(n,q)=\#\mathrm{GL}(n,q)/(q-1)\)
  • \({n \choose k}_q = \frac{\gamma_n}{\gamma_k\gamma_{n-k}q^{k(n-k)}}\)
  • ランク \(k\) の \(n \times m\) 行列の個数 \begin{align}
    &{m \choose k}_q(q^n-1)(q^n-q)\cdots(q^n-q^{k-1}) \\
    =&{n \choose k}_q (q^m-1)(q^m-1)\cdots(q^m-q^{k-1}) \\
    =&\frac{(q^n-1)\cdots(q^n-q^{k-1})(q^m-1)\cdots(q^m-q^{k-1})}{(q^k-1)\cdots(q^k-q^{k-1})}
    \end{align}
  • ランク \(k\) の \(n \times n\) 行列の個数を \(\gamma_{n, k}\) と置く。長さ \(M\) の \(n \times n\) 行列の列 \(A_1, B_2, \ldots, A_M\) であって、\(\operatorname{rank} A_1A_2\cdots A_M = k\) となるものの個数 \(\sum_{n=i_0 \geq i_1 \geq \cdots \geq i_M = k} \gamma_{i_0, i_{1}}\gamma_{i_1, i_2} \cdots \gamma_{i_{M-1}, i_M}q^{n \sum_{j=1}^{M-1} (n-i_j)}\)

\(V_n\) の非空な部分空間の集合\(\{W_1,W_2, \ldots, W_k\}\) であって、$$V_n = W_1 \oplus W_2 \oplus \cdots \oplus W_k$$ となるものを考える。整数列 \(a\) を固定して、\(a_i = \#\{i = \dim W_j : j\}\) となる場合の数は
$$\frac{1}{k!}\frac{\gamma_n}{\prod_i \gamma_i^{a_i}}$$ である。これは二項係数の q 類似である。

対角化できる行列の個数の母関数は\((\sum x^n/\gamma_n)^q\)

\({2n \choose n}_q = \sum {n \choose k}_q {n \choose n-k}_q q^k\)
\(V_{2n}=V_n \oplus V_n\)として考える。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA