Chủ đề này có 10 trả lời

[hxthanh]

Bằng phương pháp đếm theo hai cách:

CMR: $\sum_{k=0}^n {k\choose a}{n-k\choose b}={n+1\choose a+b+1}$

 

Mở rộng:

 

$\sum_{k_1+k_2+...+k_m=n}{k_1\choose a_1}{k_2\choose a_2}...{k_m\choose a_m}={n+m-1\choose a_1+a_2+...+a_m+m-1}$

[hxthanh]

Mở rộng:

 

$\sum_{k_1+k_2+...+k_m=n}{k_1\choose a_1}{k_2\choose a_2}...{k_m\choose a_m}={n+m-1\choose a_1+a_2+...+a_m+m-1}$

Thử mang công thức tầm thường này để tính một vài tổng cơ bản xem nào!

 

$\sum_{k=1}^n k=\sum_{k+j=n} {k\choose 1}{j\choose 0}={n+2-1\choose 1+0+2-1}=\dfrac{n(n+1)}{2}\qquad (*)$

 

$\sum_{k=1}^n \left(\dfrac{1}{2}k^2-\dfrac{1}{2}k\right)=\sum_{k=1}^n {k\choose 2}=\sum_{k+j=n}{k\choose 2}{j\choose 0}=\sum_{k+j=n}{k\choose 1}{j\choose 1}$ $=\sum_{k=1}^n k(n-k)={n+1\choose 3}$

 

Suy ra:

 

$n\sum_{k=1}^n k^2-n\sum_{k=1}^n k=2n{n+1\choose 3}\quad$ (Suy từ vế đầu với vế cuối)

$-\sum_{k=1}^n k^2+n\sum_{k=1}^n k={n+1\choose 3}\quad$ (Suy từ hai vế đẳng thức cuối)

 

Cộng lại thì được $(n-1)\sum_{k=1}^n k^2=(2n+1){n+1\choose 3}$

Hay $\sum_{k=1}^n k^2=\dfrac{n(n+1)(2n+1)}{6}\quad $ (Hoàn toàn không sử dụng giá trị của $(*)$)

 

Thậm chí nếu nhân đẳng thức phía dưới với $n$ rồi cộng vế ta có:

$(n^2-n)\sum_{k=1}^n k=3n{n+1\choose 3}$

Hay $\sum_{k=1}^n k=\dfrac{n(n+1)}{2}$

 

v.v...

Bây giờ các bạn hãy tìm cách chứng minh công thức mà ta đã sử dụng nhé!

[chanhquocnghiem]

Bằng phương pháp đếm theo hai cách:

CMR: $\sum_{k=0}^n {k\choose a}{n-k\choose b}={n+1\choose a+b+1}$

 

Mở rộng:

 

$\sum_{k_1+k_2+...+k_m=n}{k_1\choose a_1}{k_2\choose a_2}...{k_m\choose a_m}={n+m-1\choose a_1+a_2+...+a_m+m-1}$

Ta chỉ cần chứng minh công thức mở rộng.

Giả sử cần chọn ra $p$ người trong số $q$ người.

Đếm theo cách 1 :

- Xếp $q$ người thành 1 hàng ngang.

- Chọn m-1 người ($m$ là số nguyên dương cố định chọn trước) làm "vách ngăn" ($k_{1}$ người đứng trước "vách ngăn" thứ nhất (gọi là nhóm $1$), $k_{2}$ người đứng giữa "vách" thứ nhất và "vách" thứ hai (nhóm $2$), ... , $k_{m}$ người đứng sau "vách ngăn" cuối cùng (nhóm $m$))

   Như vậy $k_1+k_2+...+k_m+m-1=q$ (1)

  $k_1,k_2,...,k_m$ là những số không âm biến đổi thỏa mãn (1)

- Chọn tất cả các "vách ngăn" và chọn thêm $a_1$ người từ nhóm $1$; $a_2$ người từ nhóm $2$; ... ; $a_m$ người từ nhóm $m$ sao cho $a_1+a_2+...+a_m+m-1=p$ (2)

  $a_1,a_2,...,a_m$ là những số nguyên dương được chọn cố định từ đầu và thỏa mãn (2)

 

Đặt $k_1+k_2+...+k_m=q-m+1=n$ (là số cố định)

$\Rightarrow$ số cách chọn $p$ người từ $q$ người (đếm theo cách 1) là :

$\sum _{k_1+k_2+...+k_m=n}\left ( ^{k_1}_{a_1} \right )\left ( ^{k_2}_{a_2} \right )...\left ( ^{k_m}_{a_m} \right )$

(Thực ra trường hợp trong bộ $(k_1,k_2,...,k_m)$ có ít nhất 1 số $k_i=0$ hoặc $k_i< a_i$ thì có $0$ cách tương ứng, nhưng vẫn cho $0\leqslant k_i\leqslant n$ cho có tính tổng quát.

Chỉ khi tất cả các số trong bộ $(k_1,k_2,...,k_m)$ đều khác $0$ mới có thể có cách chọn tương ứng (do đó m-1 "vách ngăn" là phân biệt)

 

Đếm theo cách 2 :

Số cách chọn $p$ người từ $q$ người là :

$\left ( ^{q}_{p} \right )=\left ( ^{n+m-1}_{a_1+a_2+...+a_m+m-1} \right )$

 

So sánh kết quả 2 cách đếm suy ra ĐPCM.

Bài viết đã được chỉnh sửa nội dung bởi chanhquocnghiem: 06-06-2015 - 21:20

[Karl Heinrich Marx]

Bằng phương pháp đếm theo hai cách:

CMR: $\sum_{k=0}^n {k\choose a}{n-k\choose b}={n+1\choose a+b+1}$

 

Mở rộng:

 

$\sum_{k_1+k_2+...+k_m=n}{k_1\choose a_1}{k_2\choose a_2}...{k_m\choose a_m}={n+m-1\choose a_1+a_2+...+a_m+m-1}$

Em thấy khá thắc mắc là nếu ta nói số cách chọn $a+b$ bạn trong $n$ bạn là số bằng số cách chọn $a$ bạn từ $k$ bạn đầu tiên và $b$ bạn từ $n-k$ bạn còn lại thì sai cái gì nhỉ? Như vậy thành ra $\sum_{k=0}^n {k\choose a}{n-k\choose b}={n\choose a+b}$?

Thật sự xem những ứng dụng thầy Thanh post ở trên khá hay, một điều thú vị là các số $a_1,a_2,..,a_m$ có thể thay đổi một cách tùy ý miễn đảm bảo giữ nguyên tổng của chúng là được.

Mình có một vài ý thế này:

Nếu thêm một biến $k_{m+1}$ viết lại thế này:

$\sum_{k_1+k_2+...+k_m+k_{m+1}=n}{k_1\choose a_1}{k_2\choose a_2}...{k_m\choose a_m}{k_{m+1}\choose 0}={n+m\choose a_1+a_2+...+a_m+m}$

giờ lược biến $k_{m+1}$ này đi thì ta viết lại thế này:

$\sum_{k_1+k_2+...+k_m \le n}{k_1\choose a_1}{k_2\choose a_2}...{k_m\choose a_m}={n+m\choose a_1+a_2+...+a_m+m}$

Bây giờ cho $m=2,a_1=a_2=1$ thì ta có $\sum_{k_1+k_2 \le n}k_1k_2={n+2\choose 4}$

Hoặc cho $m=2,a_1=2,a_2=0$ thì:

$\sum_{k_1+k_2 \le n}{k_1\choose 2}={n+2\choose 4}$ hay là $\sum_{i=2}^n \sum_{k_1+k_2 =i}{k_1\choose 2}={n+2\choose 4}$

Chú ý là với mỗi số $k$ thì $k$ đóng $n-k+1$ lần vai trò là $k_1$ (với mỗi $i \ge k$ thì $k$ được xét làm $k_1$ một lần). Như vậy ta suy ra:

$\sum_{k=2}^n (n-k+1){k \choose 2} = {n+2\choose 4}$

Dùng kết quả ở trên của thầy Thanh thì ta có:

$(n+1)\sum_{k=2}^n{k \choose 2}=(n+1){n+1 \choose 3}=(n+2){n+1 \choose 3}-{n+1 \choose 3}=4 {n+2\choose 4}-{n+1 \choose 3}$

Vậy $\sum_{k=2}^n k{k \choose 2}=3 {n+2\choose 4}-{n+1 \choose 3}$

Với một đẳng thức linh hoạt thế này có thể điều chỉnh, gán một số giá trị ta sẽ cho ra được thêm nhiều đẳng thức thú vị khác!

[hxthanh]

Em thấy khá thắc mắc là nếu ta nói số cách chọn $a+b$ bạn trong $n$ bạn là số bằng số cách chọn $a$ bạn từ $k$ bạn đầu tiên và $b$ bạn từ $n-k$ bạn còn lại thì sai cái gì nhỉ? Như vậy thành ra $\sum_{k=0}^n {k\choose a}{n-k\choose b}={n\choose a+b}$?

Thật sự xem những ứng dụng thầy Thanh post ở trên khá hay, một điều thú vị là các số $a_1,a_2,..,a_m$ có thể thay đổi một cách tùy ý miễn đảm bảo giữ nguyên tổng của chúng là được.
...
Với một đẳng thức linh hoạt thế này có thể điều chỉnh, gán một số giá trị ta sẽ cho ra được thêm nhiều đẳng thức thú vị khác!

Thắc mắc của em cũng giống tôi, khi tôi tìm ra đẳng thức này (sẽ post cm vào lúc khác) tôi cũng từng đặt câu hỏi như vậy.
Để xem xét một cách cẩn thận, thì có thể khẳng định một cách chắc chắn rằng: $\sum_{k=0}^n {k\choose a}{n-k\choose b}>{n\choose a+b}$
Tìm hiểu quá trình xây dựng phép đếm của ta:
Gọi $x_1,x_2,...,x_n$ là $n$ bạn (cố định một hàng như thế)
Không mất tổng quát ta giả sử $a+b<n$
Quá trình $k=0$ nghĩa là ta có 2 nhóm $\{\;\}\quad |\quad \{x_1,x_2,...,x_n\}$
Chọn nhóm đầu $a$ bạn, chọn nhóm sau $b$ bạn. Số cách là ${0\choose a}{n\choose b}$
...
Quá trình $k=a$ ta có 2 nhóm $\{x_1,...,x_a\}\quad |\quad \{x_{a+1},...,x_n\}$
Chọn nhóm đầu $a$ bạn, chọn nhóm sau $b$ bạn. Số cách là ${a\choose a}{n-a\choose b}$
Quá trình $k=a+1$ ta có 2 nhóm $\{x_1,...,x_a,x_{a+1}\}\quad |\quad \{x_{a+2},...,x_n\}$
Chọn nhóm đầu $a$ bạn, chọn nhóm sau $b$ bạn. Số cách là ${a+1\choose a}{n-a-1\choose b}$
...
Ta bị đếm thừa chính là ở chỗ này! Ở quá trình $k=a+1$ khi chọn $a$ bạn ở nhóm thứ nhất giả sử ta vẫn chọn đúng $a$ bạn $x_1,...,x_a$ và $b$ bạn ở nhóm 2 ta vẫn chọn đúng $b$ bạn như quá trình $k=a$
Như vậy phép đếm của ta rõ ràng bị thừa!

(Nhưng mà phân tích chỗ thừa này ra, lại chính là gợi ý cho lời giải của bài toán này! Thế nên cho phép tôi Stop ở đây!)

 

...
Hoặc cho $m=2,a_1=2,a_2=0$ thì:
$\sum_{k_1+k_2 \le n}{k_1\choose 2}={n+2\choose 4}$ hay là $\sum_{i=2}^n \sum_{k_1+k_2 =i}{k_1\choose 2}={n+2\choose 4}$
Chú ý là với mỗi số $k$ thì $k$ đóng $n-k+1$ lần vai trò là $k_1$ (với mỗi $i \ge k$ thì $k$ được xét làm $k_1$ một lần). Như vậy ta suy ra:
$\sum_{k=2}^n (n-k+1){k \choose 2} = {n+2\choose 4}$
...

Ở chỗ này theo thầy, biến đổi thế này
$\sum_{k_1+k_2\le n}{k_1\choose 2}=\sum_{k_1=2}^n\sum_{k_2=0}^{n-k_1}{k_1\choose 2}=\sum_{k=2}^n{k\choose 2}\sum_{k_2=0}^{n-k}1=\sum_{k=2}^n{k\choose 2}(n-k+1)$
Đỡ tốn công giải thích!

Mặt khác $\sum_{k=2}^n (n+1-k){k\choose 2}=\sum_{k=2}^n {n+1-k\choose 1}{k\choose 2}=\sum_{k+j=n+1} {j\choose 1}{k\choose 2}={n+2\choose 4}\;\;$ (Áp dụng luôn!)

[Karl Heinrich Marx]

(Nhưng mà phân tích chỗ thừa này ra, lại chính là gợi ý cho lời giải của bài toán này! Thế nên cho phép tôi Stop ở đây!)

 

Ở chỗ này theo thầy, biến đổi thế này
$\sum_{k_1+k_2\le n}{k_1\choose 2}=\sum_{k_1=2}^n\sum_{k_2=0}^{n-k_1}{k_1\choose 2}=\sum_{k=2}^n{k\choose 2}\sum_{k_2=0}^{n-k}1=\sum_{k=2}^n{k\choose 2}(n-k+1)$
Đỡ tốn công giải thích!

Mặt khác $\sum_{k=2}^n (n+1-k){k\choose 2}=\sum_{k=2}^n {n+1-k\choose 1}{k\choose 2}=\sum_{k+j=n+1} {j\choose 1}{k\choose 2}={n+2\choose 4}\;\;$ (Áp dụng luôn!)

Cảm ơn thầy đã giúp em chỉnh sửa phần biến đổi gọn gàng hơn!

Ok em đã hiểu vấn đề chỗ này rồi, vì cái sự lặp đó mà mình buộc phải thêm một bạn đánh dấu ở vị trí $k+1$ để dù có chọn $a$ bạn đầu trùng nhau thì vì cái vị trí chốt này mà giúp phân biệt bộ $a$ bạn chọn từ $k$ này khác cũng bộ $a$ bạn đó chọn từ $k$ khác. Thực ra nhìn vào đẳng thức thì cái việc thêm cái bạn ở vị trí chốt này là điều dễ dàng thấy được nhưng em cứ nghĩ chẳng hiểu thêm anh này vào làm gì và thêm một khúc mắc nữa là $a,b$ là những hằng số quên để ý VP làm e tưởng nhầm là tổng vế trái phụ thuộc vào mỗi cặp $a,b$  nên tự hỏi là khi chọn $a+b+1$ bạn bình đẳng như nhau thì tại sao lại chọn bạn chốt ngăn cách là đúng tại giữa $a$ và $b$ người, điều này không tự nhiên. Xem kĩ lại mới thấy thực ra trong từng $a+b+1$ người đấy chọn bất kì ai làm chốt cũng được và biểu thức vế trái chỉ phụ thuộc vào $a+b$ chứ không phụ thuộc vào cặp $(a,b)$.

Bài toán tổng quát thì có vẻ là tương tự. Nếu đây là một kết quả thầy tự mày mò ra thì thật là tuyệt vời! Nhưng kq nhìn đẹp thế này thì chắc chắn là có người tìm ra trước rồi Hehe điều đấy không quá quan trọng thầy nhể!

[hxthanh]

Cảm ơn thầy đã giúp em chỉnh sửa phần biến đổi gọn gàng hơn!

Ok em đã hiểu vấn đề chỗ này rồi, vì cái sự lặp đó mà mình buộc phải thêm một bạn đánh dấu ở vị trí $k+1$ để dù có chọn $a$ bạn đầu trùng nhau thì vì cái vị trí chốt này mà giúp phân biệt bộ $a$ bạn chọn từ $k$ này khác cũng bộ $a$ bạn đó chọn từ $k$ khác. Thực ra nhìn vào đẳng thức thì cái việc thêm cái bạn ở vị trí chốt này là điều dễ dàng thấy được nhưng em cứ nghĩ chẳng hiểu thêm anh này vào làm gì và thêm một khúc mắc nữa là $a,b$ là những hằng số quên để ý VP làm e tưởng nhầm là tổng vế trái phụ thuộc vào mỗi cặp $a,b$  nên tự hỏi là khi chọn $a+b+1$ bạn bình đẳng như nhau thì tại sao lại chọn bạn chốt ngăn cách là đúng tại giữa $a$ và $b$ người, điều này không tự nhiên. Xem kĩ lại mới thấy thực ra trong từng $a+b+1$ người đấy chọn bất kì ai làm chốt cũng được và biểu thức vế trái chỉ phụ thuộc vào $a+b$ chứ không phụ thuộc vào cặp $(a,b)$.

Bài toán tổng quát thì có vẻ là tương tự. Nếu đây là một kết quả thầy tự mày mò ra thì thật là tuyệt vời! Nhưng kq nhìn đẹp thế này thì chắc chắn là có người tìm ra trước rồi Hehe điều đấy không quá quan trọng thầy nhể!

Thầy giải thích thì ít mà em thu hoạch được lại nhiều!

Đẳng thức đẹp và nhiều ứng dụng (chắc chắn có người tìm ra rồi) nhưng tự mình tìm được mới "sướng"!

[ducvipdh12]

Bằng phương pháp đếm theo hai cách:

CMR: $\sum_{k=0}^n {k\choose a}{n-k\choose b}={n+1\choose a+b+1}$

 

Mở rộng:

 

$\sum_{k_1+k_2+...+k_m=n}{k_1\choose a_1}{k_2\choose a_2}...{k_m\choose a_m}={n+m-1\choose a_1+a_2+...+a_m+m-1}$

dạ có vẻ bài toán của thầy với bài toán này có liên quan đến nhau:

( Đẳng thức Vandermonde ) Cho m,n,r là các số tự nhiên với  $r\leq min\left \{ m,n \right \}$

Chứng minh rằng: $\begin{pmatrix} m+n & \\ r & \end{pmatrix}=\sum_{i=0}^{r}\begin{pmatrix} m & \\ i & \end{pmatrix}\begin{pmatrix} n & \\ r-i & \end{pmatrix}$

[hxthanh]

dạ có vẻ bài toán của thầy với bài toán này có liên quan đến nhau:
( Đẳng thức Vandermonde ) Cho m,n,r là các số tự nhiên với  $r\leq min\left \{ m,n \right \}$
Chứng minh rằng: $\begin{pmatrix} m+n & \\ r & \end{pmatrix}=\sum_{i=0}^{r}\begin{pmatrix} m & \\ i & \end{pmatrix}\begin{pmatrix} n & \\ r-i & \end{pmatrix}$

Em thấy nó liên quan ở đâu? Liên quan như thế nào? Hay mục đích là em giới thiệu cho thầy đẳng thức Vandermonde?

P/s:Ký hiệu tổ hợp viết bằng $\LaTeX$ là

${n\choose k}$

[ducvipdh12]

Em thấy nó liên quan ở đâu? Liên quan như thế nào? Hay mục đích là em giới thiệu cho thầy đẳng thức Vandermonde?

P/s:Ký hiệu tổ hợp viết bằng $\LaTeX$ là

${n\choose k}$

dạ không, em nghĩ cái đẳng thức này cũng khá quen thuộc với cách chứng minh cũng sử dụng phương pháp đếm bằng 2 cách ( đẳng thức này cũng có thể tổng quát hóa lên được ) nhưng 2 cái chỉ khác nhau ở biến chạy $i$ nên em hi vọng có 1 chút gì đó liên quan giữa đẳng thức của thầy với cái đẳng thức này

Bài viết đã được chỉnh sửa nội dung bởi ducvipdh12: 09-06-2015 - 22:53

[hxthanh]

Thực ra thì ai cũng bảo là hai đẳng thức đó giống nhau, nhưng lại không chịu nêu ra cái sự giống nhau đó.
Công nhận là nó giống nhau thật! Nếu đặt $b=r-a$ thì
$\sum_{k=0}^n {k\choose a}{n-k\choose r-a}={n+1\choose r+1}$
Giờ cho $a$ thay đổi từ $0$ đến $r$, ta có:
$\sum_{a=0}^r\sum_{k=0}^n {k\choose a}{n-k\choose r-a}=(r+1){n+1\choose r+1}=(n+1){n\choose r}$

Mặt khác, từ đẳng thức Vandermonde nếu đặt $n$ là $a$ còn $m=n-a$ thì ta có:

$\sum_{k=0}^r {a\choose k}{n-a\choose r-k}={n\choose r}$

Bây giờ ta cũng thay đổi $a$ từ $0$ tới $n$, thì được:

$\sum_{a=0}^n\sum_{k=0}^r {a\choose k}{n-a\choose r-k}=(n+1){n\choose r}$

 

À ra thế! Cuối cùng thì ta thu được:

 

$\sum_{a=0}^r\sum_{k=0}^n {k\choose a}{n-k\choose r-a}=\sum_{a=0}^n\sum_{k=0}^r {a\choose k}{n-a\choose r-k}=(n+1){n\choose r}$

 

Thực chất, ta đã đồng bộ hóa hai quá trình: Với bài toán của ta thì lượng biến thiên là phía "trên", ta cho thêm quá trình biến thiên phía "dưới". Còn đối với đẳng thức Vandermonde thì lượng biến thiên là phía "dưới" ta lại thêm cho quá trình biến thiên phía "trên". Kết quả thu được là như nhau!