Counting permutations that respect a partial order

Question

Suppose you have three kinds of coins, say: pennies, nickels, and dimes. Each penny has a unique date, likewise for nickels and dimes. (A penny and a nickel may have the same date, etc.) How many ways can you line up the coins in order of date by type? In other words: How many ways can you line up the coins such that if you look at any two coins of the same type, they will be in the correct order by date? (You do not care if two coins of different types are out of order by date.)

The coins are just scaffolding of course. And, I'm interested in more general cases but this was hard enough alread to warrant a question in my mind. So, once again:

Given $3$ sets, $A, B, C$ (with sizes $|A|,|B|,|C|$ respectively) each with a total order, but no "inter-set" order, this defines a partial order on $A\cup B \cup C$. How many permutations of the elements of $A\cup B \cup C$ respect this partial order?

For in the case of only two sets, say $C = \{\}$, The answer is easily seen to be ${|A|+|B| \choose |A|}={|A|+|B| \choose |B|} $. But I don't know how to generalize this to three (or more) sets. I've written some code that can easily compute these counts for smallish sets but I can't see the pattern. Help!

This is a generalization of a question I read on this site that I am now unable to find. If you know it, or can find it, please link it! (that question basically asked about two kinds of items) Thanks.

Answer 1

With disjoint sets of sizes $a$, $b$, and $c$ the number of ways is the multinomial coefficient $$\dbinom{a+b+c}{a,b,c}=\frac{(a+b+c)!}{a!b!c!}.$$

Remark: To see this, note that we are looking for the number of "words" of length $a+b+c$ that have $a$ A's, $b$ B's, and $c$ C's.

The location of the A's can be chosen in $\binom{a+b+c}{a}$ ways. For each such way, the location of the B's can be chosen in $\binom{b+c}{b}$ ways, for a total of $\binom{a+b+c}{a}\binom{b+c}{b}$. Express this in terms of factorials, and you will get the formula of the answer.

Answer 2

Let $a, b, c$ denote the cardinalities of $A, B, C$, respectively. You have a total of $a + b + c$ placeholders, $a$ of which you will assign to elements of $A$, $b$ of which you will assign to elements of $B$ and $c$ of which you will assign to $C$. Since the individual sets are totally ordered, once you've picked the placeholders, you have a unique way of placing the individual elements to respect the ordering.

The number of ways to choose the placeholders is the multinomial coefficient $$ {a+b+c \choose a, \, b, \, c} = \frac{(a+b+c)!}{a!b!c!}.$$

The generalization to $n$ sets is immediate. If they have cardinalities $a_1, a_2, \dots, a_n$, then the number of orderings you want is $$ {a_1 + a_2 + \cdots + a_n \choose a_1, \, a_2, \, \dots, \, a_n} = \frac{(a_1 + a_2 + \cdots + a_n)!}{a_1! a_2! \cdots a_n!}. $$