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 ...
- 15.8k
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 ...
- 11
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 ...
- 48.8k
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 ...
- 11
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
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 ...
- 1
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\...
- 105
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}$.
...
- 48.8k
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\...
- 10.6k
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 $$\...
- 48.8k
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_{...
- 251
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,...
- 557
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
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
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 ...
- 21
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
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
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 ...
- 44.7k
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
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
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
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
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 ...
- 48.8k
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 ...
- 1,190
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 $...
- 33.8k
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)) ...
- 4,928
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 \...
- 4,928
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?
...
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 ...
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 $...
- 17.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
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 ...
- 34.3k
3
votes
1
answer
188
views
Removing the symmetry maps from a small category of cubes
Let $[1]^n=\{0<1\}^n$ equipped with the product order. I consider the small category $\widehat{\square}$ of the category of partially ordered sets generated by the coface maps $\delta^\epsilon_i:[1]...
- 3,901
0
votes
0
answers
133
views
On nilpotent singular $\mathbb F_2^{n\times n}$ matrices
Let $M$ be a $0/1$ matrix over $\mathbb F_2^{n\times n}$ with determinant $0$.
The set of such singular matrices form a semigroup.
The set of nilpotent matrices of size $n\times n$ form a semigroup.
...
- 13.9k
2
votes
0
answers
76
views
Uniqueness of the permutation
Let $f(n)$ be A000045(n), i.e., Fibonacci numbers: $f(n)=f(n-1)+f(n-2)$ for $n>1$ with $f(0)=0$ and $f(1)=1$.
Let $g(n)$ be A072649, i.e., $n$ occurs $f(n)$ times. The sequence begins with
$$1, 2, ...
- 4,928
1
vote
0
answers
109
views
Existence of binary permutations with a given property
Let
$$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$
Let
$$f(n)=n-2^{\ell(n)}$$
Let $a(n)$ be a permutation of the nonnegative integers such that $a(0)=0$, $a(n)=n$ if $n$ is a power of $2$ and ...
- 4,928
2
votes
1
answer
172
views
Permutation and its binary analog
Let $f(n)$ be A000045(n), i.e., Fibonacci numbers: $f(n)=f(n-1)+f(n-2)$ for $n>1$ with $f(0)=0$ and $f(1)=1$.
Let $g(n)$ be A072649, i.e., $n$ occurs $f(n)$ times. The sequence begins with
$$1, 2, ...
- 4,928
1
vote
0
answers
81
views
Infiniteness of the pairs of sequences with a given conditions
Let
$$\varphi=\frac{1+\sqrt{5}}{2}$$
Let
$$a_1(n)=\left\lfloor n\varphi \right\rfloor, a_2(n)=n+a_1(n)$$
Let $\operatorname{tr}(n)$ be A007814, i.e., the number of trailing zeros in the binary ...
- 4,928
0
votes
0
answers
61
views
Stolarsky array and Stolarsky representation
Let $T(n,k)$ be A035506, i.e., Stolarsky array read by antidiagonals. Here we consider that $T(n,k)=0$ for $n<1, k<1$.
Let $a(n)$ be A200714, i.e., Stolarsky representation interpreted as binary ...
- 4,928