Javascript bị vô hiệu

Javascript bị vô hiệu, một vài chức năng sẽ không hoạt động. Vui lòng bật lại Javascript để sử dụng đầy đủ các chức năng.

tìm số dãy 10 bit (x1, x2, x3...x10)

Bắt đầu bởi Ngô Văn Trung, 22-10-2012 - 08:42

Please log in to reply

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

#1
Ngô Văn Trung

Đã gửi 22-10-2012 - 08:42

Binh nhì

Thành viên
19 Bài viết

dãy (x1,x2,....,x10) trong đó mỗi giá trị x chỉ nhận giá trị 0 hoặc 1 gọi là dãy nhị phân 10 bit. Có bao nhiêu dãy nhị phân 10 bit mà trong đó có ít nhất 3 kí tự 0 và 3 kí tự 1.

hxthanh yêu thích

#2
hxthanh

Đã gửi 22-10-2012 - 14:03

Tín đồ $\sum$

Hiệp sỹ
3921 Bài viết

Phân tích logic một chút cho bạn dễ hình dung:
$\left|\overline{\text{ít nhất 3 kí tự 0 và 3 kí tự 1}}\right|=\left|\text{Nhiều nhất 2 kí tự 0}\right|+\left|\text{Nhiều nhất 2 kí tự 1}\right|=\left|\text{Đúng 0 kí tự 0}\right|+\left|\text{Đúng 1 kí tự 0}\right|+\left|\text{Đúng 2 kí tự 0}\right|+\left|\text{Đúng 0 kí tự 1}\right|+\left|\text{Đúng 1 kí tự 1}\right|+\left|\text{Đúng 2 kí tự 1}\right|$
Suy ra
$\left|\text{ít nhất 3 kí tự 0 và 3 kí tự 1}\right|=\left|\text{tổng số xâu}\right|-\left|\text{Đúng 0 kí tự 0}\right|-\left|\text{Đúng 1 kí tự 0}\right|-\left|\text{Đúng 2 kí tự 0}\right|-\left|\text{Đúng 0 kí tự 1}\right|-\left|\text{Đúng 1 kí tự 1}\right|-\left|\text{Đúng 2 kí tự 1}\right|$

Ta có: Tổng số xâu nhị phân $10$ bit là $2^{10}=1024$ xâu
Đúng 0 kí tự 0 có: $1$ xâu
Đúng 0 kí tự 1 có: $1$ xâu
Đúng 1 kí tự 0 có: $C_{10}^1=10$ xâu
Đúng 1 kí tự 1 có: $C_{10}^1=10$ xâu
Đúng 2 kí tự 0 có: $C_{10}^2=45$ xâu
Đúng 2 kí tự 1 có: $C_{10}^2=45$ xâu

Vậy số xâu nhị phân $10$ bit có ít nhất 3 kí tự 0 và 3 kí tự 1 là
$1024-1-1-10-10-45-45=912$ xâu

Ngô Văn Trung và Nobodyv3 thích

#3
hxthanh

Đã gửi 22-10-2012 - 19:51

Tín đồ $\sum$

Hiệp sỹ
3921 Bài viết

Cách 2:
Xét các xâu nhị phân độ dài 10

|Có ít nhất 3 vị trí 0 và 3 vị trí 1| = |Có đúng 3 vị trí 0 và 7 vị trí 1|+|Có đúng 4 vị trí 0 và 6 vị trí 1|+|Có đúng 5 vị trí 0 và 5 vị trí 1|+|Có đúng 6 vị trí 0 và 4 vị trí 1|+|Có đúng 7 vị trí 0 và 3 vị trí 1|

Như vậy tổng số xâu thoả mãn là $C_{10}^3+C_{10}^4+C_{10}^5+C_{10}^6+C_{10}^7=120+210+252+210+120=912$ xâu

Nobodyv3 yêu thích

#4
Ngô Văn Trung

Đã gửi 23-10-2012 - 08:44

Binh nhì

Thành viên
19 Bài viết

Phân tích logic một chút cho bạn dễ hình dung:
$\left|\overline{\text{ít nhất 3 kí tự 0 và 3 kí tự 1}}\right|=\left|\text{Nhiều nhất 2 kí tự 0}\right|+\left|\text{Nhiều nhất 2 kí tự 1}\right|=\left|\text{Đúng 0 kí tự 0}\right|+\left|\text{Đúng 1 kí tự 0}\right|+\left|\text{Đúng 2 kí tự 0}\right|+\left|\text{Đúng 0 kí tự 1}\right|+\left|\text{Đúng 1 kí tự 1}\right|+\left|\text{Đúng 2 kí tự 1}\right|$
Suy ra
$\left|\text{ít nhất 3 kí tự 0 và 3 kí tự 1}\right|=\left|\text{tổng số xâu}\right|-\left|\text{Đúng 0 kí tự 0}\right|-\left|\text{Đúng 1 kí tự 0}\right|-\left|\text{Đúng 2 kí tự 0}\right|-\left|\text{Đúng 0 kí tự 1}\right|-\left|\text{Đúng 1 kí tự 1}\right|-\left|\text{Đúng 2 kí tự 1}\right|$

Ta có: Tổng số xâu nhị phân $10$ bit là $2^{10}=1024$ xâu
Đúng 0 kí tự 0 có: $1$ xâu
Đúng 0 kí tự 1 có: $1$ xâu
Đúng 1 kí tự 0 có: $C_{10}^1=10$ xâu
Đúng 1 kí tự 1 có: $C_{10}^1=10$ xâu
Đúng 2 kí tự 0 có: $C_{10}^2=45$ xâu
Đúng 2 kí tự 1 có: $C_{10}^2=45$ xâu

Vậy số xâu nhị phân $10$ bit có ít nhất 3 kí tự 0 và 3 kí tự 1 là
$1024-1-1-10-10-45-45=912$ xâu

Mình đưa bài này lên k phải là vì k giải dc nhưng mình có cách giải như thế này k bik sai chỗ nào nhưng k ra kq là 912 xâu bạn coi giúp mình nhék
ta có 10C3 cách chọn 3 vị trí để điền 3 chữ số 0
sau đó có 7C3 cách chọn 3 vị trí để điền 3 chữ số 1
còn lại 4 vị trí, mỗi vị trí trong 4 vị trí này có 2 cách để điền số có thể điền 0 hoặc điền 1 nên có 2⁴ cách điền
vậy số xâu cần tìm là 10C3 . 7C3 . 2⁴= 67200 xâu kết quả này hình như sai nhưng mình k hiểu tại sao lại sai giúp mình với

#5
hxthanh

Đã gửi 23-10-2012 - 08:51

Tín đồ $\sum$

Hiệp sỹ
3921 Bài viết

Bạn sai là bởi vì vi phạm quy tắc nhân: "các hành động chọn phải độc lập với nhau"

Ở hành động thứ nhất bạn "chọn vị trí để viết số 0"
độc lập với
Hành động thứ hai bạn "chọn vị trí để viết số 1"
Nếu muốn hành động thứ 3 độc lập với 2 hành động trên thì
Hành động thứ ba bạn phải "chọn vị trí để viết số khác 0 và khác 1"

Tất nhiên điều này là không thể !!!

Nobodyv3 yêu thích

#6
Ngô Văn Trung

Đã gửi 23-10-2012 - 11:14

Binh nhì

Thành viên
19 Bài viết

thật là khó hiểu ghê!!! Tự nhiên mình sai bài ni hix hix. Cảm ơn bạn nhiều nha!!

#7
Nobodyv3

Đã gửi 17-01-2023 - 09:27

Generating Functions Faithful

Thành viên
940 Bài viết

Đếm như vậy thì bạn đếm bị trùng rất nhiều.
=======
Cách 3:
Số các dãy có nhiều nhất 2 bit 0 (và cũng là số các dãy có nhiều nhất 2 bit 1):
$\binom {10}{0}+\binom {10}{1}+\binom {10}{2}=56$
Vì tập hợp của 2 loại dãy này rời nhau nên số các dãy thỏa yêu cầu là:
$1024-2\cdot56=912$

Cách 4: dùng hàm sinh.
Vì các dãy nhị phân có ít nhất 3 kí tự 0 và 3 kí tự 1 nên ta có hàm sinh:
$f(x)=\left (e^x-1-x-\frac{x^2}{2!} \right )^2=...+\frac {420x^9}{9!}+\frac {912x^{10}}{10!}+\frac {1914x^{11}}{11!}+...$
Số cách viết các dãy nhị phân thỏa yêu cầu là:
$10![x^{10}]f(x)=912$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 17-01-2023 - 11:24

hxthanh và DOTOANNANG thích

===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

Trở lại Tổ hợp - Xác suất và thống kê - Số phức

1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh

Community Forum Software by IP.Board
Licensed to: Diễn đàn Toán học

tìm số dãy 10 bit (x1, x2, x3...x10)

#1 Ngô Văn Trung Đã gửi 22-10-2012 - 08:42

#2 hxthanh Đã gửi 22-10-2012 - 14:03

#3 hxthanh Đã gửi 22-10-2012 - 19:51

#4 Ngô Văn Trung Đã gửi 23-10-2012 - 08:44

#5 hxthanh Đã gửi 23-10-2012 - 08:51

#6 Ngô Văn Trung Đã gửi 23-10-2012 - 11:14

#7 Nobodyv3 Đã gửi 17-01-2023 - 09:27

1 người đang xem chủ đề

Đăng nhập

#1
Ngô Văn Trung

Đã gửi 22-10-2012 - 08:42

#2
hxthanh

Đã gửi 22-10-2012 - 14:03

#3
hxthanh

Đã gửi 22-10-2012 - 19:51

#4
Ngô Văn Trung

Đã gửi 23-10-2012 - 08:44

#5
hxthanh

Đã gửi 23-10-2012 - 08:51

#6
Ngô Văn Trung

Đã gửi 23-10-2012 - 11:14

#7
Nobodyv3

Đã gửi 17-01-2023 - 09:27