ryamadaのコンピュータ・数学メモ

2012-05-12

場合の数

R 割り付け

k人いて、その名札がk枚あって、割り付ける。k人全員に正しい名札を割り付けることもある(完璧な割り付け)し、全員に間違った名札を割り付けることもある
k人のうち、一部には名札を割り付け、残りは間違っていることもある(不完全な割り付け)
k人のうちk-i人に正しく割り付け、残りのi人は誰一人として正しい名札持たないような割り付けの場合の数はいくつあるかを計算しよう
$N(k,i)$ をそのような場合の数とする
任意のkについて、 $\sum_{i=0}^k N(k,i) = k!$ が成り立つ
あるkについての $N(k,i)$ というのは、 $\begin{pmatrix}k\\i\end{pmatrix}$ の選び方ごとに $N(i,i)$ の場合の数が取れるので $N(k,i)=\begin{pmatrix}k\\i\end{pmatrix} N(i,i)$ という関係にある
ここで $N(0,0)=1$ とすると
[tex:N(k,i),i
その方法で求まらない $N(k,k)$ は条件 $\sum_{i=0}^k N(k,i) = k!$ から $N(k,k)=k!-\sum_{i=0}^{k-1} N(k,i)$ で求まるので結局…

Waritsuke3<-function(k){
	ret<-matrix(0,k+1,k+1)
	ret[1,1]<-1
	f<-factorial(0:k)
	for(i in 2:(k+1)){
		for(j in 1:i){
			if(j==i){
				ret[i,j]<-f[i]-sum(ret[i,])
			}else{
				ret[i,j]<-f[i]/(f[j]*f[i-j+1])*ret[j,j]
			}
		}
	}
	ret
}

Waritsuke3(k=5)

以下は $N(k,i)$ が第(k+1)行、第i+1列のセルの値を表している

> Waritsuke3(k=5)
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    1    0    0    0    0    0
[2,]    1    0    0    0    0    0
[3,]    1    0    1    0    0    0
[4,]    1    0    3    2    0    0
[5,]    1    0    6    8    9    0
[6,]    1    0   10   20   45   44