|
投稿者：山中和義
投稿日：2012年 9月16日(日)11時03分5秒
|
|
|
|
問題
nは自然数とする。
1が1個、2が2個、3が3個、… 、nがn個とすると、全部でn(n+1)/2個の数がある。
これらすべてを横一列に並べるとき、同じ数が隣り合わないように並べる。
このような並べ方は何通りあるか。
答え
実際に、並べてみよう。
補題. 連続する数の箇所の個数を調べてみよう。 → 漸化式
検証対象は、{(n(n+1))/2}!/(1!2!3!…n!) 通り
n=1
1 通り
1 0 0 0 0 0 0 0 0 0 0
n=2
3 通り
1 2 0 0 0 0 0 0 0 0 0
n=3
60 通り
10 26 18 6 0 0 0 0 0 0 0
n=4
12600 通り
1074 3366 4170 2730 1020 216 24 0 0 0 0
よって、X(0)が求める値である。
結果は、多桁の整数になるので、有理数モードで実行する必要があるが、
実質求められる範囲では、精度は保たれるので、2進数モードでよい。
LET N=3 !※N≧5は非現実的
PUBLIC NUMERIC X(0 TO 10) !連数の出現頻度 ※調整の必要性あり
MAT X=ZER
DIM F(N) !n個ずつ
FOR i=1 TO N
LET F(i)=i
NEXT i
LET T=1 !{n(n+1)/2}!/(1!2!3!…n!)の値
LET S=0
FOR i=N TO 1 STEP -1
LET S=S+F(i)
LET T=T*COMB(S,F(i))
NEXT i
PRINT T;"通り" !検証
PUBLIC NUMERIC C !並べ方の総数
LET C=0
LET M=N*(N+1)/2
DIM A(0 TO M) !並び ※0は番兵
MAT A=ZER
CALL try(1,N,F,M,A,0)
IF C=0 THEN PRINT "解なし" ELSE PRINT C;"通り"
MAT PRINT X; !解 X(0)
END
EXTERNAL SUB try(P,N,F(),M,A(),L) !1からnまでの数の並びをすべて列挙する
FOR i=1 TO N !未使用の数を順に使っていく
IF F(i)>0 THEN
IF A(P-1)=i THEN LET LL=L+1 ELSE LET LL=L !連続する数の箇所を数える
LET A(P)=i !p番目の数はiとする
IF P=M THEN !すべて並んだら
LET C=C+1
PRINT "No.";C; " 連数=";LL !debug
MAT PRINT A; !debug
LET X(LL)=X(LL)+1 !記録する
ELSE
LET F(i)=F(i)-1
CALL try(P+1,N,F,M,A,LL) !次へ
LET F(i)=F(i)+1
END IF
END IF
NEXT i
END SUB
|
|
|
|
投稿者：山中和義
投稿日：2012年 9月16日(日)19時11分47秒
|
|
|
|
> No.1978[元記事へ]
> 問題
> nは自然数とする。
> 1が1個、2が2個、3が3個、… 、nがn個とすると、全部でn(n+1)/2個の数がある。
> これらすべてを横一列に並べるとき、同じ数が隣り合わないように並べる。
> このような並べ方は何通りあるか。
別解 補題で求めた値をもとに算出する方法
たとえば、n=3を求める場合、n=2の並べ方 3!/(1!2!)=3通り に着目する。
並びをすべて列挙して、これに3個の3を並べることを考える。
122のとき、1232として3を1つ使う。残りの並べ方は、①1②232③なので、C(3,2)=3通り
212のとき、①2②1③2④なので、C(4,3)=4通り
221のとき、①232②1③なので、C(3,2)=3通り
よって、3+4+3=10通り
このように、(n-1)をもとにnを求めることができる。
n=4の場合（一般的に）
表
N＼L 0 1 2 3 4 ← 連なりの個数
3 10 26 18 6 0
├─┴─┴─┴─┘+0から+Nまでの範囲
4 ?
L 場合の数 説明
-- ------------- ------------------------------
0 10*C(7,4)=350 _○_○_○_○_○_○_ のアンダーバーの箇所に、4つの△を挿入する
1 26*C(6,3)=520 _●△●_○_○_○_○_ の箇所に、3つの△を挿入する
2 18*C(5,2)=180 _●△●△●_○_○_○_ の箇所に、2つの△を挿入する
_●△●_○_●△●_○_ の箇所に、2つの△を挿入する
3 6*C(4,1)= 24 _●△●△●△●_○_○_ の箇所に、1つの△を挿入する
※この並びはないが、連なりが3個の場合の一般な記述となる。
_●△●_○_●△●△●_ の箇所に、1つの△を挿入する
4 0*C(3,0)= 0 _●△●△●△●△●_○_ の箇所 ※
-----------------
1074
記号の意味
●,○,▲,△は1つの数字を表す。
●●、▲▲は数が並んでいることを意味する。
○○、△△は数が並んでいないことを意味する。
たとえば、●●○○○○は、具体的には、332132,213323,132332 など
n=5の場合
検証対象は、高々10!/(1!2!3!4!)=12600通りである。
{1223334444}のように6箇所では、5個の5で「連続」を除くことはできない。
その場合の数は、1,22,333,4444を4つの数とみて並べる並べ方4!=24通りが不適となる。
並び12576通りから、1637124通りを得る。
この現象は、n≧5で発生する。
n=6なら、37837800通り中、20072983通り
：
LET N=4 !N-1 → N ※N≧7は非現実的
DIM F(N-1) !i個ずつ
FOR i=1 TO N-1
LET F(i)=i
NEXT i
LET T=1 !{n(n+1)/2}!/(1!2!3!…n!)の値
LET S=0
FOR i=N-1 TO 1 STEP -1
LET S=S+F(i)
LET T=T*COMB(S,F(i))
NEXT i
PRINT T;"通り"
PUBLIC NUMERIC C !元になる並びの個数
LET C=0
PUBLIC NUMERIC D !解
LET D=0
LET M=(N-1)*N/2
DIM A(0 TO M) !並び ※0は番兵
MAT A=ZER
CALL try(1,N,F,M,A,0)
IF C=0 THEN PRINT "解なし" ELSE PRINT C;"通り"
PRINT D;"通り" !解
END
EXTERNAL SUB try(P,N,F(),M,A(),L) !1から(n-1)までの数の並びに数nを追加する
FOR i=1 TO N-1
IF F(i)>0 THEN
IF A(P-1)=i THEN LET LL=L+1 ELSE LET LL=L
IF LL<=N+1 THEN !連続数の箇所がn+1個以下なら、条件を満たして並べられる
LET A(P)=i !p番目の数はiとする
IF P=M THEN !すべて並んだら
LET C=C+1
PRINT "No.";C; " 連数=";LL !debug
MAT PRINT A; !debug
LET D=D+COMB((M+1)-LL,N-LL) !解
ELSE
LET F(i)=F(i)-1
CALL try(P+1,N,F,M,A,LL) !次へ
LET F(i)=F(i)+1
END IF
END IF
END IF
NEXT i
END SUB
|
|
|
|
投稿者：山中和義
投稿日：2012年 9月17日(月)19時12分44秒
|
|
|
|
> No.1979[元記事へ]
> 問題
> nは自然数とする。
> 1が1個、2が2個、3が3個、… 、nがn個とすると、全部でn(n+1)/2個の数がある。
> これらすべてを横一列に並べるとき、同じ数が隣り合わないように並べる。
> このような並べ方は何通りあるか。
答え
連なりが0以外も、(n-1)から求めてみる。
n=3で、連なりが1の場合、
表
N＼L 0 1 2 3 4 ← 連なりの個数
1: 1
2: 1 2 (0) (0) (0)
└─┼─┴─┴─┘-(N-1)から+Nまで
3: 10 26
212のとき、①2②1③2④なので、3,33を挿入する。C(4,1)C(3,1)=12通り
122のとき、①1②22③なので、3個の3を挿入する。C(3,3)=1通り
①1②232③なので、2個の3を挿入する。C(3,2)=3通り
①1②2332③なので、1個の3を挿入する。C(3,1)=3通り
計 7通り
よって、12+7*2=26通り
n=3で、連なりが2の場合、
表
N＼L 0 1 2 3 4 5 ← 連なりの個数
1: 1
2: 1 2 (0) (0) (0) (0)
└─┴─┼─┴─┴─┘-(N-1)から+Nまで
3: 10 26 18
212のとき、①2②1③2④なので、333を挿入する。C(4,1)=4通り
122のとき、①1②22③なので、3,33を挿入する。C(3,1)C(2,1)=6通り
①1②23332③なので、1通り
計 7通り
よって、4+7*2=18通り
n=3で、連なりが3の場合、
表
N＼L 0 1 2 3 4 5 6 ← 連なりの個数
1: 1
2: 1 2 (0) (0) (0) (0) (0)
└─┴─┼─┴─┴─┘-(N-1)から+Nまで
3: 10 26 18 6
122のとき、①1②22③なので、333を挿入する。C(3,1)=3通り
よって、3*2=6通り
（プログラムの算出方法）
n=3で、連なりが1の場合、
212のとき、①2②1③2④なので、C(0,0)C(4,2)RepComb(2,1)=12通り
122のとき、①1②2○2③なので、
C(1,0)C(3,3)RepComb(3,0)=1通り
C(1,1)C(3,1)RepComb(2,1)=6通り
計 7通り
よって、12+7*2=26通り
OPTION ARITHMETIC RATIONAL !多桁整数
DEF ReptComb(N,K)=COMB(N+K-1,K) !重複組合せ（repeated combination、nHk）
LET N=20
DIM A(0 TO (N-1)*N/2) !表 N＼L
MAT A=ZER
LET A(0)=1 !N=1のとき
DIM B(0 TO (N-1)*N/2) !新しい表 N＼L
!dを増やしたり減らしたりする個数を表すとして、
!連なりをm個から(m+d)個にする並べ方を考える。
!
!今、挿入するi個の△がある。具体的には、i個の数字iである。
!1から(i-1)までの数（総数s個）の並びで、
! _●_●_ … _●_○_○_○_ … _○_ (s+1)個の挿入箇所はアンダーバーで表す
! └ k個 ┘
!連なりがk個の状態とする。
!ここで、連なりをm個除去しておいて、(m+d)個にする並べ方を考える。
!・連なっている箇所kからm箇所選んで数字を入れる。 0≦m≦k とする。
!・連なっていない箇所(s+1-k)からmm箇所選んで数字を入れる。
! ただし、残りが(m+d)個になるようにmmを調整する。i-(m+mm)=m+dより、mm=i-d-2*m となる。
! _●△●△ … ●_○△○△○_ … _○_ 残り(m+d)個の△
! └ m個の△ ┘ └ mm個の△ ┘
!・挿入した(m+mm)箇所に、残り(m+d)個の数字を重複的に追加する。
! _●▲▲▲●▲▲ … ●_○▲▲▲○▲▲○_ … _○_
! └ m箇所に△を追加 ┘ └ mm箇所に△を追加 ┘
!以上の手順で実現できる。
!
!よって、
! a[i,j]=Σ[k=0,s[i-1]]Σ[m=0,k]C(k,m)*C(s[i]+1-k,mm)*H(m+mm,m+d)*a[i-1,k]
! ここで、s[i]=(i-1)*i/2, d=j-k, 0≦m≦k, mm=i-d-2*m とする。
! ただし、mm≧0かつm+d≧0で和をとる。
!とする漸化式で求まる。
LET S=0
FOR i=2 TO N !i行（(i-1)番目からi番目を生成する）
MAT B=ZER
LET S0=S !a[k]の存在する範囲
LET S=(i-1)*i/2
FOR j=0 TO S !j列（連なりの個数）
LET T=0
FOR K=MAX(0,j-(i-1)) TO MIN(j+i,S0) !※実際は、(j-(i-1))から(j+i)までの範囲でよい
LET D=j-K !増減
LET W=0 !場合の数
FOR M=0 TO K
LET MM=i-D-2*M
IF MM>=0 AND M+D>=0 THEN
LET W=W+COMB(K,M)*COMB(S+1-K,MM)*ReptComb(M+MM,M+D)
!!!PRINT "C(";STR$(K);",";STR$(M);")"; !debug
!!!PRINT " C(";STR$(S+1-K);",";STR$(MM);")"; !debug
!!!PRINT " ReptComb(";STR$(M+MM);",";STR$(M+D);")"; !debug
!!!PRINT " =";COMB(K,M)*COMB(S+1-K,MM)*ReptComb(M+MM,M+D) !debug
END IF
NEXT M
LET T=T+W*A(K) !累計
!!!PRINT "A[";STR$(i-1);",";STR$(K);"] ="; A(K) !debug
NEXT K
LET B(j)=T !求める値
!!!PRINT "→ A[";STR$(i);",";STR$(j);"] ="; T !debug
NEXT j
MAT A=B !copy it
!!!PRINT !debug
NEXT i
!!!MAT PRINT A; !結果を表示する
PRINT A(0) !結果を表示する
END
表
N＼L 0 1 2 3 4 5 6 7 8 9 10 ← 連なりの個数
1: 1
2: 1 2
3: 10 26 18 6
4: 1074 3366 4170 2730 1020 216 24
5: 1637124 6175296 10226280 9877440 6217680 2686656 815304 174000 25500 2400 120
|
|
|
戻る