４つの順序を持つ変数に関して、以下の条件 X があるとします。
x1 < x2 < x3 < x4
X が 真とならない 4変数の関係はいくつ考えられるでしょうか？
X を二項ずつに書き直します。
(x1 < x2)
∧ (x2 < x3)
∧ (x3 < x4)
X の否定 not X をとります。
(x1 ≧ x2)
∨ (x2 ≧ x3)
∨ (x3 ≧ x4)
不等号と等号を別にします。
(x1 > x2)
∨ (x2 > x3)
∨ (x3 > x4)
∨ (x1 = x2)
∨ (x2 = x3)
∨ (x3 = x4)
4変数のいずれかが存在しない場合も考慮することにします。
ここでは、 "is null" と表記しておきます。
(x1 > x2)
∨ (x2 > x3)
∨ (x3 > x4)
∨ (x1 = x2)
∨ (x2 = x3)
∨ (x3 = x4)
∨ (x1 is null)
∨ (x2 is null)
∨ (x3 is null)
∨ (x4 is null)
突き詰めますと、この10個の条件のいずれかになるわけですが。全部の数が知りたいので、不等号の場合、等号の場合、変数が存在しない場合、各々について、順に考えてみます。
不等号の場合
不等号をそのままにして、4変数の場所を並べ替えることを考えますと。
P4 = 4! = 24
4つをとる順列を考えればよく、全部で24個の並びが存在することになります。うちひとつは、 X そのものですので、 X が真とならないものは 23個ですね。
| 0 |
x1 < x2 < x3 < x4 |
| 1 |
x1 < x2 < x4 < x3 |
| 2 |
x1 < x3 < x2 < x4 |
| 3 |
x1 < x3 < x4 < x2 |
| 4 |
x1 < x4 < x2 < x3 |
| 5 |
x1 < x4 < x3 < x2 |
| 6 |
x2 < x1 < x3 < x4 |
| 7 |
x2 < x1 < x4 < x3 |
| 8 |
x2 < x3 < x1 < x4 |
| 9 |
x2 < x3 < x4 < x1 |
| 10 |
x2 < x4 < x1 < x3 |
| 11 |
x2 < x4 < x3 < x1 |
| 12 |
x3 < x1 < x2 < x4 |
| 13 |
x3 < x1 < x4 < x2 |
| 14 |
x3 < x2 < x1 < x4 |
| 15 |
x3 < x2 < x4 < x1 |
| 16 |
x3 < x4 < x1 < x2 |
| 17 |
x3 < x4 < x2 < x1 |
| 18 |
x4 < x1 < x2 < x3 |
| 19 |
x4 < x1 < x3 < x2 |
| 20 |
x4 < x2 < x1 < x3 |
| 21 |
x4 < x2 < x3 < x1 |
| 22 |
x4 < x3 < x1 < x2 |
| 23 |
x4 < x3 < x2 < x1 |
等号の場合
４変数のうち２変数が等しい場合は、
4C2 = 4 ・ 3 / 2 ・ 1 = 6
４つから2つをとる組合わせの数で6個あります。
4変数のうち3変数が等しい場合は、
4C3 = 4C1 = 4
4個あります。
4変数のうち4変数が等しい場合は、1個あります。
さらに、等号を不等号を組み合わせるわけですが。これは、等しい変数を1変数にまとめ、その並べ替えを考えれば良いかと思います。
例えば、4変数のうち2変数が等しいとしまして、これが、
x1 = x2
であるとしますと、これを X12 とまとめまして、3変数の並べ替えを考えます。
P3 = 3! = 6
6個あります。
| 1 |
X12 < x3 < x4 |
| 2 |
X12 < x4 < x3 |
| 3 |
x3 < X12 < x4 |
| 4 |
x3 < x4 < X12 |
| 5 |
x4 < X12 < x3 |
| 6 |
x4 < x3 < X12 |
まとめますと、
4C2 ・ P3 + 4C3 ・ P2 + 4C4 ・ P1
= 6 ・ 6 + 4 ・ 2 + 1
= 45
45個となります。
変数が存在しない場合
4変数のうち１変数が存在しない場合、4変数のうち2変数が存在しない場合、4変数のうち3変数が存在しない場合、4変数のすべてが存在しない場合、各々の場合を考えます。
4C1 4C2 4C3 4C4
4変数のうち3変数が存在しない場合、4変数のすべてが存在しない場合、については、順序関係が成り立ちませんので、これ以上を考える必要はありません。
4変数のうち１変数が存在しない場合、4変数のうち2変数が存在しない場合、については、それぞれ、3変数の順序関係、2変数の順序関係がありますので、これを考えます。
4変数のうち１変数が存在しない場合（3変数の順序関係）：
P3 + 3C2 ・ P2 + 3C3 ・ P1
= 6 + 3 ・ 2 + 1
= 13
4変数のうち2変数が存在しない場合（2変数の順序関係）：
P2 + 2C2 ・ P1
= 2 + 1
= 3
従いまして、
4C1 ・ 13 + 4C2 ・ 3 + 4C3 + 4C4
= 4 ・ 13 + 6 ・ 3 + 4 + 1
＝ 75
75個となります。
まとめ
以上の結果から、 X が真とならない関係は、
23 + 45 + 75 = 143
全部で143個となります。
この問題は、コンピュータ・ソフトウエアの仕様を考えるものとしても良いですし、プログラムのテストケースを考えるものとしても良いかと思います。詳細仕様の１つの条件について、143個のケースを顧客と打ち合わせる、というのはかなり困難かもしれませんね。プログラムのテストケースであれば、このぐらいはやることもあるでしょうが。
現実には、なんらかの事前条件が使えると思いますので、ここまでケースが膨らむことはないでしょう。典型的には、 x1 < x3, x2 < x4 などが事前条件として与えられることが多いと思います。4分の1くらいには減らせますかね。
最近のコメント