Search Results

No polynomial will suffice for $f$ since sets with the same moments up to order equal to the degree of $f$ are indistinguishable. To determine the set, moments of order up to the size of the set are …

It's unlikely that there is an exact answer simpler than the inclusion-exclusion sum. One can also use much the same calculations to show that the number of matched pairs adjacent to each other is asy …

An array of $k$ permutations of $n$ letters such that each pair are derangements of each other is a $k\times n$ Latin rectangle. …

These are mutual derangements. Equivalently, the rows of a latin rectangle. Probably other names have appeared.

That is, if $g,h$ are permutations, then $gh$ means "do $g$ then do $h$". Actions are usually written using exponential notation: $x^g$ is the image of $x$ under $g$. …

From (2), the numbers of permutations with 0 and 1 fixed points are the same to $O(1/n)$ relative error. … Combining this with (1) shows that the fraction of permutations with no fixed points is at least $\frac13-O(1/n)$. This is the switching method and it can be used in extremely many circumstances. …

Define a 0-1 matrix $A=(a_{ij})$ of order $n\times k$, where $a_{ij}=1$ iff $i\in S_j$. Then the task is to count the number of ways of choosing a 1 in each column so that the row sums are $b_1,\ldot …

$$\pmatrix{ 2&3&0&0\\0&2&3&0\\0&0&2&3\\3&0&0&2}$$ Every swap of two columns or swap of two rows decreases the trace. However, there is a permutation putting all the 3s on the diagonal.

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 …

Consider all permutations $\pi$ on the natural numbers such that for each $i$, $\pi(3i)=2i$ and $\lbrace \pi(3i+1),\pi(3i+2)\rbrace = \lbrace 4i+1,4i+3\rbrace$. …

Ilya correctly wrote in the comments that a clique cannot be larger than $n$, and also that size $n$ is not possible when $n$ is even (except $n=2$). Cliques of size exactly $n$ are studied under the …

It is a $k\times n$ latin rectangle: write the permutations one per row. This paper has a nice summary of theoretical and practical methods. …

There are also "pan-Hamiltonian" Latin squares, see Perfect Factorisations of Bipartite Graphs and Latin Squares Without Proper Subrectangles by I. M. Wanless, Electronic J. Combin. 6 (1999), R9.

This is OEIS sequence A181230. The square case $r=c$ is OEIS sequence A088310. See those pages for formulas. As Pat Devlin mentions, the asymptotic problem is trivial if both $r$ and $c$ increase qu …

This is more of a comment than a new answer because it uses no more technique than Joseph's answer. The expression of the problem in terms of graphs or 0-1 matrices is a red herring and I suggest a mo …