Enumerating all partitions with certain cycle characteristics

In permutations: The Symmetric Group: Permutations of a Finite Set

knitr::opts_chunk$set(echo = TRUE)
suppressMessages(library("permutations"))

![](`r system.file("help/figures/permutations.png", package = "permutations")`){width=10%}

This document discusses functions in the allcyc() family of functions.

• allcycn()
• allcyc()
• allpermslike()
• some_perms_shape()
• all_cyclic_shuffles()
• all_perms_shape()

Although all these functions are pursuant to generating all permutations of a given shape, each one is self-contained and at least potentially useful.

Function allcycn()

Function allcycn() takes a strictly positive integer argument n and returns all cycles on set $\left[n\right]=\left\lbrace 1,2,\ldots, n\right\rbrace$. This is the lowest-level function in the series.

allcycn(4)

Function allcyc()

Function allcycn() is a generalization of allcycn(). It takes a set of strictly positive integers and returns all cyclic permutations of them:

allcyc(c(1:3,7:8))

Thus allcycn(n) and allcyc(1:n) should return the same object.

Function allpermslike()

This generates all permutations "like" its argument:

allpermslike(as.cycle("(12)(3456)(789)"))

Each element of the returned vector has cycles with the same membership as its argument's cycles. All possible different permutations consistent with this are returned. In this case we see $(2-1)!(4-1)!(3-1)!=12$ distinct permutations.

Function some_perms_shape()

Given an integer vector shape, interpreted as an integer partition, function some_perms_shape() returns the permutation of size sum(shape) with shape shape, and all of whose cycles are in increasing order. Thus

some_perms_shape(c(2,2,3))

Notes

• When creating cycles, the package uses an ordering system which means that the permutation may appear as either $(\cdot\,\cdot)(\cdot\,\cdot)(\cdot\cdot\cdot)$ or $(\cdot\,\cdot)(\cdot\cdot\cdot)(\cdot\,\cdot)$ or $(\cdot\,\cdot)(\cdot\,\cdot)(\cdot\cdot\cdot)$, as per nicify_cyclist(). This can be confusing but does not change the value of the permutation [disjoint cycles commute].
• Permutation $(127)(35)(46)$ is present but $(172)(35)(46)$ is not (this is why the function is called "some_perms_shape()").

Function all_cyclic_shuffles()

Given a vector of permutations, function all_cyclic_shuffles() takes a vector of permutations u. For each element of u, it returns a vector comprising of all permutations with the same shape and cycle sets:

(x <- cyc_len(3:5))
all_cyclic_shuffles(x)

If the argument has multiple cycles the same logic operates:

all_cyclic_shuffles(as.cycle("(12)(3456)(789)"))

In this case the single permutation expands to $3!2!=12$ permutations.

Function all_cyclic_shuffles()

body(all_perms_shape)

How many permutations are there of a given shape? If the shape is

$$ \underbrace{r_1,\ldots,r_1}{m_1}, \underbrace{r_2,\ldots,r_2}{m_2},\ldots, \underbrace{r_d,\ldots,r_d}_{m_d} $$

(that is, there are $m_1$ cycles of size $r_1$, $m_2$ cycles of size $r_2$, etc; we understand that $r_1>r_2>\cdots>r_d$). Writing $\sum_{i=1}^d m_ir_i=n$ for the size of the permuted set [NB $r_d=1$ is permissible] then I get

$${n\choose \underbrace{r_1,\ldots,r_1}{m_1}, \underbrace{r_2,\ldots,r_2}{m_2},\ldots, \underbrace{r_d,\ldots,r_d}{m_d}\,\, }\prod{i=1}^d\frac{\Gamma(r_i)^{m_i}}{m_i!} = \frac{n!}{\prod_{i=1}^d m_i!\cdot r_i^{m_i}} $$

stackexchange has a good question here, the answer agrees with mine. He asks how many permutations of shape $3,2,2,1$, that is, $(\cdot\cdot\cdot)(\cdot\,\cdot)(\cdot\,\cdot)(\cdot)$ and gets 1680. I get:

$$ {8\choose 3\,2\,2\,1}\frac{2}{2!}=5678=30\cdot 56=1680 $$

We can enumerate these easily with the package:

library(permutations)
jj <- all_perms_shape(c(1,2,2,3))
length(jj)
jj[c(1:10,1671:1680)]

Further notes on all_perms_shape()

Observe that although cycles of length 1 are trivial, including 1s in the argument to all_perms_shape() nevertheless affect the output:

all_perms_shape(c(2,2))
all_perms_shape(c(2,2,1))

permutations documentation built on Sept. 11, 2024, 6:10 p.m.