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
2answers
24 views
1
vote
1answer
27 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}$ ...
7
votes
5answers
372 views

How does advancing through the math major work?

I am an undergrad math major that just completed Calculus 3 last semester. This semester I signed up for Discrete Mathematics, and will be taking Intro to Advanced/Abstract Math next. Of course-- I ...
0
votes
0answers
15 views

Factorial and $\Theta$ notation

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) $$ $$ ...
0
votes
1answer
36 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
31 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
24 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 ...
3
votes
2answers
68 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
34 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
17 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
42 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
22 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
33 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
69 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
11 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
37 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
21 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
39 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
8 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
33 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
16 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
18 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
52 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 ...
3
votes
4answers
66 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
63 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
3 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
40 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
27 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
26 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
19 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
219 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 ...
0
votes
2answers
37 views

Algebraically transform logic expression

Algebraically transform: $\neg \forall x(P(x) \wedge Q(y) \implies \exists zR(z))$ to $\exists x\forall z(P(x) \wedge Q(y) \wedge \neg R(z))$ Justify each step with one or more ...
2
votes
2answers
53 views

How do I deal with a floor function is a system of equations?

How would one solve an equation with a floor function in it: \begin{cases} y=12(x-\lfloor x \rfloor) \\ x=12(y-\lfloor y \rfloor) \end{cases} Maybe an algebraic method could be used?
0
votes
0answers
23 views

License Plate Permutations

A state has changed its license plate numbering system for the three largest counties. Before the change, each plate had the number 1, 2, or 3, followed by either one or two letters, followed by 3 ...
1
vote
0answers
23 views

Determine whether or not $∀x[p(x) → q(x)]$ and $[∀xp(x)] → [∀xq(x)]$ are logically equivalent.

Determine whether or not $∀x[p(x) → q(x)]$ and $[∀xp(x)] → [∀xq(x)]$ are logically equivalent. I believe that they are not equivalent, but that is just an assumption. I am not sure how to go ...
0
votes
2answers
46 views

How many 10-digit decimal sequences (using 0, 1, 2, . . . , 9) are there in which digits 3, 4, 5, 6 all appear?

So i was given this question. How many 10-digit decimal sequences (using 0, 1, 2, . . . , 9) are there in which digits 3, 4, 5, 6 all appear? My solution below (not sure if correct) Let $A_i$ = set ...
5
votes
1answer
91 views

Why isn't finite calculus more popular?

I'm reading through Concrete Math, and learning about finite calculus. I've never heard of it anywhere else, and a Google search found very few relevant sources. It seems to me an incredibly powerful ...
0
votes
2answers
53 views

Prove or disprove: For non-negative integers $m$ and $n$, $m!n! = (mn)!$

I have rewritten the question as "If $m$ and $n$ are non-negative integers, then $m!n!$ = $(mn)!$" Here is my current attempt. I am not sure if I am on the right path. Proof. Let $m$ and $n$ be ...
1
vote
1answer
48 views

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 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? I have ...
1
vote
1answer
48 views

Discrete Mathematics - Perfect square proof with non-constructive approach. [on hold]

The questions reads the following: Prove that either $2 * 10^{500} + 15$ or $2 * 10^{500} + 16$ is not a perfect square using the non-constructive approach.
2
votes
1answer
28 views

Determining Whether or not a graph is bipartition?

So I have been trying to do research on this online, and all I see are a bunch of graphs with multicolored dots, and telling me to use those to determine if the graph is bipartition. The ones in the ...
-2
votes
1answer
24 views

Discrete Math Sequences (Graph or No Graph) [on hold]

Determine if there exists a graph whose degree sequence is the one specified. Draw a graph, or explain why no graph exists. The sequence is 5,4,3,2,1,1
-1
votes
2answers
53 views

Number of words of length $n$ on the alphabet $a,b,c$ recurrence. [on hold]

Let $a_{n}$ be the number of words of length $n$ on the alphabet $a,b,c$ such that $b,c$ are not adjacent. What is the recurrence relation for $a_{n}$.
1
vote
2answers
37 views

Discrete math induction proof

I am trying to solve a induction proof and i got stuck at the end, some help would be great. This is the question and what i did so far: Statement: For all integers $n \geq 5$ we have $2^n \geq n^2$. ...
1
vote
0answers
22 views

Small tree containing smaller trees

Given $n$, what is the smallest number $N=N(n)$ with the property that there exists a tree on $N$ (unlabelled) vertices that contains a copy of every tree on $n$ vertices? That such $N$ must exist is ...
3
votes
1answer
30 views

Inclusion exclusion principle questions i tried(doing it correct?)

$x_1+x_2+x_3\le10$ how many natural numbers solve this problem if $1\le x_1 \\ 2\le x_2 \\3\le x_3$ What i did: i created $y_1,y_2 , y_3$ so $\\ y_1=x_1-1 \\y_2=x_2-2\\ y_3=x_3 -3$ and then added ...
1
vote
1answer
34 views

How do I determine whether this relation is transitive?

I've been given this relation, and I'm supposed to determine whether it is transitive. I understand the definition of transitive (sort of, in theory) but I'm not sure how to put it in action here. ...
1
vote
3answers
62 views

How many different integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 21$ with restrictions

So i was Given this question. How many different integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 21$ $0 \leq x_i \leq 9$? I just assumed it would be ${21+4-4-1 \choose ...
2
votes
2answers
20 views

Why use C(n,r) instead of P(n,r) when considering how many strings can be formed in which a specific letter appears before another specific letter?

I am dealing with a problem in which I must determine how many strings can be formed by ordering the letters ABCDE subject to the conditions given. The condition that I am given is that A appears ...