The enumeration of permutations whose posets have a maximum element

Recently, Tenner [B.E. Tenner, Reduced decompositions and permutation patterns, J. Algebraic. Combin., in press, preprint arXiv: math.CO/0506242] studied the set of posets of a permutation of length n with unique maximal element, which arise naturally when studying the set of zonotopal tilings of Elnitsky's polygon. In this paper, we prove that the number of such posets is given byP5n−4P5(n−1)+2P5(n−2)−∑j=0n−2CjP5(n−2−j), where PnPn is the n  th Padovan number and CnCn is the nth Catalan number.