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

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

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
  • Проголосовать: не нравится

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

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

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

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

    • »
      »
      »
      21 месяц назад, # ^ |
      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
      • »
        »
        »
        »
        21 месяц назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        you are so smart sir, it's so hard for me to even understand like how to proceed solving this problem. i have also found this formula

        $$$ 2* nC2k* (n − 2k)! (k!)2 $$$

        but it's really confusing i just don't understand why are we multiplying it by 2 can you please help me understand this. what's the need for multiplying the answer by 2. and also if you have time to explain it then please explain the whole formula.

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

          Sorry, I don't understand this Latex. Would you please explain it?

          • »
            »
            »
            »
            »
            »
            21 месяц назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            So, There are n number and we are choosing 2k ( k numbers for A and k numbers for B) from them. That means we choose $$${n \choose 2k}$$$ and there are $$$k!$$$ permutations of A and $$$k!$$$ permutations B. And there $$$(n-2k)!$$$ permutations of the remaining numbers. So there will be a total of $$${n \choose 2k}*(k!)*(k!)*(n-2k)!$$$ permutations. And B can come infront of A so we will multiply it by 2. So the answer becomes $$$2*{n \choose 2k}*(k!)*(k!)*(n-2k)!$$$.

            This is how i understand the problem and i want you to tell me if this is correct way to solve this problem or not. Sorry for my bad English.