Chương 4: Đếm các phần tử

Thảo luận những vấn đề liên quan đến Phép đếm !

Tỷ lệ trúng Vietlott: Chơi Vietlott có dễ trúng vậy không?
Công thức sẽ là: f!/(p!*(f-p)!). Với trường hợp của Vietlott, kết quả này sẽ là 45!/(6!*(45-6)!).

Cuối cùng, chúng ta sẽ có tổng cộng 8.145.060 kết quả.

Như vậy, để là người trúng giải thưởng của Vietlott, tỷ lệ của mỗi bộ số trong tấm vé số mà người chơi đã mua sẽ là 1/8.145.060. Điều này cũng đồng nghĩa mỗi người sẽ chỉ có 0.00001227738% cơ hội chiến thắng. Con số này rõ ràng là vô cùng nhỏ.

Nói như vậy để chúng ta có thể thấy được rằng phải vô cùng… vô cùng… vô cùng may mắn thì chúng ta mới có thể trở thành chủ nhân giải thưởng hàng chục tỷ đồng của Vietlott.

Ví dụ 14: Có bao nhiêu xâu nhị phân có chiều dài 4 bit mà không có hai bit 1 liên tiếp ?

Bước 1: Xác định số xâu nhị phân có thể có với chiều dài 4 bit.

  Ta có: Với 1 bit ta có hai lựa chọn là 1 và 0, vậy với 4 bit, ta áp dụng quy tắc nhân:
2 x 2 x 2 x 2 = 2^4 = 16 (xâu)

Bước 2: Vẽ Biểu đồ cây:
    (Mẹo: Chấm 16 điểm thẳng hàng trước rồi nối 2 điểm gần nhau để tạo thành 1 điểm và tiếp tục nối cho đến khi chỉ còn 1 điểm thì Biểu đồ cây sẽ đẹp và đều hơn)



Bước 3: Bỏ những xâu có hai bit 1 liền kề và xuất kết quả là những sâu bit còn lại.



Kết quả: Có 8 xâu bit có chiều dài 4 bit mà không có xâu nào có hai bit 1 liền kề.