計數問題中的轉化與構造

☉湖北省天門中學鄭月姣

計數問題中的轉化與構造

☉湖北省天門中學鄭月姣

計數問題是高考考查的一個基本問題，問題呈現方式多樣，較難入手·如何讓看似“雜亂無章”的問題“有章可循”，筆者想以轉化與構造的思路探討一下，下面舉例說明·

例1求滿足下列條件的集合M的個數·

（1）｛1｝?M?｛1，2，3｝；

（2）｛1，2，3｝?M?｛1，2，3，4，5，6，7，8，9，10｝；

（3）｛a1，a2，…，am｝?M?｛a1，a2，…，an｝（n＞m，n，m∈N*）·

解析：（1）列舉法可解決·符合條件的集合M為：

｛1｝，｛1，2｝，｛1，3｝，｛1，2，3｝，共4個·

第（2）、（3）小題、就不適合用列舉法了·觀察（1）中的規(guī)律：

設A=｛1｝，B=｛1，2，3｝，CBA=｛2，3｝·

CBA的子集為?，｛2｝，｛3｝，｛2，3｝·

集合M為A與CBA的某一個子集的并集·

所以集合M的個數等于CBA的子集的個數，求集合M的個數轉化為求CBA的子集的個數·而含n個元素的集合的子集為2n個·

所以（1）中符合條件的集合M的個數為22=4（個）·

（2）中符合條件的集合M的個數為210-3=128（個）·

（3）符合條件的集合M的個數為2n-m（個）·

例2（1）已知集合A，B滿足A∪B=｛1，2｝，則滿足條件的集合A，B有多少對？

（2）已知集合A，B滿A∪B=｛1，2，3，4，5，6，7，8，9，10｝，則滿足條件的集合A，B有多少對？

（3）已知集合A，B滿足A∪B=｛1，2，…，n｝，則滿足條件的集合A，B有多少對？

解析：（1）可以由列舉法解決·

A ?｛1｝｛1｝｛2｝｛2｝｛1，2｝｛1，2｝｛1，2｝｛1，2｝B｛1，2｝｛2｝｛1，2｝｛1｝｛1，2｝?｛1｝｛2｝｛1，2｝

共9對·

（2）、（3）列舉法就不適用了·

圖1

對于（1）可作如下的轉化·將1、2兩個數字填入圖1中的Ⅰ、Ⅱ、Ⅲ三個區(qū)域內，每個數字必須且只需填一個區(qū)域，按照這種方法，每一個方案就對應著一對集合A、B，而由排列組合的有關知識，不同的方案有3×3=32種·所以，滿足條件的集合A，B有32= 9對·

此法對于（2）、（3）也適用·所以問題（2）中有310對·問題③中有3n對·

例3設集合Pn=｛1，2，…，n｝，n∈N*，記f（n）為同時滿足下列集合A的個數：①A?Pn；②若x∈A，則2x?A；③若x∈CPnA，則2x?CPnA·

（1）求f（4）；

（2）求f（n）的解析式（用n表示）·

解析：（1）P4=｛1，2，3，4｝，符合條件的集合可以由列舉法解決·｛2｝，｛1，4｝，｛2，3｝，｛1，3，4｝·

（2）不能由列舉法解決，分析（1）中集合A中的元素，由條件①②③知：當1∈A時，2?A，2∈CP4A，4?CP4A，4∈A；當1?A時，1∈CP4A，2?CP4A，2∈A，4?A，4∈CP4A·

故2、4兩個偶數是否屬于A，由1是否屬于A確定，而1、3無限制條件，既可以屬于A，也可以不屬于A·因此，集合A的個數即等于｛1，3｝的子集的個數f（4）=22=4個·對于（2）任取偶數x∈Pn··

設x=m·2k，k∈N*，m為奇數·由條件①②③知：

若m∈A時，x∈A?k為偶數；

若m∈A時，x?A?k為奇數·

所以，x是否屬于A由奇數m是否屬于A確定·集合A中的元素只要確定Pn中每一個奇數是否屬于A，相應的偶數也可以隨之確定，設Qn為Pn中所有奇數組成的集合，Qn的子集個數即等于集合A的個數·當n為奇數時，Pn中有

小結：（1）綜上所述，將所要解決的問題記為集合A，要確定A中元素的個數卻難于直接確定，可以構造一個與之一一對應的集合B，而集合B中的元素個數方便計數，B中的元素個數等于A中的元素個數·

（2）在由具體到抽象的探討中，從具體問題出發(fā)，力爭找出問題的實質，尋求通解通法，由淺入深，由表及里，訓練學生研究性的思維品質，這是教學中應大力提倡的·

1·杜志建·2009～2013新高考五年匯編·數學（理科）［J］·烏魯木齊：新疆青少年出版社，2014·F