几个排列组合计数的变式问题

原问题:

可重复选择的组合。有n个不同元素,每个元素可以选多次,一共选k个元素,有多少种方法。

刘汝佳; 陈锋. 算法竞赛入门经典——训练指南 (算法艺术与信息学竞赛) (Kindle位置1683). 清华大学出版社. Kindle 版本.

解:ANS = C(n+k-1,  n-1)。可以用方程的解的思路来做。

变式:

  1. 有n个不同元素,每个元素可以选多次,一共选k个元素排成一排,有多少种排法。
  2. 有n个元素,每个元素有ni个,每个元素可以选[0,ni]个,一共选k个元素,有多少种方法。
  3. 有n个元素,每个元素有ni个,每个元素可以选[0,ni]个,一共选k个元素排成一排,有多少种排法。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注