Let $X$ be the set of all nonempty subsets of a given finite set $F$. I am looking for the number of permutations $f$ of $X$ such that for any proper subset $A$ of $F$ the sets $A$ and $f(A)$ are disjoint.

  • $\begingroup$ As written I'd say there are none -- no matter how you permute $X$, you can't make $F$ and $f(F)$ disjoint, because you're excluding the empty subset. $\endgroup$ – Henning Makholm Nov 28 '15 at 12:35
  • $\begingroup$ @HenningMakholm Sorry I forgot to mention that the sets are proper. I have edited the problem. $\endgroup$ – alex alexeq Nov 28 '15 at 12:41

There is exactly one such permutation:

Theorem. Let $F$ be a finite set, and let $f$ be a permutation of $\mathcal P(F)\setminus \{\varnothing\}$ with the property that $A$ and $f(A)$ are disjoint for all proper nonempty subsets $A$. Then for each proper nonempty subset $A$ it holds that $f(A)=F\setminus A$.

Proof by long induction on $|F|-|A|$.

Let $A$ be such a set. We know that $f(A)$ is a subset of $F\setminus A$. All of the proper nonempty subsets of $F\setminus A$ are complements of proper supersets of $A$, and from the induction hypothesis we know that every such superset of $A$ maps to its complement. Since $f$ (being a permutation) is injective, $f(A)$ cannot be any of the proper subsets of $F\setminus A$, so $F\setminus A$ itself is the only possible value of $f(A)$, which completes the proof.

The above theorem fixes the value of $f(A)$ for all $A$ except $F$ itself. But by now all other possible values of $f(F)$ have been taken, so we must have $f(F)=F$.

Thus, the permutation $f$ is completely determined by the conditions given.

On the other hand, if $F$ is infinite, there are many such permutations -- in fact $2^{2^{|F|}}$ of them, same as the total number of permutations of $\mathcal P(F)$.

  • $\begingroup$ Thanks, what happens if we allow the emptyset to be a member of $X$ ? $\endgroup$ – alex alexeq Nov 28 '15 at 13:38
  • $\begingroup$ @alexalexeq: But still don't require $f(F)$ to be disjoint from $F$? Then there'll be some choice: One of the proper subsets can be allowed to map to $\varnothing$, and then its complement is free to be the image of one of the subsets of the subset, and so forth. Then we'll get as many permutations as there are chains in $\mathcal P(F)$, which I don't know offhand how to count. $\endgroup$ – Henning Makholm Nov 28 '15 at 13:43
  • $\begingroup$ The number of chains is investigated in this question; every other such chain will give rise to a permutation when $\varnothing$ is included and $f(F)$ is allowed to be nonempty. $\endgroup$ – Henning Makholm Nov 29 '15 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.