縦がNピクセル、横がMピクセルサイズで、１ピクセルが白か黒のみで構成される２値画像で作れるパターンは２のMN乗になると思いますが、図のように同じパターンが平行移動したパターンは同じパターンとみなすとき、全部で何パターンあるかということは、ＭとＮを使って一般式に表すことはできるのでしょうか？
また一般式に表せない場合はどのような方法でカウントしていけばいいのでしょうか？
No.1
8
1
50pt
カウントする方法を。
質問の画像中にある平行移動をしている白のパターンを「図形」と呼びます。
「図形」の「外接四角形」の縦横を(n,m)とおきます。（画像のは(3,2)になります）
このとき「外接四角形の縦横が(n,m)になるような図形の個数」をn,mを用いてあらわせれば、あとはN≧n,M≧mの(n,m)に関して数え上げればよいわけです。
「外接四角形の縦横が(n,m)になるような図形の個数」は以下のように求めます。
まず、
n=1のとき、図形は横長の四角形になりM個あります。
m=1のとき、図形は縦長の四角形になりN個あります。
つぎに、n≧2かつm≧2のときを考えます。
このとき外接四角形の4隅が図形に含まれるかどうかで場合わけして考えます。
必ず各辺の四隅以外の部分に、最低1ヶ所は図形に含まれる部分があります。（ない場合、その図形の外接四角形は一回り小さくなってしまいます）
それ以外の部分は自由です。よって
(2^(m-2)-1)(2^(m-2)-1)(2^(n-2)-1)(2^(n-2)-1)*2^((m-2)(n-2))
となります。
(以下略)
このように考え、最後に
Σ[N≧n≧2,M≧m≧2](上述の場合分けの和)+M+N
を計算すればOKです。
No.1
81
ここでベストアンサー
50pt
カウントする方法を。
質問の画像中にある平行移動をしている白のパターンを「図形」と呼びます。
「図形」の「外接四角形」の縦横を(n,m)とおきます。（画像のは(3,2)になります）
このとき「外接四角形の縦横が(n,m)になるような図形の個数」をn,mを用いてあらわせれば、あとはN≧n,M≧mの(n,m)に関して数え上げればよいわけです。
「外接四角形の縦横が(n,m)になるような図形の個数」は以下のように求めます。
まず、
n=1のとき、図形は横長の四角形になりM個あります。
m=1のとき、図形は縦長の四角形になりN個あります。
つぎに、n≧2かつm≧2のときを考えます。
このとき外接四角形の4隅が図形に含まれるかどうかで場合わけして考えます。
必ず各辺の四隅以外の部分に、最低1ヶ所は図形に含まれる部分があります。（ない場合、その図形の外接四角形は一回り小さくなってしまいます）
それ以外の部分は自由です。よって
(2^(m-2)-1)(2^(m-2)-1)(2^(n-2)-1)(2^(n-2)-1)*2^((m-2)(n-2))
となります。
(以下略)
このように考え、最後に
Σ[N≧n≧2,M≧m≧2](上述の場合分けの和)+M+N
を計算すればOKです。
No.2
81394
19pt
一般的な数式では表せないと思いますが、
例えばm=4,n=4であったとすれば、
2mn-(12(m-1)(n-1))-(32(m-2)(n-2))-(60(m-3)(n-3))
というふうに同じパターンを引いていけば可能だと思います。
当然かも知れませんがnとmの値が分かっていれば数式にすることは可能でしょう。
No.3
33158
35pt
http://q.hatena.ne.jp/1202629909
URLはダミーです。
他の回答者の方々がもっときちんとした回答をしていらっしゃるかもしれませんが。
例えば、4x4配列において以下の2値画像が同じパターンであるとした場合、：
1100 0110 0010 0001
0100 0010 1100 0110
1111 1111 0100 0010
0010 0001 1111 1111
これらは左端の図を基本として、
それぞれ全体をX方向1、Y方向に1、X方向1+Y方向に1移動させたものです。
(※はみ出した分は逆端に配置してます)
この場合、左端の図の一番左上の1を基準に考えると、移動可能な場所は4x4=16となります。
ただし、全てが同じパターンの場合(真っ黒と真っ白の2通り)は対象外となりますので、
なので、パターン数は、【｛2^(4x4)-2｝/4x4】+2 通りになります。
これを一般化すると、全体のパターン数は【｛2^(MxN)-2｝/MxN】+2 通りとなります。
･･･と思われましたが、平行移動によって元と同じパターンになる場合があり、
それを単純計算で求めるのは極めて難しいように思います。
(例)
0101 全体を 0101
1010 X(Y)方向に2移動！ または 1010
0101 → X方向に1+Y方向に1移動！ → 0101 （元と同じ･･･）
1010 1010
もし、逆端配置パターンを同一と認めないということになると、
私が例示した上の4つの2値画像はいずれも違うもの、と認識される事になります。
その場合は、まずMxNピクセル内における白ピクセルの広がりに着目します。
例えば、質問者が提示されている画像の場合、
X方向への広がりが2、Y方向への広がりを3と捉えます。
これを一般化すると、
MxNピクセル内における(例えば)白ピクセルの広がりがX方向にX、Y方向にY存在するパターン数については、まず(X-2)(Y-2)ピクセル中の任意の配列を計算すると、2^(X-2)(Y-2) 通りで表されますが、これ自体はあまり難しくありません。下の2値画像で言うところの0に相当する部分を計算しただけです。
← X →
111111111 ↑
100000001 Y
111111111 ↓
むしろ「1」の部分について、白ピクセルがどこに点在するかについて計算できなければいけませんので。ちなみに、「1」の部分に白ピクセルが1つしか無い場合は、絶対に”白ピクセルの広がりがX方向にX、Y方向にY存在する”ことを示す事は出来ませんので、必ず白ピクセルは2箇所以上存在し、かつある数(=X+Y-1)未満の場合は特定の領域(四隅あるいは4辺それぞれ)にいくつか存在しなければいけません。
2+ 4x(X-2)(Y-2)+2x{(X-2)+(Y-2)+(2X+2Y-8)}+4x(2X+2Y-8) + ･･･
2箇所の場合は両対角、3箇所の場合は四隅のうち最低一つ以上、4箇所以上の場合は四隅を押さえなければ各縁に最低1箇所以上、といった具合に場合分けをして計算をしていきます。 X+Y-1箇所以上ある場合(※仮にT箇所)はどのような配置であれ、必ず”白ピクセルの広がりがX方向にX、Y方向にY存在する”パターンになりますので、組み合わせの計算式：(2X+2Y-4)C(T)で求める事が出来ます。後は合計した結果とそのパターン全体がMxNピクセル中でどのくらい平行移動できるか(＝(M-X+1)(N-Y+1) パターン)を算出して掛け合わせればよいと思います。ただし、この時点ではXおよびYがそれぞれ一つの定数である場合の結果ですので、X=1 to M, Y=1 to Nまでそれぞれ変化させて(つまりMxN通り)、それぞれを合計すると、求めるパターン数になると思います。
ひたすら文章だけ見づらいのに加えて、これで間違っているようでしたら非常にゴメンナサイ。
No.4
120
15pt
他の方も指摘済みかもしれませんが、例えば
■□■■
■□□■
■■□■
■■■■
と、それを二マス左にずらした
■■■□
□■■□
□■■■
■■■■
を「同じパターン」とみなすかどうかで答えが変わってきます。
同じパターンとみなさない考え方ですと、例えば
■■■■
■□□■
■□□■
■■■■
と
■■■■
□□■■
□□■■
■■■■
は、一つめのパターンを「白マスの塊」と捉えれば二つめと同じパターンになるでしょうが、逆に一つめのパターンを「黒マスで描いた四角」と捉える場合には二つめと違うパターンということになるでしょう。
というわけで、まずは「同じパターン」であることをどう判定するのかきちんと定めることが必要かと思います。
5
5
3
2
1
コメント（1件)
参考にさせていただきます。