多项式系数学习笔记

今天刚学的东西，简单记一下

多项式系数

对于多项式$(x_1 + x_2 + x_3 + \dots + x_k) ^n$的展开式中$x_1^{d_1}x_2^{d_2}x_3^{d_3} \dots x_k^{d_k}$这一项(满足$d_1 + d_2 + d_3 + \dots + d_k = N$)的系数，记做

${\binom{n}{d_1,d_2,d_3, \dots, d_k}} = \frac{n!}{d_1!d_2!d_3! \dots d_k!}$

组合意义

将$n$个可分辨的球放到$m$个不同的盒子$T_1, T_2, \dots T_m$中，在$T_i$中放$d_i$个，不记盒内的次序，且满足$\sum_{i = 1}^m d_i= N$的方案数为$${\binom{n}{d_1,d_2,d_3, \dots, d_k}}$$

一道题目

给你一棵n个节点的有根树。你要给每个节点分配一个$1 \sim n$的数字，使得每个节点分配的数字不同，并且每个节点分配的数字都是它子树内最小的。求方案数。

设$f[i]$表示在以$i$为根的子树内放了$1 \sim siz[i]$的方案数

转移的时候，根节点肯定放了$1$号元素

那么

$f[i] = \binom{siz[i] - 1} {e siz[u_1], siz[u_2], \dots siz[u_k]} \prod f_{u_i}$

直接把$1$号节点的dp值展开之后得到

$ans = n! \prod \frac{1}{siz[i]}$