Explore Discrete Math Examples

If A and B are finite sequences and $A,B=B,A$ (where the comma denotes the concatenation of sequences), then both A and B are repetitions of some sequence C.

How can I figure out how many anagrams of oranwawoods contain at least two consecutive o’s?
Because we can let two o's be x, and there are 9 letters left, and in the rest of 9 letters, we have 2a and 2w, so number of anagrams is:
$\frac{9!}{2!\times <!--\; \times \; -->2!}$.

What is the smallest number of roads in a country?
There are 300 cities in the country. Some pairs of them are connected by roads. It turned out that if you close any 150 cities, then there will be at least 150 roads. What is the smallest number of roads in a country?

How many 20-digit numbers can be formed from $\{1,2,3,4,5,6,7,8,9\}$ such that no 2 consecutive digit is both odd
I've noticed that the number of odd digit in the number must be less than 11. But i can't progress more than that.

How many length-6 lists can be made from the symbols {A,B,C,D,E,F,G} if repetition is allowed
I am trying to solve this question from The Book of Proof, and I solved it in a different way than the author. The question is as follows:
How many length-6 lists can be made from the symbols {A,B,C,D,E,F,G} if repetition is allowed and the list is in alphabetical order? (Ex. BBCEGG, but not BBBAGG).
My Solution
Since we want this to be in alphabetical order we need to think of what the starting letter is. If the starting letter is A then we are free to choose A as many times after that. If we choose B to be our first letter than we can never choose A in that list.
Using "stars and bars," let's say we choose A to be our first letter, then we have 5 more spots to from our selection of symbols. Thus, we have 5 stars and 6 bars, (115).
Using the same idea for choosing B being the first letter, we have 5 more spots to fill in, but we cannot choose A. This leads to the consequence of loosing a bar. So, we have 5 stars and now 5 bars leading to
Continuing with this choosing the first letter from A to G we get:
$(\genfrac{}{}{0ex}{}{11}{5})+(\genfrac{}{}{0ex}{}{10}{5})+(\genfrac{}{}{0ex}{}{9}{5})+(\genfrac{}{}{0ex}{}{8}{5})+(\genfrac{}{}{0ex}{}{7}{5})+(\genfrac{}{}{0ex}{}{6}{5})+(\genfrac{}{}{0ex}{}{5}{5})=924$
Authors Solution:
Any such list corresponds to a 6-element multiset made from the symbols {A,B,C,D,E,F,G}. For example, the list AACDDG corresponds to the multiset [A,A,C,D,D,G]. Thus the number of lists equals the number of multisets, which is $(\genfrac{}{}{0ex}{}{12}{6})$
My Question:
Is my solution a correct way to use Stars and Bars?
The way the author solved it, how can you enforce the idea that the lists are in alphabetical order without explicitly telling it so?

How is the summation being expanded?
I am trying to understand summations by solving some example problems, but I could not understand how is the second to last line being expanded? I would really appreciate if you could explain me how is it being expanded.
$\begin{array}{rl}& \underset{i=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}\underset{j=i+1}{\overset{n}{\sum <!--\; \sum \; -->}}\underset{k=1}{\overset{j}{\sum <!--\; \sum \; -->}}1=\\ & \underset{i=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}\underset{j=i+1}{\overset{n}{\sum <!--\; \sum \; -->}}j=\\ & \underset{i=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}(\underset{j=1}{\overset{n}{\sum <!--\; \sum \; -->}}j-<!--\; -\; -->\underset{j=1}{\overset{i}{\sum <!--\; \sum \; -->}}j)=\\ & \underset{i=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}(\frac{n(n+1)}{2}-<!--\; -\; -->\frac{i(i+1)}{2})=\\ & \frac{1}{2}\underset{i=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{n}^2+n-<!--\; -\; -->i^2-<!--\; -\; -->i=\\ & \frac{1}{2}((n-<!--\; -\; -->1)n^2+(n-<!--\; -\; -->1)n-<!--\; -\; -->(\frac{n(n+1)(2n+1)}{6}-<!--\; -\; -->n^2)-<!--\; -\; -->(\frac{n(n+1)}{2}-<!--\; -\; -->n))=\\ & f(n)=\frac{n(n(n+1))}{2}-<!--\; -\; -->\frac{n(n+1)(2n+1)}{12}-<!--\; -\; -->\frac{n(n+1)}{4}\end{array}$

Prove that $\underset{n\in <!--\; \in \; -->\mathbb{N}}{\bigcup <!--\; \bigcup \; -->}(-<!--\; -\; -->n,\frac{1}{n}]=(-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->},1]$
I understand that for this to be true, I have to show that $\underset{n\in <!--\; \in \; -->\mathbb{N}}{\bigcup <!--\; \bigcup \; -->}(-<!--\; -\; -->n,\frac{1}{n}]\subset (-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->},1]$ and $(-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->},1]\subset \underset{n\in <!--\; \in \; -->\mathbb{N}}{\bigcup <!--\; \bigcup \; -->}(-<!--\; -\; -->n,\frac{1}{n}]$, however, I'm stuck on figuring it out. I think the latter can be proven by contradiction somehow.

Let's say we had a sack with exactly 4 green marbles, 4 orange marbles, 4 black marbles and 4 violet marbles.
How many different picks are there having exactly 8 marbles that have at least one marble of each color?
I'm not quite sure whether this is a permutation or a combination. Going with the assumption that it is a combination I'm guessing the sample space is $(\genfrac{}{}{0ex}{}{16}{8})$. To find at least one marble of each color we could go with the complement of this statement. Not quite sure how to express it.
Perhaps $(\genfrac{}{}{0ex}{}{16}{8})$ with the assumption that the complement of "at least one of each color" could be expressed as $-<!--\; -\; -->4(\genfrac{}{}{0ex}{}{12}{4})$. But even that seems lacking.

Why don't we use the equivalence sign $\equiv <!--\; \equiv \; -->$ in set identities?
I am currently studying Discrete Maths in my 1st year.
Consider the following equivalences : (I'll just use absorption law as example)
In logical expression: $p\vee (p\wedge q)\equiv p$
In set theory: $P\cup (P\cap Q)=P$
Every article I see uses only the "=" sign for laws of set identities.
I have tried searching for this, but to no avail. I also emailed my professor, in which he replied "the reasoning is simple, as the equivalence sign can only be used for logic expression." I don't quite understand this and would like to have a more intuitive approach.
My thoughts on this: the only possible reason that I could think of is because in set theory, the LHS and RHS are not completely "identical" to each other, as there are different ways of representing the LHS and RHS (for example, I could shade the venn diagrams differently). Whereas, in logical expressions, we are only interested in binary values T/F, as such, they are completely identical because there can only be "one" way of expressing the LHS and RHS.
I am not quite sure whether my trail of thoughts is clear... but I hope someone can share some light on this.

How many different ways of planting the flowers?
Peter's neighbour, Paul likes tulips. He would like to plant 2 white, 5 red and 6 black tulips in a row in a way such that a red and a black tulip cannot be next to each other. How many different ways can he design the row?
I count two cases:
1. …w…w…
bwrwb in which wrw takes 7 positions and it can start from 7 different places.
rwbwr wbw takes 8 positions and can start from 6 different places.
2. …ww…
red ww black
black ww red Which is 2 ways
So in Total I got $7+6+2=15$ ways. But the answer is 33 ways. I can’t think of any other ways of arrangement…

How to prove $(1+q{)}^n\ge <!--\; \ge \; -->1+qn$ for all $\mathbb{N}$ with $q>0$
I need to prove $(1+q{)}^n\ge <!--\; \ge \; -->1+qn$ for all $n\in <!--\; \in \; -->\mathbb{N}$ with $q>0,q\in <!--\; \in \; -->\mathbb{R}$ using mathematical induction.
Firstly, I proved the base case for $n=1$ that indeed $1+q\ge <!--\; \ge \; -->1+q$.
Then in the inductive step, I started with $(1+q{)}^{k+1}$ and came to the following form
$(1+q{)}^k(1+q)\ge <!--\; \ge \; -->(1+qk)(1+q)$. However I'm uncertain how to explicitly show that $(1+q{)}^{k+1}\ge <!--\; \ge \; -->1+q(k+1)$ because after the expansion I get the $k{q}^2$ term that I'm unable to get rid of.

Top-injective and indiscrete
I have found one proposition in some papers about pure injectivity topological modules. Proposition: A topological space is categorically Top-injective if and only if it is indiscrete. Proof: $(\Leftarrow <!--\; \Leftarrow \; -->)$ Suppose that $(I,\mathrm{\tau <!--\; \tau \; -->})$ is a topological space where I is non-empty and $\mathrm{\tau <!--\; \tau \; -->}$ is the indiscrete topology. Let f be a continuous one-to-one function from $(Y,{\mathrm{\tau <!--\; \tau \; -->}}_1)$ to $(X,{\mathrm{\tau <!--\; \tau \; -->}}_2)$. Let g be a continuous map from $(Y,{\mathrm{\tau <!--\; \tau \; -->}}_1)$ to $(I,\mathrm{\tau <!--\; \tau \; -->})$. Let $i\in <!--\; \in \; -->I$. Let $h(x)=g{f}^{-<!--\; -\; -->1}(x)$ if $x\in <!--\; \in \; -->f(Y)$ and $h(x)=i$ if $x\notin <!--\; \notin \; -->f(Y)$. Now h is a continuous map from $(X,{\mathrm{\tau <!--\; \tau \; -->}}_2)$ to $(I,\mathrm{\tau <!--\; \tau \; -->})$ since $\mathrm{\tau <!--\; \tau \; -->}$ is the discrete topology on I. Furthermore, $g=hf$. Therefore, $(I,\mathrm{\tau <!--\; \tau \; -->})$ is categorically Top-injective.
Is h(x) well-defined? I mean, $h(x)=i$ for every $x\notin <!--\; \notin \; -->f(Y)$ doesn't guarantee that h(x) is well-defined. This proposition state that if M is Top-injective, then the only topology for M is trivial topology. Is it right? Thank you for any help.

Is the function $f:\mathbb{R}\to <!--\; \to \; -->\mathbb{R}:f(x)=1$ bijective?

Fibonacci Addition Identity for Fibonacci Numbers Separated by 3 Terms
The Fibonacci Addition Identity states that: $F_n=F_m{F}_{n-<!--\; -\; -->m+1}+F_{m-<!--\; -\; -->1}{F}_{n-<!--\; -\; -->m}$. This was useful in showing that: $F_{i+k}=F_{k-<!--\; -\; -->2}{F}_{i+1}+F_{k-<!--\; -\; -->1}{F}_{i+2}$. However, I would like to use this result to express the same for $F_i$ and $F_{i+3}$, where we can express $F_{i+k}$ in some linear combination of $F_i$ and $F_{i+3}$. Is there any way to do this? I haven't been able to make use of the typical Fibonacci substitutions to make any progress.

Use strong induction to prove piecewise function
$H_0=0,H_1=1,H_2=1$, for all $n\in <!--\; \in \; -->\mathbb{N}$ where $n\ge <!--\; \ge \; -->3$:
Prove for all $n\in <!--\; \in \; -->\mathbb{N}$,
$H_n=H_{n-1}+H_{n-2}-H_{n-3}.$
$H_n=\{\begin{array}{ll}{\displaystyle \frac{n}{2}},& \text{if }n\text{ is even}\\ {\displaystyle \frac{n+1}{2}},& \text{if }n\text{ is odd}\end{array}$
I don't know how the inductive step $k+1$ in a strong induction would go for piecewise function like this. I think I'll have to show the proposition hold when $k+1$ is even and odd, but I don't know how to continue the proof.

What would the negation of these two statements be?
I need to negate these two statements and I believe that I have the quantifiers correct, but I'm not completely sure how to negate the math statements. I think I would keep the equations before the equal signs the same but I'm still unsure how to negate the last parts.
Here are the statements I want to negate:
Statement 1:
$\mathrm{\exists <!--\; \exists \; -->}x,y\in <!--\; \in \; -->{\mathbb{R}}_{\ge <!--\; \ge \; -->0},\sqrt{9x^2+y^2}\ne <!--\; \ne \; -->3x+y.$
Statement 2:
$\mathrm{\forall <!--\; \forall \; -->}x\in <!--\; \in \; -->{\mathbb{R}}_{\ge <!--\; \ge \; -->0},\sqrt{25x^2+9}=5x+3.$

Difference between $p\cos <!--\; \; -->\theta$ and $\cos <!--\; \; -->p\theta$

Is the system is a geometric progression?
I am trying to show that the following system is a geometric progression i.e. $a_2=a_1^2$, $a_3=a_1^3$ etc.
$a_k^2=a_{k-<!--\; -\; -->1}{a}_{k+1}$
$a_{k-<!--\; -\; -->1}^2=a_{k-<!--\; -\; -->2}{a}_k$
$a_2^2=a_1{a}_3$
here $a_k>...>a_2>a_1$ is assumed.
Is there sufficient information to conclude that $a_i=a_1^i$ in general? I am seeing that I would probably need to assume $a_2=a_1^2$. Could the geometric progression be concluded otherwise?

Prove $\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}\frac{(2k)!(2n-<!--\; -\; -->2k)!}{2^{2n}(2k+1)[k!(n-<!--\; -\; -->k)!{]}^2}=\frac{[2^{n}n!{]}^2}{(2n+1)!}$ using mathematical induction
Since I already know the way using combinatorial proof, I am trying to prove it by mathematical induction but it is not easy to show.
I derived that
$S_n=\frac{2n}{2n+1}{S}_{n-<!--\; -\; -->1}$ from RHS, but how can I proceed from this? I mean, how can I organize the LHS? I cannot organize LHS properly because of different $n,n=m\text{and}n=m+1$.