# Any permutation of {1,2,3,4} generates a permutation of the 6 subsets of {1,2,3,4} that have exactly 2 elements. So ...

We could convert or encode a permutation of the 6 subsets of {1,2,3,4} that have exactly 2 elements into a permutation of {1,2,3,4,5,6}, but I would like to keep things in their original form. In other words, what gets permuted is precisely the set { {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}}.

It may be helpful to explain the motivation, before I get to the actual question. I'm interested in generalizing from an ordinary binary one-time pad for encryption of data that is not necessarily binary. Let's suppose that we have converted our plain-text into a sequence of symbols, with each symbol in the sequence chosen from an inventory or alphabet of exactly 6 values.

Now, if we write each of the six values of our inventory or alphabet as a four-digit sequence of zeroes and ones, with exactly two 0s and exactly two 1s in each such four-digit sequence, then we have a simple representation of a 2-element subset of {1,2,3,4}.

Given this context, it seems obvious that if each of the 24 permutations of {1,2,3,4} is equally likely to arise, and the sequence of permutations of {1,2,3,4} is truly random, and we apply a one-time pad sequence of permutations of {1,2,3,4} to our input sequence (each item of the input sequence being one of six possible values) ...

... then our output cipher-text should give no clues about the input sequence.

My question: what is special about the 24 permutations?

If we considered all possible permutations of 6 things, then we would be looking at not merely 24 possible permutations, but (24 * 5 * 3 * 2) = (24 * 30) permutations. So a selection has been made.

Often, when we consider permutations of 6 things, we assume for the sake of convenience and simplicity that those six things are simply the numbers from 1 to 6. However, I haven't selected one particular subset of 24 permutations from the set of all permutations of {1, ..., 6}. What I have done is identify a kind of subset of the set of permutations of {1, ..., 6}. In particular, the kind of subset that I have described always consists of exactly 24 permutations.

To get one particular set of 24 permutations, as described, from among the permutations of {1, ..., 6}, we would need to use a particular one-to-one correspondence between {1, ..., 6} and the set of subsets of {1,2,3,4} that have exactly 2 elements.

If there's a simple and clear answer, then I am hoping that it's possible to generalize. For example, maybe 4 becomes 2k and 6 gets replaced with C(2k,k), the number of subsets of a set of 2k elements, each subset having exactly k elements. However, we can initially keep things very simple and specific, with k = 2.

• Do you know some basic group theory? Knowing that will help an answerer choose language. In short, an assignment of combinations of $1, 2, 3, 4$ taken $2$ at a time to $1, \ldots, 6$ defines an embedding of groups (an injective group homomorphism) $S_4 \hookrightarrow S_6$, and changing your mind about the assignments, say, by composing the assignment with $g \in S_6$ replaces the image of the homomorphism with the conjugate copy $g S_4 g^{-1}$ of $S_4$ in $S_6$. Feb 22, 2023 at 22:41

The $$24$$ permutations used have the property that if two subsets share an element, the mappings of those two subsets also share an element.
Imagine we build a regular tetrahedron out of $$4$$ identical marshmallows (vertices) and $$6$$ differently colored sticks (edges). If we say the tetrahedron must have one vertex on top, one in front, one in a rear-left position, and one in a rear-right position, that fixes the overall shape. The full $$6!$$ permutations are like taking the whole thing apart and putting it together any which way. The $$4!$$ permutations are the ones we can get by rotating and reflecting the whole shape. These symmetry permutations preserve connectedness properties: Two edges either share a vertex or don't, before and after the permutation. Three edges either form a triangle or don't, before and after the permutation.
If we generalize to the effects of the $$n!$$ permutations of a set of $$n$$ elements on its $$n \choose k$$ subsets of size $$k$$, we have similar facts. (It's not necessary that $$n=2k$$, but that does give a relatively large number of subsets.) For example, the size of intersections is preserved: given $$A \subset C$$ and $$B \subset C$$ and a permutation $$\sigma$$ of $$C$$, then
$$|\sigma(A) \cap \sigma(B)| = |A \cap B|$$
The same can't be said of a general $$\sigma$$ which just permutes the subsets.