YLL討論網

設f(m,n)=((m+n-2)(m+n-1))/2+m
證明:f是從N*N到N的1對1映成函數

f(m,n) = (m+n-2)(m+n-1)/2  + m顯然為整數值.

1-1:

假設有兩組不一樣的(m1,n1)，(m2,n2)使得

(m1+n1-2)(m1+n1-1)/2 + m1 = (m2+n2-2)(m2+n2-1)/2 + m2

=> (m1+n1-2)(m1+n1-1) - (m2+n2-2)(m2+n2-1) = 2(m2 - m1)

=> [ (m1+n1)^2 - 3(m1+n1) + 2 ] - [ (m2+n2)^2 - 3(m2+n2) + 2 ] = 2(m2-m1)

=> (m1+n1+m2+n2)(m1+n1-m2-n2) - 3(m1+n1-m2-n2) = 2(m2-m1)

=> (m1+n1+m2+n2-3)(m1+n1-m2-n2) = 2(m2-m1)......(*)

不失一般性可設m2 > m1使右式為正，則左式也為正，且 m1+n1+m2+n2-3 < 2(m2-m1)

=> m2 > 3m1+n1+n2-3

且m1+n1-m2-n2 > 0

=> 0 < m1+n1-(3m1+n1+n2-3)-n2 = -2m1 + 3，此式只對m1 = 1成立，m1在

2以上時皆矛盾.所以由對稱性知只要m1或m2之中有一個比1大就不合.故只有m1 = m2.

再由(*)知左式為0，由於m1+m2+n1+n2-3 > 0，所以m1+m2-n1-n2 = 0 => n1 = n2.

onto:

解(m+n-2)(m+n-1)/2 + m = k，k為正整數.

可變成 C(m+n-1,2) + m = k，其中C代表組合符號.

case1. 當k = C(N,2)，N為某大於1的整數時，取m+n-1 = N-1，

             則m = C(N,2)-C(N-1,2) = N-1，n = 1.

case2.當k = C(N,2) + M，其中 0 < M < N，則取m = M，m+n = N，n = N-M.

         且任意不在case1的K必可如此表示.