3
高校数学解説
文献あり

nCr, nPr, nHrの残りの仲間を探す

6
0
$$$$

導入

$ {}_n \mathrm{C}_r $は、

  • $ n $個のものから$ r $個を選ぶ方法
  • $ n $個のもののうち$ r $個に「選ぶ」というラベルを与える方法
  • $ n $個の区別できる箱に$ r $個の区別できない玉を箱の重複なく入れる方法

の数とみなすことができます。

また、$ {}_n \mathrm{P}_r $は、

  • $ n $個のものから$ r $個を選んで並べる方法
  • $ n $個のもののうち$ r $個に「$ 1 $番目」~「$ r $番目」というラベルを与える方法
  • $ n $個の区別できる箱に$ r $個の区別できる玉を箱の重複なく入れる方法

の数とみなすことができます。

最後の言い換えでは、$ {}_n \mathrm{H}_r $は

$ n $個の区別できる箱に$ r $個の区別できない玉を箱の重複を許して入れる方法

と表現することができます。

では、残りの1つは?

となると、

$ n $個の区別できる箱に$ r $個の区別できる玉を箱の重複を許して入れる方法

を考えたくなりますが、これは$ n^r $に等しいことが直ちにわかります。まれに$ {}_n \Pi_r $という表記が使われるようです。

https://zenn.dev/anozon/articles/permutation-programming

もう1つの自由度

ここまでで
$ n $個の区別できる箱に$ r $個の(区別できる/区別できない)玉を箱の(重複なしで/重複を許して)入れる方法
の$ 4 $パターンを列挙しました。
しかし、箱の区別がまだ残っています。
箱の区別をなくすと、もう$ 4 $パターンの構文が現れます。
この記事だけの記号として、これらに対応する記号は、箱の区別があるときの記号に$ \tilde{\phantom{\mathrm{C}}} $をつけて表すことにします。

正確な定義は以下です。

$ _n \tilde{\mathrm{C}}_r $は、$ n $個の区別できない箱に$ r $個の区別できない玉を箱の重複なく入れる方法の数である。
$ _n \tilde{\mathrm{P}}_r $は、$ n $個の区別できない箱に$ r $個の区別できる玉を箱の重複なく入れる方法の数である。
$ _n \tilde{\mathrm{H}}_r $は、$ n $個の区別できない箱に$ r $個の区別できない玉を箱の重複を許して入れる方法の数である。
$ _n \tilde{\Pi}_r $は、$ n $個の区別できない箱に$ r $個の区別できる玉を箱の重複を許して入れる方法の数である。

自明なケース

$ _n \tilde{\mathrm{C}}_r $は、箱も玉も区別しません。そのため、「$ n $個の箱に$ r $個の玉を$ 1 $個ずつ入れる」全てのパターンが同じと数えられるため、以下の式が成り立ちます。

$ _n \tilde{\mathrm{C}}_r = \begin{cases} 1\ (0 \leq r \leq n) \\ 0\ (\text{otherwise}) \end{cases} $

$ _n \tilde{\mathrm{P}}_r $には玉の区別はありますが、箱の区別がないので箱を並べ替えて玉を特定の順序($ 1 $番から$ r $番など)に固定することができます。すると、やはり「$ n $個の箱に左から順に$ r $個の玉を$ 1 $番から順に入れる」$ 1 $パターンしかないので、以下の式が成り立ちます。

$ _n \tilde{\mathrm{P}}_r = \begin{cases} 1\ (0 \leq r \leq n) \\ 0\ (\text{otherwise}) \end{cases} $

分割数

$ _n \tilde{\mathrm{H}}_r $の場合は、「各箱に入れる個数」による区別が生まれます。このとき、たとえば玉が$ 4 $個あれば

\begin{align*} &\ 4 \\ =&\ 3+1 \\ =&\ 2+2 \\ =&\ 2+1+1 \\ =&\ 1+1+1+1 \end{align*}

のような分解が考えられます。

すなわち、$ _n \tilde{\mathrm{H}}_r $は「$ r $を$ n $個以下の正整数の和として表す方法」の個数であり、$ 0 \leq r \leq n $のときは必ず$ n $によらない値を取ります。この値は$ r $の分割数と呼ばれ、それ自体興味深い研究対象です。

直和分割

$ _n \tilde{\Pi}_r $は少し難しいです。「集合$ \{ 1, 2, \cdots, r \} $を、最大$ n $個の集合に直和分解する方法」の数です。
「集合$ \{ 1, 2, \cdots, r \} $を、ちょうど$ n $個の集合に直和分解する方法」の数は、第二種スターリング数として知られています。また、$ 0 \leq r \leq n $のときは全ての直和分解が数えられます。この場合の数はベル数と呼ばれます。

まとめ

箱玉重複記号$ 0 \leq r \leq n $$ r > n $
区別する区別しないなし$ _n \mathrm{C}_r $二項係数$ 0 $
区別する区別するなし$ _n \mathrm{P}_r $下降階乗冪$ 0 $
区別する区別しないあり$ _n \mathrm{H}_r $(二項係数)(二項係数)
区別する区別するあり$ _n \Pi_r $冪乗冪乗
区別しない区別しないなし$ _n \tilde{\mathrm{C}}_r $$ 1 $$ 0 $
区別しない区別するなし$ _n \tilde{\mathrm{P}}_r $$ 1 $$ 0 $
区別しない区別しないあり$ _n \tilde{\mathrm{H}}_r $分割数制限された分割数
区別しない区別するあり$ _n \tilde{\Pi}_r $ベル数第二種スターリング数

発展

ここまで書いて、twelvefoldを発見しました。twelvefoldによると、重複のオプションに「各箱に最低$ 1 $個は入る」を加えて$ 12 $パターンにし、「写像12相」と呼ぶのが一般的であるようです。

参考文献

投稿日:16日前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

nayuta_ito
153
46647

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中