Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

0
votes
0answers
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
3answers
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
1answer
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
0answers
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
1answer
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
3answers
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
0answers
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
0answers
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
2answers
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
0answers
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
3answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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 ...