We study the distribution of combinatorial statistics that exhibit a structure of crossings and nesting in various discrete structures, in particular, in set partitions, matchings, and fillings of moon polyominoes with entries 0 and 1. Let pi and y be two set partitions with the same number of blocks. Assume pi is a partition of [n]. For any integers l, m >̲ 0, let T (pi, l) be the set of partitions of [n + l] whose restrictions to the last n elements are isomorphic to pi, and T (pi, l, m) the subset of T (pi, l) consisting of those partitions with exactly m blocks. Similarly define T (pi, l) and T (y, l, m). We prove that if the statistic cr (ne), the number of crossings (nestings) of two edges, coincides on the sets T (pi, l) and T (pi, l) for l = 0; 1, then it coincides on T (pi, l, m) and T (y, l, m) for all l, m >̲ 0. These results extend the ones obtained by Klazar on the distribution of crossings and nestings for matchings. Moreover, we give a bijection between partially directed paths in the symmetric wedge y = +̲ x and matchings, which sends north steps to nestings. This gives a bijective proof of a result of E. J. Janse van Rensburg, T. Prellberg, and A. Rechnitzer that was first discovered through the corresponding generating functions: the number of partially directed paths starting at the origin confined to the symmetric wedge y = +̲ x with k north steps is equal to the number of matchings on [2n] with k nestings. Furthermore, we propose a major index statistic on 01-fillings of moon polyominoes which, when specialized to certain shapes, reduces to the major index for permutations and set partitions. We consider the set F(M, s, A) of all 01-fillings of a moon polyomino M with given column sum s whose empty rows are A, and prove that this major index has the same distribution as the number of north-east chains, which are the natural extension of inversions (resp. crossings) for permutations (resp. set partitions). Hence our result generalizes the classical equidistribution results for the permutation statistics inv and maj. Two proofs are presented. The first is an algebraic one using generating functions, and the second is a bijection on 01-fillings of moon polyominoes in the spirit of Foata's second fundamental transformation on words and permutations.

We study universal cycles of the set P(n,k) of k-partitions of the set [n]:={1,2,…,n} and prove that the transition digraph associated with P(n,k) is Eulerian. But this does not imply that universal cycles (or ucycles) exist, since vertices represent equivalence classes of partitions. We use this result to prove, however, that ucycles of P(n,k) exist for all n≥3 when k=2. We reprove that they exist for odd n when k=n−1 and that they do not exist for even n when k=n−1. An infinite family of (n,k) for which ucycles do not exist is shown to be those pairs for which (Formula presented) is odd (3≤k

In this paper we consider the enumeration of ordered set partitions avoiding a permutation pattern of length 2 or 3. We provide an exact enumeration for avoiding the permutation 12. We also give exact enumeration for ordered partitions with 3 blocks and ordered partitions with n-1 blocks avoiding a permutation of length 3. We use enumeration schemes to recursively enumerate 123-avoiding ordered partitions with any block sizes. Finally, we give some asymptotic results for the growth rates of the number of ordered set partitions avoiding a single pattern; including a Stanley-Wilf type result that exhibits existence of such growth rates.

Covering arrays for words of length (Formula presented.) over a (Formula presented.) -letter alphabet are (Formula presented.) arrays with entries from the alphabet so that for each choice of (Formula presented.) columns, each of the (Formula presented.) (Formula presented.) -letter words appears at least once among the rows of the selected columns. We study two schemes in which all words are not considered to be different. In the first case known as partitioning hash families, words are equivalent if they induce the same partition of a (Formula presented.) element set. In the second case, words of the same weight are equivalent. In both cases, we produce logarithmic upper bounds on the minimum size (Formula presented.) of a covering array. Definitive results for (Formula presented.), as well as general results, are provided.

In the first part of this thesis we generalise the well-known K-terminal reliability R(G,K) to different kinds of terminal vertices. By means of lattice theoretic tools, we propose a divide and conquer approach to compute this new reliability measure efficiently. The first part concludes with an improved path decomposition algorithm that computes R(G,K) much more memory and time efficient compared to current state-of-the-art algorithms. In the second part we discuss the counting of connected set partitions of a graph G and its application to network reliability problems. Again we utilise the lattice theoretic approach to carry out the counting efficiently. Finally, we investigate the domination reliability DR(G) of a graph G as an interesting network reliability measure.

In the first part of this thesis we generalise the well-known K-terminal reliability R(G,K) to different kinds of terminal vertices. By means of lattice theoretic tools, we propose a divide and conquer approach to compute this new reliability measure efficiently. The first part concludes with an improved path decomposition algorithm that computes R(G,K) much more memory and time efficient compared to current state-of-the-art algorithms. In the second part we discuss the counting of connected set partitions of a graph G and its application to network reliability problems. Again we utilise the lattice theoretic approach to carry out the counting efficiently. Finally, we investigate the domination reliability DR(G) of a graph G as an interesting network reliability measure.