「数え上げ理論」というブルーバックスの真ん中あたりを開いたら、9つのものを袋に分ける分け方は何通りあるか？という問題が載っていました。
本を真ん中から読むというのはよくやります。
推理小説の最初と最後だけ読むというのもたまにやります。
9つのものを1つの袋に入れる入れ方は1つ。9つの袋に入れる入れ方は1つ。というように数えていきます。9つぐらいなら数えられないことはないと思う。
1. 9 2. 8 1 3. 7 2 4. 7 1 1 5. 6 3 6. 6 2 1 7. 6 1 1 1 8. 5 4 9. 5 3 1 10. 5 2 2 11. 5 2 1 1 12. 5 1 1 1 1 13. 4 4 1 14. 4 3 2 15. 4 3 1 1 16. 4 2 2 1 17. 4 2 1 1 1 18. 4 1 1 1 1 1 19. 3 3 3 20. 3 3 2 1 21. 3 3 1 1 1 22. 3 2 1 1 1 1 23. 3 1 1 1 1 1 1 24. 2 1 1 1 1 1 1 1 25. 1 1 1 1 1 1 1 1 1
むむう、数え漏れもありそうだし、二重数えもありそうですね。
まずい。ちゃんと考えましょう。
分け方の数をp(m)とします。今回の場合m=9です。m個を分ける袋の数の方をnとして、最初に考えたようにn=1ならば9個のものを1個の袋に入れる入れ方ですので1通りというのをp(m,n)でm=9、n=1ならばp(9,1)=1というように考えます。すると、p(m)=p(m,1)+p(m,2)+...+p(m,m)になります。pは順列permutationではなくて今回の場合区分けpartition。
NB. p(9, 1)=1 (9) NB. p(9, 2)=4 (8 1) (7 2) (6 3) (5 4) NB. p(9, 3)=7 (7 1 1) (6 2 1) (5 3 1) (5 2 2) (4 4 1) (4 3 2) (3 3 3) NB. p(9, 4)=6 (6 1 1 1) (5 2 1 1) (4 3 1 1) (4 2 2 1) (3 3 2 1) (3 2 2 2) NB. p(9, 5)=5 (5 1 1 1 1) (4 2 1 1 1) (3 3 1 1 1) (3 2 2 1 1) (2 2 2 2 1) NB. p(9, 6)=3 (4 1 1 1 1 1) (3 2 1 1 1 1) (2 2 2 1 1 1) NB. p(9, 7)=2 (3 1 1 1 1 1 1) (2 2 1 1 1 1 1) NB. p(9, 8)=1 (2 1 1 1 1 1 1 1) NB. p(9, 9)=1 (1 1 1 1 1 1 1 1 1) +/ 1 4 7 6 5 3 2 1 1 30
れれれ。30個もある。しかしこれでも自信ないなぁ。なんとかJ言語で数え上げられないかしら。
再帰も使いたい。
少し実験
i.9 0 1 2 3 4 5 6 7 8 9#1 1 1 1 1 1 1 1 1 1 +/9#1 9 +/\9#1 1 2 3 4 5 6 7 8 9 +\9#1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
なんかできそうですが、いまは出来ない。思いついたら追記します。
追記：まだ出来ませんが、すこし進歩。
i.3 0 1 2 A. 1 2 0 NB.anagram index 3 3 A. i.3 1 2 0 (! A. i.) 3
| index error |
| (!A.i.)3 |
すべての順列はできたので、partitionとして数えればよい。
どう数えるか。今回の場合、(3), (2, 1), (1, 1, 1)の3種類という意味の3が得られればよい。
ちなみに数えただけですが、
p(1)=1、p(2)=2、p(3)=3, p(4)=5、p(6)=11、p(7)=15、p(8)=22、p(9)=30
と思う。
