空箱あり・なしの分割数の定義
空箱あり・なしの分割数の定義
空箱あり・なしの分割数を次で定義します。
function)という。
これは箱に\(n\)個入れることを自然数の\(n\)と対応させれば、ある自然数(0以上の整数)\(n\)を\(k\)個の0以上の整数の和で表す組み合わせの個数と同じである。
ただし、\(p\left(0,0\right)=1\)として、\(m<0\)のとき、\(p\left(m,k\right)=0,p\left(n,m\right)=0\)とする。
また、区別の出来ない\(n\)個の玉を箱に分ける方法の数を\(p\left(n\right)\)で表し、
\begin{align*} p\left(n\right) & =p\left(n,n\right) \end{align*} となる。
分割数\(p\left(n\right)\)はある自然数を自然数に分割する組み合わせの個数と同じである。
\[ q\left(n,k\right)=p\left(n-k,k\right) \] となる。
これは箱に\(n\)個入れることを自然数の\(n\)と対応させれば、ある自然数(0以上の整数)\(n\)を\(k\)個の自然数の和で表す組み合わせの個数と同じである。
また空箱ありの定義より、\(q\left(0,0\right)=p\left(0,0\right)=1\)となり、\(m<0\)のとき、\(q\left(m+k,k\right)=p\left(m,k\right)=0,q\left(n+m,m\right)=p\left(n,m\right)=0\)となる。
空箱あり・なしの分割数を次で定義します。
(1)空箱あり
区別の出来ない\(n\)個の玉を区別の出来ない\(k\)個の箱に空箱ありで分ける方法の数を\(p\left(n,k\right)\)で表し分割数(partitionfunction)という。
これは箱に\(n\)個入れることを自然数の\(n\)と対応させれば、ある自然数(0以上の整数)\(n\)を\(k\)個の0以上の整数の和で表す組み合わせの個数と同じである。
ただし、\(p\left(0,0\right)=1\)として、\(m<0\)のとき、\(p\left(m,k\right)=0,p\left(n,m\right)=0\)とする。
また、区別の出来ない\(n\)個の玉を箱に分ける方法の数を\(p\left(n\right)\)で表し、
\begin{align*} p\left(n\right) & =p\left(n,n\right) \end{align*} となる。
分割数\(p\left(n\right)\)はある自然数を自然数に分割する組み合わせの個数と同じである。
(2)空箱なし
区別の出来ない\(n\)個の玉を区別の出来ない\(k\)個の箱に空箱なしで分ける方法の数\(q\left(n,k\right)\)は分割数\(p\left(n,k\right)\)を使って\[ q\left(n,k\right)=p\left(n-k,k\right) \] となる。
これは箱に\(n\)個入れることを自然数の\(n\)と対応させれば、ある自然数(0以上の整数)\(n\)を\(k\)個の自然数の和で表す組み合わせの個数と同じである。
また空箱ありの定義より、\(q\left(0,0\right)=p\left(0,0\right)=1\)となり、\(m<0\)のとき、\(q\left(m+k,k\right)=p\left(m,k\right)=0,q\left(n+m,m\right)=p\left(n,m\right)=0\)となる。
-
\(p\left(n,k\right)\)と\(q\left(n,k\right)\)は再帰的に次のように表される。\[ p\left(n,k\right)=\begin{cases} 1 & n=0\\ \delta_{n,0} & k=0\\ 0 & n<0\lor k<0\\ p\left(n,n\right) & 0<n<k\\ p\left(n,k-1\right)+p\left(n-k,k\right) & 0<k\leq n \end{cases} \] \begin{align*} q\left(n,k\right) & =p\left(n-k,k\right)\\ & =\begin{cases} 1 & n=k\\ \delta_{n,0} & k=0\\ 0 & n<k\lor k<0\\ q\left(2\left(n-k\right),n-k\right) & k<n<2k\\ q\left(n-1,k-1\right)+q\left(n-k,k\right) & 0\leq2k\leq n \end{cases} \end{align*}
-
空箱ありの分割数\(p\left(n,k\right)\)一覧
\[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30\\ \hline 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ \hline 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ \hline 2 & 0 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2\\ \hline 3 & 0 & 1 & 2 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3\\ \hline 4 & 0 & 1 & 3 & 4 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5\\ \hline 5 & 0 & 1 & 3 & 5 & 6 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7\\ \hline 6 & 0 & 1 & 4 & 7 & 9 & 10 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11\\ \hline 7 & 0 & 1 & 4 & 8 & 11 & 13 & 14 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15\\ \hline 8 & 0 & 1 & 5 & 10 & 15 & 18 & 20 & 21 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22\\ \hline 9 & 0 & 1 & 5 & 12 & 18 & 23 & 26 & 28 & 29 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30\\ \hline 10 & 0 & 1 & 6 & 14 & 23 & 30 & 35 & 38 & 40 & 41 & 42 & 42 & 42 & 42 & 42 & 42 & 42 & 42 & 42 & 42 & 42 & 42 & 42 & 42 & 42 & 42 & 42 & 42 & 42 & 42 & 42\\ \hline 11 & 0 & 1 & 6 & 16 & 27 & 37 & 44 & 49 & 52 & 54 & 55 & 56 & 56 & 56 & 56 & 56 & 56 & 56 & 56 & 56 & 56 & 56 & 56 & 56 & 56 & 56 & 56 & 56 & 56 & 56 & 56\\ \hline 12 & 0 & 1 & 7 & 19 & 34 & 47 & 58 & 65 & 70 & 73 & 75 & 76 & 77 & 77 & 77 & 77 & 77 & 77 & 77 & 77 & 77 & 77 & 77 & 77 & 77 & 77 & 77 & 77 & 77 & 77 & 77\\ \hline 13 & 0 & 1 & 7 & 21 & 39 & 57 & 71 & 82 & 89 & 94 & 97 & 99 & 100 & 101 & 101 & 101 & 101 & 101 & 101 & 101 & 101 & 101 & 101 & 101 & 101 & 101 & 101 & 101 & 101 & 101 & 101\\ \hline 14 & 0 & 1 & 8 & 24 & 47 & 70 & 90 & 105 & 116 & 123 & 128 & 131 & 133 & 134 & 135 & 135 & 135 & 135 & 135 & 135 & 135 & 135 & 135 & 135 & 135 & 135 & 135 & 135 & 135 & 135 & 135\\ \hline 15 & 0 & 1 & 8 & 27 & 54 & 84 & 110 & 131 & 146 & 157 & 164 & 169 & 172 & 174 & 175 & 176 & 176 & 176 & 176 & 176 & 176 & 176 & 176 & 176 & 176 & 176 & 176 & 176 & 176 & 176 & 176\\ \hline 16 & 0 & 1 & 9 & 30 & 64 & 101 & 136 & 164 & 186 & 201 & 212 & 219 & 224 & 227 & 229 & 230 & 231 & 231 & 231 & 231 & 231 & 231 & 231 & 231 & 231 & 231 & 231 & 231 & 231 & 231 & 231\\ \hline 17 & 0 & 1 & 9 & 33 & 72 & 119 & 163 & 201 & 230 & 252 & 267 & 278 & 285 & 290 & 293 & 295 & 296 & 297 & 297 & 297 & 297 & 297 & 297 & 297 & 297 & 297 & 297 & 297 & 297 & 297 & 297\\ \hline 18 & 0 & 1 & 10 & 37 & 84 & 141 & 199 & 248 & 288 & 318 & 340 & 355 & 366 & 373 & 378 & 381 & 383 & 384 & 385 & 385 & 385 & 385 & 385 & 385 & 385 & 385 & 385 & 385 & 385 & 385 & 385\\ \hline 19 & 0 & 1 & 10 & 40 & 94 & 164 & 235 & 300 & 352 & 393 & 423 & 445 & 460 & 471 & 478 & 483 & 486 & 488 & 489 & 490 & 490 & 490 & 490 & 490 & 490 & 490 & 490 & 490 & 490 & 490 & 490\\ \hline 20 & 0 & 1 & 11 & 44 & 108 & 192 & 282 & 364 & 434 & 488 & 530 & 560 & 582 & 597 & 608 & 615 & 620 & 623 & 625 & 626 & 627 & 627 & 627 & 627 & 627 & 627 & 627 & 627 & 627 & 627 & 627\\ \hline 21 & 0 & 1 & 11 & 48 & 120 & 221 & 331 & 436 & 525 & 598 & 653 & 695 & 725 & 747 & 762 & 773 & 780 & 785 & 788 & 790 & 791 & 792 & 792 & 792 & 792 & 792 & 792 & 792 & 792 & 792 & 792\\ \hline 22 & 0 & 1 & 12 & 52 & 136 & 255 & 391 & 522 & 638 & 732 & 807 & 863 & 905 & 935 & 957 & 972 & 983 & 990 & 995 & 998 & 1,000 & 1,001 & 1,002 & 1,002 & 1,002 & 1,002 & 1,002 & 1,002 & 1,002 & 1,002 & 1,002\\ \hline 23 & 0 & 1 & 12 & 56 & 150 & 291 & 454 & 618 & 764 & 887 & 984 & 1,060 & 1,116 & 1,158 & 1,188 & 1,210 & 1,225 & 1,236 & 1,243 & 1,248 & 1,251 & 1,253 & 1,254 & 1,255 & 1,255 & 1,255 & 1,255 & 1,255 & 1,255 & 1,255 & 1,255\\ \hline 24 & 0 & 1 & 13 & 61 & 169 & 333 & 532 & 733 & 919 & 1,076 & 1,204 & 1,303 & 1,380 & 1,436 & 1,478 & 1,508 & 1,530 & 1,545 & 1,556 & 1,563 & 1,568 & 1,571 & 1,573 & 1,574 & 1,575 & 1,575 & 1,575 & 1,575 & 1,575 & 1,575 & 1,575\\ \hline 25 & 0 & 1 & 13 & 65 & 185 & 377 & 612 & 860 & 1,090 & 1,291 & 1,455 & 1,586 & 1,686 & 1,763 & 1,819 & 1,861 & 1,891 & 1,913 & 1,928 & 1,939 & 1,946 & 1,951 & 1,954 & 1,956 & 1,957 & 1,958 & 1,958 & 1,958 & 1,958 & 1,958 & 1,958\\ \hline 26 & 0 & 1 & 14 & 70 & 206 & 427 & 709 & 1,009 & 1,297 & 1,549 & 1,761 & 1,930 & 2,063 & 2,164 & 2,241 & 2,297 & 2,339 & 2,369 & 2,391 & 2,406 & 2,417 & 2,424 & 2,429 & 2,432 & 2,434 & 2,435 & 2,436 & 2,436 & 2,436 & 2,436 & 2,436\\ \hline 27 & 0 & 1 & 14 & 75 & 225 & 480 & 811 & 1,175 & 1,527 & 1,845 & 2,112 & 2,331 & 2,503 & 2,637 & 2,738 & 2,815 & 2,871 & 2,913 & 2,943 & 2,965 & 2,980 & 2,991 & 2,998 & 3,003 & 3,006 & 3,008 & 3,009 & 3,010 & 3,010 & 3,010 & 3,010\\ \hline 28 & 0 & 1 & 15 & 80 & 249 & 540 & 931 & 1,367 & 1,801 & 2,194 & 2,534 & 2,812 & 3,036 & 3,210 & 3,345 & 3,446 & 3,523 & 3,579 & 3,621 & 3,651 & 3,673 & 3,688 & 3,699 & 3,706 & 3,711 & 3,714 & 3,716 & 3,717 & 3,718 & 3,718 & 3,718\\ \hline 29 & 0 & 1 & 15 & 85 & 270 & 603 & 1,057 & 1,579 & 2,104 & 2,592 & 3,015 & 3,370 & 3,655 & 3,882 & 4,057 & 4,192 & 4,293 & 4,370 & 4,426 & 4,468 & 4,498 & 4,520 & 4,535 & 4,546 & 4,553 & 4,558 & 4,561 & 4,563 & 4,564 & 4,565 & 4,565\\ \hline 30 & 0 & 1 & 16 & 91 & 297 & 674 & 1,206 & 1,824 & 2,462 & 3,060 & 3,590 & 4,035 & 4,401 & 4,691 & 4,920 & 5,096 & 5,231 & 5,332 & 5,409 & 5,465 & 5,507 & 5,537 & 5,559 & 5,574 & 5,585 & 5,592 & 5,597 & 5,600 & 5,602 & 5,603 & 5,604 \\\hline \end{array} \]
空箱なしの分割数\(q\left(n,k\right)\)一覧
\[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30\\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 2 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 3 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 4 & 0 & 1 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 5 & 0 & 1 & 2 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 6 & 0 & 1 & 3 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 7 & 0 & 1 & 3 & 4 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 8 & 0 & 1 & 4 & 5 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 9 & 0 & 1 & 4 & 7 & 6 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 10 & 0 & 1 & 5 & 8 & 9 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 11 & 0 & 1 & 5 & 10 & 11 & 10 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 12 & 0 & 1 & 6 & 12 & 15 & 13 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 13 & 0 & 1 & 6 & 14 & 18 & 18 & 14 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 14 & 0 & 1 & 7 & 16 & 23 & 23 & 20 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 15 & 0 & 1 & 7 & 19 & 27 & 30 & 26 & 21 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 16 & 0 & 1 & 8 & 21 & 34 & 37 & 35 & 28 & 22 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 17 & 0 & 1 & 8 & 24 & 39 & 47 & 44 & 38 & 29 & 22 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 18 & 0 & 1 & 9 & 27 & 47 & 57 & 58 & 49 & 40 & 30 & 22 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 19 & 0 & 1 & 9 & 30 & 54 & 70 & 71 & 65 & 52 & 41 & 30 & 22 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 20 & 0 & 1 & 10 & 33 & 64 & 84 & 90 & 82 & 70 & 54 & 42 & 30 & 22 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 21 & 0 & 1 & 10 & 37 & 72 & 101 & 110 & 105 & 89 & 73 & 55 & 42 & 30 & 22 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 22 & 0 & 1 & 11 & 40 & 84 & 119 & 136 & 131 & 116 & 94 & 75 & 56 & 42 & 30 & 22 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 23 & 0 & 1 & 11 & 44 & 94 & 141 & 163 & 164 & 146 & 123 & 97 & 76 & 56 & 42 & 30 & 22 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 24 & 0 & 1 & 12 & 48 & 108 & 164 & 199 & 201 & 186 & 157 & 128 & 99 & 77 & 56 & 42 & 30 & 22 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 25 & 0 & 1 & 12 & 52 & 120 & 192 & 235 & 248 & 230 & 201 & 164 & 131 & 100 & 77 & 56 & 42 & 30 & 22 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\ \hline 26 & 0 & 1 & 13 & 56 & 136 & 221 & 282 & 300 & 288 & 252 & 212 & 169 & 133 & 101 & 77 & 56 & 42 & 30 & 22 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0\\ \hline 27 & 0 & 1 & 13 & 61 & 150 & 255 & 331 & 364 & 352 & 318 & 267 & 219 & 172 & 134 & 101 & 77 & 56 & 42 & 30 & 22 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0 & 0\\ \hline 28 & 0 & 1 & 14 & 65 & 169 & 291 & 391 & 436 & 434 & 393 & 340 & 278 & 224 & 174 & 135 & 101 & 77 & 56 & 42 & 30 & 22 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0 & 0\\ \hline 29 & 0 & 1 & 14 & 70 & 185 & 333 & 454 & 522 & 525 & 488 & 423 & 355 & 285 & 227 & 175 & 135 & 101 & 77 & 56 & 42 & 30 & 22 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & 0\\ \hline 30 & 0 & 1 & 15 & 75 & 206 & 377 & 532 & 618 & 638 & 598 & 530 & 445 & 366 & 290 & 229 & 176 & 135 & 101 & 77 & 56 & 42 & 30 & 22 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 \\\hline \end{array} \]
(2)
\(p\left(n,k\right)\)は空箱を作らないときは\(q\left(n,k\right)\)通りで空箱を作るときは\(p\left(n,k-1\right)\)通りなので、\[ p\left(n,k\right)=q\left(n,k\right)+p\left(n,k-1\right) \] となり、漸化式より、
\begin{align*} q\left(n,k\right) & =p\left(n,k\right)-p\left(n,k-1\right)\\ & =p\left(n-k,k\right) \end{align*} となる。
(2)-2
空箱なしにする場合の数は最初に\(k\)個の全ての箱に1つずついれてそこから残った\(n-k\)の玉を\(k\)個に空箱ありで入れる場合の数と等しいので、\(q\left(n,k\right)=p\left(n-k,k\right)\)となる。-
箱が\(k\)個で空箱ありの場合の数は、空箱なしで箱を\(0,1,2,\cdots,k\)と全ての和をとったものと等しいので\begin{align*} p\left(n,k\right) & =\sum_{j=0}^{k}q\left(n,j\right) \end{align*} の関係がある。
これより、
\begin{align*} p\left(n,k\right) & =\sum_{j=0}^{k}q\left(n,j\right)\\ & =q\left(n,k\right)+\sum_{j=0}^{k-1}q\left(n,j\right)\\ & =q\left(n,k\right)+p\left(n,k-1\right) \end{align*} が導出できる。
ページ情報
| タイトル | 空箱あり・なしの分割数の定義 |
| URL | https://www.nomuramath.com/s9rjloy3/ |
| SNSボタン |
異分割・奇分割とオイラーの分割恒等式
\[
\sum_{k=0}^{\infty}P_{d}\left(k\right)z^{k}=\prod_{k=1}^{\infty}\left(1+z^{k}\right)
\]
分割数の漸化式
\[
p\left(n,k\right)=p\left(n,k-1\right)+p\left(n-k,k\right)
\]
分割数の定義と母関数
\[
\sum_{k=0}^{\infty}P\left(k\right)z^{k}=\prod_{k=1}^{\infty}\frac{1}{1-z^{k}}
\]