Is this a violation of the Pigeonhole Principle?

Question

Given a set $S$ of elements [1, to 21] generate a list of permutations fixed to a constant of $3$.

$P(n,r)$=$P(21,3)$

$=21!/(21−3)!$

$= 7980$ possible permutations of 3-element sets

Fact: There are $23940$ elements altogether; because $7980*3 = 23940$ and there are 3-elements in each set. Remember this is a list of permutations of $3$ generated from elements from $S$.

Consider that, I have a select few $3$-$element$ sets but with two empty slots in each set. The empty slots can ONLY be filled from elements in $S$. (But can only be an exact cover of $S$)

Example:

$(1,~,~)$$(2,~,~)$$(3,~,~)$$(4,~,~)$$(5,~,~)$$(6,~,~)$$(7,~,~)$

Remember that our list $S$ has integers [1, to 21] and $21$/$3$ $=$ $7$.

I can find the set difference to see what elements I need.

Set difference:

I crossed out the elements that exist in the sets above to see what I need.

$S$ = $X,X,X,X,X,X,X,8,9,10,11,12,13,14,15,16,17,18,19,20,21$

I need $14$ integers to create an exact cover for $S$.

$Needed~~elements$ = $8,9,10,11,12,13,14,15,16,17,18,19,20,21$

Violation of the Pigeonhole Principle??

I need $14!$ orderings below to find all possible Exact Covers that have 1,2,3,4,5,6,7 starting at the first in each set of $3$

$(1,~,~)$$(2,~,~)$$(3,~,~)$$(4,~,~)$$(5,~,~)$$(6,~,~)$$(7,~,~)$

Well, that's bad news... $14!$ = $87178291200$ and $14!$ > 7980*3 or $23940$ elements.

Question

How is it even possible to have $14!$ orderings in $23940$ elements of the list we just generated?

Answer 1

I agree with you down to the statement that there are $23940$ elements in all the $3$ element permutations from $S$. The next sentence makes no sense at all. It appears you are computing the number of ways of filling in your $7$ tuples (not sets because they are ordered) with the other $14$ elements of $S$. Yes, there are $14!$ ways to do that. Why should that have any relation to the $23940$ number? There are $7980$ three tuples. You are selecting some of them with restrictions. There are lots of ways to do that. They have no relation to $3$ times the number of tuples you are selecting from.

Answer 2

Your figure of $14!$ is the number of sequences of $7$ ordered triples from the set $\{1,2,\ldots,21\}$ such that

• $1$ appears in the first triple, $2$ in the second, and so on through $7$, and
• each integer in the set appears in exactly one of the ordered triples.

It’s perfectly true that there there are only $7980$ different ordered triples from that set and that listing them would entail listing $3\cdot7980=23,940$ individual members of that set, but those figures has only a very indirect connection with what your $14!$ is counting.