The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

learn more… | top users | synonyms

1
vote
3answers
26 views

Probability of an odd amount of sixes when rolling a 6-sided die 10 times.

Rolling a fair die 10 times, what is the probability it will give an odd amount of sixes? So the outcomes I'm interested in are: 1 six in 10 rolls or 3 sixes in 10 rolls or 5 sixes in 10 ...
0
votes
0answers
10 views

Prove $(x\vee y)\wedge (x\equiv y) \Rightarrow (x\Rightarrow y)$ using proof by hypothesis technique

I have this propositional calculus problem: Prove $(x\vee y)\wedge (x\equiv y) \Rightarrow (x\Rightarrow y)$ using proof by hypothesis technique. Solution: Teo.: $(x\vee y)\wedge (x\equiv y) ...
0
votes
0answers
21 views

How many ways to pile up boxes in a direction

Lets assume that there are columns with spesific limits, and there are boxes on these columns. We need to find all the possible ways(positions) from the original layout to the layout that completely ...
0
votes
2answers
33 views

Complexity of Discrete Mathematics algorithms

I'm new to decision maths and searching algorithms, but one thing I don't understand is how it's determined what complexity (in big-O notation) an algorithm is? For example, I've seen $O(2^n), ...
1
vote
3answers
36 views

What is the significance of using prime numbers in proving: $x$ is a multiply of $y$?

I came to a problem where it asks me to prove, for example, $n^4-n^2$ is a multiple of $12$. Now, factorize the multiple: $n\times n\times (n-1)\times (n+1)$. Here we have $3$ consecutive integers. ...
3
votes
1answer
33 views

How many ways we can choose items from different boxes

I searched through the internet but couldn't find my answer, which can either be a very simple or a hard one. Assume there are $3$ boxes, which carry, respectively, $1$, $4$, $2$ items. My question ...
1
vote
0answers
29 views

Find the minimum number of tickets to guarantee the win of a n-bit binary lottery?

Here's the problem. I just don't know how to approach it. If the 'one error tolerance' were removed, then this would be a simple binomial distribution problem. But now I can't figure it out. In ...
0
votes
0answers
15 views

Prove that $\operatorname{lcm}(ca, cb) = c\operatorname{lcm}(a,b)$ for positive non zero integers $a,b,c$. [duplicate]

Prove that $$\operatorname{lcm}(ca, cb) = c\operatorname{lcm}(a,b)$$ for positive non zero integers $a,b,c$. I'm in a first year discrete math course and the professor asked us to prove this. I'm ...
1
vote
2answers
30 views

Linear Recurrence - Form not familiar

To start off, I am not looking for the answers to this question, only a how-to. I would like to figure out the solutions myself, but I don't know where to start with this one. The form described was ...
0
votes
0answers
6 views

How does a DTFT relate to physical frequency?

After performing a DTFT and normalizing the frequency plot I ended up with the following figure The resulting data is correct, as the input signals were of 5kHz and 25kHz frequency. The part I am ...
2
votes
1answer
32 views

Shortest Path Via Dynamic Programming Formulation?

We have a directed Graph $G=(V,E)$ with vertex set $V=\left\{ 1,2,...,n\right\}$. weight of each edge $(i,j)$ is shown with $w(i, j)$. if edge $(i,j)$ is not present, set $ w(i,j)= + \infty $. for ...
0
votes
0answers
9 views

Examples of rules in the definition of function by Dirichlet

I'm reviewing Introduction to Mathematical Thinking course in Coursera, and I have a question about the definition of function by Dirichlet (Keith Devlin - Introduction to Mathematical Thinking [Page ...
1
vote
1answer
36 views

Prove fibonacci with matrixes [duplicate]

I have a question which i could not figure out the answer to, it was the hardest of them all that i got and i couldnt figure it out, its a proof of fibonaccis serie using matrixes and i need som help ...
0
votes
0answers
35 views

How to compute the original sequence given a DTFT?

Without directly performing an IDTFT, but by using the definition of the DTFT, how can one reverse the operation and compute the original input sequence producing a given DTFT? That is, Given ...
0
votes
3answers
18 views

Right way to show associativity.

Authors usually write that $*$ is associative on a set $S$ if, $a*(b*c)=(a*b)*c$ $\forall a,b,c \in S$ I think it should have been, $a*(b*c)=(a*b)*c=(a*c)*b$ $\forall a,b,c \in S$ I think the ...
1
vote
1answer
33 views

Finding the no of ways to count the letters in an English alphabet

How many strings of six lower case letters from the English alphabet contain a) the letter $a$? b) the letters $a$ and $b$? c) the letters $a$ and $b$ in consecutive positions with $a$ preceding ...
1
vote
1answer
27 views

Explicit piecewise linear approximation of a function of 4 variables

I have a table of numbers for fixed values of 4 parameters $x, y, z, t$, at this $x$ belongs to finite set of natural numbers, $y\in\{1;2\}$, $z\in\{5;10;15;20;25\}$ and $t\in\{1,2,3\}$. Is there a ...
0
votes
1answer
17 views

Calculating 5 different ranges for people resource management

I am working on a project for my company. My team is building a project charter template. In this template needs to be a drop down that estimates how many full-time employee days(FTE) will be ...
3
votes
1answer
45 views

Number of faces in a planar graph bounded by odd length cycles?

Suppose that every face in a planar graph is bounded by odd length cycles, then the number of faces of this planar graph is even. I want to prove this using Euler's formula, but not really sure where ...
1
vote
2answers
32 views

Proving that the binary relation defined by $xRy$ if $x \pmod{p} \equiv y \pmod{p}$, with $p \geq 2$, is an equivalence relation

Let $R$ be the binary relation on $\mathbb{N}$ defined by $xRy$ if $x \pmod{p} = y \pmod{p}$. Prove that, for $p \geq 2$, $R$ is a equivalence relation. Specify the equivalence classes of $R$. ...
1
vote
1answer
44 views

Prove that even $n$ can be partitioned to $\frac n2$ edges

I have to show that the edges of a complete graph on $n$ vertices for even $n$ can be partitioned into $\frac n2$ edge disjoint spanning trees. I know that a complete graph has $\frac{n(n-1)}{2}$ ...
1
vote
0answers
18 views

Factorial and $\Theta$ notation [duplicate]

If $N$ is a $n$-bit number, how many bits longs is $N!$, approximately in $\Theta( )$ form? I know that $$ \log(N!) = \log(N*(N-1)*...*2*1) \leq \log (N)+\log (N-1)+...+\log(2)+\log(1) $$ $$ ...
1
vote
1answer
46 views

Graph Theory Proof of Website Clicks [on hold]

Suppose we have n websites such that for every pair of websites $A$ and $B$, either $A$ has a link to $B$ or $B$ has a link to $A$. Prove or disprove that there exists a website that is reachable from ...
1
vote
1answer
35 views

A man has to paint n consecutive mile posts and wants to do this as inefficiently as possible…

I can't comment on this question A man has to paint n consecutive mile posts and wants to do this as inefficiently as possible... but I have further questions from this problem. Based on the most ...
1
vote
2answers
29 views

Trying to understand recursive definitions in discrete math

Consider the recursive definition of the natural numbers: Basis: $0 \in \mathbb{N}$ Recursive step: if $n \in \mathbb{N}$ , then $s(n) \in \mathbb{N} $ Give recursive ...
4
votes
2answers
92 views

Prove that a planar graph has four coloring

There is a theorem which says that every planar graph can be colored with five colors. It can also be colored with four colors. How can I prove that any planar graph with max degree of $4$, has a four ...
2
votes
2answers
38 views

Is it correct to say gcd$(r, 0)$? The definition says greatest common divisor of nonzero integers.

Source: Discrete Mathematics with Applications, Susanna. S. Epp In the definition of greatest common divisor of $a$ and $b$: $a$ and $b$ in gcd$(a, b)$ are nonzero integers, so why it follows in ...
0
votes
1answer
18 views

How to calculate time complexity?

You have a binary tree with n elements that is not in sorted order. What is the time complexity to find the smallest value? Explain. Say I have a binary tree of 5 is the parent of siblings (2 ...
1
vote
2answers
47 views

Big O notation: ratio of two $O(\cdot)$'s is $O(\cdot)$ of the ratio?

Is it true that if $f_1=O(g_1)$ and $f_2=O(g_2)$ then $$\frac{f_1}{f_2}=\frac{O(g_{1})}{O(g_{2})}=O\!\left(\frac{g_1}{g_2}\right)$$ ?
0
votes
0answers
25 views

Partial differential equations

​ My subject about the canonical form of PDE. I had many exercises to do and they were fine, but I'm stuck with this one: ​ ​ $Uxx−yUxy+xUx+yUy+u=0$ ​ ​ So first we have to calculate $B^2−4AC=y2−4​$ ...
0
votes
2answers
36 views

How is unique factorization of integers related to computing greatest common divisors?

Source: Discrete Mathematics with Applications, Susanna S. Epp. What does the unique factorization of integers have to do with gcd $2^{10}$ of ($10^{20}, 6^{30}$) in Example 4.8.5.b? ...
-3
votes
3answers
71 views

Prove that it is impossible to find integers $x, y$ with $2^x + 6 = 8y + 5$ [on hold]

Prove that it is impossible to find integers $x, y$ such that $2^x + 6 = 8y + 5$.
0
votes
0answers
15 views

Determining intersection number of $C_n+C_n$ and $\overline{C_n}$.

Is there a method to compute intersection numbers of graphs? For example, I would like to compute the intersection number of $C_n+C_n$ and $\overline{C_n}$, where $C_n$ is the $n-$cycle. I was trying ...
-2
votes
3answers
47 views

Proving that $6|n(n + 1)(n + 2)$ for any integer $n \geq 1$ [on hold]

I am having difficulty proving that $6|n(n + 1)(n + 2)$ for any integer $n \geq 1$. How can I go about this?
0
votes
1answer
23 views

Inference Rules, Not(P) Implies Not(Q) / Q Implies P

I do not understand Implication and Inference, I am going over the MIT Computer Science course and they have this part in their lecture notes, why is the second rule not a logical deduction? Can ...
1
vote
0answers
40 views

Proof: For every positive integer $n$, there is a sequence of $n$ consecutive positive integers containing no primes. [duplicate]

Let $x=(n+1)!+2$. I get how to prove that $x$ or $x+1$ is prime, but there is a step in my book that proves that $x+i$ is prime like this: $x+i=(1)(2)(3)(4)....(n+1)+(i+2)$. But then it factors out ...
0
votes
1answer
11 views

Prove $\langle x_0\rangle$ has only finitely many elements if and only if there exists $k_1$ and $k_2$ with $k_1 < k_2$ so that $x_{k_1} = x_{k_2}$

Prove that the orbit $\langle x_0\rangle$ has only finitely many (distinct) elements if and only if there exists $k_1$ and $k_2$ with $k_1 < k_2$ so that $x_{k_1} = x_{k_2}$ I know this to be true ...
-1
votes
1answer
51 views

Discrete Mathematics question regarding functions. [on hold]

Let $S = \{s_1,s_2,...,s_n\}$. How many functions are there with domain $S$ and target Z2? Of those functions, how many are one-to-one? How many are onto?
0
votes
2answers
20 views

Express each of the following statements as expression using quantified predicates and the domain“People.”

Here are two questions confused me. Express each of the following statements as expression using quantified predicates and the domain "People." 1) Some high school students are not enrolled in class ...
0
votes
1answer
21 views

Alternative methods to solve DLP for $GL_{3}(\mathbb{F}_2)$

Is there (or rather what is) a more elegant/efficient way to solve the DLP for $g^x=h$ in $GL_3(\mathbb{F}_2)$ where $$g=\begin{pmatrix}0 &1 & 1 \\ 1 &1 &1 \\ 1&0&1 ...
0
votes
0answers
53 views

Why are positive rational numbers countable but real numbers are not? [duplicate]

If we can say that any positive rational number is countable or listable by showing that every positive rational number is the quotient of p/q of two positive ...
2
votes
4answers
90 views

Prove the formula $\sum_{k=1}^n k\binom{n}{k} = n \cdot 2^{n-1}$ for all integers $n > 0$ [duplicate]

I just got to this question and I became a question mark. I wonder if anyone can help me with this one, because I don't even know how to begin to tackle this problem. The question: Prove the ...
0
votes
4answers
67 views

Explicit formula for $e_k = 4e_{k-1} + 5$

The sequence looks like this: $e_0 = 2$ $e_1 = 4(e_{1-1}) + 5 = 13$ $e_2 = 4(e_{2-1}) + 5 = 57$ $e_3 = 4(e_{3-1}) + 5 = 233$ $e_4 = 4(e_{4-1}) + 5 = 937$ How would I go about finding the ...
0
votes
0answers
4 views

Counting subgraphs of bounded extremal degrees

Let $m\leq n-1$. Is there a closed expression counting the subgraphs of minimum degree $\geq m$ (resp. maximum degree $\geq m$) on $n$ labelled vertices?
0
votes
1answer
89 views

Question regarding target space, one-to-one functions and onto

If I am understanding this correctly. We know $p_1$ has the domain of $A \times B$, where the first parameter of $p_1$ is an element of $A$, $p_1(a,b)=a$ where $a$ is an element of $A$. Since $B$ is a ...
3
votes
0answers
30 views

Properties of the Discrete Logarithm Problem

I am self-studying Hoffstein's An Introduction to Mathematical Cryptography, and this is problem 2.3 (p. 107-08). Let $p$ be a prime and $g$ an element in $\mathbb{F}_p^*$ with order $r$. ...
2
votes
0answers
27 views

Distribution of distinct object problem

So i was given this question. How many ways are there to place 10 distinct people within 3 distinct rooms with exactly 5 people in the first room and 2 people in the second room? So i asked this ...
0
votes
1answer
23 views

How can I find the maximum/minimum and maximal/minimal elements of a poset?

My teacher has given us really unclear definitions for all these terms, and now I have this assignment due where I have to find the maximum, minimum, and maximal/minimal elements of this poset: ...
4
votes
3answers
225 views

How many solutions for equation with simple restrictions

I'm working on an assignment in which I have to count the number of solutions for this particular equation: $$x_1+x_2+x_3+x_4=20$$for non negative integers with $x_1<8 $ and $x_2<6$ I'm aware ...
0
votes
1answer
14 views

Determining Whether or not a complex graph is bipartition?

So I asked a question earlier similar to this, and the solution made sense; however, the graph was very simple with only five vertices. If the graph is more complex like this one then how would you ...