組み合わせ

どうしても分からないので、教えて下さい。

問題）20箇所の場所の中から6箇所選ぶ方法は何通りあるか？
　　　数え上げでなく、数式的に答えよ。　　　
　　　ただし、周期性を含めて考え、見方によっては等価な選び方だと
　　　見なせる選び方は、同じ選び方とする。


意味分からないですよね。うまく説明できなくて、すいません。
どういうことかというと、例で説明します。

例１）
○○○　の３箇所から１箇所選ぶ方法は１通り。

●○○、○●○、○○●　この組み合わせは全部下の組み合わせに帰着するので


・・・・○●○○●○○●・・・・

１通りです。

例２）
○○○○○○○○ の8箇所から4箇所選ぶことを考えるとき

○○●●●○●○　→　・・・○○●●●○●○○○●●●○●○・・・・

○○●○●●●○　→　・・・○○●○●●●○○○●○●●●○・・・・

上の２つの選び方は、同じ選び方。
画面に対して表裏逆に見れば(or 180度回転させれば）、
同じ組み合わせ。

ちなみに、
○○○○○○○○○○　の10箇所から6箇所選ぶ方法は
16通りです。（たぶん。）

よろしくお願いします。

No.12 回答者： AssurBanipal 回答日時： 2005/09/30 17:11

求める個数は、1032個 である。

(解法1)
ポリヤの数え上げ理論を使えば、求める個数は、
(1/40)*Σ_[k|20]{ EULER_PHI(k)*(x^k + y^k)^(20/k) }
+ (1/4)*((x^2 + y^2)^10 + (x+y)^2 * (x^2+y^2)^9)
を展開したときの x^14*y^6 の項の係数になる。
展開して x^14*y^6 の項の係数を求めると 1032 となる。


(解法2)
まず、14個の白球と6個の黒球を含む円順列の個数を求める。
それは、
(1/20)*Σ_[k|2]{ EULER_PHI(k)* (20/k)!/((14/k)!*(6/k)!) }
= 1944
個ある。
14個の白球と6個の黒球を含む数珠順列の個数は、
(1944-C(10,3))/2 + C(10,3)=1032 個。

No.11 回答者： stomachman 回答日時： 2003/01/04 20:58

チョンボ訂正です。

[1] 並び
誤：　P(m,n)＝{p｜len(p)＝m ∧ len(p)＝n}
正：　P(m,n)＝{p｜len(p)＝m ∧ wgt(p)＝n}

[3] 類別、問題の記述
誤：　{q｜q≡p}を「P(m,n)の≡による同値類」と呼ぶ。
正：　{q｜q≡p}を「pの≡による同値類」と呼ぶ。

誤：　同様にp∈P(m,n)のとき、{q｜q～p} を「P(m,n)の～による同値類」と呼ぶ。
正：　同様にp∈P(m,n)のとき、{q｜q～p} を「pの～による同値類」と呼ぶ。

誤：　∀p(p∈P(m,n) → ∃!x(x∈X/≡ ∧ p∈x))
正：　∀p(p∈P(m,n) → ∃!x(x∈P(m,n)/≡ ∧ p∈x))

誤：　∀p(p∈P(m,n) → ∃!x(x∈X/～ ∧ p∈x))
正：　∀p(p∈P(m,n) → ∃!x(x∈P(m,n)/～ ∧ p∈x))

[7]最大次数による並びの分類
誤：　Pr(m,n,f)＝{p｜p∈P(m,n) ∧ ∃q(p≡q^k) ∧ ∀j∀s(p≡s^j → j≦k)}
正：　Pr(m,n,f)＝{p｜p∈P(m,n) ∧ ∃q(p≡q^f) ∧ ∀j∀s(p≡s^j → j≦f)}

まだあるかも知れないけど、取りあえず。

No.10 回答者： stomachman 回答日時： 2003/01/04 09:09

stomachmanです。

　前回に続く本論です。なお、もう少し整理したら
|P(m,n)/～|＝(1/2)(|S(m,n)/≡|+|P(m,n)/≡|)
|S(m,n)/≡|＝if (mが偶数 ∧ nが奇数) then C(m/2-1,(n-1)/2)
else C(floor(m/2),floor(n/2))
|P(m,n)/≡|＝(1/m)Σ{f∈D(m,n)}(f|Pn(m/f,n/f)|))
|Pn(m,n)|＝C(m,n)-Σ{f∈(D(m,n)-{1})}|Pn(m/f,n/f)|
　　ただしD(m,n)はm,nの公約数の集合、D(m,n)-{1}はD(m,n)から1を除いたもの、
　　C(m,n)はm個中からn個を選ぶcombination、
　　floor(x)は切り捨て関数。
となりました。答|P(m,n)/～|が合うかどうか、幾つかの場合に計算してテストしてあります。というわけで、理論編です。すんげ長いです。

方針
　碁石でも並べて幾つか例を検討してみると、kony0さんのご指摘の通り、短い並びの反復で出来ている数珠（たとえば●○○●○○●○○のようなもの）の扱いがひとつのポイントだと分かります。反復の単位（●○○）が何通りあるかを調べることが必要ですが、これは反復の単位の長さ（この例の場合3）と同じ長さを持つ数珠順列の問題に帰着します。
　だから「長さ２０、○の個数１６の数珠」という特定の場合だけ検討するより、一般に長さm,○の個数nの場合について考察する方が見通しが良くなると考えました。（それに、その方が数学っぽくて美しいではないですか。）
　しかし、ややこしい。ややこしくて、説明が不正確になる。つまり直感が狂います。なもんですから、形式的な表記法を導入し、分かり切ってると思うことでも用語を定義して整理する、という方針でアプローチします。
　
　以下、定理の証明は省きました。
　[1]は本当に厳密な形式化をやると余りにうるさいので端折っています。このため、証明できない（けれどどう見たって自明の）定理が含まれています。
　[2]以降の定理は概ね容易に証明できますが、中には累積帰納法が必要なものもあります。（念のため、累積帰納法とはP(0)と∀k(∀j(j＜k → P(j)) → P(k))を証明することで命題∀jP(j)（jは自然数）を証明する方法で、数学的帰納法のバリエーションのひとつです。）

……………………………………………………………………………………
[0] 記号
・notP は命題Pの否定。
・P∧Q は命題Pと命題Qの連言、すなわちP and Q。
・P∨Q は命題Pと命題Qの選言、すなわちP or Q。
・P → Q は「PならばQ」、すなわち(notP)∨Q。
・P ⇔ Q は(P → Q)∧(Q → P)。
・∃!x(P(x))は 「P(x)を満たすxがただ一つ存在する」の意味。
すなわち∃x(P(x) ∧ ∀y(P(y) → x＝y))の意味。
・|X| は集合Xの「濃度」、すなわち要素の個数。例えば|{1,2,4}|＝3。
・{x｜P(x)} は述語P(x)を満たす全てのxから成る集合。
・A - B はA,Bが集合のとき、差集合{x｜x∈A ∧ not(x∈B)}のこと。
・<a,b>は順序対。<a,b>≠<b,a>, <a,a>≠<a>であることを除くと{a,b}と同じ。
・以下に出てくる数はすべて自然数0,1,2,....である。
・floor(x) はxを越えない最大の整数。例えばfloor(7/2)＝3
・x! は「xの階乗」。
・Σ{x∈X}f(x) はXの全ての要素xについて式f(x)の総和を取ることを表す。
　例えばΣ{x∈{1,2,4}}(2x+1)＝17
・∪X は（Xが集合を要素とする集合であって）Xの全ての要素xについて合併集合を作る操作を表す。例えば∪{{1,2},{2,4}}＝{1,2}∪{2,4}＝{1,2,4}
……………………………………………………………………………………
[1] 並び
「マル」（●か○）を一列に並べた「並び」qを考える。
qに含まれるマルの個数を「qの長さ」と呼んでlen(q)と書く。qに含まれる○の個数を「qの重み」と呼んでwgt(q)と書く。当然 0≦wgt(p)≦len(p)である。
＊例えばlen(○○●)＝3, wgt(○○●)＝2です。
特にlen(q)＝0のとき、q＝εと書く。
m,n (m≧n≧0)について
　P(m,n)＝{p｜len(p)＝m ∧ len(p)＝n}
と定義する。
len(p)＝i, wgt(p)＝jである並びの場合の数をC(i,j)と書く。
C(i,j)＝|P(i,j)|
　C(i,j)＝i!/j!/(i-j)!
である。
＊これは単なる組み合わせ(combination)の計算です。

二つの並びp,qを繋いだ並びをpqと書く。
並びqをn個繋いだものを、q^nと書く。すなわち
　　q^0＝ε、n≧1のときq^n＝(q^(n-1))q
qを左右ひっくり返したものを「qの反転」と呼んでq'と書く。
p＝p'のとき、pは「自己反転」であると言う。

定理1-1 ε'＝ε, pε＝p, εp＝p
定理1-2 p^n＝ε ⇔ (p＝ε ∨ n＝0)
定理1-3 (p')'＝p, (pq)'＝q'p', (p'＝q' ⇔ p＝q), (p^n)'＝(p')^n
定理1-4 (p^n)p＝p(p^n)＝p^(n+1), (p^j)(p^k)＝p^(j+k)
定理1-5 p((qp)^n)＝((pq)^n)p
定理1-6 len(p)＝0 → p＝ε, len(p)≦1 → p＝p'
定理1-7
len(p')＝len(p), wgt(p')＝wgt(p)
len(pq)＝len(p)+len(q), wgt(pq)＝wgt(p)+wgt(q)
len(p^n)＝n len(p), wgt(p^n)＝n wgt(p)
定理1-8 pq＝ε → (p＝ε ∧ q＝ε)
定理1-9 ((len(p)は奇数 ∧ p＝p') ⇔ ∃x∃q(len(x)＝1 ∧ p＝qxq'}),
((len(p)は偶数 ∧ p＝p') ⇔ ∃q(p＝qq'))
定理1-10 (ab＝cd ∧ len(a)＝len(c)) ⇔ (a＝c ∧ b＝d)
定理1-11 (ab＝cd ∧ len(a)≦len(c)) ⇔ ∃e(c＝ae ∧ b＝ed)
定理1-12 (p＝q^i ∧ i≧1) ⇔ ∃s∃t∃j(q＝st ∧ p=(q^j)st(q^(i-j-1)))
定理1-13 0≦j≦len(p) ⇔ ∃!a∃!b(p＝ab ∧ j＝len(a))

＊マジメにやるためには、最初にεと、マルを並びの右にくっつける演算を定義して、そこから並びおよびその反転を作ることになるでしょうけれども、当たり前過ぎてかったるいですね。（どんな風にやるかについては、例えば形式文法の理論の初めの部分を参照なさると宜しいでしょう。）その代わりに、上記の定理の幾つかをうまく選んで公理にするという手もありますが、公理系として丁度ピッタリであるかどうかを検討するのも結構な手間です。だからここでは手抜きします。手抜きの結果、これらの（自明だけど、以下の議論で必須になる）定理の幾つかは証明できないままになります。

定理1-14
(ab＝ba) ⇔ ∃i∃j∃q(a＝q^i ∧ b＝q^j)
＊累積帰納法で証明できます。

len(p)＝i, wgt(p)＝jである自己反転の並びの場合の数をCs(i,j)と書く。
Cs(i,j)＝|{p｜p∈P(i,j) ∧ p＝p'}|

定理1-15
Cs(i,j)＝if (iが偶数でjが奇数) then 0 else C(floor(i/2),floor(j/2))

……………………………………………………………………………………
[2] 円環順列としての同値(≡)と数珠順列としての同値(～)
・円環順列として同値であることを表す記号"≡"を次のように定義する。
　p≡q ⇔ ∃s∃t(p＝st ∧ q＝ts)
＊円環をぐるぐる廻す操作に相当することを、真っ直ぐ並べた並びで表したに過ぎません。例えば○●●○●○≡○●○○●●です。なぜなら、
○●●○●○＝(○●●)(○●○), ○●○○●●＝(○●○)(○●●)
だからです。しかし○●●○●○と○●○●●○は≡で結べません。

定理2-1（≡の性質）
・≡は同値関係である。即ちp≡p, (p≡q → q≡p), ((p≡q ∧ q≡r) → p≡r)
・ab≡ba, (st)^n≡(ts)^n
・p≡q → (len(p)＝len(q) ∧ wgt(p)＝wgt(q))

数珠順列としての同値"～"は次のように定義する。
　p～q ⇔ (p≡q ∨ p≡q')
＊～は、反転と≡であるものも含めて同値と考える訳です。
たとえば○●●○●○～●●○○●○です。

定理2-2
　～は同値関係である。
……………………………………………………………………………………
[3] 類別、問題の記述
＊同値類、類別（商集合）の概念は数学ではおなじみですが念のため。
p∈P(m,n)のとき、{q｜q≡p} を考えると、
{q｜q≡p}⊂P(m,n)
は自明である。{q｜q≡p}を「P(m,n)の≡による同値類」と呼ぶ。
集合Xの≡による類別X/≡とは
X/≡＝{{q｜q≡p}｜p∈X}
のことである。
同様にp∈P(m,n)のとき、{q｜q～p} を「P(m,n)の～による同値類」と呼ぶ。
集合Xの～による類別X/～とは
X/～＝{{q｜q～p}｜p∈X}
のことである。
同値類の一般的性質として、
∀p(p∈P(m,n) → ∃!x(x∈X/≡ ∧ p∈x))
not(p≡q) ⇔ {r｜r≡p}∩{r｜r≡q}＝φ
p≡q ⇔ {r｜r≡p}＝{r｜r≡q}
∀p(p∈P(m,n) → ∃!x(x∈X/～ ∧ p∈x))
not(p～q) ⇔ {r｜r～p}∩{r｜r～q}＝φ
p～q ⇔ {r｜r～p}＝{r｜r～q}
である。
＊たとえば
P(4,2)＝{○○●●,○●○●,●○○●,○●●○,●○●○,●●○○}
P(4,2)/≡ ＝{{○○●●,●○○●,●●○○,○●●○},{○●○●,●○●○}}
|P(4,2)/≡|＝2
P(4,2)/～＝P(4,2)/≡
です。

以上の記法を使うと、問題は
「P(m,r)の～による類別P(m,r)/～の要素の個数|P(m,r)/～|を求む」
である。
……………………………………………………………………………………
[4] 縮退
p≡q^k (q≠ε)
となるqが存在するとき、pは「k次の縮退」であると言う。
kが存在して(k≧2)であり、pがk次の縮退であるとき、pは「縮退」であるという。
pがk次の縮退であり、しかもkより大きい任意のjについてj次の縮退でないとき、つまり
∃q(p≡q^k ∧ q≠ε) ∧ ∀j∀r(p≡r^j → j≦k)
であるとき、kをpの「最大次数」と呼ぶ。
＊「縮退」だの「最大次数」だのはいい加減に付けた名前です。

自然数m,nの公約数の集合をD(m,n)と書く。
D(m,n)＝{j｜ mはjで割り切れる ∧ nはjで割り切れる｝
また、D(m,n)-{1}は、D(m,n)から要素 1 を除いた集合である。
＊例えばD(12,4)＝{1,2,4}, D(12,4)-{1}＝{2,4}です。特にD(m,0)はmの全ての約数の集合になることは要注意です。例えばD(12,0)＝{1,2,3,4,6,12}。

定理4-1 （公約数と縮退の関係）
m＞0, f＞0のとき
(p∈P(m,n) ∧ p≡q^f) → (f∈D(m,n) ∧ q∈P(m/f,n/f))

定理4-2 （縮退の簡約化）
p≡q^n ⇔ ∃r(p＝r^n ∧ r≡q)
＊ごく簡単なことなんですが、この定理のおかげで縮退が扱いやすくなります。

定理4-3 （≡の分解一意性）
(p≠ε ∧ p≡q) ⇔
(∃!s∃!t(p＝st ∧ q＝ts ∧ t≠ε) ∨
∃f∃!r∃!u(f≧2 ∧ p＝r^f ∧ q＝u^f ∧ r≡u ∧ r≠ε))
＊pをp＝stと分けて、入れ替えて繋ぎts＝qを作ったとします。そのとき、pを「分けて入れ替えて繋ぐ」ことによってqを作る方法は（もしpが縮退でないのなら）１通りしかない。この定理は数え上げの方法の根拠となります。
……………………………………………………………………………………
[5] 自己鏡像
p≡p'であるとき、pを「自己鏡像である」と呼ぶ。
＊pが自己反転(p＝p')ならpは自己鏡像ですが、逆は言えません。例えば○●≡●○だから○●は自己鏡像だけれど、自己反転ではありません。もちろん「自己鏡像」だの「自己反転」だのはいい加減に付けた名前です。

定理5-1 （自己鏡像の基本定理）
p≡p' ⇔　∃a∃b(p＝ab ∧ a＝a' ∧ b＝b')
系1
(p≡p'∧ p≠ε) ⇔ ∃a∃b(p＝ab ∧ a＝a' ∧ b＝b'∧ b≠ε)
＊自己鏡像を自己反転に帰着する定理です。自己反転なら扱いやすい。因数分解みたいですね。

定理5-2 （縮退における自己鏡像の再帰性）
(n≧1 ∧ p＝x^n) → (p≡p' ⇔ x≡x')
＊この定理は縮退である自己鏡像の並びを数え上げるための原理になります。

定理5-3 （自己鏡像の分解一意性）
(p≠ε ∧ p≡p') ⇔
(∃!s∃!t(p＝st ∧ s＝s' ∧ t＝t' ∧ t≠ε) ∨
∃f∃!r∃!u(f≧2 ∧ p＝r^f ∧ r≡r' ∧ r≠ε))
＊この定理によって、縮退でない自己鏡像をイッパツで数え上げることが可能になります。
……………………………………………………………………………………
[6]自己鏡像の同値類の数え上げ
P(m,n)の要素のうち、自己鏡像である並びの集合をS(m,n)と書く。
S(m,n)＝{p｜p≡p' ∧ p∈P(m,n)}

定理6-1
m＞0のとき S(m,n)＝{p｜p∈P(m,n) ∧ ∃a∃b(p＝ab ∧ a＝a' ∧ b＝b')}
＊定理5-1から自明です。

m＞0のとき
F(m,n)＝{<a,b>｜a＝a' ∧ b＝b'∧ b≠ε∧ len(a)+len(b)＝m ∧ wgt(a)+wgt(b)＝n}
と定義する。

定理6-2（|F(m,n)|の計算方法 その１）
m＞0のとき
|F(m,n)|
　＝Σ{i∈{0,..,m-1}}Σ{j∈{max(0,n-m+i),..,min(i,n)}}Cs(i,j)Cs(m-i,n-j)
＊これはF(m,n)の定義から直ちに導けます。

定理6-3 （|F(m,n)|の計算方法 その２）
m＞0のとき
|F(m,n)|＝if (mが偶数 ∧ nが奇数) then m C(m/2-1,(n-1)/2)
else m C(floor(m/2),floor(n/2))
＊定理6-2より遙かに簡単な計算方法です。定理6-2とCs(i,j)の定義からゴリゴリと計算して証明できますが、直接F(m,n)の定義からもうちょっとカッコよく導くこともできます。

定理6-4　（自己鏡像のFによる表現）
m＞0のとき
S(m,n)＝{ab｜<a,b>∈F(m,n)}

定理6-5 （自己鏡像の≡による類別の数え上げ定理）
m＞0のとき、
p∈S(m,n) → m＝|{<a,b>｜<a,b>∈F(m,n) ∧ p≡ab}|
|S(m,n)/≡|＝|F(m,n)|/m
＊pが縮退でないときはp, pを1マルずらしたもの, 2マルずらしたもの、…がそれぞれab (a＝a', b＝b')の形でただ一通りに表せて、<a,b>がF(m,n)に含まれている。だからp≡abとなる<a,b>はF(m,n)に丁度m個含まれています。
＊pがf次の縮退の場合には、p, pを1マルずらしたもの, 2マルずらしたもの、…を数えるとm/f通りあるけれど、そのそれぞれp≡q^f, q≡q'について、（qが縮退でなければ）q＝st, ( s＝s',t＝t')と表す方法がただ一通りあり、p＝ab, a＝((q^i)s), b＝(g(q^(k-1-i)))と表す方法が丁度f通り(i＝0,1,...,f-1)あるので、結局p＝abとなるm通りの<a,b>がF(m,n)に含まれています。
＊かくて、自己鏡像である並びの同値類の個数|S(m,n)/≡|はイッパツで計算できるわけです。しかし残念なことに、自己鏡像でない並びの同値類の個数をイッパツで計算する方法は未知です。
……………………………………………………………………………………
[7]最大次数による並びの分類
m＞0のとき、
Pr(m,n,f)＝{p｜p∈P(m,n) ∧ ∃q(p≡q^k) ∧ ∀j∀s(p≡s^j → j≦k)}
と定義する。
＊すなわちf≧2のとき、Pr(m,n,f)とは、p∈P(m,n)であって、pが縮退であって、pの最大次数がfであるような並びpの集合です。
さらに
Pn(m,n)＝{p｜p∈P(m,n) ∧ ∀f(f≧2 → not(p∈Pr(m,n,f))}
と定義する。
＊Pn(m,n)は縮退でない並びの集合です。

定理7-1（Pr(m,n,f)の分離性）
m＞0のとき
∀f∀g(f∈D(m,n)∧g∈D(m,n) ∧ f≠g) → Pr(m,n,f)∩Pr(m,n,g)＝φ

定理7-2 （Pr(m,n,f)の再帰性）
m＞0のとき
　Pr(m,n,f)＝{p｜∃q(p＝q^f ∧ q∈Pn(m/f,n/f))}
系1
m＞0のとき Pn(m,n)＝Pr(m,n,1)
系2
m＞0のとき |Pr(m,n,f)|＝|Pn(m/f,n/f)|

定理7-3（|Pr(m,n,f)/≡|の数え方）
m＞0のとき |Pr(m,n,f)/≡|＝|Pn(m/f,n/f)/≡|
……………………………………………………………………………………
[8] 数え上げ

定理8-1（|Pn(m,n)/≡|の数え方）
m＞0のとき |Pn(m,n)/≡|＝(1/m)|Pn(m,n)|

定理8-2
m＞0のとき
|P(m,n)|＝Σ{f∈D(m,n)}|Pr(m,n,f)|
|P(m,n)/≡|＝Σ{f∈D(m,n)}|Pr(m,n,f)/≡|

定理8-3
m＞0のとき
|S(m,n)/～|＝|S(m,n)/≡|
|P(m,n)/～|＝(1/2)(|S(m,n)/≡|+|P(m,n)/≡|)

定理8-4　（|Pn(m,n)|を計算する再帰的アルゴリズム）
m＞0のとき
|Pn(m,n)|＝C(m,n)-Σ{f∈(D(m,n)-{1})}|Pn(m/f,n/f)|

定理8-5 （数珠順列の～および≡による類別の数え上げ定理）
m＞0のとき
|P(m,n)/～|＝(1/2)(|S(m,n)/≡|+|P(m,n)/≡|)
|S(m,n)/≡|＝if (mが偶数 ∧ nが奇数) then C(m/2-1,(n-1)/2)
else C(floor(m/2),floor(n/2))
|P(m,n)/≡|＝(1/m)Σ{f∈D(m,n)}(f|Pn(m/f,n/f)|))
|Pn(m,n)|＝C(m,n)-Σ{f∈(D(m,n)-{1})}|Pn(m/f,n/f)|
＊この計算方法をすなおに実行すると、同じi,jについて何度も|Pn(i,j)|を計算することになり、損です。ですけどまあ、そこから先はプログラムの最適化の問題に過ぎません。
……………………………………………………………………………………
＊以上の理論は、○と●の２種類だけでなく、一般にN+1種類(N≧1)のマルを用いて数珠pを作る場合にも、wgt(p)をベクトル値関数（各種類のマルの個数を表すベクトル）にすれば（従ってP(m,n)ではなくP(m,<n1,n2,....,nN>)を考えれば）容易に拡張できるでしょう。

No.9 回答者： stomachman 回答日時： 2002/12/24 09:54

ずーっと考えてまして、やっとこさ解決しました。

しかし、きちんとやるとすんごく長くなります。つーか、まだ細かい（自明と思われるけれど形式化すると記述が長くなる）部分の証明は書き上げていません。
ですから、結果だけを。

m個のタマのうちn個を○に（或いは●に）する数珠の種類の数は以下の式で計算できる　|P(m,n)/～| です。そして、
|P(10,6)/～|=16
|P(20,12)/～|=3260
です。

|P(m,n)/～|=|S(m,n)/～|+|A(m,n)/～|.
|S(m,n)/～|= mが偶数でnが奇数のとき C(m/2-1,(n-1)/2),
　　　　　　　　さもなくばC(floor(m/2),floor(n/2)).
|A(m,n)/～|=(1/(2m))Σ{f∈D(m,n)}(f|An(m/f,n/f)|).
|An(m,n)|=|Pn(m,n)|-|Sn(m,n)|.
|Pn(m,n)|=C(m,n)-Σ{f∈(D(m,n)-{1})}(|Pn(m/f,n/f)|).
|Sn(m,n)|=|S(m,n)|-Σ{f∈(D(m,n)-{1})}(|Sn(m/f,n/f)|).
|S(m,n)|=m(|S(m,n)/～|)-Σ{f∈(D(m,n)-{1})}((f-1)|Sn(m/f,n/f)|).

注１：C(m,n)はm個中n個を選ぶcombination。
C(m,n)=m!/n!/(m-n)!.

注２：floor(x)=xを越えない最大の整数
例えば
floor(5/2)=2.

注３：D(m,n)={f｜fはmとnの公約数}, ただし1∈D(m,n).
D(m,n)-{1} はD(m,n)から要素1を除いたもの。
例えば
D(12,4) = {1,2,4}、D(12,4)-{1}={2,4}.

注４：Σ{i∈X}(g(i)) とは Xの要素である各iについて、g(i)の総和を取る事を表す。
ただし、Xが空集合ならΣ{i∈X}(g(i)) =0.
例えば
Σ{i∈{2,3,5}}(i^2) = 2^2+3^2+5^2=4+9+25.

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～
基本的な考え方はkony0さんの真似っこです。kony0さんの最初の解析では『「裏返しても同じ円順列」には軸があって、それは○か●』という仮定がちょっと失敗でしたね。
「裏返しても同じ円順列」の一つの表現は：
『タマの並びsと並びtがそれぞれ左右反転しても同じであるとき、これらをつないだ並びstは「裏返しても同じ円順列（を一箇所で切って真っ直ぐにのばしたもの）」である。また「裏返しても同じ円順列」は必ずこの形をしている。』
ということです。
たとえば上記の
●●○○○○○○○○は円順列としては
○●●○○○○○○○と同値ですし、
○○○○●●○○○○とも同値です。そしてこれらは
s=(●●), t=(○○○○○○○○)
s=(○●●○), t=(○○○○○○)
s=(), t=(○○○○●●○○○○)
と表せます。
そして、上記の式で
|S(m,n)/～|= mが偶数でnが奇数のとき C(m/2-1,(n-1)/2),
　　　　　　　　さもなくばC(floor(m/2),floor(n/2)).
というのが、「裏返しても同じ円順列」の種類の数です。残念ながら|A(m,n)/～|（「裏返しても同じ円順列」ではないものの種類の数）の方は、もっと簡単な計算方法がないものか、まだ分かりません。

この回答へのお礼

お礼が遅くなってしまってすいません。
ずっと体調が悪かったことと、卒論の追われている関係で
遅くなってしまいました。

　卒論の目星がつきしだい、ご回答を参考によく考えようと思っています。
2月になってしまうと思いますが、質問させていただくこともあると思いますので、
その折りにはよろしくお願いします。ご回答をいただきながら
放っておくことになってしまい、すいません。

お礼日時：2003/01/16 14:49

No.8 回答者： kony0 回答日時： 2002/12/18 06:13

大変お久しぶりです。

えっと、根本的に考慮不足な点がございました。(汗)
それは、「対称の軸が、玉と玉の間を通る場合」を考え忘れておりました。
たとえば、
→●●○○○↓
↑●●○○○←
というやつです。（●●●●○○○○○○）
このタイプに該当するのは、片側の5C2通りを考えて、
→●●○○○↓　→○○○●●↓
↑●●○○○←　↑○○○●●←
ただし、上記のようなものは円順列的に考えて同じものです。（5C2通りのうち、左右非対称なものについて●●○○○と○○○●●のような２つずつのペアができる。）
ということで5C2=10通りのうち左右対称なのは2C1=2通りであることから、該当する円順列は2+(10-2)/2=6通りあります。

ここで、左右対称な2C1通りについては、
→●○(○)○●↓
↑●○(○)○●←
「対称の軸が白となる場合」、「対称の軸が玉と玉の間となる場合」の複数の軸を併せ持ちます！（上記の（）書きの白を軸にする場合と、横半分を軸にする場合）
ということで、これら２通りは実はすでに数え上げていたことに留意して、

結局裏返しても同じものは、＃６の６通り＋今回新たに（６－２＝）４通りあることが判明しました。

つまり２２個の円順列のうち、１０個は裏返してももとの円順列と同じ、残り１２個については数珠順列的に同じとなるペアがあるもの。
ということで、数珠順列の個数は10+(22-10)/2=16通りとなります。（ふぅ）

ちなみに、#6の補足にある例でいうと、
4,5,7,14,15,16が、#6で考えた6個。
1,6,7,11,13,16が、今回考えた6個であり、
7,16が重複したものに相当します。

・・・で、本題の20個中12個を選ぶ問題は。。。これはもっと考慮しないといけなさそうで、大変ですぞ．きっと。。。

この回答へのお礼

回答ありがとうございます。
お礼が遅くなってしまって、すいません。
去年の末から、風邪をひいてしまい
まだ直らなく、よく考えられないのですが
直り次第、よく考えてみます。

お礼日時：2003/01/04 21:51

No.7 ベストアンサー 回答者： kony0 回答日時： 2002/11/24 02:53

同じ手法で20個中12個を選んでみましょう。

これは円順列が一段と難しいです。○12個と●8個を並べるのですが、GCM(12,8)=4であることから、1列に並べる並べ方20C12のうち、周期10×2周のものと、周期5×4周のものがあります。
・周期5×4周・・・5C3=10通り→円順列: 10/5=2個
・周期10×2周・・・10C6-5C3=200通り→円順列: 200/10=20個
・周期20×1周・・・20C12-10C6=125,760通り→円順列: 125,760/20=6,288個
よって、円順列の合計は6,310個あります。

さて、このうち裏返しても同じになる円順列の個数を求めましょう。
同じく軸に○or●がくるそれぞれの場合を考えて、
1)軸に○がくる場合・・・あと右半分に○5個と●4個を並べます。（9C5通り=126通り）
そのうち、これら9個自身が左右対称になるのは、真中に○があって、あと○2個と●2個を並べる4C2=6通り
よって、軸が○である、裏返しても同じ円順列は(126-6)/2 + 6=66個あります。
2)軸に●がくる場合・・・あと右半分に○6個と●3個を並べます。（9C6=84通り）
そのうち、これら9個自身が左右対称になるのは、真中に●があって、あと○3個と●1個を並べる4C3=4通り
よって、軸が●である、裏返しても同じ円順列は(84-4)/2 + 4=44個あります。
1)2)より、裏返しても同じ円順列は110個。残りの6200個は裏返すと同じになる円順列のペアがあることになるので、求める個数は6200/2 + 110 = 3,210個・・・（答）

うーん、#6の考え方自身に間違いがあるとどうしようもないのですが、一旦これで回答といたします。

No.6 回答者： kony0 回答日時： 2002/11/24 02:37

難しいので、○６個と●４個を並べるほうで。

^^;
まず、円順列は(10C6-5C3)/10 + (5C3)/5 = 22通りです。
これは、一列に並べたものを考えたときに10C6通りあるのですが、
○○○○○○●●●●
○○○○○●●●●○
○○○○●●●●○○
○○○●●●●○○○
○○●●●●○○○○
○●●●●○○○○○
●●●●○○○○○○
●●●○○○○○○●
●●○○○○○○●●
●○○○○○○●●●
の10個は同じ円順列になります。ところが、
○○○●●○○○●●と同じ円順列になるのは
○○●●○○○●●○
○●●○○○●●○○
●●○○○●●○○○
●○○○●●○○○●
の５つしかありません。
これは、｜○○○●●｜○○○●●｜というように、1列の順列の中で周期5のものが２つ並んでいるためです。
10C6=210通りの順列の中で、周期5のものは5C3=10通りあります。残りの200通りは周期10の順列です。
ということで、円順列の個数が(10C6-5C3)/10 + (5C3)/5 = 22となります。

次に、円順列のうち、裏返して同じものが何個あるかなんですが。
これは左右対称の軸になるものを固定して考えることが可能です♪
1)この軸上（軸は南北方向に置くことにします）に○がくる場合
軸の右半分に○２個と●２個を並べます。並べ方は4C2=6通り
○－○○●●－○－●●○○5212
○－○●○●－○－●○●○31111111
○－○●●○－○－○●●○3232
○－●○○●－○－●○○●21112111
○－●○●○－○－○●○●31111111☆
○－●●○○－○－○○●●5212☆
しかし円順列にした場合、上から2番目と5番目、1番目と6番目は同じモノになります。
これは軸の右半分に並べたものが左右対称になっていないものについては裏がある（1個目と6個目でいうと○○●●に対する●●○○の存在）に対応します。
また3個目のような○●●○のパターンは、裏を考えても自分自身となります。
2)軸上に●がくる場合
●－○○○●－●－●○○○3331
●－○○●○－●－○●○○21111121
●－○●○○－●－○○●○21111121☆
●－●○○○－●－○○○●3331☆
この場合は、軸の右半分に並べるものとして、左右対称になりえないため、必ず裏の並びがある（○○○●に対する●○○○）ことになります。
これらの結果から、円順列のうち、裏返しても同じになるものは6通りあることになります。

結果として、数珠順列の個数は、22個の円順列のうち、6個は裏返してももとと同じであり、残りの16個の円順列については裏返すと他の円順列があるということに相当します．
ということで、求める円順列は(22-6)/2 + 6=14個となるのですが、どうでしょうか？（domdomdomさんの16個と答えが違うので自信がないのですが・・・）

この回答へのお礼

遅くなってしまいましたが、回答ありがとうございます。
答えなのですが、円順列は22通りだと思うのですが
数珠陣列は、やはり16通りだと思います。

一応、僕の考えた10箇所から6箇所選ぶ方法を示しますと
下のようになりました。（●4箇所 〇6箇所）　


数珠順列（16通り）　　　　　　　　省いた選び方（6通り）

●●●●〇〇〇〇〇〇
●●●〇●〇〇〇〇〇　　　←　●●●〇〇〇〇〇●〇
●●●〇〇●〇〇〇〇　　　←　●●●〇〇〇〇●〇〇
●●●〇〇〇●〇〇〇
●●〇●●〇〇〇〇〇
●●〇〇●●〇〇〇〇
●●〇〇〇●●〇〇〇　　　　
●●〇●〇●〇〇〇〇　　　←　●●〇〇〇〇●〇●〇
●●〇●〇〇●〇〇〇　　　←　●●〇〇〇●〇〇●〇
●●〇●〇〇〇●〇〇　　　←　●●〇〇●〇〇〇●〇
●●〇●〇〇〇〇●〇
●●〇〇●〇●〇〇〇　　　←　●●〇〇〇●〇●〇〇
●●〇〇●〇〇●〇〇
●〇●〇●〇●〇〇〇
●〇●〇●〇〇●〇〇
●〇〇●〇●〇〇●〇

もしよかったら、まだアドバイスいただけるとうれしいです。

お礼日時：2002/11/27 14:30

No.5 回答者： kony0 回答日時： 2002/11/24 02:03

＃４さんの「１つを固定して残りを並べる方法」は、「同じものを含む」円順列では使えません。

たとえば、白２つ黒２つの円順列で、白を１個固定して、そこから時計回りに○（固定）－○●●と並べるのと○（固定）－●●○と並べるのでは、円順列として同じモノになるためです。（これらを重複してカウントすることになる）

では、同じモノを含む円順列の考え方はというと・・・私は、１列の順列を考えて、そのうち円順列にしたら同じになるものが何個あるかという考え方以外にないのではないかなぁと思っています．これが「同じモノを含む円順列」の難しいところです。この考え方をもとにして、数珠の「裏返して同じ」を考慮するのは難しい・・・いまだに妙案が浮かんでこないところです。(汗)

No.4 回答者： shinnopapa 回答日時： 2002/11/23 18:42

俗に言う「同じものを含む数珠順列」ですね。

１２個の黒玉と８個の白玉とで輪を作る問題と同じと考えます。

１　まず円順列にするために一つの○を固定します。
残り黒１２と白７の「同じものを含む順列」です。　１９Ｃ７

２　次に数珠順列だと、この１／２ですが、この中には「左右対称」のものがあります。左右対称は裏返してもそれ自身なので１／２しません。
これは初め固定した白の向かいに白、左がわに白３つと黒６つを並べ、右を同じように並べばよいので　９Ｃ３

３　１から２を引いて１／２倍し、２を加えます。

（１９Ｃ７－９Ｃ３）／２　＋　９Ｃ３

この回答へのお礼

回答ありがとうございます。僕が間違えているのかもしれないのですが、
この考え方でいくと、10箇所から6箇所を選ぶ方法は

(9C3-4C1)/2+4C1=44(通り）

ですよね。なんか違う気がするのですが。
僕が間違っていたら、本当にごめんなさい。
そもそも、実際は（上の回答が正解なのかもしれないですが）
何通りなんでしょう？
僕は、プログラム作ってみたのですが
プログラム初心者なせいもあり、メモリを使いすぎてしまい
最後まで動いてくれませんでした。
この問題（選び方の数）を求めるような
プログラムを作れる方がいらっしゃいましたら、ぜひ
プログラムのソースを教えて下さい。
僕は、Perl,C言語、C++だったら一応使えます。

お礼日時：2002/11/23 19:51

No.3 回答者： kony0 回答日時： 2002/11/22 12:32

この問題は、いわゆる「数珠順列」の問題です。

・・・「円順列」考えるだけでも難しい問題なのに・・・

円順列の個数からいきましょう。
式でいうと、(20C6-10C3)/20 + 10C3/10 = 1944個です。

肝心の数珠順列は・・・アイデアがすぐ浮かばないので、浮かべば書きます。^^;

この回答への補足

上のお礼の式間違えました。

(20C12-10C6)/20+16

ですよね。(16は、僕が考えた10箇所から6箇所を選ぶ選び方の数。）
どちにしろ、僕の考え方間違えてたりして。(^_^;

補足日時：2002/11/22 21:33

この回答へのお礼

上の式は、10箇所から3箇所選ぶ選び方に、その選び方とは違う
20箇所から6箇所選ぶ選び方を足しているということですよね？
円順列は分かった気がします。ありがとうございます。


○・・・○|○・・・○
　10箇所　　10箇所

ところで、とても恥ずかしいことに問題間違えていました。
本当は、20箇所から12箇所選ぶ選び方を知りたかったのです。
とはいっても、根本的な考え方は同じですよね。

＜円順列＞
(20C12-10C6)/20+10C6/10

お礼日時：2002/11/22 21:21