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

2015/01/08 by Mansour, Toufik, Mirzavaziri, Madjid, Yaqubi, Daniel
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1501.01997

Abstract

Let n be a non-negative integer and A=\a₁,…,a_k\ be a multi-set with k not necessarily distinct members, where a₁\leqslant…\leqslant a_k. We denote by Δ(n,A) the number of ways to partition n as the form a₁x₁+…+a_kx_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 Δ(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.

Related

• The number of s-separated k-sets in various circles
• Minimally Intersecting Set Partitions of Type B
• Intersection theorems for multisets
• Hilton-Milner theorem for k-multisets
• Non-trivially intersecting multi-part families