So for the specific case when
.
We have the set
To satisfy the condition, the
numbers must be adjacent and we can have either
, (3,1), (2,4), (4,2))
where
)
represents an adjacent pair.
To find those that satisfy
we need to find:
 \cup (3,1) \cup (2,4) \cup (4,2))
Using PIE we can find those that doesn't satisfy
 \cup (3,1) \cup (2,4) \cup (4,2)} = \overline{(1,3)} \cap \overline{(3,1)} \cap \overline{(2,4)} \cap \overline{(4,2)})
Let
} \cap \overline{(3,1)} \cap \overline{(2,4)} \cap \overline{(4,2)}|)
Defining an indicator function
)
where
, (3,1), (2,4), (4,2)\})
with domain
such that
contains all sets
 = \begin{cases} 0, & \mbox{if} \ \mbox{x} \ \notin \ \mbox{y} \\ 1, & \mbox{if} \ \mbox{x} \ \in \ \mbox{y} \end{cases})
}}(x) I_{\overline{(3,1)}}(x)I_{\overline{(2,4)}}(x)I_{\overline{(4,2)}}(x))
}(x))(1-I_{(3,1)}(x))(1-I_{(2,4)}(x))(1-I_{(4,2)}(x)))
}(x)+I_{(3,1)}(x)+I_{(2,4)}(x)+I_{(4,2)}(x)+\sum_{x \in \mathbb{U}} I_{(1,3)}(x)I_{(3,1)}(x) + I_{(1,3)}(x)I_{(2,4)}(x)+I_{(1,3)}(x)I_{(4,2)}(x) + I_{(3,1)}(x)I_{(2,4)}(x) +I_{(3,1)}(x)I_{(4,2)}(x)+I_{(2,4)}(x)I_{(4,2)}(x))
}(x)I_{(3,1)}(x)I_{(2,4)}(x)+I_{(1,3)}(x)I_{(2,4)}(x)I_{(4,2)}(x)+I_{(3,1)}(x)I_{(2,4)}(x)I_{(4,2)}(x)+I_{(1,3)}(x)I_{(3,1)}(x)I_{(4,2)}(x) + \sum_{x \in \mathbb{U}}I_{(1,3)}(x)I_{(3,1)}(x)I_{(2,4)}(x)I_{(4,2)}(x))
Now to work out the cardinality of each consider the set
, (3,1)\})
and
, (4,2)\})
The first sum is obvious:
The second sum is also pretty obvious:
}(x)+I_{(3,1)}(x)+I_{(2,4)}(x)+I_{(4,2)}(x) = 4!)
The third sum is not so obvious since we have terms that equal
, eg,
}(x)I_{(3,1)}(x) = 0)
.
Thus we need to pick any
pairs from the 1st set and any
pairs from the 2nd set.
So there are
non-zero pairs. Each pair however has 2 ways to rearrange. So the third sum equals
The fourth sum is
since we need
sets but we only have
to pick from.
The fifth sum is also
by the same argument as above.
Now we can generalise.
Consider the set
Let
, (1+n,1), (2,2+n), (2+n,2), \cdots, (n,2n),(2n,n))
represent the adjacent pairs. There are a total of
pairs.
To find those that satisfy
we need to find
 \cup (1+n,1) \cup (2,2+n) \cup (2+n,2) \cup \cdots \cup (n,2n) \cup (2n,n))
Using PIE we can find the complement of
:
 \cup (1+n,1) \cup (2,2+n) \cup (2+n,2) \cup \cdots \cup (n,2n) \cup (2n,n)} = \overline{(1,1+n)} \cap \overline{(1+n,1)} \cap \overline{(2,2+n)} \cap \overline{(2+n,2)} \cap \cdots \cap \overline{(n,2n)} \cap \overline{(2n,n)})
Let
} \cap \overline{(1+n,1)} \cap \overline{(2,2+n)} \cap \overline{(2+n,2)} \cap \cdots \cap \overline{(n,2n)} \cap \overline{(2n,n)}|)
Now we define an indicator function
where
, (1+n,1), (2,2+n), (2+n,2), \cdots, (n,2n),(2n,n)\})
}(x))(1-I_{(1+n,1)}(x))(1-I_{(2,2+n)}(x))(1-I_{(2+n,2)}(x)) \cdots (1-I_{(n,2n)}(x))(1-I_{(2n,n)}(x)))
}(x)+I_{(1+n,1)}(x)+ \cdots + I_{(n,2n)}(x) + I_{(2n,n)}(x) + \sum_{x \in \mathbb{U}} I_{(1,1+n)}(x)I_{(1+n,1)}(x)+I_{(1,1+n)}(x)I_{(2,2+n)}(x)+ \cdots + I_{(1+n,n)}(x)I_{(2n,n)}(x) \cdots - \sum_{x \in \mathbb{U}}I_{(1,1+n)}(x)I_{(1+n,1)}(x)I_{(2,2+n)}(x) \cdots)
}(x))(I_{(1+n,1)}(x))(I_{(2,2+n)}(x))(I_{(2+n,2)}(x)) \cdots (I_{(n,2n)}(x))(I_{(2n,n)}(x)))
The first sum equals
!)
The second sum equals
!)
The third sum is a bit tricky since some pairs equal
, thus consider all the different pairs placed into sets like this:
, (1+n,1)\}, \{(2,2+n), (2+n,2)\}, \{(3,3+n), (3+n,n)\}, \cdots, \{(n,2n), (2n,n)\})
We need
pairs, since there are
sets, we need to pick
sets first
. But each set contains
terms, thus we can have
different pairings for each
sets.
Therefore this sum equals
!)
The fourth sum is equal to
!)
The fifth sum is equal to
!)
.
.
.
The last sum is equal to
!)
In total we have
!-(2n)! + 2^2\binom{n}{2}(2n-2)! - 2^3\binom{n}{3}(2n-3)! + 2^4\binom{n}{4}(2n-4)! - \cdots + 2^{2n}\binom{n}{2n}(2n-2n)!)
^{i}2^i\binom{n}{i}(2n-i)!)
So that means there are a total of
sets which does not satisfy
.
Now we just have to prove that the number of sets that satisfy
is larger than those that don't.
The number of sets that satisfies
is equal to
!-Q_n)
.
So we need to prove
!-Q_n > Q_n)
! > 2Q_n)
First let
represent
^{i}2^i\binom{n}{i}(2n-i)!|)
We see that
^{2}2^3\binom{n}{2}(2n-2)! = (2^2)\left(\frac{n!}{(n-2)!2!}\right)(2n-2)! = (2^3)\left(\frac{n(n-1)}{2}\right)(2n-2)! = 2n(2n-2)(2n-2)!)
But
! = (2n)(2n-1)(2n-2)!)
(2n-1)(2n-2)! > 2n(2n-2)(2n-2)!)
! > 2t_2)
Next take
and
for example.
means at least 3 pairs satisfy
and
means at least
pairs satisfy
.
But at least 4 pairs is a subset of at least 3 pairs which means
Generalising this leads to
So
 + \cdots 2(t_{2n} - t_{2n-1}))
, \cdots, (t_{2n}-t_{2n-1})\} \le 0 )
 + \cdots 2(t_{2n} - t_{2n-1}) \le 2t_2 < (2n)!)
!)
fuck yeah good job guys
Home
Help
Search
Login
