Bài giảng Nhập môn lý thuyết tổng hợp: Chương 2

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

ÑH KHTN, Tp HCM

Nguyeãn Anh Thi

2017

1 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Chöông 2 TOÅ HÔÏP TÍNH TOAÙN

2017

2 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Noäi dung

Noäi dung 1 Caùc baøi toaùn ñeám Caùc nguyeân lyù Giaûi tích toå hôïp Hoaùn vò laëp, toå hôïp laëp

2 Ñònh lyù nhò thöùc 3 Phaân hoaïch

Phaân hoaïch taäp hôïp Phaân hoaïch soá nguyeân

4 Chu trình trong hoaùn vò 5 Nguyeân lyù buø tröø 6 Haøm sinh

2017

3 / 99

Ñònh nghóa haøm sinh Heä soá haøm sinh Phaân hoaïch Haøm sinh muõ Phöông phaùp toång Baøi toaùn ñeä quy Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Caùc baøi toaùn ñeám

Caùc nguyeân lyù

Nguyeân lyù coäng: Giaû söû ñeå laøm coâng vieäc A ta coù theå choïn moät trong hai bieän phaùp khaùc nhau (theo nghóa laø caùch thöïc hieän bieän phaùp thöù nhaát luoân luoân khaùc caùch thöïc hieän bieän phaùp thöù hai). Neáu bieän phaùp thöù nhaát coù m caùch, bieän phaùp thöù hai coù n caùch, thì ta coù soá caùch laøm coâng vieäc A laø m + n. Toång quaùt, giaû söû ñeå laøm coâng vieäc A ta coù theå choïn moät trong k bieän phaùp khaùc nhau, moãi bieän phaùp coù mi caùch laøm vôùi i = 1, 2, . . . , k, khi ñoù soá caùch laøm coâng vieäc A laø m1 + m2 + · · · + mk.

Ví duï

Ta choïn moät vieân bi baát kyø töø hai hoäp A vaø B. Bieát raèng hoäp A chöùa 5 vieân bi maøu ñoû, hoäp B chöùa 3 vieân bi maøu xanh. Vaäy soá caùch choïn laø 5 + 3 = 8.

2017

4 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Caùc baøi toaùn ñeám

Caùc nguyeân lyù

Nguyeân lyù nhaân: Giaû söû chuùng ta phaûi thöïc hieän moät coâng vieäc bao goàm hai coâng vieäc keá tieáp nhau. Ñeå thöïc hieän coâng vieäc thöù nhaát chung ta coù m caùch, vaø öùng vôùi moãi caùch choïn thöïc hieän coâng vieäc thöù nhaát ta coù n caùch thöïc hieän coâng vieäc thöù hai.Vaäy ta coù soá caùch thöïc hieän coâng vieäc ñoù laø m.n. Toång quaùt, Giaû söû moät coâng vieäc bao goàm k böôùc keá tieáp nhau, neáu moãi böôùc ta coù ni caùch laøm vôùi i = 1, 2, . . . , k. Vaäy ta coù n1.n2. . . . .nk caùch ñeå thöïc hieän coâng vieäc.

Ví duï

Ta choïn hai vieân bi maøu khaùc nhau töø hai hoäp A vaø B. Bieát raèng hoäp A chöùa 5 vieân bi maøu ñoû, hoäp B chöùa 3 vieân bi maøu xanh. Vaäy soá caùch choïn laø 5.3 = 15.

2017

5 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Caùc baøi toaùn ñeám

Giaûi tích toå hôïp

Ñònh nghóa

Cho taäp hôïp A coù n phaàn töû. Moãi caùch saép ñaët coù thöù töï n phaàn töû cuûa A ñöôïc goïi laø moät hoaùn vò coù n phaàn töû. Soá caùc hoaùn vò cuûa n phaàn töû kyù hieäu laø Pn, vaø Pn = n! = n.(n − 1).(n − 2)...2.1, quy öôùc 0! = 1.

Ví duï

Cho X laø taäp hôïp coù n phaàn töû thì soá song aùnh töø X vaøo X laø n! Cho A = {a, b, c}. Khi ñoù A coù caùc hoaùn vò sau: abc, acb, bac, bca, cab, cba. Cho X = {1, 2, 3, 4, 5}, hoûi coù bao nhieâu soá töï nhieân goàm 5 chöõ soá khaùc nhau ñöôïc taïo thaønh töø taäp X?

2017

6 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Caùc baøi toaùn ñeám

Giaûi tích toå hôïp

Ñònh nghóa

n. Ta coù coâng thöùc Ak

n = n!

(n−k)!

Cho A laø taäp hôïp goàm n phaàn töû. Moãi boä goàm k phaàn töû (1 ≤ k ≤ n) saép thöù töï cuûa taäp hôïp A ñöôïc goïi laø moät chænh hôïp chaäp k cuûa n phaàn töû. Soá caùc chænh hôïp chaäp k cuûa n, kyù hieäu laø Ak

Ví duï

Cho X = {a, b, c}. Khi ñoù X coù caùc chænh hôïp chaäp 2 cuûa caùc phaàn töû cuûa X laø: ab, ac, bc, ba, ca, cb.

Ví duï

Coù bao nhieâu soá töï nhieân goàm 3 chöõ soá khaùc nhau ñöôïc taïo thaønh töø {1, 2, 3, 4, 5, 6} ?

2017

7 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Caùc baøi toaùn ñeám

Giaûi tích toå hôïp

Ñònh nghóa

n hay

Cho taäp hôïp A goàm n phaàn töû. Moãi taäp con goàm k phaàn töû cuûa A ñöôïc goïi laø moät toå hôïp chaäp k cuûa n phaàn töû. Soá caùc toå hôïp chaäp k cuûa n phaàn töû (cid:19) . Ta coù coâng thöùc ñöôïc kyù hieäu laø Ck (cid:18)n k

n =

Ck n! k!(n − k)!

Tính chaát

n+1

Cn−k n = Ck n n + Ck−1 n = Ck Ck

2017

8 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Caùc baøi toaùn ñeám

Giaûi tích toå hôïp

Ví duï

Cho X = {1, 2, 3, 4}. Toå hôïp chaäp 3 cuûa 4 phaàn töû cuûa X laø {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}

Ví duï

Moät lôùp coù 30 hoïc sinh, hoûi coù bao nhieâu caùch choïn 10 baïn. Soá caùch choïn laø toå hôïp chaäp 10 cuûa 30: C10 30.

2017

9 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Caùc baøi toaùn ñeám

Hoaùn vò laëp, toå hôïp laëp

Ñònh nghóa

Cho n ñoái töôïng trong ñoù coù ni ñoái töôïng loaïi i gioáng heät nhau (i = 1, 2, . . . , k; n1 + n2 + · · · + nk = n). Moãi caùch saép xeáp coù thöù töï n ñoái töôïng ñaõ cho goïi laø moät hoaùn vò laëp cuûa n.

Soá hoaùn vò cuûa n ñoái töôïng, trong ñoù coù n1 ñoái töôïng gioáng nhau thuoäc loaïi 1, n2 ñoái töôïng gioáng nhau thuoäc loaïi 2,. . . , nk ñoái töôïng gioáng nhau thuoäc loaïi k, laø

n! n1!n2! . . . nk!

2017

10 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Caùc baøi toaùn ñeám

Hoaùn vò laëp, toå hôïp laëp

Ví duï

Coù bao nhieâu chuoãi kyù töï khaùc nhau baèng caùch saép xeáp caùc chöõ caùi cuûa töø SUCCESS?

Trong töø SUCCESS coù 3 chöõ S, 1 chöõ U, 2 chöõ C, vaø 1 chöõ E. Do ñoù soá chuoãi coù ñöôïc laø

= 420 7! 3!1!2!1!

2017

11 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Caùc baøi toaùn ñeám

Hoaùn vò laëp, toå hôïp laëp

Ñònh nghóa

n = Ck Kk

n+k−1

Moãi caùch choïn ra k vaät töø n loaïi vaät khaùc nhau (trong ñoù moãi loaïi vaät coù theå ñöôïc choïn laïi nhieàu laàn) ñöôïc goïi laø toå hôïp laëp chaäp k cuûa n. Soá caùc toå hôïp laëp chaäp k cuûa n ñöôïc kyù hieäu laø Kk n.

Ví duï

3 = C2

4 = 6.

3+2−1 = C2

Coù 3 loaïi noùn A, B, C. An mua 2 caùi noùn. Hoûi An coù bao nhieâu caùch choïn? Moãi caùch choïn laø moät toå hôïp laëp chaäp 2 cuûa 3. Cuï theå AA, AB, BB, BC, CC, AC, K2

2017

12 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Ñònh lyù nhò thöùc

Ñònh lyù

Vôùi moïi soá nguyeân döông n, ta coù

n X

k=0

(cid:19) (x + y)n = xkyn−k. (cid:18) n k

Chöùng minh. Ta thaáy (x + y)n = (x + y)(x + y) · · · (x + y). Sau khi nhaân laïi vôùi nhau ta ñöôïc moät toång maø caùc soá haïng coù daïng xkyn−k, vôùi (cid:19) . Ta ñöôïc ñieàu 0 ≤ k ≤ n. Soá löôïng caùc phaàn töû coù daïng xkyn−k laø (cid:18) n k caàn chöùng minh.

2017

13 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Ñònh lyù nhò thöùc

Heä quaû (cid:19) Vôùi moïi soá nguyeân döông n, toång ñan daáu cuûa caùc heä soá nhò thöùc (cid:18) n k baèng 0. Hay noùi caùch khaùc

n X

k=0

(cid:19) (−1)n = 0 (cid:18) n k

Chöùng minh. AÙp duïng ñònh lyù treân cho tröôøng hôïp x = −1, y = 1.

2017

14 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Ñònh lyù nhò thöùc

Heä quaû

Chöùng minh raèng vôùi moïi soá töï nhieân n vaø k ta coù

(cid:19) (cid:19) (cid:19) (cid:18) n + = (cid:18) n k k + 1 (cid:18) n + 1 k + 1

Chöùng minh. Ta thaáy veá phaûi laø soá taäp con k + 1 phaàn töû cuûa taäp [n + 1]. Goïi S laø moät taäp con k + 1 phaàn töû cuûa [n + 1], thì S coù theå chöùa n + 1 hay khoâng chöùa n + 1. Neáu S chöùa n + 1 thì phaàn coøn laïi cuûa taäp S chính laø taäp con k phaàn töû cuûa [n]. Neáu S khoâng chöùa n + 1 thì S laø taäp con k + 1 phaàn töû cuûa taäp [n]. Ta ñöôïc ñieàu caàn chöùng minh.

2017

15 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Ñònh lyù nhò thöùc

Heä quaû

Chöùng minh raèng vôùi moïi soá töï nhieân n ta coù

n X

k=0

(cid:19) 2n = (cid:18) n k

Chöùng minh. AÙp duïng ñònh lyù nhò thöùc vôùi x = 1 vaø y = 1.

2017

16 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Ñònh lyù nhò thöùc

Heä quaû

Vôùi moïi soá töï nhieân n vaø k, ta coù

(cid:19) (cid:19) (cid:19) (cid:19) (cid:19) + + + · · · + . = (cid:18) k k (cid:18) k + 1 k (cid:18) k + 2 k (cid:18) n k (cid:18) n + 1 k + 1

Chöùng minh. Ta thaáy veá phaûi laø soá taäp con k + 1 phaàn töû cuûa taäp [n + 1]. Goïi S laø moät taäp con k + 1 phaàn töû cuûa [n + 1]. Neáu S coù phaàn töû lôùn nhaát laø k + 1, thì phaàn coøn laïi chính laø taäp con k phaàn töû cuûa [k]. Soá caùc taäp S (cid:19) (cid:19) nhö vaäy baèng . Töông töï ta cuõng tính ñöôïc soá taäp con S (cid:18) k + 1 k (cid:18) k k

coù k + 1 phaàn töû cuûa [n + 1], caø coù phaàn töû lôùn nhaát laø k + 2. Toång quaùt, (cid:19) ta seõ coù taäp con k + 1 phaàn töû maø coù phaàn töû lôùn nhaát laø (cid:18) k + i k k + i + 1. Ta ñöôïc ñieàu caàn chöùng minh.

2017

17 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Ñònh lyù nhò thöùc

Heä quaû

Vôùi moïi soá nguyeân döông n, ta coù

n X

k=1

(cid:19) k = n2n−1. (cid:18) n k

Chöùng minh. Theo ñònh lyù nhò thöùc ta coù

n X

k=1

(cid:19) xk (x + 1)n = (cid:18) n k

Laáy ñaïo haøm hai veá theo x ta ñöôïc

n X

k=1

(cid:19) xk−1 n(x + 1)n−1 = k (cid:18) n k

Thay x = 1, ta ñöôïc ñieàu caàn chöùng minh.

2017

18 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Ñònh lyù nhò thöùc

Ñònh lyù (Môû roäng ñònh lyù nhò thöùc)

Vôùi moïi soá nguyeân döông n vaø k, ta coù

2 . . . xak k .

a1+a2+···+ak=n

i=1 ai, ta

X (x1 + x2 + · · · + xk)n = xa1 1 xa2 n! a1!a2! . . . ak!

Ñònh lyù Vôùi moïi soá nguyeân khoâng aâm n vaø a1, a2, . . . , ak sao cho n = Pk coù ñaúng thöùc sau (cid:18) (cid:19)

n a1, a2, . . . , ak

(cid:19) (cid:19) (cid:19) = . . . . . . (cid:18) n a1 (cid:18) n − a1 − · · · − ai ai+1 (cid:18) n − a1 − · · · − ak−1 ak

2017

19 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Ñònh lyù nhò thöùc

Ñònh nghóa (cid:19) = 1, vaø Cho soá thöïc m, vaø k laø moät soá nguyeân khoâng aâm. Ta coù (cid:18) m 0

(cid:19) = , neáu k ≥ 0. (cid:18) m k m(m − 1) . . . (m − k + 1) k!

Ñònh lyù

Cho m laø moät soá thöïc. Khi ñoù

n≥0

(cid:19) X (1 + x)m = xn (cid:18) m n

vôùi toång ñöôïc laáy treân taát caû caùc soá nguyeân khoâng aâm n.

Ví duï √ Vieát khai trieån luõy thöøa cuûa 1 − 4x.

2017

20 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Phaân hoaïch

Phaân hoaïch taäp hôïp

Caáu thaønh

Ñònh nghóa

Daõy caùc soá nguyeân (a1, a2, . . . , ak) vôùi ai ≥ 0 vôùi moïi i, vaø a1 + a2 + · · · + ak = n ñöôïc goïi laø moät caáu thaønh yeáu cuûa n. Neáu trong tröôøng hôïp ai laø caùc soá nguyeân döông vôùi moïi i ∈ [k], thì daõy (a1, a2, . . . , ak) ñöôïc goïi laø moät caáu thaønh cuûa n.

Ví duï

Caùc sinh vieân töï cho ví duï.

Ñònh lyù

Vôùi moïi soá nguyeân döông n vaø k, soá caùc caáu thaønh yeáu cuûa n thaønh k phaàn laø (cid:19) (cid:19) = (cid:18) n + k − 1 k − 1 (cid:18) n + k − 1 n

2017

21 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Phaân hoaïch

Phaân hoaïch taäp hôïp

Heä quaû

(cid:19) . Vôùi moïi soá nguyeân döông n vaø k, soá caùc caáu thaønh cuûa n thaønh k phaàn laø (cid:18) n − 1 k − 1

Heä quaû Vôùi moïi soá nguyeân döông n, soá taát caû caùc caáu thaønh cuûa n laø 2n−1

n X

k=1

Chöùng minh. (cid:19) = 2n−1. (cid:18) n − 1 k − 1

2017

22 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Phaân hoaïch

Phaân hoaïch taäp hôïp

Ñònh nghóa

Soá caùc phaân hoaïch cuûa [n] thaønh k phaàn khaùc roãng ñöôïc kyù hieäu laø S(n, k), vaø soá S(n, k) ñöôïc goïi laø soá Stirling daïng thöù hai.

Ví duï

Vôùi moïi soá nguyeân döông n ≥ 1, ta coù S(n, 1) = S(n, n) = 1. Vôùi moïi (cid:19) . n ≥ 2, ta coù ñaúng thöùc S(n, n − 1) = (cid:18) n 2

Ví duï

S(4, 2) =? Lieät keâ taát caû caùc phaân hoaïch ñoù.

2017

23 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Phaân hoaïch

Phaân hoaïch taäp hôïp

Ñònh lyù

Vôùi moïi soá nguyeân döông k ≤ n, ta coù

S(n, k) = S(n − 1, k − 1) + k.S(n − 1, k).

Chöùng minh. Sinh vieân töï chöùng minh nhö baøi taäp.

Heä quaû

Soá caùc toaøn aùnh f : [n] → [k] laø k!S(n, k).

Sinh vieân chöùng minh nhö baøi taäp

Heä quaû

Vôùi moïi soá thöïc x, vaø taát caû caùc soá nguyeân khoâng aâm n, xn = Pn k=0 S(n, k)(x)k vôùi (x)k = x(x − 1) · · · (n − k + 1).

2017

24 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Phaân hoaïch

Phaân hoaïch taäp hôïp

Ñònh nghóa

Soá taát caû caùc phaân hoaïch cuûa [n] thaønh caùc phaàn khaùc roãng ñöôïc kyù hieäu laø B(n), vaø ñöôïc goïi laø soá Bell thöù n. Ta thaáy B(0) = 1, vaø B(n) = Pn i=0.

i=0 S(n, i).

Deã daøng ta thaáy ñöôïc B(n) = Pn

Ñònh lyù

Vôùi moïi soá nguyeân döông khoâng aâm n,

n X

i=0

(cid:19) B(n + 1) = B(i) (cid:18) n i

2017

25 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Phaân hoaïch soá nguyeân

Phaân hoaïch

Phaân hoaïch soá nguyeân

Ñònh nghóa

Goïi caùc soá nguyeân a1 ≥ a2 ≥ · · · ≥ ak ≥ 1 laø caùc soá nguyeân sao cho a1 + a2 + · · · + ak = n. Khi ñoù daõy (a1, a2, . . . , ak) ñöôïc goïi laø moät phaân hoaïch cuûa soá nguyeân n. Soá taát caû caùc phaân hoaïch cuûa n ñöôïc kyù hieäu bôûi p(n). Soá caùc phaân hoaïch cuûa n ra thaønh k phaàn ñöôïc kyù hieäu bôûi pk(n)

Ví duï

Vieát ra taát caû caùc phaân hoaïch soá nguyeân cuûa 5.

2017

26 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Phaân hoaïch soá nguyeân

Phaân hoaïch

Phaân hoaïch soá nguyeân

Ñònh nghóa

Moät hình maãu Ferrers cuûa moät phaân hoaïch caùc soá nguyeân p = (x1, x2, . . . , xk) laø taäp hôïp taát caû n hình vuoâng vôùi chieàu ngang vaø chieàu doïc sao cho ôû doøng thöù i, ta coù xi oâ vuoâng, vaø taát caû caùc doøng ñeàu baét ñaàu töø cuøng moät coät.

Ví duï

Hình maãu Ferrers cuûa phaân hoaïch p = (4, 2, 1).

2017

27 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Phaân hoaïch soá nguyeân

Phaân hoaïch

Ñònh nghóa

Khi ta laáy ñoái xöùng hình maãu Ferrers cuûa moät phaân hoaïch p qua ñöôøng cheùo chính, ta ñöôïc moät hình maãu khaùc. Hình maãu ñoù ñöôïc goïi laø phaân hoaïch lieân hôïp cuûa p.

Ví duï

Tìm phaân hoaïch lieân hôïp cuûa phaân hoaïch p trong ví duï treân.

Ñònh nghóa

Moät phaân hoaïch ñöôïc goïi laø töï lieân hôïp neáu noù baèng vôùi chính lieân hôïp cuûa noù.

Ví duï

Caùc phaân hoaïch (4, 3, 2, 1), (5, 1, 1, 1, 1), vaø (4, 2, 1, 1) laø töï lieân hôïp.

2017

28 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Phaân hoaïch soá nguyeân

Phaân hoaïch

Ñònh lyù

Soá caùc phaân hoaïch cuûa n thaønh nhieàu nhaát k phaàn baèng vôùi soá caùc phaân hoaïch cuûa n thaønh caùc phaàn maø khoâng lôùn hôn k.

Chöùng minh. Ta thaáy Soá caùc phaân hoaïch cuûa n thaønh k phaàn baèng soá caùc hình maãu Ferrer vôùi nhieàu nhaát k doøng. Hôn nöõa, soá caùc phaân hoaïch cuûa n thaønh caùc phaàn maø khoâng lôùn hôn k thì baèng vôùi soá hình maãu Ferrer vôùi nhieàu nhaát laø k coät. Ta chæ caàn laáy lieân hôïp hai loaïi hình maãu Ferrer treân laø ñöôïc keát quaû.

2017

29 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Phaân hoaïch soá nguyeân

Phaân hoaïch

Ñònh lyù

Soá caùc phaân hoaïch cuûa n thaønh nhöõng phaàn leû rôøi nhau thì baèng vôùi soá caùc phaân hoaïch töï lieân hôïp cuûa n.

Chöùng minh. Ta ñònh nghóa moät song aùnh f töø taäp caùc phaân hoaïch töï lieân hôïp cuûa n vaøo taäp caùc phaân hoaïch cuûa n thaønh caùc phaàn leû rôøi nhau. Choïn π = (π1, π2, . . . , πt) laø moät phaân hoaïch töï lieân hôïp cuûa n. Töø ñoù ta coù ñöôïc hình maãu Ferrers cuûa noù. Ta boû heát caùc oâ vuoâng ôû hình doøng ñaàu tieân vaø coät ñaàu tieân cuûa hình maãu. Bôûi vì π laø phaân hoaïch töï lieân hôïp neân soá oâ vuoâng bò boû ñi laø 2π1 − 1. Ñaët f(π)1 = 2π1 − 1, nghóa laø phaàn ñaàu tieân cuûa aûnh cuûa f(π) laø 2π1 − 1..., töông töï, f(π)2 = 2π2 − 3...Tieáp tuïc laøm nhö vaäy ta ñöôïc

f(π) = (2π1 − 1, 2π2 − 3, . . . , 2πi − (2i − 1), . . . )

laø moät phaân hoaïch coù caùc phaàn leû rôøi nhau, (do π1 ≥ π2 ≥ · · · ≥ πt)

2017

30 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Phaân hoaïch soá nguyeân

Phaân hoaïch

Ngöôïc laïi, goïi α laø moät phaân hoaïch cuûa n thaønh caùc phaàn leû rôøi nhau, α = (2a1 − 1, 2a2 − 3, . . . , 2au − (2u − 1)). Goïi π laø moät phaân hoaïch sao cho π = (a1, a2, . . . , au). Khi ñoù, f(π) = α.

Ví duï

Neáu π = (6, 6, 4, 3, 2, 2), thì f(π) = (11, 9, 3)

2017

31 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Phaân hoaïch soá nguyeân

Phaân hoaïch

Moái lieân heä giöõa soá caùc phaân hoaïch soá nguyeân cuûa n vaø soá caùc phaân hoaïch cuûa taäp [n]

Goïi π = (π1, π2, . . . , πk) laø moät phaân hoaïch cuûa taäp [n], vôùi πi laø caùc 'block' cuûa π. Ta saép xeáp caùc block treân theo kích côõ (|π1|, |π2|, . . . , |πk|) khoâng taêng ñeå nhaän ñöôïc moät daõy a1 ≥ a2 ≥ · · · ≥ ak. Khi ñoù a = (a1, a2, . . . , ak) laø moät phaân hoaïch caùc soá nguyeân cuûa n. Ta noùi a laø loaïi cuûa phaân hoaïch π.

Ví duï

Tìm loaïi cuûa phaân hoaïch {1, 5, 6}, {2, 7}, {3, 9}, {4, 8}, {10}?

2017

32 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Phaân hoaïch soá nguyeân

Phaân hoaïch

Moái lieân heä giöõa soá caùc phaân hoaïch soá nguyeân cuûa n vaø soá caùc phaân hoaïch cuûa taäp [n]

Ñònh lyù

Goïi a = (a1, a2, . . . , ak) laø moät phaân hoaïch cuûa soá nguyeân n, goïi mi laø soá boäi cuûa i trong phaân hoaïch a. Khi ñoù, soá caùc phaân hoaïch taäp hôïp cuûa [n] coù 'loaïi' a laø (cid:18) (cid:19)

Pa = Q n a1, a2, . . . , ak i≥1 mi!

2017

33 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Phaân hoaïch soá nguyeân

Phaân hoaïch

Baûng toång keát

2017

34 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Phaân hoaïch soá nguyeân

Phaân hoaïch

Baûng toång keát

2017

35 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Chu trình trong hoaùn vò

Boå ñeà

Goïi p : [n] → [n] laø moät hoaùn vò, vaø x ∈ [n]. Khi ñoù toàn taïi moät soá nguyeân döông 1 ≤ i ≤ n sao cho pi(x) = x.

Ñònh nghóa

Goïi p : [n] → [n] laø moät hoaùn vò, x ∈ [n], vaø i laø moät soá nguyeân döông nhoû nhaát sao cho pi(x) = x. Khi ñoù ta noùi x, p(x), p2(x), · · · , pi−1(x) taïo thaønh moät i − chu trình trong p.

Heä quaû

Moïi hoaùn vò ñeàu ñöôïc phaân tích thaønh hoäi caùc chu trình rôøi nhau.

Ví duï

321564 = (31)(2)(564)

2017

36 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Chu trình trong hoaùn vò

Ñònh lyù

i=1 i.ai = n. Khi ñoù soá caùc hoaùn vò ñoä daøi n vôùi ai chu trình coù chieàu daøi

Goïi a1, a2, . . . , an laø caùc soá nguyeân khoâng aâm sao cho ta coù toång Pn

i vôùi i ∈ [n] laø

. n! a1!a2! . . . an!.1a12a2 . . . nan

Chuù yù

Neáu moät hoaùn vò p coù ai chu trình coù ñoä daøi i, vôùi i = 1, 2, . . . , n, thì ta noùi (a1, a2, . . . , an) laø loaïi cuûa p.

Ví duï

Soá caùc hoaùn vò ñoä daøi n coù duy nhaát moät chu trình, hay noùi caùch khaùc, soá caùc hoaùn vò loaïi (0, 0, . . . , 1) baèng (n − 1)!.

2017

37 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Chu trình trong hoaùn vò

Ñònh nghóa

Goïi c(n, k) laø soá caùc hoaùn vò ñoä daøi n vôùi k chu trình, vaø s(n, k) = (−1)n−kc(n, k). Khi ñoù ta goïi s(n, k) laø soá Stirling daïng thöù nhaát, vaø c(n, k) laø soá Stirling khoâng daáu daïng thöù nhaát.

Ñònh lyù

Goïi n vaø k laø caùc soá nguyeân döông thoûa maõn n ≥ k, ta coù

c(n, k) = c(n − 1, k − 1) + (n − 1)c(n − 1, k).

2017

38 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Chu trình trong hoaùn vò

Höôùng daãn. Ta xeùt hai tröôøng hôïp.

n taïo thaønh chu trình bôûi chính noù, vaø n − 1 phaàn töû coøn laïi taïo thaønh k − 1 chu trình. Khi ñoù soá caùc hoaùn vò laø c(n − 1, k − 1). Neáu n khoâng taïo thaønh chu trình bôûi chính noù, thì n − 1 phaàn töû coøn laïi seõ taïo thaønh k chu trình, vaø phaàn töû n seõ ñöôïc theâm vaøo moät chu trình naøo ñoù. Soá caùch taïo ra k chu trình laø c(n − 1, k). Sau ñoù ta theâm n vaøo sau moãi phaàn töû. Soá caùch theâm laø n − 1. Vaäy ta coù taát caû (n − 1)c(n − 1, k) caùch.

Keát hôïp hai tröôøng hôïp treân ta ñöôïc soá caùc hoaùn vò ñoä daøi n coù k chu trình laø c(n, k) = c(n − 1, k − 1) + (n − 1)c(n − 1, k).

2017

39 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Chu trình trong hoaùn vò

Boå ñeà

n X

Cho n laø soá nguyeân döông, ta coù

k=0

k=0 an,kxk. Ta thaáy k=0 an−1,kxk =

c(n, k)xk = x(x + 1) . . . (x + n − 1).

k=1 an−1,k−1xk + (n − 1) Pn−1

k=0 an−1,k. Ta vöøa chöùng minh ñöôïc

n X

n−1 X

Höôùng daãn. Ta chöùng minh raèng heä soá cuûa xk ôû veá phaûi chính laø soá Stirling khoâng daáu daïng thöù nhaát. Goïi Gn(x) = x(x + 1) . . . (x + n − 1) = Pn Gn(x) = (x + n − 1)Gn−1(x) = (n + n − 1) Pn−1 Pn

k=0

k=1

k=0

an,kxk = an−1,k−1xk + (n − 1) an−1,kxk.

Töø ñaây suy ra

an,k = an−1,k−1 + (n − 1)an−1,k.

2017

40 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Chu trình trong hoaùn vò

Ta thaáy c(n, k) vaø an,k coù cuøng heä thöùc ñeä quy, vaø cuøng ñieàu kieän ñaàu c(0, 0) = a0,0 = 1, vaø c(n, 0) = an,0 neáu n > 0, neân ta coù ñöôïc c(n, k) = an,k.

n X

Chuù yù Ta thay x baèng −x trong heä thöùc treân, vaø nhaân caû hai veá cho (−1)n, ta ñöôïc coâng thöùc

k=0

(1) s(n, k)xk = (x)n.

n X

So saùnh vôùi coâng thöùc Stirling daïng thöù hai

k=0

(2). xn = S(n, k)(x)k.

Ta thaáy soá Stirling daïng thöù nhaát gaàn nhö laø 'aûnh ngöôïc' cuûa soá Stirling daïng thöù hai .

2017

41 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Chu trình trong hoaùn vò

Ñeå thaáy ñöôïc tính chaát naøy, ta xem suy luaän sau.

Goïi V laø khoâng gian vectô goàm caùc ña thöùc coù heä soá thöïc. Khi ñoù ta bieát raèng B = {1, x, x2, . . . } laø moät cô sôû cuûa khoâng gian V. Ngoaøi ra, ta cuõng chöùng minh ñöôïc B0 = {1, (x)1, (x)2, (x)3, . . . } cuõng laø moät cô sôû cuûa V. Goïi S laø ma traän maø coù heä soá ôû vò trí (n, k) baèng S(n, k), vaø s laø ma traän maø coù heä soá ôû vò trí (n, k) baèng s(n, k). Khi ñoù s chính laø ma traän ñoåi cô sôû töø B sang B0, vaø S laø ma traän ñoåi cô sôû töø B0 sang B. Roõ raøng ta thaáy S = s−1.

2017

42 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Nguyeân lyù buø tröø

Ñònh lyù (Nguyeân lyù buø tröø)

n X

Goïi A1, A2, . . . , An laø caùc taäp con cuûa taäp A, ta coù

j=1

|A1 ∪ A2 ∪ · · · ∪ An| = |Ai1 ∩ Ai2 ∩ · · · ∩ Aij| (−1)j−1 X i1,i2,...,ij

trong ñoù (i1, i2, . . . , ij) laø caùc taäp con j phaàn töû cuûa [n].

Ví duï

Tìm soá nghieäm nguyeân khoâng aâm cuûa phöông trình

x1 + x2 + x3 + x4 = 18 (∗)

thoûa ñieàu kieän xi ≤ 7, ∀i = 1, . . . , 4.

2017

43 / 99

Ñaùp aùn. 246 Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Nguyeân lyù buø tröø

Ví duï

Coù bao nhieâu caùch laáy 6 laù baøi töø 52 laù sao cho

a. coù ñaày ñuû boán chaát (cô, roâ, chuoàn, bích)?8682544.

b. ít nhaát moät chaát khoâng coù. 11675976.

Ví duï

Tìm soá nghieäm nguyeân khoâng aâm cuûa phöông trình

x1 + x2 + x3 + x4 = 25 (∗)

thoûa ñieàu kieän x1 ≤ 5, x2 ≤ 6, x3 ≤ 7.

Ví duï

Tìm soá nghieäm nguyeân khoâng aâm cuûa phöông trình x1 + x2 + x3 + x4 + x5 + x6 = 20 (∗) thoûa ñieàu kieän xi ≤ 8, (i = 1, 2, . . . , 6).

2017

44 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Nguyeân lyù buø tröø

Ñònh lyù

i=0 (−1)i (cid:19)

(cid:19) Cho taäp vuõ truï U coù N phaàn töû vaø A1, A2, . . . , An laø n taäp con cuûa taäp hôïp U. Khi ñoù soá phaàn töû thuoäc vaøo ñuùng m taäp hôïp, kyù hieäu Nm, laø Nm = Pn−m Sm+i = (cid:18) m + i i (cid:19) Sm − Sm+1 + · · · + (−1)n−m Sn. Vôùi Sk laø toång soá phaàn (cid:18) m + 1 m (cid:18) n m

töû cuûa taát caû taäp giao cuûa ñuùng k taäp hôïp töø caùc taäp {Ai}i=1,2,...,n, cuï theå

i6=j

X X S1 = |Ai|, S2 = |Ai ∩ Aj|, . . . . . . , Sn = |A1 ∩ A2 ∩ · · · ∩ An|.

2017

45 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Nguyeân lyù buø tröø

m laø soá phaàn töû thuoäc ít nhaát m taäp hôïp thì

i=0 (−1)i (cid:19)

(cid:19) Nm+i = (cid:18) m + i m − 1 (cid:19) Heä quaû Neáu ta goïi N∗ m = Pn−m N∗ (cid:18) m Sm − Sn. Sm+1 + · · · + (−1)n−m m − 1 (cid:18) n − 1 m − 1

Ví duï

Coù bao nhieâu chuoãi tam phaân (chæ goàm 0, 1, 2) ñoä daøi 4 thoûa maõn a.chöùa ñuùng 2 chöõ soá 1, b. chöùa nhieàu hôn 2 chöõ soá 1.

2 = 33.

(cid:19) (cid:19) (cid:19) 31, vaø 32, S3 = 33, S2 = Höôùng daãn. Goïi U laø taäp hôïp taát caû caùc chuoãi tam phaân coù ñoä daøi 4. Goïi Ai laø taäp hôïp taát caû caùc chuoãi tam phaân coù chöõ soá taïi vò trí i laø 1. Ta tính (cid:18) 4 ñöôïc N = 34, S1 = 2 (cid:18) 4 3 (cid:18) 4 1 (cid:19) S4 = 30. AÙp duïng ñònh lyù treân ta ñöôïc keát quaû N2 = 24, N∗ (cid:18) 4 4

2017

46 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Nguyeân lyù buø tröø

Ñònh lyù

Vôùi moïi soá nguyeân döông n vaø k, ta coù ñaúng thöùc

k X

i=0

(cid:19) (−1)i (−1)i S(n, k) = (k − i)n (k − i)n = (cid:18) k i 1 k! 1 i!(k − i)!

j=1(−1)j−1 P

i1,i2,...,ij

i=1(−1)i−1

i=0(−1)i

|Ai1 ∩ Ai2 ∩ · · · ∩ Aij| = (cid:19) Chöùng minh. Tröôùc tieân, ta tìm soá toaøn aùnh töø taäp [n] vaøo taäp [k]. Deã daøng thaáy raèng soá caùc aùnh xaï töø [n] vaøo trong [k] laø kn. Vôùi moïi i ∈ [k], goïi Ai laø taäp taát caû caùc aùnh xaï töø [n] vaøo [k] maø taäp aûnh cuûa noù khoâng chöùa i. Ta thaáy soá phaàn töû |Ai| = (k − 1)n.Töông töï ta coù |Ai1 ∩ Ai2 ∩ · · · ∩ Aij| = (k − j)n vôùi moïi j ≤ k. AÙp duïng coâng thöùc nguyeân lyù buø tröø ta ñöôïc, |A1 ∪ A2 ∪ · · · ∪ An| = Pn Pk (cid:18) k i (cid:19) (cid:19) (k − i)n. (k − i)n = Pk kn − Pk (k − i)n. Suy ra soá toaøn aùnh laø (cid:18) k i (cid:18) k i

2017

47 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Nguyeân lyù buø tröø

Hôn nöõa, töø chöông tröôùc ta coù soá toaøn aùnh baèng k!S(n, k). Do ñoù ta ñöôïc

k X

i=0

(cid:19) (−1)i S(n, k) = (k − i)n. (cid:18) k i 1 k!

Ñònh lyù

T⊆S

Goïi f vaø g laø caùc haøm ñöôïc ñònh nghóa treân taäp hôïp [n], vaø f, g thoûa ñieàu kieän X g(S) = f(T).

T⊆S

Khi ñoù X f(S) = g(T)(−1)|S−T|

2017

48 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Ñònh nghóa haøm sinh

n≥0 anxn ñöôïc goïi laø haøm sinh thoâng thöôøng (hay haøm sinh) cuûa

Ñònh nghóa

Cho {an}n≥0 laø moät daõy caùc soá thöïc, thì chuoãi luõy thöøa hình thöùc A(x) = P daõy {an}n≥0.

Ví duï

Xeùt taäp hôïp X vôùi m phaàn töû, goïi an laø soá taäp con coù n phaàn töû cuûa X, (cid:19) . an = (cid:18) m n

Ta ñöôïc haøm sinh cuûa daõy soá thöïc {an}n≥0 laø

(cid:19) (cid:19) (cid:19) x2 + · · · + · · · + xm = (1 + x)m A(x) = 1 + x + (cid:18) m 1 (cid:18) m 2 (cid:18) m m

2017

49 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Ñònh nghóa haøm sinh

Ví duï

Tìm haøm sinh cuûa ar, vôùi ar laø soá caùch ñeå choïn r vieân bi töø 3 vieân bi maøu xanh, 3 vieân bi maøu traéng, 3 vieân bi maøu ñoû, vaø 3 vieân bi maøu vaøng.

Baøi toaùn treân coù theå ñöa veà baøi toaùn tìm nghieäm nguyeân cuûa phöông trình

e1 + e2 + e3 + e4 = r

vôùi 0 ≤ ei ≤ 3. ÔÛ ñaây e1 laø soá quaû caàu maøu xanh ñöôïc choïn, e2 laø soá quaû caàu maøu traéng, e3 laø soá quaû caàu maøu ñoû, vaø e4 laø soá quaû caàu maøu vaøng.

2017

50 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Ñònh nghóa haøm sinh

Ta xaây döïng moät tích cuûa caùc nhaân töû ña thöùc sao cho sau khi nhaân caùc ña thöùc ñoù laïi vôùi nhau, ta ñöôïc taát caû caùc haïng töû coù daïng xe1xe2xe3xe4, trong ñoù 0 ≤ ei ≤ 3. Nhö vaäy ta caàn 4 nhaân töû, vaø moãi nhaân töû baèng 1 + x + x2 + x3, bao goàm taát caû caùc luõy thöøa nhoû hôn hay baèng 3 cuûa x. Ta ñöôïc haøm sinh caàn tìm laø

(1 + x + x2 + x3)4 =1 + 4x + 10x2 + 20x3 + 31x4 + 40x5 + 44x6+ + 31x8 + 40x7 + 20x9 + 10x10 + 4x11 + x12.

2017

51 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Ñònh nghóa haøm sinh

Ví duï

Tìm haøm sinh cuûa {ar}r≥0, vôùi ar laø soá caùch ñeå choïn r quaû töø 6 quaû leâ, 5 quaû cam, 3 quaû chanh, 3 quaû maän.

Giaûi. Töông töï nhö ví duï treân ar laø nghieäm nguyeân cuûa phöông trình

e1 + e2 + e3 + e4 = r

vôùi 0 ≤ e1 ≤ 6, 0 ≤ e2 ≤ 5, 0 ≤ e3 ≤ 3, vaø 0 ≤ e4 ≤ 3. Ñeå tìm haøm sinh ta xaây döïng moät tích cuûa caùc nhaân töû ña thöùc sao cho sau khi nhaân caùc ña thöùc ñoù laïi vôùi nhau, ta ñöôïc taát caû caùc haïng töû coù daïng xe1xe2xe3xe4. Caùc nhaân töû ña thöùc töông öùng laø: 1 + x + x2 + x3 + x4 + x5 + x6, 1+x+x2+x3+x4+x5, 1+x+x2+x3, vaø 1+x+x2+x3. Vaäy haøm sinh caàn tìm laø (1 + x + x2 + x3 + x4 + x5 + x6)(1 + x + x2 + x3 + x4 + x5)(1 + x + x2 + x3)2.

2017

52 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Giaûi. ar laø soá nghieäm nguyeân cuûa phöông trình

e1 + e2 + e3 + e4 + e5 = r

vôùi e1, e2 chaün, 0 ≤ e1, e2 ≤ 10, vaø 3 ≤ e3, e4, e5 ≤ 5. Ñeå tìm haøm sinh ta xaây döïng moät tích cuûa caùc nhaân töû ña thöùc sao cho sau khi nhaân caùc ña thöùc ñoù laïi vôùi nhau, ta ñöôïc taát caû caùc haïng töû coù daïng xe1xe2xe3xe4xe5. Ta ñöôïc nhaân töû ña thöùc töông öùng vôùi e1 vaø e2 laø (1 + x2 + x4 + x6 + x8 + x10), vaø töông öùng vôùi e3, e4, vaø e5 laø (x3 + x4 + x5). Haøm sinh caàn tìm laø

(1 + x2 + x4 + x6 + x8 + x10)2(x3 + x4 + x5)3

Haøm sinh

Ñònh nghóa haøm sinh

Ví duï

Tìm haøm sinh cuûa {ar}r≥0, vôùi ar laø soá caùch chia r ñoàng xu vaøo 5 hoäp vôùi ñieàu kieän: Soá ñoàng xu ôû hoäp 1 vaø hoäp 2 laø soá chaün vaø khoâng quaù 10, vaø caùc hoäp coøn laïi chöùa 3 ñeán 5 ñoàng xu.

2017

53 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Ñònh nghóa haøm sinh

Ví duï

Giaûi. ar laø soá nghieäm nguyeân cuûa phöông trình

e1 + e2 + e3 + e4 + e5 = r

(1 + x2 + x4 + x6 + x8 + x10)2(x3 + x4 + x5)3

2017

53 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Heä soá haøm sinh

Haøm sinh

Heä soá haøm sinh

Trong phaàn naøy, chuùng ta seõ söû duïng moät soá kyû thuaät ñeå tính toaùn caùc heä soá trong haøm sinh. Phöông phaùp chuû yeáu laø ñöa moät haøm sinh phöùc taïp veà haøm sinh kieåu nhò thöùc hoaëc tích cuûa caùc haøm sinh kieåu nhò thöùc. Ta caàn söû duïng moät soá khai trieån sau: Moät soá khai trieån ña thöùc

(1) = 1 + x + x2 + x3 + · · · + xm

(2) = 1 + x + x2 + · · · 1 − xm+1 1 − x 1 1 − x (cid:19) (cid:19) (cid:19) (cid:19) x2 + · · · + xr + · · · + xn (3) (1 + x)n = 1 + x + (cid:18) n r (cid:18) n n (cid:19) (cid:19) (cid:19) xm + x2m + · · · + (−1)k xkm + (cid:18) n 1 (cid:18) n 1 (cid:18) n 2 (cid:18) n 2 (cid:18) n k (cid:19) · · · + (−1)n xnm (4) (1 − xm)n = 1 − (cid:18) n n

2017

54 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Heä soá haøm sinh

Haøm sinh

Heä soá haøm sinh

Moät soá khai trieån ña thöùc

(5)

(cid:19) (cid:19) (cid:19) 1 + x2 + · · · + xr + · · · x + 1 (1 − x)n = (cid:18) 1 + n − 1 1 (cid:18) 2 + n − 1 2 (cid:18) r + n − 1 r

(6) Neáu h(x) = f(x)g(x), vôùi f(x) = a0 + a1x + a2x2 + · · · vaø g(x) = b0 + b1x + b2x2 + · · · , thì h(x) = a0b0 + (a1b0 + a0b1)x + (a2b0 + a1b1 + a0b2)x2 + · · · + (arb0 + ar−1b1 + ar−2b2 + · · · + a0br)xr + · · ·

2017

55 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Heä soá haøm sinh

Haøm sinh

Heä soá haøm sinh

Ví duï Tìm heä soá cuûa x16 trong (x2 + x3 + x4 + · · · )5?

Giaûi. Ta coù

(x2 + x3 + x4 + · · · )5 = [x2(1 + x + x2 + · · · )]5 = x10(1 + x + x2 + · · · )5

= x10 1 (1 − x)5

1 (1−x)5 laø

Ñeå tìm heä soá cuûa x16 trong (x2 + x3 + x4 + · · · )5, ta tìm heä soá cuûa x6 trong (1−x)5 . Theo khai trieån treân ta ñöôïc heä soá cuûa x6 trong

(cid:19) . (cid:18) 6 + 5 − 1 6

2017

56 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Giaûi. Baøi toaùn treân töông ñöông vôùi baøi toaùn tìm nghieäm nguyeân cuûa phöông trình x1 + x2 + · · · + x20 = 15

thoûa ñieàu kieän xi = 0 hoaëc 1 vôùi i = 1, 2, . . . , 19 vaø x20 = 0 hoaëc 1, hoaëc 5. Ta coù ñöôïc haøm sinh cho baøi toaùn treân laø

(1 + x)19(1 + x + x5)

Heä soá haøm sinh

Haøm sinh

Heä soá haøm sinh

Ví duï

Tìm soá caùch ñeå laáy 15 ñoàng xu töø 20 ngöôøi sao cho, trong 19 ngöôøi ñaàu tieân ta coù theå laáy ôû moãi ngöôøi 0 ñoàng hoaëc 1 ñoàng, vaø ngöôøi thöù 20 ta coù theå laáy 0 ñoàng, hoaëc 1 ñoàng, hoaëc 5 ñoàng?

2017

57 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Heä soá haøm sinh

Haøm sinh

Heä soá haøm sinh

Ví duï

Giaûi. Baøi toaùn treân töông ñöông vôùi baøi toaùn tìm nghieäm nguyeân cuûa phöông trình x1 + x2 + · · · + x20 = 15

thoûa ñieàu kieän xi = 0 hoaëc 1 vôùi i = 1, 2, . . . , 19 vaø x20 = 0 hoaëc 1, hoaëc 5. Ta coù ñöôïc haøm sinh cho baøi toaùn treân laø

(1 + x)19(1 + x + x5)

2017

57 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Heä soá haøm sinh

Haøm sinh

Heä soá haøm sinh

Theo coâng thöùc khai trieån ta coù

(cid:19) (cid:19) (cid:19) (1 + x)19 = 1 + x + x2 + · · · + · · · + x19 (cid:18) 19 1 (cid:18) 19 2 (cid:18) 19 19

(cid:19) , vaø Ñaët f(x) = (1 + x)19 vaø g(x) = 1 + x + x5. Goïi ar laø heä soá cuûa xr trong f(x), vaø br laø heä soá cuûa xr trong g(x). Ta thaáy ar = (cid:18) 19 r

b0 = b1 = b5 = 1, caùc bi khaùc baèng 0. Heä soá cuûa x15 trong h(x) = f(x)g(x) ñöôïc tính bôûi (6) laø,

a15b0 + a14b1 + a13b2 + · · · + a0b15

Thu goïn ta ñöôïc (cid:19) (cid:19) (cid:19) × 1 + × 1 + × 1 = 107882. a15b0 + a14b1 + a10b5 = (cid:18) 19 15 (cid:18) 19 14 (cid:18) 19 10

2017

58 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Giaûi. Haøm sinh cuûa daõy {ar}r≥0 vôùi ar laø soá caùch chia r vieân bi vaøo 7 hoäp vôùi ñieàu kieän nhö ñeà baøi laø:

(1 + x + . . . + x10)(1 + x + x2 + . . . +)6

! !6 1 1 − x11 = 1 − x 1 − x

!7 1 = (1 − x11) 1 − x

Heä soá haøm sinh

Haøm sinh

Heä soá haøm sinh

Ví duï

Coù bao nhieâu caùch chia 25 vieân bi vaøo 7 hoäp vôùi ñieàu kieän hoäp thöù nhaát coù khoâng quaù 10 vieân, caùc hoäp coøn laïi tuøy yù.

2017

59 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Heä soá haøm sinh

Haøm sinh

Heä soá haøm sinh

Ví duï

Coù bao nhieâu caùch chia 25 vieân bi vaøo 7 hoäp vôùi ñieàu kieän hoäp thöù nhaát coù khoâng quaù 10 vieân, caùc hoäp coøn laïi tuøy yù.

Giaûi. Haøm sinh cuûa daõy {ar}r≥0 vôùi ar laø soá caùch chia r vieân bi vaøo 7 hoäp vôùi ñieàu kieän nhö ñeà baøi laø:

(1 + x + . . . + x10)(1 + x + x2 + . . . +)6

! !6 = 1 − x11 1 − x 1 1 − x

!7 = (1 − x11) 1 1 − x

2017

59 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Heä soá haøm sinh

Haøm sinh

Heä soá haøm sinh

Theo coâng thöùc (5) ta coù !7 (cid:19) (cid:19) = 1 + x + · · · + xr + · · · (cid:18) 1 + 7 − 1 1 (cid:18) r + 7 − 1 r 1 1 − x

!7 Ñaët f(x) = 1 − x11 vaø g(x) = . Goïi ar laø heä soá cuûa xr trong f(x),

1 1 − x vaø br laø heä soá cuûa xr trong g(x). Ta thaáy a0 = 1, a11 = −1, ai = 0 vôùi (cid:19) . i 6= 0, 11 vaø br = (cid:18) r + 7 − 1 r

Heä soá cuûa x25 trong h(x) = f(x)g(x) ñöôïc tính bôûi (6) laø,

a0b25 + a1b24 + · · · + a25b0

Thu goïn ta ñöôïc (cid:19) (cid:19) + (−1) × = 697521 a0b25 + a11b14 = 1 × (cid:18) 25 + 7 − 1 25 (cid:18) 14 + 7 − 1 14

2017

60 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Heä soá haøm sinh

Haøm sinh

Heä soá haøm sinh

Ví duï

Coù bao nhieâu caùch choïn 25 noùn töø 6 loaïi noùn, vôùi ñieàu kieän moãi loaïi noùn phaûi ñöôïc choïn töø 1 ñeán 5 caùi.

Ví duï

Cho n laø soá nguyeân döông. Chöùng minh raèng:

(cid:19)2 (cid:19)2 (cid:19)2 (cid:19) + + · · · + = (cid:18) n 0 (cid:18) n 1 (cid:18) n n (cid:18) 2n n

2017

61 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Heä soá haøm sinh

Haøm sinh

Heä soá haøm sinh

(cid:19) Giaûi. Ta coù laø heä soá cuûa xn trong (1 + x)2n = (1 + x)n(1 + x)n. (cid:18) 2n n

Ñaët f(x) = (1 + x)n, g(x) = (1 + x)n vaø ar, br laàn löôït laø heä soá cuûa xr trong (cid:19) . AÙp duïng coâng thöùc (6), ta coù heä soá f(x) vaø g(x). Ta coù ar = br = (cid:18) n r xn trong f(x)g(x) laø

a0bn + a1bn−1 + · · · + anb0 (cid:19) (cid:19) (cid:19) (cid:19) (cid:18) n + + · · · + = (cid:18) n 1 (cid:19) (cid:18) n 0 (cid:18) n n

(cid:19)2 (cid:19)2 (cid:19)2 + = + · · · + . (cid:18) n 0 (cid:18) n 0 (cid:19) (cid:18) n n (cid:18) n 1 n − 1 (cid:18) n n

2017

62 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Phaân hoaïch

Ñònh nghóa

Cho soá nguyeân döông n. Khi ñoù daõy (a1, a2, . . . , ak) ñöôïc goïi laø moät phaân hoaïch cuûa n neáu 1 ≤ a1 ≤ a2 ≤ · · · ≤ ak ≤ n vaø a1 + a2 + · · · + ak = n.

Ví duï

Soá nguyeân döông 5 coù 7 phaân hoaïch laø (1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 3), (1, 2, 2), (1, 4), (2, 3), vaø (5), trong ñoù 5 ñöôïc goïi laø moät phaân hoaïch taàm thöôøng cuûa chính noù.

Ví duï

Lieät keâ taát caû caùc phaân hoaïch cuûa 6.

2017

63 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Phaân hoaïch

Chuùng ta xaây döïng moät haøm sinh cho ar, vôùi ar laø soá löôïng caùc phaân hoaïch cuûa soá nguyeân r. Moät phaân hoaïch cuûa soá nguyeân r ñöôïc moâ taû baèng soá löôïng caùc soá 1, 2,...sao cho khi laáy toång laïi vôùi nhau ta ñöôïc r. Goïi ek laø soá caùc soá nguyeân k xuaát hieän trong phaân hoaïch, ta coù

1e1 + 2e2 + 3e3 + · · · + kek + · · · + rer = r

Ta ñöôïc haøm sinh caàn tìm laø

g(x) = (1 + x + x2 + · · · + xn + · · · ) × (1 + x2 + x4 + · · · + x2n + · · · )×

· · · × (1 + xk + x2k + · · · + xkn + · · · )

Deã daøng thaáy ñöôïc g(x) = 1 (1 − x)(1 − x2)(1 − x3) . . . (1 − xk) . . .

2017

64 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Phaân hoaïch

Ví duï

Tìm haøm sinh cho ar, vôùi ar laø soá caùch bieåu dieãn r nhö toång cuûa caùc soá nguyeân khaùc nhau.

Töông töï nhö treân ta cuõng goïi ek laø soá caùc soá nguyeân k xuaát hieän trong phaân hoaïch cuûa r, ta coù

1e1 + 2e2 + 3e3 + · · · + kek + · · · + rer = r

Do yeâu caàu cuûa baøi toaùn caùc ei chæ nhaän giaù trò laø 0 hoaëc 1. Ta ñöôïc haøm sinh cuûa ar laø g(x) = (1 + x)(1 + x2)(1 + x3) . . .

Ví duï

Tìm haøm sinh cho ar, vôùi ar laø soá caùch choïn caùc ñoàng xu 1 ñoàng, 2 ñoàng, 5 ñoàng ñeå ñöôïc toång laø r ñoàng.

2017

65 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Phaân hoaïch

Ví duï

Chöùng minh raèng moïi soá nguyeân döông ñeàu ñöôïc vieát nhö laø toång duy nhaát cuûa caùc luõy thöøa khaùc nhau cuûa 2.

Goïi ar laø soá caùch ñeå vieát moät soá nguyeân r thaønh toång cuûa caùc luõy thöøa khaùc nhau cuûa 2. Ta tìm haøm sinh cho ar. Töông töï nhö haøm sinh cho toång caùc soá nguyeân khaùc nhau trong ví duï treân, nhöng trong tröôøng hôïp naøy ta chæ xeùt caùc soá nguyeân laø luõy thöøa cuûa 2. Goïi ek laø soá caùc soá nguyeân 2k trong phaân hoaïch, thì ta coù

1e0 + 2e1 + 22e2 + · · · + 2kek + · · · = r

Haøm sinh cuûa ar laø

) . . . g(x) = (1 + x)(1 + x2)(1 + x4)(1 + x8) . . . (1 + x2k

2017

66 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Phaân hoaïch

Ñeå chöùng minh moïi soá nguyeân ñeàu ñöôïc vieát döôùi daïng toång duy nhaát cuûa caùc luõy thöøa khaùc nhau cuûa 2, ta phaûi chöùng minh heä soá cuûa moãi luõy thöøa cuûa x trong g(x) baèng 1. Nghóa laø chöùng minh

g(x) = 1 + x + x2 + x3 + · · · = 1 1 − x

Ta thaáy

(1 − x)g(x) = (1 − x)(1 + x)(1 + x2)(1 + x4) . . . (1 + x2k) . . .

= (1 − x2)(1 + x2)(1 + x4) . . . (1 + x2k) . . . = (1 − x4)(1 + x4) . . . (1 + x2k) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . = 1

Do ñoù g(x) = 1 + x + x2 + x3 + · · · . Vaäy ta ñöôïc ñieàu caàn chöùng minh.

2017

67 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Haøm sinh muõ

Trong phaàn naøy chuùng ta seõ noùi veà haøm sinh muõ vaø söû duïng chuùng ñeå giaûi quyeát caùc baøi toaùn lieân quan ñeán söï saép xeáp coù laëp laïi.

Ví duï

Tìm soá caùc töø khaùc nhau coù 4 kyù töï ñöôïc taïo thaønh töø caùc chöõ a, b, c, vaø moãi töø chöùa ít nhaát hai chöõ a?

Töø taäp hôïp caùc kyù töï sau ñaây ta coù theå saép xeáp ñeå ñöôïc caùc töø caàn tìm: {a, a, a, a}, {a, a, a, b}, {a, a, a, c}, {a, a, b, b}, {a, a, b, c}, {a, a, c, c}. Deã daøng thaáy raèng soá töø coù theå coù ñöôïc laø

+ + + + + 4! 4!0!0! 4! 3!1!0! 4! 3!0!1! 4! 2!2!0! 4! 2!1!1! 4! 2!0!2!

2017

68 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Haøm sinh muõ

Goïi e1, e2, e3 laø soá chöõ a, b, c xuaát hieän trong moät töø. Thoaït nhìn, baøi toaùn cuûa chuùng ta seõ töông ñöông vôùi baøi toaùn tìm soá nghieäm nguyeân cuûa phöông trình e1 + e2 + e3 = 4

4! e1!e2!e3! töø coù theå. Trong tröôøng hôïp naøy ngöôøi ta ñöa ra khaùi nieäm haøm sinh muõ.

vôùi e1 ≥ 2 , e2, e3 ≥ 0, vaø chuùng ta coù theå duøng haøm sinh thoâng thöôøng ñeå giaûi. Söï khaùc bieät ôû ñaây naèm ôû choã öùng vôùi moãi nghieäm nguyeân cuûa phöông trình treân ta ñöôïc soá löôïng caùc chöõ caùi moãi loaïi, vaø öùng vôùi soá löôïng caùc chöõ caùi ñoù ta coù theå saép xeáp ñeå cho ra nhieàu töø khaùc nhau. Nghóa laø öùng vôùi moät nghieäm nguyeân cuûa phöông trình treân cho ta

2017

69 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Haøm sinh muõ

Ñònh nghóa

Cho {ar}r≥0 laø moät daõy caùc soá thöïc. Khi ñoù chuoãi luõy thöøa hình thöùc

+ · · · E(x) = a0 + a1x + a2 + a3 + · · · + ar x2 2! x3 3! xr r!

ñöôïc goïi laø haøm sinh muõ cuûa daõy {ar}r≥0.

Chuùng ta xaây döïng haøm sinh muõ gioáng nhö caùch xaây döïng haøm sinh thoâng thöôøng: moät nhaân töû ña thöùc cho moãi ñoái töôïng, moãi nhaân töû chöùa taäp hôïp caùc luõy thöøa cuûa x. Tuy nhieân moãi luõy thöøa xr ñöôïc chia cho r!.

2017

70 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Haøm sinh muõ

Ví duï

Tìm haøm sinh muõ cho ar, soá caùc boä goàm k phaàn töû khoâng laëp laïi coù saép thöù töï töø n phaàn töû?, (ar laø chænh hôïp chaäp r cuûa n phaàn töû. )

r! laø ar = n!/(n − r)!

Do khoâng coù söï laëp laïi, neân haøm sinh muõ caàn tìm laø (1 + x)n. Heä soá cuûa xr (cid:19) laø . Heä soá cuûa xr (cid:18) n r

, do ñoù haøm sinh muõ laø Hay noùi caùch khaùc, ta coù ar = n! (n − r)!

+ + · · · + + · · · . E(x) = 1 + nx + x2 2! x3 3! n! (n − 2)! n! (n − 3)! n! (n − r)! xr r!

2017

71 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Haøm sinh muõ

Ví duï

Tìm haøm sinh muõ cho ar, vôùi ar laø soá caùch saép xeáp khaùc nhau cuûa r vaät theå ñöôïc choïn ra töø 4 loaïi vaät theå khaùc nhau, sao cho moãi loaïi vaät theå xuaát hieän ít nhaát 2 laàn vaø khoâng quaù 5 laàn?

Goïi ei laø soá löôïng loaïi vaät theå thöù i, i = 1, 2, 3, 4, xuaát hieän trong soá r vaät theå caàn saép xeáp. Ta coù e1 + e2 + e3 + e4 = r vaø 2 ≤ ei ≤ 5, vôùi i = 1, 2, 3, 4. Nhaân töû ña thöùc öùng vôùi moãi loaïi vaät theå laø

+ + + x2 2! x3 3! x4 4! x5 5!

. Töø ñoù suy ra haøm sinh caàn tìm laø

!4 + + + . x2 2! x3 3! x4 4! x5 5!

2017

72 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Haøm sinh muõ

Ví duï

Tìm haøm sinh muõ cho soá caùch xeáp r ngöôøi vaøo trong 3 caên phoøng vôùi ít nhaát moät ngöôøi moãi phoøng?

Deã daøng thaáy haøm sinh muõ caàn tìm laø

(cid:18) (cid:19)3 + + + · · · . x + x2 2! x3 3! x4 4!

2017

73 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Haøm sinh muõ

Moät soá khai trieån cô baûn cuûa haøm sinh muõ

Ta coù

+ + · · · + + · · · ex = 1 + x + x2 2! x3 3! xr r! Thay x bôûi nx ta ñöôïc

+ + · · · + + · · · . enx = 1 + nx + n2x2 2! n3x3 3! nrxr r!

Ta cuõng suy ra ñöôïc laø

+ + + · · · = ex − 1 − x x2 2! x3 3! x4 4!

+ + + . . . (ex + e−x) = 1 +

+ + + · · · (ex − e−x) = x + 1 2 1 2 Moät soá khai trieån höõu ích thöôøng gaëp x6 6! x7 7! x4 4! x5 5! x2 2! x3 3!

2017

74 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Haøm sinh muõ

Ta xem moät soá öùng duïng:

Ví duï

Tìm soá caùch saép xeáp r ñoái töôïng ñöôïc choïn ra töø n loaïi ñoái töôïng khaùc nhau?

Ta deã daøng thaáy haøm sinh cuûa noù laø

r! trong

(cid:18) (cid:19)n + + · · · = (ex)n = enx 1 + x + x2 2! x3 3!

Theo coâng thöùc khai trieån treân ta deã daøng thaáy ñöôïc heä soá cuûa xr haøm sinh treân laø nr (coâng thöùc chænh hôïp laëp).

2017

75 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Haøm sinh muõ

Ví duï

Tìm soá caùch ñeå chia 25 ngöôøi vaøo trong 3 caên phoøng vôùi ít nhaát moät ngöôøi moãi phoøng?

3! + · · ·

2! + x3 Ta deã daøng thaáy ñöôïc haøm sinh muõ laø tìm heä soá cuûa xr/r! ta khai trieån bieåu thöùc cuûa ex, (ex − 1)3 = e3x − 3e2x + 3ex − 1 Thay vaøo ta ñöôïc

∞ X

(cid:16) (cid:17)3 x + x2 = (ex − 1)3 ñeå

r=0

− 3 + 3 − 1 e3x − 3e2x + 3ex − 1 = 3r xr r! 2r xr r! xr r!

Suy ra heä soá cuûa x25/25! laø 325 − (3 × 225) + 3.

2017

76 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Phöông phaùp toång

Trong phaàn naøy ta chæ ra caùch xaây döïng haøm sinh thoâng thöôøng h(x) maø heä soá cuûa xr phuï thuoäc vaøo r. Ta coù moät soá quy luaät sau ñaây ñeå xaây döïng haøm sinh môùi töø caùc haøm sinh ñaõ coù saün. Giaû söû A(x) = P anxn, B(x) = P bnxn, C(x) = P cnxn.

dx g(x) = a1 + 2a2x + 3a3x2 + · · · + rarxr−1 + · · · .

Neáu bn = dan, thì B(x) = dA(x) vôùi moïi haèng soá d. Neáu cn = an + bn, thì C(x) = A(x) + B(x). Neáu cn = Pn i=0 aibn−i, thì C(x) = A(x)B(x). Neáu bn = an−k, ngoaïi tröø bi = 0 vôùi i < k, thì B(x) = xkA(x).

(cid:21) g(x) x = a1x + 2a2x2 + 3a3x3 + · · · + rarxr + · · · Neáu g(x) = a0 + a1x + a2x2 + a3x3 + · · · + arxr + · · · , laáy ñaïo haøm cuûa g(x) ta ñöôïc d Nhaân hai veá cho x ta ñöôïc (cid:20) d dx

2017

77 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Phöông phaùp toång

Ví duï Xaây döïng haøm sinh h(x) vôùi heä soá ar = 2r2.

1−x = 1 + x + x2 + x3 + · · · , ta ñöôïc (cid:17)

1 1−x

(1−x)2

(1−x)2 ta ñöôïc

(cid:17) (cid:16) 1 = x = 1x + 2x2 + 3x3 + · · · + rxr + · · · Töø (cid:16) d dx

x (1−x)2

(1−x)3 = 12x + 22x2 + 32x3 + · · · + r2xr + · · · Cuoái cuøng

(cid:17) = x(1+x) x x Ta laëp laïi quaù trình treân vôùi (cid:16) d dx

(1−x)3 = (2 × 12)x + (2 × 22)x2 + · · · + (2 × r2)xr + · · · .

nhaân 2 vaøo hai veá cuûa phöông trình treân ta ñöôïc h(x) = 2x(1+x)

2017

78 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Phöông phaùp toång

Ví duï

Xaây döïng haøm sinh h(x) vôùi heä soá ar = (r + 1)r(r − 1).

Ta coù

(cid:18) (cid:19) (cid:19) (cid:19) 1 3! 1 + x2 + · · · x + (cid:18) 1 + 4 − 1 1 (cid:18) 2 + 4 − 1 r (1 − x)4 = 3!

Heä soá ar cuûa khai trieån treân laø

(cid:19) = 3! = (r + 3)(r + 2)(r + 1) ar = 3! (cid:18) r + 4 − 1 r (r + 3)! r!3!

2017

79 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Phöông phaùp toång

(1−x)4 laø:

Khi ñoù khai trieån luõy thöøa cuûa 3!

3! (1 − x)4 = (3 × 2 × 1) + (4 × 3 × 2)x + · · · + (r + 3)(r + 2)(r + 1)xr + · · ·

Nhaân hai veá cho x2 ta ñöôïc

(1−x)4 .

3!x2 (1 − x)4 = (3 × 2 × 1)x2 + (4 × 3 × 2)x3 + · · · + (r + 1)r(r − 1)xr + · · ·

Vaäy haøm sinh caàn tìm laø h(x) = 3!x2 Toång quaùt, ta thaáy (n − 1)!(1 − x)−n coù heä soá ar laø

ar = (n − 1)!C(r + n − 1, r) = [r + (n − 1)][r + (n − 2)] · · · (n + 1)

2017

80 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Phöông phaùp toång

Ñònh lyù Neáu h(x) laø haøm sinh vôùi ar laø heä soá cuûa xr, thì h∗(x) = h(x)/(1 − x) laø haøm sinh cuûa toång caùc ar, nghóa laø

i=0

! r X xr + · · · . h∗(x) = a0 + (a0 + a1)x + (a0 + a1 + a2)x2 + · · · + ai

Ví duï Tính toång 2 × 12 + 2 × 22 + 2 × 32 + · · · + 2n2.

2017

81 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Phöông phaùp toång

Haøm sinh h(x) cho ar = 2r2 laø

2x(1 + x)/(1 − x)3

Theo ñònh lyù treân, toång caàn tìm a1 + a2 + · · · + an laø heä soá cuûa xn trong

h∗(x) = h(x)/(1 − x) = 2x(1 + x)/(1 − x)4 = 2x(1 − x)−4 + 2x2(1 − x)−4

Heä soá cuûa xn trong 2x(1 − x)−4 laø heä soá cuûa xn−1 trong 2(1 − x)−4, vaø heä soá cuûa xn trong 2x2(1 − x)−4 laø heä soá cuûa xn−2 trong 2(1 − x)−4. Do ñoù toång caàn tìm baèng

(cid:19) (cid:19) 2 + 2 (cid:18) (n − 1) + 4 − 1 (n − 1) (cid:18) (n − 2) + 4 − 1 (n − 2)

(cid:19) (cid:19) = 2 + 2 . (cid:18) n + 2 3 (cid:18) n + 1 3

2017

82 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Phöông phaùp toång

Ví duï

Tính toång 3 × 2 × 1 + 4 × 3 × 2 + · · · + (n + 1)n(n − 1).

Haøm sinh h(x) cho ar = (r + 1)r(r − 1) laø:

h(x) = 6x2(1 − x)−4.

Bôûi ñònh lyù treân, toång caàn tìm laø heä soá cuûa xn trong h∗(x) = h(x)/(1 − x) = 6x2(1 − x)−5. Heä soá cuûa xn trong h∗(x) baèng vôùi heä soá cuûa xn−2 trong 6(1 − x)−5, vaø baèng

6C((n − 2) + 5 − 1, n − 2) = 6C(n + 2, 4).

2017

83 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh thoâng thöôøng trong baøi toaùn ñeä quy

Trong phaàn naøy, chuùng ta seõ trình baøy moät öùng duïng quan troïng cuûa haøm sinh trong vieäc giaûi baøi toaùn ñeä quy, ta goïi G(x) laø haøm sinh cuûa daõy {an}n≥0 vaø tieán haønh caùc böôùc sau:

(1) Chuyeån coâng thöùc ñeä quy thaønh moät phöông trình cuûa G(x), thöôøng ñöôïc thöïc hieän baèng caùch nhaân caû hai veá cuûa phöông trình ñeä quy cho xn, hay xn+1, hay xn+k vôùi moät k naøo ñoù, vaø laáy toång treân taát caû caùc soá nguyeân khoâng aâm n. (2) Giaûi phöông trình ñeå tìm G(x). (3) Tìm heä soá cuûa xn trong G(x), heä soá ñoù chính baèng an, vaø ta ñöôïc moät coâng thöùc töôøng minh cho an.

2017

84 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh thoâng thöôøng trong baøi toaùn ñeä quy

Ví duï

n≥0 anxn laø haøm sinh cuûa daõy

Moät ngöôøi göûi 1000 ñoâ la vaøo trong moät taøi khoaûn tieát kieäm vôùi laõi suaát laø 5 phaàn traêm moät naêm. Baét ñaàu moãi naêm, ngöôøi ñoù laïi chuyeån vaøo taøi khoaûn ñoù 500 ñoâ la nöõa. Hoûi soá tieàn trong taøi khoaûn tieát kieäm cuûa ngöôøi ñoù sau n naêm laø bao nhieâu?

Goïi an laø soá dö trong taøi khoaûn tieát kieäm sau n naêm. Ta thaáy a0 = 1000, an+1 = 1.05an + 500. Goïi G(x) = P {an}n≥0. Baây giôø ta giaûi baøi toaùn theo caùc böôùc nhö treân: (1) Nhaân caû hai veá cuûa heä thöùc ñeä quy vôùi xn+1 vaø laáy toång treân taát caû caùc

n≥0

soá nguyeân khoâng aâm n, ta ñöôïc X X X 500xn+1 1.05anxn+1 + an+1xn+1 =

Phöông trình treân töông ñöông vôùi: G(x) − a0 = 1.05xG(x) + 500x 1−x

2017

85 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh thoâng thöôøng trong baøi toaùn ñeä quy

(2)Do ñoù ta ñöôïc

+ G(x) = 1000 1 − 1.05x 500x (1 − x)(1 − 1.05x)

n≥0

(3)Ta thaáy X = 1000 · 1.05nxn 1000 1 − 1.05x

500x

do ñoù heä soá cuûa xn trong bieåu thöùc treân laø 1000 · 1.05n.

n≥0 xn(cid:17) (cid:16)P

n≥0 1.05nxn(cid:17)

(1−x)(1−1.05x) = 500x.

(cid:16)P Xeùt thaønh phaàn thöù hai

2017

86 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh thoâng thöôøng trong baøi toaùn ñeä quy

500x (1−x)(1−1.05x) laø

n−1 X

Trong tích treân xn−1 ñöôïc taïo thaønh töø xi cuûa toång thöù nhaát vaø 1.05n−1−ixn−1−i töø toång thöù hai vôùi 0 ≤ i ≤ n − 1. Do ñoù heä soá cuûa xn trong

i=0

500 1.05i = 500 = 10000 · (1.05n − 1) 1.05n − 1 1.05 − 1

Ta ñöôïc heä soá

an = 1000 · 1.05n + 10000 · (1.05n − 1) = 1.05n.11000 − 10000.

Thöû laïi ta ñöôïc keát quaû ñuùng.

2017

87 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh thoâng thöôøng trong baøi toaùn ñeä quy

Ví duï Cho heä thöùc ñeä quy an+1 = 4an − 100, vaø a0 = 50. Tìm coâng thöùc cho an.

. Ñaùp aùn: an = 50 · 4n − 100 · 4n−1 3

Ví duï Cho heä thöùc ñeä quy an+2 = 3an+1 − 2an, vaø a0 = 0, a1 = 1. Tìm coâng thöùc cho an.

Ñaùp aùn: an = 2n − 1.

2017

88 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

Ñònh lyù (Coâng thöùc tích cho haøm sinh thoâng thöôøng)

Goïi an laø soá caùch ñeå xaây döïng moät caáu truùc naøo ñoù treân taäp n phaàn töû, vaø bn laø soá caùch ñeå xaây döïng moät caáu truùc khaùc treân taäp n phaàn töû. Goïi cn laø soá caùch ñeå chia [n] thaønh caùc ñoaïn S = {1, 2, · · · , i} vaø T = {i + 1, i + 2, · · · , n}, (S vaø T coù theå baèng roãng), vaø xaây döïng caáu truùc loaïi thöù nhaát leân S, vaø caáu truùc loaïi thöù hai leân T. Goïi A(x), B(x), vaø C(x) laø caùc haøm sinh töông öùng cuûa caùc daõy {an}, {bn}, vaø {cn}. Thì A(x)B(x) = C(x).

Ví duï

Moät hoïc kyø ôû moät tröôøng ñaïi hoïc coù n ngaøy. Ñaàu moãi hoïc kyø, coâ hieäu tröôûng chia hoïc kyø ñoù ra laøm 2 phaàn, k ngaøy ñaàu tieân seõ duøng cho lyù thuyeát, vaø n − k ngaøy coøn laïi seõ ñöôïc duøng cho thöïc haønh (ôû ñaây 1 ≤ k ≤ n − 2). Trong ñôït daïy lyù thuyeát seõ coù 1 ngaøy nghæ, vaø trong ñôït daïy thöïc haønh seõ coù 2 ngaøy nghæ. Hoûi coâ hieäu tröôûng coù bao nhieâu caùch khaùc nhau ñeå laøm nhö vaäy?

2017

89 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh thoâng thöôøng trong baøi toaùn ñeä quy

k≥1 kxk, vaø

Neáu ñôït daïy lyù thuyeát coù k ngaøy thì ta seõ coù k caùch ñeå choïn ra moät ngaøy (cid:19) caùch ñeå

m≥2

1−x .

i≥0 xi = 1 (1−x)2 vaø B(x) = x2

(cid:19) (cid:18) n − k nghæ, vaø neáu ñôït daïy thöïc haønh coù n − k ngaøy thì coù 2 choïn ra 2 ngaøy nghæ. Caùc haøm sinh töông öùng laø A(x) = P xm. Ta coù P B(x) = P (cid:18) m 2

Laáy ñaïo haøm ta ñöôïc A(x) = x (1−x)3 Goïi fn laø soá caùch ñeå chia hoïc kyø ra hai phaàn vaø choïn ngaøy nghæ, vaø goïi F(x) laø haøm sinh cuûa noù. Khi ñoù ta coù A(x)B(x) = F(x). Do ñoù

n≥0

n≥3

(cid:19) (cid:19) X xn = xn = x3 X F(x) = (cid:18) n + 4 4 (cid:18) n + 1 4 x3 (1 − x)5

(cid:19) . Töø ñoù suy ra fn = (cid:18) n + 1 4

2017

90 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh thoâng thöôøng trong baøi toaùn ñeä quy

Ví duï

k≥0 2kxk = 1

1−2x . Ta thaáy phaàn thöù hai cuõng coù haøm

Töông töï nhö ví duï treân nhöng ôû ñaây thay vì choïn ngaøy nghæ, hieäu tröôûng choïn ra moät soá ngaøy töï hoïc trong caû hai phaàn cuûa hoïc kyø. Hoûi coù bao nhieâu caùch khaùc nhau ñeå hieäu tröôûng laøm nhö vaäy?

n≥0

(1−2x)2 = P

n≥0(n + 1)2nxn. Vaäy ta ñöôïc gn = (n + 1)2n.

n≥0

(cid:19) (2x)n = (cid:18) n + 2 − 1 n (cid:19) P (2x)n = P Goïi gn laø soá caùch maø hieäu tröôûng coù theå choïn. Chia baøi toaùn ra thaønh 2 phaàn. Goïi C(x) laø haøm sinh cho soá caùch ñeå choïn ra moät taäp caùc ngaøy töï hoïc trong phaàn thöù nhaát cuûa hoïc kyø. Bôûi vì moät taäp k phaàn töû seõ coù 2k taäp con, ta coù C(x) = P sinh gioáng nhö phaàn thöù nhaát. Do ñoù haøm sinh caàn tìm laø F(x) = C(x)C(x) = 1 (cid:18) n + 1 1

2017

91 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh thoâng thöôøng trong baøi toaùn ñeä quy

Ví duï

Tìm soá caùch ñeå chia n ngaøy cuûa moät hoïc kyø ra thaønh ba phaàn. Trong ñoù, ôû phaàn thöù nhaát soá ngaøy nghæ ñöôïc choïn tuøy yù, ôû phaàn thöù hai soá ngaøy nghæ laø soá leû, vaø ôû phaàn thöù ba soá ngaøy nghæ laø soá chaün.

Ñaùp aùn: gn = 2n−3n(n + 3).

Ví duï

∞ X

k Y

Goïi p≤k(n) laø soá caùc phaân hoaïch cuûa soá nguyeân n thaønh nhöõng phaàn coù nhoû hôn hay baèng k, chöùng minh raèng

n≥0

i=1

p≤k(n)xn = 1 1 − xi

= (1 + x + x2 + x3 + · · · )(1 + x2 + x4 + x6 + · · · ) · · · (1 + xk + x2k + x3k + · · · ).

2017

92 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh muõ trong baøi toaùn ñeä quy

Töông töï nhö haøm sinh thoâng thöôøng, goïi G(x) laø haøm sinh muõ cho daõy {an}, ta thöïc hieän theo moät soá böôùc nhö sau:

(1) Chuyeån heä thöùc ñeä quy thaønh moät phöông trình trong G(x), thöôøng ñöôïc thöïc hieän baèng caùch nhaân caû hai veá cuûa phöông trình ñeä quy cho xn/n!, hay xn+1/(n + 1)!, hay xn+k/(n + k)! vôùi moät k naøo ñoù, vaø laáy toång treân taát caû caùc soá nguyeân khoâng aâm n.

(2) Giaûi G(x). (3) Tìm heä soá cuûa xn/n! trong G(x), heä soá ñoù chính baèng an, vaø ta ñöôïc moät coâng thöùc töôøng minh cho an.

2017

93 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh muõ trong baøi toaùn ñeä quy

Ví duï

Cho a0 = 1, vaø an+1 = (n + 1)(an − n + 1), neáu n ≥ 0. Tìm moät coâng thöùc cho an.

Chuù yù

Neáu chuùng ta giaûi baøi toaùn treân baèng caùch duøng haøm sinh thoâng thöôøng, thì seõ gaëp vaán ñeà luùc ñöa ra keát quaû. Daõy {an} taêng khaù nhanh, vaø chuùng ta khoâng tìm ñöôïc daïng haøm sinh thoâng thöôøng töông öùng. Do ñoù baøi toaùn treân seõ ñöôïc giaûi baèng haøm sinh muõ.

2017

94 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh muõ trong baøi toaùn ñeä quy

n≥0 an

xn n! laø haøm sinh muõ cuûa daõy {an}n≥0. Ta nhaân caû hai xn+1 (n+1)! , vaø laáy toång vôùi moïi n ≥ 0, ta ñöôïc

Goïi A(x) = P veá cuûa heä thöùc ñeä quy vôùi

n≥0

X X X = − (n − 1) an an+1 xn+1 (n + 1)! xn+1 n! xn+1 n!

Ta thaáy veá traùi laø A(x) − 1, haïng töû ñaàu tieân cuûa veá phaûi laø xA(x). Töø ñoù ta ñöôïc phöông trình treân töông ñöông vôùi

A(x) − 1 = xA(x) − x2ex + xex.

n≥0

n≥0 xn laø n!, trong khi heä soá cuûa xn/n! trong

X X + xex = xn + A(x) = 1 1 − x xn+1 n!

n≥0

xn+1 n!

Heä soá cuûa xn/n! trong P P laø n. Vaäy heä soá cuûa xn/n! trong A(x) laø n! + n.

2017

95 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

n≥0 fn

n! laø haøm sinh muõ cuûa daõy {fn}. Nhaân caû hai veá cuûa

Goïi F(x) = P

xn+1

n≥0 fn

n≥0 xn+1

n≥0 fn+1

n! + P

(n+1)! = 2x P

heä thöùc treân vôùi xn+1/(n + 1)!, vaø laáy toång vôùi moïi n ≥ 0. Ta ñöôïc P

1−x , hay F(x) =

(1−x)(1−2x) Suy ra,

Do f0 = 0 neân veá traùi baèng F(x), haïng töû thöù nhaát cuûa veá phaûi baèng 2xF(x), vaø haïng töû thöù hai cuûa veá phaûi baèng x/(1 − x). Do ñoù, ta coù ñöôïc F(x) = 2xF(x) + x

n≥0

X F(x) = (2n − 1)xn

Ta ñöôïc heä soá cuûa xn/n! trong F(x) laø fn = (2n − 1)n!

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh muõ trong baøi toaùn ñeä quy

Ví duï

Cho f0 = 0, vaø fn+1 = 2(n + 1)fn + (n + 1)! neáu n ≥ 0. Tìm moät coâng thöùc cho fn.

2017

96 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh muõ trong baøi toaùn ñeä quy

n≥0 fn

xn n! laø haøm sinh muõ cuûa daõy {fn}. Nhaân caû hai veá cuûa

n≥0 xn+1

n≥0 fn

n≥0 fn+1

(n+1)! = 2x P xn+1

Ví duï

1−x , hay F(x) =

(1−x)(1−2x) Suy ra,

Cho f0 = 0, vaø fn+1 = 2(n + 1)fn + (n + 1)! neáu n ≥ 0. Tìm moät coâng thöùc cho fn. Goïi F(x) = P heä thöùc treân vôùi xn+1/(n + 1)!, vaø laáy toång vôùi moïi n ≥ 0. Ta ñöôïc n! + P P xn Do f0 = 0 neân veá traùi baèng F(x), haïng töû thöù nhaát cuûa veá phaûi baèng 2xF(x), vaø haïng töû thöù hai cuûa veá phaûi baèng x/(1 − x). Do ñoù, ta coù ñöôïc F(x) = 2xF(x) + x

n≥0

X F(x) = (2n − 1)xn

Ta ñöôïc heä soá cuûa xn/n! trong F(x) laø fn = (2n − 1)n!

2017

96 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh muõ trong baøi toaùn ñeä quy

k≥0 bk

xk k!

i≥0 ai (cid:19)

i! , vaø B(x) = P xi aibn−i, vaø C(x) laø haøm

i=0

Boå ñeà Goïi {ai} vaø {bk} laø hai daõy, vaø goïi A(x) = P (cid:18) n laø caùc haøm sinh cuûa noù. Goïi cn = Pn i sinh cuûa daõy {cn}. Thì A(x)B(x) = C(x)

i=0

(cid:19) Hay noùi caùch khaùc, heä soá cuûa xn/n! trong A(x)B(x) laø cn = Pn aibn−i. (cid:18) n i

2017

97 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh muõ trong baøi toaùn ñeä quy

Ñònh lyù (Coâng thöùc tích cho haøm sinh muõ)

Goïi an laø soá caùch ñeå xaây döïng moät caáu truùc naøo ñoù treân moät taäp hôïp n phaàn töû, vaø bn laø soá caùch ñeå xaây döïng moät caáu truùc khaùc treân taäp n phaàn töû. Goïi cn laø soá caùch ñeå chia ñoaïn [n] thaønh nhöõng taäp con rôøi nhau S vaø T, (S ∪ T = [n]), vaø xaây döïng moät caáu truùc treân S, vaø moät caáu truùc thöù hai leân T. Goïi A(x), B(x), vaø C(x) laø caùc haøm sinh muõ töông öùng cuûa caùc daõy {an}, {bn}, vaø {cn}, thì

A(x)B(x) = C(x).

Ví duï

Moät ñoäi boùng coù n caàu thuû. Huaán luyeän vieân chia ñoäi boùng ra thaønh hai nhoùm, vaø moãi nhoùm ñöùng thaønh moät doøng. Caùc thaønh vieân cuûa nhoùm thöù nhaát maët aùo cam, aùo traéng, hoaëc aùo xanh. Caùc thaønh vieân cuûa nhoùm coøn laïi maëc aùo ñoû. Hoûi coù bao nhieâu caùch ñeå thöïc hieän caùc vieäc treân?

2017

98 / 99

Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp

Haøm sinh

Baøi toaùn ñeä quy

ÖÙng duïng haøm sinh muõ trong baøi toaùn ñeä quy

k≥0 k!3k xk

1−3x .

k! = 1

m≥0 m! xm

m! = 1

1−x .

m≥0 xm,

1−3x = P

1−x = P

1−3x ·

Giaû söû huaán luyeän vieân choïn ra k ngöôøi ñeå taïo thaønh nhoùm thöù nhaát. Goïi ak laø soá caùch ñeå k ngöôøi naøy coù theå choïn aùo cam, traéng, hoaëc xanh, vaø ñöùng thaønh moät doøng. Thì ak = k!3k, haøm sinh muõ cuûa daõy {ak} laø A(x) = P Töông töï, giaû söû coù m ngöôøi trong nhoùm thöù hai. Goïi bm laø soá caùch ñeå m ngöôøi naøy ñöùng thaønh moät doøng, bm = m!, vaø haøm sinh muõ cuûa daõy bm laø B(x) = P Goïi cn laø soá caùch ñeå thöïc hieän taát caû nhöõng vieäc treân, vaø C(x) laø haøm sinh muõ töông öùng cuûa noù. Theo coâng thöùc treân ta coù C(x) = A(x)B(x) = 1 1 k≥0 3kxk, vaø 1−x . Do ta coù heä soá cuûa xn/n! trong C(x) laø cn = n!(3n+1 − 1)/2.

Bài giảng Nhập môn lý thuyết tổng hợp: Chương 2 - Nguyễn Anh Thi