|
|
問題
7人がけの長いすが全て空いていて、そこへ7人の客が1人ずつ座っていくとする。
最初の客は、任意の位置に座る。
2番目の客は、最初の客と隣り合わないように離れた位置に座る。
以降同様に、なるべく隣り合わないような位置を選んで座っていく。
ある程度座るとそのような位置が選べなくなり、仕方なく任意の客の隣に座ることになる。
さて、この席が7人で埋め尽くされる順序は、全部で何通りあるか。
例 3人の場合
123 番目の席
132 番目の客
123
231
123
213
123
312
以上、4通り
考察
k人目で、これ以上隣り合わないようにすることができなくなったとする。
そのときの空き席は、(n-k)個である。
その内の(k-1)個を用いて間を埋めて、k人が隣り合わないようにする。
残りは、(n-k)-(k-1)=n-2k+1個なので、これを(k+1)箇所に1つずつ埋めればよい。
（∵それぞれの左側のk個 と 右端の1個 との 計(k+1)個 より）
よって、C(k+1,n-2k+1)通りのパターンを得る。
例 n=7、k=3のとき、
│×●│×●│×│ 残りは、2個 ∴C(4,2)=6
例 n=7、k=4のとき、
│×●│×●│×●│×│ 残りは、なし ∴C(5,0)=1
また、kの範囲は、
最小値は、2個ずつ空けて座る場合である。
最大値は、1個ずつ空けて座る場合である。
よって、[(n+2)/3]≦k≦[(n+1)/2]となる。
（終り）
OPTION ARITHMETIC RATIONAL !多桁の整数
LET N=7 !席の数 ※2以上
DIM A(N) !これ以上隣り合わないように座れるパターン
MAT A=ZER
PUBLIC NUMERIC C !パターンの場合の数
LET C=0
PUBLIC NUMERIC X !場合の数
LET X=0
LET A(1)=1 !1番目の席に座る
CALL try(2,N,A)
PRINT
LET A(1)=0 !1番目の席を空ける
CALL try(2,N,A)
PRINT C; "通り"
PRINT X; "通り"
LET S=0
FOR K=INT((N+2)/3) TO INT((N+1)/2)
LET S=S+COMB(K+1,N-2*K+1)
PRINT K; COMB(K+1,N-2*K+1) !debug
NEXT K
PRINT S; "通り"
END
EXTERNAL SUB try(P,N,A()) !バックトラック法で埋めていく
OPTION ARITHMETIC RATIONAL !多桁の整数
IF P=N THEN !右端（最後の席）の場合
IF A(P-1)=0 THEN LET A(P)=1 !補正する
LET T=0 !座る順序を考える
FOR i=1 TO N
IF A(i)=0 THEN LET T=T+1
NEXT i
LET X=X+FACT(N-T)*FACT(T)
LET C=C+1
MAT PRINT A; !パターン
LET A(P)=0 !元に戻す
ELSE
IF A(P-1)=1 THEN !1つ前に座っている
LET A(P)=0 !空き席にする
CALL try(P+1,N,A) !左端から埋めていく
LET A(P)=0 !元に戻す
IF P+1<N THEN !空き席は連続2つまで可能である
LET A(P)=0
LET A(P+1)=0
CALL try(P+2,N,A)
LET A(P)=0
LET A(P+1)=0
END IF
ELSE !1つ前が空き席なら
LET A(P)=1 !座らせる
CALL try(P+1,N,A)
LET A(P)=0
END IF
END IF
END SUB
実行結果
1 0 1 0 1 0 1
1 0 1 0 0 1 0
1 0 0 1 0 1 0
1 0 0 1 0 0 1
0 1 0 1 0 1 0
0 1 0 1 0 0 1
0 1 0 0 1 0 1
7 通り
1008 通り
3 6
4 1
7 通り
|
|