4
$\begingroup$

Let $S$ be a set with $n$ elements and $\Sigma_k= \{ R\subseteq S \mid |R|=k \}$. For $k\le n/2$ how many bijections $f$ are there between $\Sigma_k$ and $\Sigma_{n-k}$, such that $x\subseteq f(x)$?

For $k=1$ clearly the answer is the number of derangements of order $n$. I'm really mostly curious about the case $n=2k+1$, and even then I would just be happy with some estimate or euristic for the answer. Are there "many" such maps, or only a "few"? I have no intuition whatsoever for this.

The question has surely been asked before, at the very least here, where a proof of Berlekamp is also given showing that the answer is not zero. (My original source for the card trick is actually the delightful Mathematical Puzzles: A Connoisseur's Collection of Peter Winkler.)

$\endgroup$
  • 1
    $\begingroup$ This estimate is probably very far from the real answer, but in the corresponding bipartite $(\Sigma_k,\Sigma_{k+1})$-graph (I consider the case $n=2k+1$) all vertices have degree $k+1$, thus it contains at least $(k+1)!$ perfect matchings (this is a general fact.) $\endgroup$ – Fedor Petrov Feb 14 '17 at 16:46
  • 2
    $\begingroup$ For $n=2k+1$ a lower bound is $\left(\frac{k^k}{(k+1)^{k-1}}\right)^n$. See homepages.cwi.nl/~lex/files/countpms2.pdf. $\endgroup$ – Richard Stanley Feb 14 '17 at 17:07
  • $\begingroup$ @RichardStanley: I don't completely follow - shouldn't the $n$ in the paper correspond to ${n}\choose{k}$, the size of $\Sigma_k$, here? $\endgroup$ – Yaakov Baruch Feb 14 '17 at 17:21
  • $\begingroup$ Both comments above are applicable to the general case, which can be regarded as a ${n-k}\choose{n-2k}$-regular bipartite graph with $2 {{n}\choose{k}}$ vertices. Thank you. $\endgroup$ – Yaakov Baruch Feb 14 '17 at 17:33
  • $\begingroup$ @YaakovBaruch: oops, you are right. This change just increases the lower bound. $\endgroup$ – Richard Stanley Feb 15 '17 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.