組合せ論についての証明

質問

「正整数nが存在して, t>nなる正整数tと, n以下の非負整数kに対して
{(t-n)*(nCk)*(tCn)} / (t-k)
が整数値になる」
ことを示したいのですが, どうしたらいいのか教えてください.
実は, 上式の組み合わせを使わないで書くと, tが負整数のときも, 整数となります.
(本当はこちらも証明したいのですが…)

また, 上のものを別の言い方で書くと
「正整数nが存在して, t>nなる正整数tと, n以下の非負整数kに対して
t-n, nCk, tCnの中にt-kの倍数となるものがある」
です.

回答No.1

nag0720 · ベストアンサー

(nCk)*(tCn)=(tCk)*((t-k)C(t-n))
(t-n)*((t-k)C(t-n))/(t-k)=(t-k-1)C(t-n-1)
なので、{(t-n)*(nCk)*(tCn)}/(t-k)は整数値になる。

なお、
「{(t-n)*(nCk)*(tCn)}/(t-k)　が整数値になる」
と
「t-n, nCk, tCnの中にt-kの倍数となるものがある」
とでは意味が違う。
t=5,n=3,k=1のとき、t-n=2、nCk=3、tCn=10だがこの中に4の倍数はない。

お礼

ありがとうございました. また, nが負整数のときは自分でやってみます.

回答No.3

ramayana

ANo.2の後半の例は間違いでした。すみません。

回答No.2

ramayana

上の命題については、n=1と置けばよいようです。

n=1なら、k = 0 or 1 で、

　{(t-n)*(nCk)*(tCn)} = (t-1) *1*t

だから、これは、kが0でも1でも t-k で割り切れます。

下の命題は、上の命題と同値ではありませんし、正しくないと思います。例えば、t = n+1、k = 0 とすれば、どんな n を持ってきても

　t-n = 1
　nCk = 1
　tCn = t+1

となり、どれも、t=t-kで割り切れません。

お礼

解決しました. ありがとうございます.