1
$\begingroup$

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?

$\endgroup$
9
  • 1
    $\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$
    – hmakholm left over Monica
    Jul 24, 2016 at 12:20
  • 1
    $\begingroup$ How does "choosing $\binom54$ of the items" produce a set with less than $\binom54$ items in it? $\endgroup$
    – hmakholm left over Monica
    Jul 24, 2016 at 14:46
  • 1
    $\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$
    – hmakholm left over Monica
    Jul 24, 2016 at 14:57
  • 1
    $\begingroup$ Your question expliclitly speaks about "the set of all sets that are formed by choosing $5$ items". The sets in your set have only $4$ members each, not $5$. If you want to speak about sets that are formed by choosing $4$ items, you should not describe them as "sets that are formed by choosing $5$ items", becuase $4$ and $5$ are different numbers, and none of your $4$-element sets represent a choice of $5$ items. $\endgroup$
    – hmakholm left over Monica
    Jul 24, 2016 at 15:03
  • 1
    $\begingroup$ {3,7,6,5} is not a set that is formed by choosing 5 items. {3,6,5,9} is not a set that is formed by choosing 5 items. {3,7,5,9} is not a set that is formed by choosing 5 items. {3,7,6,9} is not a set that is formed by choosing 5 items. {7,6,5,9} is not a set that is formed by choosing 5 items. $\endgroup$
    – hmakholm left over Monica
    Jul 24, 2016 at 15:05

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2016 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, 2016 at 11:49
1
$\begingroup$

\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$ ...
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .