指数型母函数 简介

母函数分:普通型母函数指数型母函数

普通型母函数主要是来求组合的方案数,而指数型母函数是求多重排列数。

关于普通型母函数的讲解,以前写过:

http://www.wutianqi.com/?p=596

而指数型母函数主要是关于排列组合方面的问题。

分别看两个比较典型的问题对比:

普通母函数问题:有红球两个,白球、黄球各一个,试求有多少种不同的组合方案。

指数型母函数问题:
假设有8个元素,其中a1重复3次,a2重复2次,a3重复3次。从中取r个组合,求其组合数。

下面是指数型母函数的定义

对于上面的问题“假设有8个元素,其中a1重复3次,a2重复2次,a3重复3次。从中取r个组合,求其组合数。”:

(感谢 3Dnn 同学指出,下图的 28/3! 应该改为 26/3!)

代表:

HDOJ 1521 排列组合

http://acm.hdu.edu.cn/showproblem.php?pid=1521

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《指数型母函数 简介》有9个想法

  1. 有一个地方学长似乎算错啰。。

    最后的(28/3!)*x^3应该是(26/3!)*x^3吧。。

    数据就是:

    3 3
    3 2 3

    结果应该是26而不是28

    【这里有时候会看不见图片,但有个人转载你的可以看的看不了的同学去这里哦~】
    【http://blog.sina.com.cn/s/blog_79b832820100x8pa.html】

    1. 你看上面第二个图的第一项:
      (1+x/1! + x^2/2! + x^3/3!)
      题目说a重复3次,而又要从a,b,c中取r次,因为这里是排列组合的问题,高中学过,要除以阶乘来防止多次求解,x^2/2!表示a取2个的情况,除以2表示排列组合去除重复情况。
      这里你好好理解下。不难。

  2. 指数型母函数问题:
    假设有8个元素,其中a1重复3次,a2重复2次,a3重复3次。从中取r个组合,求其组合数。

    这里的组合数是指取A和B时组合成AB和BA吗?那就hdu1521来说,如果输入
    3 3
    3 2 3
    不熟应该输出28吗?怎么就26呢?

发表评论

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