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)
: 倒着想就容易理解多了， 谢谢各位
|
|
