およそ 1 年ぶりにコボスタへ。西武戦。則本と岸の投げ合いで投手戦なのか貧打戦なのかよくわからない中、ウィーラーのホームランなどで 3-0 で楽天が勝利。
例によってソロ観戦であって、例によって往復の運転で無事疲弊。
(1+x^k) の乗積を展開したときの係数・その 4
- (1+x^k) の乗積を展開したときの係数 - ヨーキョクデイ
- (1+x^k) の乗積を展開したときの係数・その 2 - ヨーキョクデイ
- (1+x^k) の乗積を展開したときの係数・その 3 - ヨーキョクデイ
今回は整数の分割から歩み寄る。
18 の "strict partition" を考えてみる。分割の最大成分ごとに分けて書くと、$$
\begin{align}
q_\infty(18) &= 46 \\ &= |\{18\}| \\ &\;+ |\{17+1\}| \\ &\;+ |\{16+2\}| \\ &\;+ |\{15+3,15+2+1\}| \\ &\;+ |\{14+4,14+3+1\}| \\ &\;+ |\{13+5,13+4+1,13+3+2\}| \\ &\;+ |\{12+6,12+5+1,12+4+2,12+3+2+1\}| \\ &\;+ |\{11+7,11+6+1,11+5+2,11+4+3,11+4+2+1\}| \\ &\; \vdots \\ &\;+ |\{7+6+5,7+6+4+1,7+6+3+2,7+5+4+2,7+5+3+2+1\}| \\ &\;+ |\{6+5+4+3,6+5+4+2+1\}|
\end{align}
$$である。そのうち、要素の上限が 7 であるものを考えてみる。
$$\begin{align}
q_7(18) &= 7 \\ &= |\{7+6+5,7+6+4+1,7+6+3+2,7+5+4+2,7+5+3+2+1\}| \\ &\;+ |\{6+5+4+3,6+5+4+2+1\}|
\end{align}$$
当然、18 の "strict partition" の一部として、成分の上限が 7 である 18 の"strict partition" が含まれる。で、その差を考える。
ここで、たとえば $ \{7+6,7+5+1,7+4+2,7+3+2+1\}$ と、それから 7 を除いた $ \{6,5+1,4+2,3+2+1\}|$ が 1 対 1 に対応すると考えて、各分割から最大成分を除去した物を考えて、$$\begin{align}
q_\infty(18) &= |\{0\}| \\ &\;+ |\{1\}| \\ &\;+ |\{2\}| \\ &\;+ |\{3,2+1\}| \\ &\;+ |\{4,3+1\}| \\ &\;+ |\{5,4+1,3+2\}| \\ &\;+ |\{6,5+1,4+2,3+2+1\}| \\ &\;+ |\{7,6+1,5+2,4+3,4+2+1\}| \\ &\; + |\{8,7+1,6+2,5+3,5+2+1,4+3+1\}| \\ &\; + |\{8+1,7+2,6+3,6+2+1,5+4,5+3+1,4+3+2\}| \\ &\; + |\{7+3,7+2+1,6+4,6+3+1,5+4+1,5+3+2,4+3+2\}| \\ &\; + q_7(18) \end{align}
$$となるから、$$
\begin{align}
q_\infty(18) - q_7(18) &= q_0(0) \\ &\;+ q_1(1) \\ &\;+ q_2(2) \\ &\;+ q_3(3) \\ &\;+ q_4(4) \\ &\;+ q_5(5) \\ &\;+ q_6(6) \\ &\;+ q_7(7) \\ &\;+ q_8(8) \\ &\;+ q_8(9) \\ &\;+ q_7(10)
\end{align}$$となる。前回、$$
q_r(r)=q_{r+1}(r)=q_{r+2}(r)= \cdots = q_\infty(r)
$$という関係を示したので、$$
\begin{align}
q_\infty(18) - q_7(18) &= q_{17}(0) \\ &\;+ q_{16}(1) \\ &\;+ q_{15}(2) \\ &\;+ q_{14}(3) \\ &\;+ q_{13}(4) \\ &\;+ q_{12}(5) \\ &\;+ q_{11}(6) \\ &\;+ q_{10}(7) \\ &\; + q_9(8) \\ &\; + q_8(9) \\ &\; + q_7(10) \\ &= \sum_{m=7}^{17}q_k(17-m)
\end{align}
$$とできる。これを一般化すれば、$$\begin{align}
q_\infty(r) - q_n(r) &= \sum_{m=n}^{r-1}q_m(r-(m+1)) \\ &= \sum_{m={n+1}}^r q_{m -1}(r-m)
\end{align}
$$とできそうである。ところで、$$
\begin{cases}
q_0(0)=1 \\ q_n(r)=0 & \qty(r < 0, r > \frac{n(n+1)}{2}) \\ q_n(r) = q_{n-1}(r)+q_{n-1}(r-n)
\end{cases}
$$という漸化式を思い出すと、右辺は$$
\begin{align}
& \sum_{m={n+1}}^r q_{m -1}(r-m) \\ =& \sum_{m={n+1}}^r \{ q_m(r) - q_{m -1}(r) \} \\ =& -\sum_{m={n+1}}^r \left\{ q_{m -1}(r) - q_m(r) \right\} \\ =& -[ \{q_n(r) - q_{n+1}(r)\} + \{q_{n+1}(r) - q_{n+2}(r)\} + \cdots \\ &\; + \{q_{r -2}(r) - q_{r -1}(r)\} + \{q_{r -1}(r) - q_r(r)\} ] \\ =& -\{ (q_n(r) - q_r(r) \} \\ =&\; q_r(r) - q_n(r)
\end{align}
$$と変形できて、$ q_r(r) = q_\infty(r)$ であるから、左辺と等しいことがわかる。
この総和部分はその変数が動く範囲からわかるように $ n+1 \leq r$ のときのみ効いてくるわけであって、逆に言えば $ n \geq r$ のときは $ 0$ である。前回、$ n \geq r$ のとき $ q_n(r) = q_\infty(r)$ となることを示したので当然の結果だ。
続かない気がする。
(1+x^k) の乗積を展開したときの係数・その 3
前回の続きとして、$$\begin{cases} q_0(0)=1 \\ q_n(r)=0 & \qty(r < 0, r > \frac{n(n+1)}{2}) \\ q_n(r) = q_{n-1}(r)+q_{n-1}(r-n) \end{cases}$$という（一般化された）漸化式で表される数列 $ q_n(r)$ を調べる。
$ q_n(r)$ を書き出してみた表を発展させる。
| n\r | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | … |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | |||||||||||||||||
| 1 | 1 | 1 | ||||||||||||||||
| 2 | 1 | 1 | 1 | 1 | ||||||||||||||
| 3 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | |||||||||||
| 4 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | |||||||
| 5 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 1 | 1 | 1 | ||
| ∞ | 1 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 6 | 8 | 10 | 12 | 15 | 18 | 22 | 27 | 32 | … |
$ n \to \infty$ の場合の極限を $ q_\infty(r)$ と書くことにして、それも表に入れてみた。この数列 $ q_\infty(r)$ は初回に少し触れた "strict partition" の数を示す物であり、例によってオンライン整数列大辞典にある。
上表では少しわかりにくいが、$ r$ を固定して縦の変化を見たとき、$ q_n(r)$ は $ n=r$ のとき以来、値が変化しない。つまり、その時点で極限値たる $ q_\infty(r)$ に収束しているわけで、次のような等式が得られる。$$q_r(r)=q_{r+1}(r)=q_{r+2}(r)= \cdots = q_\infty(r)$$
要するに、$ n \geq r$ において、$$q_n(r)= q_\infty(r)$$である。表の対角線を含むその下側を見れば "strict partition" が見えるよ、というお話。
これは漸化式からも容易にわかることであり、$ n \geq r$ のとき、正の整数 $ k$ に対して $ n+k > r$ であるから、 $ r-n-k < 0$ である。そのとき、$ q_{n}(r-n-k) = 0$ であるから、$$q_{n+k}(r) = q_{n+k -1}(r)+q_n(r-n-k) = q_{n+k -1}(r)$$という具合である。
自然数の分割という観点からもこれは明らかにわかる。たとえば、6 の分割に 7 以上の整数は登場しえないわけで、分割の成分の上限を 6 より大きな整数と定めたり、上限を撤去したところで、それは上限を 6 に定めた場合と同じ結果が生じるという話だ。
続く。
(1+x^k) の乗積を展開したときの係数・その 2
乗積$$\begin{align} Q_n(x) &= (1+x)(1+x^2)(1+x^3) \cdots (1+x^n) \\ &= \prod_{k=1}^{n}(1 + x^k) \end{align}$$に対して、多項式$$\begin{align} Q_n(x) &= q_n(0) + q_n(1)\,x + q_n(2)\,x^2 + \cdots + q_n \left(\frac{n(n+1)}{2} \right)\,x^\frac{n(n+1)}{2} \\ &= \sum_{r=0}^{\frac{n(n+1)}{2}}q_n(r)\,x^r \end{align}$$を考える続き。
とりあえず、$q_n(r)$ を書き出してみる試み。
| n\r | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | |||||||||||||||
| 1 | 1 | 1 | ||||||||||||||
| 2 | 1 | 1 | 1 | 1 | ||||||||||||
| 3 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | |||||||||
| 4 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | |||||
| 5 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 1 | 1 | 1 |
この数の並びから何が読み取れるか。
ところで、乗積形より明らかに、$$\begin{align} Q_{n+1}(x) &= Q_n(x) \cdot (1+x^{n+1}) \\ &= Q_n(x) + x^{n+1}\,Q_n(x) \end{align}$$である。
さらに、一般に母関数の性質として、$x^n \cdot F(x)$ は $F(x)$ の係数列を $n$ だけ「右シフト」する操作である（推移則っていうの？）。また、線型性から、母関数同士の和は母関数の係数同士を加える操作である。たとえば、$q_5(6) = q_4(6)+q_4(1)$ であることが上表からも見えるわけだが、便宜上 $r$ を整数全体に拡張して、上表における右側の空白、すなわち $r > \frac{n(n+1)}{2}$ の領域と左側、すなわち $r < 0$ において、$q_n(r) = 0$ と定義した無限列として扱うことにすると、$$Q_n(x) = \sum_{r=0}^\infty q_n(r)\,x^r$$なる母関数で表せる $q_n(r)$ であることになる。さらに先程の母関数の関係も踏まえて、$$\begin{cases} q_0(0)=1 \\ q_n(r)=0 & \left(r < 0, r > \frac{n(n+1)}{2}\right) \\ q_n(r) = q_{n-1}(r)+q_{n-1}(r-n) \end{cases}$$という漸化式を導ける。めでたし。
さて、この数列が オンライン整数列大辞典 で発見されたわけだが。
うむ、リンク先の解説記事みたいになってしまっているなぁ。
もうちっとだけ続くんじゃ？
(1+x^k) の乗積を展開したときの係数
何年か前になぜか気になって、でもそのままにしていた問題をシンプルにした物だが、数学熱が高いことを理由に改めて考えてみた。
今気にしている式は、$$\begin{align} Q_n(x) &= (1+x)(1+x^2)(1+x^3) \cdots (1+x^n) \\ &= \prod_{k=1}^{n}(1 + x^k)\end{align}$$である。この $Q_n(x)$ は $x$ の $\frac{n(n+1)}{2}$ 次式であるが、これを展開するとどうなるのかという問題。まず、展開すると、次のような形の多項式となる。$$\begin{align} Q_n(x) &= a_0 + a_1\,x + a_2\,x^2 + \cdots + a_\frac{n(n+1)}{2}\,x^\frac{n(n+1)}{2} \\ &= \sum_{r=0}^{\frac{n(n+1)}{2}}a_r\,x^r \end{align}$$
で、具体的な係数 $a_r$ が欲しいよね、というお話である。
少し扱いづらいので、$Q_n(x)$ における $x^r$ の係数を $q_n(r)$ と書くことにすると、$$Q_n(x) = \sum_{r=0}^{\frac{n(n+1)}{2}}q_n(r)\,x^r$$と書ける。
正確さを欠く説明をすれば、実際の展開を考えたとき、$r$ 次の項は、$\{x^k\}$ から最大で $n$ 個選び、掛け合わせたときに $x^r$ になりました、という組み合わせから生じる。で、その積 $x^r$ がいくつか生じたものの和が最終的な $r$ 次の項となり、その係数 $q_n(r)$ は組み合わせの総数に等しい。つまり、指数法則の面から見れば、$n$ 以下の自然数から重複を許さずいくつか選び、それらの和が $r$ となる組み合わせの総数である。
さらに別の言い方をすれば、「自然数 $r$ の分割、すなわち $r$ を（必然的に $r$ 以下の）自然数の和で表す方法のうち、それぞれの分割方法において、成分がすべて異なり（制限その 1）、かつ、成分がすべて $n$ 以下（制限その 2）であるもの」の数が $q_n(r)$ であると。
俺の苦手な初等整数論とかの話になってきたぞ。
具体的に、$Q_4(x)$ を見てみる。$$\begin{align} Q_4(x) &= (1+x)(1+x^2)(1+x^3)(1+x^4) \\ &= 1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^{10} \end{align}$$
係数の構成要素は次のようになる。$$\begin{cases} q_4(1)=|\{1\}|=1 \\ q_4(2)=|\{2\}|=1 \\ q_4(3)=|\{3,\,2+1\}|=2 \\ q_4(4)=|\{4,\,3+1\}|=2 \\ q_4(5)=|\{4+1,\,3+2\}|=2 \\ q_4(6)=|\{4+2,\,3+2+1\}|=2 \\ q_4(7)=|\{4+3,\,4+2+1\}|=2 \\ q_4(8)=|\{4+3+1\}|=1 \\ q_4(9)=|\{4+3+2\}|=1 \\ q_4(10)=|\{4+3+2+1\}|=1 \end{cases}$$
例によって $r=0$ は $0$ 次の項を 4 つ掛けた 1 つの場合を考えるので、$q_4(0)=1$ なのである。上記の分割方法において、4 つの整数に満たない部分は $0$ で埋めるとすれば、$$q_4(0)=|\{0+0+0+0\}|=1$$ であり、同様に
$$q_4(3)=|\{3+0+0+0,\,2+1+0+0\}|=2$$であるので同じことであるというか、指数部の成り立ちとしてはこちらの表記のほうが無難であろう。
それはさておき、$Q_n(x)$ はそういう数 $q_n(r)$ を表す母関数と考えられる。もちろん、$r > \frac{n(n+1)}{2}$ なる $r$ については、その上記の 2 つの制限を満たすような分割は存在しないので、そのような $r$ に関しては $q_n(r)=|\{\}|=0$ と定義することができて、より一般的な母関数のように $Q_n(x)$ を$$Q_n(x) = \sum_{r=0}^\infty q_n(r)\,x^r$$といった冪級数で表すことも可能である。また、母関数の常套手段であるマクローリン展開同様のアプローチで、$$q_n(r) = \frac{Q_n^{(r)}(0)}{r!}$$と閉じた形で表せるわけだが、この高階微分を計算するときに上記の分割の話に舞い戻る。
ところで、Wikipedia にはは上記の制限 2 を除去した場合、つまり $n \to \infty$ の極限をとった場合と思われる話があったぞ。
それはそれは有名というか有用というか、メジャーな議論のようで、このような分割は "strict partition" と呼ぶらしく、下記において Partition Function Q として紹介されている。
この辺の性質は数論の人が詳しく解明しているのだろう。
続く。
マニアのための n 倍角・その 3
前回は 7 年近く前に書いた マニアのための n 倍角・証明 であるが、これは $\sin$ の $n$ 倍角、すなわち $\sin n\theta$ を $\sin(\theta+\alpha)$ の有限積で表すものであった。つまり、$$\sin n\theta = 2^{n-1} \prod_{k=0}^{n-1} \sin(\theta + \frac{k}{n}\pi)$$と表せるということを示した。
さて、左辺を $\theta$ で微分してみる。
$$\frac{d}{d\theta}\sin n\theta = n \cos n\theta$$
では同様に右辺を $\theta$ で微分してみるわけだが、積の微分法則の復習 で導出した、$$\begin{align} \frac{d}{dx}\prod_k f_k &= \qty( \sum_k \qty(\frac{df_k}{dx} \cdot \frac{1}{f_k} ) )\prod_k f_k \end{align}$$となる関係を用いることで、
$$\begin{align}
&\phantom{{}={}} \frac{d}{d\theta} \qty(2^{n-1} \prod_{k=0}^{n-1} \sin(\theta + \frac{k}{n}\pi) ) \\
&= 2^{n-1} \frac{d}{d\theta} \prod_{k=0}^{n-1} \sin(\theta + \frac{k}{n}\pi) \\
&= 2^{n-1} \qty[ \sum_{k=0}^{n-1} \qty(\qty(\frac{d}{dx}\sin(\theta + \frac{k}{n}\pi) ) \cdot \frac{1}{\sin(\theta + \frac{k}{n}\pi)} ) ] \prod_{k=0}^{n-1} \sin(\theta + \frac{k}{n}\pi) \\
&= \qty[ \sum_{k=0}^{n-1} \frac{\cos(\theta + \frac{k}{n}\pi)}{\sin(\theta + \frac{k}{n}\pi)} ] \cdot 2^{n-1} \prod_{k=0}^{n-1} \sin(\theta + \frac{k}{n}\pi) \\
&= \qty[ \sum_{k=0}^{n-1} \cot(\theta + \frac{k}{n}\pi) ] \cdot \sin n\theta
\end{align}$$となるわけである。すなわち、
$$n \cos n\theta = \qty[ \sum_{k=0}^{n-1} \cot(\theta + \frac{k}{n}\pi) ] \cdot \sin n\theta$$であるので、$$\cot n\theta = \frac{1}{n} \sum_{k=0}^{n-1} \cot(\theta + \frac{k}{n}\pi)$$
となって、$\cot$ の $n$ 倍角、すなわち $\cot n\theta$ が $\cot(\theta+\alpha)$ の有限和で表されることがわかる。何かしら図形的な意味を見いだせるのであろうか。
積の微分法則の復習
今回は積の微分の公式をいじる。
$x$ の関数である 2 関数 $f(x),\,g(x)$ の積を $x$ で微分すると、$$
\dv{x} \qty(f(x)g(x) ) = \qty( \dv{x} f(x) )g(x) + f(x) \qty(\dv{x} g(x) )
$$となるわけである。一般に複数の関数の積で表される $f(x) = \prod_k f_k(x)$ という関数の微分であっても、これを再帰的に適用することで同様の関係が得られる。
$$\begin{align} \dv{f}{x} &= \dv{x}\prod_k f_k \\ &= \sum_k \qty(\dv{f_k}{x} \cdot \prod_{i \ne k} f_i ) \end{align}$$
さらに（形式的に）変形すると、
$$\begin{align} \dv{f}{x} &= \sum_k \qty(\dv{f_k}{x} \cdot \frac{1}{f_k} \prod_i f_i ) \\ &= \qty(\sum_k \qty(\dv{f_k}{x} \cdot \frac{1}{f_k} ) )\prod_k f_k \\ &= \qty(\sum_k \qty(\dv{f_k}{x} \cdot \frac{1}{f_k} ) )f \end{align}$$となり、対称性を意識すれば、$$\begin{align} \dv{f_k}{x} \cdot \frac{1}{f} &= \sum_k \qty(\dv{f_k}{x} \cdot \frac{1}{f_k} ) \end{align}$$と書ける。この両辺を積分すれば、分子が分母の微分の形なので $\log$ なんちゃらが出てくるが、それを外せば（絶対値記号付きで）元の式が出てきそうであることがわかる。
