排列组合

本文主要是介绍排列组合，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一·不定方程解的个数

例：一个商场有m种颜色的小球，每种小球足够多，在这m种小球中挑选n个小球的选法有多少？

一道纯纯的数学题对吧。

由题目，我们可以知道\(\sum_{i=1}^n a[i]=n\)，我们将n分成若干个1

1.解都为正整数

挑选不同颜色的小球，可理解为在这一串1里插入m-1个隔板，每个被隔开的区间即为各种颜色的各自的数量，如上图所示
所以答案为\(C_{n-1}^{m-1}\),即从n-1个间隔中插入m-1个隔板

2.解都为非负整数

我们要注意的是，某一种颜色的小球可以为0,即多个隔板可以放在同一个位置，而这种特殊情况，可以通过加1的方法消除这种情况，即每个颜色的区间里多加一个1。以下为说明：
\(\sum_{i=1}^n a[i]=n\)可以转化为\(\sum_{i=1}^n b[i]=n+m\),其中b[i]=a[i]+1。这两者是等价的对吧。所以对于第二个式子的解的个数即为答案，那么又通过1中所证，答案即为\(C^{m-1}_{n+m-1}\)

这篇关于排列组合的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！