notatio

SetPartitionsIntoKBlocks ​

A name from the enumeratio catalogue with no kernel of its own yet; this page carries its crosswalk only.

Catalogued in the enumeratio database, with crosswalk rows in mathlib4, oeis, sage, wolfram; not yet written up here.

✓ checked against that system · ! checked, with disagreements (hover a chip)OEISA008277A048993✓Wolfram LanguageStirlingS2SageMathSetPartitions(n, k)sage.combinat.combinat.stirling_number2(n, k)mathlib4Nat.stirlingSecond
SetPartitionsIntoKBlocks(...)Catalogued in the enumeratio database, with crosswalk rows in mathlib4, oeis, sage, wolfram; not yet written up here.
Typed signatures
TypePackageApplies
(integer<0..>, integer<0..>) -> indexed_collection<set_partition>combinatoricsalways

Domain: Combinatorics

Definition

Epsil, as the implementation runs it.

count(_n, _k)

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

unrank(_n, _k, _r)

Apply(
       (uend: list<integer>) => Map(Function(Filter(
                                                     Range(1, _n, 1),
                                                     Function(Drop(uend, 2)[p] ==
                                                              j, p),
                                                   ), j), Range(
                                                                0,
                                                                uend[2] - 1,
                                                                1,
                                                              )),
       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) *
                                                                                   (_k + 1) + uo + 1],
                                                                         ), us[2]), us[1]), us, ui),
             [_r, 0],
             Range(1, _n, 1),
           ),
     )

rank(_n, _k, _x)

Apply(
       (rgs0: list<integer>) => 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]) *
                                                                                                            (_k + 1) + ro + 1],
                                                                                                  ), rs[2]), rs[1]), rs, rv),
                                      [0, 0, 1],
                                      rgs0,
                                    )[1],
       Apply((mins: list<integer>) => Map(
                                           Function(Fold(Function(
                                                                   Count(Filter(
                                                                                 mins,
                                                                                 Function(z < mins[j], z),
                                                                               )) if Contains(_x[j], x) else lbl,
                                                                   lbl,
                                                                   j,
                                                                 ), 0, Range(
                                                                             1,
                                                                             Length(_x),
                                                                             1,
                                                                           )), x),
                                           Range(1, _n, 1),
                                         ), Map(Function(Min(blk), blk), _x)),
     )

valid(_n, _k, _x)

Length(_x) == _k && Apply((flat: list<integer>) => Length(flat) == _n &&
                                                   Fold(Function(
                                                                  ok_blk && Length(blk) >=
                                                                            1,
                                                                  ok_blk,
                                                                  blk,
                                                                ), True, _x) &&
                                                   Fold(
                                                         Function(ok_x &&
                                                                  Contains(
                                                                            flat,
                                                                            x,
                                                                          ), ok_x, x),
                                                         True,
                                                         Range(1, _n, 1),
                                                       ), Flatten(_x))

tables(_n, _k)

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

Statistics

On SetPartition, called as CombinatorialStat(x, "Name").

Maps

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

From SetPartition

  • ArcRepresentationSetPartition → EndofunctionEach position linked to the next in its block, or to itself when last.
  • AssociatedStandardTableauSetPartition → StandardTableauSurjectionMp00258The standard tableau whose j-th column holds the j-th smallest elements of the blocks, in increasing order.
  • BlockSizeCompositionSetPartition → IntegerCompositionsurjectionSurjectionGraded mapMp00128The block sizes of a set partition, its blocks taken in order of their least elements.
  • BlockSizePartitionSetPartition → IntegerPartitionsurjectionSurjectionGraded mapMp00079The partition of n a set partition's block sizes form, largest first.
  • CallanSwitchSetPartition → SetPartitionBijectionGraded mapInvolutionMp00249Callan's involution: switches the first closer with the lesser of the least closer and the second element of the block of 1.
  • ComplementSetPartition → SetPartitioninvolutionBijectionGraded mapInvolutionMp00112Each element i replaced by n + 1 - i: the set partition seen from the other end.
  • DecreasingRotationSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00176Every element lowered by one, cyclically: 1 becomes the largest.
  • DualMajorIndexToIntertwiningSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00174The inverse of IntertwiningToDualMajorIndex: read the growth word as an intertwining word and rebuild the blocks.
  • IncreasingCyclePermutationSetPartition → PermutationInjectionGraded mapMp00080The permutation whose cycles are the blocks, each cycle increasing: every element goes to the next larger in its block, the largest to the least.
  • IncreasingRotationSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00091Every element raised by one, cyclically: the largest becomes 1.
  • IntertwiningToDualMajorIndexSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00171The set partition whose growth word is the intertwining word: a bijection taking the intertwining number to the dual major index.
  • InverseWachsWhiteSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00216The set partition joined by the arcs of the rook placement that Wachs and White's bijection gamma assigns to the set partition.
  • InverseWachsWhiteRhoSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00218The set partition joined by the arcs of the rook placement that Wachs and White's bijection rho assigns to the set partition.
  • InverseYipSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00219The set partition joined by the arcs of the rook placement that Yip's bijection psi assigns to the set partition.
  • KasraouiZengSetPartition → SetPartitionBijectionGraded mapInvolutionMp00115The Kasraoui-Zeng involution: exchanges the number of crossings with the number of nestings.
  • RestrictedGrowthStringSetPartition → RestrictedGrowthStringinverseA set partition's restricted growth string: each position labelled with its block's index, from 0.
  • WachsWhiteSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00215The set partition whose arcs, read as a rook placement, Wachs and White's bijection gamma carries to a set partition.
  • WachsWhiteRhoSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00217The set partition whose arcs, read as a rook placement, Wachs and White's bijection rho carries to a set partition.
  • YipSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00220The set partition whose arcs, read as a rook placement, Yip's bijection psi carries to a set partition.

To SetPartition

  • CyclePartitionPermutation → SetPartitionsurjectionSurjectionGraded mapMp00151The orbits, as a set partition of the positions.
  • NoncrossingPartitionDyckPath → SetPartitionInjectionGraded mapMp00138Biane's noncrossing set partition: the up steps whose matching downs lie in one run of downs form a block.
  • RowSetPartitionStandardTableau → SetPartitionInjectionGraded mapMp00284The set partition whose blocks are the rows of the tableau.
  • SetPartitionRestrictedGrowthString → SetPartitioninverseThe set partition a restricted growth string labels: block j holds the positions labelled j.
  • UnderlyingSetPartitionSetComposition → SetPartitionsurjectionSurjectionGraded mapMp00285The set partition with the same blocks, the order of the blocks forgotten.
  • WeakExceedancePartitionPermutation → SetPartitionSurjectionGraded mapMp00240The coarsest set partition containing every arc from i to π(i) with i ≤ π(i).
3 more in FindStat, not implemented here
  • Mp00092PerfectMatching → SetPartitionInjectionGraded mapto set partition
  • Mp00164SetPartition → SetPartitionBijectionGraded mapInvolutionChen Deng Du Stanley Yan
  • Mp00221SetPartition → SetPartitionBijectionGraded mapInvolutionconjugate

Enumeration

Examples

Basic #

The Stirling number of the second kind S(4,2)=7S(4, 2) = 7

live ↗
InCount(SetPartitionsIntoKBlocks(4,2))\mathrm{Count}(\mathrm{SetPartitionsIntoKBlocks}(4, 2))Out77

The set partitions of {1,2,3,4}\{1,2,3,4\} into two blocks

live ↗
InTake(SetPartitionsIntoKBlocks(4,2),7)\mathrm{Take}(\mathrm{SetPartitionsIntoKBlocks}(4, 2), 7)Out[SetPartition⁡([[1,2,3],[4]]),SetPartition⁡([[1,2,4],[3]]),SetPartition⁡([[1,2],[3,4]]),SetPartition⁡([[1,3,4],[2]]),SetPartition⁡([[1,3],[2,4]]),SetPartition⁡([[1,4],[2,3]]),SetPartition⁡([[1],[2,3,4]])]\bigl\lbrack{\operatorname{SetPartition}}([[1, 2, 3], [4]]), {\operatorname{SetPartition}}([[1, 2, 4], [3]]), {\operatorname{SetPartition}}([[1, 2], [3, 4]]), {\operatorname{SetPartition}}([[1, 3, 4], [2]]), {\operatorname{SetPartition}}([[1, 3], [2, 4]]), {\operatorname{SetPartition}}([[1, 4], [2, 3]]), {\operatorname{SetPartition}}([[1], [2, 3, 4]])\bigr\rbrack
About
Examples2
CrosswalkOEIS ×2Wolfram LanguageSageMath ×2mathlib4