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 ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
  • 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_{\...
user avatar
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 ...
user avatar
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$.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 >...
user avatar
  • 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_\...
user avatar
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 ...
user avatar
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)=...
user avatar
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: ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
  • 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 $\...
user avatar
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 ...
user avatar
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 $\...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
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). ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible