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?

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ This notation is used for example in Stanley's Enumerative Combinatorics (see Vol. I, p. 13). $\endgroup$ – Hans Lundmark Mar 21 '11 at 18:57
  • $\begingroup$ Consider mentioning how to read that. $\endgroup$ – Abcd Dec 18 '17 at 9:07
  • $\begingroup$ @Abcd "the set of all $k$-combinations of a set $S$" is one possibility, but the question asked for notation $\endgroup$ – Henry Dec 18 '17 at 10:21
  • $\begingroup$ @Henry I have heard something like "k choose S" , is it correct? $\endgroup$ – Abcd Dec 18 '17 at 11:25
  • $\begingroup$ @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 sets $\endgroup$ – Henry Dec 18 '17 at 14:08
6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.