Counting cycles after permuting within rows and columns

Consider a rectangular p×q array, labelled by the numbers 0,…,pq−1 for convenience. Let Sp and Sq and Spq denote the symmetric groups. Take a family of permutations: ρ1,…,ρq∈Sp, κ1,…,κp∈Sq. Then letting ρt act on the tth row, one obtains a permutation ρ∈Spq which leaves the rows of the array stable (but permutes within each row). … Read more

Find the set of numbers for which some sum over permutations is independent of the initial value

Question I have a sequence of natural numbers 0=k0<k1<k2<⋯<kn and we want to find the set of numbers which satisfy some property, so we want to find (in function of n): An:={(k1,…,kn)∈Nn∣(k0,…,kn) satisfy property A} The property A we are looking at is the following: let σ be an arbitrary permutation on {k0,…,kn} and k∈{k0,…,kn} be arbitrary, … Read more

Have wiring diagrams been generalized to arbitrary digraphs?

A “combinatorial wiring diagram” is a way to define a permutation by a drawing of a particular planar digraph. For example, this wiring diagram corresponds to the permutation $(3412)$: In Coxeter combinatorics it is common to study the properties of reduced wiring diagrams, where no two wires cross twice (one could “reduce” such a diagram … Read more

Counting “deflected” permutations: Part II

This is the second sequel to my earlier question on MO. Although the the current problem appears very similar, the answer is certainly different as experiments indicate. As usual, let Sn be the set of permutations on {1,2,…,n} and introduce the sets B(k)n:={π∈Sn+k:−k≤π(j)−j≤n,∀j}. I would like to ask: Question. What is the cardinality #B(k)n of … Read more

Is there a permutation $\pi\in S_n$ with $\sum\limits_{07$?

Let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$. QUESTION: Is it true that for each $n=8,9,\ldots$ we have $$\sum_{0<k<n}\frac1{\pi(k)^2-\pi(k+1)^2}=0\tag{$*$}$$ for some $\pi\in S_n$? Let $s(n)$ denote the number of permutations $\pi\in S_n$ with $\pi(1)<\pi(n)$ satisfying $(*)$. Via Mathematica, I find that $$s(1)=s(2)=\ldots=s(7)=0,\ s(8)=1,\ s(9)=s(10)=4,\ s(11)=55.$$ When $n=8$ we can only take $$(\pi(1),\ldots,\pi(8))=(4,5,2,7,3,1,6,8)$$ … Read more

Distance properties of the permutations of a set of points in a Euclidean space

We are given a set of $n$ distinct points $S=\{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\}$ in a Euclidean space $\mathbb{R}^d$, where the distance between two points $\mathbf{x}_i,\mathbf{x}_j\in S$ is denoted by $d(i,j)$ for any $i,j\in[n]$, and $\max_{i,j\in [n]}d(i,j)=1$. Let $\mathcal{\Pi}$ be the set of all functions $\pi$ mapping each index of a point of $S$ to a … Read more

Words that give rise to an enumeration of elements of the symmetric group

Let $\mathbb{S}_m$ be the symmetric group on $m$ letters. Let $n=m-1$. Let $\mathbf{w}=a_1\cdots a_r$ be a word on the alphabet $\{1,\ldots,n\}$. We say that $\mathbf{w}$ gives rise to an enumeration of elements of the symmetric group $\mathbb{S}_m$ if $1,s_{a_r},s_{a_{r-1}}s_{a_r},\ldots,s_{a_2}\cdots s_{a_r},s_{a_1}\cdots s_{a_r}$ are all distinct elements of the symmetric group $\mathbb{S}_m$. For example, $32323132323132323$ gives rise … Read more

Identities involving derangements and roots of unity

For a positive integer $n$, a derangement of $\{1,\ldots,n\}$ is a permutation $\tau$ of $\{1,\ldots,n\}$ with $\tau(j)\not=j$ for all $j=1,\ldots,n$. For convenience, we let $D(n)$ denote the set of all derangements of $\{1,\ldots,n\}$. I have the following conjecture on identities involving both derangements and roots of unity. Conjecture. Let $n>1$ be an integer and let … Read more

Is there a geometric meaning of the Major index?

The actual question I want to ask is whether there is a geometric proof of this famous identity ∑σ∈Snqinvσ=∑σ∈Snqmajσ, along the lines of interpreting both sides as the Poincare polynomial of some nice variety computed in two different ways. Here inv and maj stand for number of inversions and Major index, respectively. One possible candidate … Read more

Generating bitstring combinations using a butterfly network

I’m using a butterfly network to generate a random combination of a bitstring of length n and weight w. Let me clarify it with an example. Suppose I want a random bitstring of length 8 and Hamming weight 2. The idea is: set the first 2 bits to 1, leaving all others to 0 apply … Read more