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})$ .

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.

Maps

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

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

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

1 more kept as data, checked against the oracles

Basic #

$Count(RestrictedGrowthStrings(4)) = 15$

\mathrm{Count}(\mathrm{RestrictedGrowthStrings}(4))

Out

15

The first element in enumeration order

\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

\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

mappedcombinatoricapackages/oracle/src/mappings.ts

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