WeakCompositions

The weak compositions of $n$ into $k$ parts: ordered sequences of $k$ non-negative integers summing to $n$, unlike IntegerCompositions where every part must be positive.

✓ checked against that system · ! checked, with disagreements (hover a chip)OEISA178300✓↗

WeakCompositions(n, k)the $\binom{n+k-1}{k-1}$ sequences of $k$ non-negative parts summing to $n$

CombinatoricaCompositions[n, k]

Typed signatures

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

Domain: Collections

Definition

Epsil, as the implementation runs it.

count(_n, _k)

(1 if _k == 0 else 0) if _n + _k == 0 else Binomial(_n + _k - 1, _k - 1)

unrank(_n, _k, _r)

Apply(
       (cd_digits: list<integer>) => Map(Function((0 if pos == 0 else _n + _k if pos == _k else cd_digits[pos + 1] +
                                                                                                1) -
                                                  (0 if pos - 1 == 0 else _n +
                                                                          _k if pos -
                                                                              1 ==
                                                                              _k else cd_digits[pos - 1 +
                                                                                              1] +
                                                                                    1) - 1, pos), Range(1, _k, 1)),
       Apply((cd_st_init: list<integer>) => Fold(
                                                  (cd_st: list<integer>, cd_i) => Apply(
                                                                                         (cd_st_next: list<integer>) => cd_st_next,
                                                                                         Apply((cd_left: integer) => Apply(
                                                                                                                            (cd_found: integer) => ReplaceAt(ReplaceAt(cd_st, 1, cd_left -
                                                                                                                                                                                 _tables[cd_found *
                                                                                                                                                                                         (Max(_k - 1, 0) +
                                                                                                                                                                                          1) + cd_i + 1]), cd_i + 1, cd_found),
                                                                                                                            Fold(
                                                                                                                                  Function(cd_c if _tables[cd_c *
                                                                                                                                                           (Max(_k - 1, 0) +
                                                                                                                                                            1) + cd_i + 1] <=
                                                                                                                                                   cd_left else cd_best, cd_best, cd_c),
                                                                                                                                  cd_i - 1,
                                                                                                                                  Range(
                                                                                                                                         cd_i - 1,
                                                                                                                                         (_n + _k -
                                                                                                                                          1 if cd_i ==
                                                                                                                                              _k - 1 else cd_st[cd_i + 2]) -
                                                                                                                                         1,
                                                                                                                                         1,
                                                                                                                                       ),
                                                                                                                                ),
                                                                                                                          ), cd_st[1]),
                                                                                       ),
                                                  cd_st_init,
                                                  Range(_k - 1, 1, -1),
                                                ), Join(
                                                        [_r],
                                                        Map(
                                                             Function(0, cd_z),
                                                             Range(1, _k - 1, 1),
                                                           ),
                                                      )),
     )

rank(_n, _k, _x)

Fold(Function(
               acc3 + _tables[(Fold(
                                     Function(acc2 + (_x[t] - -1), acc2, t),
                                     0,
                                     Range(1, i, 1),
                                   ) - 1) * (Max(_k - 1, 0) + 1) + i + 1],
               acc3,
               i,
             ), 0, Range(1, _k - 1, 1))

valid(_n, _k, _x)

Length(_x) == _k && Fold(
                          Function(acc2 + (_x[t] - -1), acc2, t),
                          0,
                          Range(1, Length(_x), 1),
                        ) == _n + _k && Fold(
                                             Function(
                                                       okv && _x[jv] >= 0,
                                                       okv,
                                                       jv,
                                                     ),
                                             True,
                                             Range(1, 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) *
                                                                      (Max(_k -
                                                                           1, 0) +
                                                                       1) + (pc_c -
                                                                          1) + 1] +
                                                                 pc_t[(pc_s - 1) *
                                                                      (Max(_k -
                                                                           1, 0) +
                                                                       1) + pc_c +
                                                                      1],
                                           ), pc_row, pc_c), Map(
                                                                 Function(
                                                                           0,
                                                                           pc_z,
                                                                         ),
                                                                 Range(
                                                                        0,
                                                                        Max(_k -
                                                                            1, 0) +
                                                                        1 - 1,
                                                                        1,
                                                                      ),
                                                               ), Range(
                                                                        0,
                                                                        Max(_k -
                                                                            1, 0) +
                                                                        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, Max(_k - 1, 0) + 1 - 1, 1),
                                          ),
                                       Range(0, Max(_k - 1, 0) + 1 - 1, 1),
                                     ), Range(1, Max(_n + _k, 1) - 1, 1))

Examples

Basic #

$\binom{6}{2} = 15$

live ↗

In$\mathrm{Count}(\mathrm{WeakCompositions}(4, 3))$Out$15$

Parts may be zero

live ↗

In$\mathrm{Take}(\mathrm{WeakCompositions}(2, 2), 3)$Out$\bigl\lbrack\bigl\lbrack0, 2\bigr\rbrack, \bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack2, 0\bigr\rbrack\bigr\rbrack$

About

Examples	2
Checked against	Combinatorica 2 agree
Crosswalk	OEISCombinatorica

Implementation

mappedcombinatoricapackages/oracle/src/mappings.ts

Combinatorica's Compositions[n, k] allows zero parts: ours is WeakCompositions, not the strict IntegerCompositions.

See also: IntegerCompositions