StirlingPermutations

Permutations of the multiset $\{1,1,2,2,…,n,n\}$ where everything between the two copies of $i$ exceeds $i$, a lazy indexed family of $(2n-1)!!$.

StirlingPermutations(n)the $(2n-1)!!$ permutations of $\{1,1,…,n,n\}$ with that betweenness property.

Typed signatures

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

Domain: Collections

Details

• A lazy indexed collection; the count is the double factorial $(2n-1)!!$. See Factorial2.
• Built by inserting the pair $(k,k)$, for $k=2,…,n$ increasing, into any of the $2(k-1)+1$ gaps of a Stirling permutation of order $k-1$ — every gap is valid because a later pair always carries a larger label.
• Each element is the length-$2n$ word itself; $At$ unranks the per-$k$ gap choices as mixed-radix digits (radix $2k-1$ at level $k$), combined by the standard Horner scheme.

Definition

Epsil, as the implementation runs it.

count(_n)

Fold(Function(sp * (2sj - 1), sp, sj), 1, Range(2, _n, 1))

unrank(_n, _r)

[] if _n == 0 else Fold(Function(Join(
                                       Take(
                                             uw,
                                             (_r - _r % Fold(
                                                              Function(
                                                                        sp * (2sj -
                                                                              1),
                                                                        sp,
                                                                        sj,
                                                                      ),
                                                              1,
                                                              Range(
                                                                     uk + 1,
                                                                     _n,
                                                                     1,
                                                                   ),
                                                            )) / Fold(
                                                                      Function(sp *
                                                                               (2sj - 1), sp, sj),
                                                                      1,
                                                                      Range(
                                                                             uk +
                                                                             1,
                                                                             _n,
                                                                             1,
                                                                           ),
                                                                    ) % (2uk - 1),
                                           ),
                                       [uk, uk],
                                       Drop(
                                             uw,
                                             (_r - _r % Fold(
                                                              Function(
                                                                        sp * (2sj -
                                                                              1),
                                                                        sp,
                                                                        sj,
                                                                      ),
                                                              1,
                                                              Range(
                                                                     uk + 1,
                                                                     _n,
                                                                     1,
                                                                   ),
                                                            )) / Fold(
                                                                      Function(sp *
                                                                               (2sj - 1), sp, sj),
                                                                      1,
                                                                      Range(
                                                                             uk +
                                                                             1,
                                                                             _n,
                                                                             1,
                                                                           ),
                                                                    ) % (2uk - 1),
                                           ),
                                     ), uw, uk), [1, 1], Range(2, _n, 1))

rank(_n, _x)

Fold(Function(ra * (2rk - 1) +
              Fold(
                    Function(
                              [1, rs[2]] if _x[rj] == rk else rs if rs[1] == 1 else [0, rs[2] +
                                                                                        (1 if _x[rj] < rk else 0)],
                              rs,
                              rj,
                            ),
                    [0, 0],
                    Range(1, Length(_x), 1),
                  )[2], ra, rk), 0, Range(2, _n, 1))

valid(_n, _x)

Fold(Function(
               (ReplaceAt(
                           ReplaceAt(ReplaceAt(vs, 2 + _x[vj], 1), 2, vs[2] + 1),
                           2 + _n + vs[2] + 1,
                           _x[vj],
                         ) if (0 if vs[2] == 0 else vs[2 + _n + vs[2]]) < _x[vj] else ReplaceAt(vs, 1, 1)) if vs[2 + _x[vj]] ==
                                                                                                             0 else ReplaceAt(ReplaceAt(vs, 2 + _x[vj], 2), 2, vs[2] - 1) if vs[2 + _x[vj]] ==
                                                                                                                                                                            1 &&
                                                                                                                                                                            (0 if vs[2] == 0 else vs[2 + _n + vs[2]]) ==
                                                                                                                                                                            _x[vj] else ReplaceAt(vs, 1, 1),
               vs,
               vj,
             ), Map(Function(0, vz), Range(1, 2 + 2 * _n, 1)), Range(
                                                                     1,
                                                                     Length(_x),
                                                                     1,
                                                                   ))[1] == 0 if Length(_x) ==
                                                                                2 * _n &&
                                                                                Fold(
                                                                                      Function(ok_j &&
                                                                                               1 <= _x[j] &&
                                                                                               _x[j] <= _n, ok_j, j),
                                                                                      True,
                                                                                      Range(1, Length(_x), 1),
                                                                                    ) else False

Enumeration

Examples

1 more kept as data, checked against the oracles

Basic #

$Count(StirlingPermutations(4)) = 105 = 7!!$, A001147

live ↗

In$\mathrm{Count}(\mathrm{StirlingPermutations}(4))$Out$105$

Properties #

$Count(StirlingPermutations(n)) = (2n-1)!!$. See Factorial2

live ↗

In$\mathrm{Count}(\mathrm{StirlingPermutations}(4))=7!!$Out$\mathrm{True}$

About

Examples	3

See also: Factorial2, Count, At