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.)

Improve this question
$\endgroup$
6
  • 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
    Commented Feb 14, 2017 at 16:46
  • 3
    $\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
    Commented Feb 14, 2017 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
    Commented Feb 14, 2017 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
    Commented Feb 14, 2017 at 17:33
  • $\begingroup$ @YaakovBaruch: oops, you are right. This change just increases the lower bound. $\endgroup$
    – Richard Stanley
    Commented Feb 15, 2017 at 15:08

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .