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
71 views

If an empty set is an element of a set, $\{5,\{\}\}$ is that equal to just $\{5\}$?

Is this true $\{5, \emptyset\} = \{5\}$? I know that the empty set is always a subset of any set, but when it's an element is that necessary to write in or not?
5
votes
2answers
1k views

Is $f(x) = (x + 1)/(x +2)$ a function?

My Disc Math book has the following problem: Determine whether each of these functions is a bijection from $\mathbb{R} \to \mathbb{R}.$ c) $f (x) = \frac{x + 1}{x + 2}$ Is $f(x) = ...
-6
votes
2answers
61 views

MATH PROBLEMS THIRD GRADE [closed]

Name the property? a+b=b+a 4+5=5+4
1
vote
1answer
28 views

Show the following: $a_{n-1} = a_{n} - ∇a_n $ and $ a_{n-2} = a_{n} - 2∇a_{n} + ∇^{2}a_{n}$

Show the following: $$a_{n-1} = a_{n} - ∇a_n $$ and $$ a_{n-2} = a_{n} - 2∇a_{n} + ∇^{2}a_{n}$$ -These two equations were presented to me in one single question and I am not sure where to go with ...
1
vote
1answer
39 views

Finding a Limit for Big Omega

I'm taking a discrete math course, and we were asked to prove that $2^n = \Omega(n^2)$. Trying to do that with big-Omega's limit definition, it leaves me with $\lim_{n\to \infty} \frac{n^2}{2^n}$. How ...
-1
votes
2answers
103 views

Use generating functions to solve $a_n = 6a_{n-1} - 8a_{n-2} + 3 $ and… [closed]

Use generating functions to solve: $$a_n = 6 a_{n - 1} - 8 a_{n - 2} + 3$$ With initial condition: $a_0 = 1$ and $a_1 = 0$ $$a_n = 3 a_{n - 1} + 4 a_{n - 2}$$ With initial conditions: $a_0 = 1$ ...
0
votes
1answer
107 views

Can you define a function f: N->N that is one-to-one and not onto?

The book 'Discrete Math and its Application' has the following problem: 20. Give an example of a function from N to N that is a) one-to-one but not onto. Is it ...
3
votes
1answer
32 views

Prove or Disprove: $m^2-n^2=2$ where m and n are integers. (Checking)

Prove or Disprove: The following statement: There are integers m and n such that $m^2-n^2=2$ Solution: $m^2-n^2=(m-n)(m+n)=2\times1$ Since 2 is a prime number, then Case 1: $m-n=2$ and $m+n=1$ ...
1
vote
1answer
69 views

Prove the following two statements about the Catalan numbers $C_n$

Prove the following two statements about the Catalan numbers $C_n$, $$ C_n \ge 2^{n-1} $$ and $$ C_n \ge \frac{4^{n-1}}{n^2} $$ for all all positive integers $n\ge1$. Which result is more precise. ...
1
vote
1answer
36 views

Prove that $a_{n-k} $ can be expressed in the terms of $∇a_n, ∇a_n, ∇^2a_n,…,∇^ka_n$

Prove that $a_{n-k} $ can be expressed in the terms of $$∇a_n, ∇a_n, ∇^2a_n,...,∇^ka_n$$ -I'm brand new to the del operator, and unsure of how to utilize it/ work with it in this proof, any help is ...
0
votes
1answer
28 views

Chvatal-Erdos theorem proof (that is hamiltonian)

Theorem. If G is hamiltonian then, for every nonempty proper subset $S$ of $V(G)$, we have: $k(G-S) \le |S|$ I need to proof that it works in the opposite direction. That If I find a subset $S$ that ...
0
votes
1answer
31 views

any example shows that coloring number does not equal to clique number? [closed]

Could you please show me any graph whose coloring number does not equal to its clique number ? Thank you in advance
0
votes
2answers
100 views

Proof by induction: $3^n > n^2$ for all integers greater or equal to 1

I have to prove that $3^n\geq n^2$ for all integers $n\geq1$ . This task is quite similar to other like the one given in 1, but with the difference that it has to be also valid for $n=1$. The usual ...
1
vote
2answers
48 views

Express $A \cup B$ in set buildier notation when $A=\{2n+1 \mid n \in \mathbb{Z}\}$ and $B=\{3n+2 \mid n \in \mathbb{Z}\}$

Express $A \cup B$ in set buildier notation when $A=\{2n+1 \mid n \in \mathbb{Z}\}$ and $B=\{3n+2 |n \in \mathbb{Z}\}$ We know that the rooster notation version of the union set is $A \cup B = ...
0
votes
1answer
49 views

Directed graph reduction

I know that in order to find a reduction of a directed graph, first of all we need to find all the strongly connected components of the graph. My question is, once we find all the connected components ...
0
votes
1answer
57 views

Determine the truth value for the predicate (logic)

Im not quite sure how to go about answering these type of questions as the difference of the universal and existential quantifier are confusing me. Hoping someone could explain how to go about ...
4
votes
3answers
53 views

Discrete Math: Finding the inverse of (natural) modulo (natural)

Basically the style of the question is like this: Find the inverse of $24$, modulo $35$. The answer I get is $-16$ whereas wolframalpha gets 19. I know that $35 - 16 = 19$. The question isn't ...
2
votes
2answers
144 views

Laws of logic Assertion/Reason format

I am taking a Discrete Math class and we have this question. $(B-A) \cup (C-A) = (B \cup C) -A$ Our section notes barely gloss over this, and Discrete Mathematics and Its Application, 7th ...
3
votes
2answers
103 views

is an empty set an element of {empty set}

I am on set section right now and I have questions about empty set is an empty set an element of {empty set}? is an empty set a subset of {empty set}? is an empty set a proper subset of {empty set}? ...
-2
votes
2answers
92 views

A' union B' equals B'? [closed]

what can I say about set A and B if A'U B' = B' the original question is why (A intersect B)' = B' what I did was I used the dem's law sol: (A intersect B)' = A'U B' and now I left with A'U ...
0
votes
0answers
30 views

solving recursively

The functions f : N → N and g : N^2 → N are recursively defined as follows: f(0) =1, f(1) =2, f(n) = g(f(n − 2),f(n − 1)) if n ≥ 2, g(m,0) =2m if m ≥ 0, g(m,n) =g(m,n − 1) + 1 ...
2
votes
1answer
169 views

How many six digit numbers start with the same two digits and end with the same three digits?

Say that there is a 6 digit number the first digit is not allowed to be 0 or 1 so How many number combinations start with the same two digits and end with the same three digits ie.119333, 448222, ...
0
votes
1answer
33 views

Determine the truth value of these predicates:

The domain for x, y, z is real numbers. i) $\forall x \exists y (y^2<x)$ FALSE counterexample: $x=0$ ii) $\forall x \exists y (y^3<x)$ TRUE iii) $\forall x\exists y \forall z ((y>0) ...
0
votes
2answers
54 views

Counter example to not surjective

I have to provide a counter example to show that the function $f\colon \mathbb{N} \to \mathbb{N}$ where $f(x) = x^2+4 $ is not surjective Would making the function natural number into integer ie ...
0
votes
2answers
84 views

Why do we use inclusion and exclusion here?

Determine the number of permutations of $\{1,2,...,9\}$ in which at least one odd integer is in its natural position. I know this question has been asked before. But nobody really had a ...
1
vote
2answers
61 views

Show $(A \cup B)\setminus(A \cap B) = (A\setminus B) \cup (B\setminus A)$

Show $(A \cup B)\setminus(A \cap B) = (A\setminus B) \cup (B\setminus A)$. What I have so far... This is (A or B) and (A and B)' = (A and B') or (B and A') (A or B) and (A' or B') = (A and B') or ...
1
vote
1answer
50 views

Is my 3-circle Venn diagram for this set correct?

(Apologies for the poor quality) Thanks in advance!
0
votes
1answer
51 views

Number of spanning trees using matrix tree theorem

$K_n$ denotes the complete graph with $n$ vertices. Show by means of the matrix tree theorem that the number of spanning trees of $K_n$ is $n^{n-2}$. I did something like this: $$(D-A)' = ...
0
votes
2answers
78 views

First Order Non-Homogeneous Linear Recurrence for Summation

I've been studying Linear Recurrences in the non-homogeneous case, but have gotten stuck with the following problem: Find a closed form for $s_n=\sum_{i=1}^n i$. I know the answer is $n(n+1)/2$ by ...
0
votes
2answers
47 views

What is the Symbolic definition of a function?

From what i understand, a function from set A to B: $F: A\to B$, exists iff for every element a∈A there exists exactly one element b∈A such that $f(a) = b$. Can this be expressed symboblically like ...
0
votes
1answer
30 views

Deriving a simple formula for $S(m,2)$

I need to derive a simple formula for $S(m,2)$ and these are the Stirling number of the second kind. My thinking is that we need to count the number of ways to distribute $m$ distinct objects onto ...
0
votes
1answer
68 views

Does the graph have an Euler's circuit?

Each of the following describes a graph. In each case answer yes, no , or not necessary to this question. Does the graph have an Euler's circuit? Justify your answer. a) G is a connected graph with ...
0
votes
1answer
27 views

Is this a good improvement on heaps?

I just wrote this paper: http://arxiv.org/abs/1510.03367 called "Layered Heaps Beating Fibonacci and Regular Heaps in Practice" which describes a recursively defined layered heap structure that ...
2
votes
3answers
74 views

How many functions $f : \{0,1,2,3\}^n \to \{1,2,3\}$ are there, that take the value $1$ exactly once?

How many functions $f : \{0,1,2,3\}^n \to \{1,2,3\}$ are there, that take the value $1$ exactly once? I know the answer to this question is $4^n \cdot 2^{4^n-1}$ but I don´t understand at all how ...
0
votes
1answer
39 views

Prove that a group of size $\ge18$ people can be assembled from groups of 4 and 7

How can I prove that a group of size $\ge18$ can be assembled from groups of $4$ and $7$ using the well ordering principle? Well-ordering principle: Every nonempty subset $T$ of $N$ has a least ...
2
votes
0answers
52 views

Partitioning functions into equivalence classes based on running time?

I'm studying for my midterm and doing some practice problems, and I would be grateful if someone showed how to solve this. From my understanding you have to partition the functions into equivalence ...
1
vote
2answers
82 views

Help with solving recurrence relations using iterative substitution

I need help solving these two recurrences with iterative substitution. I've looked at examples, and tried to follow them, but I just don't understand the whole plugging the recurrence into itself. I ...
0
votes
1answer
45 views

Proofing with predicate logic

Please solve this step by step. I have a test coming up and this is the only problem I cannot solve. Assume that the universe of discourse is the set of natural numbers. Let <(x,y) denote the ...
2
votes
2answers
467 views

What is the difference between automorphism and isomorphism of a graph in graph theory?

Please explain with an example the difference between automorphism and isomorphism of a graph.
1
vote
3answers
304 views

How to tell if a graph is bipartite?

So I have the following graphs drawn. How can I tell whether they are bipartite? If it is bipartite, how to identify 2 disjoint non empty sets?
1
vote
1answer
83 views

How to find the complement of the following graphs?

So G is a simple graph, the complement of G, denoted G' is obtained as follows: The vertex set of G' is identical to the vertex set of G. However 2 distinct vetices v and w of G' are connected by an ...
0
votes
1answer
36 views

Prove that $\overline{A\cap B \cap C}=\overline{A}\cup(\overline{B}-\overline{A})\cup \overline C$

How do you prove $\overline{A\cap B \cap C}=\overline{A}\cup(\overline{B}-\overline{A})\cup \overline C$? The only thing that seems clear to me is by deMorgan the LHS breaks down to $(\overline A ...
2
votes
2answers
40 views

e of a propositional function such that the statement ∃!x ∃!y p(x,y) is true but the statement ∃!y∃!x p(x,y) is false

Give an example of a propositional function such that the statement ∃!x ∃!y p(x,y) is true but the statement ∃!y∃!x p(x,y) is false (be sure to specify the domain for each variable)
0
votes
0answers
132 views

Finding The Radix of A Quadratic Equation

I have found previous solutions to finding the radix of a quadratic equation, where both of the provided roots return the same radix or base. However, unless I am some type of arithmetic error of ...
0
votes
1answer
27 views

$2a+5b=n$ - recurrence of the sequence

Find a recurrence for the sequence $u_n=$ number of nonnegative integral solutions of $$2a+5b=n.$$ I think I can use a generating function, but I'm a bit confused at this point. Is anyone is ...
0
votes
1answer
85 views

Understanding explicit bijection betweent wo sets

I'm having a lot difficulty understanding the concept of explicit bijection and how to show an explicit bijection between two sets. My professor rushed through the topic during class and now I'm ...
0
votes
1answer
77 views

Counting Iterations

I am given a question of such: How many floating point multiplications are performed when each of the following code fragments is executed? Express your answer in terms of n, where n >= 10. for ...
3
votes
3answers
84 views

Can we use derangements here?

Determine the number of permutations of $\{1,2,....,9 \}$ in which at least one odd integer is in its natural position. We have $5$ odd integers right, which is $1,3,5,7,9$ Now I think about ...
-3
votes
1answer
52 views

Prove that if H ∪ K is a subgroup of G… [duplicate]

Suppose G is a group, with subgroups H and K. Prove that if H ∪ K is a subgroup of G implies that H ⊆ K or K ⊆ H. I'm not really sure how to start this, I can prove that H ∩ K is a subgroup but I ...
0
votes
2answers
45 views

How many numbers in $\{2,3,…,360\}$ share at least one prime factor with $360$?

What is the best way to go about solving this question?