代数的組合せ論

7 個の元からなる集合 $P=\{\hat{0},a,b,c,d,e,\hat{1}\}$ に、次の被覆関係（$x⋖y$ は「$y$ は $x$ のすぐ上にある」を表す）から生成される半順序 $\le$ を入れる。
$$\hat{0}⋖a,\hat{0}⋖b,\hat{0}⋖c,\hat{0}⋖d,a⋖e,b⋖e,c⋖\hat{1},d⋖\hat{1},e⋖\hat{1}$$
すなわち、$x\le y$ となるのは $x=y$ であるか、$x$ から $y$ へ被覆関係をたどって上がれるときである。$P$ のメビウス関数 $\mu$ を
$$\mu (x,x)=1,\mu (x,y)=-\sum _{x\le z<y}\mu (x,z)(x<y)$$
で定めるとき、$\mu (\hat{0},\hat{1})$ を求めよ。

正の整数 $n$ の分割とは、正の整数の非増加列 $\lambda =({\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_{\ell }>0)$ で ${\lambda }_1+\cdots +{\lambda }_{\ell }=n$ を満たすものをいい、このとき $\lambda ⊢n$ と書く。分割 $\lambda$ の部分のうち $2$ に等しいものの個数を $m_2(\lambda )$ とする（たとえば $m_2((3,2,2))=2$, $m_2((4,1,1,1))=0$）。

$\lambda$ を $0$ 以上の整数すべての分割（$0$ の分割は空の分割 $1$ 個とする）にわたらせた 2 変数母関数
$$F(x,t)=\sum _{n\ge 0}\sum _{\lambda ⊢n}{t}^{m_2(\lambda )}{x}^n$$
を用いて、
$$\sum _{\lambda ⊢7}{m}_2(\lambda )$$
を求めよ。

正の整数 $n$ の分割 $\lambda =({\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_{\ell }>0)$ に対し、そのヤング図形（第 $i$ 行に ${\lambda }_i$ 個の箱を左詰めで並べた図形）を主対角線に関して転置して得られるヤング図形が表す分割を、$\lambda$ の共役分割といい ${\lambda }^{\prime }=({\lambda }_1^{\prime }\ge {\lambda }_2^{\prime }\ge \cdots )$ で表す。

$16$ の分割 $\lambda =(5,4,4,2,1)$ の共役分割 ${\lambda }^{\prime }$ を、その部分を大きい順に並べた組 $({\lambda }_1^{\prime },{\lambda }_2^{\prime },\dots )$ の形で求めよ。

$q$ を素数の累乗とし、${\mathbb{F}}_q$ を位数 $q$ の有限体とする。${\mathbb{F}}_q$ の元を成分とする $3\times 3$ 行列のうち、階数がちょうど $2$ であるものの個数を $q$ の式で求めよ。

分割 $\lambda$ のヤング図形（第 $i$ 行に ${\lambda }_i$ 個の箱を左詰めで並べ、第 1 行を一番上にかく）の各箱に正の整数を 1 つずつ書き入れたもので、各行では左から右へ広義単調増加、各列では上から下へ狭義単調増加となっているものを、形 $\lambda$ の半標準ヤング盤という。数 $i$ がちょうど ${\mu }_i$ 回現れるとき、その内容は $\mu =({\mu }_1,{\mu }_2,\dots )$ であるという。形 $\lambda$・内容 $\mu$ の半標準ヤング盤の個数をコストカ数 $K_{\lambda \mu }$ という。

$\lambda =(4,2)$, $\mu =(2,2,2)$ のとき、コストカ数 $K_{\lambda \mu }$ を求めよ。

$\{1,2,\dots ,6\}$ の置換 $w$ を語 $w(1)w(2)\cdots w(6)$ とみなす。添字 $1\le i_1<i_2<\cdots <i_k\le 6$ に対して $w(i_1)<w(i_2)<\cdots <w(i_k)$ となるとき $w(i_1)w(i_2)\cdots w(i_k)$ を長さ $k$ の増加部分列といい、$w(i_1)>w(i_2)>\cdots >w(i_k)$ となるとき長さ $k$ の減少部分列という。

最長増加部分列の長さがちょうど $3$ であり、かつ最長減少部分列の長さもちょうど $3$ であるような置換 $w\in S_6$ の個数を求めよ。

可算無限個の変数 $x_1,x_2,\dots$ の有理数係数対称関数環を考える。正の整数 $r$ に対し $h_r={\sum }_{i_1\le i_2\le \cdots \le i_r}{x}_{i_1}{x}_{i_2}\cdots x_{i_r}$ を $r$ 次の完全対称関数とし、分割 $\mu$ に対する単項対称関数を $m_{\mu }$ とする。

$5$ 次の対称関数 $h_3{h}_2$ を単項対称関数の一次結合
$$h_3{h}_2=\sum _{\mu }{c}_{\mu }{m}_{\mu }(\mu \text{ は }5\text{ の分割})$$
で表したとき、$m_{(2,2,1)}$ の係数 $c_{(2,2,1)}$ を求めよ。

$C_4=\{0,1,2,3\}$、$C_3=\{0,1,2\}$ を通常の大小関係による全順序集合（鎖）とし、直積 $P=C_4\times C_3$ に
$$(a,b)\le (a^{\prime },b^{\prime })⟺a\le a^{\prime }\text{かつ}b\le b^{\prime }$$
で半順序を入れる。関数 $f:P\to \mathbb{Z}$ が、すべての $(c,d)\in P$ に対して
$$\sum _{(a,b)\le (c,d)}f(a,b)=(c+d+1{)}^3$$
を満たすとき、$f(3,2)$ の値を求めよ。

$q$ を素数の累乗とし、${\mathbb{F}}_q$ を位数 $q$ の有限体、$V={\mathbb{F}}_q^4$ とする。$e_1,e_2,e_3,e_4$ を $V$ の標準基底とする。$V$ の $2$ 次元部分空間 $W$ のうち、$e_1\notin W$ かつ $e_2\notin W$ をみたすものの個数を $q$ の多項式として求めよ。

$n$ を $2$ 以上の整数とする。分割 $\lambda =(2,2)$ のヤング図形（英国式: 上から順に $2$ 個、$2$ 個の箱を左詰めに並べたもの）の各箱に $\{1,2,\dots ,n\}$ の整数を $1$ つずつ書き込む。各行では左から右へ広義単調増加、各列では上から下へ狭義単調増加となる書き込み方（形 $(2,2)$ の半標準ヤング盤）の個数を $n$ の式で求めよ。

可算無限個の変数 $x_1,x_2,\dots$ の有理数係数対称関数環 ${\Lambda }_{\mathbb{Q}}$ において、分割 $\lambda$ に対するシューア関数を $s_{\lambda }$、完全対称関数を $h_{\mu }=h_{{\mu }_1}{h}_{{\mu }_2}\cdots$ とする。ここで $h_k$ は次数 $k$ の単項式すべての和である。

4 次の完全対称関数 $h_{(2,1,1)}=h_2{h}_1{h}_1$ をシューア関数の一次結合で
$$h_{(2,1,1)}=a_1{s}_{(4)}+a_2{s}_{(3,1)}+a_3{s}_{(2,2)}+a_4{s}_{(2,1,1)}+a_5{s}_{(1,1,1,1)}$$
と表すとき、係数の組 $(a_1,a_2,a_3,a_4,a_5)$ を求めよ。

集合 $[6]=\{1,2,3,4,5,6\}$ の集合分割全体を ${\Pi }_6$ とし、細分による順序（$\sigma \le \tau ⟺\sigma$ の各ブロックが $\tau$ のあるブロックに含まれる）で半順序集合とみなす。${\Pi }_6$ の最大元（ブロックが $[6]$ ただ 1 つの分割）を $\hat{1}$ とし、$\mu$ を ${\Pi }_6$ のメビウス関数とする。

分割
$$\sigma =\{\{1,2\},\{3,4\},\{5\},\{6\}\}$$
に対して、$\mu (\sigma ,\hat{1})$ の値を求めよ。

頂点集合 $V=\{1,2,3,4,5\}$、辺集合
$$E=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,1\}\}$$
の単純グラフ $G$（長さ $5$ の閉路 $C_5$）を考える。$V$ の集合分割のうち、各ブロックが $G$ の誘導部分グラフとして連結であるもの全体を $L_G$ とし（ボンド束）、細分による順序（$\sigma \le \tau ⟺\sigma$ の各ブロックが $\tau$ のあるブロックに含まれる）を入れる。$L_G$ の最小元（すべて 1 元ブロック）を $\hat{0}$、最大元（ブロックが $V$ だけ）を $\hat{1}$ とし、$\mu$ を $L_G$ のメビウス関数とする。

$\mu (\hat{0},\hat{1})$ の値を求めよ。

可算無限個の変数の有理数係数対称関数環 ${\Lambda }_{\mathbb{Q}}$ に、完全対称関数 $h_{\lambda }$ と単項対称関数 $m_{\mu }$ について $⟨h_{\lambda },m_{\mu }⟩={\delta }_{\lambda \mu }$ となる双線形形式としてホールの内積 $⟨,⟩$ を定める。ここで $h_{\lambda }=h_{{\lambda }_1}{h}_{{\lambda }_2}\cdots$ であり、$h_k$ は次数 $k$ の単項式すべての和である。

$$⟨h_{(2,1)},h_{(1,1,1)}⟩$$
の値を求めよ。

可算無限個の変数 $x_1,x_2,\dots$ の有理数係数対称関数環において、$p_k={\sum }_{i\ge 1}{x}_i^k$ を $k$ 次のべき和対称関数、$p_{\mu }=p_{{\mu }_1}{p}_{{\mu }_2}\cdots$ とし、$s_{\lambda }$ を分割 $\lambda$ に対するシューア関数とする。

4 次の対称関数 $p_{(3,1)}=p_3{p}_1$ をシューア関数の一次結合
$$p_{(3,1)}=\sum _{\lambda ⊢4}{c}_{\lambda }{s}_{\lambda }$$
で表すとき、$s_{(2,2)}$ の係数 $c_{(2,2)}$ を求めよ。

$[5]=\{1,2,3,4,5\}$ とし、$[5]$ の部分集合のうち要素の個数が $0,1,4,5$ のいずれかであるもの全体を
$$P=\{S\subseteq [5]:|S|\in \{0,1,4,5\}\}$$
とおく。$P$ に包含関係 $\subseteq$ で半順序を入れる。$P$ のメビウス関数 ${\mu }_P$ について、${\mu }_P(\varnothing ,[5])$ の値を求めよ。

集合 $\{1,2,\dots ,12\}$ に、新しい元 $\hat{1}$ を 1 つ付け加えた集合を $P=\{1,2,\dots ,12\}\cup \{\hat{1}\}$ とする。$P$ に次の半順序 ${\le }_P$ を入れる。
- $a,b\in \{1,\dots ,12\}$ に対しては、$a{\le }_{P}b⟺a$ は $b$ を割り切る
- すべての $x\in P$ に対して $x{\le }_P\hat{1}$

$P$ のメビウス関数を ${\mu }_P$ とするとき、${\mu }_P(1,\hat{1})$ を求めよ。

可算無限個の変数 $x_1,x_2,\dots$ の有理数係数対称関数環において、$e_2={\sum }_{i<j}{x}_i{x}_j$ を $2$ 次の基本対称関数、分割 $\mu$ に対する単項対称関数を $m_{\mu }$ とする。$6$ 次の対称関数 $e_2^3$ を単項対称関数で
$$e_2^3=\sum _{\mu ⊢6}{a}_{\mu }{m}_{\mu }$$
と展開するとき、係数 $a_{(2,2,1,1)}$ を求めよ。

$q$ を素数の累乗とし、${\mathbb{F}}_q$ を位数 $q$ の有限体とする。${\mathbb{F}}_q$ の元を成分とする $2\times 4$ 行列 $A$ のうち、次の 2 つの条件をともにみたすものの個数を $q$ の多項式として求めよ。

• $A$ の階数は $2$ である
• $A$ のどの列も零ベクトルではない

頂点集合 $\{1,2,3,4\}$ をもち、辺集合が $\{12,13,23,24,34\}$ である単純グラフを $G$ とする（$K_4$ から辺 $14$ を除いたグラフ）。$\{1,2,3,4\}$ の集合分割 $\pi$ のうち、$\pi$ のどのブロック $B$ についても $B$ が誘導する $G$ の部分グラフが連結であるもの全体を $L_G$ とする（要素が 1 個のブロックは連結とみなす）。$L_G$ に細分による半順序（$\sigma \le \tau ⟺\sigma$ の各ブロックが $\tau$ のあるブロックに含まれる）を入れる。$L_G$ の最小元 $\hat{0}=\{1\}\{2\}\{3\}\{4\}$ と最大元 $\hat{1}=\{1,2,3,4\}$ に対し、メビウス関数の値 ${\mu }_{L_G}(\hat{0},\hat{1})$ を求めよ。ただしメビウス関数は $\mu (x,x)=1$、$x<y$ のとき $\mu (x,y)=-{\sum }_{x\le z<y}\mu (x,z)$ で定める。

有限アーベル群 $G=\mathbb{Z}/3\mathbb{Z}\times \mathbb{Z}/9\mathbb{Z}$ の部分群全体を包含関係で順序づけた半順序集合（部分群束）を $L(G)$ とし、$\mu$ を $L(G)$ のメビウス関数とする。$$S=\sum _{H\in L(G)}\mu (H,G)|H{|}^2$$ の値を求めよ。ただし $|H|$ は部分群 $H$ の位数を表す。

$q$ を素数冪、${\mathbb{F}}_q$ を $q$ 元体とし、$n,m$ を $0$ 以上の整数とする。$0\le k\le m$ に対して $q$ 二項係数を
$${\left(\genfrac{}{}{0ex}{}{m}{k}\right)}_q=\prod _{i=0}^{k-1}\frac{q^{m-i}-1}{q^{k-i}-1}\left(k=0\text{ のときは空積で }{\left(\genfrac{}{}{0ex}{}{m}{0}\right)}_q=1\right)$$
で定める。次の事実は証明なしに用いてよい。

• ${\left(\genfrac{}{}{0ex}{}{m}{k}\right)}_q$ は ${\mathbb{F}}_q^m$ の $k$ 次元部分空間の個数に等しい。
• ${\mathbb{F}}_q^m$ の部分空間全体を包含関係で順序づけた半順序集合を $L_m$ とすると、そのメビウス関数は、$W\subseteq V$ のとき $\mu (W,V)=(-1{)}^d{q}^{d(d-1)/2}$（$d=\dim V-\dim W$）である。
• 有限半順序集合上のメビウスの反転公式。

このとき、${\mathbb{F}}_q^n$ から ${\mathbb{F}}_q^m$ への全射な線形写像の個数を 2 通りに数えることにより、等式
$$\sum _{k=0}^m(-1{)}^k{q}^{k(k-1)/2}{\left(\genfrac{}{}{0ex}{}{m}{k}\right)}_q{q}^{n(m-k)}=\prod _{i=0}^{m-1}\left(q^n-q^i\right)$$
が成り立つことを証明せよ。ただし $m=0$ のとき右辺は空積で $1$ とし、${\mathbb{F}}_q^0=\{0\}$ とする。

$n$ を正の整数とする。$n$ の分割 $\lambda =({\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_{\ell }>0)$ のヤング図形を、正の整数の組の集合
$$D(\lambda )=\{(i,j)\in {\mathbb{Z}}^2:1\le i\le \ell ,1\le j\le {\lambda }_i\}$$
と同一視する（$(i,j)$ を第 $i$ 行・第 $j$ 列の箱とよぶ）。$\lambda$ の共役分割 ${\lambda }^{\prime }$ を、${\lambda }_j^{\prime }=\#\{i:{\lambda }_i\ge j\}$ $(1\le j\le {\lambda }_1)$ で定める。形 $\lambda$ の標準ヤング盤とは、全単射 $T:D(\lambda )\to \{1,2,\dots ,n\}$ であって、各行で右へ（$j$ が増える向きに）、各列で下へ（$i$ が増える向きに）値が真に増加するものをいい、その個数を $f^{\lambda }$ とする。また $\lambda$ の内容の和を
$$c(\lambda )=\sum _{(i,j)\in D(\lambda )}(j-i)$$
と定める。

$k$ を正の奇数とするとき、
$$\sum _{\lambda ⊢n}{f}^{\lambda }c(\lambda {)}^k=0$$
が成り立つことを証明せよ。ただし和は $n$ の分割 $\lambda$ 全体にわたる。

$a,b$ を $a\ge b\ge 0$ をみたす整数とし、$n=a+b\ge 1$ とする。ヤング図形 $\lambda =(a,b)$ とは、第 $1$ 行の第 $1$ 列から第 $a$ 列までの $a$ 個の箱と、第 $2$ 行の第 $1$ 列から第 $b$ 列までの $b$ 個の箱からなる図形とする（$b=0$ のときは第 $1$ 行だけ。$a\ge b$ なので、第 $2$ 行の各箱の真上には第 $1$ 行の箱がある）。$\lambda$ の標準ヤング盤とは、$\lambda$ の $n$ 個の箱に $1,2,\dots ,n$ を $1$ つずつ書き入れたもので、次の 2 条件をみたすものをいう。ここで第 $i$ 行第 $j$ 列の箱に書かれた数を $T(i,j)$ と書く。

• 行の条件: $T(1,1)<T(1,2)<\cdots <T(1,a)$ かつ $T(2,1)<T(2,2)<\cdots <T(2,b)$。
• 列の条件: $1\le j\le b$ をみたすすべての $j$ について $T(1,j)<T(2,j)$。

$\lambda =(a,b)$ の標準ヤング盤の個数を $f^{(a,b)}$ とするとき、
$$f^{(a,b)}=\left(\genfrac{}{}{0ex}{}{n}{b}\right)-\left(\genfrac{}{}{0ex}{}{n}{b-1}\right)$$
が成り立つことを証明せよ。ただし $\left(\genfrac{}{}{0ex}{}{n}{-1}\right)=0$ とし、フック長公式は用いないものとする。

分割 $\lambda =(5,4,2,1)$ のヤング図形を考える（英国式：上から順に $5,4,2,1$ 個の箱を左詰めに並べる）。各箱に $1,2,\dots ,12$ を $1$ つずつ重複なく書き込み、各行は左から右へ、各列は上から下へ増加するようにしたもの（標準ヤング盤）を考える。このような標準ヤング盤のうち、$11$ と $12$ が同じ行にあるものの個数を求めよ。

位数 $12$ の二面体群
$$G=⟨r,s\mid r^6=s^2=1,sr{s}^{-1}=r^{-1}⟩$$
を考える（正六角形の合同変換全体のなす群）。$G$ の部分群全体を包含関係で順序づけた半順序集合（部分群束）を $L(G)$ とし、その最小元は自明な部分群 $1=\{e\}$、最大元は $G$ である。$L(G)$ のメビウス関数を $\mu$ とするとき、$\mu (1,G)$ の値を求めよ。

$q$ を不定元とし、正の整数 $m$ に対して $[m{]}_q!={\prod }_{i=1}^m(1-q^i)/(1-q)$、$[0{]}_q!=1$ と定める。$0\le k\le n$ に対し、ガウスの二項係数（$q$-二項係数）を
$${\left[\begin{array}{c}n\\ k\end{array}\right]}_q=\frac{[n{]}_q!}{[k{]}_q![n-k{]}_q!}=\frac{(1-q^n)(1-q^{n-1})\cdots (1-q^{n-k+1})}{(1-q^k)(1-q^{k-1})\cdots (1-q)}$$
で定める。これは $q$ の整数係数多項式である。
$${\left[\begin{array}{c}10\\ 4\end{array}\right]}_q=\sum _{j\ge 0}{a}_j{q}^j$$
と展開したとき、係数 $a_{12}$ を求めよ。

分割 $\lambda =(5,4,3,2)$ と $\mu =(3,2,1)$ を考える。ヤング図形は英国式（上から順に各行の箱を左詰めに並べる）で描くものとし、$\lambda$ のヤング図形から $\mu$ のヤング図形に含まれる箱を取り除いた歪ヤング図形 $\lambda /\mu$（箱は $8$ 個）を考える。

$\lambda /\mu$ の $8$ 個の箱に $1,2,\dots ,8$ を $1$ つずつ書き込む方法のうち、各行で左から右へ数が増加し、各列で上から下へ数が増加するもの（歪シェイプ $\lambda /\mu$ の標準ヤング盤）の個数を求めよ。

集合 $\{1,2,\dots ,30\}$ に整除関係による順序（$a\le b⟺a\mid b$）を入れた半順序集合に、すべての元より大きい新しい元 $\hat{1}$ を最大元として付け加えた半順序集合を $P$ とする。$P$ のメビウス関数を ${\mu }_P$ とするとき、${\mu }_P(1,\hat{1})$ の値を求めよ。

正の整数 $n$ の分割とは、正の整数の非増加列 $\lambda =({\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_{\ell }>0)$ で ${\lambda }_1+\cdots +{\lambda }_{\ell }=n$ を満たすものをいう。分割 $\lambda$ に現れる相異なる値の個数（例えば $\lambda =(3,3,2,1,1)$ なら $\{3,2,1\}$ の $3$ 個）を $d(\lambda )$ とする。

$10$ のすべての分割 $\lambda$ にわたる和 $\sum _{\lambda ⊢10}d(\lambda )$ を求めよ。

可算無限個の変数 $x_1,x_2,\dots$ の有理数係数対称関数環において、$p_k={\sum }_{i\ge 1}{x}_i^k$ を $k$ 次のべき和対称関数、$s_{\lambda }$ を分割 $\lambda$ に対するシューア関数とする。$p_2^3$ をシューア関数の一次結合で
$$p_2^3=\sum _{\lambda ⊢6}{c}_{\lambda }{s}_{\lambda }$$
と表すとき、係数 $c_{(4,2)}$ を求めよ。

頂点集合を $V=\{1,2,3,4,5\}$ とし、辺集合を $$E=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,1\},\{1,3\}\}$$ とする単純グラフ $G=(V,E)$ を考える（$5$ 頂点の閉路に弦 $\{1,3\}$ を加えたグラフ）。$V$ の集合分割 $\pi$ であって、$\pi$ の各ブロックが誘導する $G$ の部分グラフがすべて連結であるもの全体を $L_G$ とし、$L_G$ に細分による順序（$\sigma \le \tau ⟺\sigma$ の各ブロックが $\tau$ のあるブロックに含まれる）を入れる。$L_G$ はすべてのブロックが $1$ 点である分割 $\hat{0}$ を最小元、$V$ 全体を $1$ つのブロックとする分割 $\hat{1}$ を最大元にもつ。$L_G$ のメビウス関数 $\mu$ について、$\mu (\hat{0},\hat{1})$ の値を求めよ。

$n$ を正の整数とする。分割 $\lambda =(3,2,1)$ のヤング図形（英国式: 上から順に $3$ 個、$2$ 個、$1$ 個の箱を左詰めに並べたもの）の各箱に $\{1,2,\dots ,n\}$ の整数を $1$ つずつ書き込む。各行では左から右へ広義単調増加（等号を許す）、各列では上から下へ狭義単調増加となるような書き込み方（半標準ヤング盤）の個数を $n$ の式で求めよ。

$99$ を、相異なる $3$ つの正の奇数の和として表す方法は何通りあるか。ただし、和の順序だけが異なるもの（たとえば $1+3+95$ と $95+3+1$）は同じ表し方とみなす。

$q$ を素数べきとし、${\mathbb{F}}_q$ を $q$ 元からなる有限体とする。${\mathbb{F}}_q$ の元を成分とする $3\times 3$ 正則行列全体を $G{L}_3({\mathbb{F}}_q)$ とする。$g\in G{L}_3({\mathbb{F}}_q)$ のうち、$gv=v$ を満たす零でないベクトル $v\in {\mathbb{F}}_q^3$ が存在しないもの（すなわち $1$ を固有値にもたないもの）の個数を、$q$ の多項式として求めよ。

正の整数 $n$ の分割とは、和が $n$ になる正の整数の非増加列のことであり、各項を部分という。分割の中に正の整数 $k$ が部分として現れる回数を $k$ の重複度という（現れなければ重複度は $0$）。また $0$ の分割は空列ただ 1 つとする。正の整数 $n$ に対し

• $A(n)$: $n$ の分割のうち、どの正の整数 $k$ についても $k$ の重複度が $3$ を法として $1$ に合同でないもの（すなわち各重複度が $0,2,3,5,6,8,9,\dots$ のいずれかであるもの）の個数
• $B(n)$: 非負整数 $a,b$ と、$a$ の分割 $\mu$、$b$ の分割 $\nu$ の組 $(\mu ,\nu )$ であって、$a+b=n$、$\mu$ のどの部分も $4$ を法として $2$ に合同、$\nu$ のどの部分も $3$ の倍数であるものの個数

とする。すべての正の整数 $n$ に対して $A(n)=B(n)$ が成り立つことを、母関数を用いて証明せよ。

ただし、母関数は有理数係数の形式的冪級数環 $\mathbb{Q}[[x]]$ で考え、次の事実は用いてよい: 形式的冪級数の列 $a_1,a_2,\dots$ で $a_k$ の位数（$0$ でない最低次の次数）が $k\to \infty$ で $\infty$ に発散するものについて、無限積 ${\prod }_{k\ge 1}(1+a_k)$ は収束し、その $x^N$ までの係数は有限個の因子の積で決まること、また収束する無限積どうしの積・商（定数項が $1$ のもの）は因子ごとにとってよく、因子の並べ替えや分け方を変えても値は変わらないこと。

$q$ を不定元とします。整数 $m\ge 1$ に対して $[m{]}_q=1+q+\cdots +q^{m-1}$、$[m{]}_q!=[1{]}_q[2{]}_q\cdots [m{]}_q$ とし、$[0{]}_q!=1$ とします。$0\le k\le n$ に対して $q$ 二項係数を
$${\left[\begin{array}{c}n\\ k\end{array}\right]}_q=\frac{[n{]}_q!}{[k{]}_q![n-k{]}_q!}$$
で定めます。

$\{1,2,\dots ,n\}$ の置換 $\sigma$ の主指数（major index）を
$$\mathrm{maj}(\sigma )=\sum _{\begin{array}{c}1\le i\le n-1\\ \sigma (i)>\sigma (i+1)\end{array}}i$$
と定めます。不動点をもたない置換を完全順列（derangement）といい、その全体を ${\mathcal{D}}_n$ と書きます。さらに
$$D_n(q)=\sum _{\sigma \in {\mathcal{D}}_n}{q}^{\mathrm{maj}(\sigma )}(n\ge 1),D_0(q)=1$$
とおきます。

次の事実は証明なしに用いてかまいません。

（事実）すべての整数 $n\ge 0$ に対して
$$[n{]}_q!=\sum _{k=0}^n{\left[\begin{array}{c}n\\ k\end{array}\right]}_q{D}_k(q)$$
が成り立つ。（これは、MacMahon の等式 ${\sum }_{\sigma \in S_n}{q}^{\mathrm{maj}(\sigma )}=[n{]}_q!$ と、置換を不動点の集合と残りの部分の完全順列に分解したときの Wachs による主指数の分解から得られる。）

このとき、$D_5(q)$ を $q$ の多項式として展開した形で求めてください。

可算無限個の変数 $x_1,x_2,\dots$ の有理数係数対称関数環 ${\Lambda }_{\mathbb{Q}}$ において、分割 $\lambda$ に対するシューア関数を $s_{\lambda }$ とする。対称関数 $$F=(s_{(2,1)}{)}^3$$ をシューア関数の一次結合 $F={\sum }_{\lambda }{c}_{\lambda }{s}_{\lambda }$ として表す（シューア関数は ${\Lambda }_{\mathbb{Q}}$ の基底なので、この表示は一意である）。分割 $(4,3,2)$ に対する係数 $c_{(4,3,2)}$ を求めよ。

$q$ を素数の累乗とし、${\mathbb{F}}_q$ を位数 $q$ の有限体、$V={\mathbb{F}}_q^5$ とする。$e_1,\dots ,e_5$ を $V$ の標準基底とし、$u=e_1+e_2+e_3+e_4+e_5$ とおく。$6$ 個のベクトル
$$e_1,e_2,e_3,e_4,e_5,u$$
のいずれも含まない $V$ の $3$ 次元部分空間 $W$ の個数を、$q$ の多項式として求めよ。

$0$ 以上の整数の分割 $\lambda =({\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_{\ell }>0)$ を考える（$0$ の分割として空の分割 $\lambda =\varnothing$ も含め、$|\lambda |={\lambda }_1+\cdots +{\lambda }_{\ell }$ とする）。部分の個数 $\ell$ が $6$ 以下で、最大の部分 ${\lambda }_1$ が $8$ 以下であるような分割 $\lambda$（すなわちヤング図形が $6\times 8$ の長方形に収まる分割）全体を $\mathcal{B}$ とする。$\mathcal{B}$ に属する分割 $\lambda$ のうち、$|\lambda |$ が $4$ の倍数であるものの個数を求めよ。

有理数係数の対称関数環 ${\Lambda }_{\mathbb{Q}}$ を考える。${\Lambda }_{\mathbb{Q}}$ にはホール内積 $⟨,⟩$ が入っており、シューア関数 $\{s_{\lambda }\}$ はこの内積について正規直交基底をなすものとする。分割 $\rho$ に対し、$\rho$ に $i$ がちょうど $m_i$ 回現れるとき $z_{\rho }={\prod }_{i\ge 1}{i}^{m_i}{m}_i!$ とおき、べき和対称関数 $p_{\rho }$ どうしの内部積（クロネッカー積）$\ast$ を
$$p_{\rho }\ast p_{\sigma }={\delta }_{\rho \sigma }{z}_{\rho }{p}_{\rho }$$
で定め、各次数の斉次部分上で双線形に拡張する。

$6$ 次の対称関数 $s_{(4,2)}\ast s_{(4,2)}$ をシューア関数で
$$s_{(4,2)}\ast s_{(4,2)}=\sum _{\nu ⊢6}{g}_{\nu }{s}_{\nu }(g_{\nu }\in \mathbb{Q})$$
と展開する。係数の $2$ 乗和 $\sum _{\nu ⊢6}{g}_{\nu }^2$ を求めよ。

分割 $\lambda =(4,3,2,1)$ に対するシューア関数 $s_{\lambda }$ を単項対称関数 $m_{\mu }$ の一次結合で
$$s_{(4,3,2,1)}=\sum _{\mu ⊢10}{K}_{(4,3,2,1),\mu }{m}_{\mu }$$
と表す。このとき係数 $K_{(4,3,2,1),(2,2,2,2,2)}$（すなわち、形 $(4,3,2,1)$ で内容が $(2,2,2,2,2)$ の半標準ヤング盤の個数）を求めよ。

正の整数 $n$ の分割 $\lambda =({\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_{\ell }>0)$ が、その共役分割 ${\lambda }^{\prime }$ と一致するとき、$\lambda$ を自己共役であるという。また $\lambda$ のダーフィー正方形の大きさ $d(\lambda )$ を、${\lambda }_i\ge i$ をみたす最大の $i$ と定める。

$30$ の自己共役な分割全体を $\mathcal{S}$ とするとき、
$$\sum _{\lambda \in \mathcal{S}}d(\lambda )$$
の値を求めよ。

$q$ を素数べきとし、${\mathbb{F}}_q$ を $q$ 元からなる有限体とする。$V={\mathbb{F}}_q^5$ の標準基底を $e_1,e_2,e_3,e_4,e_5$ とする。$V$ の $3$ 次元部分空間 $W$ であって、$e_1,e_2,e_3,e_4,e_5$ のいずれも含まないものの個数を $q$ の多項式として求めよ。

$\{1,2,\dots ,7\}$ の置換 $\sigma$ を語 $\sigma (1)\sigma (2)\cdots \sigma (7)$ とみなす。添字 $i_1<i_2<\cdots <i_k$ に対して $\sigma (i_1)<\sigma (i_2)<\cdots <\sigma (i_k)$ となるものを長さ $k$ の増加部分列、$\sigma (i_1)>\sigma (i_2)>\cdots >\sigma (i_k)$ となるものを長さ $k$ の減少部分列という。

長さ $4$ の増加部分列も長さ $4$ の減少部分列ももたない $\{1,2,\dots ,7\}$ の置換の個数を求めよ。

有理数係数の対称関数環 ${\Lambda }_{\mathbb{Q}}$ において、分割 $\lambda =(4,4,1)$ に対するシューア関数 $s_{\lambda }$ をべき和対称関数 $p_{\mu }=p_{{\mu }_1}{p}_{{\mu }_2}\cdots$（$p_k={\sum }_i{x}_i^k$）の一次結合として
$$s_{(4,4,1)}=\sum _{\mu ⊢9}{c}_{\mu }{p}_{\mu }(c_{\mu }\in \mathbb{Q})$$
と表す。$\mu =(3,3,3)$ に対する係数 $c_{(3,3,3)}$ を求めよ。

$q$ を素数の累乗とし、${\mathbb{F}}_q$ を位数 $q$ の有限体、$V={\mathbb{F}}_q^3$ とする。一般線形群 $G{L}_3({\mathbb{F}}_q)$ の元 $g$ のうち、
$$gv=v(v\in V)$$
をみたす $v$ が $v=0$ だけであるもの（すなわち $1$ を固有値にもたないもの）の個数を $D_3(q)$ とする。$D_3(q)$ を $q$ の多項式として求めよ。

$S_{10}$ を $\{1,2,\dots ,10\}$ の置換全体とする。置換 $w\in S_{10}$ を語 $w(1)w(2)\cdots w(10)$ とみなし、$1\le i_1<i_2<\cdots <i_k\le 10$ かつ $w(i_1)<w(i_2)<\cdots <w(i_k)$ となる $k$ の最大値を $w$ の最長増加部分列の長さ、$w(i_1)>w(i_2)>\cdots >w(i_k)$ となる $k$ の最大値を最長減少部分列の長さとよぶ。

$w^2=\mathrm{id}$ をみたす $w\in S_{10}$（恒等置換も含む）のうち、最長増加部分列の長さと最長減少部分列の長さがともにちょうど $4$ であるものの個数を求めよ。

$[8]=\{1,2,\dots ,8\}$ の集合分割のうち、すべてのブロックの要素の個数が偶数であるもの全体を ${\Pi }_8^e$ とする。${\Pi }_8^e$ に細分による順序（$\sigma \le \tau ⟺\sigma$ の各ブロックが $\tau$ のいずれかのブロックに含まれる）を入れ、さらにすべての元より小さい最小元 $\hat{0}$ を新たに付け加えた半順序集合を $\hat{P}={\Pi }_8^e\cup \{\hat{0}\}$ とする。$\hat{P}$ の最大元を $\hat{1}=\{[8]\}$（ブロックが $[8]$ ただ 1 つの分割）とするとき、$\hat{P}$ のメビウス関数の値 $\mu (\hat{0},\hat{1})$ を求めよ。

正の整数 $n$ の分割 $\lambda$ に対し、$\lambda$ に現れる相異なる部分（パート）の値の個数を $d(\lambda )$ とする。たとえば $\lambda =(3,3,2,1,1)$ なら現れる値は $3,2,1$ なので $d(\lambda )=3$ である。

$10$ のすべての分割 $\lambda$ にわたる和
$$\sum _{\lambda ⊢10}d(\lambda {)}^2$$
を求めよ。

$0$ 以上の整数 $n$ に対し、相異なる部分からなる分割（空の分割も含め、$0$ の分割は空の分割 $1$ つとする）を考える。分割 $\lambda$ の部分の個数を $\ell (\lambda )$、部分の和を $|\lambda |$ と書く。相異なる部分からなる分割の順序つきの 3 つ組 $(\alpha ,\beta ,\gamma )$ で $|\alpha |+|\beta |+|\gamma |=n$ をみたすもの全体にわたる和
$$c_n=\sum _{(\alpha ,\beta ,\gamma )}(-1{)}^{\ell (\alpha )+\ell (\beta )+\ell (\gamma )}$$
を定める。このとき
$$\sum _{n=0}^{1000}{c}_n$$
の値を求めよ。

$n$ を $0$ 以上の整数とし、$[n]=\{1,2,\dots ,n\}$（$[0]=\varnothing$）とする。$[n]$ の部分集合のうち、要素の個数が偶数であるものすべてからなる集合
$$P_n=\{S\subseteq [n]:|S|\text{ は偶数}\}$$
を包含関係 $\subseteq$ で順序づけた有限半順序集合を考える（$\varnothing \in P_n$ である）。$P_n$ のメビウス関数 $\mu$ は、$S\subseteq T$ をみたす $S,T\in P_n$ に対して
$$\mu (S,S)=1,\sum _{U\in P_n,S\subseteq U\subseteq T}\mu (S,U)=0(S⊊T)$$
で定める。

また、有理数係数の形式的冪級数環 $\mathbb{Q}[[x]]$ において $\cos x={\sum }_{i\ge 0}\frac{(-1{)}^i{x}^{2i}}{(2i)!}$ とし、その逆元を
$$\sec x=\frac{1}{\cos x}=\sum _{m\ge 0}{E}_{2m}\frac{x^{2m}}{(2m)!}$$
と書く（$\cos x$ の定数項は $1$ なので逆元が存在し、それが偶数次の項のみからなることは用いてよい）。

$S\subseteq T$ をみたす任意の $S,T\in P_n$ に対して、$|T\setminus S|$ は偶数であり、
$$\mu (S,T)=(-1{)}^{|T\setminus S|/2}{E}_{|T\setminus S|}$$
が成り立つことを証明せよ。