In this paper, we prove a surprisingly simple formula that counts connected cycle-free families of set partitions, labelled free cacti and coloured Husimi graphs in which there are no blocks of the same colour that are incident to one another. We also provide a formula that enumerates noncrossing connected, cycle-free pairs of partitions.
Let \(I\) be an index set. For \(i\in I\), let \(S_i\) be a non-empty subset of a finite set \(S.\) The union of all \(S_i\) gives \(S.\) Now, let \(P_i\) be a set partition of \(S_i\) and let \(\mathcal{P}=\{P_i: i\in I\}\) denote the family of such partitions. We define a multigraph \(G_{\mathcal{P}}\) as having vertex set \[\{(P,p):P\in \mathcal{P}, p\in P\},\] and two distinct vertices \((P_1,p_1)\) and \((P_2,p_2)\) are joined by \(|p_1\cap p_2|\) edges in the edge set. This ensures that \(G_{\mathcal{P}}\) has no loops. The family \(\mathcal{P}\) of set partitions is said to be connected if \(G_{\mathcal{P}}\) is connected and cycle-free if the multigraph is cycle-free. This definition was first provided by Teufl and Wagner [18]. In the sequel, we prove the main result of this paper.
Theorem 1.1(Main Theorem).The number of connected, cycle-free families of \(k\) set partitions of \([n]\) is given by \[\begin{aligned} \label{family} \dfrac{n!n^{k-2}\prod_{i=1}^{k}(\ell_i-1)!}{\prod_{i=1}^{k}\prod_{j\geq 1}(j-1)!^{a_{ij}}a_{ij}!}, \end{aligned} \tag{1}\] where \(\ell_{i}\) is the number of blocks in the \(i\)-th partition and \(a_{ij}\) is the number of blocks of size \(j\) in the \(i\)-th partition such that \(\sum\limits_{i=1}^{k}\ell_{i}=(k-1)n+1\).
Proof. The case \(k=2\) was proved by Teufl and Wagner in [18]. Let us first consider the case in which all the \(k\) partitions are of the shape \(m_i^{1}1^{n-m_i}\) for \(i=1,\ldots,k\) respectively. Since the partitions are cycle-free and connected, i.e. two blocks from distinct partitions have at most one point in common, the \(k\) set partitions form a ’tree’ if we ignore the singletons. Such a tree is called a generalised tree. Let \(y_i\) mark the number of blocks of size \(i\) in the generalised tree. Let \(T(x)\) be the exponential generating function for the number of rooted labelled generalised trees. Now, the vertices in the block other than the root are given the structure of a ’forest’ of rooted generalised trees. The exponential generating function enumerating the forests is equal to \[\exp \left(\sum\limits_{i=1}^{\infty}y_{i+1}\dfrac{T(x)^{i}}{i!}\right).\]
So, the exponential generating function for the number of rooted generalised trees satisfies \[\begin{aligned} T(x)=x\exp \left(\sum\limits_{i=1}^{\infty}y_{i+1}\dfrac{T(x)^{i}}{i!}\right), \end{aligned}\] i.e., the roots of the trees in the forest are attached to a common root to form a tree.
By the Lagrange Inversion Formula [17, Theorem 5.4.2], we have \[\begin{aligned} T(x)&=\dfrac{1}{n}[t^{n-1}]\exp \left(n\sum\limits_{i=1}^{\infty}y_{i+1}\dfrac{t^{i}}{i!}\right)=\dfrac{1}{n}[t^{n-1}]\sum\limits_{j\geq 0} \dfrac{n^j}{j!} \left(\sum\limits_{i=1}^{\infty} y_{i+1}\dfrac{t^{i}}{i!}\right)^{j}\\&=\dfrac{1}{n}[t^{n-1}]\sum\limits_{j\geq 0} \dfrac{n^j}{j!} \left( y_{2}\dfrac{t}{1!}+y_{3}\dfrac{t^2}{2!}+y_{4}\dfrac{t^3}{3!}+\cdots\right)^{j}. \end{aligned}\]
It follows that \[\begin{aligned} T(x)&=\dfrac{1}{n}[t^{n-1}]\sum\limits_{j\geq 0} \dfrac{n^j}{j!}\sum\limits_{j_1+j_2+\cdots =j}\dfrac{j!}{j_1!j_2!\cdots} \left( y_{2}\dfrac{t}{1!}\right)^{j_1}\left(y_{3}\dfrac{t^2}{2!}\right)^{j_2}\cdots \\&=\sum\limits_{j\geq 0} \sum\limits_{\substack{j_1+j_2+\cdots =j \\ j_1+2j_2+\cdots =n-1}}\dfrac{n^{j-1}}{j_1!(1!)^{j_1}j_2!(2!)^{j_2}\cdots}y_{2}^{j_1}y_{3}^{j_2}\cdots. \end{aligned}\]
The generating function for unrooted generalised trees on \(n\) vertices and \(j_i\) blocks of size \(i\) is therefore given by, \[\begin{aligned} n!\prod_{i=1}^{\infty} \dfrac{y_{i+1}^{j_i}}{j_i!(i!)^{j_i}}n^{\sum{j_i}-2}. \end{aligned}\]
We multiply by \(n!\) since we are dealing with an exponential generating function.
Since \(\sum{j_i}=k,\) we obtain that the number of families of \(k\) partitions of the shape \(m_i^{1}1^{n-m_i}\) for \(i=1,\ldots,k\) is given by \[\begin{aligned} \dfrac{n!n^{k-2}}{\prod_{i=1}^{k}(m_i-1)!}. \end{aligned}\]
From the \(k=2\) case (see [18] for details), we know that, given partitions \(P_1, P_2,\ldots, P_{k-1}\) and the type of \(P_k,\) the number of possibilities for \(P_k\) to complete a connected cycle-free partition is of the form \[\alpha(P_1, P_2,\ldots, P_{k-1})\cdot \beta(\text{type}(P_k)),\] where \(\beta\) is known and only depends on the type of \(P_k\) (not \(P_1, P_2,\ldots, P_{k-1}\)). Thus changing the type \(\lambda _{k}\) to a type \(\lambda'_{k}\) only produces a factor \(\displaystyle\dfrac{\beta(\lambda'_k)}{\beta(\lambda_k)}\).
The number of families of two connected cycle-free set partitions of types \(\lambda_0=m_0^{1}1^{n-m_0}\) and \(\lambda_1=1^{a_{11}}2^{a_{12}}\cdots\) such that \(\sum\limits_ja_{1j}=\ell_1\) is given by \[\begin{aligned} \gamma(\lambda_0,\lambda_1)=\dfrac{n!(\ell_1-1)!}{(m_0-1)!\prod_{j\geq 1}((j-1)!)^{a_{1j}}a_{1j}!}. \end{aligned}\] (See [18, Theorem 5.1].)
Similarly, if \(\lambda_2=m_1^{1}1^{n-m_1}\) then, \[\begin{aligned} \gamma(\lambda_0,\lambda_2)=\dfrac{n!}{(m_0-1)!(m_1-1)!}. \end{aligned}\]
We therefore have \[\begin{aligned} \dfrac{\gamma(\lambda_0,\lambda_1)}{\gamma(\lambda_0,\lambda_2)}=\dfrac{\beta(\lambda_1)}{\beta(\lambda_2)}=\dfrac{(m_1-1)!(\ell_1-1)!}{\prod_{j\geq 1}((j-1)!)^{a_{1j}}a_{1j}!}. \end{aligned}\]
The number of connected cycle free families of \(k\) set partitions such that the first partition is \(\lambda_1=1^{a_{11}}2^{a_{12}}\cdots\) and the subsequent \(k-1\) set partitions are of the shape \(m_i^{1}1^{n-m_i}\) for \(i=2,\ldots,k\) is therefore given by \[\begin{aligned} \dfrac{n!n^{k-2}}{\prod_{i=1}^{k}(m_i-1)!}\cdot \dfrac{(m_1-1)!(\ell_1-1)!}{\prod_{j\geq 1}((j-1)!)^{a_{1j}}a_{1j}!}, \end{aligned}\]where \(\ell_1\) is the number of parts in \(\lambda_1\), and \(a_{1j}\) is the number of parts of size \(j\) in \(\lambda_1\).
Iterating this idea, we obtain the required equation. This proves Theorem 1.1. ◻
The relationship between labelled trees on \(n\) vertices and the symmetric group \(S_n\) of order \(n\) was discovered by Dénes [3] and subsequent work on the same has since been done by Moszkowski [13], Eden and Schützenberger [4], and Goulden and Pepper [8] among many other authors. A \(k\)-cactus is a connected (simple) graph in which every edge lies on exactly one \(k\)-cycle. Such a cycle will be called a \(k\)-gon. A \(k\)-cactus is said to be planar if it is embedded in the plane such that every edge is part of the unbounded region. A planar \(k\)-cactus is edge-rooted if one of the edges is distinguished as a root and it is of size \(n\) if there are \(n\) \(k\)-gons. We colour the vertices of a \(k\)-cactus with \(k\) colours such that in a \(k\)-gon, colour \(i\) is used at most once. We say that \((\ell_1,\ldots,\ell_k)\) is a vertex-colour distribution of the \(k\)-cactus if there are \(\ell_i\) vertices of colour \(i\) for all \(i=1,\ldots,k.\) The number of \(k\)-gons that are incident to a vertex is the degree of such a vertex. We also say that \((a_{ij})_{1\leq i\leq k, j\geq 0}\) is a vertex-degree distribution of the \(k\)-cactus where \(a_{ij}\) is the number of vertices of colour \(i\) and degree \(j.\) We note that \(\ell_i=\sum\limits_{j\geq 0}a_{ij}\). The following two lemmas are proved in [2].
Lemma 2.1. There exists a \(k\)-ary cactus on \(N\) vertices and \(n\) \(k\)-gons if and only if \(N=(k-1)n+1.\)
Lemma 2.2. Let \(A=(a_{ij})_{1\leq i\leq k, j\geq 0}\) be a \(k\times \infty\) matrix of non-negative integers, and set \(N=\sum\limits_{ij}a_{ij}.\) There exists a \(k\)-ary cactus having \(N\) vertices and \(n\) \(k\)-gons and whose vertex-degree distribution is given by the matrix \(A\) if and only if
1. \(n=(N-1)/(k-1)\) is an integer,
2. \(\displaystyle\sum\limits_{j}ja_{ij}=n,\) for all \(i,\)
3. \(n\geq 1 \Rightarrow a_{i0}=0,\) for all \(i.\)
Let \(\lambda=1^{k_1}2^{k_2}\cdots\) be a partition of \(n\geq 1\). We denote the length of the partition by \(l(\lambda)=k_1+k_2+\cdots\). The following theorem is due to Goulden and Jackson [7]. The case \(k=2\) was proved by Bédard and Goupil [1] using an induction argument.
Theorem 2.3. [7, Theorem 3.1]Let \(\lambda_1,\ldots,\lambda_k\) be partitions of \(n\) such that \(l(\lambda_1)+\cdots+l(\lambda_k)=(k-1)n+1.\) Then there is a bijection between planar edge-rooted \(k\)-cacti on \(n\) \(k\)-gons with vertex-colour distribution \(\lambda_i,\) \(i=1,\ldots,k,\) and \(k\)-tuples \((\alpha_1,\ldots,\alpha_k)\) of permutations in the symmetric group \(S_n\) with cycle distributions \(\lambda_1,\ldots,\lambda_k\) respectively, such that \(\alpha_1\cdots\alpha_k=(1,2,\ldots,n).\)
Using Theorem 2.3, the aforementioned authors enumerated the number of connection coefficients for the symmetric group of order \(n\) by proving that there are \[\begin{aligned} \dfrac{n^{k-1}\prod_{i=1}^{k}(\ell_i-1)!}{\prod_{i=1}^{k}\prod_{j\geq 1}a_{ij}!}, \end{aligned}\] plane edge-rooted \(k\)-cacti with \(n\) unlabelled vertices having a vertex-degree distribution \((a_{ij})_{1\leq i\leq k, j\geq 0}\), where \(\sum\limits_{i=1}^{k}\ell_i=\sum\limits_{i=1}^{k}\sum\limits_{j\geq 0}a_{ij}=(k-1)n+1.\) For \(k=2,\) they obtained an equivalent result for the number of plane edge-rooted trees.
Bóna, Bousquet, Labelle and Leroux [2] defined a free \(k\)-ary cactus informally as a \(k\)-ary cactus without the plane embedding. They obtained a formula [2, Proposition 27] for the number of labelled free \(k\)-ary cacti on \(n\) \(k\)-gons having vertex-color distribution \((\ell_1,\ldots,\ell_k)\) as \[n^{k-2}\prod _{i=1}^{k}\dfrac{(\ell_i-1)!\ell_i^{n-\lambda_i}}{(n-\ell_i)!},\] if \(\sum\limits_{i=1}^{k}\ell_i=(k-1)n+1.\) We provide a different proof of these results based on Theorem 1.1.
Proposition 2.4. The number of labelled free \(k\)-ary cacti on \(n\) \(k\)-gons having vertex-degree distribution \((a_{ij})_{1\leq i\leq k, j\geq 0}\) is given by \[\begin{aligned} \label{bona} \dfrac{n!n^{k-2}\prod_{i=1}^{k}(\ell_i-1)!}{\prod_{i=1}^{k}\prod_{j\geq 1}(j-1)!^{a_{ij}}a_{ij}!}, \end{aligned} \tag{2}\] where \(\sum\limits_{i=1}^{k}\sum\limits_{j\geq0}a_{ij}=\sum\limits_{i=1}^{k}\ell_{i}=(k-1)n+1.\)
Proof. To prove this proposition, we need to show that there is a bijection between the set of labelled free \(k\)-cacti on \(n\) \(k\)-gons having a vertex-degree distribution \((a_{ij})_{1\leq i\leq k, j\geq 0}\) such that \(\sum\limits_{i=1}^{k}\sum\limits_{j\geq 0}a_{ij}=(k-1)n+1\) and the set of families of \(k\) connected cycle-free set partitions of \([n].\)
Consider a labelled free \(k\)-cactus on \(n\) \(k\)-gons with labels from the set \([n]\) and having vertex-degree distribution \((a_{ij})\) for \(i=1,\ldots,k\) and \(j\geq 0.\) The degree distribution of vertices of colour \(i\) can therefore be written as \(\lambda_i=1^{a_{i1}}2^{a_{i2}}\cdots\). Let \(s_i\) be the set of labels of \(k\)-gons that are incident to a vertex \(s\) of colour \(i\). Let \[S_i=\{s_i: s \text{ is a vertex of colour }i\}.\]
We now show that \(S_i\) is a set partition of \([n].\) By Lemma 2.2, \(\sum\limits_jja_{ij}=n\) and \(a_{i0}=0\). This ensures that there is no empty set in \(S_i\). The sets \(s_i\) are disjoint since the labels in \([n]\) are used only once in the labelled free cactus. Therefore \(S_i\) is a partition of the set \([n].\) By Lemma 2.1, the cacti satisfy the condition \(\sum\limits_{i,j}a_{ij}=(k-1)n+1\). It follows that the partitions also satisfy this coherence condition. Since the \(n\) \(k\)-gons are connected and cycle-free then the partitions are also cycle-free and connected.
Next, we describe the reverse procedure of getting free \(k\)-cacti on \(n\) \(k\)-gons from a family of \(k\) set partitions of \([n]\) that are connected and cycle-free. Consider set partitions \(S_1,\ldots,S_k\) of \([n]\) that are connected and cycle-free such that \(\sum\limits_{i=1}^{k} \ell(S_i)=(k-1)n+1\). There is a bijection between these set partitions and cacti-like tree (a cacti-like tree is the structure obtained by replacing all edges in a tree with cycles of the same size) such that the \(k\) set partitions correspond to \(k\) vertices per block in the cacti-like tree, blocks correspond to vertices and block sizes to degrees in the cacti-like tree. Now, each block in the cacti-like tree corresponds to a \(k\)-gon in a free cactus. ◻
The bijection in Proposition 2.4 is shown by Figure 1, where the three partitions are shown by normal curves, dotted curves and dashed curves.
From the cacti-like tree in Figure 1, we obtain a labelled free ternary cactus in Figure 2.
We define a block of a connected graph.
Definition 3.1([11]). A cutpoint of a connected graph \(G\) is a vertex whose removal will disconnect \(G.\) A graph which has no cutpoint is said to be \(2\)-connected. A block in a simple graph is a maximal \(2\)-connected subgraph.
Husimi graphs were introduced by Japanese physicist Kodi Husimi in [10]. A Husimi graph is a connected graph whose blocks are complete graphs. If the blocks of a connected graph are polygons then the graph is called a cactus. Cacti were introduced by Harary and Uhlenbeck in [9] where they appeared as ’Husimi trees’. In 1996, Collin Springer [16] introduced and studied oriented cacti. These are connected graphs whose blocks are oriented cycles.
Lemma 3.2. [11, Proposition 3.1] The number of Husimi graphs on \([n]\) where \(n\geq 1\) is given by \[\begin{aligned} \label{Husimi1} \sum\limits_{k\geq 0}\left\{\begin{matrix} n-1\\k \end{matrix}\right\}n^{k-1}, \end{aligned} \tag{3}\] where \(k\) is the number of blocks and \(\left\{\begin{matrix} n-1\\k \end{matrix}\right\}\) is the Stirling number of the second kind which counts set partitions of \([n-1]\) with \(k\) parts.
Lemma 3.3(Husimi [10], Mayer [12]).Let \((n_2,n_3,\ldots)\) be a sequence of non-negative integers satisfying the condition that \(n=\sum\limits_{j\geq 2} (j-1)n_j +1\). The number \(\mathrm{HG}_n(n_2,n_3,\cdots)\) of Husimi graphs on \([n]\) having \(n_j\) blocks of size \(j\) is given by \[\begin{aligned} \label{Husimi} \mathrm{HG}_n(n_2,n_3,\cdots)=\dfrac{(n-1)!n^{k-1}}{\prod_{j\geq 2}((j-1)!)^{n_j}n_j!}, \end{aligned} \tag{4}\] where \(k=\sum\limits_{j\geq 2}n_j.\)
Formula (4) was proved by Husimi in [10] by first establishing a recurrence equation satisfied by the graphs. Later on, Mayer [12] provided a direct proof and Leroux [11] proved the formula from a generating function approach.
Lemma 3.4(Ford and Uhlenbeck [5]).Let \((n_2,n_3,\ldots)\) be a sequence of non-negative integers satisfying the condition that \(n=\sum\limits_{j\geq 2} (j-1)n_j +1\). The number of cacti on \([n]\) having \(n_j\) polygons of size \(j\) is given by \[\begin{aligned} \label{Ford} \dfrac{1}{2^{\sum\limits_{i\geq 3}n_i}}\dfrac{(n-1)!}{\prod_{i\geq 2}n_i!}n^{k-1}, \end{aligned} \tag{5}\] where \(k=\sum\limits_{j\geq 2}n_j.\)
Eq. (4) was given in [9] as the formula for counting the number of cacti in the statement of Lemma 3.4. This incorrect solution was pointed out in [5] and corrected therein.
Lemma 3.5.[11, Proposition 3.6] The number of labelled cacti on \([n]\), where \(n\geq 2\), is given by \[\begin{aligned} \label{Leroux_cacti} \sum\limits_{k\geq 0}\sum\limits_{\substack{n_2+n_3+\cdots =k \\ n_2+2n_3+\cdots =n-1}}\dfrac{(n-1)!n^{k-1}}{2^{\sum\limits_{i\geq 3}n_i}\prod_{i\geq 2}n_i!}. \end{aligned} \tag{6}\]
Lemma 3.6. Springer [16] Let \((n_2,n_3,\ldots)\) be a sequence of non-negative integers and \(n=\sum\limits_{j\geq 2} (j-1)n_j +1\). The number \(\mathrm{OC}_n(n_2,n_3,\cdots)\), of oriented cacti on \([n]\) having \(n_j\) oriented cycles of size \(j\) is given by \[\begin{aligned} \label{Springer} \mathrm{OC}_n(n_2,n_3,\cdots)=\dfrac{(n-1)!}{\prod_{i\geq 2}n_i!}n^{k-1}, \end{aligned} \tag{7}\] where \(k=\sum\limits_{j\geq 2}n_j.\)
Comparing Eqs. (4) and (7), we remark that \[\begin{aligned} \label{Husimi-Springer} \mathrm{OC}_n(n_2,n_3,\cdots)= \prod_{i\geq 2}((i-1)!)^{n_i}\cdot\mathrm{HG}_n(n_2,n_3,\cdots). \end{aligned} \tag{8}\]
Lemma 3.7. [11, Proposition 3.3] The number of oriented cacti on \([n],\) where \(n\geq 2,\) is given by \[\begin{aligned} \sum\limits_{k\geq 1}\dfrac{(n-1)!}{k!}{n-2\choose k-1}n^{k-1}, \end{aligned}\] where \(k\) is the number of cycles.
Definition 3.8. A coloured Husimi graph is a Husimi graph whose blocks are coloured such that no blocks of the same colour are incident to one another. In the same manner, a coloured cactus (resp. coloured oriented cactus) is a cactus (resp. oriented cactus) whose polygons (resp. oriented cycles) of the same colour are not incident to one another.
Husimi graphs, cacti or oriented cacti are said to be \(k\)-colourable if the blocks of the graph can be coloured with \(k\) colours such that no incident blocks receive the same colour. We show that (1) also enumerates coloured Husimi graphs with a given block-colour distribution. Let \(a_{ij}\) denote the number of blocks of size \(j\) and colour \(i.\)
Proposition 3.9. Let \((n_2,n_3,\ldots)\) be a sequence of non-negative integers satisfying the condition \(n=\sum\limits_{j\geq 2} (j-1)n_j +1\). The number of coloured Husimi graphs on \([n]\) having \(n_j\) blocks of size \(j\) and block-colour distribution \((a_{ij})_{1\leq i\leq k, j\geq 2}\) is given by \[\begin{aligned} \label{coloured Husimi} \dfrac{n!n^{k-2}\prod_{i=1}^{k}(\ell_i-1)!}{\prod_{i=1}^{k}\prod_{j\geq 1}(j-1)!^{a_{ij}}a_{ij}!}, \end{aligned} \tag{9}\] where \(a_{i1}=n-\sum\limits_{j\geq 2}a_{ij}\) and \(\ell_{i}=\sum\limits_{j\geq 1}a_{ij}.\)
Proof. We construct a bijection between the set of coloured Husimi graphs on \([n]\) having \(n_j\) blocks of size \(j\) and block-colour distribution \((a_{ij})_{1\leq i\leq k, j\geq 2}\) and the set of families of \(k\) connected cycle-free set partitions of \([n]\) such that there are \(a_{ij}\) blocks of size \(j\) in the \(i\)-th partition satisfying the coherence condition \(\sum\limits_{i=1}^{k}\sum\limits_{j\geq 1}a_{ij}=(k-1)n+1.\)
Given the coloured Husimi graph, the number of blocks of colour \(i\) is given by \(\sum\limits_{j\geq 2}a_{ij}\). Since \(a_{i1}=n-\sum\limits_{j\geq 2}a_{ij},\) we have that \(\sum\limits_{j\geq 1}a_{ij}=n.\) Let \(B_{ij}\) be the set of vertices in the \(j\)-th block of colour \(i\). Since the blocks of the same colour are not incident to one another, the \(B_{ij}\)’s are disjoint. The vertices which are not part of any block are taken as singletons. Thus the family of sets comprising the singletons and the blocks do not comprise of empty sets. Hence \((a_{ij})_{j\geq 1}\) is a partition of \([n].\) We have \(k\) such partitions since \(1\leq i\leq k.\) The set partitions satisfy the condition \(\sum\limits_{i=1}^{k}\sum\limits_{j\geq 1}a_{ij}=(k-1)n+1.\)
Let us state the reverse procedure. Consider families of \(k\) connected cycle-free set partitions of \([n]\) in which there are \(\ell_{i}\) blocks in the \(i\)-th partition and \(a_{ij}\) blocks of size \(j\) in the \(i\)-th partition such that \(\sum\limits_{i=1}^{k}\ell_i=(k-1)n+1\). Allow edges between two distinct vertices in the block and remove all singletons. If \(v\) is a block in the \(i\)-th partition then colour the resultant complete graph with colour \(i\). We thus obtain a coloured Husimi graph satisfying the condition \(n=\sum\limits_{j\geq 2} (j-1)n_j +1\) where \(n_j=\sum\limits_{i=1}^{k}a_{ij}\). ◻
Using (8), we obtain that
Corollary 3.10. Let \((n_2,n_3,\ldots)\) be a sequence of non-negative integers satisfying the condition \(n=\sum\limits_{j\geq 2} (j-1)n_j +1\). The number of coloured oriented cacti on \([n]\) having \(n_j\) cycles of size \(j\) and block-colour distribution \((a_{ij})_{1\leq i\leq k, j\geq 2}\) is given by \[\begin{aligned} \dfrac{n!n^{k-2}\prod_{i=1}^{k}(\ell_i-1)!}{\prod_{i=1}^{k}\prod_{j\geq 1}a_{ij}!}. \end{aligned}\]
And for the non-oriented case,
Corollary 3.11. Let \((n_2,n_3,\ldots)\) be a sequence of non-negative integers satisfying the condition: \(n=\sum\limits_{j\geq 2} (j-1)n_j +1\). The number of coloured cacti on \([n]\) having \(n_j\) polygons of size \(j\) and block-colour distribution \((a_{ij})_{1\leq i\leq k, j\geq 2}\) is given by \[\begin{aligned} \dfrac{n!n^{k-2}\prod_{i=1}^{k}(\ell_i-1)!}{2^{\sum\limits_{j\geq 3}n_j}\prod_{i=1}^{k}\prod_{j\geq 1}a_{ij}!}. \end{aligned}\]
If partitions forming a connected cycle-free family of set partitions are noncrossing then we get a noncrossing connected cycle-free family of set partitions. If Husimi graphs (resp. cacti or oriented cacti) are drawn with the vertices on the boundary of a circle such that the blocks do not cross inside the circle then we get noncrossing Husimi graphs (resp. cacti or oriented cacti). These structures were enumerated in [14, 15]. A butterfly is a pair of noncrossing Husimi graphs or cacti that share a vertex. Each noncrossing Husimi graph forming a butterfly is called a wing. So, we can talk of left or right wing of a butterfly. If the blocks of noncrossing Husimi graphs are assigned colours in a way that no incident blocks receive the same colour then the resultant structures are called coloured noncrossing Husimi graphs. In this section, we relate colourable Husimi graphs to noncrossing connected cycle-free families of set partitions. We obtain an explicit formula for the number of noncrossing connected, cycle-free pairs of partitions. The case where more than two partitions are involved is still open for research.
Proposition 4.1. There is a bijection between the set of coloured noncrossing Husimi graphs on \(\{1,2,\ldots,n\}\) having \(n_j\) blocks of size \(j\) and block-colour distribution \((a_{ij})_{1\leq i\leq k, j\geq 2}\) such that \(n=\sum\limits_{i=1}^{k}\sum\limits_{j\geq 2}(j-1)a_{ij}+1\) and \(a_{i1}=n-\sum\limits_{j\geq 2}a_{ij},\) and the set of noncrossing connected cycle-free families of \(k\) set partitions of \([n]\) such that there are \(a_{ij}\) blocks of size \(j\) in the \(i\)-th partition satisfying the coherence condition \(\sum\limits_{i=1}^{k}\sum\limits_{j\geq 1}a_{ij}=(k-1)n+1.\)
Proof. Given a coloured noncrossing Husimi graph, the number of blocks of colour \(i\) is given by \(\sum\limits_{j\geq 2}a_{ij}\). Since \(a_{i1}=n-\sum\limits_{j\geq 2}a_{ij},\) we have that \(\sum\limits_{j\geq 1}a_{ij}=n.\) Let \(B_{ij}\) be the set of vertices in the \(j\)-th block of colour \(i\). Since the blocks of the same colour are not incident to one another, the \(B_{ij}\)’s are disjoint. The vertices which are not part of any block are taken as singletons. Thus the family of sets comprising the singletons and the blocks do not have empty sets. Hence \((a_{ij})_{j\geq 1}\) is a partition of \([n].\) Since the blocks are noncrossing, we obtain a noncrossing set partition. We have \(k\) such partitions since \(1\leq i\leq k.\) The set partitions satisfy the condition \(\sum\limits_{i=1}^{k}\sum\limits_{j\geq 1}a_{ij}=(k-1)n+1.\)
We obtain the reverse. Consider families of cycle-free connected noncrossing \(k\) set partitions of \([n]\) in which there are \(a_{ij}\) blocks of size \(j\) in the \(i\)-th partition satisfying the condition: \(\sum\limits_{i=1}^{k}\sum\limits_{j\geq 1}a_{ij}=(k-1)n+1\). Allow edges between any two distinct vertices in a block and remove all singletons. If \(v\) is a block in the \(i\)-th partition then colour the resultant complete graph with colour \(i\). We thus obtain a noncrossing coloured Husimi graph satisfying the condition \(n=\sum\limits_{j\geq 2} (j-1)n_j +1\) where \(n_j=\sum\limits_{i=1}^{k}a_{ij}\). ◻
Theorem 4.2. Let \(\lambda_a=1^{a_1}2^{a_2}\cdots\) and \(\lambda_b=1^{b_1}2^{b_2}\cdots\) be partitions of \(n\geq 1\), with \(a=a_1+a_2+\cdots\) and \(b=b_1+b_2+\cdots\). If \(a+b=n+1\) then the number of noncrossing connected, cycle-free pairs of partitions of types \(\lambda_a\) and \(\lambda_b\) is given by \[\begin{aligned} n 2^{n-a_{1}-b_{1}}\cdot\dfrac{(a-1)!(b-1)!}{a_1!a_2!\cdots b_1!b_2!\cdots}. \end{aligned}\]
Proof. Let \(A(z)\) be the generating function for 2-colourable noncrossing Husimi graphs with root degree 1 (or 0) such that the root block is of colour 1. Let \(B(z)\) be the corresponding generating function in which the root block is of colour 2. Let \(x_j\) and \(y_i\) mark blocks of sizes \(j\) and \(i\) of colours 1 and 2 respectively. Since each vertex has degree less than or equal to two, the \(A(z)\) satisfies \[\begin{aligned} A(z)=z(1+\sum\limits_{j\geq 1}x_{j+1}(2B-z)^{j}). \end{aligned}\]
The butterflies of these graphs must be rooted at vertices of degree 1 (or consists of a single vertex). If the root block in the noncrossing Husimi graph is assigned colour 1 (generating function \(A\)), then the blocks of the butterflies (left or right wing) attached at the root block are assigned colour 2 (generating function \(B\)). We subtract \(z\) to cater for cases in which a butterfly consists of a single vertex. Similarly, \[\begin{aligned} B(z)=z(1+\sum\limits_{i\geq 1}y_{i+1}(2A-z)^{i}). \end{aligned}\]
Set \(2B-z=V\) and \(2A-z=U\) so that \[\begin{aligned} U=z\left(1+2\sum\limits_{j\geq 1}x_{j+1}V^{j}\right) \text{ and } V=z(1+2\sum\limits_{i\geq 1}y_{i+1}U^{i}). \end{aligned}\]
A 2-colourable noncrossing Husimi graph either has root degree 1, or it can be obtained by identifying the roots of two Husimi graphs with root blocks of colour 1 and 2, respectively. Thus the generating function for 2-colourable noncrossing Husimi graphs is \[\begin{aligned} \dfrac{2(A-z)(B-z)}{z}+A+B-z=\dfrac{UV}{2z}+\dfrac{z}{2}. \end{aligned}\]
We apply the multivariate Lagrange Inversion Formula [6, Theorem 1.29] to the system: \[\begin{aligned} U=z_1\left(1+2\sum\limits_{j\geq 1}x_{j+1}V^{j}\right), \hspace{1cm} V=z_2\left(1+2\sum\limits_{i\geq 1}y_{i+1}U^{i}\right). \end{aligned}\]
We have \[\begin{aligned} UV &=\displaystyle\sum\limits_{s,t\geq 0}z_1^{s+1}z_2^{t+1}[\alpha^{s}\beta^{t}]\left(1+2\sum\limits_{j\geq 1}x_{j+1}\alpha^{j}\right)^{t+1} \left(1+2\sum\limits_{i\geq 1}y_{i+1}\beta^{i}\right)^{s+1}\Delta, \end{aligned}\] where \(\Delta\) is the determinant given by \[\begin{aligned} \Delta=\dfrac{(1+2\sum\limits_{j\geq 1}x_{j+1}\alpha^{j})\cdot \left(1+2\sum\limits_{i\geq 1}y_{i+1}\beta^{i}\right)-4\sum\limits_{j\geq 1}jx_{j+1}\alpha^{j}\cdot\sum\limits_{i\geq 1}iy_{i+1}\beta^{i}}{\left(1+2\sum\limits_{j\geq 1}x_{j+1}\alpha^{j}\right) \left(1+2\sum\limits_{i\geq 1}y_{i+1}\beta^{i}\right)}. \end{aligned}\]
We thus have \[\begin{aligned} UV =&\sum\limits_{s,t\geq 0}z_1^{s+1}z_2^{t+1}[\alpha^{s}\beta^{t}]\left(1+2\sum\limits_{j\geq 1}x_{j+1}\alpha^{j}\right)^{t+1} \left(1+2\sum\limits_{i\geq 1}y_{i+1}\beta^{i}\right)^{s+1}\\&-4\sum\limits_{s,t\geq 0}\left[z_1^{s+1}z_2^{t+1}[\alpha^{s}\beta^{t}]\left(1+2\sum\limits_{j\geq 1}x_{j+1}\alpha^{j}\right)^{t} \left(1+2\sum\limits_{i\geq 1}y_{i+1}\beta^{i}\right)^{s}\right.\\ &\left.\sum\limits_{j\geq 1}jx_{j+1}\alpha^{j}\sum\limits_{i\geq 1}iy_{i+1}\beta^{i}\right]. \end{aligned}\]
Let us extract the coefficient of \(\alpha^{s}.\) \[\begin{aligned} \left(1+2\sum\limits_{j\geq 1}x_{j+1}\alpha^{j}\right)^{t+1} &=[\alpha^{s}]\sum\limits_{k\geq 0}{t+1\choose k}\left(2\sum\limits_{i\geq 1}x_{j+1}\alpha^{i}\right)^{k}\\&=\sum\limits_{k\geq 0}2^{k}{t+1\choose k}\sum\limits_{\substack{a_2+a_3+\cdots= k \\ a_2+2a_3+\cdots =s}}\dfrac{k! x_2^{a_2}x_3^{a_3}\cdots}{a_2!a_3!\cdots}. \end{aligned}\]
Similarly, \[\begin{aligned} \left(1+2\sum\limits_{i\geq 1}y_{i+1}\beta^{i}\right)^{s+1} &=[\beta^{t}]\sum\limits_{\ell\geq 0}{s+1\choose \ell}\left(2\sum\limits_{i\geq 1}y_{i+1}\beta^{i}\right)^{\ell}\\&=\sum\limits_{\ell\geq 0}2^{\ell}{s+1\choose \ell}\sum\limits_{\substack{b_2+b_3+\cdots= \ell \\ b_2+2b_3+\cdots =t}}\dfrac{\ell! y_2^{b_2}y_3^{b_3}\cdots}{b_2!b_3!\cdots}. \end{aligned}\]
Since \(k=a-a_1\), \(\ell=b-b_1\), \(s=n-a\) and \(t=n-b\) in our notation, we have \[\begin{aligned} &\left(1+2\sum\limits_{j\geq 1}x_{j+1}\alpha^{j}\right)^{n-b+1}\\&=\sum\limits_{a_1}2^{a-a_1}\dfrac{(n-b+1)!}{(n-b-a+a_1+1)!}\sum\limits_{\substack{a_1+a_2+\cdots= a \\ a_2+2a_3+\cdots =n-a}}\dfrac{ x_2^{a_2}x_3^{a_3}\cdots}{a_2!a_3!\cdots}, \end{aligned}\] and \[\begin{aligned} &\left(1+2\sum\limits_{i\geq 1}y_{i+1}\beta^{i}\right)^{n-a+1}\\&=\sum\limits_{b_1}2^{b-b_1}\dfrac{(n-a+1)!}{(n-a-b+b_1+1)!}\sum\limits_{\substack{b_1+b_2+\cdots= b \\ b_2+2b_3+\cdots =n-b}}\dfrac{ y_2^{b_2}y_3^{b_3}\cdots}{b_2!b_3!\cdots}. \end{aligned}\]
By the coherence condition, \(a+b=n+1\), we obtain \[\begin{aligned} \left(1+2\sum\limits_{j\geq 1}x_{j+1}\alpha^{j}\right)^{n-b+1} &=\sum\limits_{a_1}2^{a-a_1}a!\sum\limits_{\substack{a_1+a_2+\cdots= a \\ a_2+2a_3+\cdots =n-a}}\dfrac{ x_2^{a_2}x_3^{a_3}\cdots}{a_1!a_2!\cdots}, \end{aligned}\] and \[\begin{aligned} \left(1+2\sum\limits_{i\geq 1}y_{i+1}\beta^{i}\right)^{n-a+1} &=\sum\limits_{b_1}2^{b-b_1}b!\sum\limits_{\substack{b_1+b_2+\cdots= b \\ b_2+2b_3+\cdots =n-b}}\dfrac{ y_2^{b_2}y_3^{b_3}\cdots}{b_1!b_2!\cdots}. \end{aligned}\]
We also have \[\begin{aligned} &\left(1+2\sum\limits_{j\geq 1}x_{j+1}\alpha^{j}\right)^{t}\sum\limits_{j\geq 1}jx_{j+1}\alpha^{j}\\ &=\sum\limits_{w= 0}^{s}[\alpha^{w}]\left(1+2\sum\limits_{j\geq 1}x_{j+1}\alpha^{j}\right)^{t}[\alpha^{s-w}]\sum\limits_{j\geq 1}jx_{j+1}\alpha^{j}\\ &=\sum\limits_{w= 0}^{s}[\alpha^{w}]\sum\limits_{k\geq 0}{t\choose k}\left(2\sum\limits_{i\geq 1}x_{j+1}\alpha^{i}\right)^{k} (s-w)x_{s-w+1}\\ &=\sum\limits_{w= 0}^{s}\sum\limits_{k\geq 0}2^{k}{t\choose k}\sum\limits_{\substack{a_2+a_3+\cdots= k \\ a_2+2a_3+\cdots =w}}\dfrac{k! x_2^{a_2}x_3^{a_3}\cdots}{a_2!a_3!\cdots}(s-w)x_{s-w+1}\\ &=\sum\limits_{w= 0}^{s}\sum\limits_{k\geq 0}2^{k}{t\choose k}\sum\limits_{\substack{a_2+a_3+\cdots= k+1 \\ a_2+2a_3+\cdots =s}}\dfrac{k! x_2^{a_2}x_3^{a_3}\cdots}{a_2!a_3!\cdots}(s-w)a_{s-w+1}\\ &=\sum\limits_{k\geq 0}2^{k}{t\choose k}\sum\limits_{\substack{a_2+a_3+\cdots= k+1 \\ a_2+2a_3+\cdots =s}}\dfrac{k! x_2^{a_2}x_3^{a_3}\cdots}{a_2!a_3!\cdots}\cdot \sum\limits_{w= 0}^{s}(s-w)a_{s-w+1}\\ &=\sum\limits_{k\geq 0}2^{k}{t\choose k}\sum\limits_{\substack{a_2+a_3+\cdots= k+1 \\ a_2+2a_3+\cdots =s}}\dfrac{k! x_2^{a_2}x_3^{a_3}\cdots}{a_2!a_3!\cdots}\cdot s. \end{aligned}\]
Likewise, \[\begin{aligned} &[\beta^{t}]\left(1+2\sum\limits_{i\geq 1}y_{i+1}\beta^{i}\right)^{s}\sum\limits_{i\geq 1}iy_{i+1}\beta^{i} =\sum\limits_{\ell\geq 0}2^{\ell}{s\choose \ell}\sum\limits_{\substack{b_2+b_3+\cdots= \ell+1 \\ a_2+2a_3+\cdots =s}}\dfrac{\ell! y_2^{b_2}y_3^{b_3}\cdots}{b_2!b_3!\cdots}\cdot t. \end{aligned}\]
Again using coherence conditions \(k=a-a_1-1\), \(\ell=b-b_1-1\), \(s=n-a\), \(t=n-b\) and \(a+b=n+1\), we obtain \[\begin{aligned} \left(1+2\sum\limits_{j\geq 1}x_{j+1}\alpha^{j}\right)^{n-b}&\sum\limits_{j\geq 1}jx_{j+1}\alpha^{j} \\&=\sum\limits_{a_1}2^{a-a_1-1}(a-1)!\sum\limits_{\substack{a_1+a_2+\cdots= a \\ a_2+2a_3+\cdots =n-a}}\dfrac{ x_2^{a_2}x_3^{a_3}\cdots}{a_1!a_2!\cdots}\cdot (b-1) \end{aligned}\] and \[\begin{aligned} \left(1+2\sum\limits_{i\geq 1}y_{i+1}\beta^{i}\right)^{n-a}&\sum\limits_{i\geq 1}iy_{i+1}\beta^{i} \\&=\sum\limits_{b_1}2^{b-b_1-1}(b-1)!\sum\limits_{\substack{b_1+b_2+\cdots= b \\ b_2+2b_3+\cdots =n-b}}\dfrac{y_2^{b_2}y_3^{b_3}\cdots}{b_1!b_2!\cdots}\cdot(a-1). \end{aligned}\]
Hence, \[\begin{aligned} UV\\ &=z_1^{n-a+1}z_2^{n-b+1} 2^{a+b-a_1-b_1} \dfrac{a!b!}{a_1!a_2!\cdots b_1!b_2!\cdots}\\ &\quad-z_1^{n-a+1}z_2^{n-b+1}\cdot 4 \cdot 2^{a+b-a_1-b_1-2}(a-1)(b-1) \dfrac{(a-1)!(b-1)!}{a_1!a_2!\cdots b_1!b_2!\cdots}\\ &=z_1^{n-a+1}z_2^{n-b+1}(a+b-1)\cdot 2^{n+1-a_1-b_1}\dfrac{(a-1)!(b-1)!}{a_1!a_2!\cdots b_1!b_2!\cdots}\\ &=z_1^{n-a+1}z_2^{n-b+1}n\cdot 2^{n+1-a_1-b_1}\dfrac{(a-1)!(b-1)!}{a_1!a_2!\cdots b_1!b_2!\cdots}. \end{aligned}\]
Now, by setting \(z_1=z_2=z\), we have \[\begin{aligned} &[x_2^{a_2}x_3^{a_3}\cdots y_2^{b_2}y_3^{b_3}\cdots] \dfrac{UV}{2z} =z^{n}n\cdot 2^{n-a_1-b_1}\dfrac{(a-1)!(b-1)!}{a_1!a_2!\cdots b_1!b_2!\cdots}. \end{aligned}\]
Therefore, \[\begin{aligned} \dfrac{UV}{2z} &=n\cdot 2^{n-a_1-b_1}\dfrac{(a-1)!(b-1)!}{a_1!a_2!\cdots b_1!b_2!\cdots}. \end{aligned}\]
By Proposition 4.1, we obtain that there are \[\begin{aligned} n\cdot 2^{n-a_1-b_1}\dfrac{(a-1)!(b-1)!}{a_1!a_2!\cdots b_1!b_2!\cdots}, \end{aligned}\] noncrossing connected, cycle-free pairs of partitions of \([n]\) of types \(1^{a_1}2^{a_2}\cdots\) and \(1^{b_1}2^{b_2}\cdots\). ◻
The author thanks Prof. Stephan Wagner for supervising this work.