KSubsets

The k-element subsets of $\{1, \dots, n\}$ in lexicographic order (the combinations).

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaCombination↗MathWorldk-Subset↗Combination↗WikidataQ202805↗Encyclopedia of MathematicsCombination↗Britannicatopic/combination↗OEISA007318✓↗Wolfram LanguageBinomial↗SageMathSubsets(n, k)↗SymPysubsets↗mathlib4Finset.powersetCard k↗MATLABnchoosek↗Rosetta CodeCombinations↗

KSubsets(n, k)the $\binom{n}{k}$ subsets of size $k$

CombinatoricaKSubsets[Range[n], k]

Typed signatures

Type	Package	Applies
(integer<0..>, integer<0..>) -> indexed_collection<finset>	combinatorics	always

Domain: Combinatorial collections

Details

• Count is the binomial coefficient $\binom{n}{k}$
• Elements are the k-combinations in lexicographic order: compare the smallest element first, so $\{1,4\}$ precedes $\{2,3\}$
• IntegerDigits with CombinatorialNumerals(k) unranks in colexicographic order, which is not this one
• $k = 0$ gives the single empty subset; $k > n$ gives an empty family

Definition

Epsil, as the implementation runs it.

count(_n, _k)

Fold(
      Function(gc + (Binomial(_n, gn) if gn == _k else 0), gc, gn),
      0,
      Range(0, _n, 1),
    )

unrank(_n, _k, _r)

Apply(
       (gp: list<integer>) => Apply(
                                     (gm: list<integer>) => gm,
                                     Rest(Fold(
                                                Function(Apply(
                                                                (lc: list<integer>) => Join([lc[1]], Rest(ls_g), [lc[2]]),
                                                                Fold(
                                                                      Function(
                                                                                lp_g if lp_g[2] != 0 ||
                                                                                        lv_g <=
                                                                                        (0 if lj_g == 1 else ls_g[lj_g]) else [lp_g[1], lv_g] if lp_g[1] <
                                                                                                                 Binomial(_n - lv_g, gp[2] - lj_g) else [lp_g[1] -
                                                                                                                        Binomial(_n - lv_g, gp[2] - lj_g), 0],
                                                                                lp_g,
                                                                                lv_g,
                                                                              ),
                                                                      [
                                                                        ls_g[1],
                                                                        0,
                                                                      ],
                                                                      Range(
                                                                             1,
                                                                             _n,
                                                                             1,
                                                                           ),
                                                                    ),
                                                              ), ls_g, lj_g),
                                                [gp[1]],
                                                Range(1, gp[2], 1),
                                              )),
                                   ),
       Fold(
             Function(gs if gs[2] >= 0 else [gs[1], gk] if gs[1] <
                                                           (Binomial(_n, gk) if gk == _k else 0) else [gs[1] -
                                                                  (Binomial(
                                                                             _n,
                                                                             gk,
                                                                           ) if gk ==
                                                                               _k else 0), -1], gs, gk),
             [_r, -1],
             Range(0, _n, 1),
           ),
     )

rank(_n, _k, _x)

Apply((gy: list<integer>) => Fold(Function(gb +
                                           (Binomial(_n, gt) if gt == _k else 0), gb, gt), 0, Range(
                                                                0,
                                                                Length(_x) - 1,
                                                                1,
                                                              )) + Fold(
                                                                        Function(kr +
                                                                                 Fold(
                                                                                       Function(kq +
                                                                                                Binomial(_n - kv, Length(_x) - kj), kq, kv),
                                                                                       0,
                                                                                       Range((0 if kj == 1 else gy[kj - 1]) +
                                                                                             1, gy[kj] - 1, 1),
                                                                                     ), kr, kj),
                                                                        0,
                                                                        Range(1, Length(_x), 1),
                                                                      ), Apply((gx: list<integer>) => gx, Sort(_x)))

valid(_n, _k, _x)

Fold(Function(
               (ReplaceAt(dm_seen, _x[dm_j], 1) if dm_seen[_x[dm_j]] == 0 else ReplaceAt(
                                                                                          dm_seen,
                                                                                          _n + 1,
                                                                                          1,
                                                                                        )) if 1 <= _x[dm_j] &&
                                                                                             _x[dm_j] <= _n else ReplaceAt(dm_seen, _n + 1, 1),
               dm_seen,
               dm_j,
             ), Map(Function(0, dm_z), Range(1, _n + 1, 1)), Range(
                                                                   1,
                                                                   Length(_x),
                                                                   1,
                                                                 ))[_n + 1] == 0 &&
Length(_x) == _k

Maps

Into and out of Finset, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.

From Finset

• BinaryWordFinset → BinaryWordinverseA subset of 1..n as its characteristic word: letter i is 1 when i is a member.

To Finset

• DescentSetPermutation → FinsetThe positions where the word falls.
• FinsetBinaryWord → FinsetinverseThe subset of 1..m a binary word of length m marks: the positions holding 1.
• PeakSetPermutation → FinsetThe interior positions that rise then fall.
• PermutahedronVertexPermutation → FinsetThe vertex (σ(1), …, σ(n)), or its Loday point, is an ordered tuple of coordinates, while finset is an unordered set of positions (the carrier DescentSet and PeakSet use). Reordering the coordinates gives a different vertex but the same finset, so the map would not be injective. A finset-valued PermutahedronVertex is a type mismatch, not a gap to close.

Enumeration

Examples

Basic #

$\binom{5}{2}$

live ↗

In$\mathrm{Count}(\mathrm{KSubsets}(5, 2))$Out$10$

live ↗

In$\mathrm{KSubsets}(5, 2)[1]$Out$\operatorname{Finset}(\operatorname{Tuple}(5,\bigl\lbrack1, 2\bigr\rbrack))$

Properties #

lex order: after $\{1,2\}$ and $\{1,3\}$ comes $\{1,4\}$

live ↗

In$\mathrm{KSubsets}(5, 2)[3]$Out$\operatorname{Finset}(\operatorname{Tuple}(5,\bigl\lbrack1, 4\bigr\rbrack))$

About

Examples	3
Checked against	Combinatorica 3 agree
Crosswalk	WikipediaMathWorld ×2WikidataEncyclopedia of MathematicsBritannicaOEISWolfram LanguageCombinatoricaSageMathSymPymathlib4MATLABRosetta Code

Implementation

mappedcombinatoricapackages/oracle/src/mappings.ts

Combinatorica takes the set itself; ours is the k-subsets of 1..n.

See also: Subsets, Multisets, Binomial