Tewelvefold way

摘要

今天我们来探讨一道综合计数题。

问题描述

n个有标号/无标号的球分给m个有标号/无标号的盒子,盒子有三种限制:

A. 无限制
B. 每个盒子至少有一个球
C. 每个盒子至多一个球

共12种问题。问方案数。(所有球都要放)

为了方便,将有标号的记为L(labelled),无标号的记为U(unlabelled)。一个问题可以缩写为3个字母。

Section 1

LLA

n个有标号的球分给m个有标号的盒子,无限制。那么每一个球有 种选择,于是总方案数是

LLB

n个有标号的球分给m个有标号的盒子,每个盒子至少一个球。考虑容斥,全集大小 ,问题转化为至少一个盒子没有球的方案数。

于是 减掉容斥的部分得到

LLC

n个有标号的球分给m个有标号的盒子,每个盒子至多一个球。

显然当 时无解,否则答案为排列

Section 2

ULA

n个无标号的球分给m个有标号的盒子,无限制。这可以看作一个不定方程非负整数解的个数的问题。使用插板法,答案为

ULB

n个无标号的球分给m个有标号的盒子,每个盒子至少一个球。等价于方程正整数解的个数。答案即为

ULC

n个无标号的球分给m个有标号的盒子,每个盒子至多一个球。

组合数问题,如果 则无解,否则答案为

Section 3

LUA

n个有标号的球分给m个无标号的盒子,无限制。那么我们枚举有几个盒子是非空的,转化为LUB。答案为

LUB

n个有标号的球分给m个无标号的盒子,每个盒子至少一个球。这样就是把一个大小为 的集合分成 个非空子集的方案数,即第二类斯特林数

LUC

n个有标号的球分给m个无标号的盒子,每个盒子至多一个球。

如果 无解,否则你就放。答案为

Section 4

UUA

n个无标号的球分给m个无标号的盒子,无限制。

枚举有几个非空盒子,转化为UUB,答案为

UUB

n个无标号的球分给m个无标号的盒子,每个盒子至少一个球。

即把 划分为m个部分的方案数,即拆分数

UUC

n个无标号的球分给m个无标号的盒子,每个盒子至多一个球。

答案即为


  转载请注明: Sshwy's Blog Tewelvefold way

 上一篇
斐波那契数列 斐波那契数列
斐波那契数列(The Fibonacci sequence,OEIS A000045)的定义如下: F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}该数列的前几项如下: 0, 1, 1, 2, 3, 5
2019.07.21
下一篇 
笛卡尔树 笛卡尔树
摘要 本文介绍一种不太常用,但是与大家熟知的平衡树与堆密切相关的数据结构——笛卡尔树。 笛卡尔树是一种二叉树,每一个结点由一个键值二元组 构成。要求 满足二叉搜索树的性质,而 满足堆的性质。一个有趣的事实是
2019.07.18
  目录