All Questions
Tagged with co.combinatorics permutations
352 questions
0
votes
0
answers
185
views
Sum of unit vectors always has a binary span after constrained permutations
Conjecture:
Let $e_1 = (1,0,\ldots,0), \ldots , e_{m_1+m_2} = (0,\ldots,0,1)$ be the unit vectors of the standard basis $E$ of $\mathbb{R}^{m_1+m_2}$.
An enumeration $ E \cup -E = \{f_1, \ldots, ...
- 121
6
votes
2
answers
273
views
Number of linear orderings of a set to have balanced frequencies of triple orders
Let $S$ be a set of $n$ elements and let $Q = (s_1, s_2, \ldots, s_n)$ be a linear ordering of $S$. We write $s_i <_Q s_j$ when $s_i$ appears before $s_j$ in $Q$.
I want to construct a set (or ...
- 270
-3
votes
2
answers
2k
views
What is the number of self-inverse permutations on a set of cardinality $N$?
Given a function (aka 'permutation') $f:A \rightarrow A$, where $A$ is a finite set such that $|A| = N$, we call it a self-inverse if $f(f(x)) = x$. The sequence of how many such functions exist for ...
12
votes
2
answers
292
views
Permutation search problems with no known $o(n!)$ algorithms
I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one ...
- 333
3
votes
1
answer
126
views
Density of permutation of syndetic sets of integers
Define the upper uniform density of a set $A\subset\mathbb{Z}$ to be
$$
D^+(A)=\lim_{r\rightarrow\infty}\sup_{a\in\mathbb{R}}\frac{|A\cap[a,a+r)|}{r}
$$
Fix an arbitrary permutation of the integers $\...
- 549
6
votes
1
answer
410
views
Maximum size of minimal sequence of transpositions whose product is a given permutation
Consider the sequence $S = 1,2,3,\ldots n$ of elements, along with a sequence $T = t_1, t_2, \ldots, t_m$ of transpositions. Each transposition $t_i$ is a tuple $(a_i, b_i) \in [n]^2$. When applying a ...
- 291
1
vote
1
answer
153
views
Counting faces on multipermutahedra/multipermutohedra
A multipermutahedron is the convex hull of all permutations of a list of numbers. For example, $\Pi(0,1,2)$ generates a regular hexagon, and $\Pi(0,1,1,2)$ generates a cuboctahedron.
In general, ...
- 363
3
votes
1
answer
200
views
Braid group: Can a left-twist increase the number of right twists?
Disclaimer: This question was first posted on math.se without any answer.
This is something that naturally occurs in my research, but I am no expert on this - it feels like a natural question so I am ...
- 15.8k
9
votes
1
answer
523
views
Choosing $K$ "centers" from the space of permutations
Let $\Pi$ denote the space of all permutations of $\{1,\dots,n\}$, and let $d(\cdot,\cdot)$ be a metric on $\Pi$. Suppose I am given a large integer $K$ and I have to select $K$ permutations $\pi_1,\...
- 4,049
5
votes
1
answer
270
views
Counting the number of permutations of $(1,\ldots,i,\ldots,j,\ldots,m)$, where $i < j$ and number of inversions is $k$
How can I prove the following:
$d^{ij}(m,k) > d^{ji}(m,k)$ for all $k < \frac{1}{2}\binom{m}{2},$
where $d^{ij}(m,k)$ denotes the number of permutations of $(1,\ldots,i,\ldots,j,\ldots,m)$ ...
- 85
0
votes
0
answers
62
views
normal sets and conjugate generating sets of $S_n$
In this arXiv paper (p. 13), Steinhardt defines a normal set in $S_n$ as follows:
Definition: A split set of more than two cycles generating $S_n$ is said to be normal if any element is adjacent to ...
- 146
1
vote
0
answers
52
views
Invariants of Permutations with Predicate and Equivalency Relation
Has the following kind of problem been investigated previously and, where can I find information about it:
Given
the set $\mathbb{P}_{n_0}$ of all permutations of $n_0$ elements
a predicate $P: p\...
- 13.2k
4
votes
1
answer
325
views
Hyperoctahedral group acting on a special permutation
Let $[n]=\{1,...,n\}$ and $[\hat n]=\{\hat 1,...,\hat n\}$. Realize the hyperoctahedral group $H_n$ as the centralizer of the permutation $(1\hat 1)\cdots (n \hat n)$. It has $2^n n!$ elements.
Let $...
- 2,552
6
votes
0
answers
240
views
Factorization of permutations into two factors with fixed number of cycles, plus a placement condition
In my recent work I have been led to consider the following type of permutation factorizations.
Let $\pi_1$ and $\pi_2$ be two fixed permutations, with disjoint support, i.e. $\pi_1$ acts on $\{1,......
- 2,552
3
votes
2
answers
1k
views
Counting Specific Permutations of Elements in a Multiset
I have a question regarding counting permutations of a multiset's elements. The problem is the following:
Given a multi-set $M=\{0^{m}, 1^{n-m}\}$ the number of all possible permutations of its ...
- 33
2
votes
2
answers
664
views
On $XX'=I$ such that $AX=XB$ is true when $A,B\in\{0,1\}^{n\times n}$
Given real symmetric matrices $A,B\in\{0,1\}^{n\times n}$ is it true that $$AX=XB$$ has a solution of form $X$ a permutation matrix iff a solution with $XX'=I$ exists? We are over reals.
It is clear ...
- 13.9k
5
votes
1
answer
150
views
Weights on cyclic orderings
Are there standard or known weights/metrics on cyclic orders?
Cyclic orderings are different ways of listing elements from a finite set, where you call two lists the same if they differ only by a ...
- 609
7
votes
1
answer
414
views
Weighted Permutation Sum
I am trying to find out a closed-form formula (or a generating function at least) for the number of permutations $\sigma$ that satisfy $$ S = \sum_{i = 1}^{n} i\sigma(i)$$ for a given value of $S$. We ...
- 301
2
votes
0
answers
151
views
How hard is recognizing a permutation that is a square for the shift product?
This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation ...
- 2,993
1
vote
0
answers
151
views
Finding optimal set of permutations [closed]
I have the following data set of a human population. The data set captures households and relationships of the persons living in those households. My problem is how to group the individuals into ...
- 111
45
votes
5
answers
3k
views
How many rearrangements must fail to alter the value of a sum before you conclude that none do?
This will not be altogether unrelated to this earlier question.
For which classes $C$ of bijections from $\{1,2,3,\ldots\}$ to itself is it the case that for all sequences $\{a_i\}_{i=1}^\infty$ of ...
30
votes
1
answer
1k
views
Rearrangements that never change the value of a sum
I posted this question on math.stackexchange.com and so far the only answer posted (also mentioned in the comments under the question) shows that one of my rash initial guesses about the bottom-line ...
0
votes
0
answers
96
views
A constrained minimum edge coloring
Is minimum number of colors needed to color edges of complete graph $K_n$ so that every even simple cycle contains at least one color assigned to odd number of edges at most $\beta n$ where $\beta\...
- 13.9k
5
votes
0
answers
181
views
Extrapolation between longest increasing and longest alternating subsequences
The question
When should we expect Tracy-Widom?
motivated me to post the following question, in which I have been
interested for a while. Let $f(n)$ be a function from the positive
integers to ...
- 50.8k
8
votes
3
answers
3k
views
Permutations with all cycles odd length and permutations with all cycles even length
If $n$ is even, then the number of permutations of $n$ in which all cycles have odd length equals the number of permutations of $n$ in which all cycles have even length. This fact is easily proved, ...
- 82.7k
3
votes
1
answer
647
views
Regarding left-to-right minima
Let $\rho$ be a permutation on $[1,n]$ and $l_i$ be the number of left-to-right minima in $\rho_{i\ldots n}$, I know that for a random permutation $E[l_1] = H_n$ (the $n$-th Harmonic number) but is ...
- 31
3
votes
0
answers
156
views
Exact growth rate of Longest Increasing Subsequence expectation
Let $S_n$ be the symmetric group, $\pi\in S_n$ a uniformly random permutation and $L_n:=L_n(\pi)$ denoting the length of the longest increasing subsequence (LIS). We know that $\lim_{n\rightarrow\...
- 4,952
15
votes
4
answers
639
views
Sets of points containing permutations - a Ramsey-type question
The following question arised as a side-question in a geometric problem. It has a "feel" similar to problems in Ramsey-theory, but I have not found any mention of it (also I'm not very familiar with ...
- 711
3
votes
1
answer
252
views
Hopf structures on "pictorial" descriptions of permutations
There is a well-known Hopf structure on permutations, due to Malvenuto and Reutenauer. Here, the F basis elements are permutations in one-line notation, the product of two permutations is their ...
- 131
7
votes
2
answers
1k
views
Numbers with all N-digit prefixes divisible by N
In base 10, the number 3816547290 contains every digit exactly once. When I take the first N digits, that substring is divisible by N. For example, 381 is divisible by 3, 38165 is divisible by 5, etc. ...
- 173
12
votes
1
answer
353
views
Number of orders of $k$-sums of $n$-numbers
Suppose we have a $n$-element set $S$. Denote the set of its $k$-element subsets by $K$ ($|K|=\binom{n}{k}$).
If the elements of $S$ are real numbers then to each $k$-element subset we can associate ...
- 1,431
15
votes
2
answers
512
views
Does a classification of simultaneous conjugacy classes in a product of symmetric groups exist?
Let the symmetric group $S_n$ on $n$ letters act on $S_n^d=S_n\times\cdots\times S_n$ by simultaneous conjugation, i.e. $\pi\in S_n$ acts on $(\sigma_1,\ldots,\sigma_d)\in S_n^d$ by $\pi.(\sigma_1,\...
- 4,902
4
votes
1
answer
255
views
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
$$\sum_{\sigma \in S_n} q^{\operatorname{inv} \sigma}=\sum_{\sigma\in S_n}q^{\operatorname{maj}\sigma},$$...
- 85.6k
28
votes
2
answers
1k
views
Is this graph polynomial known? Can it be efficiently computed?
I am a physicist, so apologies in advance for any confusing notation or terminology; I'll happily clarify. To provide a minimal amount of context, the following graph polynomial came up in my research ...
- 281
3
votes
1
answer
365
views
counting the number of ordered pairs in a permutohedron
Recall that a permutohedron is a graph on the set of permutations $S_n$ with an edge between $\sigma$ and $\tau$ if they differ by one adjacent transposition: $\tau = (i,i+1) \circ \sigma$ for some $i ...
- 4,466
12
votes
2
answers
758
views
Principal Order Ideals in the Weak Bruhat Order
Let $\sigma\in S_n$ be a permutation on $n$ elements, and $\mathrm{Inv}(\sigma):=\{(i,j) : 1\leq i<j\leq n\text{ and }\sigma(i)>\sigma(j)\}$ be its set of inversions. In the weak order on ...
- 1,324
22
votes
2
answers
2k
views
Shortest supersequence of all permutations of $n$ elements
Given an alphabet with $n$ characters, what is the shortest sequence that contains all $n!$ permutations as subsequences?
A subsequence can be obtained from a sequence by deleting any characters, ...
- 702
8
votes
1
answer
227
views
Distribution of entries of a doubly-sorted random matrix
Take an $n \times n$ random matrix whose entries are i.i.d. with uniform distribution in $[0,1]$. Look at the sums of the elements of each row and then permute the rows so that these sums form an ...
- 2,479
10
votes
1
answer
519
views
Explicit algorithm for composing permutations in factorial notation
Given two permutations p1 and p2 in factorial notation, is there an algorithm which computes their composition directly, i.e. without translating to a different notation (like Cauchy's 2-line notation,...
- 11.8k
3
votes
2
answers
333
views
Combinatorial design for minimization problem over binary strings
Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...
26
votes
6
answers
3k
views
Why is the right permutohedron order (aka weak order) on $S_n$ a lattice?
This is one of those things I never expected to be hard until I tried to prove it. Why is the right permutohedron order (a.k.a. weak Bruhat order, a.k.a. weak order -- not to be confused with the ...
- 33.8k
1
vote
1
answer
321
views
Cycles of Permutation Related to Rectangular Matrix Transposition
let the entries of a rectangular matrix $A\in\mathbb{C}^{m\times n}; m,n\in\mathbb{N}$ be stored in row-order in a linear vector $v$, i.e. $A_{i,j}=v_{i*m+j}$
Question:
How can the first element ...
- 13.2k
9
votes
2
answers
500
views
Unimodality of length of longest increasing subsequence
For $w \in S_n$, the symmetric group on $n$ letters, let $\mathrm{is}(w)$ denote the length of the longest increasing subsequence of $w$. Define, $g_n(p) := |\{w \in S_n \colon \mathrm{is}(w) = p\}|$. ...
- 24.2k
4
votes
1
answer
330
views
Combinatorial Technique Needed
The following problem is likely too special for MO.
However I have no clue how to deal with it, so I'll just try. Nevertheless
it is a combinatorial problem and a discussion about general methods
in ...
- 2,074
1
vote
1
answer
101
views
Probability of seeing m nonzero bits in off any d consecutive bits in a circle of n bits
Suppose n bits are arranged circularly with given condition that random k of them are 1 and rest 0, and all possible d consecutive bits (total n possibilities) are looked at, what is the probability ...
- 11
1
vote
2
answers
163
views
Draws from multiple non-disjoint urns
Let $C = \{1,...,n\}$ be a set of $n$ colors. Let $S_1,...,S_k$ be non-empty subsets of $C$, that is, $S_i \subseteq C$ for all $i \in \{1,...,k\}$. It is helpful to think of the $S_i$ as urns with ...
- 83
10
votes
5
answers
1k
views
Number of Permutations?
Edit: This is a modest rephrasing of the question as originally stated below the fold: for $n \geq 3$, let $\sigma \in S_n$ be a fixed-point-free permutation. How many fixed-point-free permutations $\...
- 101
22
votes
2
answers
1k
views
Laws of Iterated Logarithm for Random Matrices and Random Permutation
The law of iterated logarithm asserts that if $x_1,x_2,\dots$ are i.i.d $\cal N(0,1)$ random variables and $S_n=x_1+x_2+\cdots+x_n$, then
$$\limsup_{n \to \infty} S_n/\sqrt {n \log \log n} = \sqrt 2, $...
- 24.7k
35
votes
1
answer
2k
views
How hard is reconstructing a permutation from its differences sequence?
My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is ...
- 2,993
37
votes
2
answers
3k
views
A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself
Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...
- 1,730