排列组合

来自 吴语维基百科
蹦到: 导航搜寻

组合数学中的著名问题[编辑]

  • 計算一些物品在特定條件下分組的方法數目。這些是關於排列組合整數分拆的。
  • 地图着色问题:对世界地图着色,每一個国家使用一种颜色。如果要求相邻国家的颜色相异,是否总共只需四种颜色?這是圖論的問題。
  • 船夫过河问题:船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场,羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河?這是線性規劃的問題。
  • 中国邮差问题:由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次,怎样行走走过的路程最短?这不是一个NP完全问题,存在多项式复杂度算法:先求出度为奇数的点,用匹配算法算出这些点间的连接方式,然后再用欧拉路径算法求解。這也是圖論的問題。
  • 任务分配问题(也称婚配问题):有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少?這是線性規劃的問題。
  • 如何構作幻方
  • 大樂透

排列[编辑]

主条目:排列
3个彩球的排列(不重复出现)

排列个任务是定落来n个不一色一样个元素个排序概率。家手边个示意图可以看出来,3个不同颜色个球搭了一道儿生有6种不一色一样个的排列法子,∴有下底个种定理嘞:「n个不一色一样元素可以有n !种不一色一样个排列法子,即n阶乘。」噶套一来,高头个例子个算法转肯定是3 ! = 6。
另外一道题目啦,如果从n个元素里向窦出来k个元素个嗦倭,举个k个元素个排列算出来结果是多少伲?公式啦哈下底嘞:

 P_n^k = \frac{n!}{(n-k)!}

比方窝,啦哈赌马个活动里向加起来有8匹马参加比赛,赌博个您要啦哈票子高头写进前头三个赢个马各自滴号码,按照高头个公式,n = 8,k = 3,赌博个您一共好写进的个匹马号个排列数字是:

 P_8^3 =\frac{8!}{(8-3)!}=336

因为一共有336种可能性嘞,所以窝玩家啦哈一次填入就中奖个概率会的是:

 P = \frac{1}{336}= 0.00298

啦哈前头我伲提到个皆是啦哈k没重复个情况下底个排列。

如啦哈n个元素里向窦出k个元素去排列个嗦倭,个么k个元素可以重复显现,噶套个话语排列数就有下底举个公式的嘞:

n^k

还是高头个例子,k可以重复显现,个就说明赌博个您好啦哈前三名个位置上填进同一匹马个号数,个么啦哈这种情况下底可能出现的排列总数是:

83 = 512

另外,n^k阿可以記為[1]

 U_n^k = n^k[1]

个辰光,一次性加进去中奖个概率就会的是:

P=\frac{1}{512}=0.002(大家来东隔得要注意的嘞,同一匹马啦哈同一辰光得1,2,3名个情况啦哈生活里头是不存在个)

另一个数字技术的例子,在二进制中只有0搭1两种可能性,一个有x位个二进制数字好有2x种排列法子,啊好来表示2x个不一色一样个数字伲。

组合[编辑]

主条目:組合

和排列不同的是,在组合中取出元素的顺序则不在考虑之中。从n个元素中取出k个元素,这k个元素可能出现的组合数为:

C_n^k ={n \choose k} = \frac{P_n^k}{k!} = \frac{n!}{k!(n-k)!}

最常见的例子应该是六合彩游戏了。在六合彩游戏中从49个球中取出6个进行组合的可能性一共有:

C_{49}^{6}  = {49 \choose 6} = \frac{49!}{6!43!} = 13983816

如同排列,上面的例子是建立在如下前提的(即球从摇奖机中出来后不再放回去,或者说组合不发生重复),但如果球摇出来后再放回摇奖机中,这时的组合的可能性则是:

H_n^k = C_{n+k-1}^{k} = {n+k-1 \choose k}

类似的例子比如连续掷两次骰子,获得的两个点数的组合可能性一共有:

H_6^2 = C_{6+2-1}^{2} = {6+2-1 \choose 2} = C_7^2 = \frac{7!}{2!5!} = 21

另外H_n^r也可以記為[2]

F_n^r = H_n^r = C_{n+r-1}^{r} = {n+r-1 \choose r}[2]

归类[编辑]

排列
{ a,b } ≠ { b,a }
(考慮次序个)
组合
{ a,b } = { b,a }
(弗考慮次序个)
不重复个(不放回去滴)
{ a,b,c }
P_n^k C_n^k
重复个(再放回去一毛)
{ a,a,b }
n^k \,  H_n^k


引用错误:<ref>标签存在,但没有找到<references/>标签