Counting proper mergings of chains and antichains

A proper merging of two disjoint quasi-ordered sets ( P , ← P ) and ( Q , ← Q ) , denoted by P and Q , respectively, is a quasi-order on the union of P and Q such that the restriction to P or Q yields the original quasi-orders on those sets and such that no elements of P and Q are identified. In this article, we consider the cases where P and Q are chains, where P and Q are antichains, and where P is an antichain and Q is a chain. We give formulas that determine the number of proper mergings in all three cases. We also introduce two new bijections from proper mergings of two chains to plane partitions and from proper mergings of an antichain and a chain to monotone colorings of complete bipartite digraphs.