Số xuất hiện bao nhiêu lần trong tam giác pascal?
|
e) Vì, chúng tôi đang chọn một tập hợp con có kích thước k từ tập hợp kích thước n của chúng tôi. Chọn tùy ý một phần tử của tập hợp, e. Mỗi tập con phần tử k của chúng ta có chứa e hoặc không. Vì thế, Show = số tập con chứa e + số tập con không chứa e Nếu một tập hợp con chứa e thì ta vẫn phải chọn k – 1 phần tử trong n – 1 phần tử còn lại của tập hợp (). Nếu một tập con không chứa e thì ta phải lấy k phần tử từ n – 1 phần tử còn lại (). Vì thế, yêu cầu tất cả các tập hợp con chứa tất cả các phần tử của một tập hợp và chỉ có một cách để làm điều đó (lấy toàn bộ tập hợp). Tương tự như vậy, yêu cầu tất cả các tập hợp con không chứa phần tử nào của tập hợp và chỉ có một cách để làm điều đó (sử dụng tập hợp rỗng). Thỏa mãn các thuộc tính giống như Pascal(n, k) và f(n, k) Bằng chứng cuối cùng này chứng minh rằng các cách xác định tam giác Pascal bằng số học (cộng hai số ở trên) và tổ hợp (các phần tử xuất phát từ) là nhất quán. Hai bằng chứng này cho thấy giá trị của số thứ k trong hàng thứ n của tam giác Pascal (với số đếm của chúng tôi bắt đầu từ giá trị thứ 0 trong hàng 0) khớp với các giá trị từ công thức giai thừa và kết hợp Kêt quả chung cuộcDo có nhiều cách khác nhau để suy ra tam giác Pascal nên có nhiều cách để chứng minh những khám phá về nó. Các kết quả sau đây có các cách tiếp cận khác nhau để chứng minh các phát hiện liên quan. Mỗi biểu diễn cung cấp những hiểu biết sâu sắc kết hợp lại để cho chúng ta một bức tranh phong phú về các mẫu trong tam giác Suy nghĩ về Pascal mod 2 về mặt hình học và số học (một số câu trả lời cho câu hỏi dự án #3)Mặc dù tam giác Pascal của mod 2 thường được so sánh với miếng đệm của Sierpinski, nhưng nó khác ở một khía cạnh quan trọng. Tam giác Pascal rời rạc. Do sự thiếu liên tục này, tỷ lệ tự tương tự là không chính xác. Ví dụ: số 0 ở giữa trong hình tam giác màu đỏ trong hình bên dưới tương ứng với hình tam giác có sáu số 0 trong hình tam giác màu xanh và hình tam giác có hai mươi tám số 0 ở giữa hình. Hai tỷ lệ này không duy trì tỷ lệ nhất quán (mặc dù tỷ lệ này có xu hướng hướng tới 4, phù hợp với hệ số tỷ lệ là 2). Tuy nhiên, con số hiển thị một biến thể của sự tự đồng dạng khi chúng ta nhìn vào các phần lớn hơn bao giờ hết. Đó là sự tự tương tự dựa trên bản dịch. Mỗi phần tử có cùng tính chẵn lẻ với phần tử của các hàng phần tử trước đó (đối với phần tử lớn nhất có thể) Pascal's Triangle mod 2 với các vùng phù hợp được tô sáng định lý. Đối với tam giác Pascal mod 2, mỗi khối hàng mới từ hàng qua hàng–1 có chính xác hai bản sao của hàng đầu tiên (hàng 0 đến–1) với một tam giác 0 ở giữa Bằng chứng. Ta sẽ chứng minh khẳng định theo quy nạp. Chúng tôi sẽ thêm khẳng định bổ sung rằng hàng–1 bao gồm toàn bộ số 1 (tỷ lệ cược). Chúng tôi có trường hợp cơ sở ở hàng 1, là hai bản sao của hàng 0. Các số hàng 0 và 1 đều có dạng–1 và cả hai hàng chỉ chứa các số 1 Bây giờ hãy chứng minh rằng nếu khẳng định của chúng ta đúng với n thì chúng cũng phải đúng với n + 1. Nếu đúng với n, thì hàng– 1 bao gồm toàn bộ 1. Điều đó có nghĩa là hàng đó sẽ có số 1 ở cuối và– 1 số 0 ở giữa. Đoạn số 0 này sẽ giảm đi một số 0 trên mỗi hàng cho đến khi chúng biến mất trong hàng+– 1 =– 1. Hai thiết bị đầu cuối 1 trong hàng– mỗi thiết bị đầu cuối sẽ bắt đầu mẫu mà thiết bị đầu cuối 1 trong hàng 0 bắt đầu. Hai bản sao này, ban đầu cách nhau bởi – 1 dấu cách, sẽ lớn dần cho đến khi hết các số 0 trong hàng – 1. Đó là, chúng sẽ phát triển, không có sự can thiệp, các mũi tên và từng bản sao của các mũi tên ban đầu. Vì hàng– 1 có 1, hàng– 1 sẽ có +=1. Do đó, chúng tôi đã chỉ ra rằng cả hai yêu cầu, bản sao của tập hợp các hàng trước đó và sự hiện diện của tất cả 1 cần thiết để thiết lập các điều kiện cho một vòng sao chép mới, đều được đáp ứng. Hỏi. E. D Mô tả mô hình tỷ lệ cược (câu trả lời đầu tiên cho số tỷ lệ cược ở hàng 100)Mặc dù các ý tưởng trên có thể tuân theo việc khám phá câu hỏi số 1 của dự án, nhưng sẽ dễ dàng hơn để chứng minh các quan sát về các mẫu tỷ lệ cược sau khi làm việc với câu hỏi số 3 Quá trình sao chép hình học gợi ý một phương pháp liên quan để đếm số lượng tỷ lệ cược trong mỗi hàng. Nếu S là dãy số lẻ trong các hàng của tam giác Pascal, chúng ta có thể lấy S từ quy trình sau. S0 = 1, Sn = Sn – 1 & (2. SN – 1). Nghĩa là. để có chuỗi tiếp theo, hãy lấy chuỗi cuối cùng và theo dõi nó (“&” có nghĩa là nối tiếp) với tất cả các phần tử của chuỗi cuối cùng được nhân đôi
Việc nhân đôi và nối thêm này tương ứng với việc dịch và sao chép mô tả hình học ở trên. Nếu chúng tôi tiếp tục tạo Sn, chúng tôi thấy rằng việc lấy hàng 100 không tốn nhiều công sức. Sn có phần tử nên phần tử thứ 101 trong S nằm trong S7. Các lệnh sau được nhập vào máy tính TI-83 của Texas Instruments sẽ xử lý công việc Bắt đầu với S0 {1}L1 L1 là một biến danh sách Bản dựng S1 tăng(L1, 2*L1)L1 Augment nối hai danh sách Bản dựng S1 đến S7 Nhấn ENTER sáu lần ENTER lặp lại quy tắc đệ quy Để có được hàng 100 L1(101) Đây là phần tử thứ 101 trong L1 Và phần tử thứ 101 là 8 nên có 8 lẻ ở hàng 100 Cách tiếp cận đệ quy này khá nhanh, nhưng nếu máy tính của chúng ta hết pin thì sao? Dự đoán rõ ràng mẫu cho bất kỳ dòng nàoKhi một vấn đề liên quan đến các mẫu nhân đôi hoặc nhân ba, suy nghĩ về biểu diễn cơ số 2 hoặc cơ số 3 có thể dẫn đến hiểu biết sâu sắc. Bảng bên dưới, được tạo bởi một giáo viên Toán học, so sánh số đơn vị trong biểu diễn cơ số 2 của một hàng với số tỷ lệ cược trong hàng đó n n trong cơ sở 2 # của 1 (ở cơ số 2) Số tỷ lệ cược ở hàng n 0 0 0 20 = 1 1 1 1 21 = 2 2 10 1 21 = 2 3 11 2 22 = 4 4 100 1 21 = 2 5 101 2 22 = 4 6 110 2 22 = 4 7 111 3 23 = 8 8 1000 1 21 = 2 Tại sao mô hình này dường như làm việc? . Những điều này ngụ ý sau đây Gọi f(n) là số mục lẻ trong dòng n của tam giác Pascal, khi đó Chức năng này tương đương với việc di chuyển lên trên tam giác theo lũy thừa cao nhất có thể là 2 (đến dòng mà chúng ta đã nhân đôi để tạo thành dòng n). Ví dụ f(27) = 2 f(27 – 16) = 2 f(11). Nhưng f(11) là gì? . Tiếp tục, chúng ta có f(3) = 2 f(3 – 2) = 2 f(1) và f(1) = 2 f(1 – 1) = 2 f(0) và f(0) = 1. Đặt dãy đệ quy đó hoàn toàn cho f(27) = 24. Mỗi thừa số của hai được đóng góp khi chúng ta trừ đi lũy thừa cao nhất của hai có thể và mỗi thừa số này được biểu thị bằng 1 trong biểu diễn cơ số 2 là 27 (2710 = 110112). Nói chung, việc áp dụng lặp đi lặp lại công thức trên sẽ dẫn đến f(0) sau nhiều lần truy hồi bằng số lượng 1 trong biểu diễn cơ số hai của n. Quy tắc này tương ứng độc đáo với mẫu 1, 2, 2, 4 vì các chữ số ngoài cùng bên phải của các số đếm trong cơ số 2 quay vòng qua 00, 01, 10 và 11 (và khiến chúng ta nghĩ về bản chất phân dạng của phép đếm trong bất kỳ cơ số nào Một phát hiện đại sốĐây là đoạn trích từ báo cáo của một nhà thám hiểm Pascal “Tôi đã sử dụng công thức giai thừa để chứng minh rằng các mẫu tỷ lệ trong Pascal luôn hoạt động. Tôi đã có thể chỉ ra rằng tính chẵn lẻ của các trận đấu của. Tuy nhiên, quy mô đó để lại rất nhiều khoảng trống. Nếu chúng ta biết bốn hàng đầu tiên hoặc Pascal, việc nhân đôi tất cả các tọa độ chỉ mang lại cho chúng ta tính chẵn lẻ của các mục chẵn trong hàng 6 và 8 (ví dụ: là số lẻ, nên cũng phải như vậy). Sau đó, tôi chuyển sang chứng minh tính chẵn lẻ của các phần tử lân cận các phần tử có số hàng và số cột chẵn khi tôi phát hiện ra điều mà tôi nghĩ là một quan sát nhỏ kỳ lạ. tôi đã cố chứng minh. Nếu= 0 thì Định lý quan sát nhỏ của Meg. Số chẵn, số lẻ có thể xuất hiện trong tam giác Pascal ở ba trong bốn trường hợp số hàng, số cột chẵn, số lẻ. Tuy nhiên, khi hàng chẵn và cột lẻ, mục nhập luôn là số chẵn Bằng chứng Trường hợp 1. hàng lẻ, cột lẻ. Bằng chứng bằng ví dụ. = 5 và = 10 (vì vậy chúng ta có thể nhận được kết quả chẵn hoặc lẻ) trường hợp 2. hàng là số lẻ, cột là số chẵn. Bằng chứng bằng ví dụ. = 10 và = 5 trường hợp 3. hàng chẵn, cột chẵn. Bằng chứng bằng ví dụ. = 15 và = 28 Trường hợp 4. hàng là chẵn, cột là lẻ. Hàng chẵn là 2r và cột lẻ là 2c-1 Chúng tôi biết rằng toàn bộ biểu thức này là một số nguyên. Vì mẫu số của thừa số cuối cùng bao gồm tất cả các số hạng lẻ, nên thừa số ban đầu của 2 vẫn còn và kết quả là chẵn. Hỏi. E. D Câu hỏi của tôi là tại sao?. Điều gì đặc biệt về những kết hợp này mà chúng phải bằng nhau? . ” Kết quả trên được tóm tắt trong bảng dưới đây Phần còn lại có thể có cho differentmod 2 Các biến thể cũng phát sinh với 3 là mô đun (xem bên dưới). Hai bảng này gợi ý về một số khả năng khái quát hóa. Những khái quát này có giá trị không? Phần còn lại có thể có cho differentmod 3 Suy nghĩ về Pascal mod p số học (một số câu trả lời cho câu hỏi dự án #4)Có 8 số lẻ ở hàng thứ 100 của tam giác Pascal, 89 số chia hết cho 3 và 96 số chia hết cho 5 Tất nhiên, một cách để có được những câu trả lời này là viết ra hàng thứ 100 của tam giác Pascal, chia cho 2, 3 hoặc 5 rồi đếm (đây là ý tưởng cơ bản đằng sau cách tiếp cận hình học) Nhưng hãy xem liệu chúng ta có thể tìm ra cách hiệu quả hơn (và thanh lịch) hơn để có được câu trả lời của mình không. Trong nỗ lực chỉ ra cách một người thực sự có thể đưa ra những kết quả thú vị, phần tiếp theo là tập hợp các cách tiếp cận số học khác nhau mà chúng tôi đã thấy qua nhiều năm khi làm việc với học sinh và giáo viên Chúng ta muốn đếm số phần tử trong một hàng của tam giác Pascal chia hết (hoặc không) chia hết cho một số nguyên nào đó. Chia hết cho một số nguyên tố thì dễ giải quyết hơn, vì vậy hãy xem xét trường hợp đó. Sau đó, câu hỏi đặt ra là
Chà, đôi khi một câu hỏi rõ ràng hơn sẽ dễ trả lời hơn
Hàm “p mạnh nhất của p” này rất hữu ích trong nhiều ngữ cảnh và đôi khi nó được biểu thị bằng ordp, vì vậy, ví dụ: ord5(40)= 1 (20 = 51. 23)ord2(40)= 3ord7(40)= 0ord7(58. 34. 5. 72. 115)= 2Để có ordp(n), hãy phân tích n thành các số nguyên tố và nhìn vào lũy thừa của p xuất hiện. Đó là ordp(n). Bạn có thể kiểm tra xem ordp có thuộc tính mà đối với các số nguyên không âm m và n,Và, nếu n là thừa số của m,Vì vậy, câu hỏi của chúng tôi trở thành Cho một số nguyên n không âm và một số nguyên tố p, cách dễ dàng để tính ordp là gì? Đặc biệt, chúng tôi muốn biết khi nào Chà, có một công thức rõ ràng về các giai thừa Tất nhiên, chúng tôi đã bỏ lỡ một số bội số "thêm" của 3. mọi bội số của 9 (nghĩa là 9, 18, 27. ) đếm hai lần, và có dự luật 1. Nếu n là số nguyên không âm và p là số nguyên tố thì Điều này không thỏa mãn theo nhiều cách. Thứ nhất, nó không cho bạn biết khi các số hạng của tổng giảm xuống 0. Để làm được điều đó, bạn phải viết n trong cơ số p. Nhưng chờ đã—nếu bạn viết n trong cơ số p, toàn bộ tổng trong mệnh đề sẽ dễ dàng hơn. Đây là cách Hãy quay lại ví dụ của chúng ta nếu 139 và 3. Đầu tiên, hãy viết 139 dưới dạng khai triển cơ số 3 Vì thế,Sau đó, để có được ord3(139. ), ta sử dụng mệnh đề và tính toán như sau = = (1. 1) + (0. 3) + (2. 32) + (1. 33) = = = Và mọi thứ là 0 sau này. Chà, nhìn này. Nhìn vào các phương trình ngoài cùng bên phải. Một điều chúng ta có thể làm là đọc xuống thay vì đọc ngang; . Và, giống như khi bạn đọc ngang, khi bạn đọc xuống, bạn sẽ thấy 3 chữ số cơ số của 139, đầu tiên là tất cả ngoại trừ “hàng đơn vị” 1, sau đó là tất cả ngoại trừ 11, sau đó là tất cả trừ 011 và cuối cùng là tất cả trừ 2011. Điều này sẽ luôn luôn xảy ra? . Giả định Sau đó =( n 0. ) + ( n 1. 1) + ( n 2. p ) + ( n 3. p2 ) ++ ( n s. ps - 1 )= ( n 1. 1) + ( n2. p ) + ( n3. p2 ) ++ ( n s. ps - 1 )và=( n0. ) + ( n 1. ) + ( n 2. 1) + ( n3. p ) ++ ( n s. ps - 2 )= (n2. 1) + (n3. p) ++ (ns. ps-2)Và, tổng quát hơn, =(n0. ) + (n1.Vì vậy, hãy viết tất cả những điều này ra và xem liệu chúng ta có thể sử dụng thủ thuật “thêm bớt” không. = (n1. 1) + (n2. p) + (n3. p2) + (n 4. p3) ++ (n s. ps-1)= (n2. 1) + (n3. p) + (n4. p2) + (n 5. p3)+ (n s. ps-2)= (n3. 1) + (n4. p) + (n5. p2) ++ (n s. ps-3)= (ns. 1) Nếu chúng ta cộng xuống, chúng ta sẽ nhận được tổng "đã cắt" của các chữ số cơ số p của n. Hãy phát minh ra một ký hiệu cho điều này. Gọi p(n) là tổng các chữ số cơ số p của n. Sau đó cộng xuống, ta có p(n. )= (p(n) - n0). 1 + (p(n) - n0 - n1). p + (p(n) - n0 - n1 - n2). p2+ (p(n) - n0 - n1 - n2 - n3). p3 ++ (p(n) - n0 - n1 - n2 -- ns-1). ps-1+ (p(n) - n0 - n1 - n2 -- ns). psDòng cuối cùng là 0, nhưng chúng tôi đặt nó vào để duy trì mô hình. Thời gian cho một số đánh lừa đại số xung quanh. Tập hợp thep(n)s, n0s, n1s, v.v. ordp(n. )=p(n)- n0- n1- n2- nsMỗi tổng là một chuỗi hình học, chỉ xin được tính tổng. ordp(n. )=p(n)Dự luật 2. Nếu n là số nguyên không âm và p là số nguyên tố thì Chúng ta có thể áp dụng công thức này cho ví dụ của mình và một lần nữa, nhận được 67 Hiện chúng tôi đang ở một vị trí tốt hơn để đánh giá ordp. Trong thực tế, ordpDự luật 3. Nếu n là số nguyên không âm và p là số nguyên tố thì Lưu ý rằng những gì chúng tôi thực sự quan tâm là whichhave khác 0 ords. Nhưng hóa ra người ta có thể nhận được giá trị chính xác của biểu thức trong mệnh đề 3 mà không cần phải làm gì thêm (chúng tôi biết điều này vì chúng tôi đã nghiên cứu nó trước khi viết các kết quả này). thực tế là Hãy nhìn vào ord3 Vâng, theo đề xuất, chúng ta cần nhìn vào tổng các chữ số (cơ số 3) của 139, 32 và 139 - 32 = 107. Chúng ta có 139= (1. 1) + (1. 3) + (0. 32) + (2. 33) + (1. 34)32= (2. 1) + (1. 3) + (0. 32) + (1. 33) + (0. 34)107= (2. 1) + (2. 3) + (2. 32) + (0. 33) + (1. 34)Vậy,1393= 12011323= 010121073= 10222Vậy,3(139)= 53(32)= 43(107)= 7và mệnh đề 3 nói rằngGiả sử chúng ta đang xem. Chúng tôi viết n, k và n - k trong cơ sở p n= n0 + n1p + n2p2 ++ n spsk= k0 + k1p + k2p2 ++ k spsn - k= m0 + m1p + m2p2 ++ m spsVà giả sử các vật mang được ký hiệu là i.Định lý 1. Nếu n là số nguyên không âm và p là số nguyên tố thì Hãy quay lại câu hỏi ban đầu Cho số nguyên không âm n và số nguyên tố p, với bao nhiêu k thì ordp> 0 ? Theo định lý 1, đây là câu hỏi tương tự như Cho một số nguyên n không âm và một số nguyên tố p, có bao nhiêu k khi cộng k và n - k vào cơ số p? . Và từ đây, chúng ta có thể trừ (từ n + 1) để có câu trả lời mong muốn Một ví dụ sẽ giúp. Giả sử p = 5 và, n = 133866, vì vậy, trong cơ số 5, n là Làm thế nào hai số có thể thêm vào điều này mà không có mang? . Nếu k “kết thúc” bằng 0, n - k kết thúc bằng 1 và ngược lại. Đối với vị trí “năm”, có 4 lựa chọn cho k—nó có thể có số 0, 1, 2 hoặc 3 ở vị trí của số 5 (và n - k tương ứng sẽ có số 3, 2, 1 hoặc 0 ở vị trí . Và vì vậy nó đi. Đây là một bản tóm tắt về những gì có thể xảy rachữ số vị trí trong n số lựa chọn chữ số cho k112—cụ thể là {0,1}534—cụ thể là {0,1,2,3}5245—cụ thể là {0,1,2,3,4}5301—cụ thể là { Nói chung, chúng tôi có câu trả lời cho câu hỏi của chúng tôi Định lý 2. Số phần tử trong hàng thứ n của tam giác Pascal không chia hết cho số nguyên tố p có thể được xác định như sau
Vì vậy, ví dụ, giả sử p = 2. Sau đó, nhìn vào 100 trong cơ số 2 Vì vậy, hãy thêm 1 vào mỗi chữ số và nhân các câu trả lời với nhau. và 8 số ở hàng thứ 100 không chia hết cho 2 (tức là số lẻ). Hãy thử nó trong 3. và số mục trong hàng thứ 100 không chia hết cho 3 làNhưng có 101 mục trong hàng thứ 100, vì vậy101 - 12 = 89 chia hết cho 3 Định lý là của Ernst Kummer (1810-1893), một nhà toán học đã đặt nền móng cho một số phép toán dẫn đến việc chứng minh Định lý cuối cùng của Fermat. Thật vậy, việc biết lũy thừa của một số nguyên tố chia hết bất kỳ mục cụ thể nào của tam giác Pascal hóa ra lại là một công cụ thiết yếu trong chứng minh đó, và nói chung, trong tất cả lý thuyết số, vì vậy dự án này kết nối với một số toán học tiền tuyến Xem Hành vi toán học của Tam giác Pascal tại http. // học viện. giấy bạc. edu/~lriddle/ifs/siertri/pascal. htm để thảo luận thêm về các kết nối hình học và lý thuyết số trong Tam giác Pascal Kết quả cho một số vấn đề mở rộng1) Qua hàng 2n-1 – 1, chúng ta có tỷ lệ cược 3n-1 (tuyên bố này xuất phát từ đối số hình học và số học được trình bày ở trên cho thấy mỗi mẫu được sao chép hai lần trong các hàng tiếp theo). Lên đến hàng r, tổng số giá trị là Biểu thức này là công thức quen thuộc cho các số tam giác. Vì vậy, thông qua hàng, số lượng giá trị trong tam giác là Chúng ta có thể viết lại biểu thức này dưới dạng . Do đó, phần tỷ lệ cược trong tam giác thông qua hàng 2n-1 – 1 là Vì biểu thức cuối cùng này tiến tới 0 khi d trở nên lớn hơn và nó là giới hạn trên của phần số trong tam giác là số lẻ, nên tỷ lệ cược đại diện cho 0% của tam giác. Kết quả đáng ngạc nhiên này có vẻ phản trực giác khi chúng tôi xem xét tất cả các mục lẻ và xem xét rằng tỷ lệ cược xuất hiện trong mỗi hàng. Tuy nhiên, cho dù chúng ta chọn tỷ lệ phần trăm nhỏ như thế nào, tỷ lệ phần trăm cuối cùng sẽ giảm xuống dưới mục tiêu đó 2) Để thảo luận về tam giác Pascal với các mô đun phức hợp, hãy xem Tính chất Số học của Hệ số Nhị thức tại http. //www. toán học. uga. edu/~andrew/Nhị thức. Xem thêm Granville, Andrew (1992). Bộ não của Zaphod Beeblebrox và hàng thứ năm mươi chín của tam giác Pascal. Toán học hàng tháng của Mỹ, 99. 318-331 và Granville, Andrew (1997). Corrigendum. Toán học hàng tháng của Mỹ, 104. 848-851 Số 41 xuất hiện bao nhiêu lần trong tam giác Pascal?Số 41 xuất hiện bao nhiêu lần trong tam giác Pascal? . Just twice, on the line beginning and ending .
Số 91 xuất hiện bao nhiêu lần trong tam giác Pascal?Bốn lần . Một số quan sát sơ bộ. Số trên các dòng trước dòng không thể chia cho.
Số nào xuất hiện nhiều nhất trong tam giác Pascal?Trong tam giác Pascal, số 1 xuất hiện vô số lần. Số 2 chỉ xuất hiện một lần. Số 3 xuất hiện 2 lần.
Có bao nhiêu số ở hàng thứ 100 của tam giác Pascal?Phương pháp số học. Có tám số lẻ ở hàng thứ 100 của tam giác Pascal, 89 số chia hết cho 3 và 96 số chia hết cho 5. |
