Блог пользователя Another_Alt_123

Автор Another_Alt_123, история, 3 года назад, По-английски

Let U = {1, 2,...,n}, where n is a large positive integer greater than 1000. Let k be a positive integer less than n. Let A, B be subsets of U with |A| = |B| = k and A ∩ B = ∅. We say that a permutation of U separates A from B if one of the following is true.

  • All members of A appear in the permutation before any of the members of B.

  • All members of B appear in the permutation before any of the members of A.

How many permutations of U separate A from B?

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
3 года назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

$$$(n-2k+2)!$$$.

  • »
    »
    3 года назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    no it's definitely wrong. but i think you thought in the right direction

    • »
      »
      »
      3 года назад, скрыть # ^ |
      Rev. 7  
      Проголосовать: нравится +3 Проголосовать: не нравится

      Yes, I misread your problem. I only consider the case where $$$A$$$ and $$$B$$$ are continuous. The answer should be

      $$$2(n-2k)!k\sum\limits_{t=k}^{n-k} \frac{(t-1)!(n-t)!}{(t-k)!(n-t-k)!}$$$.

      Suppose $$$A$$$ is in front of $$$B$$$. You should multiply $$$2$$$ to the final answer.

      Suppose the last place of $$$A$$$ is $$$t$$$, where $$$k \le t \le n-k$$$. Then, we can choose $$$k-1$$$ places from the first $$$t-1$$$ places to settle $$$A$$$, which is $$$\binom{t-1}{k-1}$$$. And there are $$$k!$$$ ways to place $$$A$$$. For the first $$$t$$$ places, there are $$$t-k$$$ places that are not $$$A$$$. We can choose from $$$n-2k$$$ numbers to fill in these $$$t-k$$$ places because we cannot choose elements from $$$A$$$ as they have already been fixed, and we could not choose elements from $$$B$$$ because they should be placed after $$$A$$$. So there are $$$\binom{n-2k}{t-k}$$$ choices. The $$$t-k$$$ spare places in the range $$$[1, t]$$$ can be randomly placed, so you should multiply $$$(t-k)!$$$. Now, the first $$$t$$$ places are settled, so the set of elements in the last $$$n-t$$$ places are also settled, and they can be placed randomly, so there are $$$(n-t)!$$$ ways.

      In all, for each $$$t$$$ such that $$$k \leq t \leq n-k$$$ and $$$A$$$ is in front of $$$B$$$, there are

      $$$\binom{t-1}{k-1}\cdot k! \cdot \binom{n-2k}{t-k} \cdot {(t-k)!} \cdot {(n-t)!} = \frac{(n-2k)!k(t-1)!(n-t)!}{(t-k)!(n-t-k)!}$$$ ways.

      Check Code:

      Spoiler