I've been searching for a way to express "the set of all combinations generated by taking $\binom{n}{k}$ items". For example, if I have the set $\{3,7,6,5,9\}$, and I want the set of all sets that are formed by making $\binom{5}{4}$ choices, then the result would be

$\{\{3,7,6,5\}, \{3,6,5,9\}, \{3,7,5,9\}, \{3,7,6,9\}, \{7,6,5,9\}\}$

But I'm struggling to find a notation that describes this. I can describe the number of results with $\binom{5}{4}=5$, but how do I describe the resulting set-of-sets itself? The notation $5 \brace 4$ is already taken by Stirling numbers. I've looked at articles and questions about sets, set theory, the binomial coefficient, and I've drawn a blank.

So, is there a standard notation? (I feel that, surely, there must be!) If there is, what is it? And if there isn't, could anyone suggest a notation that would be halfway familiar to a reader?

  • $\begingroup$ $\binom54$ is $5$, and each of the sets you display have only $4$ elements. The only subset of $\{3,7,6,5,9\}$ that has $\binom54$ elements is $\{3,7,6,5,9\}$ itself! $\endgroup$ – Henning Makholm Jul 24 '16 at 12:20
  • $\begingroup$ $\binom{5}{4}=5$, so there are 5 unique sets in total (shown in the question), and each set has 4 elements. $\binom{5}{5}=1$, so there is 1 unique set in total ($\{3,7,6,5,9\}$), and that set has 5 elements. $\endgroup$ – Rhyme Jul 24 '16 at 14:44
  • $\begingroup$ How does "choosing $\binom54$ of the items" produce a set with less than $\binom54$ items in it? $\endgroup$ – Henning Makholm Jul 24 '16 at 14:46
  • $\begingroup$ It does not. There are 5 subsets, count them in my question. $\endgroup$ – Rhyme Jul 24 '16 at 14:49
  • $\begingroup$ x @Rhyme: I've counted. $\{3,7,6,5\}$ contains only $4$ items, countrary to your claim that you produced it by choosing $\binom 54=5$ of the items in $\{3,7,6,5,9\}$. $\endgroup$ – Henning Makholm Jul 24 '16 at 14:57

You want a notation for the set of all $k$-element subsets of some set $X$. There’s a standard notation for this: $[X]^k$. However, it’s most commonly found in set theory and some areas of combinatorics and for a more general audience is quite likely to be unfamiliar to some readers, so you’d do well to define it anyway.

Added: I don’t care for the notation myself, but it occurs to me that I have also seen the notation $\binom{X}k$ used, by analogy with the binomial coefficient itself. Here again it would be a good idea to define the notation if you use it.

  • $\begingroup$ Thank you very much, that is very comprehensive. Might I ask if the different notations tend to be used in different fields? I am writing for a Computer Science audience myself, and am specifically wondering whether one of these notations may be more familiar for that audience. If not, I too find the first notation to be more accessible, and will likely default to defining & using it. $\endgroup$ – Rhyme Jul 24 '16 at 11:45
  • $\begingroup$ @Rhyme: You’re most welcome. I’ve seen the second notation only a few times; I don’t know whether that’s because it’s more common in fields that I don’t normally see, or whether it’s because it’s genuinely not very common at all. In particular, I’m afraid I don’t know how likely either is to be familiar to a computer science audience. $\endgroup$ – Brian M. Scott Jul 24 '16 at 11:49

\begin{array}{ccl} &2^S\qquad&\qquad \text{the set of all subsets of the set } S\\ &\binom{S}{k}\qquad&\qquad \text{the set of $k$-element subsets of } S\\ \end{array}

We can find in section 1.2, p.23 in his classic Enumerative Combinatorics, ed. 2 also the preferred wording for the symbol.

  • Now define $\binom{S}{k}$ (sometimes denoted $S^{(k)}$ or otherwise, and read $S$ choose $k$) to be the set of all $k$-element subsets (or $k$-subsets) of $S$ ...

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.