60
The mean number of fixed points is 1. This is very elementary.
Consider the operation of rotating three values around: $p(i)\to p(j)\to p(k)\to p(i)$. Given a permutation with no fixed points, there are $n^2-O(n)$ rotations that create from it a permutation with exactly one fixed point. Given a permutation with exactly one fixed point, there are $n^2-O(n)$ ...
40
Yes, $u$ must be a polynomial of degree $2$.
I had to draw on a few unexpected ingredients to prove this;
perhaps there's a simpler proof.
[EDIT Or maybe not: Peter Mueller's answer reports that
this was "an open problem on planar functions for many years",
and gives links to three independent papers c.1990 that independently
solved it. Two of them give ...
36
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.
$$
Upon writing $y_n = x_n$, $y_{n-1}=x_n+x_{n-1}$, etc this becomes
$$
\sum_{\pi \in {S_n} } n! \int_{y_1 \ge y_2 \ge \ldots y_n \ge 0} e^{-\sum_{i=1}^{n} \...
31
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 to show that $a_n>0$ for all $n\geq12$.
If $n$ is an odd, let $n=2m+1$, we have $m\geq6$, so by induction hypothesis, there exists $\pi\in S_m$ such that $\...
28
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. Brendle, W. Brian, J. D. Hamkins, M. Hardy, and P. B. Larson, The rearrangement number, manuscript under review.
Abstract. How many permutations of the natural ...
answered Aug 14 '15 at 13:33
Joel David Hamkins
178k27 gold badges527 silver badges922 bronze badges
27
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 (all balls have equal probability) and forbid all the balls from its basket. Repeat with $n-1$ remaining baskets and so on. What is the probability that we ...
23
The question was an open problem on planar functions for many years, which was settled independently in three papers around 1990. See the papers by Gluck, Ronyai and Szonyi, and Hiramine. Elkies' answer is similar to Gluck's proof. The proof by Hiramine avoids Segre's theorem, it is based on quite complicated computations instead.
23
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, and vice versa. Hence the number of permutations under the question is the square of the number of bijections from odds (from 3 to $n$) to evens satisfying the ...
23
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_{\sigma\in S_{n}}(-1)^{\ell(\sigma)}\left(\sum_{i=1}^n i^2\right)$ is zero. It remains to show that
$$\sum_{\sigma\in S_{n}}(-1)^{\ell(\sigma)}\sum_{i=1}^n i\sigma(...
22
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$.
22
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 vector $x$ and a vector space $V$ (the null-space of $A$), is there a permutation of $x$ that lies in $V$?
I'll take the number of components of $x$ to be $2n$....
21
I'm not sure this qualifies, but here goes.
It doesn't take any fancy enumerations to show that the average number of fixed points is 1: Among the $n!$ permutations of $n$ objects, each object is fixed by $(n-1)!$ permutations, for a total of $n!$ fixed points. So if the probability of having no fixed points tends to 0 (for some subsequence of $n$'s), ...
21
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 others) describes a simple algorithm to generate them with
$$m = n^2 -2n +4.$$
This is not, however, the best one. Radomirovic proves that the shortest ...
21
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 probability you ask for is $n!\, L(3,n)/L(2,n)^2$. The value of $L(2,n)$ is $n!$ times the number of derangements. The value of $L(3,n)$ doesn't have closed form ...
21
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 > n$, it follows that if $1 \le j \le n$ and $p_i$ divides $a + j$ then $i = j$. In particular, if $(x_1, \dots, x_n)$ lie in this range and $$\prod_{i=1}^n (a +...
20
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_\alpha=1$. All factorisations of the sporadic simple groups were determined by me in my paper 'Factorisations of sporadic simple groups' in the Journal of Algebra ...
20
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 \Pi_\sigma$ if and only if $\sigma(a)=b$. This is obviously a bijection between involutions and such set partitions; and the fixed points of $\sigma$ ...
18
Write a fair permutation in cycle form, as follows. First write all
cycles of length $>1$ in decreasing order of their smallest element,
with the smallest element of each cycle written as the leftmost
element of the cycle. Then append all the fixed points in increasing
order. An example is
$$ (3,9,4,6)(1,7,2,10)(5)(8). $$
Now erase the parentheses. We ...
17
L. Lu and L. A. Szekely have successfully applied the Lopsided (i.e. Negative Dependency Graph) Lovasz Local Lemma to this problem.
A negative dependency graph is as a dependency graph except that independence is replaced with the inequality
$$
\Pr\left(A_k \middle\vert \bigwedge_{i \in S} A_i\right) \leq \Pr(A_k)
$$
for any fixed event $A_k$ and collection ...
16
One technique which is very helpful in proving identities like this one is to express that expression as a coefficient in a generating function.
Consider the expression
$$\sum_{p\geq 2} \frac{(-1)^p}{p!}\binom{p}{2}\left(x+\frac{x^2}{2}+\frac{x^3}{3}+\cdots\right)^{p-2}\left(x^2+2x^3+3x^4+\cdots\right)$$
You can check that the coefficient of $x^n$ is ...
16
In my opinion, the most elegant proof is by Björner, Edelman and Ziegler (PDF file). They prove the following generalization: Let $\mathcal{H}$ be a finite set of hyperplanes in $\mathbb{R}^n$. Let $\mathcal{D}$ be the set of connected components of $\mathbb{R}^n \setminus \bigcup_{H \in \mathcal{H}} H$. Choose one region in $\mathcal{D}$; call it $D_0$....
16
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 this set $G$.
Levi answered a slightly different question, namely characterizing the permutations for which
if the left hand limit exists then so does the ...
16
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 represented uniquely as a polynomial $P_\psi (x) = \sum a_i x^i$ of degree less than $2^n$, with each $a_i \in F$. If the map $\psi$ is linear, then in fact $a_i =0$ ...
16
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)=f_{1,2,\dots,n}(\alpha) \ (=:\sum_{k=0}^n c_k\alpha^k)\quad\tag{1}$$
holds iff $x_1,...,x_n$ is a permutation of $1,2,...,n$.
Now, in order to answer the 1st ...
15
This determinant came up, and was evaluated, in the comments of the Secret Blogging Seminar. The motivation there was that it vanishes if and only if $V^{\otimes n}$ has neglible endomorphisms in Deligne's category of "$GL_x$ representations for noninteger $x$". Here $V$ is the "$x$-dimensional representation of $GL_x$". See that post for more.
15
I might as well turn my comment into an answer. From the Taylor expansion of the exponential function applied to $e^{-1}$, we have:
$$\frac{N!}{e} = \left( \sum_{k=0}^N (-1)^k \frac{N!}{k!} \right) + \left( \sum_{j=N+1}^\infty (-1)^j \frac{N!}{j!} \right)$$
where the first sum is an integer, and the second sum has absolute value between $\frac{1}{N+2}$ and $...
15
My initial answer was wrong. Instead of completely deleting it, I left it at the bottom of the post. I use notation now that slightly differ from my original post.
As before, I give only a partial answer related to the max eigenvalue question and the limsup. Recall that the tail estimates for the max eigenvalue is
$$(P(\lambda_1(n) >2\sqrt{n}+tn^{-1/6})\...
15
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:
Complete cycles are much easier to search for: cycleP[33, 2] (for $n=33,$ power$=2$, code below) produces
whereas cyclePall[23, 2] produces
and it is clear why ...
15
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 some error in the proof.)
14
I might as well write an answer with the proof I referenced to above (found as theorem 110 here). Hopefully Darij will write a more detailed answer tomorrow.
The first thing to observe is that your matrix $A$ is the image of the element
$$\omega=\sum_{\sigma\in S_n} x^{|\pi|}\pi$$
in the regular representation of the group algebra $\mathbb C[S(n)]$. Next ...
Only top voted, non community-wiki answers of a minimum length are eligible
