All Questions
3 questions
8
votes
1
answer
1k
views
Is there an efficient algorithm to check whether two matrices are the same up to row and column permutations?
Define $\mathcal M_n$ as the set of all $n\times n$ matrices with each entry either 1 or $x$. Two such matrices are equivalent iff they can be obtained from each other by swapping pairs of rows and ...
12
votes
2
answers
292
views
Permutation search problems with no known $o(n!)$ algorithms
I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one ...
4
votes
2
answers
2k
views
How to compute the rook polynomial of a Ferrers board?
Given a Ferrers board of shape $(b_1,\ldots,b_m)$, we define $r_k$ as number of ways to place $k$ non-attacking rooks (as in Chess). In section 2.4 of Stanley's Enumerative Combinatorics (vol. 1) it's ...