7个数加起来180有多少种方法?

机器算法验证 可能性 组合学 选举
2022-04-14 12:49:16

农夫有 7 头猪和 180 个土豆。分配这 180 个土豆有多少种组合?顺序无所谓。每头猪可以得到 0 到 180 个土豆,但所有 7 头猪必须正好得到 180 个土豆(不少于)。一般如何解决这个问题:存在多少个 K 集合的组合,它们的总和正好为 N?

我想在选举数学领域应用该解决方案来计算选举逆转的概率。思考如果无效选票(土豆)是有效的以及它们是否分布在竞争候选人(猪)之间会发生什么。

这是类似的东西,但没有必须吃掉所有土豆的条件。 https://stackoverflow.com/questions/4588429/number-of-ways-to-add-up-to-a-sum-s-with-n-numbers 此外,它已通过递归函数解决,而不是优雅公式。

1个回答

反过来看你的问题:你有k猪,你正在用替换画n其中,每次抽到猪时,都会给它一个土豆。因此,马铃薯在猪之间的分布遵循多项分布,每头猪的概率相等。

至于这些集合的组合数量,这是关于multisets组合星条形问题,所以有

((n+1k1))=(n+k1n)

这样的组合。

经典的星条形问题可以描述如下:你有n星星分为k多组。这可以认为是加星k1标记组边界的附加条,然后随机打乱所有对象,例如

||||

现在你只需要计算重新排列的次数n+k1对象。