|
|
> No.1971[元記事へ]
ＧＡＩさんへのお返事です。
解
n個の球をm個の箱に分ける方法
●分割の仕方を数える（分割数）
・和の順序を区別する
> （３）相異なる７個の球を、相異なる３個の箱に少なくとも１個配る方法は何通り？
> （９）相異なる７個の球を、区別できない３個の箱に少なくとも１個配る配り方は何通り？
> （６）区別できない７個の球を、相異なる３個の箱に少なくとも１個配る配り方は何通り？
!問題
!(1)
!相異なるn個のボールと区別のつくm個の箱がある。
!各箱にボールを1個以上配る配り方は何通りあるか。
!(2)
!相異なるn個のボールと区別のつかないm個の箱がある。
!各箱にボールを1個以上配る配り方は何通りあるか。
!(3)
!同種類のn個のボールと区別のつくm個の箱がある。
!各箱にボールを1個以上配る配り方は何通りあるか。
!
!答え
!第2種スターリング数 S2(n,m)とすると、
!(1) m!S2(n,m) (2) S2(n,m) (3) C(n-1,m-1)
LET N=7 !1≦N
LET M=3 !1≦M≦N
DIM A(1 TO M) !分け方（要素数）
PUBLIC NUMERIC C !解 m!S2(n,m)
LET C=0
PUBLIC NUMERIC F !分割数
LET F=0
CALL try(1,N,M,A,0)
PRINT C;"通り" !(1)の解
PRINT C/FACT(M);"通り" !(2)の解
PRINT F;"通り" !(3)の解
PRINT FACT(M)*StirlingS2(n,m);"通り" !(1)の解
PRINT StirlingS2(n,m);"通り" !(2)の解
PRINT COMB(N-1,M-1);"通り" !(3)の解
END
EXTERNAL SUB try(P,N,M,A(),S) !各箱に配るボールの個数に着目して、数え上げる。
!例 N=7,M=3の場合
!和の順序を区別する分割数p(n,m)を考える。
!たとえば、1+1+5、1+5+1、5+1+1の3種類ある。
FOR i=1 TO N-(M-1) !自然数nをm個の自然数の和で表す
LET W=S+i
IF W>N THEN EXIT FOR !これ以降は可能性なし！
LET A(P)=i !p番目は数字iとする
IF P<M THEN
CALL try(P+1,N,M,A,W) !次へ
ELSE
IF W=N THEN !すべて並んだら
MAT PRINT A; !debug
!並び c, … ,b,a として、
! C(a,a) * C(a+b,b) * … * C(a+b+ … +c,c)
!のように、式を逆から順に遡る。
!例 N=7,M=3の場合
! 1,1,5 なら、並べ方は、7!/(1!1!5!) = C(7,1)C(6,1)C(5,5) 通りである。
! 1,5,1 なら、並べ方は、7!/(1!5!1!) = C(7,1)C(6,5)C(1,1) 通りである。
! 5,1,1 なら、並べ方は、7!/(5!1!1!) = C(7,5)C(2,1)C(1,1) 通りである。
! 以下、同様
! 1,2,4 なら、7!/(1!2!4!) = C(7,1)C(6,2)C(4,4)
! 1,3,3 なら、7!/(1!3!3!) = C(7,1)C(6,3)C(3,3)
! 2,2,3 なら、7!/(2!2!3!) = C(7,2)C(5,2)C(3,3)
LET X=1 !場合の数
LET D=0 !個数の総数
FOR K=M TO 1 STEP -1
LET E=A(K)
LET D=D+E
LET X=X*COMB(D,E) !重複を削除する
NEXT K
PRINT X !debug
LET C=C+X !累計
LET F=F+1 !分割数
END IF
END IF
NEXT i
END SUB
EXTERNAL FUNCTION StirlingS2(n,m) !第2種スターリング数 ※公式による
LET s=0
FOR k=0 TO m-1 !包除原理より
LET s=s+(-1)^k*COMB(m,k)*(m-k)^n
NEXT k
LET StirlingS2=s/FACT(m)
END FUNCTION
・和の順序を区別しない
> （１２）区別できない７個の球を、区別できない３個の箱に少なくとも１個配る配り方は何通り？
> （１０）区別できない３個の球を、区別できない７個の箱に自由に配る方法は何通り？
!問題
!(4) n≧mのとき
!同種類のn個のボールと区別のつかないm個の箱がある。
!各箱にボールを1個以上配る配り方は何通りあるか。
!(4')
!同種類のn個のボールと区別のつかないm個の箱がある。
!各箱にボールを配る配り方（空箱があってよい）は何通りあるか。
!
!答え
!和の順序を区別しない分割数 p(n,m)とすると、
!(4) p(n,m) (4') Σ[k=1,m]p(n,k) ※区別のつかない箱なので、C(m,k)は付かない
LET N=7 !1≦N
LET M=3 !1≦M≦N
DIM A(0 TO M) !分け方（要素数） ※0は番兵
LET A(0)=1
PUBLIC NUMERIC C !解 p(n,m)
LET C=0
CALL try(1,N,M,A,0)
PRINT C;"通り" !(4)の解
LET CC=0
FOR k=1 TO M !Σ[k=1,m]p(n,k)
MAT A=ZER
LET A(0)=1
LET C=0
CALL try(1,N,k,A,0)
LET CC=CC+C
NEXT k
PRINT CC;"通り" !(4')の解
!検算
LET CC=0
FOR k=1 TO M !Σ[k=1,m]p(n,k)
LET CC=CC+p(n,k)
NEXT k
PRINT CC;"通り" !(4')の解
END
EXTERNAL SUB try(P,N,M,A(),S) !各箱に配るボールの個数に着目して、数え上げる。
!例 N=7,M=3の場合
!和の順序を区別しない分割数p(n,m)を考える。
!たとえば、1+1+5、1+5+1、5+1+1の3種類あるが、
!1+1+5 のみとする。（和の順序を区別しない）
FOR i=A(P-1) TO N-(M-1) !自然数nをm個の自然数の和で表す ※昇順のみ
LET W=S+i
IF W>N THEN EXIT FOR !これ以降は可能性なし！
LET A(P)=i !p番目は数字iとする
IF P<M THEN
CALL try(P+1,N,M,A,W) !次へ
ELSE
IF W=N THEN !すべて並んだら
MAT PRINT A; !debug
LET C=C+1
END IF
END IF
NEXT i
END SUB
EXTERNAL FUNCTION p(n,k) !分割数（partition number）
IF k=1 OR k=n THEN !p(n,1)=p(n,n)=1
LET p=1
ELSEIF n<k THEN
LET p=0
ELSE !p(n,k)=p(n-k,k)+p(n-1,k-1)
LET p=p(n-k,k)+p(n-1,k-1)
END IF
END FUNCTION
|
|