All Questions
Tagged with enumerative-combinatorics permutations
37 questions
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
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
0
answers
205
views
Non-crossing and crossing bijection in higher genus
This is a follow-up question of my SO post I'll briefly mention it here.
So given a $n$ cycle say $(1,2,\ldots,n)$, what are the monotonic 2 -tuples, of the form $(a,b)(c,d)$, monotonicity in on the ...
- 685
3
votes
1
answer
226
views
Sums over permutations relates to permutations?
Consider the permutation group $\mathfrak{S}_n$ on $n$ letters $\{1,2,\dots,n\}$. Let $\iota=(1,2,3,\dots,n)\in\mathfrak{S}_n$ be the identity permutation in a $1$-line notation. Given $\pi, \rho\in\...
- 43.1k
10
votes
0
answers
429
views
321-avoiding and parity-alternating permutations
It is classical that 321-avoiding permutations are enumerated by the Catalan numbers.
A permutation is parity-alternating if it sends even integers to even integers, and odd integers to odd. I am ...
- 15.8k
4
votes
1
answer
349
views
The fraction $\frac{g_{\mu}}{f_{\lambda}}$ is an integer
Let $\lambda=(\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_{\ell(\lambda)}>0)$ be an integer partition of $n\in\mathbb{N}$; i.e., $\lambda_1+\cdots+\lambda_{\ell(\lambda)}=n$.
One may now associate $...
- 43.1k
5
votes
1
answer
347
views
Counting monomials and the Catalan numbers
Given a multi-variable polynomial $F$, denote the number of monomials by $N(F)$. Take for instance, \begin{align*}N(x(x+y)+(x+y)^2-(x-y)^2)=N(x^2+5xy)&=2 \qquad \text{and} \\
N((x+z)(x+y)^2)=N(x^3 ...
- 43.1k
3
votes
1
answer
295
views
Generating function for "descents" and "cycle-types", in tandem
This question is inspired but not directly related to this recent Stanley's MO post.
The descent set $D(w)$ of a permutation $w=a_1 a_2\cdots a_n\in\frak{S}_n$ (the symmetric group on $\{1,\dots,n\}$) ...
- 43.1k
9
votes
0
answers
409
views
Number of sets $S$ for which number of permutations in $S_n$ with descent set $S$ is odd
The descent set $D(w)$ of a permutation $w=a_1 a_2\cdots a_n\in\frak{S}_n$ is
defined by $D(w)=\{ 1\leq i\leq n-1\,:\, a_i>a_{i+1}\}$.
Given a set $S$, let
$\beta_n(S)$ denote the number of ...
- 50.8k
4
votes
1
answer
376
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 \...
- 1,889
2
votes
1
answer
199
views
Sequence of monotone tuples and permutation condition for rotation
I was doing some counting in $S_n$ symmetric group I encountered the following problem, which also someway related to central factorial number.
So given a $n$ cycle say $(1,2,\ldots,n)$, what are the ...
- 685
7
votes
0
answers
183
views
Explaining $\left(a-1\right)^n \cdot n! \mid a^{n-1} \prod_{i=1}^n \left(a^i-1\right)$ by a free $S_n$-action
Here is an olympiad-level problem on elementary number theory:
Let $a$ be an integer and $n$ a positive integer. Prove that
\begin{align}
\left(a-1\right)^n \cdot n! \mid a^{n-1} \prod_{i=1}^n \left(...
- 33.8k
18
votes
2
answers
991
views
A conjecture harmonic numbers
I will outlay a few observations applying to the harmonic numbers that may be interesting to prove (if it hasn't already been proven).
From the Online Encyclopedia of Positive Integers we have:
$a(n)$ ...
- 181
11
votes
5
answers
927
views
The number of ways to merge a permutation with itself
Let $\sigma$ be a permutation of $[k]=\{1,2, \dots , k\}$. Consider all the ordered triples $(\pi, s_{1},s_{2})$, such that $\pi$ is a permutation of length $2k-1$ that is a union of its two ...
- 109
10
votes
1
answer
357
views
Induction step in Bóna and Ehrenborg's proof that the generating function of the alternating runs has -1 as a root of a certain multiplicity
This is a crosspost of a question I asked on Mathematics SE four months ago. Periodically bumping it and placing a bounty on it to attract more attention were to no avail. There are some comments ...
user82537
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
1
answer
94
views
Calculating the values of a generalization of binomials to permutations
let $$\Pi\binom{n}{k}:=\mathrm{card}\left( \left\lbrace \lbrace \Pi_1^n\,\cdots\,\Pi_k^n\rbrace\,|\,0\leq \pi_{r,c}\in\sum_{i=1}^k\Pi_i^n\ni\pi_{r,c}\leq 1\right\rbrace\right)$$ be the number of sets ...
- 13.2k
2
votes
0
answers
166
views
Number of permutations with precedence constraints : DP case [closed]
I have two sets of balls (blacks and whites), each set is numbered from $1$ to $n$, and all are put in a jar. My precedence constraint is expressed as following : to pick a black ball with index $i$, ...
- 67
4
votes
1
answer
419
views
Enumerating all permutations that are "square roots" of derangements
Is there an algorithm that enumerates all permutations that are "square roots" of derangements, i.e. permutations that, when applied twice, yield a derangement?
Other information about those kind ...
- 13.2k
-2
votes
1
answer
108
views
Sum of: k permutations of n $\times e^x$
Simplify the following:
\begin{equation}
\sum\limits_{\ell =1}^n P(n,\ell) (e^x -1)^\ell
\end{equation}
to something like $n!n^n$. I got curious about this expression after going through this ...
- 37
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
1
answer
233
views
What does this permutation polynomial look like?
What is the number of terms of the unique multilinear polynomial $f\in\Bbb F_2[x_{1,1},\dots,x_{n,n}]$ in $n^2$ variables such that $f$ vanishes only on matrices that are permutations?
Are there good ...
- 13.9k
4
votes
0
answers
165
views
Counting "deflected" permutations: Part II
This is the second sequel to my earlier question on MO. Although the the current problem appears very similar, the answer is certainly different as experiments indicate.
As usual, let $\mathfrak{S}_n$...
- 43.1k
4
votes
1
answer
158
views
Counting "deflected" permutations: Part I
Let $\mathfrak{S}_n$ denote the group of permutations on $\{1,2,\dots,n\}$. Now, introduce the sets
$$\mathcal{A}_n^{(k)}:=\{\pi\in\mathfrak{S}_n: -1\leq \pi(j)-j\leq k,\,\forall j\}.$$
I would like ...
- 43.1k
4
votes
1
answer
140
views
Counting block-equivalent permutations
Consider the group $\mathfrak{S}_n$ of permutations on the letters $\{1,2,\dots,n\}$.
We say two permutations are b-equivalent, $\pi_1\,\pmb{\sim^b}\,\pi_2$, if one can be determined from the other ...
- 43.1k
12
votes
0
answers
642
views
Wilf's conjecture: complementary Bell numbers
The complementary Bell numbers or Uppuluri–Carpenter numbers, denoted $\tilde{B}_n$, can be delivered by
$$G(x):=\sum_{n\geq0}\tilde{B}_n\frac{x^n}{n!}=e^{1-e^x}.$$
Definition. Fix an integer $m\geq0$....
- 43.1k
5
votes
0
answers
175
views
A close cousin of involutions?
If $\mathfrak{S}_n$ denotes the permutation group on $n$ letters, then $Inv(n)=\{\pi: \pi^2=1\}\subset\mathfrak{S}_n$ is the set of involutions or
self-inverse permutations. The latter is enumerated ...
- 43.1k
3
votes
2
answers
543
views
Number of $\{0,1\}$ matrices with distinct rows and distinct columns
How many $M\in\{0,1\}^{r\times c}$ are there such that each row and each column of $M$ is distinct?
How many classes of matrices in $\{0,1\}^{r\times c}$ up to permutation equivalence are there such ...
user94040
9
votes
0
answers
275
views
pattern-avoiding permutations vs multi-core partitions
Let $\mathfrak{S}_n$ be the permutation group on $[n]$. Given the pattern $\sigma=k(k-1)\cdots321$, let $I_n(\sigma)$ be the number of involutions in $\mathfrak{S}_n$ that avoid the pattern $\sigma$. ...
- 43.1k
4
votes
1
answer
597
views
genus zero permutation and noncrossing partition
Question
Let $g$ to be an element of permutation group $S_n$, and $\tau = (1,2,3,\cdots,n)$ is the circular permutation. $g$ and $\tau g$ have $n+1$ cycles in total(fixed point is also a cycle), ...
- 165
8
votes
2
answers
540
views
Combinatorial proof of fact about Eulerian numbers?
Let $A(m,n)$ denote the Eulerian numbers.
I'm looking for a simple combinatorial proof of the following fact.
Fact. If $p$ is prime and $0\le k < p-1$, then $A(p-1,k) \equiv 1 \pmod{p}$.
The ...
- 82.6k
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
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
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
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.6k
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
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