CHAINS, MULTICHAINS AND MOBIUS NUMBERS

For any finite poset P and any integer k greater-than-or-equal-to 0, l et alpha(k)(P) denote the number of k-chains (i.e. chains of cardinali ty k or length k- 1) in P. The polynomial alpha(p, X)=SIGMA(k greater- than-or-equal-to 0) alpha(k)(P)X(k) will be referred to as the chain g enerating polynomial of P. Our first results determine the chain gener ating polynomial alpha(P x Q, X) and the multichain generating series m(P x Q, X) of the ordinal product P x Q, for any two finite posets P and Q. Using this we determine the Mobius function for certain ordinal products. For any integer n greater-than-or-equal-to 1 let [n], B(n), D(n), L(n)(q) and PI(n) denote the lattices defined by Stanley (1986) . When P is one of the posets [n], B(n) or D(n) the values of alpha(k) (P) for any k greater-than-or-equal-to 0 are well known and can easily be determined. When P=L(n)(q) or PI(n) we will establish recurrence r elations in this paper which will effectively determine alpha(k)(P). F or example, we explicitly determine alpha(k)(L(n)(q)) for all k greate r-than-or-equal-to 0 when n less-than-or-equal-to 3. We also obtain re currence relations for the number m(k)(P) of k-multichains of P when P = L(n)(q) or PI(n). Using these we explicitly determine m(k)(L(n)(q)) for n less-than-or-equal-to 4.