Toán học tổ hợp

Go down

Toán học tổ hợp

Bài gửi by Admin on 20/10/2011, 23:04

Toán học tổ hợp
http://vi.wikipedia.org/wiki/T%E1%BB%95_h%E1%BB%A3p

http://www.baomoi.com/Toan-to-hop/59/6766444.epi

Toán tổ hợp

Ta hãy bắt đầu từ một số bài toán sau.

Bài toán 1. Qua kỳ nghỉ hè, bốn bạn học sinh gặp lại nhau. Mừng rỡ, các bạn đã bắt tay nhau. Biết hai bạn bất kỳ đều bắt tay nhau. Hỏi có bao nhiêu cái bắt tay?

Bài toán 2. Trong giờ thực hành, ba bạn An, Bình, Nam được cô giáo giao cho mang ba dụng cụ khác nhau từ phòng dụng cụ đến phòng thí nghiệm. Biết mỗi bạn chỉ mang được một dụng cụ. Hỏi có bao nhiêu cách mang dụng cụ đến phòng thí nghiệm?

Bài toán 3. Có bao nhiêu số có ba chữ số mà các chữ số chỉ là 4 hoặc 6?

Bài toán 4. Có bao nhiêu số có ba chữ số khác nhau mà các chữ số chỉ là 1, 2, 3, 4 hoặc 5?

Bài toán 5. Có bao cách xếp 4 người thành hàng ngang để chụp ảnh?

Bài toán 6. Đầu năm học, tổ I của lớp 4A gồm tám bạn chọn ra hai bạn đưa vào danh sách bầu cán bộ lớp. Hỏi có bao nhiêu cách chọn?

Bài toán 7. Đầu năm học, lớp 5A gồm 40 học sinh tổ chức bầu ra một lớp trưởng và hai lớp phó, một lớp phó học tập, một lớp phó văn nghệ. Hỏi có bao nhiêu cách chọn?

Bài toán 8. Nghỉ hè, ba người cháu nội và ngoại của ông Bắc là Tùng, Hà và Hằng được về thăm ông. Vừa lúc đó, ông có 5 cái kẹo, đem chia cho các cháu, mỗi cháu ít nhất một chiếc. Hỏi ông có bao nhiêu cách chia?

Các bài toán trên là những dạng toán khác nhau của toán tổ hợp, một ngành của toán rời rạc. Một trong những mảng của toán tổ hợp được nghiên cứu sớm nhất là lý thuyết đồ thị với kết quả đầu tiên là bài toán Bảy cây cầu của Leonhard Euler năm 1736. Chỉ riêng lý thuyết đồ thị cũng đã có nhiều đóng góp cho thực tiễn cũng như trong toán học. Tiêu biểu như Bài toán bốn màu: chỉ dùng bốn màu khác nhau để tô màu cho một bản đồ bất kỳ sao cho hai quốc gia có chung đường biên giới thì không cùng màu. Các em hãy lấy bản đồ ra để quan sát xem đúng không nhé. Bài toán Tìm đường đi ngắn nhất cũng rất được chú ý. Tuy vậy, những kết quả chủ yếu của toán tổ hợp thì phần lớn được nghiên cứu kỹ vào cuối thế kỷ XX, từ khi khoa học máy tính phát triển mạnh.

Thế thì toán tổ hợp là gì? Quan sát 8 bài toán trên, chúng ta có thể hình dung đó là một ngành của toán nghiên cứu sự kết hợp của một số đối tượng trong một nhóm đối tượng hữu hạn. Nó có liên quan đến nhiều lĩnh vực khác như đại số, lý thuyết xác suất, hình học, cũng như đến các ngành ứng dụng như khoa học máy tính và vật lý thống kê.

Bây giờ, ta cùng giải các bài toán trên.

Bài toán 1. Vì mỗi bạn bắt tay 3 lần nên 4 bạn bắt tay 3 x 4 = 12 lần. Mà mỗi cái bắt tay được tính 2 lần (cho cả hai bạn) nên có 12 : 2 = 6 (cái bắt tay).

Bài toán 2. Giả sử khi mang thiết bị, bạn An lấy đầu tiên, kế đến là bạn Bình rồi đến bạn Nam. Như thế An có 3 cách chọn, Bình có 2 cách chọn, Nam có 1 cách chọn. Vậy có 3 x 2 x 1 = 6 (cách mang).

Bài toán 3. Vì mỗi chữ số hàng trăm, hàng chục và hàng đơn vị đều có 2 cách chọn nên có 2 x 2 x 2 = 8 (số có ba chữ số).

Bài toán 4. Chữ số hàng trăm có 5 cách chọn là lấy bất kỳ một trong năm số 1, 2, 3, 4, 5. Sau đó chữ số hàng chục có 4 cách chọn (khác chữ số hàng trăm). Chữ số hàng đơn vị còn 3 cách chọn. Vậy có 5 x 4 x 3 = 60 (số có ba chữ số).

Bài toán 5. Đáp số 4 x 3 x 2 x 1 = 24 (cách).

Bài toán 6. Đáp số 8 x 7 : 2 = 28 (cách).

Bài toán 7. Đáp số 40 x 39 x 38 = 59280 (cách).

Bài toán 8: Với 5 (n) và 3 (k) cho trước thì số các bộ tần số k1,k2,...,kn có thể có là


Được sửa bởi Admin ngày 20/10/2011, 23:10; sửa lần 1.
avatar
Admin
Admin

Tổng số bài gửi : 2046
Points : 3620
Reputation : 0
Join date : 25/10/2009
Đến từ : http://casablanca.top-forum.net

Xem lý lịch thành viên http://casablanca.top-forum.net

Về Đầu Trang Go down

Re: Toán học tổ hợp

Bài gửi by Admin on 20/10/2011, 23:10

http://vi.wikipedia.org/wiki/T%E1%BB%95_h%E1%BB%A3p


Toán học tổ hợp (hay giải tích tổ hợp, đại số tổ hợp, lý thuyết tổ hợp) là một ngành toán học rời rạc, nghiên cứu về các cấu hình kết hợp các phần tử của một tập hữu hạn phần tử. Các cấu hình đó là các hoán vị, chỉnh hợp, tổ hợp,... các phần tử của một tập hợp.
Nó có liên quan đến nhiều lĩnh vực khác của toán học, như đại số, lý thuyết xác suất, lý thuyết ergod (ergodic theory) và hình học, cũng như đến các ngành ứng dụng như khoa học máy tính và vật lí thống kê.
Toán học tổ hợp liên quan đến cả khía cạnh giải quyết vấn đề lẫn xây dựng cơ sở lý thuyết, mặc dù nhiều phương pháp lý thuyết vững mạnh đã được xây dựng, tập trung vào cuối thế kỉ 20 (xem trang Danh sách các chủ đề trong toán học tổ hợp). Một trong những mảng lâu đời nhất của toán học tổ hợp là lý thuyết đồ thị.
Một ví dụ về câu hỏi tổ hợp là: Có bao nhiêu trật tự sắp xếp các quân bài có thể có của một bộ bài 52 lá riêng biệt? Câu trả lời là 52!.
Toán học tổ hợp được dùng nhiều trong khoa học máy tính để ước lượng số phần tử của các tập hợp.

Mục lục
1 Các bài toán cơ bản
2 Một số cấu hình chính
3 Một số công thức tính
4 Bài toán liệt kê
4.1 Thứ tự từ điển
4.2 Liệt kê các hoán vị của tập n phần tử
4.2.1 Hoán vị kế tiếp của một hoán vị (theo thứ tự từ điển)
4.2.2 Thuật toán liệt kê tất cả các hoán vị của n số 1,2,...,n
5 Ví dụ

Một số công thức tính

1 - Công thức tính số các chỉnh hợp lặp chập k của n phần tử là F(n,k) = n^k
2 - Công thức tính số các chỉnh hợp chập k của n phần tử là



3 - Công thức tính số các hoán vị của n phần tử là P(n) = n!

4 - Công thức tính số các hoán vị vòng quanh của n phần tử là Q(n) = (n − 1)!

5 - Công thức tính số các tổ hợp chập k của n phần tử là


6 - Công thức tính số các chỉnh hợp lặp của n phần tử với tần số k1,k2,...,kn là

với k = k1 + k2 + .. + kn

7 - Với n và k cho trước thì số các bộ tần số k1,k2,...,kn có thể có là


=================================================================
VD

http://www.diendantoanhoc.net/vmf/index.php?option=com_kunena&Itemid=468&func=view&catid=8&id=407

VD về liệt kê các tổ hợp chập k của tập n phần tử
Cho tập A gồm 5 chữ số hệ thập phân A={1,2,3,4,5}
Tính
1) Số các số tự nhiên 4 chữ số lập thành từ 5 chữ số trên
2) Số các số tự nhiên gồm 3 chữ số khác nhau lập thành từ 5 chữ số trên
3) Số các tập con 3 phần tử cua 5 chữ số trên
4) Số các hoán vị của 5 số đó
5) Số các hoán vị vòng quanh
6) Số các hoán vị khác nhau có thể có khi hoán vị các chữ cái trong từ XAXAM
7) Số cách chia 7 chiếc kẹo cho 4 trẻ em là

Bạn dùng công thức trên kia mà làm nhé.

------------------------------------------

Cho tập A gồm 5 chữ số hệ thập phân A={1,2,3,4,5}
1) Số các số tự nhiên 4 chữ số lập thành từ 5 chữ số trên


2) Số các số tự nhiên gồm 3 chữ số khác nhau lập thành từ 5 chữ số trên


3) Số các tập con 3 phần tử cua 5 chữ số trên


4) Số các hoán vị của 5 số đó


5) Số các hoán vị vòng quanh


6) Số các hoán vị khác nhau có thể có khi hoán vị các chữ cái trong từ XAXAM


7) Số cách chia 7 chiếc kẹo cho 4 trẻ em là
avatar
Admin
Admin

Tổng số bài gửi : 2046
Points : 3620
Reputation : 0
Join date : 25/10/2009
Đến từ : http://casablanca.top-forum.net

Xem lý lịch thành viên http://casablanca.top-forum.net

Về Đầu Trang Go down

Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết