45
votes
Accepted
Why 'excedances' of permutations?
Mea culpa. Comtet used the term excédence. When writing EC1 I needed an English term for this concept. For some reason I didn't like the word exceedance. I thought it looked better without the double ...
- 43.8k
41
votes
Accepted
Multiplying all the elements in a group
Yes, your $G!$ (as a set) is always either $[G,G]$ (if the order of $G$ is odd, or its Sylow $2$-subgroup is non-cyclic) or $z[G,G]$ if $G$ has cyclic Sylow $2$-subgroup, where $z$ is the involution ...
- 1,837
36
votes
Accepted
Sum over permutations is 1
Yes. Write the sum as
$$
\sum_{\pi \in S_n} n! \int_0^{\infty} e^{-\pi(1) x_1} \int_{0}^{\infty} e^{-(\pi(1)+\pi(2)) x_2} \ldots \int_0^{\infty} e^{-(\pi(1) + \ldots +\pi(n))x_n} dx_n \ldots dx_1.
...
- 42.4k
33
votes
Permutations $\pi\in S_n$ with $\sum_{k=1}^n\frac1{k+\pi(k)}=1$
Claim: $a_n>0$ for all $n\geq 6\quad (*)$.
Proof: We use induction to prove $(*)$.
We have $a_6,a_7,a_8,a_9,a_{10},a_{11}>0$. Assume $(*)$ holds for all the integers $\in [6,n-1]$. We want ...
- 331
31
votes
Accepted
How many rearrangements must fail to alter the value of a sum before you conclude that none do?
Update. A research collaboration growing out of this question and some of its answers has now resulted in the following article, providing an account of the rearrangement number:
A. Blass, J. ...
- 195k
28
votes
Sum over permutations is 1
Here is a probabilistic, or, if you wish, combinatorial proof. Assume that we have $n$ baskets containing $z_1,\dots,z_n$ balls respectively (well, let them be positive integers). Choose a random ball ...
- 88.5k
25
votes
A mysterious connection between primes and squares
The fact on squareness is easy.
If $n$ is odd, among the sums of the form $i^4+\tau_i^4$ there is an even one; it should equal to 2, hence $\tau_1=1$. All other odd numbers should map to even ones, ...
- 18.9k
25
votes
Accepted
Fraction of $S_n$ reachable by using every transposition once as $n\to\infty$?
The value is $1/2$.
The problem can be reformulated as follows: How to sort a non-sorted list $(a_1,...,a_n)$ that is a permutation of $\{1 .. .n\}$ with the parity the same as $n \choose 2$ by ...
- 8,174
23
votes
Accepted
A cancellation property for permutations?
Let $n$ be some integer greater than 2. Since the number of even and odd permutations in $S_n$ is the same we have $\sum_{\sigma\in S_{n}}(-1)^{\ell(\sigma)}=0$ therefore the contribution of $\sum_{\...
- 82.1k
22
votes
Accepted
Shortest supersequence of all permutations of $n$ elements
This seems to be an open problem. It is listed in the OEIS as sequence A062714, as noted by Ilya. Summarising the most important results:
Let $m$ be the length of such a sequence. Then Newey (amongst ...
- 33.7k
22
votes
Sum over permutations is 1
Purely algebraic proof. We induct on $n$. Fix $\pi_n$. This part of the sum equals $z_{\pi_n}/(z_1+\dots+z_n)$ by induction proposition. Now sum up by all values of $\pi_n$.
- 88.5k
22
votes
Accepted
Determining if some permutation of a vector satisfies a system of linear equations
Let's see if I can convince everyone that this problem is NP-complete.
First: it is in NP because a permutation $P$ can be guessed and checked in polynomial time.
I'll restate the problem: Given a ...
- 34k
21
votes
Rearrangements that never change the value of a sum
For the purpose of recording an answer rather than just a pile of links: Michael Hardy requires that
if either limit exists then so does the other and in that case then they are equal?
Let's call ...
21
votes
Composition of Derangements
An array of $k$ permutations of $n$ letters such that each pair are derangements of each other is a $k\times n$ Latin rectangle. If $L(k,n)$ is the number of $k\times n$ Latin rectangles, then the ...
- 34k
21
votes
A necessary and sufficient condition for $(x_1,...,x_n)$ to be a permutation of $(1,...,n)$
Let $p_1, \dots, p_n$ be distinct prime numbers each greater than $n$. By the Chinese remainder theorem, there exists an $a$ such that $a + i$ is divisible by $p_i$ for $1 \le i \le n$. Since $p_i >...
- 1,342
20
votes
Can all the sporadic groups be expressed as permutation groups based on a single big cycle?
If a permutation group $G$ on a set of size $n$ contains an $n$-cycle then the subgroup $C$ generated by this $n$-cycle is transitive. Thus we have a factorisation $G=CG_\alpha$. Moreover, $C\cap G_\...
- 1,873
20
votes
Accepted
trace and involution permutations: Part I
Let us identify an involution $\sigma$ in $\mathfrak{S}_n$ with a set partition $\Pi_\sigma$ of $[n] := \{1,2,...,n\}$ into nonempty blocks of size at most two in the obvious way: we have $\{a,b\} \in ...
- 19k
17
votes
A necessary and sufficient condition for $(x_1,...,x_n)$ to be a permutation of $(1,...,n)$
Start by thinking about $\prod_{k=1}^n (x_k+\alpha)$ as the polynomial $f_{x_1,\dots,x_n}(\alpha)$ in $a$ with roots at $-x_1$,...,$-x_n$. Then the equality of polynomials
$$f_{x_1,\dots,x_n}(\alpha)=...
- 12.9k
16
votes
Arranging numbers from $1$ to $n$ such that the sum of every two adjacent numbers is a perfect power
Not an answer, but maybe a start:
It is fairly clear why trivial cases like $n=18,$ power$=2$ don't work, after all of the sum-pairs $\neq$ a power of $2$ that are $\leq2n$ are stripped away:
...
- 1,801
16
votes
Accepted
Linear permutations commuting with $x\rightarrow x^{-1}$
The answer is no: a linear transformation of $F$ which commutes with $\phi$ is an automorphism of $F$.
This is a seemingly inelegant but simple argument.
Any map $\psi: F \rightarrow F$ can be ...
- 4,661
15
votes
Is the Number of Carries in Integer-Addition Associative?
For any base $b$, if we add $a$ and $c$ with $k$ carries, then $S_b(a+c)=S_b(a)+S_b(c)-(b-1)k$, where $S_b$ denotes the sum of digits. Since the resulting sum is independent of the order of addition, ...
- 18.9k
15
votes
Accepted
Is $(\mathbb{R},+)$ isomorphic to a subgroup of $S_\omega$?
See Theorem 4.3 of this paper by De Bruijn. Any abelian group of order $2^\kappa$ can be embedded in $Sym(\kappa)$ when $\kappa$ is infinite. (There is also an addendum to the paper which corrects ...
- 2,925
15
votes
A conjecture harmonic numbers
We can use the characterization by Christie. Let $\pi \in S_n$. Add a fixed point $0$ to $\pi$, and let $c$ be the cycle $(0, 1, \ldots, n)$. Then the smallest number of block interchanges to sort $\...
- 5,141
15
votes
Accepted
Two questions on the permutohedron
The number of integer points in $P_n$ is the number of forests on $[n]$; see Section 3 of Stanley's Decompositions of rational convex polytopes. In fact you can see there a simple description of its ...
- 19k
14
votes
Accepted
Rank of $A\otimes B - B\otimes A$
For generic $A,B$ the matrix $A$ is invertible and $B=CA$, where $C$ is also generic. We have $(A\otimes B-B\otimes A)(u\otimes v)=Au\otimes CAv-CAu\otimes Av$. The vectors $Au$ run over the whole $\...
- 88.5k
14
votes
Accepted
Constructing permutations avoiding a pattern
As far as "combining pattern foo and bar makes the set empty for large $n$", there is an answer and it is fairly trivial. There are no permutations of length longer than $(k-1)(\ell-1)+1$ ...
- 2,251
13
votes
Permutations with all cycles odd length and permutations with all cycles even length
Here is Eytan's proof in more detail. First, there is a canonical way to write the cycle decomposition of a permutation. You order the cycles in descending order based on the largest member they ...
- 107k
13
votes
How many rearrangements must fail to alter the value of a sum before you conclude that none do?
This is really a comment on Joel's answer, but apparently too long. Let P be the forcing which adds a permutation of $\mathbb{N}$ by finite pieces (so $P$ is forcing-equivalent to Cohen forcing). ...
- 2,430
13
votes
Can all the sporadic groups be expressed as permutation groups based on a single big cycle?
This already fails for the second-smallest sporadic group $M_{12}$.
A simple subgroup $G$ of $S_N$ cannot contain an $n$-cycle with $n$ even
(unless $|G|=2$...),
because then $G \cap A_N$ would be an ...
- 71.6k
12
votes
Arranging numbers from $1$ to $n$ such that the sum of every two adjacent numbers is a perfect power
This is a to long for a comment:
Let $G(n,N)$ Micah's graph with vertices the numbers $1,..,n$ and edges $\{i,j\}$ if $i+j$ is a power of $N$. Your condition is satisfied if and only if $G$ contains ...
- 10.2k
Only top scored, non community-wiki answers of a minimum length are eligible