Explore Discrete Math Examples

Determining the truth value of $\exists x\forall y(y=x^2+2x+1)$
The domain for x and y are all integers.
$\exists x\forall y(y=x^2+2x+1)$ can be interpreted as: There is an x for all y such that it satisfies $y=x^2+2x+1$. There is a single x value which results in all the domain values of y - all the integers.
This can't be true, as the relationship between x and y is given; a single x value cannot result in every elements in the range of integers. Thus, the truth value of the statement is false.
Yet, a different justification for the false value was stated on the answer sheet. Referring to it, the statement's truth value is false because for every x, there is always an integer $y=x^2+2x+2>x^2+2x+1$.
Can anyone explain to me regarding its meaning?

If I flip a coin n times how many different combinations are there?
For example if a coin is flipped 3 times I know how to calculate all the possible outcomes. I don't understand how I reduce that count to only the combinations where the order doesn't matter.
I know there's 8 permutations but how do you reduce that count to 4? {HHH,TTT,HTT,THH}
I've tried thinking about the combinations formula with repetition, the product rule, the division rule.

let L be a bounded distributive lattice with dual space $(X:={\mathcal{I}}_p(L),\subseteq <!--\; \subseteq \; -->,\mathrm{\tau <!--\; \tau \; -->})$, then the clopen downsets of X are $X_a,a\in <!--\; \in \; -->L$.

How can I prove ${\mathrm{\Sigma <!--\; \Sigma \; -->}}_{i=1}^{n-<!--\; -\; -->1}i={(}_2^n)$

Calculating the distribution of the random variable Y at the output
The random variable X at the entrance to the transmission path is sufficient for the following distribution.
$X=P(x)$
$x_1=0.1$ $x_2=0.2$ $x_3=0.3$ $x_4=0.4$
The random variable Y at the output of the transmission link only takes three values. The transfer matrix T with $p_i^j=P(Y=y_j|X=x_i)$ is
$T=(p_i^j)=\left(\begin{array}{ccc}0.50& 0& 0.50\\ 0.20& 0.40& 0.40\\ 0.50& 0.25& 0.25\\ 0& 0.50& 0.50\end{array}\right)$

Coloring of a table with red or green rows and columns
In a $10\times <!--\; \times \; -->10$ table, half of the cells are red and half are green. Let's call a row or a column good if all cells in it are the same color. What is the maximal total number of good rows and columns in such a table?
The simple and obvious answer is 10. I've been trying to search for different intersections of the same color, yet 10 is still the biggest number. Can there be 11, for instance?

Prove for every $n\ge <!--\; \ge \; -->2$ : $1!+2!+...+n!<\frac{(n+1)!}{n-<!--\; -\; -->1}$
I tried to solve it with induction, for $n=2$ it holds, $1!+2!<\frac{6}{1}$.
so by using induction step I have to prove:
$\frac{(n+1)!}{n-<!--\; -\; -->1}+(n+1)!<\frac{(n+2)!}{n}$
but I just don't know how. Any help would be greatly appreciated.

Arranging 120 students into 6 different groups so that the largest and smallest group differ by 2 members
In how many different ways can we arrange 120 students into 6 groups for 6 different classes so that the largest group has at most 2 members more than the smallest group?
My initial plan was to use a generating function, but I stumbled across a problem. Let's mark the groups with numbers 1 to 6 and let $n_i,i\in <!--\; \in \; -->\{1,\dots <!--\; \dots \; -->,6\}$ denote the number of members of the i-th group in some arrangment. To see where this would lead me, for a moment, I assumed $n_1\le <!--\; \le \; -->n_2\le <!--\; \le \; -->\cdots <!--\; \cdots \; -->\le <!--\; \le \; -->n_6\le <!--\; \le \; -->n_1+2$ in hope to find some range $\{m,\dots <!--\; \dots \; -->M\}$ for $n_i$'s and use a generating function $f(x)=(x^m+\cdots <!--\; \cdots \; -->+x^M{)}^6$ and find $⟨<!--\; ⟨\; -->x^{120}⟩<!--\; ⟩\; -->-<!--\; -\; -->$ the coefficient in front of $x^{120}$, however students are distinct entities and m and M still remained misterious. I then tried figuring out if I was on the somewhat right track by, again taking $m=min\{n_1,\dots <!--\; \dots \; -->,n_6\}$ and write $n_i=m+j_i,j_i\in <!--\; \in \; -->\{0,1,2\}.$. I believe, an arrangement with 2 groups of 19,2 groups of 20 and 2 groups of 21 people suggests there should be at least 19 people in each group.

What is the probability that a five-card poker hand contains all 4 suits?
What is the probability that a five-card poker hand contains all 4 suits?
What I did was I this:
$\frac{C(4,1)C(13,1)C(3,1)C(13,1)C(2,1)C(13,1)C(1,1)C(13,1)C(4,4)C(48,1)}{C(52,5)}.$
My logic for C(4,1) was to choose one of the four suits, then the C(13,1) was to pick one of the cards of that suit, and similarly for C(3,1) subtracting one because there is one less suit to choose from.
Same logic applies for C(2,1) and C(1,1) and then C(4,4) and C(48,1) lets me choose any of the remaining 48 cards from all suits because the last card doesn't matter.
Then answer ends up being something ridiculously big (not a fraction) and I don't know where I went wrong because I believe my logic is sound. What would be the correct answer and why?

Clever proof for showing that if a graph G is critically k-colorable then $\mathrm{\delta <!--\; \delta \; -->}(G)\ge <!--\; \ge \; -->k-<!--\; -\; -->1$
While reading for my graph theory class, I came across a short - yet curious - proof for the following theorem: if a graph G is critically k−colorable then $\mathrm{\delta <!--\; \delta \; -->}(G)\ge <!--\; \ge \; -->k-<!--\; -\; -->1$. Here is the proof to the claim:
Suppose (for a contradiction) that G is k-critical and that $v\in <!--\; \in \; -->V(G)$ satisfies $\text{deg}(G)<k-<!--\; -\; -->1$. Then $G-<!--\; -\; -->v$ has a $(k-<!--\; -\; -->1)-<!--\; -\; -->$ coloring, and this coloring extends to a $k-<!--\; -\; -->1$- coloring of G. This yields a contradiction.
Everything in this proof makes sense besides one particular item: in the second line, what does the author mean by extending a coloring from a subgraph of G to the whole graph? In addition, why does $G-<!--\; -\; -->v$ have a $(k-<!--\; -\; -->1)$ coloring that extends to all of G (if that makes any sense)? I understand this may seem like an easy Google search but to be honest I can't find anything helpful and figured someone could provide some insight.
Note that this is not a homework question but simply for going beyond what I am learning in class.

Number of combinations with given outcomes for a set number of dice rolls
How to find the number of combinations for n rolls of a pair of 6-sided dice with all of the specified sums rolled at least once?
Example. A pair of 6-sided dice is rolled 5 times. What is the number of combinations containing each of: 3, 4, 8 at least once? So that (3, 7, 8, 5, 4) is counted and (3, 4, 2, 2, 12) is not.
Thoughts on the example. It's possible to roll 3 in 2 ways, 4 in 3 and 8 in 5 and the total number of outcomes is 36. So I think the number of combinations containing 3, 4, 8 is:
$C={36}^2\times <!--\; \times \; -->{}_5{\mathrm{P}}_3\times <!--\; \times \; -->2\times <!--\; \times \; -->3\times <!--\; \times \; -->5-<!--\; -\; -->D$
Where D is duplicates. But if this is correct, not sure what pattern the duplicates follow.

Find Consistency Of System Specifications
1. $p\wedge \neg q=T$
2. $(q\wedge p)\to r=T$
3. $\neg p\to \neg r=T$
4. $(\neg q\wedge p)\to r=T$
From Eq 1, we got $p=T$ and $q=F$.
Now Apply value of P in Eq 3, we get:
$\begin{array}{ccccc}p& \neg p& r& \neg r& \neg p\to <!--\; \to \; -->r\\ \text{T}& \text{F}& \text{T}& \text{F}& \text{T}\\ \text{T}& \text{F}& \text{F}& \text{T}& \text{T}\\ \text{F}& \text{T}& \text{T}& \text{F}& \text{F}\\ \text{F}& \text{T}& \text{F}& \text{T}& \text{T}\end{array}$
Now there are two possibilities when $\neg p\to r$ is T, and $\neg p$ is F but the r has two separate values.

Graph Theory in discrete mathematics
Let G be a graph with order 9 so that the degree of each vertex is either 5 or 6. Prove that there are either at least 5 vertices of degree 6 or at least 6 vertices of degree 5

Which is the difference between the logical propositions $\mathrm{\exists <!--\; \exists \; -->}a,b$ and $\mathrm{\exists <!--\; \exists \; -->}a\mathrm{\exists <!--\; \exists \; -->}b$?
I was wondering if there is any difference between $\mathrm{\exists <!--\; \exists \; -->}a,b$ and $\mathrm{\exists <!--\; \exists \; -->}a\mathrm{\exists <!--\; \exists \; -->}b$. I can't imagine there would be any but my homework uses them both.

Consider the sets A and B , where
$A=\{3,|B|\}$
and $B=\{1,|A|,|B|\}$
What are the sets?
Answer: We need to be a little careful here. If B contains 3 elements, then A contains just the number 3 (listed twice). So that would make $|A|=1$, which would make $B=\{1,3\}$, which only has 2 elements. Thus $|B|\ne <!--\; \ne \; -->3$. This means that $|A|=2$ so B contains at least the elements 1 and 2. Since $|B|\ne <!--\; \ne \; -->3$, we must have $|B|=2$ which agrees with the definition of B . Therefore it must be that $A=\{2,3\}$ and $B=\{1,2\}$.
I do not understand how the solution ended. If at the end A now has 2 elements, B should be updated as well. Previously B knows that A is just {3} with $|A|=1$, but since A now has two elements 2 and 3, then $|A|=2$ and B must be $\{1,2,3\}$. The last 3 is the new cardinality of B .
Of course, if I go this route, then A must be updated as well because now $|B|=3$, making A go back to $\{3\}$. Thus we go back to the original forms of the sets, namely $A=\{3\}$ and $B=\{1,2\}$ and so on.
It seems to me, finding both cardinalities leads to never ending transformations. There must be something that I am missing. Why is it correct to end the sets such that $A=\{2,3\}$ and $B=\{1,2\}$.
It seems to only respect the cardinality of B but did not continue to respect the cardinality of A. But continuing on this reasoning will lead to an infinite loop. Can someone explain what is wrong in my thinking?

Isn't chromatic number just the minimum number of independent sets?
Almost everywhere I read it defines chromatic number as the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color. But if adjacent vertices are of different colours, it seems to mean that adjacent vertices belong to different independent sets. So, I'm almost certain that the definition in title is correct, but I couldn't find a standard source where it is defined like it. So, I'm posting this question to get confirmation.

Minimum number of edges for a specific type of graph.
Let G be a graph on $n\ge <!--\; \ge \; -->6$ vertices.
What is the minimum number of edges required if we assume that the graph is both bipartite and Eulerian?
Also, can we characterize all such graphs as having a minimum number of edges?
We know that for the Eulerian graph we need all vertices to be of even degree. And due to bipartitedness we cant have odd cycles. Also, minimum edges are possible if we have partitions of equal size almost.
So even cycle will be one such graph. But I feel there will be more, like if n is odd then?

Number of solutions to $x_1+x_2+x_3+x_4=1097$ with multiple "at least" restrictions
How many solutions to $x_1+x_2+x_3+x_4=1097$, in nonnegative integers $x_1$, $x_2$, $x_3$, and $x_4$ which satisfy at least one of the inequalities $x_1\ge <!--\; \ge \; -->100$, $x_2\le <!--\; \le \; -->499$?
I understand how to calculate the number of solutions to the unrestricted problem: $(\genfrac{}{}{0ex}{}{1097+4-<!--\; -\; -->1}{1097})$ solutions $=(\genfrac{}{}{0ex}{}{1100}{1097})=(\genfrac{}{}{0ex}{}{1100}{3})$
I also know how to handle a single restriction being added. For example if we just take $x_1\ge <!--\; \ge \; -->100$: We have $x_1=x_1^{\prime }+100$. Then our problem is equivalent to $x_1^{\prime }+x_2+x_3+x_4=997$. Then we have $(\genfrac{}{}{0ex}{}{4+997-<!--\; -\; -->1}{997})=(\genfrac{}{}{0ex}{}{1000}{3})$ solutions
Finally, I know if we had to meet both restrictions, we could do the unrestricted number of solutions - the number of solutions that violate each requirement. Where I'm running into trouble is determining how to calculate the number of solutions that meet at least one restriction. How can I find the number of solutions that violate both restrictions?

Battleship placement proving that the number of battleships is divisible by 3
We have a grid of 6 columns and x number of rows. All battleships are three units long and can be placed like this: 1 or like this: 2
Where the entire grid is filled with ships with no square units left unfilled, I'm interested in showing that the number of ships positioned as seen in (2) must be divisible by 3; the number of ships placed upright is divisible by 3.
I noticed that the restriction on the number of columns to be 6 means that each column can only have up to two of the ships of type (1), I can show that the number of square units remaining is divisible by 3 but I know that this does not imply the actual number of ships is divisible by 3.

Find the coefficient of $x^n$ in $(x^2+x^3+x^4+\cdots <!--\; \cdots \; -->{)}^5$.
I have got stuck on this question, though I realise that I have probably got really close to an answer. This is how I approached it:
$\begin{array}{rl}f(x)& =(x^2+x^3+x^4+\cdots <!--\; \cdots \; -->{)}^5\\ & =x^{10}(1+x+x^2+\cdots <!--\; \cdots \; -->{)}^5\\ & =x^{10}{\left(\frac{1-<!--\; -\; -->x^m}{1-<!--\; -\; -->x}\right)}^5\\ & =x^{10}(1-<!--\; -\; -->x^m{)}^5(1-<!--\; -\; -->x{)}^{-<!--\; -\; -->5}.\end{array}$
Then I have used the binomial theorem:
$\begin{array}{rl}(1-<!--\; -\; -->x^m{)}^5& =\underset{i=0}{\overset{5}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{5}{i})(-<!--\; -\; -->1{)}^i(x^m{)}^i,\\ (1-<!--\; -\; -->x{)}^{-<!--\; -\; -->5}& =\underset{j=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{4+j}{j})(x{)}^j.\end{array}$
Therefore, $f(x)=x^{10}\cdot <!--\; \cdot \; -->(\underset{i=0}{\overset{5}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{5}{i})(-<!--\; -\; -->1{)}^i(x^m{)}^i)\cdot <!--\; \cdot \; -->\left(\underset{j=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{4+j}{j})x^j\right),$
and as I work out coefficient of $x^n$ I arrive to:
$[x^n]=(\genfrac{}{}{0ex}{}{5}{0})(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->6}{n-<!--\; -\; -->10})$
I think my answer is incomplete and unfortunately, I don't have a solution to check it. I would really appreciate your help. Thank you