Các phương pháp đếm nâng cao
Started By namdung, 04-05-2006 - 19:19
#41
Posted 16-05-2006 - 16:11
Thưa thầy, quyển "Tìm tòi để học toán" có thể tìm ở đâu? Nhà sách nào?
#42
Posted 16-05-2006 - 16:52
thầy có thể tổng hợp lại thành file Word hoặc pdf được không ???
em thấy bài viết này rất hay
em thấy bài viết này rất hay
#43
Posted 16-05-2006 - 17:05
chưa có bài viết đâu bạn ạ
Các thành viên còn đang đóng góp mà
Các thành viên còn đang đóng góp mà
la vieillesse est une île entourée par la mort
#44
Posted 16-05-2006 - 22:41
Đúng rồi. Bây giờ đang là lúc để chúng ta bung ra. Sau đó sẽ gom lại thành 1 bài viết hoàn chỉnh.
Cuốn sách "Tìm tòi để học toán" của Lê Quang Nẫm có thể tìm ở các nhà sách ở Tp HCM như nhà sách Phú Nhuận, nhà sách Phan Đăng Lưu. Nếu các bạn thích để hôm nào tôi tìm mua tặng cho các bạn.
Cuốn sách "Tìm tòi để học toán" của Lê Quang Nẫm có thể tìm ở các nhà sách ở Tp HCM như nhà sách Phú Nhuận, nhà sách Phan Đăng Lưu. Nếu các bạn thích để hôm nào tôi tìm mua tặng cho các bạn.
#45
Posted 16-05-2006 - 22:47
Lời giải 2 mà Hatucdao đưa ra thật là độc đáo. Theo Erdos thì Chúa có 1 cuốn sáchHì, về lục mãi mới ra ... hi vọng góp vài ví dụ minh họa (đây là "phiên bản" thời 2002, ko biết có lạc hậu chưa )
ghi toàn những lời giải như vậy, vấn đề là chúng ta phải tìm ra nó thôi.
Bài học: Bài toán nào hay cũng có lời giải đẹp.
Tuy nhiên: Trước khi tìm được lời giải đẹp phải tìm được lời giải cái đã.
- caybutbixanh likes this
#46
Posted 17-05-2006 - 07:13
Các anh em ở gần Viện Toán Học có thể tìm đọc cuốn Proff from the book để hiểu rõ hơn về câu nói nàyTheo Erdos thì Chúa có 1 cuốn sách ghi toàn những lời giải như vậy
#47
Posted 18-05-2006 - 12:53
Sử dụng phương pháp hàm sinh (một chút về số phức) nmt có một số bài đề nghị sau:
1, Cho trước p nguyên tố, k và n, Tính số bộ $(x_1,...,x_n)$ nguyên không âm trong khoảng [0,k] sao cho $1x_1+2x_2+...+nx_n$ chia hết cho p.
2, cho số nguyên tố p lẻ, n>p. Tính số tập con p phần tử của tập hợp gồm n số nguyên dương đầu tiên mà tổng của p phần tử này chia hết cho p. (n=2p là bài thi toán quốc tế 95)
...
1, Cho trước p nguyên tố, k và n, Tính số bộ $(x_1,...,x_n)$ nguyên không âm trong khoảng [0,k] sao cho $1x_1+2x_2+...+nx_n$ chia hết cho p.
2, cho số nguyên tố p lẻ, n>p. Tính số tập con p phần tử của tập hợp gồm n số nguyên dương đầu tiên mà tổng của p phần tử này chia hết cho p. (n=2p là bài thi toán quốc tế 95)
...
Edited by inhtoan, 11-06-2009 - 10:16.
Any matter begins with a great spiritual disturbance - Antonin Artaud
#48
Posted 19-05-2006 - 19:27
Mình cũng đang quan tâm tới Combinatoric, cụ thể là Schubert-, Shur polynomials và Schubert calculus. Tuy nhiên hồi học phổ thông mình không được học Background cẩn thận về Combinatoric, thấy trên trang nhất của dd có topic này khá hay, liệu ai đó có thể trình bầy từ đầu 1 cách cơ bản ( thay vì đem những bài toán khó ra ) để cho những người có cùng quan tâm có thể có 1 overview về Combinatoric được không? Nói thực sự thì cuốn Enumerative Combinatorics của Stanley dầy quá, mà kiến thức thì cần nhanh, đọc xong chắc tới già mới giải quyết được vấn đề mất.
Thay vì trình bầy dài dòng các bài toán hoặc các ví dụ (ít nhất đối với mình không interesting lắm ) thì ai đó có thể trình bầy 1 cách precisely các định nghĩa căn bản nhất không? Ví dụ như Symmetric Polynomials, Young Tableaux, Ferrer Diagramm, Symmetric groups $S_n$ or something like that.
Thay vì trình bầy dài dòng các bài toán hoặc các ví dụ (ít nhất đối với mình không interesting lắm ) thì ai đó có thể trình bầy 1 cách precisely các định nghĩa căn bản nhất không? Ví dụ như Symmetric Polynomials, Young Tableaux, Ferrer Diagramm, Symmetric groups $S_n$ or something like that.
Edited by inhtoan, 11-06-2009 - 10:18.
#49
Posted 19-05-2006 - 19:33
Em nghĩ là các topic về Symmetric Polynomials, Ferrer Diagramn và Nhóm S_n thì có thể lập riêng thành các topic khác anh Thi ạ. Trong topic này chủ đề chính là các phép đếm ạ
Ferrer Diagramn: cái này thú vị đấy nhỉ, có ai mở màn đi cho hào hứng nào
Ferrer Diagramn: cái này thú vị đấy nhỉ, có ai mở màn đi cho hào hứng nào
#50
Posted 19-05-2006 - 20:11
Vấn đề là pp đếm và các vấn đề tôi nhắc đến ở trên không disjoint. There is no field, which has nothing to do with the orthers.
Nhân tiện về Ferrer Diagramm mình có câu hỏi về LaTeX có ai biết cách vẽ mấy cái bảng vuông không?
Nhân tiện về Ferrer Diagramm mình có câu hỏi về LaTeX có ai biết cách vẽ mấy cái bảng vuông không?
#51
Posted 22-05-2006 - 22:43
Tất nhiên là các khái niệm này đều liên quan đến Tổ hợp, phép đếm (Phân hoạch, đếm số các đơn thức ...). Tuy nhiên, có lẽ với các bạn học sinh phổ thông thì hơi cao và chưa thật cần (chúng ta sẽ trích vài bài ra để các bạn làm quen). Theo tôi, chúng ta nên mở 1 topic về Shubert Polynomials, Schur Polynomials, Ferrer Diagramm, Young Tablaux ... bên làng Đại học thì phù hợp hơn.
#52
Posted 22-05-2006 - 23:09
Hướng giải bài toán nghịch thế:
Nhắc lại, với hoán vị p của {1, 2, ..., n}, ta gọi (i, j) là một nghịch thế nếu p(i) > p(j) mà i < j. Gọi b(i) là số các nghịch thế mà thành phần thứ nhất là i.
b = (b(1), b(2), ..., b(n)) được gọi là bảng nghịch thế của hoán vị p.
Hãy chứng minh rằng
1) Tồn tại 1 song ánh giữa các hoán vị của {1, 2, ..., n} và tập các bảng nghịch thế
2) 0 <= b(i) <= n-i với mọi i = 1, 2, ..., k.
Và số nghịch thế của p bằng I(p) = b(1) + b(2) + ...+ b(n)
Từ đó sẽ đưa đến 2 lời giải khác nhau cho bài toán tính số nghịch thế trung bình.
Các thảo luận tiếp theo
Để topic của chúng ta không bị lan man, chúng ta sẽ tiếp tục thảo luận về những ứng dụng của phương pháp hàm sinh.
Tiếp theo, tôi sẽ trình bày về cơ sở của phương pháp thêm bớt, công thức nghịch đảo Mobius và những ứng dụng.
Mong tiếp tục nhận được sự đóng góp của các bạn.
Các câu hỏi thắc mắc, các đề nghị luôn được hoan nghênh.
Nhắc lại, với hoán vị p của {1, 2, ..., n}, ta gọi (i, j) là một nghịch thế nếu p(i) > p(j) mà i < j. Gọi b(i) là số các nghịch thế mà thành phần thứ nhất là i.
b = (b(1), b(2), ..., b(n)) được gọi là bảng nghịch thế của hoán vị p.
Hãy chứng minh rằng
1) Tồn tại 1 song ánh giữa các hoán vị của {1, 2, ..., n} và tập các bảng nghịch thế
2) 0 <= b(i) <= n-i với mọi i = 1, 2, ..., k.
Và số nghịch thế của p bằng I(p) = b(1) + b(2) + ...+ b(n)
Từ đó sẽ đưa đến 2 lời giải khác nhau cho bài toán tính số nghịch thế trung bình.
Các thảo luận tiếp theo
Để topic của chúng ta không bị lan man, chúng ta sẽ tiếp tục thảo luận về những ứng dụng của phương pháp hàm sinh.
Tiếp theo, tôi sẽ trình bày về cơ sở của phương pháp thêm bớt, công thức nghịch đảo Mobius và những ứng dụng.
Mong tiếp tục nhận được sự đóng góp của các bạn.
Các câu hỏi thắc mắc, các đề nghị luôn được hoan nghênh.
#53
Posted 25-05-2006 - 05:57
Mấy cái này thiết nghĩ sau khi tổng kết hết nên để vào 1 file pdf đọc cho tiện.
Edited by 1001001, 25-05-2006 - 05:58.
My major is CS.
#54
Posted 29-05-2006 - 23:26
Mấy hôm nay bận quá, chưa gõ bài Inclusion-Exclusion được. Tạm thời mọi người đọc bài sau về Moebius.
Công thức nghịch đảo Moebius
Anh em ơi, có cái gì hay post lên đi nhé, đây là bài viết mở mà.
Công thức nghịch đảo Moebius
Anh em ơi, có cái gì hay post lên đi nhé, đây là bài viết mở mà.
#55
Posted 31-05-2006 - 15:28
Thầy namdung có thể cho em biết nguồn gốc của các phương pháp thầy đưa ra không ạ?
Với lại thầy cho em một số tư liệu sơ bộ về mấy cái này được không ạ?Em có vẻ hơi khó hiểu về chúng.
Với lại thầy cho em một số tư liệu sơ bộ về mấy cái này được không ạ?Em có vẻ hơi khó hiểu về chúng.
#56
Posted 31-05-2006 - 17:11
Nguồn gốc các phương pháp này? Nghe chừng là khó đấy. Cái này phải đọc các sách kinh điển may ra mới biết được, chứ mình chỉ học lóm từ các cuốn sách khác nhau, làm sao mà nói rõ nguồn gốc được.
Phương pháp song ánh và Phương pháp thêm bớt rõ ràng là sử dụng lý thuyết tập hợp. Bản thân bài toán đếm cũng xuất phát từ việc đếm số phần tử của một tập hợp.
Phương pháp hàm sinh sử dụng các công cụ của đại số và giải tích để giải quyết bài toán đếm, bằng cách cho tương ứng các kết quả của một phép đếm với hệ số của một đa thức hoặc một chuỗi.
Món này được nghiên cứu khá sâu, có 1 cuốn sách lớn của Wilf gọi là "Generafunctology" có thể tìm ở trên mạng.
Tôi gửi cho các bạn bài giảng của tôi soạn năm 2003 để giảng cho đội tuyển (tuy nhiên đến lúc giảng thì chẳng giảng được bao nhiêu, vì các bạn đội tuyển biết hết rồi ). Bài này viết giống như đề cương nên chưa được triển khai đầy đủ. Các bạn cần hỏi gì cứ hỏi nhé.
Phương pháp song ánh và Phương pháp thêm bớt rõ ràng là sử dụng lý thuyết tập hợp. Bản thân bài toán đếm cũng xuất phát từ việc đếm số phần tử của một tập hợp.
Phương pháp hàm sinh sử dụng các công cụ của đại số và giải tích để giải quyết bài toán đếm, bằng cách cho tương ứng các kết quả của một phép đếm với hệ số của một đa thức hoặc một chuỗi.
Món này được nghiên cứu khá sâu, có 1 cuốn sách lớn của Wilf gọi là "Generafunctology" có thể tìm ở trên mạng.
Tôi gửi cho các bạn bài giảng của tôi soạn năm 2003 để giảng cho đội tuyển (tuy nhiên đến lúc giảng thì chẳng giảng được bao nhiêu, vì các bạn đội tuyển biết hết rồi ). Bài này viết giống như đề cương nên chưa được triển khai đầy đủ. Các bạn cần hỏi gì cứ hỏi nhé.
Attached Files
#57
Posted 01-06-2006 - 21:02
Em cảm ơn thầy rất nhiều về cái tài liệu này,cũng có thể nó phần nào giúp em hiểu hơn về mấy phương pháp này.Em sẽ cố gắng đào sâu về phần này.
#58
Posted 05-06-2006 - 17:49
ở thành phố còn nhà sách nào bán không thầy?Cuốn "Toán rời rạc nâng cao" của Trần Ngọc Danh, NXB Đại học QG Tp HCM 2004.Em hiểu rồi,thưa thầy,cuốn 'Toán rời rạc nâng cao'có thể tìm thấy ở đâu ?
#59
Posted 05-06-2006 - 21:20
Bán ở Trường ĐHKHTN, 227 Nguyễn Văn Cừ, Q5.
Nhà sách ở bên trong trường ấy.
Nhà sách ở bên trong trường ấy.
#60
Posted 06-06-2006 - 20:26
Tiếp tục chủ đề của chúng ta, mời các bạn tham khảo địa chỉ
Các nguyên lý đếm
để nắm cơ bản về các nguyên lý và phương pháp đếm.
Các nguyên lý đếm
để nắm cơ bản về các nguyên lý và phương pháp đếm.
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users