The Twelvefold way, the non-intersecting circles problem, and partitions of multisets

Abstract

Let $n$ be a non-negative integer and $A=\{a_1,\dots ,a_k\}$ be a multi-set with $k$ not necessarily distinct members, where $a_1⩽\dots ⩽a_k$. We denote by $\Delta (n,A)$ the number of ways to partition $n$ as the form $a_1{x}_1+\dots +a_k{x}_k$, where $x_i$'s are distinct positive integers and $x_i<x_{i+1}$ whenever $a_i=a_{i+1}$. We give a recursive formula for $\Delta (n,A)$ and some explicit formulas for some special cases. Using this notion we solve the non-intersecting circles problem which asks to evaluate the number of ways to draw $n$ non-intersecting circles in a plane regardless to their sizes. The latter also enumerates the number of unlabelled rooted tree with $n+1$ vertices.

partitions of multisets