|
|
> No.3203[元記事へ]
問題：n個の球をm個の箱に分ける方法
関係図 m進法n桁の数による
0
(2) → (1)
f↓ ↓f
(4) → (3)
0
とする手法があるが、m^nが10^9程度になると、場合の数を数え上げるのが困難になる。
そこで、条件に合うm進法n桁の数を生成することを考える。
答え (3)
(7)の結果より、箱の中の球の個数は、[●] [●] [●●●] と [●] [●●] [●●] の2通り。
[●] [●] [●●●] の場合
箱の番号 1,2,3,3,3 と考えると、
5!/(1!1!3!)=20通り
は、3進法5桁（各位の数は1,2,3とする）の並び方となる。例 12333, 13233,13323,…,33321
1個の並び2!=2通りが重複する（例 ①②333と②①333）ので、20/2=10通り
[●] [●●] [●●] の場合
1,2,2,3,3 と考えると、5!/(1!2!2!)=30通り
2個の並び2!=2通りが重複するので、30/2=15通り
よって、10+15=25通りとなる。
（終り）
関係図 同じものを含む順列
(5):1 → (1)
(6):0 → (2)
(7):1 → (3)
(8):0 → (4)
以上を、プログラムに反映させる。
!(1) n＜mなら0なので、n≧mのとき
!相異なるn個の球と区別のつくm個の箱がある。
!各箱に球を1個以上配る配り方は何通りあるか。
PUBLIC NUMERIC N,M
LET N=5
LET M=3
DIM A(N) !n個の球 値は、箱の番号
DIM B(M) !m個の箱 値は、球の個数
PUBLIC NUMERIC C !場合の数
LET C=0
CALL try(1,1,N,A,B)
PRINT C;"通り"
PRINT FACT(m)*StirlingS2(n,m);"通り" !検算
PRINT
!(2)
!相異なるn個の球と区別のつくm個の箱がある。
!各箱に球を配る配り方（空箱があってよい）は何通りあるか。
LET C=0
CALL try(1,0,N,A,B)
PRINT C;"通り"
PRINT M^N;"通り" !検算
END
EXTERNAL SUB try(P,S,T,A(),B())
IF P>M THEN !最後の箱まで配って、
IF T=0 THEN !球を残らず配り終えたなら
CALL stub(N,M,A,B)
END IF
ELSE
FOR i=S TO T !p番目の箱 B(1)≦B(2)≦B(3)≦…≦B(p)
LET B(P)=i
CALL try(P+1,S,T-i,A,B) !(5),(6)
NEXT i
END IF
END SUB
EXTERNAL SUB stub(N,M,A(),B()) !同じ球● を 異なる球① へ
LET K=0 !最初のパターン
FOR J=1 TO M
FOR X=1 TO B(J)
LET A(K+X)=J
NEXT X
LET K=K+B(J)
NEXT J
MAT PRINT A; !debug
DO
LET C=C+1
PRINT STR$(C); ": "; !結果を表示する
FOR J=1 TO M !j番目の箱
PRINT "[";
FOR K=1 TO N
IF A(K)=J THEN PRINT K; !球の番号
NEXT K
PRINT "]";
NEXT J
PRINT
CALL NextPermFactorial(A,N, rc) !次へ
LOOP UNTIL rc<>0
END SUB
EXTERNAL SUB NextPermFactorial(A(),N, rc) !辞書式順序で次の順列を返す ※「異なるn個のもの」と共通
LET i=N-1 !順列を右から左にみて、増加列から減少列に変わる位置iを探す
DO WHILE i>0 AND A(i)>=A(i+1) !０は番人
LET i=i-1
LOOP
IF i=0 THEN !A(1)>A(2)>A(3)> … >A(N)なら 例. N=4、4,3,2,1
LET rc=1 !完了（最後の並びである）
EXIT SUB
END IF
LET j=N !その位置iより右で、A(i)以上で最小の数A(j)を探す
DO WHILE A(i)>=A(j)
LET j=j-1
LOOP
LET t=A(i) !A(i)とA(j)を交換する
LET A(i)=A(j)
LET A(j)=t
LET i=i+1 !(i+1)からNまでの範囲を逆順にする
LET j=N
DO WHILE i<j
LET t=A(i) !swap it
LET A(i)=A(j)
LET A(j)=t
LET i=i+1
LET j=j-1
LOOP
LET rc=0 !未了
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
上記をベースに考える。青色の字は修正、赤色の字は追加して、
!(3) n＜mなら0なので、n≧mのとき
!相異なるn個の球と区別のつかないm個の箱がある。
!各箱に球を1個以上配る配り方は何通りあるか。
PUBLIC NUMERIC N,M
LET N=5
LET M=3
DIM A(N) !n個の球 値は、箱の番号
DIM B(M) !m個の箱 値は、球の個数
PUBLIC NUMERIC C !場合の数
LET C=0
CALL try(1,1,N,A,B)
PRINT C;"通り"
PRINT StirlingS2(n,m);"通り" !検算
PRINT
!(4)
!相異なるn個の球と区別のつかないm個の箱がある。
!各箱に球を配る配り方（空箱があってよい）は何通りあるか。
LET C=0
CALL try(1,0,N,A,B)
PRINT C;"通り"
LET S=0 !検算
FOR k=1 TO M
LET S=S+StirlingS2(n,k)
NEXT k
PRINT S;"通り"
END
EXTERNAL SUB try(P,S,T,A(),B())
IF P>M THEN !最後の箱まで配って、
IF T=0 THEN !球を残らず配り終えたなら
CALL stub(N,M,A,B)
END IF
ELSE
FOR i=S TO T !p番目の箱 B(1)≦B(2)≦B(3)≦…≦B(p)
LET B(P)=i
CALL try(P+1,i,T-i,A,B) !(7),(8)
NEXT i
END IF
END SUB
EXTERNAL SUB stub(N,M,A(),B()) !同じ球● を 異なる球① へ
LET K=0 !最初のパターン（m進法n桁）
FOR J=1 TO M
FOR X=1 TO B(J)
LET A(K+X)=J
NEXT X
LET K=K+B(J)
NEXT J
MAT PRINT A; !debug
DO
CALL Filter(N,M,A,B, rc) !箱の中の球の並びで篩う
IF rc<>0 THEN
LET C=C+1
PRINT STR$(C); ": "; !結果を表示する
FOR J=1 TO M !j番目の箱
PRINT "[";
FOR K=1 TO N
IF A(K)=J THEN PRINT K; !球の番号
NEXT K
PRINT "]";
NEXT J
PRINT
END IF
CALL NextPermFactorial(A,N, rc) !次へ
LOOP UNTIL rc<>0
END SUB
EXTERNAL SUB Filter(N,M,A(),B(), rc) !個数が同じ箱の並びが昇順になっているかどうあ確認する
DIM F(M) !m個の箱 値は、球の番号で最小のもの
LET rc=0 !NG
!中身（球の並び）について、
! [①][②][③4][⑤6] と [①][②][⑤6][③4] を同一とみなす必要がある。
FOR J=1 TO M !j番目の箱
FOR K=1 TO N !球の番号で最小のもの
IF A(K)=J THEN EXIT FOR
NEXT K
LET F(J)=K !空の場合は、N+1
NEXT J
!!!MAT PRINT F; !debug
FOR K=1 TO N !球の個数が同じものでは
LET W=-1
FOR J=1 TO M !j番目の箱
IF B(J)=K THEN
IF F(J)<W THEN EXIT FOR !球の番号が昇順のもの
LET W=F(J)
END IF
NEXT J
IF J<=M THEN EXIT FOR
NEXT K
IF K>N THEN LET rc=-1 !OK
END SUB
EXTERNAL SUB NextPermFactorial(A(),N, rc) !辞書式順序で次の順列を返す ※「異なるn個のもの」と共通
LET i=N-1 !順列を右から左にみて、増加列から減少列に変わる位置iを探す
DO WHILE i>0 AND A(i)>=A(i+1) !０は番人
LET i=i-1
LOOP
IF i=0 THEN !A(1)>A(2)>A(3)> … >A(N)なら 例. N=4、4,3,2,1
LET rc=1 !完了（最後の並びである）
EXIT SUB
END IF
LET j=N !その位置iより右で、A(i)以上で最小の数A(j)を探す
DO WHILE A(i)>=A(j)
LET j=j-1
LOOP
LET t=A(i) !A(i)とA(j)を交換する
LET A(i)=A(j)
LET A(j)=t
LET i=i+1 !(i+1)からNまでの範囲を逆順にする
LET j=N
DO WHILE i<j
LET t=A(i) !swap it
LET A(i)=A(j)
LET A(j)=t
LET i=i+1
LET j=j-1
LOOP
LET rc=0 !未了
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
|
|