An Exact Enumeration of the Unlabeled Disconnected Posets

Salah Uddin Mohammad, Md. Shah Noor, and Md. Rashed Talukder

Department of Mathematics Shahjalal University of Science and Technology Sylhet-3114 Bangladesh

                salahuddin-mat@sust.edu
                  msnoor-mat@sust.edu
                r.talukder-mat@sust.edu

Abstract

We give an exact enumeration of the unlabeled disconnected posets according to the number of connected components of the posets. This result establishes that the enumeration of unlabeled posets belonging to a class that is closed under the direct sum depends mainly on the enumeration of unlabeled connected posets contained in the class. We also give an algorithm to determine the parameters involved in the enumeration formula, and finally, find the number of unlabeled disconnected posets with a certain number of elements. We show that the enumeration algorithm runs in polynomial time.

1 Introduction

We give an exact enumeration of the unlabeled disconnected posets belonging to a class of posets that is closed under the direct sum of posets. Let P_{n}, n ≥ 1 be the set of all n-element unlabeled posets. Also let Q_{n}, n ≥ 1 and R_{n}, n ≥ 2 be the sets of all n-element unlabeled connected and disconnected posets, respectively. Since the singleton poset is connected, we have P_{1} = Q_{1} and |P_{1}| = |Q_{1}| = 1. In general, for all n ≥ 2, we have P_{n} = Q_{n} ∪ R_{n} and hence |P_{n}| = |Q_{n}| + |R_{n}|. We observe that every member of R_{n} can be expressed as the direct sum of two or more members from Q_{r}, 1 ≤ r ≤ n−1. In our enumeration method, for finite n ≥ 2, we express |R_{n}| as a finite series consisting of the numbers |Q_{r}|, r ≤ n − 1 that gives the enumeration of the posets belonging to R_{n} according to the number of connected direct terms (components) of the posets. Here, we establish in general the criterion for the pairwise nonisomorphic direct sum of unlabeled posets obtained by Mohammad [12] and used particularly for the enumeration of the class of P -series, a subclass of the class of series-parallel posets.

For common enumeration methods, we refer the readers to [3, 4, 7, 10] for the enumeration of finite posets, [1, 2] for graphs, and [6, 11] for topologies. In the most of these cases, the enumeration of a class of structures was done by generating and counting all the pairwise nonisomorphic structures belonging to the class. The running time of these algorithms increases rapidly even though the structures under consideration are significantly small in size. Mainly, the running time for generating pairwise nonisomorphic structures make these algorithms highly time-complex. We observe that the steps for generating pairwise nonisomorphic disconnected posets in an enumeration process can be skipped. Therefore, the proposed exact enumeration method for the unlabeled disconnected posets must reduce the time-complexities of the algorithms for enumeration of unlabeled posets. Further, this enumeration method is applicable for the enumeration and generation of any unlabeled mathematical structures (posets, graphs, networks, topologies, and so on) belonging to a class that is closed under the direct sum of the structures.

We also give an algorithm to determine the parameters involved in the enumeration formula and to compute the numbers |R_{n}| for n ≥ 2. We show that the enumeration algorithm runs in polynomial time with complexity O(n^{5}). We implement the enumeration algorithm into the computer and gather some numerical results. Brinkmann and McKay [3] obtained the number of unlabeled posets up to 16 elements, the sequence \underline{A000112} in OEIS [13]. By using the number of unlabeled connected posets up to 16 elements, we determine the number of unlabeled disconnected posets up to 17 elements according to the number of connected direct terms of the posets, the sequences \underline{A349401} and \underline{A263864} in OEIS [13]. Khamis [9] obtained the number of unlabeled N-free posets up to 14 elements according to the height of the posets, the sequence \underline{A202182} in OEIS [13]. By using the number of unlabeled connected N-free posets up to 14 elements, we determine the number of unlabeled disconnected N-free posets up to 15 elements according to the number of connected direct terms of the posets, the sequences \underline{A349367} and \underline{A350783} in OEIS [13].

In Section 2, we recall some basic terminologies related to the posets and their direct sum. In Section 3, we give the criterion for pairwise nonisomorphic direct sums of connected posets. In Section 4, we establish the formulae giving the enumeration of disconnected posets. In Section 5, we give the enumeration algorithm and prove its time-complexity. In Section 6, we include the numerical results obtained by implementing the enumeration algorithm into the computer.

2 Preliminaries

A poset (partially ordered set) is a structure A = ⟨A, ⩽⟩ consisting of the nonempty set A with the order relation ⩽ on A. A poset A is called finite if the underlying set A is finite. Here, we assume that every poset is finite. Let A = ⟨A, ⩽_{A}⟩ and B = ⟨B, ⩽_{B}⟩ be any posets. A bijective map ϕ : A → B is called an order isomorphism if for all x, y ∈ A, x ⩽_{A} y if and only if ϕ(x) ⩽_{B} ϕ(y). We write A ≅ B whenever A and B are order isomorphic. By saying that a collection of posets is isomorphic (analogously, nonisomorphic), we mean that the posets in the collection are pairwise isomorphic (nonisomorphic). For further details on posets, we refer the readers to the classical book by Davey and Priestley [5].

We use the notation 1 for the singleton poset, C_{n} (n ≥ 1) for the n-element chain poset, I_{n} (n ≥ 1) for the n-element antichain poset, B_{m,n} (m ≥ 1, n ≥ 1) for the complete bipartite poset with m minimal elements and n maximal elements. We write A + B to denote the direct sum of A and B. Here, A and B are called the direct terms (components) of the poset A + B. We write briefly ∑_{i=1}^{r} A_{i} for the direct sum A_{1} + A_{2} + ⋯ + A_{r} and rA for the direct sum A+A+⋯ +A of r posets A. For example, I_{n} ≅ n1. A poset having two or more direct terms is called disconnected, otherwise, it is called connected. Note that, for all posets A_{i}, B_{i}, 1 ≤ i ≤ r, since the direct sum of posets is commutative, we have ∑_{i=1}^{r} A_{i} ≅ ∑_{i=1}^{r} B_{i} if and only if A_{i} ≅ B_{i} for every 1 ≤ i ≤ r.

3 Nonisomorphic direct sum criterion

For unlabeled connected posets, in particular, we have Q_{1} = {1}, Q_{2} = {C_{2}}, and Q_{3} = {B_{1,2}, B_{2,1}, C_{3}}. For unlabeled disconnected posets, we have R_{2} = {21}, R_{3} = {1 + C_{2}, 31}, and R_{4} = {1 + C_{3}, 1 + B_{1,2}, 1 + B_{2,1}, C_{2} + C_{2}, 21 + C_{2}, 41}. We observe that, for every 2 ≤ n ≤ 4, every member of R_{n} can be expressed as the direct sum of some members of Q_{r}, 1 ≤ r ≤ 3. In general, for R_{n} ∈ R_{n}, n ≥ 2, there exist Q_{n_{i}} ∈ Q_{n_{i}}, 1 ≤ i ≤ m such that

R_{n} ≅ Q_{n_{1}} + Q_{n_{2}} + ⋯ + Q_{n_{m}} = ∑_{i=1}^{m} Q_{n_{i}},  (1)

where 2 ≤ m ≤ n and n = ∑_{i=1}^{m} n_{i}. Here, m is the number of connected direct terms of R_{n}. Since the direct sum of posets is commutative, we observe the following.

1. For n = 2, we have R_{2} ≅ Q_{1} + Q_{1}. Thus an R_{2} can be obtained only in one way with 2 connected direct terms.

2. For n = 3, we have R_{3} ≅ Q_{1} + Q_{2} ≅ Q_{2} + Q_{1} and R_{3} ≅ Q_{1} + Q_{1} + Q_{1}. Thus, an R_{3} can be obtained in one way with 2 connected direct terms and in one way with 3 direct terms.

3. For n = 4, all the ways in which an R_{4} can be obtained are given in Table 1. Here, we see that an R_{4} can be obtained in two ways with 2 connected direct terms, in one way with 3 connected direct terms, and in one way with 4 connected direct terms.

Number of  Ways in which an
connected direct terms  R_{4} can be obtained
2  Q_{2} + Q_{2}
and Q_{1} + Q_{3} ≅ Q_{3} + Q_{1}
3  Q_{1} + Q_{1} + Q_{2} ≅ Q_{1} + Q_{2} + Q_{1}
≅ Q_{2} + Q_{1} + Q_{1}
4  Q_{1} + Q_{1} + Q_{1} + Q_{1}

Table 1: All the ways in which an R_{4} can be obtained as a direct sum of Q_{r}, r ≤ 3.

We see that if the posets R_{n} ∈ R_{n} are obtained as above, some of the posets in R_{n} can be isomorphic even though the collection of direct terms Q_{n_{i}}, 1 ≤ i ≤ m is nonisomorphic. In this section, we establish the criterion for the direct sum so that all the posets in R_{n} obtained as the direct sum of the posets Q_{n_{i}}, 1 ≤ i ≤ m are nonisomorphic. Here, for every 1 ≤ r ≤ n − 1, we must assume that the collection Q_{r} is nonisomorphic. To make our intuition more precise, we observe the connected direct terms of the posets R_{6} ∈ R_{6}. We see that an R_{6} can be obtained in all the ways given in Table 2.

Number of  Ways in which an
connected direct terms  R_{6} can be obtained
2  Q_{1} + Q_{5}, Q_{2} + Q_{4},
and Q_{3} + Q_{3}
3  Q_{1} + Q_{1} + Q_{4},
Q_{1} + Q_{2} + Q_{3},
and Q_{2} + Q_{2} + Q_{2}
4  Q_{1} + Q_{1} + Q_{1} + Q_{3}
and Q_{1} + Q_{1} + Q_{2} + Q_{2}
5  Q_{1} + Q_{1} + Q_{1} + Q_{1} + Q_{2}
6  Q_{1} + Q_{1} + Q_{1} + Q_{1} + Q_{1} + Q_{1}

Table 2: All the ways in which an R_{6} can be obtained as a direct sum of Q_{r}, r ≤ 5.

Here, in Table 2, we see that all the other direct sums in which an R_{6} can be obtained are isomorphic to one of the direct sums given in the table. This observation shows that all the direct sums in which a poset R_{n} can be obtained will be nonisomorphic if the sequence ⟨n_{1}, n_{2}, …, n_{m}⟩, as in the equation (1), is nondecreasing, that is, n_{1} ≤ n_{2} ≤ ⋯ ≤ n_{m}. We prove this conjecture in the following. Recall the assumption that, for every 1 ≤ r ≤ n − 1, the collection Q_{r} is nonisomorphic.

Theorem 1. For all R_{n} ∈ R_{n}, let R_{n} = ∑_{i=1}^{m} Q_{n_{i}}, where n = ∑_{i=1}^{m} n_{i} for some 2 ≤ m ≤ n, such that the sequences ⟨n_{1}, n_{2}, …, n_{m}⟩ are all nondecreasing and distinct. Then for every pair of posets R_{n}, R′_{n} ∈ R_{n}, we have R_{n} ≇ R′_{n}.

Proof. For R_{n}, R′_{n} ∈ R_{n}, let R_{n} ≅ ∑_{i=1}^{m} Q_{n_{i}} and R′_{n} ≅ ∑_{i=1}^{m′} Q_{r_{i}}, as in the hypothesis, such that L = ⟨n_{1}, n_{2}, …, n_{m}⟩ ≠ ⟨r_{1}, r_{2}, …, r_{m′}⟩ = L′. If m ≠ m′ then R_{n} and R′_{n} have different numbers of connected direct terms and, clearly, R_{n} ≇ R′_{n}. Otherwise, let m = m′. In this case, since both L and L′ contain nondecreasing lengths, there exist 1 ≤ s, t ≤ m, such that n_{i} ≠ r_{i} when s ≤ i ≤ t and n_{i} = r_{i} otherwise (in the simplest case, for example, consider the sequences ⟨1, 2, 3, 4, 5⟩ and ⟨1, 2, 2, 5, 5⟩ where s = 3 and t = 4). Also, r_{i} < n_{s} or n_{i} < r_{s} for all 1 ≤ i ≤ s − 1 (when s > 1); and n_{t} < r_{i} or r_{t} < n_{i} for all t + 1 ≤ i ≤ m (when t < m − 1). Thus, there exist either s ≤ u ≤ t such that Q_{n_{u}} ≇ Q_{r_{i}} for all 1 ≤ i ≤ m, or s ≤ v ≤ t such that Q_{r_{v}} ≇ Q_{n_{i}} for all 1 ≤ i ≤ m. This shows that R_{n} ≇ R′_{n}.

4 Enumeration of unlabeled disconnected posets

To determine |R_{n}|, n ≥ 2, the observations in the previous section suggest that, for certain 2 ≤ m ≤ n (the number of connected direct terms of the R_{n} ∈ R_{n}), we must consider only the distinct nondecreasing sequences ⟨n_{1}, n_{2}, …, n_{m}⟩, as given in the equation (1). In particular, we see that |R_{6}| can be computed by using the direct sums given in Table 2 and the numbers |Q_{1}| = |Q_{2}| = 1, |Q_{3}| = 3, |Q_{4}| = 10, and |Q_{5}| = 44, see [3, 4, 7]. Here, we use the notation R_{n}^{m} to denote the set of all posets R_{n} ∈ R_{n} with m connected direct terms. Then we have R_{n} = ⋃_{m=2}^{n} R_{n}^{m}. Since the collections R_{n}^{m}, 2 ≤ m ≤ n of unlabeled posets are pairwise disjoint, we have |R_{n}| = ∑_{m=2}^{n} |R_{n}^{m}|. Firstly, we compute |R_{6}^{2}|. For R_{6} ∈ R_{6}^{2}, we have the following cases.

1. R_{6} ≅ Q_{1} + Q_{5}. Since the direct terms are the posets with unequal numbers of elements, in this case, we have |Q_{1}| × |Q_{5}| = 1 × 44 = 44 disconnected posets.

2. R_{6} ≅ Q_{2} + Q_{4}. Due to the reason same to the previous case, here, we have |Q_{2}| × |Q_{4}| = 1 × 10 = 10 disconnected posets.

3. R_{6} ≅ Q_{3} + Q_{3}. Since both the direct terms are the posets with the same number of elements (that is, a direct term in the expression is repeated), in this case, we have \binom{|Q_{3}|+2−1}{2} = \binom{3+1}{2} = 6 disconnected posets.

These give

|R_{6}^{2}| = 44 + 10 + 6 = 60.

Similarly, we have

|R_{6}^{3}| = 10 + 3 + 1 = 14,
|R_{6}^{4}| = 3 + 1 = 4,
|R_{6}^{5}| = 1, and
|R_{6}^{6}| = 1.

Finally, we have

|R_{6}| = ∑_{m=2}^{6} |R_{6}^{m}| = 60 + 14 + 4 + 1 + 1 = 80.

In the following, we establish, in general, the above observations consecutively.

Lemma 2. For given 2 ≤ t ≤ n, let R̃_{n}^{t} ⊆ R_{n} be the collection of posets such that for R_{n} ∈ R̃_{n}^{t}, we have R_{n} ≅ ∑_{i=1}^{t} Q_{n_{i}}, where n = ∑_{i=1}^{t} n_{i} and the sequence ⟨n_{1}, n_{2}, …, n_{t}⟩ is strictly increasing. Then |R̃_{n}^{t}| = ∏_{i=1}^{t} |Q_{n_{i}}|.

Proof. Let R_{n} ∈ R̃_{n}^{t}. As the sequence ⟨n_{1}, n_{2}, …, n_{t}⟩ is strictly increasing, the direct terms Q_{n_{i}}, 1 ≤ i ≤ t of R_{n} have different cardinalities. Thus, all the t direct terms of a poset R_{n} can be chosen consecutively from one of the disjoint collections Q_{n_{1}}, Q_{n_{2}}, …, and Q_{n_{t}} each of which consists of all nonisomorphic connected posets. Therefore, |R̃_{n}^{t}| equals the number of the collections consisting of t distinct items each of which is chosen consecutively from one of the collections consisting of |Q_{n_{1}}|, |Q_{n_{2}}|, …, and |Q_{n_{t}}| distinct items, respectively. Therefore, we have |R̃_{n}^{t}| as follows:

|R̃_{n}^{t}| = |Q_{n_{1}}| × |Q_{n_{2}}| × ⋯ × |Q_{n_{t}}| = ∏_{i=1}^{t} |Q_{n_{i}}|.  (2)

Lemma 3. For given 2 ≤ t ≤ n, let R̄_{n}^{t} ⊆ R_{n} be the collection of posets such that for R_{n} ∈ R̄_{n}^{t}, we have R_{n} ≅ ∑_{i=1}^{t} Q_{n_{i}}, where n = ∑_{i=1}^{t} n_{i} and the sequence ⟨n_{1}, n_{2}, …, n_{t}⟩ is constant. Then |R̄_{n}^{t}| = \binom{|Q_{r}|+t−1}{t}, where r = n_{i}, 1 ≤ i ≤ t.

Proof. Let R_{n} ∈ R̄_{n}^{t}. As the sequence ⟨n_{1}, n_{2}, …, n_{t}⟩ is constant, we assume r = n_{i}, 1 ≤ i ≤ t. Thus, every poset Q_{n_{i}}, 1 ≤ i ≤ t consists of r elements. This shows that all the t direct terms of a poset R_{n} can be chosen from the same collection Q_{r} consisting of |Q_{r}| nonisomorphic connected posets. Therefore, |R̄_{n}^{t}| equals the number of t-element combinations of |Q_{r}| objects, with repetition. This gives |R̄_{n}^{t}| as follows:

|R̄_{n}^{t}| = \binom{|Q_{r}| + t − 1}{t}.  (3)

Theorem 4. For given 2 ≤ m ≤ n, let R_{n}^{m} ⊆ R_{n} be the collection of posets such that for R_{n} ∈ R_{n}^{m}, we have R_{n} ≅ ∑_{i=1}^{m} Q_{n_{i}}, where n = ∑_{i=1}^{m} n_{i} and the sequence ⟨n_{1}, n_{2}, …, n_{m}⟩ is nondecreasing. Then, there exist q ≤ m and r_{k}, t_{k}, 1 ≤ k ≤ q such that |R_{n}^{m}| = ∏_{k=1}^{q} \binom{|Q_{r_{k}} |+t_{k}−1}{t_{k}}.

Proof. Let R_{n} ∈ R_{n}^{m}. Since the sequence ⟨n_{1}, n_{2}, …, n_{m}⟩, as in the hypothesis, is nondecreasing, there exist q and r_{k}, t_{k}, 1 ≤ k ≤ q such that

r_{1} = n_{1} = n_{2} = ⋯ = n_{t_{1}},
r_{2} = n_{t_{1}+1} = n_{t_{1}+2} = ⋯ = n_{t_{1}+t_{2}},
r_{3} = n_{t_{1}+t_{2}+1} = n_{t_{1}+t_{2}+2} = ⋯ = n_{t_{1}+t_{2}+t_{3}},
⋮
r_{q} = n_{t_{1}+···+t_{q−1}+1} = n_{t_{1}+···+t_{q−1}+2} = ⋯ = n_{m},

where r_{1} < r_{2} < ⋯ < r_{q} and m = t_{1} + ⋯ + t_{q}. Let R_{r_{k}t_{k}} ∈ R̄_{r_{k}t_{k}}^{t_{k}} be the k-th subcollection of t_{k} consecutive connected direct terms of the poset R_{n}. Then, for every 1 ≤ k ≤ q, the poset R_{r_{k}t_{k}} can be expressed as follows:

R_{r_{k}t_{k}} ≅ \underbrace{Q_{r_{k}} + Q_{r_{k}} + ⋯ + Q_{r_{k}}}_{t_{k} terms} .  (4)

Therefore, the poset R_{n} can be expressed as follows:

R_{n} ≅ R_{r_{1}t_{1}} + R_{r_{2}t_{2}} + ⋯ + R_{r_{q}t_{q}}.  (5)

Since the sequence ⟨r_{k}, r_{k}, ⋯, r_{k}⟩ is constant, all of the t_{k} direct terms Q_{r_{k}} in (4) are connected posets with r_{k} elements. Then, by Lemma 3, we have |R̄_{r_{k}t_{k}}^{t_{k}}| as follows:

|R̄_{r_{k}t_{k}}^{t_{k}}| = \binom{|Q_{r_{k}}| + t_{k} − 1}{t_{k}}.  (6)

Since the sequence ⟨r_{1}, r_{2}, ⋯, r_{q}⟩ is strictly increasing, every direct term R_{r_{k}t_{k}} in (5) is itself a direct sum that consists of t_{k} connected direct terms each consisting of r_{k} elements. Then, by Lemma 2, we have |R_{n}^{m}| as follows:

|R_{n}^{m}| = ∏_{k=1}^{q} |R̄_{r_{k}t_{k}}^{t_{k}}|.

Then, by using the equation (6), we have |R_{n}^{m}| as follows:

|R_{n}^{m}| = ∏_{k=1}^{q} \binom{|Q_{r_{k}}| + t_{k} − 1}{t_{k}}.  (7)

Note that the value of the parameter q, as in the equation (7), equals the number of blocks with the same connected direct terms in the direct sum with m terms as considered above. The following example illustrates Theorem 4.

Example 5. Let S = {R_{23} ∈ R_{23}^{6} : R_{23} ≅ Q_{3} + Q_{3} + Q_{4} + Q_{4} + Q_{4} + Q_{5}}. Here, we describe the computation of |S| by using the equation (7). We have

R_{23} ≅ Q_{3} + Q_{3} + Q_{4} + Q_{4} + Q_{4} + Q_{5}
≅ (Q_{3} + Q_{3}) + (Q_{4} + Q_{4} + Q_{4}) + (Q_{5})
≅ R_{6} + R_{12} + Q_{5} (say),

where R_{6} ≅ Q_{3} + Q_{3} and R_{12} ≅ Q_{4} + Q_{4} + Q_{4}. Note that, in the case of the direct sum considered above, the value of the parameter q (the number of distinct blocks with repeated connected direct terms), as in the equation (7), equals 3. Now we assume

S_{1} = {R_{6} ∈ R_{6}^{2} : R_{6} ≅ Q_{3} + Q_{3}},
S_{2} = {R_{12} ∈ R_{12}^{3} : R_{12} ≅ Q_{4} + Q_{4} + Q_{4}}, and
S_{3} = Q_{5}.

Then

S = S_{1} ∪ S_{2} ∪ S_{3},

where the collections S_{1}, S_{2}, and S_{3} are pairwise disjoint. This implies

|S| = |S_{1}| × |S_{2}| × |S_{3}|.

Here, we have

|S_{1}| = \binom{|Q_{3}| + 2 − 1}{2} = \binom{3 + 1}{2} = 6,
|S_{2}| = \binom{|Q_{4}| + 3 − 1}{3} = \binom{10 + 2}{3} = 220, and
|S_{3}| = |Q_{5}| = 44.

Therefore,

|S| = 6 × 220 × 44 = 58, 080.

Now, we give the enumeration formula for the unlabeled disconnected posets, in general, as follows:

Theorem 6. Let R_{n} be the collection of posets such that for R_{n} ∈ R_{n}, we have R_{n} ≅ ∑_{i=1}^{m} Q_{n_{ij}}, 1 ≤ j ≤ p_{m}, 2 ≤ m ≤ n for some p_{m} ≤ \binom{n−1}{m}, where n = ∑_{i=1}^{m} n_{ij}, 1 ≤ j ≤ p_{m} and all the sequences ⟨n_{1j}, n_{2j}, …, n_{mj}⟩, 1 ≤ j ≤ p_{m} are nondecreasing. Then, there exist q_{mj} ≤ m and r_{mjk}, t_{mjk}, 1 ≤ k ≤ q_{mj}, 1 ≤ j ≤ p_{m}, 2 ≤ m ≤ n such that |R_{n}| = ∑_{m=2}^{n} ∑_{j=1}^{p_{m}} ∏_{k=1}^{q_{mj}} \binom{|Q_{r_{mjk}} |+t_{mjk}−1}{t_{mjk}}.

Proof. Let R_{n} ∈ R_{n}. Then R_{n} ∈ R_{n}^{mj} for some 1 ≤ j ≤ p_{m} and 2 ≤ m ≤ n. Since the sequences ⟨n_{1j}, n_{2j}, …, n_{mj}⟩, 1 ≤ j ≤ p_{m}, as in the hypothesis, are nondecreasing, there exist q_{mj} and r_{mjk}, t_{mjk}, for 1 ≤ k ≤ q_{mj}, 1 ≤ j ≤ p_{m}, 2 ≤ m ≤ n such that

r_{mj1} = n_{ij}, 1 ≤ i ≤ t_{mj1},
r_{mj2} = n_{ij}, t_{mj1} + 1 ≤ i ≤ t_{mj2},
⋮
r_{mjq_{mj}} = n_{ij}, t_{mj(q−1)} + 1 ≤ i ≤ t_{mjq_{mj}},

where r_{mj1} < r_{mj2} < ⋯ < r_{mjq_{mj}} and m = t_{mj1} + ⋯ + t_{mjq_{mj}}. For certain m and j, let R_{r_{mjk}t_{mjk}} ∈ R̄_{r_{mjk}t_{mjk}}^{t_{mjk}} be the k-th subcollection of t_{mjk} consecutive direct terms of the poset R_{n}. Then, for every 1 ≤ k ≤ q_{mj}, the poset R_{r_{mjk}t_{mjk}} can be expressed as follows:

R_{r_{mjk}t_{mjk}} ≅ \underbrace{Q_{r_{mjk}} + Q_{r_{mjk}} + ⋯ + Q_{r_{mjk}}}_{t_{mjk} terms} .  (8)

Therefore, the poset R_{n} can be expressed as follows:

R_{n} ≅ R_{r_{mj1}t_{mj1}} + R_{r_{mj2}t_{mj2}} + ⋯ + R_{r_{mjq_{mj}} t_{mjq_{mj}}} .  (9)

Since the sequence ⟨r_{mjk}, r_{mjk}, ⋯, r_{mjk}⟩ is constant, all of the t_{mjk} direct terms Q_{r_{mjk}} in (8) are connected posets with r_{mjk} elements. Again, since the sequence ⟨r_{mj1}, r_{mj2}, ⋯, r_{mjq_{mj}}⟩ is strictly increasing, each of the direct terms R_{r_{mjk}t_{mjk}} in (9) itself is a direct sum consisting of the connected direct terms having r_{mjk} elements. Then, by Theorem 4, we have |R_{n}^{mj}| as follows:

|R_{n}^{mj}| = ∏_{k=1}^{q_{mj}} \binom{|Q_{r_{mjk}}| + t_{mjk} − 1}{t_{mjk}}.  (10)

Since |R_{n}| equals the sum of |R_{n}^{mj}| for all possible values of m and j, where 2 ≤ m ≤ n and 1 ≤ j ≤ p_{m} for some p_{m} ≤ \binom{n−1}{m}, we have |R_{n}| as follows:

|R_{n}| = ∑_{m=2}^{n} ∑_{j=1}^{p_{m}} |R_{n}^{mj}|, n ≥ 2.

Finally, by using the equation (10), we have |R_{n}| as follows:

|R_{n}| = ∑_{m=2}^{n} ∑_{j=1}^{p_{m}} ∏_{k=1}^{q_{mj}} \binom{|Q_{r_{mjk}}| + t_{mjk} − 1}{t_{mjk}}, n ≥ 2.  (11)

Note that for every 2 ≤ m ≤ n, the value of the parameter p_{m}, as in (11), equals the number of nondecreasing sequences ⟨n_{1}, n_{2}, …, n_{m}⟩, as in (1), where n_{i} ∈ {1, 2, …, n − 1} for all 1 ≤ i ≤ m. Also, for every 2 ≤ m ≤ n and 1 ≤ j ≤ p_{m}, the value of the parameter q_{mj}, as in (11), equals the number of blocks with same connected direct terms in the direct sum corresponding to the j-th nondecreasing sequence with m numbers as constructed above.

5 Enumeration algorithm

Recall that we do not determine explicitly the parameters p_{m}, q_{mj}, and r_{mjk}, where 1 ≤ k ≤ q_{mj}, 1 ≤ j ≤ p_{m}, and 2 ≤ m ≤ n, as in the equation (11). Therefore, for given n ≥ 2, the computation of |R_{n}| depends on determining these parameters by constructing mainly the nondecreasing sequences ⟨n_{1j}, n_{2j}, …, n_{mj}⟩ for all 1 ≤ j ≤ p_{m} and 2 ≤ m ≤ n. Note that, by inspection, we have p_{m} ≤ n^{2} for all 2 ≤ m ≤ n. Also, we have q_{mj} ≤ m + 1 for all 1 ≤ j ≤ p_{m} and 2 ≤ m ≤ n. Here, by using Algorithm 7 given below, we construct the nondecreasing sequences ⟨n_{1j}, n_{2j}, …, n_{mj}⟩ and determine the parameters p_{m}, q_{mj}, r_{mjk} for all 1 ≤ k ≤ q_{mj}, 1 ≤ j ≤ p_{m}, 2 ≤ m ≤ n, and finally compute the numbers |R_{n}| for n ≥ 2.

Algorithm 7. To compute V = |R_{n}|, the number of n-element unlabeled disconnected posets, where n ≥ 2 is fixed.

(1) Initialize V = 0.

(2) Repeat (A) for m = 2 to n.

(A) Repeat (i) to (iv) for every nondecreasing sequence L(m, j) = ⟨n_{1j}, n_{2j}, …, n_{mj}⟩, 1 ≤ j ≤ p_{m} as is constructed in (i). (Here, the total number of repetitions equals the value of the parameter p_{m} in the equation (11)).

(i) Construct j-th nondecreasing sequence L(m, j) consisting of m integers chosen from the integers 1, 2, …, n − 1.

(ii) Initialize S(m, j) as S(m, j) = 1.

(iii) Compute t_{mjk} and repeat (a) below for every distinct r_{mjk} in the sequence L(m, j). (Here, the total number of distinct r_{mjk} equals the value of the parameter q_{mj} in the equation (11)).

(a) Update S(m, j) with S(m, j) × \binom{|Q_{r_{mjk}} |+t_{mjk}−1}{t_{mjk}}.

(iv) Increase V by S(m, j).

(3) Return V.

Lemma 8. Algorithm 7 runs in time O(n^{5}).

Proof. The constructions of the sequences L(m, j) in the step (i) have complexity equal to m(n − 1). Since 1 ≤ t_{mjk}, q_{mj} ≤ m + 1 and t_{mjk} is inversely proportional to q_{mj}, the computations of S(m, j) in the step (iii) have complexity equal to m + 1. Then m ≤ n implies that the complexity m(n − 1) ≈ O(n(n − 1)) ≈ O(n^{2}) and the complexity m + 1 ≈ O(n + 1) ≈ O(n). Since 1 ≤ p_{m} ≤ n^{2}, the repetitions in the step (A) increase the complexity to n^{2}(O(n^{2}) + O(n)) ≈ O(n^{4}). Finally, the repetitions in the step (3) increase the complexity to n(O(n^{4})) ≈ O(n^{5}).

6 Data

We implemented the enumeration algorithm into the computer and determined the number of unlabeled disconnected posets up to 17 elements (Table 3 and Table 4) and the number of unlabeled disconnected N-free posets up to 15 elements (Table 5) according to the number of connected direct terms of the posets.

m⧹ n 2 3 4 5 6 7 8 9 10 11 12 13
2  1 1 4 13 60 312 2075 17316 186173 2594568 47041877 1108710868
3  1 1 4 14 63 328 2159  17801  189406  2620368  47298156
4  1 1 4 14 64 331  2175  17885  189906  2623701
5  1 1 4 14  64  332  2178  17901  189990
6  1 1  4  14  64  332  2179  17904
7  1  1  4  14  64  332  2179
8  1  1  4  14  64  332
9  1  1  4  14  64
10  1  1  4  14
11  1  1  4
12  1  1
13  1
Total: 1 2 6 19 80 395 2487 19890 206565 2804453 49872647 1158843214

Table 3: The number of n-element unlabeled disconnected posets for 2 ≤ n ≤ 13 according to the number of connected direct terms m, 2 ≤ m ≤ 13.

m⧹n  14  15  16  17
2  33887448384  1339579736074  68314951618033  4484639396830962
3  1111998749  33943069332  1340826402638  68351780482060
4  47324726  1112260708  33946401908  1340882409188
5  2624201  47328080  1112287428  33946665077
6  190006  2624285  47328580  1112290782
7  17905  190009  2624301  47328664
8  2179  17905  190010  2624304
9  332  2179  17905  190010
10  64  332  2179  17905
11  14  64  332  2179
12  4  14  64  332
13  1  4  14  64
14  1  1  4  14
15  1  1  4
16  1  1
17  1
Total: 35049606566  1374685228988  69690886873398  4554367168841547

Table 4: The number of n-element unlabeled disconnected posets for 14 ≤ n ≤ 17 according to the number of connected direct terms m, 2 ≤ m ≤ 17.

m⧹n 2 3 4 5 6 7 8  9  10  11  12  13  14  15
2  1 1 4 12 46 173 727 3195 15017 74404 388895 2134070 12266637 73642052
3  1 1 4 13 49 188 795 3502 16436 81146 421816 2300237 13134628
4  1 1 4 13 50 191 810 3570 16758 82655 429138 2336477
5  1 1 4 13 50 192 813 3585 16826  82977 430668
6  1 1 4 13  50 192  814  3588  16841  83045
7  1 1  4  13  50  192  814  3589  16844
8  1  1  4  13  50  192  814  3589
9  1  1  4  13  50  192  814
10  1  1  4  13  50  192
11  1  1  4  13  50
12  1  1  4  13
13  1  1  4
14  1  1
15  1
Total: 1 2 6 18 65 241 984 4250 19590 95484 491459 2660030 15100494 89648378

Table 5: The number of n-element unlabeled disconnected N-free posets for 2 ≤ n ≤ 15 according to the number of connected direct terms m, 2 ≤ m ≤ 15.

7 Acknowledgment

This work was supported by the Research Grant 2020-21, SUST Research Center, Shahjalal University of Science and Technology, Sylhet-3114, Bangladesh [Grant no. PS/2020/1/19]. Special thanks to the anonymous referee for carefully reading the manuscript and giving many corrections and suggestions for the improved presentations of the results.

References

[1] B. I. Bayoumi, M. H. El-Zahar, and S. M. Khamis, Algorithmic counting of types of UPO graphs and posets, Congr. Numer. 127 (1997), 117–122.

[2] M. Bodirsky, O. Giménez, M. Kang, and M. Noy, Enumeration and limit laws for seriesparallel graphs, European J. Combin. 28 (2007), 2091–2105.

[3] G. Brinkmann and B. McKay, Posets on up to 16 Points, Order 19 (2002), 147–179.

[4] C. Chaunier and N. Lygeros, The number of orders with thirteen elements, Order 9 (3) (1992), 203–204.

[5] B. A. Davey and H. A. Priestly, Introduction to Lattices and Order, 2nd Edition, Cambridge University Press, 2002.

[6] M. Erné, On the cardinalities of finite topologies and the number of antichains in partially ordered sets, Discrete Math. 35 (1981), 119–133.

[7] J. Heitzig and J. Reinhold, The number of unlabeled orders on fourteen elements, Order 17 (2000), 333–341.

[8] S. M. Khamis, On numerical counting of prime, UPO, and the general type of posets according to heights, Congr. Numer. 146 (2000), 157–171.

[9] S. M. Khamis, Height counting of unlabeled interval and N-free posets, Discrete Math. 275 (2004), 165–175.

[10] S. M. Khamis, Recognition of prime posets and one of its applications, J. Egypt. Math. Soc. 14 (2006), 5–13.

[11] Y. Koda, The numbers of finite lattices and finite topologies, Bull. Inst. Combin. Appl. 10 (1994), 83–89.

[12] S. U. Mohammad, A Study of Recognition and Enumeration for Decomposable Ordered Sets, Ph.D. Thesis, Dept. of Mathematics, Shahjalal University of Science and Technology, Sylhet-3114, Bangladesh, 2022.

[13] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2022. Available

    at https://oeis.org.

2020 Mathematics Subject Classification: Primary 06A07; Secondary 05A15, 11Y55. Keywords: unlabeled posets, exact enumeration, direct sum, enumeration algorithm, polynomial time-complexity.

(Concerned with sequences \underline{A000112}, \underline{A202182}, \underline{A263864}, \underline{A349367}, \underline{A349401}, and \underline{A350783}.)

Received February 08 2022; revised version received June 5 2022. Published in Journal of Integer Sequences, June 16 2022.

Return to Journal of Integer Sequences home page.