1

宿題としてこれを手に入れましたが、どこから始めればいいのか本当にわかりません!

set が与えられると、{1,2,3,4}そのセットから長さ 2 の 6 つの組み合わせを形成できます。

{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}

組み合わせの 1 つを選択した場合 ({1,2}たとえば)、他の組み合わせのどれがそれとばらばらではないかをどのように判断できますか? この場合は次の 4 つです。{1,3},{1,4},{2,3}{2,4}

これを数学的にどのように進めるかについてはよくわかりませんが、正しい方向へのポインタは大歓迎です。

4

5 に答える 5

1

一度にnアイテムを取るアイテムのセットから形成できるサブセットの数はr

total = P(n, r) = n! / (r! * (n - r)!)

s選択した組み合わせにしましょう。とばらばらではないサブセットの数を見つけるには、 とばらばらなサブセットの数を見つけるsことから始めsます-アイテムが含まれていないセットs(その番号を呼び出しましょうk)。したがって、アイテムkのセットから一度に形成できるサブセットの数です。n - rr

k = P(n - r, r) = (n - r)! / (r! * (n - r - r)!)
  = (n - r)! / (r! * (n - 2r)!)

したがって、選択されたセットと素であるサブセットの数は次のとおりです。

total - k = P(n, r) - P(n - r, r)

これには、選択したサブセットが含まれることに注意してくださいs。これから 1 を引いて、 で互いに素な集合の数を取得しsます。

次の例を検討してください。

//Let n = 6 and r = 2
total = P(n, r) = n! / (r! * (n - r)!) = 6! / (2! * 4!) = 15

k = P(n - r, r) = (n - r)! / (r! * (n - 2r)!) = 4! / (2! * 2!) = 6
answer = 15 - 6 = 9; answer excluding the selected set s = 8

//Super set: 
  {123456}
//Possible sub sets: 
  {12,13,14,15,16,23,24,25,26,34,35,36,45,46,56}  //15 items

//Let the selected set be {12}, then sets without 1 and 2: 
  {34,35,36,45,46,56} //6 items

//9 sets (including the selected set) are not disjoint with the selected set
于 2009-11-24T14:09:25.047 に答える
0

たぶん、組み合わせ論に関する本や記事を読むことから始めましょう..

プログラミングができるなら、このライブラリが役に立ちます。

于 2009-11-24T13:19:15.740 に答える
0

私はこのようなことをします：

For each item in my combination ( 1 then 2 ) do the following
* For each item in the set (1, 2, 3, then 4) do the following
** if set item is different from both combination item 1 and 2
*** print out combination item and print out set item
于 2009-11-24T13:21:36.143 に答える
0

Combinatoricsまたはより良いPermutationsを試してください。

于 2009-11-24T13:22:16.047 に答える
0

aとbの両方がYに現れない場合、セットX = { a , b } とYは互いに素です。したがって、 aが Y に含まれる場合、または b がYに含まれる場合、XとYは互いに素ではありません。

{ a , b }と互いに素ではない他の集合の数を調べるには、すべての可能性を検討してください。一般に、{ a , b }と素ではない 2 つの要素を持つすべての集合は、{ a , x } または{ a , x }の形式です。 { b , x }、元のセットの任意のx 。元のセットにn 個の要素があった場合、{ a , x } にはn個の可能性があり、 { b , x } には別のn個の可能性があり、合計で 2*n* になります。

ただし、{ a , b } は { a , x } ( x = bの場合) と { b , x } ( x = aの場合) の両方の形式であるため、2 回カウントしています。{ a , b } は最初に使用したセットと同じであるため、0 回カウントする必要があります。したがって、2 を引くと、合計は 2*n* - 2 になります。

しかし、まだ{ a , a } ( x = a の場合) と { b , b } ( x = bの場合) を数えています。しかし、これらにはそれぞれ 1 つの要素 ({ a , a } = { a } および { b , b } = { b }) しか含まれていないため、それらを数えるべきではありません。したがって、2 を引くと、合計は 2*n* - 4 になります。

あなたの例では、{1, 2, 3, 4} は n = 4 を与えるため、{1, 2} と素ではない要素の数は 2*4 - 4 = 4 です。

于 2009-11-24T13:41:34.760 に答える