All Questions
Tagged with co.combinatorics permutations
109 questions with no upvoted or accepted answers
3
votes
0
answers
293
views
Primes arising from permutations (II)
In Question 315259 (cf. Primes arising from permutations) I asked a question on primes arising from permutations which looks quite challenging.
Here I pose a new question in this direction which does ...
- 15.6k
3
votes
0
answers
46
views
Maximal number of sets, obtained as intersections of semiintervals of $k$ linear orders
Given a finite set $S$ with $n$ elements, and a fixed small $k$ (say $k=3$), how to find $k$ linear orders $\leq_1, \dots, \leq_k$ on $S$, such that the number of feasible subsets of $S$ is ...
3
votes
0
answers
627
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 ...
- 499
3
votes
0
answers
194
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: ...
- 593
3
votes
0
answers
190
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 ...
- 185
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
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
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
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
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,938
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
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,938
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
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,938
2
votes
0
answers
71
views
Closed form for the number of permutations with a given excedance set
Let $q(n)$ be A007814, i.e., number of trailing zeros in the binary representation of $n$. Here
$$q(2n+1)=0, q(2n)=q(n)+1$$
Let $\operatorname{wt}(n)$ be A000120, i.e., number of $1$'s in binary ...
- 4,938
2
votes
0
answers
95
views
A minimal size of a set of tuples for an upper bound of a distance between any pair of elements
Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates)....
- 959
2
votes
0
answers
732
views
Expected value of length of longest cycle in permutation
Let $n$ be a positive integer and let $S_n$ be the collection of permutations $\pi:\{1,\ldots,n\}\to \{1,\ldots,n\}$. For $\pi\in S_n$ let $\text{maxcyc}(\pi)$ denote the length of the longest cycle ...
- 48.9k
2
votes
0
answers
301
views
Magic squares as sums of permutation matrices
A magic square of size $n$ and sum $k$ is a $n\times n$ matrix with non-negative integer elements, whose rows and columns all sum to $k$. A permutation matrix is a magic square of sum $1$. Every magic ...
- 2,552
2
votes
0
answers
85
views
Elements of the Hall basis described via permutations
Good morning,
Suppose that $\mathfrak{g}$ is a free graded Lie algebra generated by the elements $1,\dots, n$, i.e. assume that $\mathfrak{g}_1=\mathrm{span}\{1,\dots, n\}$. Let us focus on the Hall ...
- 277
2
votes
0
answers
192
views
A conjecture on crossing numbers related to primes
For a permutation $\sigma\in S_n$, its crossing number $\text{cr}(\sigma)$ is the number of pairs $\{i,j\}$ with $i,j\in\{1,\ldots,n\}$ such that
$$i<j\le\sigma(i)<\sigma(j)\ \ \text{or}\ \ \...
- 15.6k
2
votes
0
answers
85
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^* = ...
- 1,989
2
votes
0
answers
85
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$ ...
- 2,552
2
votes
0
answers
110
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\...
- 1,549
2
votes
0
answers
81
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 ...
- 1,066
2
votes
0
answers
206
views
What is the maximum weighted earth-movers distance between two permutations?
What is the maximum weighted earth-mover's distance (as defined in Sun et. al. 2010) between two permutations in $\mathfrak S_n$ where the transposition $(i, i+1)$ has cost given by weight $w_i$. In ...
- 821
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
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
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,938
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,938
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,938
1
vote
0
answers
85
views
Permutation to get Stolarsky representation from lazy Fibonacci (dual Zeckendorf) representation
Let $a_1(n)$ be A200714, i.e., Stolarsky representation interpreted as binary to decimal integers. The sequence begins with
$$0, 1, 3, 2, 7, 5, 6, 15, 4, 11, 13, 14, 31, 10, 9, 23, 12, 27, 29$$
Let $...
- 4,938
1
vote
0
answers
155
views
Proving a sign rule for $f_{2n}$
If $t_{1},...,t_{n}$ are real numbers, consider the set of indexed linear operators $T(t_{1}),...,T(t_{n})$ on a Hilbert space $\mathcal{H}$ and define its ordering by:
$$\pi[T(t_{1})\cdots T(t_{n})] :...
1
vote
0
answers
46
views
Permutation of nonnegative integers applied to the numbers $n$ whose binary expansion does not begin with $11$
Let $\operatorname{wt}(n)$ is A000120, number of $1$'s in binary expansion of $n$ (or the binary weight of $n$) and
$$n=2^{b_1}(1+2^{b_2+1}(1+2^{b_3+1}(1+\cdots(1+2^{b_{\operatorname{wt}(n)-1}+1}(1+2^{...
- 4,938
1
vote
0
answers
107
views
A maximization problem with permutations
Consider a partition $f:S_n\rightarrow [n]$ of $S_n$ into $n$ parts. Denote the permutations that map $j$ to $k$ by $s(j,k)$. Set $S(f):=\Sigma_{1\leq i,j\leq n}max_{1\leq k\leq n}|f^{-1}(i)\cap s(j,k)...
- 422
1
vote
0
answers
94
views
Is there a characterization for the finite sequences of natural numbers which are the shifts of a permutation?
Given a natural number $k<n$ and a permutation $\sigma\in S_n$, I will call $k$ a shift of $\sigma$ if there is some $m$ with $\sigma(m)-m\equiv k \mod n$. If one is given a sequence $s=(x_1,...,...
- 422
1
vote
0
answers
116
views
Untruncate permutohedron of order 5
I would like to understand commutation classes of reduced expressions of the longest element in $S_5$ a little better. For this, it makes sense to look at the permutohedron of order 5. Since I am only ...
- 1,813
1
vote
0
answers
177
views
Combinatorial bijection on monotone sequences
Let $(n),\mu$ be the partition of $n$ define $H_g^{m}((n);\mu)$ count's the number of tuples $(\tau_1,\ldots,\tau_r)$ of transposition in symmetric group $S_n$ with the following conditions
$$ (1,2,\...
- 685
1
vote
0
answers
147
views
A certain kind of permutations and transport of Bruhat chains under conjugation
Let $(W,S)$ be a finite Coxeter system. Let us consider the following situation:
Let $v_1,v_2,w\in W$ such that $v_1=wv_2w^{-1}$. Let $s_{\beta_r}\ldots s_{\beta_1}$ be a reduced expression of $v_2$. ...
- 1,066
1
vote
0
answers
122
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=...
- 623
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
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
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
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,938
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
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.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 ...
- 34.3k
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
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,938
0
votes
0
answers
94
views
Permutation using irreducible fractions
Let
$$f(n,k)=n\operatorname{mod} k, g(n,k)=\left\lfloor\frac{n}{k}\right\rfloor$$
Let $T(n,k)$ be A072030, i.e., array read by antidiagonals: $T(n,k)$ = number of steps in simple Euclidean algorithm ...
- 4,938