一道有序集組計數賽題的求解與變式

●龔新平 (育才中學 上海 201801)

有序集組(A1，A2，…，Ak)計數問題在各類競賽中經常出現，在剛結束的2009年上海市高中數學競賽(新知杯)試題中就出現了一道有序集組的計數問題!本文對該問題進行了簡要地分析解答，并在此基礎上提出10個相關的變式問題，希望能拋磚引玉，對讀者解決此類問題有所啟發.

問題 設 A，B 是集合{a1，a2，a3，a4，a5}的 2個不同子集，使得A不是B的子集，B也不是的A子集，求不同的有序集組(A，B)的組數.

(2009年上海市數學競賽試題)

解法1 由集合{a1，a2，a3，a4，a5}共有 25個不同子集知，不同的有序集組(A，B)共有25(25-1)組;若A?B，當集合B含k(1≤k≤5)個元素時，滿足A?B的有序集組(A，B)共有

組，同理滿足B?A的有序集組(A，B)也共有(35-25)組，故滿足A不是B的子集且B也不是A的子集的有序集組(A，B)的組數為

解法2 由集合{a，a，a，a，a}共有 25個

12345不同子集，不同的有序集組(A，B)共有25(25-1)組;考慮滿足A?B的有序集組(A，B)的組數.每個元素 ai(i=1，2，3，4，5)均有 3 種歸屬：A，(B∩)，，故共有 35組(A，B)滿足 A?B，排除其中A=B的25組，共有(35-25)組有序集組(A，B)滿足A?B;同理有(35-25)組有序集組(A，B)滿足B?A，故滿足題意的有序集組(A，B)的組數為

推廣 設A，B是集合{a1，a2，…，an}的2個不同子集，A不是B的子集，B也不是A的子集，則不同的有序集組(A，B)的組數為

變式1 設 A，B，C 是集合{a1，a2，…，an}的 3個不同子集，且A不是B的子集，A也不是C的子集，求不同的有序集組(A，B，C)的組數.

解由A不是(B∪C)的子集知：

變式2 設A，B是數集{a1，a2，…，an}的2個不同子集，且A中每個元素都大于B中的所有元素，求不同的有序集組(A，B)的組數.

變式3 設A，B是集合{a1，a2，…，an}的2個不同子集，且滿足 A∪B={a1，a2，…，an}，求不同的有序集組(A，B)的組數.

解對于 ai=(i=1，2，…，n)有3種歸屬：(A∩)，(A∩B)，(∩B)，因此滿足 A∪B={a1，a2，…，an}的有序集組(A，B)的組數為 3n.

變式4 若 A∪B∪C={a1，a2，…，an}，且每個 ai(i=1，2，…，n)恰好屬于 A，B，C 中的2 個集合，求有序集組(A，B，C)的組數.

解對每個 ai(i=1，2，…，n)屬于 A，B，C 中的某2個時有C23種歸屬，因此有序集組最多有3n組，但需排除A，B，C中恰有1個是φ的3種情形，故有序集組(A，B，C)的組數為(3n-3).

變式5 若 A，B，C 為集合{a1，a2，…，an}的子集，且滿足 A∩B∩C=φ，A∩B≠φ，A∩C≠φ，求不同的有序集組(A，B，C)的組數.

變式6 若非空集合 A，B，C，D滿足：A∪B∪C∪D={a1，a2，…，an}，且 A∩B∩C=φ，求有序集組(A，B，C，D)的組數.

解對每個 ai(i=1，2，…，n)屬于 A，B，C，D最多有24=16種歸屬，但需排除3種情形：(1)ai不屬于 A，B，C，D;(2)ai屬于 A，B，C 不屬于 D;(3)ai屬于 A，B，C，D.故 ai有(24-3)=13 種歸屬，從而滿足條件的(A，B，C，D)的組數為 13n.

變式7 集合 A1，A2，…，Ak是{a1，a2，…，ak}的k個子集，求滿足A1∩A2∩…∩Ak=φ的不同有序集組(A1，A2，…，Ak)的組數.

解對任意元素ai?(A1∩A2∩…∩Ak)時，共有(2k-1)種歸屬，故滿足條件的有序集組(A1，A2，…，Ak)的組數為(2k-1)n.

變式8 設 Ai(1≤i≤k)是{a1，a2，…，ak}的 k個子集，若a1∈(A1∪A2∪…∪Ak)，求不同的有序集組(A1，A2，…，Ak)的組數.

解由{a1，a2，…an}共有2n個不同子集，故有序集組(A1，A2，…，Ak)的個數最多為 2nk個;又集合{a1，a2，…，an}的不含 a1的子集共有 2n-1個，因此不含a1的有序集組(A1，A2，…，Ak)共有2(n-1)k個，即含 a1的有序集組(A1，A2，…，Ak)共有(2nk-2(n-1)k)=(2k-1)2(n-1)k組.

變式9 設 Ai(i=1，2，…，k)是{a1，a2，…，an}的 k個不同的子集，且 A1∪A2∪…∪Ak={a1，a2，…，an}，求不同的有序集組(A1，A2，…，Ak)的組數.

解對任意元素ai∈(A1∪A2∪…∪Ak)時，共有(2k-1)種歸屬，于是滿足條件的有序集組(A1，A2，…，Ak)的組數為(2k-1)n.

變式10 設 Ai(i=1，2，…，k)是(a1，a2，…，an)的k個不同的非空子集，且A1∪A2∪…∪Ak={a1，a2，…，Ak}，求不同的有序集組(A1，A2，…，Ak)的組數.

解對任意元素ai∈(A1∪A2∪…∪Ak)時，共有(2k-1)種歸屬，因此滿足條件的有序集組(A1，A2，…，Ak)的組數最多為(2k-1)n;但對于有序集組(A1，A2，…，Ak)中有 i個集合為 φ 時，共有(2k-i-1)n組不符合.由容斥原理知，不同的有序集組(A1，A2，…，Ak)組數為