|
|
問題
10個のうち同じものをそれぞれ 4,3,2,1個ずつ含む a,a,a,a, b,b,b, c,c, d を、
A,B,C,Dの4人に分配する方法の数を求めよ。
条件1 1個ももらえない場合もありえるものとする。
条件2 少なくとも1個以上はもらえるものとする。
考察
条件1のとき、
aを4人に配る方法は、H(4,4)通り
bを4人に配る方法は、H(4,3)通り
cを4人に配る方法は、H(4,2)通り
dを4人に配る方法は、H(4,1)通り
なので、H(4,4)*H(4,3)*H(4,2)*H(4,1)=28000通り
同じものが、
m種類、それぞれb[k]（1≦k≦m）個ずつ
とすると、F0(n)= Π[k=1,m]H(n,b[k])
条件2のとき、
特定の1人に全部配る場合、1通り
特定の2人に全部配る場合、
全部配る方法は、H(2,4)*H(2,3)*H(2,2)*H(2,1)=120通り
そのうち1人だけがもらう方法は、C(2,1)*1=2通り
よって、120-2=118通り
特定の3人に全部配る場合、
H(3,4)*H(3,3)*H(3,2)*H(3,1)-C(3,2)*118-C(3,1)*1=2343通り
特定の4人に全部配る場合、
H(4,4)*H(4,3)*H(4,2)*H(4,1)-C(4,3)*2343-C(4,2)*118-C(4,1)*1=17916通り
F1(n)= F0(n) - Σ[k=1,n-1]C(n,k)F1(k)
（終わり）
LET M=4 !m種類
DATA 4,3,2,1 !個数
LET N=4 !n人
DIM B(4)
MAT READ B
PRINT F0(M,B,N); "通り"
PRINT F1(M,B,N); "通り"
END
EXTERNAL FUNCTION H(N,R) !重複組合せ H(n,r)=C(n+r-1,r)
LET H=COMB(N+R-1,R)
END FUNCTION
EXTERNAL FUNCTION F0(M,B(),N) !条件1
LET S=1 !Π[k=1,m]H(n,b[k])
FOR K=1 TO M
LET S=S*H(N,B(K))
NEXT K
LET F0=S
END FUNCTION
EXTERNAL FUNCTION F1(M,B(),N) !条件2
LET S=0 !特定のk人に全部配る Σ[k=1,n-1]C(n,k)F1(k)
FOR K=1 TO N-1
LET S=S+COMB(N,K)*F1(M,B,K)
NEXT K
LET F1=F0(M,B,N)-S
END FUNCTION
別解
aをAに配った個数をaA個と表すとする。
次の連立方程式を解く。
条件2のとき、
a b c d
A: aA bA cA dA ≧1 ←行の和
B: aB bB cB dB ≧1
C: aC bC cC dC ≧1
D: aD bD cD dD ≧1
=4 =3 =2 =1
↑列の和
配る個数は、a,b,c,dの順に分割数を利用して決めていく。
（終わり）
LET M=4 !m種類
DATA 4,3,2,1 !個数
LET N=4 !n人
DIM B(4)
MAT READ B
DIM A(N,M) !並び
PUBLIC NUMERIC C !場合の数
LET C=0
CALL try(1,1, B(1), M,B, N, A)
PRINT C;"通り"
END
EXTERNAL SUB try(x,y,S, M,B(),N, A(,)) !バックトラック法で検索する
IF x=N THEN !最後の人のとき
LET A(x,y)=S !残り全部
IF y=M THEN !最後のもののとき
DIM w(M),Aw(N) !0個の人があるかどうか確認する ※条件2
MAT w=CON !条件1の場合、不要（削除する）
MAT Aw=A*w !行の和
FOR i=1 TO N
IF Aw(i)=0 THEN EXIT FOR
NEXT i
IF i>N THEN !いないなら
LET C=C+1 !結果を表示する
!!MAT PRINT A;
END IF
ELSE
CALL try(1,y+1,B(y+1), M,B,N, A) !次のものへ
END IF
ELSE
FOR i=S TO 0 STEP -1 !x番目の人にy番目のものをi個配る
LET A(x,y)=i
CALL try(x+1,y,S-i, M,B,N, A) !次の人へ
NEXT i
END IF
END SUB
|
|