RestrictedGrowthStrings

The restricted-growth strings of length $n$: words $w$ with $w_0 = 0$ and $w_i \le 1 + \max(w_0, …, w_{i-1})$.

OEISA000110↗SageMathSetPartitions(n)↗

RestrictedGrowthStrings(n)the restricted-growth strings of length $n$: words $w$ with $w_0 = 0$ and $w_i \le 1 + \max(w_0, …, w_{i-1})$

CombinatoricaMap[# - 1 &, RGFs[n], {2}]

Typed signatures

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

Domain: Collections

Details

• Count is the Bell number $B_n$ (A000110); the canonical RGS encoding of a set partition of $\{1, …, n\}$ used by SetPartitions.

Definition

Epsil, as the implementation runs it.

count(_n)

_tables[_n * (_n + 1) + 0 + 1]

unrank(_n, _r)

Apply(
       (uend: list<integer>) => Drop(uend, 2),
       Fold(
             Function(Apply((ur: integer) => Apply((uo: integer) => Apply(
                                                                           (ua: integer) => Join(
                                                                                                  [ur % ua, uo],
                                                                                                  Drop(us, 2),
                                                                                                  [(ur -
                                                                                                    ur % ua) /
                                                                                                   ua],
                                                                                                ) if ur <
                                                                                                    uo * ua else Join([ur -
                                                                                                                uo * ua, uo + 1], Drop(us, 2), [uo]),
                                                                           _tables[(_n - ui) *
                                                                                   (_n + 1) + uo + 1],
                                                                         ), us[2]), us[1]), us, ui),
             [_r, 0],
             Range(1, _n, 1),
           ),
     )

rank(_n, _x)

Fold(
      Function(Apply((rr: integer) => Apply((ro: integer) => Apply(
                                                                    (ra: integer) => [rr +
                                                                                      rv * ra, ro, rs[3] + 1] if rv < ro else [rr +
                                                                                                                        ro * ra, ro + 1, rs[3] + 1],
                                                                    _tables[(_n -
                                                                             rs[3]) *
                                                                            (_n +
                                                                             1) +
                                                                            ro +
                                                                            1],
                                                                  ), rs[2]), rs[1]), rs, rv),
      [0, 0, 1],
      _x,
    )[1]

valid(_n, _x)

Length(_x) == _n && Fold(
                          Function(ok_gi && 0 <= _x[gi] && _x[gi] <= 1 + Fold(
                                                                               Function(Max(gm, _x[gj]), gm, gj),
                                                                               -1,
                                                                               Range(1, gi - 1, 1),
                                                                             ), ok_gi, gi),
                          True,
                          Range(1, _n, 1),
                        )

tables(_n)

Fold(
      Function(Join(b_t, Fold(
                               Function(ReplaceAt(
                                                   b_row,
                                                   b_c + 1,
                                                   b_c * b_t[(b_s - 1) *
                                                             (_n + 1) + b_c + 1] +
                                                   (b_t[(b_s - 1) * (_n + 1) +
                                                        b_c + 1 + 1] if b_c < _n else 0),
                                                 ), b_row, b_c),
                               Map(Function(0, b_z), Range(0, _n + 1 - 1, 1)),
                               Range(0, _n + 1 - 1, 1),
                             )), b_t, b_s),
      Fold(
            Function(ReplaceAt(b_row, b_c + 1, 1), b_row, b_c),
            Map(Function(0, b_z), Range(0, _n + 1 - 1, 1)),
            Range(0, _n + 1 - 1, 1),
          ),
      Range(1, _n + 1 - 1, 1),
    )

Maps

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

From RestrictedGrowthString

• SetPartitionRestrictedGrowthString → SetPartitioninverseThe set partition a restricted growth string labels: block j holds the positions labelled j.

To RestrictedGrowthString

• RestrictedGrowthStringSetPartition → RestrictedGrowthStringinverseA set partition's restricted growth string: each position labelled with its block's index, from 0.

Enumeration

Examples

1 more kept as data, checked against the oracles

Basic #

$Count(RestrictedGrowthStrings(4)) = 15$

live ↗

In$\mathrm{Count}(\mathrm{RestrictedGrowthStrings}(4))$Out$15$

The first element in enumeration order

live ↗

In$\mathrm{RestrictedGrowthStrings}(4)[1]$Out${\operatorname{RestrictedGrowthString}}([0, 0, 0, 0])$

Statistics #

blocks, a set-partition statistic, reached through the order isomorphism: the Stirling numbers

live ↗

In$\mathrm{Tally}(\mathrm{CombinatorialStat}(\mathrm{RestrictedGrowthStrings}(4), \text{Blocks}))$Out$\operatorname{Tuple}(\bigl\lbrack1, 2, 3, 4\bigr\rbrack,\bigl\lbrack1, 7, 6, 1\bigr\rbrack)$

About

Examples	4
Checked against	Combinatorica 3 agree
Crosswalk	OEISCombinatoricaSageMath

Implementation

mappedcombinatoricapackages/oracle/src/mappings.ts

Combinatorica's growth strings start at 1; ours start at 0.

See also: SetPartitions