2018-09-28

他己紹介の場合の数

他己紹介とは， $n$ 人の参加者が一人づつ自分以外の誰かを紹介し，結果的に $n$ 人全員が自分以外の誰かから紹介されるようにすることです．

太郎，次郎，三郎，四郎の４人が参加者とすると，例えば
太郎は三郎を紹介．
次郎は太郎を紹介．
三郎は四郎を紹介．
四郎は次郎を紹介．
すると，これは一つの他己紹介になります．

参加者が $n$ 人いるとき，何通りの他己紹介が可能か気になりますよね？
調べましょう．

上の太郎の例からすぐ分かるように， $n$ 人の他己紹介は不動点を持たない $n$ 文字の置換にほかなりません．
この数え上げ問題は撹乱の問題と呼ばれ，WikipediaによるとMontmortや Nicholas Bernoulliにより１８世紀初頭に研究されたそうです．

場合の数に関する漸化式を立てて代数的に解く方法もあるようですが，ここでは次の包除原理と呼ばれる定理を用います．

定理（包除原理, [1]）
集合 $X$ を $X\triangleq\{1,\ldots,n\}$ とする．二つの写像 $f,g\colon 2^X\to \mathbb{C}$ に関する以下の二つの主張は同等である．

すべての $S\subseteq X$ に対し $g(S)=\sum_{T\subseteq S}f(T)$ .
すべての $S\subseteq X$ に対し $f(S)=\sum_{T\subseteq S}(-1)^{|S\setminus T|}g(T)$ .

命題([1])
自然数 $n$ に対し， $n$ 人で他己紹介を行う場合の数は
$\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}k!$ 通りである．
証明
集合 $X$ を $X\triangleq\{1,\ldots,n\}$ とする．
写像 $f\colon 2^X\to \mathbb{C}$ を， $S\subseteq X$ に対し
$f(S)\triangleq(S$ 上では不動点を持たず， $X\setminus S$ の点は不動点であるような $X$ の置換の数 $)$
と定義する．
このとき $S\subseteq X$ に対し $\sum_{T\subseteq S}f(T)$ は全ての $S$ の置換の数を表すので
$|S|!=\sum_{T\subseteq S}f(T)$ である．
包除原理より $S\subseteq X$ に対し
$f(S)=\sum_{T\subseteq S}(-1)^{|S\setminus T|}|T|!$ ．

今求めたいのは $S=X$ の場合なので代入すると，不動点を持たない $X$ の置換の数は
$f(X)=\sum_{T\subseteq X}(-1)^{|X\setminus T|}|T|!=\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}k!$ である．
（終）

得られた量はさらに次のように評価できることが知られています．

命題([2])
自然数 $n$ に対し， $n$ 人で他己紹介を行う場合の数は
$n!/e$ に一番近い整数である．但し $e$ はネイピア数 $=2.71828\ldots$ ．
証明
前の命題の記号をそのまま用いる．
$|n!/e - f(X)|=|n!\sum_{k=0}^\infty (-1)^{k}/k! - \sum_{k=0}^n\binom{n}{k}(-1)^{n-k}k!|$ .
$\binom{n}{k}=n!/k!(n-k)!$ を代入して計算すると
$|n!/e - f(X)|=\frac{1}{n+1}|1-\frac{1}{n+2}+\frac{1}{(n+2)(n+3)}-\frac{1}{(n+2)(n+3)(n+4)}+\cdots$ ad. inf. $|$ .
ここから
$\frac{1}{n+2}\leq |n!/e - f(X)| \leq \frac{1}{n+1}$ を得る．
値 $f(X)$ は整数なことから，所望の結果が言える．
（終）

これにより例えば，７人で他己紹介をする場合の数は1854通りです．

参考文献
[1] Richard P. Stanley. (2011) "Enumerative Combinatorics," Volume 1, second edition. v. 15. p. 227.
[2] Ronald L. Graham, Donald E. Knuth, Oren Patashnik. (1994) "Concrete Mathematics," second edition. p.195.

2018-09-27

x_1+...+x_n=k の非負整数解の個数

命題：
自然数 $n,k$ が与えられたとき，方程式 $x_1+\cdots +x_n=k$ の非負整数解の個数は $\binom{n+k-1}{k}$ 個である．

証明１：
$k$ 個の玉「●」と $n-1$ 個のしきり「｜」を直線上に並べる場合の数だと思えるので $\binom{n+k-1}{k}$ 通りである．
（終）

証明２：
方程式 $x_1+\cdots +x_n=k$ の非負整数解の集合から
集合 $B\triangleq\{(b_1,\ldots,b_k)\in\mathbb{N}^k\mid 1\leq b_1\leq \cdots \leq b_k \leq n\}$ への全単射が存在する．
また，集合 $B$ から集合 $C\triangleq\{(c_1,\ldots,c_k)\in\mathbb{N}^k\mid 1\leq c_1 \lt \cdots \lt c_k \leq n+k-1\}\}$ への全単射を $c_i\triangleq b_i+i-1$ と作れる．
集合 $C$ の濃度は $\binom{n+k-1}{k}$ である．
（終）

興味：
変数 $x_i$ に係数がつくとどうなるだろうか？

参考：Richard P. Stanley. (2011) "Enumerative Combinatorics," Volume 1, second edition. v. 15. p. 27.

2018-07-13

直交多項式列の同値な定義

解析

複素数係数一変数多項式の全体 $\mathbb{C}[x]$ を通常の和と複素数によるスカラー倍により $\mathbb{C}$ -線形空間とみなす．

Theodore S. Chihara. (1978) "An introduction to orthogonal polynomials," p. 8.

複素数係数多項式の列 $(P_n(x))_{n=0}^{\infty}$ が与えられていて $\rm{deg}{P_n(x)}=n$ を満たすとする．また線形写像 $\mathcal{L}: \mathbb{C}[x] \to \mathbb{C}$ が与えられているとする．このとき次の二つの主張 (a), (b)は同値である．
(a) 二つの整数 $n,m \geq 0$ が異なるとき $\mathcal{L}[P_m(x)P_n(x)]=0$ .
また任意の整数 $n\geq 0$ に対し $\mathcal{L}[P_n^2(x)]\neq 0$ .
(b) 二つの整数 $n,m\geq 0$ が異なるとき $\mathcal{L}[x^mP_n(x)]=0$ .
また任意の整数 $n\geq 0$ に対し $\mathcal{L}[x^nP_n(x)]\neq 0$ .

2018-07-10

自然数 n のcompositionの数

自然数の列 $\alpha=(a_1,a_2,\ldots,a_k)$ が $\sum_{k\geq 0}a_k=n$ を満たすとき， $\alpha$ を自然数 $n$ のcomposition (構成: iwalion訳)という．列の長さのことを，構成の長さと呼ぶ．

メモ：構成は要素に線形順序のついた分割ともいえる．
例えば列 $(1,1,2)$ と列 $(1,2,1)$ は長さ $3$ の異なる $4$ の構成である．

Richard P. Stanley. (2011) "Enumerative Combinatorics," Volume 1, second edition. v. 15. p. 25.
自然数 $n$ の長さ $k$ の構成の個数は $\binom{n-1}{k-1}$ 個である．
自然数 $n$ の構成の総数は $2^{n-1}$ 個である．