các bác cứu em với

các bác cứu em với

siêu 4` các bác ạ, em ngồi 4 tiếng chiều nay không làm ra, bực mình quá. các bác chỉ giúp em với nhé. em post bài bằng tiếng Anh, nếu có chỗ nào các bác không hiểu các bác cứ bảo em để em dịch nhé.

Let Ai (A sub i) be any subset of {1,2,3...n} with n being a positive integer.
Find the total sum of all the cardinalities of all the subsets Ai:
Sigma of |Ai|, |Ai| denotes the cardinality of Ai.

Đại khái là nó bắt mình tìm một công thức chung để tính cái tổng trên rồi chứng minh (quy nạp, em nghĩ thế) rằng công thức đấy đúng.

với cả bài này nữa ạ.
there are 10 letters A through J. In how many ways can these lẻtters be arranged so that a letter G is between A and H. (between chứ không phải là in the middle of ạ.)

không fải là tổng của Ck,n*k ạ?

có fải là 10!/3 không ạ?

10 letter A -> J
__ __ __ __ __ __ __ __ __ __
A B C D E F H G I J
10!
ai tie^''p ...
tui nghi la....10!/5! thi pha?i, khong cha''c

híc, đáp số trên là middle of rồi, nếu là between thì sẽ là 2*8! thì fải

Bài này qui nạp cũng được nhưng có cách khác đẹp hơn như thế này:
Số lượng các subsets A_i có cardinality k (k=1,...,n) là C(k,n) (inom{n}{k}). Vậy tổng cần tìm là:
sigma[k=1,n]{k*C(k,n)} (1)
Ta có:
F(x) = sigma[k=0,n]{C(k,n)*x^k} = (x+1)^n.
Lấy đạo hàm (!) hai vế:
F''(x) = sigma[k=1,n]{k*C{k.n}*x^(k-1)} = n*(x+1)^(n-1) (2)
Cho x=1, (2) trở thành
(1) = n*2^(n-1)

Cách này đương nhiên là không xấu, nhưng đẹp thì chưa hẳn, cách này khó nghĩ quá. Chỉ cần dùng cái đơn giản hơn nhiều.
Cái sigma[k=0,n] {k*C(k,n)} thì hiển nhiên là vậy rồi.
Nhận thấy k*C(k,n) = n*C(k-1,n-1) suy ra
sigma[k=0,n] {k*C(k,n)}=n*sigma[k=0,n-1] {C(k,n-1)}=n*2^(n-1)
Còn bài còn lại thì mình không hiểu lắm về cái middle mới cả between, cứ lằng nhằng thế nào ấy

hic, báo cáo các bác, cái bài 1... em ngồi trâu bò, tính ra cái tổng của k = 1 ... k=5 rồi observe thế nào mà rồi cũng nghiệm ra được cái công thức n.2^(n-1)... có điều đến lúc chứng minh thì mãi không chứng minh được... là tại vì em cực kỳ dốt mấy cái permutation với combinations này nên không làm sao mà từ đầu bài để suy ra cái tổng cần tìm là có dạng:
sigma(k=0,n)[k*C(k,n)] như các bác chỉ....
đến bây giờ em vẫn còn chưa hiểu... tại sao nó lại là k*C(k,n) ạ?
cách của bác altus thì em hiểu ra rồi, nhưng lớp em đang học là non-calculus thành ra dùng đạo hàm vào không được ổn lắm.
các của bác nhtdhbk thì em có mấy cái chưa hiểu, bác chỉ giúp em với được không ạ?
thứ 1: k*C(k,n) = n*C(k-1,n-1)
tại sao lại thế ạ?
k*C(k,n) = k* [k(k-1)...(k-n+1)] / n! <-- em chỉ tính được đến thế này
từ trên để suy ra n*C(k-1,n-1) thì em chịu
sigma[k=0,n] {k*C(k,n)}=n*sigma[k=0,n-1] {C(k,n-1)}=n*2^(n-1) <-- rồi cái này em cũng không hiểu luôn ạ

bài thứ 2, sau khi được thằng bạn chỉ dẫn, em hơi hơi có tí ý tưởng, các bác thử duyệt giúp em xem thế này có đúng không ạ.
từ A --> J có 10 lettters. để G nằm giữa A và H, G chỉ có thể nằm từ vị trí 2 đến vị trí 9.
Nếu G ở vị trí 2 --> A hoặc H phải ở vị trí một, có 2 lựa chọn cho vị trí này và 8! lựa chọn cho các vị trí sau G --> 2.8! cách sắp xếp.
Nếu G ở vị trí 3 --> hoặc A hoặc H phải nằm tại 1 hoặc 2 --> có 2x2=4 cách sắp xếp. Nếu A rơi vào 1 hoặc 2 --> vị trí còn lại không thể có H (cũng đúng nếu thay A bằng H) --> ở vị trí nằm trước G còn lại, có
10 -1 (A hoặc H) - 1(A hoặc H) - 1(G) = 7 cách sắp xếp.
sau G còn lại 7! cách sắp xếp.
---> nếu G ở vị trí 3: có 2*7*7! cách sắp xếp
cứ làm như vậy cho tới khi G dừng lại ở vị trí 9 rồi cộng tổng lại. em vẫn chưa tính ra xem nó thế nào nhưng đấy là cách em định làm, các bác xem hộ xem có hợp lý không ạ?