場合の数: x+y+z=n (x,y,zに上限有り) と増加列

今回は初見だとやや難しい (?) と思われる場合の数の問題を 2テーマ扱います.
文字は整数とします.


[1]
bai1.jpg
の下,
bai2.jpg
を満たす整数の組 (x,y,z) の個数を求めよ.

x,y,z に上限が無ければ,n個の 〇 と 2本の | の並べ方を考えて,n+2C2 で終わりです.

上限が有る場合は次の様に考えて行きます.

0≤x≤a の右側,x≤a の x を右辺へ移項して,0≤a-x.
x を 0 ~ a と動かすと,0≤a-x≤a.
y,z に付いても同様で,0≤b-y≤b, 0≤c-z≤c.
(何だかこの置き換え方は積分等にも良く出て来ますね.)


bai3.jpg

x' の上限を消せた理由に付いて,
 a-{(a+b+c)-n} = n-(b+c) ≥ 0 (∵ 始めの n の条件 ①)
y', z' に付いても同様.

依って,答えは,(a+b+c-n) 個の 〇 と 2本の | の並べ方を考えて,
a+b+c-n+2C2 ですね.
始め,x,y,z の内,1つだけを上限に目1杯上げて右辺に達せられ無かったのを変数変換で,x',y',z' にする事で右辺を越えられる様に成りました.

H1(1989)東大理系数学第6問(難易度D)を聖文新社の50ヵ年ではこの考え方で手早く解答しているのですが,いきなり k-a,・・・ 等が出て来るので予備知識が無い人は面食らってしまった事でしょう (個人的にちょっと不親切?).


[2] 増加列
  0≤a1≤a2≤・・・≤am≤n
⇔ 1≤a1+1<a2+2<・・・<am+m≤n+m
⇔ 1≤a1'<a2'<・・・<am'≤n+m
1 ~ (n+m) の数字から m 個 を選ぶ選び方を考えて,n+mCm.

同様に考えて,
  k≤al≤・・・≤am≤n
は,(n-k)+(m-l+1)Cm-l+1.



整数 m, n に付いて,
 m<n ⇔ m+1≤n ⇔ m≤n-1.
これは物凄く重要な不等式だと思います.等号付きと付か無いのとどちらが都合が良いかは場合に依って異なる.
個数の処理と確率に限らず,整数問題や数列でも利用する場合が有る様です.

Post a comment

Private comment

プロフィール

A6033x

Author:A6033x
数検1級取得しました.
個人的な連絡は,hermitvseinsiedler@_@gmail.com
まで(@_@は@に置換すること).
あまり見ないかも知れないのでその場合は twitter の方へ.
twitter:https://twitter.com/A603zw
そもそもネット接続自体減らして行く事になりますが...

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QR