En studie om Pomängdsprobabilitet

Let be a finite poset (partially ordered set) with cardinality . A linear extension of is an order-preserving bijection : , that is, if in then . We define the poset probability as the proportion of linear extensions where . We are primarily interested in for incomparable elements . The probability has significance in areas such as information theory. Let denote the total number of linear extensions of . We prove that the poset probability can be evaluated as where is the set of order ideals of without or , where we can add to get a new order ideal of . The practicality of the preceding formula is explored and we show that The formula is particularly useful for certain classes of posets such as partition posets which are examined in further detail. We apply the formula to prove that, for all partition posets of shape , the probability obeys where is the nth Catalan number and . We also explore how Monte Carlo methods can be used to estimate