組合せ数学

場合の数

組合せ数学

　　１．積の法則

　　　　問題１.１
　　　　　n種の記号(1,2,3,…,n)から文字列を作る。
　　　　　長さrの文字列s₁s₂…s_rは何通りあるか。
　　　　　ただし、同じ記号を何回使ってもよい。

　　　　問題１.２
　　　　　n種の記号(1,2,3,…,n)から文字列を作る。
　　　　　長さrの文字列s₁s₂…s_rをすべて生成するプログラムを書け。
　　　　　ただし、同じ記号を何回使ってもよい。

　　　　問題１.３
　　　　　n種の記号(1,2,3,…,n)から文字列を作る。
　　　　　長さrの文字列s₁s₂…s_rにおいて、s₁≦s₂≦…≦s_rとなる文字列は
　　　　　何通りあるか。
　　　　　ただし、同じ記号を何回使ってもよい。

　　　　問題１.４
　　　　　n種の記号(1,2,3,…,n)から文字列を作る。
　　　　　長さrの文字列s₁s₂…s_rにおいて、s₁≦s₂≦…≦s_rとなる文字列を
　　　　　すべて生成するプログラムを書け。
　　　　　ただし、同じ記号を何回使ってもよい。

　　　　問題１.５
　　　　　n種の記号(1,2,3,…,n)から文字列を作る。
　　　　　長さrの文字列s₁s₂…s_rにおいて、s₁=1,|s_i-s_i-1|=1(2≦i≦r)となる
　　　　　文字列は何通りあるか。
　　　　　ただし、同じ記号を何回使ってもよい。

　　　　問題１.６
　　　　　n種の記号(1,2,3,…,n)から文字列を作る。
　　　　　長さrの文字列s₁s₂…s_rにおいて、s₁=1,|s_i-s_i-1|=1(2≦i≦r)となる
　　　　　文字列をすべて生成するプログラムを書け。
　　　　　ただし、同じ記号を何回使ってもよい。

　　２．和の法則

　　　　問題２.１
　　　　　n種の記号(1,2,3,…,n)から文字列を作る。長さr以下の文字列は
　　　　　何通りあるか。
　　　　　ただし、同じ記号を何回使ってもよい。

　●組合せ数学の基礎Ⅱ(pdfファイル)

　　３．順列

　　　　問題３.１
　　　　　　n個の要素{1,2,…,n}からr個取り出し,１列に並べる並べ方の
　　　　　　個数を求めよ。
　　　　　　ただし、重複は許さない。

　　　　問題３.２
　　　　　　n個の要素{1,2,…,n}からr個取り出し,１列に並べる並べ方を
　　　　　　すべて生成するプログラムを書け。
　　　　　　ただし、重複は許さない。

　　　　問題３.３
　　　　　　n個の要素{1,2,…,n}からr個取り出し,１列に並べる並べ方を
　　　　　　ランダムに生成するプログラムを書け。
　　　　　　ただし、重複は許さない。

　●組合せ数学の基礎Ⅲ(pdfファイル)

　　４．一般順列

　　　　問題４.１

　　　　　　1がa個、2がb個とする。
  　　　　　1をa個、2をb個取り出し、１列に並べる並べ方を求めよ

　　　　問題４.２

　　　　　　1がa個、2がb個とする。
  　　　　　1をa個、2をb個取り出し、１列に並べる並べ方をすべて生成する
　　　　　　プログラムを書け。

　　　　問題４.３

　　　　　　1がa個、2がb個、3がc個とする。
  　　　　　1をa個、2をb個、3をc個取り出し、１列に並べる並べ方を求めよ
　
　　　　問題４.４

　　　　　　1がa個、2がb個、3がc個とする。
  　　　　　1をa個、2をb個、3をc個取り出し、１列に並べる並べ方をすべて
　　　　　　生成するプログラムを書け。

　　　　問題４.５

　　　　　　1がa個、2がb個、3がc個とする。
  　　　　　1をa個、2をb個、3をc個取り出し、１列に並べる並べ方を
　　　　　　ランダムに生成するプログラムを書け。

　　　　問題４.６

　　　　　　n個の要素{1,2,…,n}で、1がm₁個、2がm₂個、…、nがm_n個あるとき、
　　　　　　合計r=m₁+m₂+…+m_n個を１列に並べたものを一般順列という。
  　　　　　一般順列をすべて生成するプログラムを書け。

　●組合せ数学の基礎Ⅳ(pdfファイル)

　　５．組合せ

　　　　問題５.１

　　　　　　集合{1,2,3,…,n}からr個の記号を選ぶ選び方をすべて生成する
　　　　　　プログラムを書け。

　　　　問題５.２

　　　　　　集合{1,2,3,…,n}からr個の記号を選ぶ選び方をランダムに
　　　　　　生成するプログラムを書け。

　　６．重複組合せ

　　　　問題６.１

　　　　　　集合{1,2,…,n}から重複を許してr個の記号を選ぶ選び方は
　　　　　　何通りか。

　　　　問題６.２

　　　　　　集合{1,2,…,n}から重複を許してr個の記号を選ぶ選び方をすべて
　　　　　　生成するプログラムを書け。

　　　　問題６.３

　　　　　　集合{1,2,…,n}から重複を許してr個の記号を選ぶ選び方を
　　　　　　ランダムに生成するプログラムを書け。

　●文字列問題(pdfファイル)

　　１．文字列問題

　　　　問題１

　　　　（１）2種類の記号0または1から作られる長さnの文字列をA(n)、
　　　　　　　その個数をa(n)とする。
　    　　　　A(n) (1≦n≦4)とa(n) (1≦n≦10)を求めよ。

　　　　（２）2種類の記号0または1から作られる長さnの文字列を
　　　　　　　すべて生成するプログラムを作成せよ。

　　　　（３）{0,1}上の長さnの文字列において、連続する文字列間で、
　　　　　　　１カ所のみ異なるという条件で、すべて生成する方法を考えよ。
　　　　　　　また、プログラムも作成せよ。

　　　　問題２

　　　　（１）2種類の記号0または1から作られる長さnの文字列で、
　　　　　　　00を含まない文字列をB(n)、その個数をb(n)とする。
　　　　　　　B(n) (1≦n≦4)とb(n) (1≦n≦10)を求めよ。

　　　　（２）2種類の記号0または1から作られる長さnの文字列で、
　　　　　　　00を含まない文字列をすべて生成するプログラムを書け。

　　　　（３）2種類の記号0または1から作られる長さnの文字列で、
　　　　　　　k桁目で00が初めて現れるものをS(n,k)、その個数を
　　　　　　　s(n,k)とする。
　　　　　　　S(k,k) (1≦k≦6)とs(k,k) (1≦k≦9)を求めよ。

　　　　（４）2種類の記号0または1から作られる長さnの文字列で、
　　　　　　　00を含まない文字列を考える。
　　　　　　　この文字列において、連続する文字列間で、１カ所のみ
　　　　　　　異なるという条件で、すべて生成する方法を考えよ。
　　　　　　　また、プログラムも作成せよ。