Questions related to permutations, bijections from a finite (or sometimes infinite) set to itself.

**0**

votes

**0**answers

5 views

### Is there a size 2 generating set of the signed symmetric group $B_n$?

The signed symmetric group $B_n$ is a permutation group where the underlying set is $B_n=\{\sigma \in S_{A_n}| \forall x \in A_n, \sigma(-x)= -\sigma(x)\}$ with $A_n=\{-n,-(n-1),-(n-2),\cdots,-1,1,\...

**7**

votes

**3**answers

242 views

### Distribution of sum of two permutation matrices

Determinant and permanent of sum of two $n\times n$ permutation matrices can be arbitrarily different.
What is the distribution of determinant of sum and difference of two $n\times n$ permutation ...

**1**

vote

**1**answer

94 views

### The number of permutations with a special condition

Suppose we are considering $S_n$. For any permutation, let $h$ be the number of derangement and $N$ be the number of cycles with length no less than 2.
I'm interested in the number of permutations ...

**2**

votes

**0**answers

53 views

### Basis for Annular Skein Algebra

Background/Notation:
Given the Iwahori-Hecke algebra $H_{n}$ (over some ring commutative ring $R$ with identity) with generators $\{T_{1},\ldots T_{n-1}\}$, we know it has basis
$\{T_{w}\}_{w\in S_{...

**1**

vote

**1**answer

165 views

### A permutation with reflection property

Consider permutations $\pi$ of the set $\{1,\dots,n\}$ having the symmetry property $\pi \pi^* \pi = \pi^*$, where $\pi^*$ is the "reflection" $k \mapsto n+1-k$. Are there references or other ...

**0**

votes

**3**answers

174 views

### The number of permutations with specified number of cycles and fixed points

I'm interested in the number of permutations for a specified number of fixed points and cycles.
Suppose we are in $S_n$. For any permutation in $S_n$, let $h$ be the number of changed points (the ...

**0**

votes

**0**answers

41 views

### k-ary bracelets with conserved/fixed indexes

Im using the formula from here:
https://en.wikipedia.org/wiki/Necklace_(combinatorics)#Number_of_bracelets
to calculate the number of unique bracelets, accepting all rotation/mirroring as equivalent,...

**2**

votes

**0**answers

40 views

### Probability Distribution on permutations with factor structure

Say I define a probability measure over the symmetric group $S_n$ as follows:
I specify $n$ positive `potential' functions $G_i : \{1, 2, \cdots, N\} \to (0,\infty)$
I then set
$$\mathbb{P}(\sigma) =...

**12**

votes

**2**answers

299 views

### Cycle generating function of permutations with only odd cycles

Let $\mathrm{ODD}(n)$ be the set of permutations in $\mathfrak{S}_n$ whose cycle lengths are all odd. It is known that
$$ \#\mathrm{ODD}(n) = \begin{cases} ((n-1)!!)^2 &\textrm{ if $n$ is even}; \\...

**3**

votes

**0**answers

102 views

### Dirichlet eta function and Stirling Permutations

The Stirling permutations of order $k$ is a permutation of the multiset $1, 1, 2, 2, ..., k, k$. The Dirichlet $\eta$-function is a function closely related to the Riemann $\zeta$-function.
According ...

**12**

votes

**3**answers

481 views

### Determining if some permutation of a vector satisfies a system of linear equations

Let $A$ be a matrix and $x$ a fixed vector. How can we determine whether or not there exists a permutation matrix $P$ such that $APx=0$? Does this problem reduce to anything well-understood?

**1**

vote

**0**answers

107 views

### A partial ordering on $S_n$

Where $P$ and $Q$ are permutations in $S_n$, let's say $P<Q$ if $P$ is obtained from $Q$ by swapping two numbers which $Q$ places in the correct order. For example, if
$$Q=(1, 3, 6, 5, 4, 2)$$
$$P=...

**6**

votes

**1**answer

185 views

### Can a primitive root-permutation of $A=\{1, 2, \ldots, p-1 \}$ be a cycle of length $p-1$ only for finitely many $p$?

Let $p$ be an odd prime, $g$ a primitive root of $p$ and $A=\{1, 2, \ldots, p-1 \}$.
Obviously, $\sigma_g(p)=\begin{pmatrix}
1 & 2 & \ldots & {p-1} \\
g^1\pmod{p} & g^2\pmod{p} &...

**1**

vote

**0**answers

67 views

### Loopless algorithm for generating permutations (Steinhaus-Johnson-Trotter)

The following is a description of the well-known Steinhaus-Johnson-Trotter algorithm to generate all permutations of an $n$-element ground set using adjacent transpositions.
In fact, it is a loopless ...

**0**

votes

**0**answers

75 views

### Bracelets with beads from different color sets

I would like to count the number of bracelets with $N$ (numbered) beads, where, say, beads with index (i.e. at position) $i \in \{1,...,n\}$ can have a 'color' $c(i) \in \{1,...,k\}$ and beads with ...

**0**

votes

**1**answer

164 views

### root of identity matrix and lexicographic order

I asked a question here order of a permutation and lexicographic order but it seems*** that a very powerful and rich generalization can be made!
Let $A$ be a finite ring together with an arbitrary ...

**1**

vote

**1**answer

118 views

### order of a permutation and lexicographic order

Let $M$ be an $n\times m$ matrix, say with entries in $\left\{0,1\right\}$ ; and let $\mathcal C(M)$ be the $n\times m$ matrix such that there exists $P$, $m\times m$ permutation matrix such that $...

**3**

votes

**1**answer

138 views

### Cycle Structure of a Permutation Based on the Binary Representation

This is a question I posted on math.stackexchange.com before but never got an answer. I am cross-posting it here.
Define a permutation $\sigma$ on the set $X=\{1,2,...,n\}$, $n$ is a natural number ...

**6**

votes

**1**answer

238 views

### A permutation problem

Here I ask a question on permutations of $n$ distinct real numbers.
QUESTION: Let $a_1,a_2,\ldots,a_n\ (n>1)$ be (pairwise) distinct real numbers. Is there a permutation $b_1,\ldots,b_n$ of $a_1,\...

**6**

votes

**0**answers

79 views

### Decomposition of even symmetric polynomials and Euler numbers

Let's denote the even part of a polynomial $p$ by $E[p]$, which means only taking into account the monomials in $p$ which are even in all the arguments. Now let's consider the even part of the ...

**3**

votes

**0**answers

94 views

### Permutation statistics in multiple rows

Usually we study the statistics of a permutation written in one row. Is there any result for the statistics of a permutation written in multiple rows? Let me give an example in order to be more clear: ...

**7**

votes

**1**answer

364 views

### Linear permutations commuting with $x\rightarrow x^{-1}$

Let $F = \operatorname{GF}(2^n)$ be a finite field. Define a permutation $\phi:F \rightarrow F$ by the formula
$$
\phi(x) = x^{-1}, \ x\neq 0; \ \phi(0) =0.
$$
We say that a permutations $\psi$ of $F$ ...

**2**

votes

**0**answers

69 views

### Combinatorial model for twisted involutions in $S_n$

Let $(W,S)$ be a Coxeter group and $*:S \to S$ be an automorphism of the Dynkin diagram of $W$ so that $*^2$ is the identity.
This induces a bijection $*:W \to W$ mapping $w = s_1 \dots s_n$ to $w^* = ...

**6**

votes

**0**answers

156 views

### How many permutations do you need to force fixed points?

For simplicity let $k$ be given fixed, and $n$ grows large. We are interested in a small set $M_n={g_1,...,g_m}$ of permutations in $S_n$, s.t for all $a\in S_n$, there is $g_i \in M_n$ with $ag_i$ ...

**0**

votes

**0**answers

29 views

### What is an example of a constructive encoding of binary strings modulo an arbitrary permutation group $G$?

Given a group $G \leq S_n$ we can construct by the axiom of choice a function $f : \{0, 1\}^n \rightarrow \{0, 1\}^{ceil(log_2 |\{0, 1\}^n/G|)}$ such that for any orbit $O$ of binary strings under $G$,...

**3**

votes

**2**answers

178 views

### Length of composition series in a primitive group

Let $G$ be a primitive group acting on a set $\Omega$ with $n$ elements. By Cameron/Liebeck (essentially a consequence of the Classification + O'Nan-Scott), there are two possibilities:
(a) $G$ has a ...

**4**

votes

**1**answer

283 views

### Sets $A$ stable under $(x,f(x))\mapsto x+f(x)$

Let $A$ be a finite set of real numbers or integers. We know how to characterize, broadly speaking, sets $A$ such that $A+A$ is not much larger than $A$ (Freiman's theorem). I have a question that ...

**4**

votes

**2**answers

128 views

### Factorizations in terms of characters

I have asked this in math.SE (https://math.stackexchange.com/questions/2698772/factorizations-in-terms-of-characters) but it was barely viewed.
I have seen mention in different places that the number ...

**0**

votes

**1**answer

59 views

### Sequence Generation with Combinations and Permutations

I am trying to generate a set of genetic sequences with conditions. The problem uses a base 4 numerical notation:
nucleotides = ['A','C','G','T']
From this, I'd ...

**2**

votes

**0**answers

72 views

### First appearance of “structure tree”?

Let $G$ be a transitive permutation group acting on a set $\Omega$. A structure tree $T$ for $(G,\Omega)$ is defined as follows: if $G$ is primitive, then it consists of a root node connected by edges ...

**2**

votes

**0**answers

68 views

### Permutation factorizations according to number of generated orbits

Let $\pi$ be a permutation in $S_n$ with cycle type $\lambda$.
How many factorizations into two factors $\pi=\sigma_1\sigma_2$ are there, such that the subgroup $\langle \sigma_1,\sigma_2\rangle$ ...

**5**

votes

**0**answers

85 views

### 'Permutation Coupling' for Markov Chains

Suppose I have a Markov chain (discrete time, finite state space) on $[N] = \{1, 2, \cdots, N\}$, with Markov kernel given by a doubly stochastic matrix $P$. The double-stochasticity guarantees that ...

**30**

votes

**1**answer

1k views

### Mysterious symmetry - in search for a bijection

I have a mysterious symmetry that I have not managed to prove.
First some definitions (see picture below)
Fix a partition that fit in a staircase shape with $n$ rows.
There are $Catalan(n)$ such ...

**5**

votes

**2**answers

221 views

### Counting transitive generators according to coset type

Let $\sigma=(1\;2)(3\;4)\cdots (n-1\; n)$ be a fixed-point-free involution in $S_{2n}$. I want to count permutations $\pi$ such that the group $\langle \pi,\sigma\rangle$ generated by $\pi$ and $\...

**2**

votes

**1**answer

59 views

### Proving symmetry of trace function of special matrix

Let $W = aI_{n\times n} + bJ_{n\times n}$, where $I$ is an identity matix, $J$ is the matrix of all ones, $a,b\in\mathbb{R}$ and a+b>0. Also, let $A = \mathbf{P} - \mathbf{p}\mathbf{p}^{T}$, where $\...

**5**

votes

**1**answer

251 views

### Is there an efficient algorithm to check whether two matrices are the same up to row and column permutations?

Define $\mathcal M_n$ as the set of all $n\times n$ matrices with each entry either 1 or $x$. Two such matrices are equivalent iff they can be obtained from each other by swapping pairs of rows and ...

**0**

votes

**1**answer

93 views

### Permutations which avoid consecutive entries of the form (m,m+1)

I found an interesting question on quora and need help in solving this question. I've just started understanding permutations but could not understand as to how I can come up with a general formula ...

**3**

votes

**0**answers

118 views

### Orthogonal basis for decomposition of induced representation of derangements

Background
Let $V_n$ be the $\mathbb{C}$-module spanned by the set of derangements (permutations with no fixed points) inside the group ring of $S_n$. We make $V_n$ into a $\mathbb{C}S_n$-module ...

**6**

votes

**0**answers

102 views

### equidistribution of the number of occurrences of a vincular pattern, and a simpler vincular pattern

This is (at least for now) a question out of curiosity, there is no "deeper" meaning to it I know of. In fact, my main question is: is the observation below obvious?
To state the observation I have ...

**8**

votes

**0**answers

212 views

### Generating $S_n$ with a fundamental transposition and a big cycle

I apologize in advance if this is too amateur, this is not really my area, but I'm very curious.
We have a permutation $\pi \in S_n$ and we want to represent it as a product of $\sigma = (1\;2)$ and $...

**0**

votes

**1**answer

72 views

### Jordan decomposition of powers of the Shift Matrix [closed]

Given the upper Shift Matrix, which for e.g. dimension $5$ is
$$
{\bf E}_{\,{\bf 5}} = \left( {\matrix{
0 & 1 & 0 & 0 & 0 \cr
0 & 0 & 1 & 0 & 0 \cr
0 &...

**4**

votes

**1**answer

108 views

### Partitions of finite sets and their behavior under permutations of the set

The following seems to be useful, and probably well-known, but I can't find a reference for it. If anyone can point me to a textbook or paper which states it, then I'd be grateful.
Consider a ...

**3**

votes

**1**answer

204 views

### What does this permutation polynomial look like?

What is the number of terms of the unique multilinear polynomial $f\in\Bbb F_2[x_{1,1},\dots,x_{n,n}]$ in $n^2$ variables such that $f$ vanishes only on matrices that are permutations?
Are there good ...

**0**

votes

**0**answers

57 views

### Permutations with restricted pairwise intersections

Preparing problem sets for an exam I encountered the next question:
Assume we have $n$ topics and $k_1$ different problems on the first topic, $k_2$
on the second, etc. We need to generate problem ...

**1**

vote

**0**answers

79 views

### Best Grouping Method

Let $\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_{2n}$ be real vectors with the following properties
$$\sum_{i=1}^{2n}\mathbf{x}_i=0$$ and $$\|\mathbf{x}_i\|_1=1$$
I want to find a grouping strategy ...

**8**

votes

**0**answers

183 views

### intriguing Polytope

Define $E_{i,j} \in \mathbb{R}^{n \times n}$ to be the canonical basis (that is all elements set to zero except the entry $i,j$ )
let the bloc matrix $M \in \mathbb{R}^{n^2 \times n^2}$ defined by :
...

**12**

votes

**1**answer

330 views

### When is the union of a graph and a random permutation thereof connected?

First things first: in what follows, a "random permutation" of a set $\Omega$ with $n$ elements does not necessarily mean an element chosen uniformly at random from $\textrm{Sym}(\Omega)$. Rather, and ...

**2**

votes

**0**answers

104 views

### How many symmetric strings a permutation fixes

Let $A$ be an alphabet of $N$ symbols. Let $S_n$ be the group of permutations of $n$ symbols. A permutation acts on a string of letters from $A$ in the obvious way.
If I ask, given a permutation $\pi\...

**11**

votes

**0**answers

194 views

### Question on a reduction in Kirillov's paper on positivity of divided difference operators

As the title says, my question is on a specific argument in Kirillov - Skew divided difference operators and Schubert polynomials (journal, MSN) on positivity of divided difference operators. I recall ...

**2**

votes

**0**answers

57 views

### Characterization of permutations which have at most one successor in the covering relation of the weak Bruhat order

Let $W$ be the symmetric group on $n+1$ letters. Let $\ell$ be the length function on $W$.
As the title says, can we characterize all $v\in W$ such that there exists a $w\in W$ such that for all ...