排列組合 I 解決計(jì)數(shù)問(wèn)題的方法
- 計(jì)數(shù)——與整數(shù)的對(duì)應(yīng)關(guān)系
計(jì)數(shù)就是計(jì)數(shù)對(duì)象和整數(shù)的對(duì)應(yīng)起來(lái)的過(guò)程，注意兩點(diǎn)：
- 遺漏
- 重復(fù)
如果需要計(jì)數(shù)的對(duì)象多到無(wú)法數(shù)數(shù)，就需要找到和整數(shù)之間的對(duì)應(yīng)規(guī)則，為此，我們必須理解計(jì)數(shù)對(duì)象具有怎么樣的特性和結(jié)構(gòu)
- 思考：植樹(shù)問(wèn)題，在10米長(zhǎng)的路上，從路的一端起每隔1米種一棵樹(shù)，那么需要種多少棵樹(shù)？
0,1,2,...10 不要忘記0哦，所以是11棵樹(shù)
10/1的結(jié)果是間隔數(shù)
抽象 n米種樹(shù)n+1棵
- 思考：內(nèi)存中排列著程序要處理的100個(gè)數(shù)據(jù)，從第一個(gè)數(shù)據(jù)開(kāi)始編號(hào)為0，依此類(lèi)推最后一個(gè)數(shù)據(jù)的編號(hào)是？
99號(hào)
歸納總結(jié) 第k個(gè)數(shù)據(jù)是k-1號(hào)
加法法則
加法法則就是將無(wú)“重復(fù)”元素的兩個(gè)集合A，B相加，得到A和B并集的元素?cái)?shù)
- A并B的元素?cái)?shù) = A的元素?cái)?shù) + B的元素?cái)?shù)
- 加法法則只在集合中元素?zé)o重復(fù)的條件下成立
容斥原理
- 思考：控制亮燈的撲克牌，一副牌有(1->K)13個(gè)級(jí)別，假設(shè)J,Q,K用11,12,13代替，在你面前放一個(gè)裝置，往里面放1張牌，它就會(huì)根據(jù)牌的級(jí)別控制燈泡的亮滅。我們?cè)O(shè)放入的牌的級(jí)別為n(1-13的整數(shù))
- 若n是2的倍數(shù)，則亮燈
- 若n是3的倍數(shù)，也亮燈
- 若n既不是2的倍數(shù)，也不是3的倍數(shù)，則滅燈
往這個(gè)裝置中依次放入13(1...13)張牌，其中亮燈的有多少?gòu)埮颇兀?/li>
答案：6+4 -2 = 8
利用了容斥原理，2的倍數(shù)和3的倍數(shù)如果有重復(fù)的倍數(shù)，就是6，6的倍數(shù)有兩次→6,12 2的倍數(shù)的個(gè)數(shù)6加上3的倍數(shù)的個(gè)數(shù)4，減去重復(fù)的倍數(shù)的個(gè)數(shù)2，就是答案
- 容斥原理就是考慮了重復(fù)元素的加法法則
集合A、B的元素總和 = A的元素?cái)?shù) + B的元素?cái)?shù) - A和B共同的元素?cái)?shù)
乘法法則
根據(jù)兩個(gè)集合進(jìn)行配對(duì)的法則
- 思考：一副牌中四種花色，每個(gè)花色13張牌，那么總共有幾張牌？
4 * 13 = 52
A和B兩個(gè)集合，所有元素分別結(jié)合起來(lái)，組合的總數(shù)就是相乘得到的結(jié)果
- 思考：將三個(gè)骰子(1-6點(diǎn))并列放置，形成3位數(shù)，一共能形成多少個(gè)數(shù)字？
沒(méi)錯(cuò)，6 * 6 * 6 = 216
- 思考：32個(gè)燈泡一排，每個(gè)燈泡可以亮滅，問(wèn)共有多少種亮滅模式
每一種2個(gè)，2x2x2......2(共32個(gè))
2^32＝4294967296
置換
將n個(gè)事物按順序進(jìn)行排列稱(chēng)作置換(subsitution)
- 思考：3張牌的置換，如果將A,B,C三張牌按照ABC,ACB,BAC等順序排列，共有多少種排法？
6種
可以看出，第一張牌有3種選法，第二張牌有2種，第三張牌有1種，3 * 2 * 1 = 6
對(duì)，這就是階乘1!=1 2!=2 3!=6 4!=24
排列組合II
- 思考：從5張牌中任意取出3張進(jìn)行排列，請(qǐng)問(wèn)有多少種排列方法？
答案明天揭曉~
