Multisets
The size-k multisets drawn from (combinations with repetition).
✓ checked against that system · ! checked, with disagreements (hover a chip)Wikipedia
MultisetMathWorldMultisetWikidataQ864377nLabmultisetOEISA165257✓SageMathsage.combinat.combinat.number_of_unordered_tuples(S, k)mathlib4Sym (Fin n) kMultisets(n, k)size- multisets over symbolsTyped signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>, integer<0..>) -> indexed_collection<multiset> | combinatorics | always |
Details
- Count is , the number of combinations with repetition
- Each element is a non-decreasing length- list
Definition
Epsil, as the implementation runs it.
count(_n, _k)
Binomial(_n + _k - 1, _k)unrank(_n, _k, _r)
Apply(
(md_digits: list<integer>) => Map(
Function(md_digits[m + 1] - m + 2, m),
Range(1, _k, 1),
),
Apply((md_st_init: list<integer>) => Fold(
(md_st: list<integer>, md_i) => Apply(
(md_st_next: list<integer>) => md_st_next,
Apply((md_left: integer) => Apply(
(md_found: integer) => ReplaceAt(ReplaceAt(md_st, 1, md_left -
_tables[md_found *
(_k + 1) + md_i + 1]), md_i + 1, md_found),
Fold(
Function(md_c if _tables[md_c *
(_k + 1) + md_i + 1] <=
md_left else md_best, md_best, md_c),
md_i - 1,
Range(
md_i - 1,
(_n + _k -
1 if md_i == _k else md_st[md_i + 2]) -
1,
1,
),
),
), md_st[1]),
),
md_st_init,
Range(_k, 1, -1),
), Join(
[_r],
Map(
Function(0, md_z),
Range(1, _k, 1),
),
)),
)rank(_n, _k, _x)
Fold(
Function(acc + _tables[(_x[j] + j - 2) * (_k + 1) + j + 1], acc, j),
0,
Range(1, Length(_x), 1),
)valid(_n, _k, _x)
Length(_x) == _k && Fold(
Function(ok_j && 1 <= _x[j] && _x[j] <= _n, ok_j, j),
True,
Range(1, Length(_x), 1),
) && Fold(
Function(ok_v && _x[v - 1] <= _x[v], ok_v, v),
True,
Range(2, Length(_x), 1),
)tables(_n, _k)
Fold(
Function(
Join(
pc_t,
Fold(
Function(
ReplaceAt(
pc_row,
pc_c + 1,
1 if pc_c == 0 else pc_t[(pc_s -
1) *
(_k +
1) +
(pc_c -
1) + 1] +
pc_t[(pc_s -
1) *
(_k +
1) +
pc_c +
1],
),
pc_row,
pc_c,
),
Map(Function(0, pc_z), Range(0, _k + 1 - 1, 1)),
Range(0, _k + 1 - 1, 1),
),
),
pc_t,
pc_s,
),
Fold(
Function(
ReplaceAt(pc_row, pc_c + 1, 1 if pc_c == 0 else 0),
pc_row,
pc_c,
),
Map(Function(0, pc_z), Range(0, _k + 1 - 1, 1)),
Range(0, _k + 1 - 1, 1),
),
Range(1, Max(_n + _k - 1, 1) - 1, 1),
)