Explore Discrete Math Examples

Let A and B be sets and let $f:A\to B$ be a function. Show that if $D\subseteq B$, then $f(f-1(D))\subseteq D$.

Big O Notation - Prove $(nlogn{)}^2-<!--\; -\; -->4\text{is}O(n^4)$.
My Attempt:
$C(n^4)\ge <!--\; \ge \; -->(nlogn{)}^2-<!--\; -\; -->4$
i assumed $n>0$, so that $n>\log <!--\; \; -->(n)$
$(n{)}^2>(\log <!--\; \; -->n{)}^2$
$n^2>{\log }^2<!--\; \; -->(n)$
$n^4>n^2\cdot <!--\; \cdot \; -->{\log }^2<!--\; \; -->(n)$

How many numbers formed from all the digits 1113333344455678 are there if the digits 6 and 8 have to appear from the different sides of the digit 7?
My thoughts:
I thought I should first find how many numbers are formed from all the 14 digits 11133333444557, which is
$(\genfrac{}{}{0ex}{}{14}{3})(\genfrac{}{}{0ex}{}{11}{5})(\genfrac{}{}{0ex}{}{6}{3})(\genfrac{}{}{0ex}{}{3}{2})=\frac{14!}{3!5!3!2!},$,
and, then, analyze the possibilies given a position of the digit 7, but then, I lose the track and I only tell for sure 6 and 8 can be first and last digits in every situation, so there are strictly more numbers than $2\frac{14!}{3!5!3!2!}=\frac{14!}{(3!{)}^{2}5!}.$.
Then, I thought, I should first consider the position $p,1<p<16$ among 16 overall places for 7 and choose the positions in $p-<!--\; -\; -->1$ and $16-<!--\; -\; -->p$ ways for 6 and 8 and multiply the result by 2 for each p, but this didn't lead me anywhere.

Prove if a relation is left-total and right-unique
In this exercise, we are dealing with Tuple sets.
So let $M\subset <!--\; \subset \; -->P(A\times \mathbb{N})$ be the set of all legal tuple sets. P (X) denotes the power set of a set X. Now, Let the tuple set operation be defined as $+$ so that $+$: $M\times M\to M$.
Prove or disprove that + is left-total and right-unique.
These types of relations are uncommon in English, it seems. So, it's a bit difficult for me to understand how to prove it.
To my knowledge, a left-total relation means that, e.g. if $\mathrm{\forall <!--\; \forall \; -->}x\in <!--\; \in \; -->A$ $\mathrm{\exists <!--\; \exists \; -->}y\in <!--\; \in \; -->N$ $(x,y)\in <!--\; \in \; -->M$, i.e. for every $x\in <!--\; \in \; -->A$ there exists (at least) one $y\in <!--\; \in \; -->N$, so that $(x,y)\in <!--\; \in \; -->M$.

Composition of 2 functions with same domain and range
Let $f\in <!--\; \in \; -->R\to <!--\; \to \; -->R$ and $g\in <!--\; \in \; -->R\to <!--\; \to \; -->R$.
If $f\circ g=id$ $\mathrm{\Re <!--\; \Re \; -->}$, does that mean that $g\circ f$ will be equal to id $\mathrm{\Re <!--\; \Re \; -->}$ as well?

A croissant shop has plain croissants, cherry croissants, chocolate croissants, almond croissants, apple croissants, and broccoli croissants. How many ways are there to choose 23 croissants with at least five chocolate croissants and at least three almond croissants?
If we choose 23 croissants and each time we have selected 5 chocolate and 3 almond, we are left with $23-<!--\; -\; -->8=15$ choices.
So we have 4 remaining croissants, $n=4,r=15$ and using the formula: $(\genfrac{}{}{0ex}{}{n+r-<!--\; -\; -->1}{r})$
We have $(\genfrac{}{}{0ex}{}{4+15-<!--\; -\; -->1}{15})$
$(\genfrac{}{}{0ex}{}{18}{15})=816$
We have 816 different ways to choose 23 croissants which should have at least 5 chocolate and 3 almond.
I am thinking since it does not specify a higher limit, it could have more but does the calculation I have shown suffice the requirement? Please advise.

Having trouble with proving this binomial identity. I have taken it as far as I can go.
I have broken down this equation into factorials, but I'm unsure of where to go from here. This may not even be the right approach to solve this binomial transform. Any help would be appreciated.
Binomial transform identity:
$\begin{array}{rl}& \underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^{n-<!--\; -\; -->k}(\genfrac{}{}{0ex}{}{n}{k})(\genfrac{}{}{0ex}{}{n+jk}{jk})=j^n\\ & \underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^{n-<!--\; -\; -->k}\frac{(jk+1)(jk+2)\dots <!--\; \dots \; -->(jk+n)}{(n-<!--\; -\; -->k)!k!}=j^n\end{array}$

Is it assumed in the given proof for the Schoeder-Bernstein theorem that A and B are the ranges of the injective functions f and g?
Preamble: I'm referring to the proof given in Art of Problem solving to the Schoeder-Bernstein Theorem. Namely, the claim is that
Let A and B be sets and $f:A\to <!--\; \to \; -->B$, $g:B\to <!--\; \to \; -->A$ be injective functions. Then there exists a bijective function $h:A\to <!--\; \to \; -->B$.
Then in order to prove the theorem, a function h is defined as $h=\{\begin{array}{ll}{g}^{-<!--\; -\; -->1}(a)& :f(a)\text{ is a descendant of a lonely point}\\ f(a)& :\text{ otherwise}\end{array}$
My immediate thought was that: What if $g^{-<!--\; -\; -->1}(a)$ is not defined? Namely given that $g:B\to <!--\; \to \; -->A$ is injective, why should necessarily $g[B]=A$? To which I answered an example in a finite case that if the cardinality of A is greater than B, and g is injective, then by the pigeonhole principle f cannot be injective. However it is not immediately obvious to me how the case of A and B being countable/uncountable should be handled, as A and B are just sets.
Question: Is it assumed in the aforementioned proof behind the link that $f[A]=B$ and $g[B]=A$?. Or does it follow from somewhere else that $g^{-<!--\; -\; -->1}(a)$ is necessarily defined, given the portion of the proof up to the definition of the function h?

How many 2021-digit numbers can be formed from 1, 2, 3, 4, 5 and is divisible by 3 (possible repetition).
So i have one approach to the problem. I used pigeon hole theorem to prove that there are at least $[\frac{2021}{5}]+1=405$ identical number. And since 405 is divisible by 3 so the sum of those 405 same digit is also divisible by 3 and i only need to solve the problem with $2021-<!--\; -\; -->405=1616$-digit numbers. I continued that until there is less than 3 identical digit (the number of identical digits must be divisible by 3). At that point, the problem can be converted to
How many 8-digit numbers can be formed from 1, 2, 3, 4, 5 and is divisible by 3 (possible repetition).
To solve the above problem, i tried to find all 3x for $5\ast <!--\; \ast \; -->1\le <!--\; \le \; -->3x\le <!--\; \le \; -->5\ast <!--\; \ast \; -->5$ and solve every custom sub-problem. But my solution seems to be too tedious and i wonder if there is a specific formula to solve the first problem. Every idea is appreciated. Thanks in advance.
I also want to know if there is a way to solve this problem
Share m candy bars to n people such that no one have more than k candy bars.
That sub-problem can help solve my problem.

Markov Chains and Conditional Probability: Easy rat in the maze problem
Why is the following solution to this problem incorrect,
A rat is trapped in a maze with three doors and some hidden cheese. If the rat takes door one, he will wander around the maze for 2 minutes and return to where he started. If he takes door two, he will wander around the maze for 3 minutes and return to where he started. If he takes door three, he will ind the cheese after 1 minute. If the rat returns to where he started he immediately picks a door to pass through. The rat picks each door uniformly at random. How long, on average, will the rat wander before finding the cheese?
1. Construct a graph with three vertices: X, Y, Z, each of which represents a door in the original problem.
2. Add edges between every vertex, including self-loops, each of which has a weight of 1/3.
3. Take the stationary distribution to be (1/3, 1/3, 1/3). It is unique because the probability transition question for the graph in (1) is regular (i.e., its limit is just the same matrix with all entries equal to 1/3)
4. Compute the expected time as $21/3+31/3+1\cdot <!--\; \cdot \; -->1/3=2$
The correct answer is 6. I know that the set-up is completely wrong and that I should use conditional probability, but is there a way to do it like this? The main issue is that we don't know the total time spent in the maze (this is kind of what we need to find) so I can see that it doesn't really make sense to take this approach.

How to understand the operation "choose a random subset" in combinatorics?
Define a set $B\subset <!--\; \subset \; -->{\mathbb{Z}}^{+}$ randomly by requiring the events $n\in <!--\; \in \; -->B$ (for $n\in <!--\; \in \; -->{\mathbb{Z}}^{+}$) to be jointly independent with probability $\mathbf{\text{P}}(n\in <!--\; \in \; -->B)=min(C\sqrt{\frac{\log <!--\; \; -->n}{n}},1)$, where C is a large constant to be chosen later.
Since I've not seen such a method before, I have several questions:
1. If one talks about randomness, then there should be a probability space. In the proof they choose a set B randomly, what is the probability space $(\mathrm{\Omega <!--\; \Omega \; -->},\mathcal{F},\mathbb{P})$ here?
2. Relating to the first question, how could I require that events $\{n\in <!--\; \in \; -->B{\}}_{n\in <!--\; \in \; -->{\mathbb{Z}}^{+}}$ to be jointly independent?
3. Why could I require that events $\{n\in <!--\; \in \; -->B{\}}_{n\in <!--\; \in \; -->{\mathbb{Z}}^{+}}$ have the assigned probability?

If 2 out of 6 Machines are Defective, and 3 were selected randomly , What is the Probability Distribution of the number of Defectives?
Even more generally :
If n objects are divided to m alike and k alike , we select x amount randomly , then to find how probable is it that y objects from x are m , using some trial and error I managed to find this complicated formula:
$P_X(y)=\frac{(\genfrac{}{}{0ex}{}{x}{y}){(}_m{P}_y){(}_k{P}_{x-<!--\; -\; -->y})}{{}_n{P}_x}$
But then it turned out that there is an easier formula with Combinations which is actually exactly equal to the previous one
$P_X(y)=\frac{(\genfrac{}{}{0ex}{}{m}{y})(\genfrac{}{}{0ex}{}{k}{x-<!--\; -\; -->y})}{(\genfrac{}{}{0ex}{}{n}{x})}$
I can't understand how any of them can be shown mathematically or why do they have the same meaning.

Is there any theorem from linear algebra about writing random variables as a linear combination of their elements?
Suppose that X is a random variable which belongs to a standard probability space $(\mathrm{\Omega <!--\; \Omega \; -->},\mathcal{B},\mathrm{\mu <!--\; \mu \; -->})$. Could anybody provide some theorem and its details where X can be written as $X=\underset{i=1}{\overset{k}{\sum <!--\; \sum \; -->}}{w}_i{x}_i$, where $w_i\ne <!--\; \ne \; -->0$ and $x_i\in <!--\; \in \; -->\mathbb{R}$?

Trivial approximation ratio of n/2 for 2-Opt for TSP
I recently read that the 2-Opt algorithm for the TSP yielded an approximation ratio of n/2 by trivial reasons. However, there was neither proof nor further context provided and I am curious how this bound can be obtained since I don't see these trivial reasons. I hope you can help me and give some intuition of why this ratio holds. (Note: Perhaps this can only obtained easily when considering metric TSP which would totally suffice for my concerns)

Extract Coefficients to Solve Recurrence Relation
$e_0=e_1=1,e_2=2$ and $e_n=3e_{n-<!--\; -\; -->1}-<!--\; -\; -->3e_{n-<!--\; -\; -->2}+e_{n-<!--\; -\; -->3}$

How many 4-permutations of the positive integers not exeeding 100 contain three consecutive integers k, $k+1,k+2$, in the correct order
a) where these consecutive integers can perhaps be separated by other integers in the permutation?
b) where they are in consecutive positions in the permutation?
We know that the number of permutations with repetition for a is $98\ast <!--\; \ast \; -->97\ast <!--\; \ast \; -->4$ since for every 98 possible choices of k we have 97*4 possible 4-permutations, (arrangements) of k, $k+1,k+2$ and another number different from those 3.
But how can I compute the repreated permutations?
For instance, consider $k=1$. Then some of the possible permutations are "1,2,3,4","4,1,2,3","1,4,2,3" which are also permutations for $k=2$. I think that given a number k I should find the 4-permutations of k that are repeated in other permutations. Then i will need to multiply this value for 98, the number of total possible Ks and subtract this from the first result. But I do not know how can I compute them.
Sorry if the question has already been made, but my point of interest regards how to find the repetitions I am interested in.

Does there exist an equivalence relation on a set such that the set of equivalence classes and all individual equivalence classes are all uncountable?
I have thought about many examples, usually involving equivalence relations on $\mathbb{R}$, and so far none of them fulfill the criteria. I have tried to think about the various definitions of equivalence relation, equivalence classes, countability and so on but I have yet to prove or disprove it for sure. At this point I feel like there exists no such equivalence relation, but I would like to know for sure and how you would go about proving this.

Intuition for expressing a cycle as a product of transpositions.
I have recently learned the proof of:
$(a_1{a}_2\dots <!--\; \dots \; -->a_n)=(a_1{a}_k)(a_1{a}_{k-<!--\; -\; -->1})\dots <!--\; \dots \; -->(a_1{a}_2)=(a_k{a}_{k-<!--\; -\; -->1})(a_k{a}_{k-<!--\; -\; -->2})\dots <!--\; \dots \; -->(ak{a}_1)=(a_1{a}_2)(a_2{a}_3)\dots <!--\; \dots \; -->(a_{k-<!--\; -\; -->1}{a}_k)$
Now I can prove the above 3 equalities through induction but unfortunately induction, unlike a direct proof, doesn't quite tell me what is really going on. I'm struggling to understand this intuitively. I don't want to just memorize it.

Let G be a connected graph and suppose that $f:V(G)\to <!--\; \backslash rightarrow\; -->\mathbb{Z}$ is a function with the property that $f(u)+f(v)\equiv <!--\; \equiv \; -->0\mathrm{mod}3$ for every edge uv. To prove that if G is not bipartite, then $f(v)\equiv <!--\; \equiv \; -->0\mathrm{mod}3$ for all $v\in <!--\; \in \; -->V(G)$