关于 prufer 序列
  • 板块学术版
  • 楼主x义x
  • 当前回复5
  • 已保存回复5
  • 发布时间2020/11/21 11:35
  • 上次更新2023/11/5 07:37:22
查看原帖
关于 prufer 序列
58567
x义x楼主2020/11/21 11:35

求满足以下条件的有标号有根树的数量：给定一个序列 m0,...,mn−1m_0,...,m_{n-1}，树中出度为 ii 的节点数量必须为 mim_i。

根据 prufer 序列我们容易得到答案为

(nm0,m1,...)(n−1)!∏i!mi{n\choose m_0,m_1,...}\dfrac{(n-1)!}{\prod i!^{m_i}}

而如果把题目中的“有标号有根树”换成“括号序列”（点没有标号，儿子之间有序的树），我们直接拉反也可以得到答案为

(nm0,m1,...)1n{n\choose m_0,m_1,...}\dfrac{1}{n}

那么这是否意味着“括号序列”的情况下也有类似 prufer 序列的从树到序列的双射呢？可能是我最近脑子坏了，反正就是没想出来，求解答 qaq

2020/11/21 11:35