Đếm số số hạng có hệ số lẻ trong khai triển nhị thức Newton trong toán học?

[xuho95 (Xuân Hòa)]

Chào mọi người, hiện tại em đang học môn toán rời rạc và có gặp một bài toán sau:
Cho 1 con vi khuẩn, cứ sau 1 đơn vị thời gian con vi khuẩn này sẽ phân bào ra 2 bên trái phải và cứ thế phân bào, nhưng nếu lúc phân bào mà gặp nhau thì sẽ triệt tiêu nhau, vậy sau n đơn vị thời gian sẽ có bao nhiêu con vi khuẩn?
Bài toán này em đã suy nghĩ và nhận thấy quy luật của nó giống với quy luật của tam giác Pascal.
Em đã nháp hình vẽ ra giấy như sau:

Trong đó nếu cứ số lẻ thì sẽ có vi khuẩn sinh ra, còn chẵn là triệt tiêu.
Cái này đưa vào code em đã code xong rồi nhưng vẫn chưa tìm ra được công thức tổng quát để tính được số vi trùng này, theo em nếu tổng quát thì sẽ là 1 công thức đếm số số hạng lẻ trong khai triển (a + b) ^ n
Mọi người gọi ý dùm em ạ, em cám ơn.

[tntxtnt]

ta tính thử thì thấy nó là 2^(số bit 1 của n)

ví dụ n = 7 tức là 111 thì có 3 bit 1, nên có 8 số hạng là số lẻ
n = 5 tức là 101 => 2^2 = 4
n = 21 tức là 10101 => 2^3 = 8

thử thế vô cái code kia coi đúng hết với mọi n ko?

[tntxtnt]

công thức tổ hợp n chập k là n! chia cho (n-k)! * k!

để n chập k lẻ thì phân tích n! ra thành 2^b * …, hay 2^b trên tử số (n!) phải bằng đúng 2^b dưới mẫu số ((n-k)! * k!)

để tìm số mũ b trên trong n! thì có cách đơn giản nhất là lấy n/2 + n/4 + … tới khi nào phần dư n/i là 0 thì dừng. Ví dụ n=14 thì số mũ b là 14/2 + 14/4 + 14/8 = 7 + 3 + 1 = 11. Hay 14! = 2¹¹ * …

chuyển n về dạng nhị phân, vì mỗi lần chia 2 là dịch phải 1 bit, nên chuyển về thấy dễ hơn:
ví dụ n=14 tức là 1110, thì ta thấy mỗi lần chia 2 thì số 1 ngoài cùng bên trái dịch sang bên phải 1 bit, 3 lần chia thì cộng được số 111, số 1 tiếp theo là cộng được 11, số 1 cuối cùng là được 1, như vậy b = 111 + 11 + 1 = 7 + 3 + 1 = 11. Để ra công thức đơn giản hơn thì lấy 1000 - 1 + 100 - 1 + 10 - 1 = 1110 - 3 hay b = n - (số bit 1 của n)

ráp vô:
n! = n - (số bit 1 của n)
(n-k)! = n - k - (số bit 1 của n-k)
k! = k - (số bit 1 của k)
để nó là số lẻ thì ta có:
n - (số bit 1 của n) = n - k - (số bit 1 của n-k) + k - (số bit 1 của k)
hay
số bit 1 của n = (số bit 1 của n-k) + (số bit 1 của k)

tới đây thì ta bí, nhưng mà có trực giác là nếu 1 + 1 thì được 10, như vậy phải 1 + 0 mới bảo toàn tổng số số 1 ở 2 vế được. Như vậy tách n thành 2 số x và y sao cho x + y = n và bit 1 ở x tương ứng với bit 0 ở y và bit 1 ở n, như vậy số bit 1 của n hoặc có, hoặc ko có, còn bit 0 thì ko tính. Như vậy tổng số cặp (x,y) tạo được là 2^{số bit 1 của n}

[xuho95 (Xuân Hòa)]

à code thì em đã code đc rồi, cho nhập số đơn vị thời gian ra số vi trùng phân bào đc thì xong rồi ạ, bây giờ là giải trên phương diện toán học để tìm 2 công thức truy hồi tổng quát đó ạ
cám ơn bác gợi ý ạ, để em đọc kỹ bài của bác ạ.