All Questions
Tagged with co.combinatorics permutations
352 questions
0
votes
1
answer
98
views
Only special permutations result in a constant expression when permuting coefficients in a sum involving binomials?
Fix $n\geq 1$ and let $p_k(x) := x^k(x-1)^{n-k}$.
Suppose $\pi$ is a permutation on $\{0,1,\dotsc,n\}$, such that
$$
\sum_{k=0}^n (-1)^k \binom{n}{k} p_{\pi(k)}(x) \text{ is a constant}.
$$
Must it be ...
- 13.2k
3
votes
0
answers
92
views
Realized graph of majority of permutations
This question was asked several months ago on Math.SE, but remains unsolved.
For any collection of permutations of $\{1,2,\dots,n\}$, we say that it realizes a directed multigraph with $1,2,\dots,n$ ...
- 277
1
vote
1
answer
77
views
Enumeration of permutations with prescribed numbers of fixed points and excedance/deficiency statistics
Consider the following refinement of permutation statistics. For $π ∈ S_n$, let:
$\mathrm{fix}(π) = |\{i : π(i) = i\}|$ (number of fixed points)
$\mathrm{exc}(π) = |\{i : π(i) > i\}|$ (number of ...
- 18.4k
18
votes
4
answers
1k
views
Generalization of a mind-boggling box-opening puzzle
Motivation. Suppose we are given $6$ boxes, arranged in the following manner:
$$\left[\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \end{array}\right]$$
Two of these boxes contain a ...
- 1,289
4
votes
0
answers
124
views
LIS-based permutation property
Let $S_n$ be the set of all permutations of $\{1, \ldots, n\}$, thereafter treated as integer sequences. Let $A_n$ be the set of all such permutations $\sigma \in S_n$ that we can choose two ...
- 5,590
4
votes
0
answers
91
views
Reference for fact about flags of vexillary permutations
Vexillary permutations are an important family of permutations in Schubert calculus. There are several definitions, for example that they avoid the pattern 2143.
Recall the Lehmer code of a ...
- 1,989
1
vote
0
answers
118
views
Can we construct the circular permutation from partial partition info?
Imagine a circular permutation of n points on a circle, if we draw a line connecting any pair of points, the rest of the points are divided into two sets that are on the same side. We can partition a ...
- 34.3k
2
votes
0
answers
71
views
Are the ranks of the following matrices given by these simple expressions?
The question itself is formulated in the title, so below I specify the matrices and expressions mentioned there. In case if this is something known or can be easily deduced from something known, this ...
- 321
4
votes
1
answer
377
views
Counting permutations with a fixed number of descents and an extra condition
I am computing the volumes of certain polytopes and it turns out that knowing a "closed formula" for the following number would help a lot.
Determine the number of permutations $\sigma\in \...
- 34.3k
0
votes
0
answers
95
views
Nested Set Permutations and their Enumeration
Let $(S_i)_{i \in \mathbb{N}}$ be a sequence of sets defined recursively as follows:
$S_1 = \{1\}$
$S_{i+1} = S_i \cup \{S_i, i+1\} \quad \forall i \in \mathbb{N}$
A permutation $\sigma$ of $S_i$ is ...
- 34.3k
4
votes
1
answer
182
views
Permutations of the natural numbers with a common conditionally convergent series
Let $S\subset S_{\infty}$ be a set of permutations of $\mathbb{N}$. A real series $\sum_{n\geq0}u_{n}$ will be called $S$-conditionally convergent if it is absolutely divergent and if, for all $\sigma\...
- 18.5k
6
votes
0
answers
254
views
Maximal bijection-dodging families on $\mathbb{N}$
We say that a family ${\cal S}\subseteq{\cal P}(\mathbb{N})$ is bijection-dodging if there is a bijection $\varphi:\mathbb{N}\to\mathbb{N}$ with $\varphi(T)\notin {\cal S}$ for all $T\in{\cal S}$.
...
- 800
42
votes
2
answers
2k
views
How decreasing can a bijection $f:\mathbb{N}\to\mathbb{N}$ be?
This is a follow-up to this question by
Dominic van der Zypen. For each bijection $f:\mathbb{N}\to\mathbb{N}$, let
$$\operatorname{rc}(f) := \liminf_{N\to\infty} \frac{\left|\left\{(m,n)\in\{1,\dots,N\...
- 114k
9
votes
1
answer
460
views
Min–max reversing bijections $f:\mathbb{N}\to\mathbb{N}$
For any set $X$, let $\newcommand{\N}{\mathbb{N}}[X]^2 = \big\{\{x,y\}:x\neq y \in X\big\}$ and set $[n]^2 = [\{0,\dotsc,n-1\}]^2$ for any positive integer $n$. For $A\subseteq [\N]^2$ we set $$\...
- 12.9k
0
votes
0
answers
174
views
3D generalization of Gaussian q-binomial coefficient
It is known that the coefficient of $q^t$ in Gaussian binomial coefficient $\binom{m+n}m_q$ equals the number of permutations of the multiset $\{0^m, 1^n\}$ with $t$ inversions.
Is there a closed ...
- 175
8
votes
2
answers
509
views
Bijection $\varphi:\mathbb{N}\to\mathbb{N}$ that distorts every finite arithmetic progression
Let $\mathbb{N}$ denote the set of non-negative integers. We say $A\subseteq \mathbb{N}$ is a finite arithmetic progression if there are $a, n, d\in\mathbb{N}$ with $d \geq 1$ and $n \geq 2$ such that ...
- 48.8k
1
vote
1
answer
200
views
Sign of the permutation when I show that $\star{\star w}= (-1)^{n(n-k)} w$ for the Hodge operator
Let $w=\sum_{I} a_{I}dx_{I}$ be a $k$-form in $\Bbb R ^n$. Let us consider the Hodge operator in a combinatorial form, i.e. as an $(n-k)$ form such that
$$\star(dx_{i_{1}} \wedge \dotsb \wedge dx_{i_{...
- 6,357
11
votes
1
answer
1k
views
Order of the "children's card shuffle"
Motivation. My eldest son thinks the following procedure is a "perfect shuffle" for a deck of cards: Take the first card, put the second on top of it, put the 3rd below cards 2 and 1, put ...
- 48.8k
5
votes
1
answer
213
views
Partition an $(2n+1)$-permutation into two parts in which there are no three consective elements in given sequences
Let $a_1a_2\ldots a_{2n+1}$ ($n\geq 2$) be a given permutation of the numbers from $1$ to $2n+1$ and let
$\alpha_i=\{i,i+1,i+2\},~1\leq i\leq 2n-1$
$\alpha_{2n}=\{2n,2n+1,1\}$
$\alpha_{2n+1}=\{2n+1,1,...
- 34.3k
1
vote
1
answer
168
views
Permutation graph with insert-and-shift
Motivation. I am working with a database software that allows
you to sort the fields of any given table in the following
peculiar way. Suppose your fields are numbered $1,\ldots, 18$.
Next to every ...
- 48.8k
2
votes
2
answers
77
views
Reference request for a subfamily of regular graphs
[Repost of same question math stack exchange which got no answers]
I'm looking for literature on the following family of graphs:
Call a regular graph $G=(V,E)$ (of regularity degree $d$) nice if there ...
- 30.1k
0
votes
0
answers
63
views
Pairs of permutations such that $p(n)<2^k$ iff $n<2^k$
Let $p(n)$ be an arbitrary permutation of natural numbers such that $p(n)<2^k$ iff $n<2^k$.
Let $q(n)$ be an inverse permutation of $p(n)$.
Let
$$
\ell(n)=\left\lfloor\log_2 n\right\rfloor
$$
...
- 4,928
4
votes
1
answer
228
views
Permutation of a mixture of (anti)commuting variables and consistency issue regarding the sign
I asked a similar question in PhysicsSE but it seems more like a mathematical issue, so I post here in a more refined form.
I am not confident if the below description of the problem makes sense. ...
- 3,477
4
votes
0
answers
155
views
Permutation generation problem using swaps
This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.
We're given as input ...
- 2,993
0
votes
0
answers
192
views
Optimal strategy of modified Mastermind game
The following game is a modified version of the popular game Mastermind described here in which you are only given information about the total correct guesses you have made, and nothing about how many ...
- 315
2
votes
2
answers
272
views
Relationship between fixed points and inversions in permutations
Inversions in a permutation $Y$ are defined as pairs where $Y_a < Y_b$ but $a > b$, while fixed points in $Y$ are defined as elements where $Y_a = a$ (i.e., 1-cycles). Let $S_\alpha$ be the set ...
- 183
8
votes
0
answers
171
views
Inversions for parity preserving presentations
I've gotten stuck on a slightly random combinatorial question, and I'm doing a bit of a shot in the dark here to see if someone else has thoughts about it. I'm interested in studying a permutation of ...
- 12.9k
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 ...
- 4,219
2
votes
0
answers
91
views
Splitting natural numbers into subsets with sums equal to A066258
Let $F(n)$ be A000045 i.e. Fibonacci numbers. Here
$$
F(n) = F(n-1) + F(n-2), \\
F(0) = 0, F(1) = 1
$$
Let $a(n)$ be A066258 i.e.
$$
a(n) = F(n)^2F(n+1)
$$
Let $b(n)$ be A345253 i.e. maximal ...
- 4,928
2
votes
0
answers
64
views
Eulerian polynomial from Bruhat interval - h* of something?
Let $\sigma \in S_n$ be a fixed permutation.
Consider the polynomial
$$
P_{\sigma}(t) = \sum_{\substack{\pi \in S_n \\ \pi \leq \sigma}} t^{\textrm{des}(\pi)}
$$
where $\leq$ denotes Bruhat order, and ...
- 15.8k
1
vote
0
answers
84
views
How can one build a min-2-wise independent small sample space from min-3-wise permutations?
I have been studying a polynomial-size set of permutations from one of my lectures. The below image, taken from the lecture notes PDF, illustrates how to construct min-3-wise permutations.
My ...
- 43
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. ...
- 1,446
161
votes
37
answers
17k
views
Conceptual reason why the sign of a permutation is well-defined?
Teaching group theory this semester, I found myself laboring through a proof that the sign of a permutation is a well-defined homomorphism $\operatorname{sgn} : \Sigma_n \to \Sigma_2$. An insightful ...
- 12.9k
9
votes
0
answers
179
views
Are there fast rank and unrank algorithms for integer vectors under the action of a permutation group?
We are distributing $m$ indistinguishable balls in $k$ numbered boxes $S=\{1,2,\ldots,k\}$. A distribution is a tuple of nonnegative integers $a=(a_1,\ldots,a_k)$ whose sum is $m$. We also have a ...
- 4,219
1
vote
0
answers
71
views
Slightly modified program for the A345253 such that specific partial sums equal A066258
Let $F(n)$ be A000045 i.e. Fibonacci numbers. Here
$$
F(n) = F(n-1) + F(n-2), \\
F(0) = 0, F(1) = 1
$$
Let $a(n)$ be A345253 i.e. maximal Fibonacci tree: arrangement of the positive integers as ...
- 4,928
6
votes
1
answer
372
views
Maximizing a sum minus its maximal summand
This is a followup to a question that appeared on m.SE:
Maximize $\displaystyle f(\pi)=\left(\sum_{i=1}^{n}{i\pi_i}\right)-\max_{1\le i\le n}{(i\pi_i)}$ over permutations $\pi\in S_n$.
The problem ...
- 5,429
2
votes
1
answer
60
views
Left-shift cycle generating maps $f:\{0,1\}^{c_0}\to\{0,1\}$ for fixed length $c_0$
This is a strengthening of an older question.
Is there a positive integer $c_0$ with the following property?
For every integer $n\geq c_0$ there is a function $f:\{0,1\}^{c_0}\to\{0,1\}$ such that ...
- 23.7k
21
votes
1
answer
1k
views
Bubblesort with a twist: a tricky termination
Consider an $n$-tuple $\left(a_1, a_2, \ldots, a_n\right)$ of real numbers. We are allowed to perform the following two moves:
S-moves: We pick two adjacent entries $a_i$ and $a_{i+1}$ satisfying $...
- 2,912
2
votes
1
answer
426
views
Conjecture on A057030
Let $P(n)$ of a sequence $s(1),s(2),s(3),...$ be obtained by leaving $s(1),...,s(n-1)$ fixed and reversing every n consecutive terms thereafter; apply $P(2)$ to $1,2,3,...$ to get $PS(2)$, then apply $...
- 23.7k
2
votes
0
answers
90
views
Unexpected recursion for the A193231 (blue code of $n$)
Let $a(n)$ be A193231, blue code of $n$ i.e. self-inverse permutation of non-negative integers such that $a(n)<2^k$ iff $n<2^k$ and
$$
a(n\operatorname{XOR}k) = a(n) \operatorname{XOR} a(k)
$$
...
- 4,928
1
vote
1
answer
108
views
Property of some permutations of non-negative integers such that $a(n)<2^k$ iff $n<2^k$
Let
$$
\ell(n) = \left\lfloor\log_2 n\right\rfloor
$$
Let
$$
f(n) = 2^{\ell(n)}
$$
Let $q_1(n)$ and $q_2(n)$ be an arbitrary self-inverse permutations of non-negative integers (that is, $q_i(q_i(n)) ...
- 7,226
0
votes
1
answer
122
views
Permutation of the natural numbers from operation related to binary expansion of $n$
Let
$$
\ell(n) = \left\lfloor\log_2 n\right\rfloor
$$
Let $T(n,k)$ be a $(k+1)$-th bit from the right side in the binary expansion of $n$. Here
$$
T(n, k) = \left\lfloor\frac{n}{2^k}\right\rfloor \...
- 7,226
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 ...
- 32.1k
0
votes
0
answers
185
views
A perfect shuffle on $\mathbb{N}$
Motivation. This weekend I was playing the pair-matching game Memory (also called Concentration in other parts of the world) against my youngest son, and wondered about what constitutes a "good ...
- 48.8k
-1
votes
1
answer
127
views
A permutation and combination problem about the number of connections in a sequence of n numbers [closed]
There is a sequence of n numbers as 1,2,3,...,n
How many combinations of the connections between two numbers in the sequence without overlaping?
...
- 667
1
vote
0
answers
94
views
The set of combinations has some algebraic structure, similar to the group of permutations? [closed]
The set $S_n$ of permutations over $\{1,2,...,n\}$ has a group structure. What if we take the set $C_{k,n}$ of $k$-combinations of $n$ elements? The first I can say is that $S_n$ acts on $C_{k,n}$. Is ...
- 2,934
7
votes
0
answers
150
views
Question about function on permutations
The following question is motivated by my research.
Let's consider a permutation $\sigma$ of the set $\{1, \ldots, n\}$. We define an element $i \in \{1, \ldots, n\}$ to be locally minimal for $\sigma$...
- 4,736
3
votes
0
answers
121
views
Twisted permutations
We consider a set $E$ with an involution (having perhaps fixed points).
We denote orbits by $\lbrace x,\overline{x}\rbrace$ (with $\overline{x}=x$ in
the case of a fixed point).
We consider sequences $...
- 63.9k
2
votes
0
answers
189
views
Component-wise sums of permutations
Given a set $S$ containing all possible permutations of a vector $v = (1, 2, 3, ..., n-1, n)$, find the size of the set $P$, where $P$ is defined as the set of possible component-wise sums obtained by ...
- 21
12
votes
1
answer
385
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,168