10
$\begingroup$

For a set $S$ with $n$ elements, the notation for a combination $\binom{n}{k}$, or $C(n, k)$, indicates the number of combinations of $k$ elements from $S$, but how does one indicate the actual set created from combinations of $k$ elements from $S$? That is, $\binom{n}{k}$ is the size of the set I'd like to represent.

Likewise, how would one indicate the actual set of items created from the permutations of $k$ elements, rather than the size of that set?

3 Answers 3

10

Wikipedia says that the set of all $k$-combinations of a set $S$ is sometimes denoted by $${S \choose k}$$

  • 2
    This notation is used for example in Stanley's *Enumerative Combinatorics* (see Vol. I, p. 13).2011-03-21
  • 0
    Consider mentioning how to read that.2017-12-18
  • 0
    @Abcd "the set of all $k$-combinations of a set $S$" is one possibility, but the question asked for notation2017-12-18
  • 0
    @Henry I have heard something like "k choose S" , is it correct?2017-12-18
  • 0
    @Abcd more commonly "$S$ choose $k$", i.e. choosing $k$ items from $S$. But that usage is more typical common when $S$ is a number rather than a set, and when ${S \choose k}$ gives a number rather than a set of sets2017-12-18
6

The set of combinations is the collection of all subsets of $\{1,2,\ldots,n\}$ of size $k$; if we let $[n]=\{1,2,\ldots,n\}$ (more or less common, depending on the context) $\mathcal{P}(X)$ denote the set of all subsets of $X$, then you are looking for the set $$\bigl\{ A\in\mathcal{P}([n])\bigm| |A|=k\bigr\}.$$ I do not think there is any particular notation for it, but $$\mathcal{P}_k([n])$$ seems reasonable enough. You would have to specify it, though.

For permutations, the order matters. So you are looking for the set of all function $f\colon[k]\to[n]$ that are one-to-one. Again, there is no standard notation, but the set of all functions is $[n]^{[k]}$, so you would want $$\bigl\{ f\in [n]^{[k]}\bigm| f\text{ is one-to-one}\bigr\}.$$ Equivalently, you would want all $k$-tuples that have $k$-distinct elements. So, using the previous notation for subsets of size $k$, you would have: $$\bigl\{ f\in[n]^{[k]}\bigm| f([k]) \in \mathcal{P}_k([n])\bigr\}.$$

2

A common notation for the collection of all size-$k$ subsets of $S$ is given by the symbol $S_k$.