Explore Discrete Math Examples

The domain for the function $A,B\subseteq X$, $AfB⟺<!--\; ⟺\; -->A\cup B=X$ and $A\cap <!--\; \cap \; -->B=\varnothing$

How many ways can you pick exactly the same 4 people from a group of 20
The question is what is the probability that Barbara, Carl, Georg, and Henrietta are randomly chosen from a set of twenty clients for a four-person group date if all possible choices are equally likely?
I know the formula is P = Favorable outcomes / possible outcomes. For whatever reason I am not sure how to get the numerator. The possible outcomes is $(\genfrac{}{}{0ex}{}{20}{4})$, but the numerator is alluding me. It is not a multiplication rule because it doesn't allow for repeating, it can't be a permutation because order doesn't matter, leaving a combination I think. but then I did $(\genfrac{}{}{0ex}{}{20}{4})$.
I got $\frac{116280}{4845}$, which is a number larger than 1.
What method am I missing? How do I get the number of ways I can exactly pick the Barbara, Carl, Georg, and Henrietta?

Induction proof on a sequence
A sequence $a_0,a_1,\dots <!--\; \dots \; -->$ is defined by letting $a_0=a_1=1$ and $a_k=a_{k-<!--\; -\; -->1}+2a_{k-<!--\; -\; -->2}$ for all integers $k>1$. Prove that for all integers $k\ge <!--\; \ge \; -->0$, $a_k=\frac{2^{k+1}+(-<!--\; -\; -->1{)}^k}{3}$.
Base case: S(2)
Let $k=2$. Then $a_2=\frac{2^{2+1}+(-<!--\; -\; -->1{)}^2}{3}=\frac{9}{3}=3$.
S(3)
Let $k=3$. Then $a_3=\frac{2^{3+1}+(-<!--\; -\; -->1{)}^3}{3}=\frac{15}{3}=5$
Base is true.
Induction step: Assume S(k) and $S(k-<!--\; -\; -->1)$ are true. Then
$S(k)=a_k=\frac{2^{k+1}+(-<!--\; -\; -->1{)}^k}{3}$
and $S(k-<!--\; -\; -->1)=a_{k+1}=\frac{2^k+(-<!--\; -\; -->1{)}^{k-<!--\; -\; -->1}}{3}$
Since $S(k)=a_k$ and $S(k-<!--\; -\; -->1)=a_{k-<!--\; -\; -->1}$, by definition $S(k+1)=S(k)+2\cdot <!--\; \cdot \; -->S(k-<!--\; -\; -->1)$.
$\frac{2^{k+2}+(-<!--\; -\; -->1{)}^{k+1}}{3}=\frac{2^{k+1}+(-<!--\; -\; -->1{)}^k}{3}+2\cdot <!--\; \cdot \; -->\frac{2^k+(-<!--\; -\; -->1{)}^{k-<!--\; -\; -->1}}{3}$
Solving this should lead to that
$k=-<!--\; -\; -->2$
Therefore $S(k+1)$ is true.
I think I've got the right idea but I'm not completely sure that I've done this correctly. Any help or suggestions are much appreciated!

Clustering data using mixed integer linear programming
I am trying to understand if it is possible to use mixed integer linear programming (MILP) in order to perform a basic clustering operation to a dataset D. I know there exists standard algorithms for it but I am particularly interested in MILP.
Assume one has the dataset $D=D_1\cup <!--\; \cup \; -->D_2$ with:
$$\begin{gathered} D_1=[1,2,2,3,4,3,1,0,2,2,1] \\ {D}_2=[7,6,5,8,7,7,4,7,9,8,6] \end{gathered}$$
Is there some MILP algorithm that can cluster the concatenated and shuffled data SD, with S some permutation acting on D, which can cluster each element of D to either $D_1$ or $D_2$?

What do the parenthesis mean in the set builder notation $\{(x,S)\mid <!--\; \mid \; -->x\in <!--\; \in \; -->S,S\in <!--\; \in \; -->2^A\}$
I've looked around but can't quite figure out what the set produced by the builder notation in the title would actually look like - specifically, what element does (x,S) actually yield? If someone could explain what the output of the statement would look like I would really appreciate it, thank you.

Determine the maximum collection of edge-disjoint xy-paths in $Q_n$
Let x be the vertex of all zeros and y be the vertex of all ones in the hypercube graph $Q_n$. We have to determine the maximum collection of edge-disjoint xy-paths in $Q_n$ and a minimum vertex cut of $Q_n$ separating x and y.
My work: We define a xy-path $P_i$ as follows:
Start from the vertex x and change the $i^{th}$ bit to 1 and then change all bits gradually one by one moving leftward from $i-<!--\; -\; -->1$ to 1 to n and back to i.
Note that all paths $P_i$ are edge-disjoint. Thus we have a maximum collection.
By Menger's Theorem, the second part follows.

Coin-weighting problem
Let n coins of weights 0 and 1 be given. We are also given a scale with which we may weigh any subset of the coins. The information from previous weighting may be used. The object is to determine the weights of the coins with the minimal number of weightings. Formally, a collection $S_1,\dots <!--\; \dots \; -->,S_m$ subsets of $\{1,\dots <!--\; \dots \; -->,n\}$ is called determing if any $T\subseteq <!--\; \subseteq \; -->\{1,\dots <!--\; \dots \; -->,n\}$ can be uniquely determined by the cardinalities $|S_i\cap <!--\; \cap \; -->T|$ for $1\le <!--\; \le \; -->i\le <!--\; \le \; -->m.$. Let D(n) be the minimum m for which such a determing collection exists. Show that $D(n)\ge <!--\; \ge \; -->\frac{n}{{\log }_2<!--\; \; -->(n+1)}$.
Let $S_1,\dots <!--\; \dots \; -->,S_m$ be an arbitrary determining collection. Also, assume that T be an arbitrary subset of $\{1,\dots <!--\; \dots \; -->,n\}$. Then there are $2^n$ possibilities to choose T from $\{1,\dots <!--\; \dots \; -->,n\}$. On the other hand, for each $1\le <!--\; \le \; -->i\le <!--\; \le \; -->m$, there are only $n+1$ possible $|S_i\cap <!--\; \cap \; -->T|$ because $0\le <!--\; \le \; -->|S_i\cap <!--\; \cap \; -->T|\le <!--\; \le \; -->|S_i|\le <!--\; \le \; -->n$. But now I don't know how to apply the pigeonhole principle. This principle says that: if a set A consisting of at least $rs+1$ objects is partitioned into r classes, then some class receives at least $s+1$ objects. Equivalently, if $A=\underset{i=1}{\overset{r}{\bigcup <!--\; \bigcup \; -->}}{B}_i$ (disjoint union) and $|B_i|\le <!--\; \le \; -->s$ for every $1\le <!--\; \le \; -->i\le <!--\; \le \; -->r$, then $|A|\le <!--\; \le \; -->rs$. I can't use this principle in my answer. How can I introduce A and $B_i^{{}^{\prime }}s$ here? I was wondering if someone could help me about it.

We arrange 12-letter words having at our disposal five letters a, four letters b and three letters c. How many words are there without any block $5\times <!--\; \times \; -->a$, $4\times <!--\; \times \; -->b$ and $3\times <!--\; \times \; -->c$. I need to use inclusion - exclusion principle. I counted all possible 12 letter words - $\frac{12!}{5!4!3!}$. Then words with block of letters:
only a blocks - $8\cdot <!--\; \cdot \; -->\frac{7!}{4!3!}$
only b blocks - $9\cdot <!--\; \cdot \; -->\frac{8!}{5!3!}$
only c blocks - $10\cdot <!--\; \cdot \; -->\frac{9!}{5!4!}$.
Now I have to count all words, where block: a, b or a, c, or b, c appears together, but I don't now how.

Is this set countably infinite? If so, how do I exhibit a one to one correspondence between these two sets?
I am supposed to determine whether or not the set $A\times <!--\; \times \; -->Z^{+}$ where $A=\{2,3\}$ is countably infinite. If so, I should exhibit a one to one correspondence between the set of positive integers and the set in question.
Although I'm pretty sure that the set is countably infinite, I am struggling to find a one to one correspondence from the positive integers to the set since it seems to me that there are twice as many elements in the set $A\times <!--\; \times \; -->Z^{+}$ than the set of positive integers since its cardinality is double due to the Cartesian product?

Construct partition such that sum of chromatic numbers is greater than chromatic number of graph
Show that for any undirected non-complete graph G there is a partition $V(G)=V_1\bigsqcup <!--\; \bigsqcup \; -->V_2$ such that $\mathrm{\chi <!--\; \chi \; -->}(G[V_1])+\mathrm{\chi <!--\; \chi \; -->}(G[V_2])>\mathrm{\chi <!--\; \chi \; -->}(G)$
I managed to show that we can assume that every vertex x with non-full degree has degree atleast $\mathrm{\chi <!--\; \chi \; -->}(G)-<!--\; -\; -->1$ (otherwise, we may take $V_1=\{x\}$ and consider its neighbors), but then I get stuck. I also considered doing induction by taking the "almost-complete" non-complete graph (i.e. a complete graph with one edge removed) and removing edges, but I'm not sure what to do in the induction step. Any help would be appreciated.

Let $A_1$, $A_2$, P be CPOs and let $\mathrm{\psi <!--\; \psi \; -->}:A_1\times <!--\; \times \; -->A_2\to <!--\; \to \; -->P$ be a map, then $\mathrm{\psi <!--\; \psi \; -->}$ is continuous $⟺<!--\; ⟺\; -->$ it is so in each variable separately
Proving this $\Rightarrow <!--\; \Rightarrow \; -->$ direction is quite easy, but I am not sure how to conclude the opposite $\Leftarrow <!--\; \Leftarrow \; -->$ direction:
If $\bigvee <!--\; \bigvee \; -->D=(d_1,d_2)=\bigvee <!--\; \bigvee \; -->(D_1\times <!--\; \times \; -->D_2)$ , we have:
$\mathrm{\psi <!--\; \psi \; -->}(\bigvee <!--\; \bigvee \; -->D)=\mathrm{\psi <!--\; \psi \; -->}(d_1,d_2)={\mathrm{\psi <!--\; \psi \; -->}}^{d_1}(d_2)={\mathrm{\psi <!--\; \psi \; -->}}_{d_2}(d_1)$ , where
${\mathrm{\psi <!--\; \psi \; -->}}^{d_1}(d_2)={\mathrm{\psi <!--\; \psi \; -->}}^{\bigvee <!--\; \bigvee \; -->D_1}(\bigvee <!--\; \bigvee \; -->D_2)=\bigvee <!--\; \bigvee \; -->{\mathrm{\psi <!--\; \psi \; -->}}^{\bigvee <!--\; \bigvee \; -->D_1}(D_2)=\bigvee <!--\; \bigvee \; -->\mathrm{\psi <!--\; \psi \; -->}(\{\bigvee <!--\; \bigvee \; -->D_1\}\times <!--\; \times \; -->D_2)$
and, similarly,
${\mathrm{\psi <!--\; \psi \; -->}}_{d_2}(d_1)={\mathrm{\psi <!--\; \psi \; -->}}_{\bigvee <!--\; \bigvee \; -->D_2}(\bigvee <!--\; \bigvee \; -->D_1)=\bigvee <!--\; \bigvee \; -->{\mathrm{\psi <!--\; \psi \; -->}}_{\bigvee <!--\; \bigvee \; -->D_2}(D_1)=\bigvee <!--\; \bigvee \; -->\mathrm{\psi <!--\; \psi \; -->}(D_1\times <!--\; \times \; -->\{\bigvee <!--\; \bigvee \; -->D_2\})$
how to conclude that $\mathrm{\psi <!--\; \psi \; -->}(\bigvee <!--\; \bigvee \; -->D)=\bigvee <!--\; \bigvee \; -->\mathrm{\psi <!--\; \psi \; -->}(D)$ ?

Set equality using distributive property
$(A\setminus <!--\; \setminus \; -->B)\cap <!--\; \cap \; -->C=(A\cap <!--\; \cap \; -->C)\setminus <!--\; \setminus \; -->B$

Philosophy of adding extra term in combinatorics question
If $x_1+x_2+x_3+x_4\le <!--\; \le \; -->20$ where $x_1,x_2,x_3,x_4$ are non negative integers , then how many possible outcome are there ?
It is basic counting problem, we solve it by adding an extra non-negative integer such that $x_1+x_2+x_3+x_4+x_5=20$, and then use star and bars . Hence the answer is $(\genfrac{}{}{0ex}{}{20+5-<!--\; -\; -->1}{20})$.
However , there is something that stuck in my mind such that why are we adding only one extra variable $x_5$, to be clearer , why dont we add more than one extra variable. For example , why did not i find the solution of $x_1+x_2+x_3+x_4+x_5+x_6=20$ where the extra terms $x_5$ and $x_6$ are non-negative, too. Briefly, why did we restrict ourselved with only one extra variable? Can you enlighten me ?

How to prove this equation using mathematical induction?
I need to prove the equation
$\frac{1}{3}=\frac{1+3+5+\cdots <!--\; \cdots \; -->+(2n-<!--\; -\; -->1)}{(2n+1)+(2n+3)+\cdots <!--\; \cdots \; -->+(2n+(2n-<!--\; -\; -->1))}$ using mathematical induction.
I tried solving this but I got stuck. I would be very thankful is someone could help me. Or maybe give me a references or hint.
My Attempt:
- For $n=1$
$\frac{1}{3}=\frac{1}{2n+1}$
$\frac{1}{3}=\frac{1}{2+1}$
$\frac{1}{3}=\frac{1}{3}$ which is true.
- For $n=k$
$\frac{1}{3}=\frac{1+3+5+\cdots <!--\; \cdots \; -->+(2k-<!--\; -\; -->1)}{(2k+1)+(2k+3)+\cdots <!--\; \cdots \; -->+(2k+(2k-<!--\; -\; -->1))}$
- For $n=k+1$
$\frac{1}{3}=\frac{1+3+5+\cdots <!--\; \cdots \; -->+(2k-<!--\; -\; -->1)+(2k+1-<!--\; -\; -->1)}{(2k+1)+(2k+3)+\cdots <!--\; \cdots \; -->+(2k+(2k-<!--\; -\; -->1))}$

Let x be a positive integer. Show that if x is a perfect square, then then $7x^4+4x^2+x+3$ cannot be a perfect square.

Binomial coefficient inequality equation proofs
Prove the statement:
If n is a positive integer, then $1=(\genfrac{}{}{0ex}{}{n}{0})<(\genfrac{}{}{0ex}{}{n}{1})<...<(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })=(\genfrac{}{}{0ex}{}{n}{\lceil n/2\rceil })>...>(\genfrac{}{}{0ex}{}{n}{n-1})>(\genfrac{}{}{0ex}{}{n}{n})=1$
I tried to read up the falling/rising factorial notation from internet sources, but I cannot find how to write up the first step.
The options are as follows (We have to put it in the right order, one option is incorrect):
- If $k<=n/2$, then $k/(n—k+1)$, so the "greater than" signs are correct. Similarly, if $k>n/2$, then $k/(n-<!--\; -\; -->k+1)$, so the "less than" signs are correct.
- If $k<=n/2$, then $k/(n—k+1)$, so the "less than" signs are correct. Similarly, if $k>n/2$, then $k/(n-<!--\; -\; -->k+1)$, so the "greater than" signs are correct.
- Since $\lfloor n/2\rfloor +\lceil n/2\rceil =n$, the equalities at the ends are clear.
- The equalities at the ends are clear. Using the factorial formulae for computing binomial coefficients, we see that $C(n,k—1)=(k/(n-<!--\; -\; -->k+1))C(n,k)$
If we consider a sample k as $k=2...k=5$ and we consider $n=7$.
Then $(\genfrac{}{}{0ex}{}{n}{3})=(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })$ because the floor value of n/2 is 3. But the same holds good on the right side of the equation with greater than signs with $(\genfrac{}{}{0ex}{}{n}{4})=(\genfrac{}{}{0ex}{}{n}{\lceil n/2\rceil })$ because the ceiling value of n/2 is 4.
It is confusing to understand which of the steps is correct between the $1^{st}$ and $2^{nd}$ provided in the option list. Also what is the first step for solving this, the problem definition or something similar does not exist in the text provided.

Alternative proof for the sum of first n natural numbers (Gauss formula)
The known formula for the sum of the first n natural numbers $n(n+1)/2$ is not intuitive at all. One proof for that formula is to duplicate the numbers and arrange it in pairs which sums up to $n+1$ and then sum up all the numbers:
$1+2+3+4+5+5+4+3+2+1=2(1+2+3+4+5)=n(n+1)$
It is a really nice proof and also very direct and intuitive. But I have come up with this alternative:
Suppose there are $n+1$ people meeting and they all shake hands with each other. To count how many hand shakes are in total, one can start counting the hand shakes for one person which is n. Then for a second person count her hand shakes, but don't count the hand shake with the first person, because that one was already counted, so in total, for the second person, we count $n-<!--\; -\; -->1$, and so on. The total hand shakes is then the sum of the first n natural numbers.
But now we can count the hand shakes in a simpler way. There are $n+1$ people in total, and each of them shakes hand with n people. Then $n(n+1)$ is twice the hands shake, because we are counting twice each hand shake. So the total hand shakes must be $n(n+1)/2$
The two ways of counting have to arrive to the same number so the formula holds.
I wonder how can this proof be formalized so it would be accepted as a real mathematical proof.

How many ways to arrange 35 distinct books on 3 distinct shelves when some of the shelves can be empty?
How many ways to arrange 35 distinct books on 3 distinct shelves when some of the shelves can be empty?
Here's is what I did
There are 3 choices for each of 35 books. So I think the answer will be $3^{35}$.
I feel like it's wrong can anyone please confirm my answer? Thanks for all the feedback in advance.

Suppose that a and b are positive integers such that $a^2=3b^2$. Show that $0<b<a<2b$ and $(3b-<!--\; -\; -->a{)}^2=3(a-<!--\; -\; -->b{)}^2$
Use these and the Well-Ordering Principle to prove that no such a and b exist. From this it follows that $\sqrt{3}\notin <!--\; \notin \; -->\mathbb{Q}$.

Fraction step in inductive proof
$\frac{1}{\sqrt{3k+1}}\ast <!--\; \ast \; -->\frac{2k+1}{2k+2}=\frac{1}{\sqrt{3k+1}}\ast <!--\; \ast \; -->\frac{1}{1+\frac{1}{2k+1}}$
I presume that $\frac{2k+1}{2k+2}=\frac{1}{1+\frac{1}{2k+1}}$
But I do not understand why this equality holds and no justification is given in the website above. Can anyone explain how the left-hand side of this equation is simplified to the right-hand side?