?183ak},r?k,若要求s的k個(gè)不同元素的每一個(gè)至少在組合-全文預(yù)覽
【正文】 ?由推論 C(121,71)=C(11,6)= C(11,5)。a 5,?a 1,?a 1,x2 ?因此 ， S的 k個(gè)不同元素的每一個(gè)至少在組合中出現(xiàn)一次的 r組合數(shù)就是 S的 rk組合數(shù) ， ? C(k+(rk)1,rk)=C(r1,rk)=C(r1,(r1)(rk))=C(r1,k1)。a 2,… , ?a 1,? ?而對(duì)于 S的任一個(gè) rk組合 ， 加入元素 a1,a2,… ,ak，就是一個(gè)含有 S中所有不同元素的 r組合 。 ?即 S={x1 ?例：一個(gè)棋手要在相繼的 7天內(nèi)下 12盤(pán)棋 ， 問(wèn)有多少種安排法 ? 如果要求每天至少下一盤(pán)棋 ，又有多少種安排法 ？ ?解：將這相繼的 7 天記為 a1,a2,a3,a4,a5,a6,a7， ?則第一種安排相當(dāng)于多重集 S={?a 4,? ?由定理 即得 C(7+121,12)=C(18,12) =C(18,6)。a 2,… ,? ? (2)不包含 a1的 r組合 , ?相當(dāng)于 {?a 1,?a 1,n2 ?(3)若 rn， 且對(duì)一切 i=1,2,… ,k有 ni?r， 則：N=C(k+r1,r) ?(4)若 rn， 且存在著某個(gè) nir,則對(duì) N沒(méi)有一般的求解方法 ， 可利用容斥原理予以解決 。 如果塊與塊之間有先后次序之分，則記為（ A1,A2,…,A t），為 S的一個(gè) t塊有序劃分。 ?定義二：設(shè) S是 n個(gè)元素的集合 ， 且q1+q2+… +qt=n(qt為正整數(shù) ),根據(jù) qI的值就可構(gòu)造 S的 t個(gè)塊的劃分 {A1,A2,… ,At},使得 |Ai|=qi ,稱 (q1,q2,… ,qt)給出了 S的一種類型的 t個(gè)塊的有序劃分 ,記這種類型的不同有序劃分?jǐn)?shù)為 P(n。 但部分問(wèn)題可根據(jù)實(shí)際情況來(lái)解決 。 ?一 、 容斥原理 ?在介紹排列組合時(shí) ， 曾給出大家熟悉的加法原理： ?設(shè) A和 B是有限集合 S的兩個(gè)互不相交的子集 ， 且 A∪ B=S， 則 |S|=| A|+|B| ?對(duì)于 A和 B是兩個(gè)相交集合 ， S的元素個(gè)數(shù)與 A和 B的關(guān)系如何 ？
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1