All Questions
Tagged with co.combinatorics permutations
352 questions
9
votes
1
answer
459
views
Non-enumerative proof that there are many simple permutations?
Terence Tao asked for a non-enumerative proof that a positive proportion of permutations are derangements and got a great answer. Inspired by this, I'd like to ask about another family of permutations....
- 2,339
5
votes
2
answers
472
views
The proportion between permutations and derangements.
Denote the number of derangements by $D_N$. It's known that $D_N/N! \rightarrow 1/e$. Therefore $N!/e$ is an approximation for $D_N$.
I'm trying to bound the difference between this approximation and ...
- 83
9
votes
0
answers
213
views
A duality on partial permutations
A partial permutation matrix $\pi$ is one with at most one 1 in any row and column (the rest 0s). Given one, we can cross out to the East and South (but not Southeast) of each 1. Some boxes get ...
- 27.8k
3
votes
1
answer
1k
views
The distribution of cycle length in random derangement
It is known that for a fixed x $\in \{0,1,...,N-1\}$, the length of the cycle of x in a random permutation in $S_N$ distributes uniformly in
$\{1, . . . ,N\}$.
My question is regarding the length of ...
- 83
0
votes
0
answers
142
views
Notation for substructure, especially for permutations?
Is there a standard notation that expresses substructure?
The specific case that I care about is the following:
Suppose $\sigma,\tau$ are permutations such that $$\sigma(x)\not=x\implies \sigma(x)=\...
- 1,329
8
votes
1
answer
465
views
Permutations of prescribed cycle types that multiply to the identity
Suppose that $\lambda_1,\lambda_2,\lambda_3$ are partititions of $n$. When do there exist permutations $\sigma_1,\sigma_2,\sigma_3 \in S_n$ such that
(1) $\sigma_1\sigma_2\sigma_3$ is the identity;
...
- 263
3
votes
0
answers
135
views
Citation for subset complement result
Let $S=\lbrace s_1,\ldots,s_n \rbrace \subset \lbrace1,\ldots,2n\rbrace$. Consider two operations on $S$: the complement $C(S)=\lbrace 1,\ldots,2n \rbrace \setminus S$ and a reflection* $R(S)=\...
- 4,589
22
votes
2
answers
2k
views
3D generalizations of permutations, RSK correspondence, contingency tables, etc.
I want to gather facts and questions related to 3D generalizations
of permutations, RSK correspondence, contingency tables,
etc. One reason I am interested in this is because it is potentially
related ...
- 1,021
8
votes
2
answers
2k
views
Distribution of distances in permutations
Let's consider all possible permutations of N numbers. Suppose for each permutation we calculate the sum of absolute differences between consecutive elements. Thus, for (1,2,3) one would have abs(1-2)+...
- 99
2
votes
1
answer
244
views
Statistics on Lehmer codes
I am looking at words $\alpha_1 \ldots \alpha_n$, where $\alpha_j \in \{ 1, \ldots, j \}$. Thinking of $\alpha_j$ as a height, these words can be interpreted as left-to-right paths on the positive ...
- 3,081
5
votes
1
answer
2k
views
Number of Permutations with k-inversions and with a single clamped value
This question is cross-posted from math.stackexchange because it might be too technical.
Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\sigma\in S_n$ is the ...
- 4,952
5
votes
2
answers
965
views
Maximum distance within a subset of permutations
I'm modelling a scheduler that accepts a sequence of requests and outputs a sequence of responses, one response per request. It can partially reorder requests, but only within a finite queue. ...
- 151
10
votes
5
answers
860
views
Properties of permutations with unknown pattern avoidance descriptions
Background
Many properties of permutations can be stated in terms of classical patterns.
For example:
a permutation is stack-sortable if and only if it avoids 231 (Knuth 1975)
a permutation ...
18
votes
1
answer
1k
views
Salié permutations and fair permutations
In October 2010, I published a Monthly problem that introduced the concept of a fair permutation, which is a permutation $\pi$ such that for every $i$, either $\pi(i) > i$ and $\pi^{-1}(i) > i$, ...
- 82.7k
0
votes
1
answer
185
views
What are the number of possible ways to build up a certain path?
What are the number of possible ways to build up a certain path?
I was working on a graph problem and was trying to find out in how many possible ways can you build/grow a given path. With building/...
3
votes
0
answers
251
views
Permutations & Balanced Distribution
I would like to implement a form of consistent hashing using a set of permutations.
The rules are as follows:
I have Y=~32 buckets and X items. Buckets may be "alive" or "dead". Items are to be ...
- 31
3
votes
1
answer
1k
views
inversion vector for multiset permutation
The definition of inversion vector for permutation is very well defined. Each permutation can be mapped to a unique inversion vector. So is there a well defined inversion vector for each multiset ...
- 285
0
votes
1
answer
293
views
Sequence of permutations without a fixed point
I need to find $m$ permutations $A_1,..,A_m$ where each $A_i$ is a permutation on $n$ objects such that any of the compositions $A_jA_{j+1}..A_{j+k}$; $1 \leq j \leq n-1$ and $j+k \leq m$ does not ...
- 103
4
votes
1
answer
1k
views
Probabilty of two permutations having common elements?
What is the probability of two permutations on set X of size m (i.e. |X|=m) having at least n points of intersection? By this I mean that if two permutations, which I'll call g(x) and h(x), map a ...
- 55
12
votes
1
answer
766
views
Sliding blocks puzzle
Consider a 'game' played on a subset $S$ of an $n^2$ square grid as follows. There are 3 types of pieces, each occupying a square of $S$, 1 green, some red and the rest are blue, a move consists of ...
- 121
10
votes
1
answer
683
views
Analogues of the Knuth and Forgotten equivalences on permutations: have they been studied?
Consider a totally ordered alphabet $A$ of $n$ letters. Let $W$ be the set of all words over $A$ which have no two letters equal. Then, for example, we can define the Knuth equivalence on $W$ as the ...
- 33.8k
6
votes
0
answers
256
views
Counting Selections of Entries such having an Extremal Permutation of length n^2+1
Let $S_{n^2+1}$ be permutations of length $n^2+1$. By Erdos-Szekeres Theorem. any $s \in S_{n^2+1}$ would have a monotone subsequence(increasing or decreasing)of length $n+1$.
Say a permutation $s$ of ...
- 393
1
vote
2
answers
540
views
Complement to part of a permutation matrix
Consider a rectangular $(m \times n)$ matrix $\underline E_1$ with $m < n$ that has only $0$ or $1$ entries. It has exactly one $1$ entry in each row and not more than one $1$ entry in each column. ...
- 113
20
votes
4
answers
2k
views
An $n!\times n!$ determinant
Let us consider the matrix $A$ with its rows and columns enumerated by the elements of $S_n$ with $A_{\sigma\tau}=x^{c(\sigma\tau^{-1})}$ where $c()$ is the number of cycles in a permutation's ...
- 3,513
47
votes
6
answers
5k
views
Non-enumerative proof that there are many derangements?
Recall that a derangement is a permutation $\pi: \{1,\ldots,n\} \to \{1,\ldots,n\}$ with no fixed points: $\pi(j) \neq j$ for all $j$. A classical application of the inclusion-exclusion principle ...
- 114k
7
votes
0
answers
204
views
Bound on coefficients in Young tableuax
The following may be known, but I didn't find anything in the literature.
Background:
The irreducible representations of $S_n$ correspond to shapes of Young tableaux with $n$ elements. Let $\lambda$ ...
- 410
0
votes
2
answers
2k
views
non negative integer solutions : Diophantine Equations [closed]
I want to know the exact number of non-negative integer solutions of $a_1 + 2a_2 + \ldots + k \cdot a_k = n$.
I know that it is the co-efficient of $x^n$ in $(1 - x^{a_1})^{-1} \cdot (1 - x^{a_2})^{-...
- 101
0
votes
3
answers
800
views
Computing Permutations with Partial Duplicates
I am looking for a way to compute the number of $K$ permutations of a multiset with $N*D$ elements where each group has exactly $D$ equal elements (and typically $D < N$ ).
I've got an application ...
- 111
6
votes
1
answer
448
views
Counting the (additive) decompositions of a quadratic, symmetric, empty-diagonal and constant-line matrix into permutation matrices
Dear community,
I have the following combinatorial question which I will explain in short first and then with some more detail. At the end you will find a very simple example.
Short version
Le $A \...
- 199
10
votes
0
answers
302
views
Are plactic classes convex under the right weak Bruhat order?
For those who are unfamiliar with the terminology, I'll explain a little.
The symmetric group $S_n$, as a type A Coxeter group, has generators $\{s_1,\ldots,s_{n-1}\}$ with relations (1) $s_i^2$ for ...
- 331
3
votes
1
answer
338
views
Stricter permutation patterns
(I asked this ten days ago on math.SE, but I received no reply, so I'm trying again here.)
A lot of work has been done on patterns in permutations, where a permutation is said to match a given ...
- 1,164
4
votes
0
answers
195
views
restricting "dances of minimal cost" (optimization on braids/permutations?)
Consider applying the permutation (1,3,0,5,2,7,4,6) to the integers (0,1,2,3,4,5,6,7) three times.
I call this a "dance of minimal cost" because all unordered pairs in {0..7} meet each other, and the
...
- 121
23
votes
0
answers
1k
views
Do all possible trees arise as orbit trees of some permutation groups?
I.Motivation from descriptive set theory
(Contains some quotes from Maciej Malicki's paper.)
The classical theorem of Birkhoff-Kakutani implies that every metrizable topological group G admits a ...
- 181
1
vote
1
answer
879
views
Generating fixtures for a chess league, with a twist
Hello,
I am in the process of building some software to generate fixtures for a chess league. Which has a little twist which complicates matters. I would like to introduce a constraint. Where by a ...
- 111
7
votes
2
answers
751
views
Looking for deterministic criteria to generate the symmetric group?
So let $S_N$ be the symmetric group of degree $N$. We think of it as a permutation group via its
natural action on the set $T=\{1,2,\ldots,N\}$.
Say that $H\leq S_N$ is a subgroup which acts ...
- 7,609
12
votes
4
answers
2k
views
Cyclic Permutations - but not what you think
This question is not about elements of $S_n$ that consist of a single $n$-cycle, though naturally it's related.
Instead, consider permutations modulo the action of $(123\ldots n)$. That is, we ...
- 367
0
votes
1
answer
482
views
Request for a copy of a paper of J. Dénes on permutation factorisations [closed]
I'm unable to access the following paper: J. Dénes, The representation of a permutation as the product of a minimal number of transpositions and its connection with the theory of graphs, Publ. Math. ...
- 1,164
6
votes
5
answers
2k
views
Convert integer to permutation number
I have no idea how to achieve this, any help would be greatly appreciated and very useful to me.
I have a loop in some computer code, that loops through every single combination of 7 on bits in a 64 ...
- 71
1
vote
0
answers
525
views
Expected number of cycles for this class of permutations
(Am not mathematician, sorry in advance for the sloppy notations.)
Consider the class of permutations of $n$ elements such that for each permutation $\pi$ in this class, and for each $x$ in $\{1,\...
- 11
3
votes
1
answer
272
views
Reference for: the Bruhat-minimal permutations not less than a fixed permutation pi?
Let $\pi\in S_n$. I recently needed to understand the permutations $\rho$ such that $\rho\not\leq\pi$ in Bruhat order. Since there are $O(n!)$ of those I really wanted a description of the $O(n^2)$ ...
- 27.8k
4
votes
2
answers
462
views
Distinguishing finite-orbit permutation groups by action on tuples
Let $G$ and $H$ be permutation groups on the natural numbers such that the orbits of $G$ and $H$ are all finite. Suppose that for all $\pi \in Sym(\mathbb{N})$, there is some $N$ (depending on $\pi$) ...
- 4,728
40
votes
1
answer
2k
views
Orders of products of permutations
Let $p$ be a prime, $n\gg p$ not divisible by $p$ (say, $n>2^{2^p}$). Are there two permutations $a, b$ of the set $\{1,...,n\}$ which together act transitively on $\{1,2,...,n\}$ and such that all ...
user6976
2
votes
1
answer
467
views
Distribution on permutations derived from probability of pairwise orderings
A followup question to Probability estimates for pairwise majority votes - I think it doesn't actually give an answer in any terribly precise sense, but it would give something I'd be happy to use in ...
- 1,331
12
votes
3
answers
2k
views
Computing Bruhat Order Covering Relations
To put this in context: I am in the process of developing a package for Macaulay 2 (a commutative algebra software,) called "Permutations", which will add permutations as a type of combinatorial ...
- 1,324
1
vote
1
answer
922
views
Permutations with extra restrictions
I have a set of items, for example: {1,1,1,2,2,3,3,3}, and a restricting set of sets, for example {{3},{1,2},{1,2,3},{1,2,3},{1,2,3},{1,2,3},{2,3},{2,3}. I am looking for permutations of items, but ...
- 13
4
votes
2
answers
2k
views
How to compute the rook polynomial of a Ferrers board?
Given a Ferrers board of shape $(b_1,\ldots,b_m)$, we define $r_k$ as number of ways to place $k$ non-attacking rooks (as in Chess). In section 2.4 of Stanley's Enumerative Combinatorics (vol. 1) it's ...
- 1,015
15
votes
5
answers
7k
views
infinite permutations
This question is related to this one: Continued fractions using all natural integers. Suppose we have the set of natural numbers $N$ with order and we perform permutation on it. So we obtain the same ...
- 1,626
8
votes
1
answer
931
views
Two [n] to [n] function families
Note. This question had a bounty, so at the end I accepted the best (and only) answer. However, a solution is implied by the answer to this question.
Question.
Fix n. We are interested in the biggest ...
- 18.8k
15
votes
3
answers
868
views
What bijection on permutations corresponds under RS to transpose?
The Robinson-Schensted correspondence is a bijection between elements of the symmetric group and ordered pairs of standard tableaux of the same shape.
Some simple operations on tableaux correspond to ...
- 44.7k
14
votes
3
answers
2k
views
Equivalence relations on permutations and pattern avoidance
I'm working on the interaction between equivalence relations on permutations and pattern avoidance. I've only considered Knuth equivalence and cyclic shifts until now and I'm looking for other ...
- 1,155