m*****f 发帖数: 1243 | 1 topcoder上的一道题, 有点进死胡同了,哪位指点我一下
n个数选m个无序唯一排列 P(n,m) 明显
例子, 3 10 6 7 9
n个数选m个有序唯一排列 C(n,m) 没问题
例子 3 6 7 9 10
n个数选m个无序不唯一排列 power(n,m) 也没问题
例子 3 9 9 7 3
问题是n个数选m个有序不唯一排列怎么计算? 答案是个很简单的公式, 但是我想不明
白.. | w*****n 发帖数: 74 | 2 (n+m-1)!/(n-1)!/m! ?
假如有5个数按照大小顺序排好,要从中选3个数,用*表示数之间的间隔,用r表示选择
的数字
rr*r*** 表示选2个1号数和1个2号数
那么问题变成在 5+3-1个位置中选三个位置
【在 m*****f 的大作中提到】 : topcoder上的一道题, 有点进死胡同了,哪位指点我一下 : n个数选m个无序唯一排列 P(n,m) 明显 : 例子, 3 10 6 7 9 : n个数选m个有序唯一排列 C(n,m) 没问题 : 例子 3 6 7 9 10 : n个数选m个无序不唯一排列 power(n,m) 也没问题 : 例子 3 9 9 7 3 : 问题是n个数选m个有序不唯一排列怎么计算? 答案是个很简单的公式, 但是我想不明 : 白..
| m*****f 发帖数: 1243 | 3 好像公式是对的, 请问
用*表示数之间的间隔,用r表示选择的数字
rr*r*** 表示选2个1号数和1个2号数
这段话能再解释下马? 什么叫数之间的间隔, rr*r***是代表六个位置?
【在 w*****n 的大作中提到】 : (n+m-1)!/(n-1)!/m! ? : 假如有5个数按照大小顺序排好,要从中选3个数,用*表示数之间的间隔,用r表示选择 : 的数字 : rr*r*** 表示选2个1号数和1个2号数 : 那么问题变成在 5+3-1个位置中选三个位置
| g*******y 发帖数: 1930 | 4 我没理解对题目?什么叫有序不唯一?给个definition呢?
按照我的理解:
3 3 7 9 9 n=5
选两个数 m=2
33, 99, 37, 39, 79 就5种
但是按那公式算出来是C(2,6) > 5 ? | m*****f 发帖数: 1243 | 5 3 7 9 n = 3
选两个数 m = 2
有
33, 37, 39
77, 79,
99
六种
C(n+m-1, m) = C(4,2) = 6 没错
但我还是想不明白为什么这么算...
【在 g*******y 的大作中提到】 : 我没理解对题目?什么叫有序不唯一?给个definition呢? : 按照我的理解: : 3 3 7 9 9 n=5 : 选两个数 m=2 : 33, 99, 37, 39, 79 就5种 : 但是按那公式算出来是C(2,6) > 5 ?
| w*****n 发帖数: 74 | 6 假如是以下5个数,在数之间用*隔开
3 * 6 * 9 * 11 * 13
rr * r * * * 表示选2个‘3’,1个‘6’
* rrr * * * 表示选 3个‘6‘
每个r都是一个位置所有总共有7个位置。
很难表达好,不知道这次清楚了吗
【在 m*****f 的大作中提到】 : 好像公式是对的, 请问 : 用*表示数之间的间隔,用r表示选择的数字 : rr*r*** 表示选2个1号数和1个2号数 : 这段话能再解释下马? 什么叫数之间的间隔, rr*r***是代表六个位置?
| g*******y 发帖数: 1930 | 7 你早说嘛。。。每个数字可以有任意多个
我还以为你只有从一个固定的pool里面取数出来
这样就简单多了。
其实就是把N-1个一模一样的隔板跟m个一模一样的球混和
【在 m*****f 的大作中提到】 : 3 7 9 n = 3 : 选两个数 m = 2 : 有 : 33, 37, 39 : 77, 79, : 99 : 六种 : C(n+m-1, m) = C(4,2) = 6 没错 : 但我还是想不明白为什么这么算...
| m*****f 发帖数: 1243 | 8 我明白了, 假设n个数字都是隔板, m个要放入隔板的球,放第一个有n种选择, 第二
个便有n+1中选择, 一直到最后n+m-1.
(n+m-1) * .... (n+1) * (n) / m! 就是 c(n+m-1,m)
倒着想就容易理解多了, 谢谢各位 | n******r 发帖数: 1247 | 9 通法是用母函数解
见例4
http://episte.math.ntu.edu.tw/articles/mm/mm_01_3_10/
【在 m*****f 的大作中提到】 : 我明白了, 假设n个数字都是隔板, m个要放入隔板的球,放第一个有n种选择, 第二 : 个便有n+1中选择, 一直到最后n+m-1. : (n+m-1) * .... (n+1) * (n) / m! 就是 c(n+m-1,m) : 倒着想就容易理解多了, 谢谢各位
|
|