[答1182] 不等式を満たす整数の組

'


[答1182] 不等式を満たす整数の組


　集合Ｓ，集合Ｔを Ｓ＝｛0，1，2，3，4，5，6，7，8，9，10｝，

　Ｔ＝｛(a，b，c，d)|a∈Ｓ，b∈Ｓ，c∈Ｓ，d∈Ｓ，3a≦b＋c＋d＋10｝ とするとき、

　集合Ｔの要素の個数は？


[参考]

　例えば、３つの負でない整数の和が 10以下の場合の数は、

　○○○○○○○○○○ の間または両端から重複を許して３個を選び、

　そこに区切りを入れれば ○○○|○|○○○○|○○ のようになり、

　各区切りまでの○の個数を数えれば ３＋１＋４ になりますので、₁₁Ｈ₃ です。

　このように、３つの負でない整数の和がｎ以下の場合の数は、_n+1Ｈ₃＝(n＋1)(n＋2)(n＋3)/6 です。

　一般に、負でない整数ｒ個の和がｎ以下になる場合の数は _n+1Ｈ_r です。


[解答]

　全体集合Ｕ＝｛(a，b，c，d)|a∈Ｓ，b∈Ｓ，c∈Ｓ，d∈Ｓ｝ とすれば、

　Ｕの要素の個数は 11⁴＝14641 個で、

　Ｔの補集合｛(a，b，c，d)|(a，b，c，d)∈Ｕ，3a＞b＋c＋d＋10｝の要素の個数を求めます。

　b＋c＋d＜3a－10 、b＋c＋d≦3a－11 ですので、

　4≦a≦10 において、負でない整数３個の和が(3a－11)以下になる場合の数は

　(3a－10)(3a－9)(3a－8)/6＝(a－3)(3a－10)(3a－8)/2 で、

　1･2･4/2＋2･5･7/2＋3･8･10/2＋4･11･13/2＋5･14･16/2＋6･17･19/2＋7･20･22/2

　 ＝4＋35＋120＋286＋560＋969＋1540＝3514 、

　b≧11 のとき (b－11)＋c＋d≦3a－22 ですので、

　8≦a≦10 において、負でない整数３個の和が(3a－22)以下になる場合の数は

　(3a－21)(3a－20)(3a－19)/6＝(a－7)(3a－20)(3a－19)/2 です。

　c≧11，d≧11 のときも同様で、11以上の整数を含む場合の数は、3(a－7)(3a－20)(3a－19)/2 で、

　3･1･4･5/2＋3･2･7･8/2＋3･3･10･11/2＝30＋168＋495＝693 、

　よって、Ｔの補集合の要素の個数は 3514－693＝2821 です。

　また、Ｔの要素の数は、14641－2821＝11820 です。


[参考]

　Ｓ＝｛0，1，2，……，n｝，Ｔ＝｛(a，b，c，d)|a∈Ｓ，b∈Ｓ，c∈Ｓ，d∈Ｓ，3a≦b＋c＋d＋n｝ のとき、

　集合Ｔの要素の個数は [(59n⁴＋226n³＋329n²＋210n＋72)/72] です。

.