🦋

写像12相をJulia言語で実装する!

2024/05/23に公開

Julia

math

idea

はじめに

私は勤務校で数学を教えていますが，先日「場合の数」の範囲のテストを実施しました。

その中に次のような問題があり，さらに，解答についてどこが違うのか説明を求めるポストをしました。

たくさんの方々に解説いただきました。ありがとうございました。

この $n$ 人を $k$ 組に分ける方法の総数は第2種スターリング数と呼ばれており， $S(n,k)$ で表します。

第2種スターリング数 $S(n,k)$ には指数型母関数があります。

\frac{(e^x-1)^k}{k!}=\sum_{n=0}^\infty S(n,k)\frac{x^n}{n!}

最初，julia言語で求める時に，TaylorSeries.jlのパッケージを利用し，マクローリン展開をして，第2種スターリング数を求めてみました。

その後，どうもCombinatorics.jlのパッケージに第2種スターリング数が定義されていることに気づき，そちらで求めてみることにしました。

写像12相とは

第2種スターリング数をはじめ，場合の数のいくつかの数え方を「写像12相」という形でまとめられています。多くは「 $n$ 個のボールを $k$ 個の箱に入れる」形で話されます。

https://manabitimes.jp/math/893

今回はこれらを，julia言語で実装してみます。

julia言語での実装

全射（空箱なし）1~4

# 全射（空箱なし）

using Combinatorics

#(1) ボールn個区別あり，箱k個区別あり，全射（空箱なし）
f₁(n,k) = factorial(k)*stirlings2(n,k)


#(2) ボールn個区別あり，箱k個区別なし，全射（空箱なし）
f₂(n,k) = stirlings2(n,k)


#(3) ボールn個区別なし，箱k個区別あり，全射（空箱なし）
f₃(n,k) = binomial(n-1,k-1)


#(4) ボールn個区別なし，箱k個区別あり，全射（空箱なし）
f₄(n,k) = partitions(n,k) |> length

#ボール6個，箱4個
f₁(6,4),f₂(6,4),f₃(6,4),f₄(6,4)

(1560, 65, 10, 2)

任意の写像（空箱あり）5~8

# 任意の写像（空箱あり）

using Combinatorics

#(5) ボールn個区別あり，箱k個区別あり，任意の写像（空箱あり）
f₅(n,k) = k^n


#(6) ボールn個区別あり，箱k個区別なし，任意の写像（空箱あり）
f₆(n,k) = sum(stirlings2(n,i) for i = 1:k)


#(7) ボールn個区別なし，箱k個区別あり，任意の写像（空箱あり）
f₇(n,k) = binomial(n+k-1,k-1)


#(8) ボールn個区別なし，箱k個区別あり，任意の写像（空箱あり）
f₈(n,k) = sum(partitions(n,i) |> length for i=1:k)

#ボール6個，箱4個
f₅(6,4),f₆(6,4),f₇(6,4),f₈(6,4)

(4096, 187, 84, 9)

全射（箱には高々1個）9~12

# 単射（箱には高々1個）

using Combinatorics

#(9) ボールn個区別あり，箱k個区別あり，単射（箱には高々1個）
f₉(n,k) = binomial(k,n)*factorial(n)


#(10) ボールn個区別あり，箱k個区別なし，単射（箱には高々1個）
f₁₀(n,k) = 1


#(11) ボールn個区別なし，箱k個区別あり，単射（箱には高々1個）
f₁₁(n,k) = binomial(k,n)


#(12) ボールn個区別なし，箱k個区別あり，単射（箱には高々1個）
f₁₂(n,k) = 1

#ボール4個，箱6個
f₉(4,6),f₁₀(4,6),f₁₁(4,6),f₁₂(4,6)

(360, 1, 15, 1)

まとめ

第2種スターリング数も分割数もjulia言語のパッケージCombinatorics.jlに実装されており，とても便利でした。