Mỗi số trong tam giác Pascal là tổng của hai số theo đường chéo phía trên nó [ngoại trừ số 1]
Ví dụ, từ hàng thứ năm và hàng thứ tư của tam giác Pascal, ta có \[10 = 4+6\]. Trong ký hiệu được giới thiệu trước đó trong mô-đun này, điều này nói
\[ \dbinom{5}{2} = \dbinom{4}{1} + \dbinom{4}{2}. \]Bây giờ chúng ta mô tả mô hình chung
Định lý [Đẳng thức Pascal]\[ \dbinom{n}{r} = \dbinom{n-1}{r-1} + \dbinom{n-1}{r}, \qquad \text{for}\quad 0 . \] Bằng chứng \begin{align*} \dbinom{n-1}{r-1} + \dbinom{n-1}{r} &= \dfrac{[n-1]. }{[n-r]. [r- 1]. } + \dfrac{[n-1]. }{[n-1- r]. r. }\\ &= \dfrac{[n-1]. }{[n-r-1]. [r-1]. }\Bigg[\dfrac{1}{n-r} + \dfrac{1}{r}\Bigg]\\ &= \dfrac{[n-1]. }{[n-r-1]. [r-1]. }\Bigg[\dfrac{n}{[n-r]r} \Bigg]\\ &= \dfrac{n. }{[n-r]. r. }\\ &=\dbinom{n}{r}. \end{align*}\[\Hộp\]
Bây giờ chúng ta sẽ thực hiện một cách chứng minh khác về danh tính của Pascal trong một trường hợp đặc biệt, nhưng cách chứng minh chung về cơ bản là giống nhau
Hãy để chúng tôi bắt đầu với một bộ sáu phần tử
\[ \{a,b,c,d,e,f\}. \]Số tập con có 4 phần tử là \[\dbinom{6}{4}\]. Bây giờ chúng ta hãy chọn ra chữ cái \[c\]. Các tập hợp con có bốn phần tử có thể được tách thành hai loại
- bộ bốn phần tử có chứa \[c\]
- các bộ bốn phần tử không chứa \[c\]
Số tập hợp con bốn phần tử chứa \[c\] là \[\dbinom{5}{3}\]. Số tập hợp con bốn phần tử không chứa \[c\] là \[\smash{\dbinom{5}{4}}\]. Kể từ đây,
\[ \dbinom{6}{4} = \dbinom{5}{3} + \dbinom{5}{4}. \]Điều này cho chúng ta một bằng chứng tổ hợp về danh tính của Pascal
Ứng dụng - số lượng đường dẫn trên lưới
Sơ đồ sau đây hiển thị lưới \[3 \times 3\]. Câu hỏi đặt ra là có bao nhiêu đường đi từ góc dưới bên trái đến góc trên bên phải của lưới, nếu bạn chỉ có thể di chuyển sang phải hoặc lên trên. Chúng tôi sẽ gọi những chuyển động như vậy là chuyển động 'về phía trước'. Một đường dẫn từ góc dưới cùng bên trái đến góc trên cùng bên phải được hiển thị bằng màu đỏ
Mô tả chi tiết sơ đồ
Các số trên lưới cho biết số lượng đường dẫn đến điểm đó. Những con số này tạo thành một phần của tam giác Pascal. Bạn có thể di chuyển lên và qua lưới bằng cách sử dụng phép cộng để tìm số lượng đường dẫn đến bất kỳ điểm nào trên lưới. Ví dụ
- Để đến điểm Y bạn phải đi qua điểm P hoặc điểm X. Có một đường dẫn đến P và hai đường dẫn đến X. Do đó có ba con đường dẫn đến Y
Theo cách tương tự, bạn có thể tìm ra tất cả các số trong lưới, kết thúc bằng 20 đường dẫn từ D đến B
Có một cách để tính tổng số đường dẫn trực tiếp. Chúng ta có thể coi các đường dẫn là các chuỗi ký tự. Chúng ta sẽ gọi một nước đi sang phải \[R\] và một nước đi lên \[U\]. Đường dẫn hiển thị trong sơ đồ là \[RURURU\]. Có sáu bước di chuyển trong mỗi chuỗi đưa bạn từ D đến B. Phải có ba \[U\] và ba \[R\] trong mỗi chuỗi như vậy. Nếu bạn chọn vị trí đặt ba \[R\] trong chuỗi, thì các vị trí còn lại phải được điền bằng \[U\]'s. Vậy có \[\dbinom{6}{3} = 20\] đường đi từ D đến B
Vấn đề này có thể được giải quyết đối với lưới \[n\times n\] bằng cách coi các đường dẫn là các chuỗi ký tự \[2n\]. Cần \[2n\] di chuyển để đi từ góc dưới cùng bên trái của lưới \[n\times n\] đến góc trên cùng bên phải và \[n\] trong số các bước di chuyển này là \[U\] và
Đường dẫn có thể là \[UUURRR\dots RUR\dots RR\]. Có \[2n\] chữ cái trong chuỗi và có \[n\] \[U\]'s và \[n\] \[R\]'s. Nếu bạn chọn vị trí đặt \[n\] \[R\] trong chuỗi, thì các vị trí còn lại phải được điền bằng \[U\]'s. Có \[\dbinom{2n}{n}\] cách để thực hiện việc này và vì vậy, đối với lưới \[n\times n\], có \[\smash{\dbinom{2n}{n}}\
bài tập 3
Chứng minh rằng số đường dẫn trong lưới \[m \times n\] di chuyển từ góc dưới bên trái lên góc trên bên phải mà chỉ được phép di chuyển về phía trước là \[\dbinom{m+n}{n}\]
Quan sát 2Mỗi hàng của tam giác Pascal là đối xứng
Rõ ràng
vì việc chọn các đối tượng \[r\] từ các đối tượng \[n\] sẽ rời khỏi các đối tượng \[n-r\] và việc chọn các đối tượng \[n-r\] sẽ rời khỏi các đối tượng \[r\]. Điều này có nghĩa là hệ số của \[x^r\] trong khai triển của \[[1+x]^n\] giống với hệ số của \[x^{n-r}\]
Quan sát 3Tổng của mỗi hàng trong tam giác Pascal là lũy thừa của 2. Trên thực tế, tổng các mục trong hàng thứ \[n\] là \[2^n\]
Bằng chứngChúng tôi sử dụng định lý nhị thức ở dạng
\[ [1+x]^n = \dbinom{n}{0}+ \dbinom{n}{1}x + \dbinom{n}{2}x^2+\dots+\dbinom{n}{r . \]Thay thế \[x = 1\] cho
\[ 2^n = \dbinom{n}{0}+ \dbinom{n}{1} + \dbinom{n}{2}+\dots+\dbinom{n}{r}+\dots+ \dbinom{n . \]
\[\Hộp\]
Ứng dụng — Số tập hợp con của một tập hợp
Có một cách khác để chứng minh quan sát trên. Dưới đây là một ví dụ để minh họa ý tưởng. Có ba loại sôcôla khác nhau \[A\], \[B\] và \[C\], và Alison có thể chọn ăn bất kỳ loại nào cô ấy muốn. Có bao nhiêu cách lựa chọn này có thể được thực hiện?
Đặt \[S=\{A,B,C\}\]. Các tập con là
\[ ø, \quad \{A\}, \quad \{B\}, \quad \{C\}, \quad \{A,B\}, \quad \{A,C\}, \quad . \]Có
\begin{alignat*}{2} \dbinom{3}{0}&=1\text{ tập hợp không có phần tử nào},&\qquad \dbinom{3}{1}&=3 \text{ tập hợp có một phần tử . \end{alignat*}Vậy tổng số cách chọn là
Bây giờ hãy nghĩ về từng viên sô cô la một
- sô cô la \[A\] có thể được chọn hoặc không [2 cách]
- sô cô la \[B\] có thể được chọn hoặc không [2 cách]
- sô cô la \[C\] có thể được chọn hoặc không [2 cách]
Vậy có tổng số \[2^3 = 8\] cách chọn sôcôla [kể cả cách không chọn]. điều này mang lại
\[ \dbinom{3}{0}+\dbinom{3}{1}+\dbinom{3}{2}+\dbinom{3}{3}=2^3. \]Đối số có thể dễ dàng được mở rộng để chứng minh kết quả cho một tập hợp các phần tử \[n\]
Quan sát 4Trong bất kỳ hàng nào của tam giác Pascal, tổng của các số thứ nhất, thứ ba, thứ năm, \[\dots\] bằng tổng của các số thứ hai, thứ tư, thứ sáu, \[\dots\]
Để chứng minh nhận xét này, ta sử dụng định lý nhị thức ở dạng
\[ [1+x]^n = \dbinom{n}{0}+ \dbinom{n}{1}x + \dbinom{n}{2}x^2+\dots+\dbinom{n}{r . \]Đặt \[x=-1\]. sau đó
\[ 0 = \dbinom{n}{0}- \dbinom{n}{1} + \dbinom{n}{2}-\dbinom{n}{3} + \dots+[-1]^{r} . \]Vì vậy
\[ \dbinom{n}{0}+\dbinom{n}{2}+\dbinom{n}{4}+\cdots = \dbinom{n}{1}+\dbinom{n}{3}+đó là quan sát
Điều này cho thấy rằng, đối với khai triển của \[[1+x]^n\], tổng các hệ số của các lũy thừa chẵn bằng tổng các hệ số của các lũy thừa lẻ. Sử dụng Quan sát 3, suy ra rằng mỗi tổng này bằng \[2^{n-1}\]