Questions on discrete mathematics generally: "the study of mathematical structures that are fundamentally discrete rather than continuous"
0
votes
1answer
42 views
How many ways are there to sit $n$ couples on a bench when every couple sits together?
How many ways are there to sit $n$ couples on a bench with $2n$ sits, when every couple sits together?
How many ways are there to sit the couples so that none of the couples will sit together?
3
votes
2answers
52 views
Proving if a relation is an equivalence relation
I have been able to figure out the the distinct equivalence classes. Now I am having difficulties proving the relation IS an equivalence relation.
$F$ is the relation defined on $\Bbb Z$ as follows: ...
1
vote
3answers
67 views
Equivalence Relations: Equivalence Classes
From my basic understanding $R$ is an equivalence relation on the set $A$, which is
a relation between elements of a set that is reflexive, symmetric, and transitive.
I am not sure how to find the ...
2
votes
1answer
66 views
$\chi(G) \cdot \chi(\bar{G})\geq n$ [duplicate]
Prove that $\chi(G) \cdot \chi(\bar{G})\geq n$
$\chi(G)$: number of colors required for a graph $G$.
Here $\bar{G}$ is a graph that consists of all the edges that are not in $G$.
0
votes
0answers
36 views
Discrete math: mathematical induction [duplicate]
Im having trouble doing this assignment with a given restriction
Show that n lines separate the plane into $\frac{n^2 + n + 2}{2}$
regions if no two of these lines are parallel and no three
pass ...
0
votes
1answer
17 views
Stability of nonlinear planar map fixed points.
Got the map:
$$x_{n+1} = x_ne^{2-x_n-y_n}$$
$$y_{n+1} = y_ne^{x_n-1}$$
I found the fixed points (0,0), (2,0), (1,1).
For the stability I have the Jacobian to find eigenvalues as:
$$J = ...
0
votes
2answers
65 views
Evaluating Line Integrals!
$3xy^2dx+2x^3dy$
where is the boundary of the region between the circles $x^2+y^2=25$ and $x^2+y^2=64$ having positive orientation.
Not quite sure how to evaluate this...
0
votes
4answers
35 views
Summation of n-squared, cubed, etc. [duplicate]
How do you in general derive a formula for summation of n-squared, n-cubed, etc...? Clear explanation with reference would be great.
0
votes
1answer
22 views
Sum of series with generic term inside it
I have the following series:
$$
\sum_{k=0}^{+\infty} k \cdot a^k \cdot s_k
$$
Having $|a| < 1$ and where $s_k \in [0,1]$ is a generic sequence having the property for which $\lim_{k \to ...
2
votes
2answers
47 views
difference between “minimal” and “minimum” edge cuts.
I was going through the topic about connectivity of graphs. There it was mentioned about the terms "minimum edge cut" and "minimal edge cut". I know both are the sets of edges if removed from the ...
2
votes
2answers
44 views
New to generating functions - how do I get the function from the sequence defined by $a_n= n$ for $n\geqslant 0$?
I'm given: $a_n= n$ for $n \geqslant 0$.
I'm quite good at recursive generating functions, but I haven't came across a simpler one like this, so I'm sure I'm just overlooking something really basic.
0
votes
0answers
127 views
Turing Machine question, this is NOT HW
I was having a hard time understanding and solving this question that wants me to show the final tape and figuring out if whether or not the turning machine accepts it or not. I have a list of 20 ...
2
votes
0answers
21 views
how the number of steps needed depends on the number of nodes and depends on the transmission range?
I run the consensus algorithm, and for each round k, we record the norm of the disagreement vector(|(|δ(k)|)|>〖10〗^(-6)). We stop, at a predefined value|(|δ(k)|)|>〖10〗^(-6) and we call this ...
2
votes
4answers
61 views
Binomial Coefficients for $(x+1)^4$
Find $(x + 1)^4$ using binomial coefficients.
I'm confused as to how to start this, as I thought binomial coefficients were things like $9 \choose 2$.
0
votes
2answers
43 views
Finding Integers With Certain Properties.
How many positive integers between 100 and 999 inclusive
e) are divisible by 3 or 4?
For this problem, I understand that one has to employ the inclusion-exclusion principle.
Those integers ...
4
votes
6answers
88 views
Prove $7|x^2+y^2$ iff $7|x$ and $7|y$
The question is basically in the title: Prove $7|x^2+y^2$ iff $7|x$ and $7|y$
I get how to do it from $7|x$ and $7|y$ to $7|x^2+y^2$, but not the other way around.
Help is appreciated! Thanks.
2
votes
1answer
44 views
self-centered property of complement of a self-centered graph
I was working out on a problem. Came out with a result that $C_n$ is self centered graph, its complement is also self centered, infact 2-self-centered. Worked out on other few graphs which are self ...
2
votes
3answers
111 views
Showing that no Hamilton Circuit exists
I was confused about a certain concept and I was wondering if I could get some help.
There were three points that were made in my textbook to show that a graph does not contain a Hamilton circuit:
...
1
vote
3answers
44 views
Can someone check the solution to this recurrence relation?
Here's the recurrence relation: $a_n = 4a_{n−1} − 3a_{n−2} + 2^n + n + 3$ with $a_0 = 1$ and $a_1 = 4$
Here's the solution:Write:
$$
a_{n + 2} = 4 a_{n + 1} - 3 a_n + 2^n + n + 3 \quad a_0 = 1, a_1 = ...
0
votes
2answers
42 views
Finding this solution to a recurrence relation
So, I know that the recurrence relation $a_n = 4a_{n−1} − 3a_{n−2} + 2^n + n + 3$ with $a_0 = 1$ and $a_1 = 4$ has the solution of $a_n = -4(2^n) - n^2 / 4 - 5n / 2 + 1/8 + (39/8)(3^n)$. I just ...
3
votes
2answers
173 views
Detect double error using Hamming code.
I have a sequence of bits
$$
111011011110
$$
and need to detect two errors(without correction) using Hamming codes. Hamming codes contain a control bit in each $2^n$ position. Hence I should put this ...
1
vote
1answer
50 views
Triangle tiling proof
How to prove that the number of triangles in the tiling below can be found by the formula
$$\left\lfloor\frac{n(n+2)(2n+1)}8\right\rfloor\;,$$
where $n$ is the number of vertical layers? (For the ...
0
votes
1answer
22 views
How to show all solutions for a particular recurrence solution
I've found that the recurrence relation $a_n = 4_{an−1} − 4a_{n−2} + (n + 1)2^n$ has the solution of $an = 2^n(p_0 + p_1n + n^2 + n^3/6)$. I'm just trying to understand the steps necessary to solve ...
0
votes
3answers
42 views
Relations: Reflexive, symmetric, transitive
I am having difficulties determining if this relation is reflexive, symmetric, transitive, or none of these.
Let A be the set of all strings of $0's$, $1's$, and $2's$ of length $4$. Define a ...
1
vote
2answers
35 views
Prove all eigenvalues of $A^*A$ are non-negative
Let $A$ be an $m\times n$ matrix. Prove that all eigenvalues of $A^*A$ are non-negative.
1
vote
2answers
48 views
Find the recurrence solution of this relation
How would we find the solution of the recurrence relation: $a_n = 2a_{n−1} + 3 · 2^n$ ?
After trying it, I've found it to be $a_n = 2^{n-1} (c_1 + 6n)$
Not sure if this is right..
Thanks!
0
votes
1answer
22 views
Weak Compositions with Size Restrictions
I have a number of elements and I'm trying to place them into boxes but one of the boxes has a restriction on the number of elements that can be placed into it, how do you account for that in the weak ...
1
vote
2answers
46 views
Discrete Logarithm
If $p$ is a prime and $a,b$ are integers not divisible by $p$ such that $a^x \equiv b \pmod p$ with $0 ≤ x < o_p(a)$, then we define $x = L_a(b)$ and say $x$ is the discrete logarithm of $b$ ...
1
vote
1answer
53 views
Graph with closed path of length $\leq 4$.
Assume $G=(V,E)$ with $\forall v \in V: \deg(v) \geq d$ and $d \geq 2$ such that $|V|= d^2$. Then there is a closed path of length $\leq 4$ in $G$.
Some hints would be helpful :)
2
votes
1answer
33 views
I need to prove a formula but I'm not sure how
I'm working on a problem with the goal of finding a general formula and proof for the number of ways to arrange a string of 2n bits so that the number of 1's is strictly greater than the number of 0's ...
0
votes
1answer
33 views
Prove that: $2^{n+1}|k^{2^n}-1$
Let's denote that $k$ is an odd number and $n\in \mathbb{N}$. Prove that:
$$2^{n+1}|k^{2^n}-1$$
Could you give me any HINT how to start with this?
2
votes
2answers
43 views
Numbers that are divisible
So I am given the following question: For natural numbers less than or equal to 120, how many are divisible by 2, 3, or 5? I solved it by inclusion-exclusion principle and by using the least common ...
0
votes
2answers
53 views
Proof of a little-oh growth function.
Prove that $n^{2.5} \in o(1.1^{n})$.
Prove using limits. That: $$\lim_{n\to\infty} \left(\frac{f(x)}{g(x)}\right) = 0$$
Thanks!
2
votes
2answers
50 views
Finding the solution to this specific recurrence relation
What would be the solution to $a_n = 7a_{n−2} + 6a_{n−3}$ with $a_0 = 9$,
$a_1 = 10$, and $a_2 = 32$
I can find it for a specific value of (n), but not for just a general solution. Thanks!
1
vote
1answer
52 views
Counting problems
1) A businessman has 10 suits. He needs to pack 3 of them to go on a trip. How many can he do this?
2) A multiple choice test has 8 questions, each with 3 possible answers. how many can the test be ...
1
vote
1answer
40 views
A bijection between certain sequences and functions
Let $n$ be a natural number. I let define $S_n$ to be number of all possible final results at a competition where ties are possible. More precisely $S_n$ is the set of all functions $f:[n]\to [n]$ ...
1
vote
3answers
55 views
Inclusion and Exclusion Secret Santa
If I am having a "secret santa" gift exchange with 5 people, how many possibilities for gift exchanges are there if nobody ends up with the same gift?
The answer could be $5!$ , but I don't think it ...
-1
votes
2answers
52 views
Pigeonhole Principle
Explain the following using Pigeonhole Principle is it is true:
1) If we choose 10 points in a $3 x 3$ inch square, there must be two points of the 10 which are at distance less than or equal to ...
0
votes
3answers
26 views
Recurrence relation of two next terms
For the recurrence relation, $a_{n+2}=3a_{n+1}-2a_n$ with $a_0=2$ and $a_1=3$, compute the first six terms of the sequence and derive a closed form formula for this sequence.
So I'm totally lost with ...
2
votes
3answers
71 views
Counting 1:1 and onto functions
I'm faced with the following questions:
1) How many functions are there from a set of size 3 to a set of size 5? How many of them are 1-to-1?
2) How many functions are there from a set of ...
1
vote
0answers
34 views
Proving a specific recurrence relation theorem
I'm trying to come up with a proof for this theorem:
Let $c_1$ and $c_2$ be real numbers with $c_2 != 0$. Suppose that $r^2 - c_1 r - c_2 = 0$ has only one root, $r_0$. A sequence $\{a_n\}$ is a ...
2
votes
3answers
84 views
Odd/Even Permutations
How do you classify a permutation as odd or even (composition of an odd or even number of transpositions)? I somewhat understand the textbook definition of it but im having hard time conceptualizing ...
2
votes
1answer
34 views
Unordered Sample With Repetition
Out of 19 different choices, I am supposed to choose 25 items. This is ${\binom{19+25-1}{25}} = {\binom{43}{25}}$. However, if two of the items cannot be chosen with repetition, how do I solve this?
...
1
vote
2answers
44 views
Finding a solution to a recurrence relation
Find the solution to $$a_n = 5a_{n−2} − 4a_{n−4}$$ with $$a_0 = 3$$
$$a_1 = 2$$ $$a_2 = 6$$ $$a_3 = 8$$
My answer: Observe that the degree of recurrence is 4. Hence, the characteristic equation is: ...
3
votes
1answer
41 views
Finding a Linear Recurrence Relation
A model for the number of lobsters caught per year is
based on the assumption that the number of lobsters
caught in a year is the average of the number caught in
the two previous years.
...
1
vote
0answers
73 views
Is this theorem proof correct?
I'm trying to prove this theorem:
Let $c_1$ and $c_2$ be real numbers with $c_2 \ne 0$. Suppose that $r^2 − c_1r − c_2 = 0$ has only one root $r_0$. A sequence $\{a_n\}$ is a solution of the ...
0
votes
2answers
40 views
Determination of Functions, 1:1, and Inverse
For the following relations, I need to answer: 1) Is it a function? If not, explain why and stop. Otherwise, 2) What are its domain and image, 3) Is the function 1:1. If not, explain why and stop. ...
0
votes
1answer
21 views
discrete random variable PMF
suppose You rented a house and realtor gave you 5 keys, one for each of the 5 doors of house. unfortunately all keys look identical. so to open the front door, you try them at random.
=> Find the ...
2
votes
2answers
46 views
Recurrence Relations for $c_1$ and $c_2$
For the following recurrence relation: $a_n = 3a_{n-1}+4a_{n-2}$, where $a_0=3$ and $a_1=2$ I solved it using quadratic equation by $x^2+3x-4$. So I got to $a_n = 4^nc_1 + c_2(-1)^n$. Now to find ...
1
vote
0answers
52 views
Chernoff Bounds. Solve the probability
Toss $n$ coins. What is the probability that we get more than
$$
n/2 + 2\sqrt{n\cdot \log(n)}.
$$
I have to use Chernoff Bounds here.
If I let
$X_i$ indicate whether coin $i$ comes up heads,
...
