Another_Alt_123's blog

By Another_Alt_123, history, 21 month(s) ago, In English

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?

  • Vote: I like it
  • -7
  • Vote: I do not like it

| Write comment?
»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 7   Vote: I like it +3 Vote: I do not like it

      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 month(s) ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        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 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              It is correct, I modify my checker and validate it. I also check your math formula.