Questions on discrete mathematics generally: "the study of mathematical structures that are fundamentally discrete rather than continuous"
0
votes
1answer
18 views
Similar statements for expressions
Is there an easy way to find out which 3 are similar from the left and right side, it will be nice with some tricks to find it out, or if you have some rules that can be followed.
$$
{lg\,n +\frac12} ...
1
vote
2answers
87 views
what does the inverse membership symbol means?
I know that the symbol $$ \in $$ stands for membership, but what does the symbol $$ \ni $$ stand for?
Because I know that in the set membership, one symbol stands for subset and the other ones for ...
0
votes
0answers
22 views
Discretizing a cosine function?
I'd like to start by noting that for some fixed natural $N$ basis functions for my system will be generated by $f(k,x)$ as defined and explained here or in numerous other sources:
$$f(k,x) = \sqrt2 ...
2
votes
2answers
87 views
Sets Problem with Discrete Mathematics
I've been having trouble solving this problem and I have no clue where to go at this point. If anyone could help me out and explain along the way I'd appreciate it greatly.
Let $A,B,C$ be a sets. ...
3
votes
1answer
30 views
Interpretation of generating function infinite product
Let $P$ denote the set of primes and let $s\in\{-1,1\}$. How can you interpret the coefficient of $x^n$ in the power series expansion of $$\prod_{p\in P} (1+sx^p)^s$$
for either choice of $s$?
I ...
2
votes
1answer
29 views
Linear equation of 4 variables
I'm stuck on this Math problem :
How many solutions does the equation
$x_{1} + x_{2} + 3x_{3} + x_{4} = k$
have, where $k$ and the $x_{i}$ are non-negative integers such that $x_{1} \geq 1$, ...
1
vote
0answers
47 views
+50
Expansion vs Sparsest cut
let $G=(V,E)$ and $S\subsetneq V$ then expansion of set $S$ is
$$\alpha(S)=\frac{|E(S,\overline{S})|}{\min\{|S|,|\overline{S}|)\}}$$
where $\bar{S}=V\setminus{S}$ and $E(S,\bar{S})$ are edges ...
0
votes
0answers
9 views
simple trend measure/score
I am looking for a very simple (potentially ‘parameterisable’) measure to determine the trend of a discrete time series where the measurements are not necessarily equidistant. The output of the ...
3
votes
2answers
67 views
Proving that there are infinitely many prime numbers of the form $4k+3$
Anyone wanna help me solve this one? Been at it for a little bit but haven't really gotten anywhere..
1
vote
3answers
73 views
number of ways to make $2.00
How many different ways can you make $2.00 using only 1 cent, 5 cent, 10 cent, and 25 cent pieces, and 1 and 2 dollar bills (there are 100 cents in a dollar)? I have worked out an equation:
$$p + 5n ...
0
votes
2answers
34 views
Can anyone solve this discrete math proof?
A hint given was: What are the possible remainders for n after dividing by 4? Break into the cases where you have each remainder.
1
vote
1answer
35 views
Determining if this relation is an equivalence relation
$$R=\left\{(f,g)\,\Bigg|\, \exists c\in\Bbb Z,\forall x\in\Bbb Z, \frac{f(x)}{g(c)}\le 2\right\}$$
I can show that this relation is reflexive by showing that $(f,f)$ is in $R$
and so $f(x)/f(c) \le ...
0
votes
2answers
46 views
Words counting problem
What is the number of words, which are made by shifting all lower case letters in the english alphabet and none of them contains any of the four subwords (null, one, two, three)?
1
vote
1answer
37 views
Generating function question about arranging n objects with limitations
Generating functions question: There are n objects - rings, earring and bracelets. How many ways are there to arrange these objects, as the amount of earring is even and there are at most 4 bracelets.
...
1
vote
1answer
28 views
Generating functions combinatorical problem
In how many ways can you choose $10$ balls, of a pile of balls containing $10$ identical blue balls, $5$ identical green balls and $5$ identical red balls?
My solution (not sure if correct, would ...
0
votes
0answers
50 views
graphs where distance between every two vertices is $\geq$2.
Are there any class of graphs where distance between every two vertices is $\geq$2.
I was wondering about the existence of such graphs. Because for counter examples I have Paths $P_n$.
Thank you ...
0
votes
1answer
45 views
Venn diagram related question
An analysis of the survey of $320$ school pupils highlighted the following facts:
• $50$ pupils live in New Town, travel to school by bus and have canteen lunch.
• $110$ pupils live in New Town ...
1
vote
1answer
26 views
Prove that any circuit contains a cycle
This is a practice question (not HW)
Prove that any circuit in a graph must contain a cycle AND that any circuit that is not a cycle contains at least two cycles.
Note : This is for a first course ...
3
votes
2answers
51 views
Generating function: Find a closed form of $\sum_{k=0}^n (-3)^k(k+1)$
Find the closed form of $\sum_{k=0}^n (-3)^k(k+1)$.
So the generating function would be: $$A(x)=1-6x+18x^2-108x^3...$$ So what I did notice is that its closed form is perhaps some variation of ...
0
votes
2answers
182 views
Elementary Row Operations To Find Inverse Matrix
I have to find the inverse matrix of this matrix that represents a relation. My question is, is it possible to use elementary row operations on a one-zero matrix to find the inverse? I've done it ...
1
vote
1answer
20 views
How Entropy scales with sample size
For a discrete probability distribution, the entropy is defined as:
$$H(p) = \sum_i p(x_i) \log(p(x_i))$$
I'm trying to use the entropy as a measure of how "flat / noisy" vs. "peaked" a distribution ...
0
votes
3answers
49 views
Pigeon holes principle
Let $P$ be a group that it's elements are 257 sentences in which only atomic sentences from $A,B,C$ exist (i.e. $A \iff B,\space\space A \wedge B \wedge C, \space\space...$) Show that there exists two ...
1
vote
2answers
54 views
Is my solution correct? Generating functions question: How many non-negative solutions does the equation $x_1+x_2+x_3+x_4+x_5+x_6=12$ have?
so we began studying this subject, and I tried solving this question: How many non-negative and whole ($\in \Bbb Z$) solutions does the equation $x_1+x_2+x_3+x_4+x_5+x_6=12$ have?
I would like to ...
1
vote
1answer
27 views
Reflexive, $s$, $t$ relations
$A=\{1,2,3,4\}$. Determine with reasons whether $R$ is reflexive, symmetric or transitive.
$R=\left\{(1,1),(1,2),(2,1),(2,2)\right\}$
How is this done?
Reflexive must contain every element to ...
3
votes
1answer
24 views
How do I apply partial fraction expansion on $\dfrac{K}{(a+bz^{-1})(x+yz)}$?
I want to apply partial fraction expansion on $\dfrac{K}{(a+bz^{-1})(x+yz)}$. I'm not able to do it in the standard way, because one term has $z^{-1}$ term and the other has $z$. What is the approach ...
2
votes
0answers
72 views
Prime numbers problem - discrete math
Show that natural numbers of the form $n^2+1$ are not divisible by primes of the form $p=4k-1$.
I can't really find a place to start.
Thank you very much in advance,
Yaron.
1
vote
2answers
162 views
Discrete math: Euler cycle or Euler tour/path?
Could someone help explain to me how I can figure out if the graphs given are Euler cycle or Euler path? Is it through trial and error?
Here are some examples:
Would appreciate any help.
1
vote
2answers
48 views
Help solving recurrence relation, $a_n = 3a_{n-1} + 4a_{n-2} - 12a_{n-3}$
This is in my homework, and I am not sure how to go about this, I've read the book but I can't seem to grasp what to do. Help?
$$a_n = 3a_{n-1} + 4a_{n-2} - 12a_{n-3}$$
where $a_0 = 2$, $a_1 = -1$, ...
5
votes
4answers
83 views
Prove or disprove the following statements involving greatest common divisor
Help with prove or disproving either of these statements would be really appreciated, one or the other is fine, I just need a start or a solution to one and I'm sure I could probably figure the other ...
3
votes
2answers
55 views
Proving a statement about $k$-colouring of a graph
Prove that a graph is $k$-colourable iff its edges can be oriented in such a way that the resulting directed graph does not contain a path of length $k$.
It seems to me that the '$\Leftarrow$' ...
1
vote
1answer
17 views
Even weighted codewords and puncturing
My question is below:
Prove that if a binary $(n,M,d)$-code exists for which $d$ is even, then a binary $(n,M,d)$-code exists for which each codeword has even weight.
(Hint: Do some puncturing ...
2
votes
3answers
91 views
Prove$\overline{(A \cap B \cap C)} = \overline{A} \cup \overline{B} \cup \overline{C}$ By Subsets
This problem I am trying to solve is one I alluded to in this thread: Proving By Subsets
I am having difficulty with proof by subsets, so I am aware that I am missing steps; I would certainly ...
0
votes
3answers
265 views
Subtract 11011001 from (00100011 + 00001101) using 8-bit signed magnitude arithmetic
Subtract using 8-bit signed magnitude arithmetic 11011001 from (00100011 + 00001101 )
The result also should be signed magnitude format.
I do it like this
(+0 0001101 ) + (+0 0100011)=+0 ...
2
votes
5answers
67 views
Finding the number of non-neg integer solutions?
How would I find the number of non negative integer solutions to this problem?
$$x_1 + x_2 + x_3 + x_4 = 12$$ if $0 \leq x_1 \leq 2$.
2
votes
1answer
68 views
Solving a recurrence relation, $a_n = \sqrt{n(n+1)}a_{n-1} + n!(n+1)^{3/2}$
I'm trying to solve the following recurrence relation, but I have a problem with the factorial part. I would like to evaluate its particular solution.
I would like also to suggest a textbook for ...
5
votes
3answers
60 views
Solve the recursion, $a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$
Bring the following recursion relation to an explicit expression:
$$a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$$
$a_{0} = 0$, $a_1 = 1$, $a_2 = 2$
All the examples I have seen were with maximum 2 steps back ...
0
votes
1answer
36 views
find recursive solution $T(n)=2T(n/2)+n-1$
I want to solve this:
$$T(n) = 2 T\left(\frac{n}{2}\right) + n - 1 $$
I try :
\begin{align*}
n &= 2^m \\
T(2^m) &= 2T(2^{m-1}) + 2^m -1 \\
2 ^ m &= B \\
T(B) ...
0
votes
0answers
8 views
Closeness of a family of function under convolution.
I'm interested in functions defined over the non-negative integers that are a product of an exponential function and a polynomial. So a standard term of such a function is something like
$$
f(k) = ...
1
vote
1answer
19 views
Details about a Recurrence Relation problem.
I am trying to understand Recurrence Relations through the Towers of Hanoi example, and I am having trouble understanding the last step:
If $H_n$ is the number of moves it takes for n rings to be ...
0
votes
0answers
28 views
How do you calculate the angle of deflection of a plumb line towards a mountain?
How do you calculate the angle of deflection of plumb line being pulled down by the entire mass of earth, 5.89 x 10^24 kg and being pulled horizontally by the entire mass of mount everest, 6.399 x ...
13
votes
4answers
813 views
Are these 2 graphs isomorphic?
They meet the requirements of both having an = number of vertices (7)
They both have the same number of edges (9)
They both have 3 vertices of deg(2) and 4 of deg(3)
However, graph two has 2 ...
2
votes
3answers
63 views
Ball-counting problem (Combinatorics)
I would like some help on this problem, I just can't figure it out.
In a box there are 5 identical white balls, 7 identical green balls and 10 red balls (the red balls are numbered from 1 to 10). A ...
2
votes
2answers
85 views
How do you figure out what are all the possible numbers that four variables can be for a given N?
I know what I want to do but I do not know how to do it. This is complication that I have, there are four variables A, B, C, D which all are ≥ 1. So in the equation (A+B+C+D)=N where I know what N ...
1
vote
1answer
52 views
Set of natural numbers, for which the reunion of the sums of all subsets is a set
My math is weak so I'll try to clarify my question with an example. Consider the set $\{1,2,4\}$ for which the powerset $\{ \{\}, \{1\}, \{2\}, \{4\}, \{1,2\}, \{1,4\}, \{2,4\}, \{1,2,4\} \}$.
Now, ...
2
votes
2answers
45 views
Graph Theory adjacency matrix
Is it possible for a graph to exist that meets these conditions.
For Graph G the adjacency martix has all 1's in the first row and all 0's in the second row.
What I think: it cant exist because if ...
0
votes
1answer
57 views
Prove that the existence of a bridge is an invariant
An invariant is a property $P$ that is shared by all isomorphic graphs. In other words, a property $P$ is an invariant provided that whenever $G_1$ and $G_2$ are isomorphic graphs, if $G_1$ satisfies ...
54
votes
11answers
3k views
Zero to the zero power - Is $0^0=1$?
Could someone provide me with good explanation of why $0^0 = 1$?
My train of thought:
$x > 0$
$0^x = 0^{x-0} = 0^x/0^0$, so
$0^0 = 0^x/0^x = ?$
Possible answers:
$0^0 * 0^x = 1 * 0^x$, so ...
0
votes
1answer
30 views
Is there a formula to calculate the minimum height of an n-nary tree with L leaves?
I'm trying to figure out if there is a way to calculate the minimum height of an n-nary tree with L leaves. Is there such a formula?
9
votes
2answers
373 views
9 pirates have to divide 1000 coins…
A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins.
Arriving on a deserted island, they now have to split up the ...
-2
votes
2answers
60 views
Use the modular exponentiation algorithm to find $13^{277} \pmod {645}$
I need to solve this question using the modular exponentiation method.
