Explore Discrete Math Examples

Discrete Math distinct words
"Let m, n, and r be non-negative integers. How many distinct "words" are there consisting of m occurrences of the letter A, n occurrences of the letter B, r occurrences of the letter C, such that no subword of the form CC appears, and no other letters are used?"

Nonisomorphic graphs Discrete Math
Find 3 different nonisomorphic graphs with 8 vertices that have the degree sequence 2,2,2,2,2,2,2,2. Answer: An 8-cycle, or two 4-cycles, or a 3-cycle and a 5-cycle.
Can someone show me how these three answers were found? I am a little confused with nonisomorphic graphs. I used to think you could just change the name of each vertex because no matter how you rearranged the vertices they would never be able to be rearranged back to their previous form. But then I was wrong and was told that you have to pay attention to adjacency but how? So for this question, how did the person come by these three answers?

Permutation in discrete math
Is the permutation
$\left(\begin{array}{ccccccc}1& 2& 3& 4& 5& 6& 7\\ 7& 4& 2& 1& 3& 6& 5\end{array}\right)$
even or odd?
The product of disjoint cycles is
$\left(\begin{array}{cccccc}1& 7& 5& 3& 2& 4\end{array}\right)\left(\begin{array}{c}6\end{array}\right)$
and the transposition are
$\left(\begin{array}{cc}1& 7\end{array}\right)\left(\begin{array}{cc}1& 5\end{array}\right)\left(\begin{array}{cc}1& 3\end{array}\right)\left(\begin{array}{cc}1& 2\end{array}\right)\left(\begin{array}{cc}1& 4\end{array}\right)\left(\begin{array}{c}6\end{array}\right)$
is it correct?
and the answer is even??

I'm studying for my discrete math class and I don't fully understand how to proof how a function is not a big O for certain questions. I understand that you have to assume that it is big O and proof by contradiction.
Please explain how you attacked these questions step by step.
1) 1 is not $O(\frac{1}{x})$
2) $e^x$ is not $O(x^5)$

Discrete Math Recursive Definition
A bit-string is simply a finite sequence of zeroes and ones. For the purposes of this problem, strings will always have length $\ge <!--\; \ge \; -->1$, i.e. no zero-length strings.
Let $A_n$ be the number of strings of length n that have no two consecutive zeros. Thus $A_1=2$ and $A_2=3$ (strings 01, 10 and 11).
Give recursive definitions for $A_n$.
My Answer:
$A(n+1)=A(n)+A(n-<!--\; -\; -->1),$
$A(n)=A(n-<!--\; -\; -->1)+A(n-<!--\; -\; -->2).$

Let P be the power set of {a,b,c} Define a function from P to the set of integers as follows: $f(A)=|A|.(|A|$ is the cardinality of A.) Is f injective? Prove or disprove. Is f surjective? Prove or disprove.
I'm having a hard time understanding what this question is asking (as I have with most discrete math problems). What does it mean by "Let P be the power set of..."?

Recurrence relations Discrete Math
Instructions say: Find the solution to the recurrence relation and prove the correctness of your solution using mathematical induction.
$a_n=a_n-<!--\; -\; -->1+3,n\ge <!--\; \ge \; -->1;a_0=1$
Please help I am completely confused, I've read the textbook section on mathematical induction and I'm so confused please be as descriptive in your explanations as possible.

Suppose we can only use 5 kinds of tiles to cover a $1\times <!--\; \times \; -->n$ board:
(1) $1\times <!--\; \times \; -->1$ size with red color,
(2) $1\times <!--\; \times \; -->1$ size with blue color,
(3) $1\times <!--\; \times \; -->2$ size with black color,
(4) $1\times <!--\; \times \; -->2$ size with green color,
(5) $1\times <!--\; \times \; -->2$ size with white color.
Let W(n) be the number of ways to tile the $1\times <!--\; \times \; -->n$ board, $n=1,2,\dots <!--\; \dots \; -->$
For example, $W(1)=2$, $W(2)=7$.
What is the W(n) equation?

Discrete math practice problems
prove whether true or false
If $a^2$ divides $b^2$, then $a^3$ divides $b^4$
I think it is false because it is true that if $a^2$ divides $b^2$ then a divides b ,
and also true that if $a^2$ divides $b^2$ then $a^4$ divides $b^4$.
could anyone check this one?

(a) Suppose each single character stored in a computer uses eight bits. Then cach character is represented by a different sequence of eight 0's and l's called a bit pattern. How many different bit patterns are there? (That is, how many different characters could be represented?)
(b) How many bit patterns are palindromes (the same backwards as forwards)?
(c) How many different bit patterns have an even number of 1's?

Discrete Math problem
Let a,b be positive integers with $a<b$. Prove that for any natural number n, $a^n<b^n$.
I feel I should start with a base case $n=1$ which yields true since a is already less than b.
Next I would implement the induction hypothesis, but I'm kinda shaky on what that is.
After that I would check the $n+1$ case.
Could someone check and verify what I'm doing?

A racketeer is allowed to bring no more than 3 of the 7 lawyers representing him to a Senate hearing. How many choices does he have?
This is what I have done but the correct answer is 64. I'm not sure how to get that answer.
$C(7,3)=\frac{7!}{3!4!}=35$

Discrete Math (Logical Question)
How many arrangements of the letters in MISSISSIPPI have no consecutive S's?
Solution:
$(\genfrac{}{}{0ex}{}{8}{4})$ $\cdot <!--\; \cdot \; -->(7!/4!\cdot <!--\; \cdot \; -->2!)$

Discrete math counting.
Let $A=\{1000,1001,1002,\dots <!--\; \dots \; -->,9999\}$
How many numbers in A have the property that the sum of it's digits is even.
How many numbers in A have the property that the digits appear in increasing order? That is the first digit is smaller than the second and so on. Example 1234.

Find a generating function involving a tiling problem
Let $h_n$ be the number of ways to tile a $1\times <!--\; \times \; -->n$ rectangle with $1\times <!--\; \times \; -->1$ tiles that are red or blue and $1\times <!--\; \times \; -->2$ tiles that are green, yellow, or white. Find a closed formula for $H(x)=\underset{n\ge <!--\; \ge \; -->0}{\sum <!--\; \sum \; -->}{h}_n{x}^n.$
I am unsure how to start this problem. Is there a way to solve this without using recurrence relations?

Let G be a graph of two or more vertices. Prove by contradiction that
(All u,v vertices in G, $N(u)=N(v)$)
(All x vertex in G, $N(x)=$ {})
(Hint: N(u) denotes the neighbourhood of vertex u; i.e. N(u) is the set of every vertex v such that u and v are neighbours.)
Solution:
(All u,v vertices in G, $N(u)=N(v)$) and (Exist x, y vertices in G, $N(x)!=$ {} and so y is in N(x))
$=>\{N(x)=N(y)\}$
(Exist y vertex in G, y in N(y))
{from definition of neighbourhood: (All z vertex in G, not (z in N(z))}
F
I'm confused. It looks like the problem is telling me that each vertex in G shares the neighbourhood with each other vertex, that the graph is complete. From that I have to prove that for all vertexes in G, the neighbourhood is empty? I'm very confused, could someone explain the question better and walk me through the process?

Discrete Maths - Range of function
Let $X=\{a,b,c,d\}$ and $Y=\{1,2,3,4,5\}$ and define $f:X\to <!--\; \to \; -->Y$ by $f(a)=1$, $f(b)=2$, $f(c)=5$, $f(d)=2$.
Find the domain, codomain and range. If someone could explain this question in detail so i can do some revision on it.

Find a recurrence and appropriate initial conditions for the number of binary strings of length n in which every 0 is immediately preceded or followed by another 0, but not both.

Consider truth assignments involving only the propositional variables $x_0,x_1,x_2,x_3$ and $y_0,y_1,y_2,y_3$.
Every such truth assignment gives a value of 1 (representing true) or 0 (representing false) to each variable. We can therefore think of a truth assignment $\mathrm{\tau <!--\; \tau \; -->}$ as determining a four-bit integer $x_{\mathrm{\tau <!--\; \tau \; -->}}$ depending on the values given to $x_0,x_1,x_2$ and $x_3$, and a four-bit integer $x_{\mathrm{\tau <!--\; \tau \; -->}}$ depending on the values given to $y_0,y_1,y_2$ and $y_3$.
More precisely, with $\mathrm{\tau <!--\; \tau \; -->}(x_i)$ being the truth value assigned to $x_i$, we can define the integers $x_{\mathrm{\tau <!--\; \tau \; -->}}=2^3\mathrm{\tau <!--\; \tau \; -->}(x_3)+2^2\mathrm{\tau <!--\; \tau \; -->}(x_2)+2^1\mathrm{\tau <!--\; \tau \; -->}(x_1)+\mathrm{\tau <!--\; \tau \; -->}(x_0)$ and $y_{\mathrm{\tau <!--\; \tau \; -->}}=2^3\mathrm{\tau <!--\; \tau \; -->}(y_3)+2^2\mathrm{\tau <!--\; \tau \; -->}(y_2)+2^1\mathrm{\tau <!--\; \tau \; -->}(y_1)+\mathrm{\tau <!--\; \tau \; -->}(y_0)$
Write a formula that is satisfied by exactly those truth assignments $\mathrm{\tau <!--\; \tau \; -->}$ for which $x_{\mathrm{\tau <!--\; \tau \; -->}}>y_{\mathrm{\tau <!--\; \tau \; -->}}$. Your formula may use any of the Boolean connectives introduced so far. Explain how you obtained your formula, and justify its correctness
Am I right in assuming that I would need to construct a formula for every single possibility where x is the greater bit?

Let $X=\{1,2,3,\dots <!--\; \dots \; -->,100\}$, If eleven numbers are selected from X, show that there are at least two numbers u and v such that $0<<!--\; <\; -->|\sqrt{u}-<!--\; -\; -->\sqrt{v}|<<!--\; <\; -->1.$