|
問題450
問題１：１≦ｘ１＜ｘ２＜ｘ３≦１０を満たす整数解の組は何組か。
問題２：１≦ｘ１≦ｘ２≦ｘ３≦１０を満たす整数解の組は何組か。
問題３：ｘ１＋ｘ２＋ｘ３＝１０を満たす自然数解の組は何組か。
問題４：ｘ１＋ｘ２＋ｘ３＝１０を満たす負でない整数解の組は何組か。
問題５：１≦ｘ１≦ｘ２≦ｘ３≦ｘ４≦ｘ５≦ｘ６≦６ かつ
１≦ｘ１，２≦ｘ２，３≦ｘ３，４≦ｘ４，５≦ｘ５，６≦ｘ６ を満たす整数解の組は何組か。
解答
・uchinyanさんのもの Orz〜
問題1：
1 <= x1 < x2 < x3 <= 10 の x1，x2，x3 は，1 〜 10 の異なる三つの整数を取ってきて小さい順に並べればいいので，
10C3 = (10 * 9 * 8)/(3 * 2 * 1) = 120 組。
問題2：
1 <= x1 <= x2 <= x3 <= 10 の x1，x2，x3 は，1 <= y1 = x1 < y2 = x2 + 1 < y3 = x3 + 2 <= 12 との
一対一対応を考えるといいです。
y1，y2，y3 の解の個数は問題1：と同様に 12C3 で，一対一対応なので，
x1，x2，x3 の個数も 12C3 = (12 * 11 * 10)/(3 * 2 * 1) = 220 組。
問題3：
10 個の球を三つの異なる箱に少なくとも一つずつ入るように分けることと同じです。
三つの異なる箱に分けるのは，10 個を並べておいて二つの区切りを入れる，と考えればいいです。
少なくとも一つずつ入っているようにするには，最初に一つずつ入れておけばいいです。
つまり，10 - 3 = 7 個の球を三つの異なる箱に分ければいいです。
したがって，7 個の球を二つの仕切りで分ければいいので，(7+2)C2 = 9C2 = (9 * 8)/(2 * 1) = 36 組。
問題4：
これは問題3：と同様で，10 個の球を三つの異なる箱に分けることと同じです。
しかも，今回は箱には入っていない場合を許すので，そのまま，(10+2)C2 = 12C2 = (12 * 11)/(2 * 1) = 66 組。
問題5；
これは少し複雑です。次のように考えてみます。
x1 から順番に x6 までを取っていくとします。
今，x1 <= x2 <= ... <= xn = k. 1 <= x1, 2 <= x2, ..., n <= xn の場合の数を a(n,k) とします。
ただし，n <= k です。また，最終的に求めるのは，a(6,6) です。
すると，a(n,k) は，x_(n-1) = k, k-1, k-2, ..., n-1 までに対する
a(n-1,k), a(n-1,k-1), a(n-1,k-2), ..., a(n-1,n-1) を加えたものになります。
ところが，xn = k-1 を考えると，a(n-1,k-1) + a(n-1,k-2) + ... + a(n-1,n-1) = a(n,k-1) なので，
結局，a(n,k) = a(n-1,k) + a(n,k-1) です。
ただし，k = n では a(n,n-1) は意味がありませんが，形式的に，
a(n-1,k-1) + a(n-1,k-2) + ... + a(n-1,n-1) のことと解釈することにします。
これを踏まえて，横に x1 〜 x6 を取り，縦にそれまでの取りえる場合の数を書いていきます。
まず，簡単のために x1, x2 で考えてみると
x1 は，1 の場合が 1 通り，2 の場合が 1 通り。
x2 は，x1 = 1 の場合の x2 = 2 と x1 = 2 の場合の x2 = 2 で 2 通り。
これを，
..x1.x2
2:1->2->2
1:1->1
と書きます。ここで，2: と x2 とが交差するところで 2 となっているのは，
x2 = 2 の場合(x2 と 2: の交点，a(2,2))が，
x1 = 1 の場合(x2 と 1: の交点，a(2,1)，これは a(1,1) と同じ)と x1 = 2 の場合(x1 と 2: の交点，a(1,2))
の両方の和であることを示しています。
また，2: の一番右端の 2 は，最終的に求める値 a(2,2) を再度示しています。(形式的には，a(3,2))
同様に，x1，x2，x3 では，
..x1.x2.x3
3:1->3->5->5
2:1->2->2
1:1->1
これを x1 〜 x6 まで続けると，
..x1.x2.x3..x4..x5..x6
6:1->6->20->48->90->132->132
5:1->5->14->28->42->42
4:1->4->9-->14->14
3:1->3->5-->5
2:1->2->2
1:1->1
そこで，132 組になります。
(考察)
問題1：〜問題4：は，省略しますが，一般化は容易です。
問題5：も，これは，平面上の n * n の格子を対角線をまたがずに行く場合の数と同じなので，カタラン数ですね。
これも一般式はよく知られています。例えば，http://aozoragakuen.sakura.ne.jp/taiwa/node85.html など。
なお，これは問題の趣旨ではないでしょうが，プログラムを組んでも簡単にできます。
・わたしの
問題１：１≦ｘ１＜ｘ２＜ｘ３≦１０を満たす整数解の組は何組か。
1-2-3〜10・・・8個
1-3-4〜10・・・7個
・
・
・
1-9-10・・・1個
2-3-4〜10・・・7個
・
・
・
で、結局、、、
Σ(8〜1)+Σ(7〜1)+・・・+Σ(1)=36+28+21+15+10+6+3+1=120
問題２：１≦ｘ１≦ｘ２≦ｘ３≦１０を満たす整数解の組は何組か。
1-1-1￣10 ・・・10
1-2-2￣10 ・・・9
1-10-10 ・・・1
2-2-2￣10 ・・・9
・
・
・
Σ(1￣10)+Σ(1￣9)+・・・+1=55+45++120=220
問題３：ｘ１＋ｘ２＋ｘ３＝１０を満たす自然数解の組は何組か。
(x1-1)+(x2-1)+(x3-1)=7
3H7=9C7=9*8/2=36
問題４：ｘ１＋ｘ２＋ｘ３＝１０を満たす負でない整数解の組は何組か。
3H10=12C10=12*11/2=66
問題5は撃沈 ^^;
たの方の解答は次に ^^v
画像：シーサー
先輩のうちの玄関にちょこんと招き（魔除け）猫のように鎮座されてました。^^
|
コメント（8）
