🌻
Juliaで同じものを含む円順列・数珠順列の総数を求める
はじめに
9月は学園祭・文化祭のシーズンです。Xのポストで東大寺学園の文化祭での数学の問題が流れてきました。
その中で，数珠順列の問題があったので，もう一度考えてみたくなりました。
以前までの到達点
円順列に関しては，コードでリストを書いて数えなくても，考え方で数えられることはわかっていました。以前の私のブログでもまとめています。
その後，数珠順列についても考えてみたのですが，うまくまとまらず，リストを作成して数えていました。
一方で，数珠順列の総数について求めるアルゴリズムについて書いてあるサイトもありました。
この記事を書いた山田一男さんによると，重複数珠順列については，場合分けが4つほどあり，そこからはまとめるには至っていませんでした。今回は，この場合分けをJulia言語で実装し，できればシンプルにまとめられないかを考えました。
4つの場合分けについて
この4つの場合分けは，同じものを含む円順列を作った後に，裏に返して，同じ並びがあれば，1通りと数えるための場合分けです。簡単のために色の球で数珠を作ることを考えます。
＜場合分け＞
- 各色の球の個数が全て偶数個 例えば🔴🔴🔴🔴🔵🔵🔵🔵⚪️⚪️
- 奇数個が1色，あとは全て偶数個 例えば🔴🔴🔴🔵🔵🔵🔵⚪️⚪️
- 奇数個が2色，あとは全て偶数個 例えば🔴🔴🔴🔵🔵🔵⚪️⚪️
- 上記以外 例えば🔴🔴🔴🔵🔵🔵⚪️⚪️⚪️
今回の結果
結論から言うと，この4つの場合を次のようにまとめました。結構シンプルになったので，満足しています。
Juliaのコード
using Combinatorics # multinomial
using Primes # totient, divisors
# 同じものを含む円順列の総数
function enkan(a)
l = gcd(a) # a の最大公約数
N = sum(a) # 総和
p = 0
for k in divisors(l)
q = div.(a, k) # 成分ごと整数除算
p += totient(k) * multinomial(q...)
end
return p ÷ N
end
# 同じものを含む数珠順列の総数
function juzu(a)
N = sum(a)
t = enkan(a)
q = div.(a, 2)
m = count(isodd, a)
# 反転の寄与
if m ≤ 2
t += multinomial(q...)
end
return t ÷ 2
end
いくつかの例
@show juzu([3,2,2])
@show juzu([3,3,3])
@show juzu([3,2,1])
@show juzu([4,6])
@show juzu([4,2,1])
@show juzu([6,3])
@show juzu([2,2,2]);
juzu([3, 2, 2]) = 18
juzu([3, 3, 3]) = 94
juzu([3, 2, 1]) = 6
juzu([4, 6]) = 16
juzu([4, 2, 1]) = 9
juzu([6, 3]) = 7
juzu([2, 2, 2]) = 11
これで，数珠順列も怖くないですね！
Discussion