2015/10/10

交代順列の数とタンジェント数,セカント数

分野: 場合の数  レベル: マニアック

交代順列の数とタンジェント数,セカント数が等しいという感動的な定理について紹介します。

交代順列の数

$1,2,\cdots, n$ の並び替えで,増減増減 $\cdots$ となるものを,要素数 $n$ の交代順列と言います。ジグザグな順列です。

例題

要素数 $4$ の交代順列の数を求めよ。

解答

実際に列挙すると,$1 3 2 4$,$1 4 2 3$,$2 3 1 4$,$2 4 1 3$,$3 4 1 2$ の5つです。

この記事では要素数 $n$ の交代順列の数 $c_n$ について考えます。

タンジェント数とセカント数

$\tan x$ の $n$ 次導関数の $x=0$ での値をタンジェント数(以下 $a_n$ で表す)と言います。

マクローリン展開の形で書くと,
$\tan x=a_1x+\dfrac{a_3}{3!}x^3+\dfrac{a_5}{5!}x^5+\cdots$
となります。 $\tan x$ は奇関数であり,マクローリン展開をしたときに偶数次の項は登場しません。つまり,$n$ が偶数のとき,$a_n=0$ です。実際に計算すると $a_1=1$,$a_3=2$,$a_5=16$ です。


$\sec x=\dfrac{1}{\cos x}$ の $n$ 次導関数の $x=0$ での値をセカント数(以下 $b_n$ で表す)と言います。

マクローリン展開の形で書くと,
$\dfrac{1}{\cos x}=b_0+\dfrac{b_2}{2!}x^2+\dfrac{b_4}{4!}x^4+\cdots$
となります。 $\sec x$ は偶関数であり,マクローリン展開をしたときに奇数次の項は登場しません。つまり,$n$ が奇数のとき,$b_n=0$ です。実際に計算すると $b_0=1$,$b_2=1$,$b_4=5$ です。

アンドレの定理

交代順列の数 $c_n$ は,
$n$ が奇数のときタンジェント数 $a_n$ と等しい
$n$ が偶数のときセカント数 $b_n$ と等しい

感動的な定理ですね!例えば,$\dfrac{1}{\cos x}$ を頑張って $10$ 回微分して $x=0$ を代入すると $50521$ になるので,要素数 $10$ の交代順列の数は $50521$ 通りだと分かります。

実際に計算する際は何回も微分するのは大変なので,動的計画法(漸化式を立てて $n$ が小さいものから順に $a_n$,$b_n$ を求めていく方法)を使います。

定理の証明の概略

定理の証明はかなり大変なので非常に大雑把な流れのみ紹介します。微分方程式も登場します(高校数学範囲外です)。

証明の概略

組み合わせ的な議論により,$n\geq 1$ のとき
$2c_{n+1}=\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_kc_kc_{n-k}$
という漸化式が成立することが分かる。

$f(x)=\displaystyle\sum_{n=0}^{\infty}\dfrac{c_n}{n!}x^n$
という関数を考える(ただし $c_0=0$)。上記の漸化式を使うと $1+f(x)^2=2f'(x)$ という微分方程式が成立することが分かる。

この微分方程式の一般解は $f(x)=\tan\left(\dfrac{x}{2}+C\right)$ となる(ただし $C$ は任意定数)。ここで,$f(0)=1$ に注意すると $C=\dfrac{\pi}{4}$ となる。よって $f(x)=\tan\left(\dfrac{x}{2}+\dfrac{\pi}{4}\right)$

半角の公式などを用いると,$\tan\left(\dfrac{x}{2}+\dfrac{\pi}{4}\right)=\tan x+\dfrac{1}{\cos x}$ という恒等式が成立することが分かる。以上より $f(x)=\tan x+\dfrac{1}{\cos x}$ が分かり,両辺の係数を比較すると定理を得る。

なお,証明の概略は英語版Wikipediaを参考にしました。→Alternating Permutation

最近サーバーの調子イマイチです。一時的にサイトが閲覧できなかった,などの問題があればご一報ください。
分野: 場合の数  レベル: マニアック