Counting number of permutations respecting partial order
Brightwell and Winkler proved that this program is #P-complete in their paper Counting linear extensions. You can, however, estimate the number of linear extensions efficiently.