?183ak},r?k,若要求s的k個(gè)不同元素的每一個(gè)至少在組合-文庫(kù)吧
2025-08-25 04:11 本頁(yè)面
【正文】 ?解：把 S的 r組合分成兩類： ? (1)包含 a1的 r組合 , ?相當(dāng)于 {?a 2,… ,?a k}的 (r1)組合 (k1個(gè)不同元素 ), ?因此包含 a1 的 r組合數(shù)是 C((k1)1+(r1),r1)=C(k+r3,r1)。 ? (2)不包含 a1的 r組合 , ?相當(dāng)于 {?a 2,… ,?a k}的 r組合 (k1個(gè)不同元素 ), ?因此不包含 a1 的 r 組合數(shù)是 C((k1)1+r,r)=C(k+r2,r)。 ?所以多重集 S={1a 1,?a 2,… ,?a k}的 r組合數(shù)是： ? C(k+r3,r1)+C(k+r2,r)。 ?關(guān)于有限多重集的組合問(wèn)題小結(jié)如下 : ?設(shè) S={n1a 1,n2a 2,… ,nka k} ，n=n1+n2+… +nk}， 則 S的 r組合數(shù) N滿足 : ?(1)若 rn， 則 N=0。 ?(2)若 r=n， 則 N=1。 ?(3)若 rn， 且對(duì)一切 i=1,2,… ,k有 ni?r， 則：N=C(k+r1,r) ?(4)若 rn， 且存在著某個(gè) nir,則對(duì) N沒(méi)有一般的求解方法 ， 可利用容斥原理予以解決 。 四、有序劃分和無(wú)序劃分 設(shè) S是 n個(gè)元素的集合。 Ai?S, Ai??,i=1,2,…t, 且 A1∪ A2∪ … ∪ At=S, Ai∩Aj=?(i,j=1,2,…,t,i ?j),則稱?={A1,A2,…,A t}是 S的一個(gè)劃分。 這里 {A1,A2,…,A t}是一個(gè)集合，即是無(wú)序劃分。 如果塊與塊之間有先后次序之分，則記為（ A1,A2,…,A t），為 S的一個(gè) t塊有序劃分。 ? ?定義一：設(shè) S是 n個(gè)元素的集合 ，{A1,A2,… ,At}是 S的一個(gè) t塊劃分 。 則(A1,A2,… ,At)為 S的 t個(gè)塊的一個(gè)有序劃分 ?要說(shuō)明的是給出一個(gè)劃分 {A1,A2,… ,At}，可以構(gòu)造 t個(gè)塊的多個(gè)有序劃分 。 ?例： S={a,b,c,d}, A1={a,b},A2={c},A3=
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1