k個ずつある自然数kを並べる

 投稿者：山中和義  投稿日：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

 		 

Re: k個ずつある自然数kを並べる

 投稿者：山中和義  投稿日：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

 		 

Re: k個ずつある自然数kを並べる

 投稿者：山中和義  投稿日：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
 		 

戻る