Subsets of a Finite Set

Subsets(S): SetEnum -> SetEnum

The set of all subsets of the set \(S\).

Subsets(S, k): SetEnum, RngIntElt -> SetEnum

The set of subsets of the set \(S\) of size \(k\). If \(k\) is larger than the cardinality of \(S\) then the result will be empty.

Multisets(S, k): SetEnum, RngIntElt -> SetEnum

The set of multisets consisting of \(k\) not necessarily distinct elements of the set \(S\).

Subsequences(S, k): SetEnum, RngIntElt -> SetEnum

The set of sequences of length \(k\) with elements from the set \(S\).

Permutations(S): SetEnum -> SetEnum;

The set of permutations (stored as sequences) of the elements of the set \(S\).

Permutations(S, k): SetEnum, RngIntElt -> SetEnum;

The set of permutations (stored as sequences) of each of the subsets of the set \(S\) of cardinality \(k\).

Example: Odd Graph (ex-676132)

The use of Subsets is illustrated in the construction of the Petersen graph as the third Odd Graph. The \(n\)th Odd Graph has its vertices in correspondence with the \((n-1)\)-element subsets of \(\lbrace 1 \ldots 2n-1 \rbrace\), and an edge between two vertices if and only if their corresponding sets have empty intersection.

> V := Subsets( {1 .. 2*n-1}, n-1) where n is 3;
> V;
{
    { 1, 5 },
    { 2, 5 },
    { 1, 3 },
    { 1, 4 },
    { 2, 4 },
    { 3, 5 },
    { 2, 3 },
    { 1, 2 },
    { 3, 4 },
    { 4, 5 }
}
> E := { {u, v} : u,v in V | IsDisjoint(u, v) };
> Petersen := Graph< V | E >;

Run in calculatorCopy input