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

0
votes
1answer
50 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
59 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
56 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
152 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
109 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
96 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
198 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
34 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
56 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 $f:\...
0
votes
2answers
85 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 fulfilling ...
2
votes
2answers
63 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
51 views

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

(Apologies for the poor quality) Thanks in advance!
0
votes
1answer
52 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)' = \begin{...
0
votes
2answers
84 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 $2$...
0
votes
1answer
71 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 ...
3
votes
3answers
80 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 to ...
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
54 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
84 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
486 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
361 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
88 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
37 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
136 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 able ...
0
votes
1answer
91 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
78 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 (i=0;...
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 it ...
-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
48 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?
0
votes
4answers
155 views

What is the probability of no 2 numbers being consecutive, if 5 numbers are randomly chosen from a set of 40 numbers?

If you randomly choose 5 numbers between 1 and 40 (inclusive), what is the probability that no two of the 5 numbers are consecutive?
0
votes
2answers
35 views

Proof By Induction for function

I am an undergrad Computer Engineering Student that is struggling through a class in discrete mathematics. One question in particular from a recent assignment has me stumped. Assuming that $T$ is a ...
0
votes
2answers
54 views

How many ways to place $n$ figures on an $n \times n$ chess board?

How many ways are there to place $n$ figures on an $n \times n$ chess board, if there are $n-k$ indistinguishable black figures and $k$ indistinguishable white figures in such a way that there is ...
2
votes
1answer
52 views

How many ways are there to put 'n' figures on a chess board?

How many ways are there to put n figures on an n x n chess board, if in at least one vertical row there are no figures? note: the figures are indistinguishable from each other
0
votes
1answer
48 views

How many ways are there to put n figures on a chess board? [closed]

How many ways are the to place n chess figures on an n x n chess board in such a way that in each row (horizontal) there is at most 1 figure? note: the figures are indistinguishable from each other.
0
votes
2answers
31 views

what is the chromatic index of this graph

I am trying to figure out the chromatic index of this graph. I thought that it is 4, however in the solutions that I have it says that the chromatic index is only 3. Which is the correct answer?
0
votes
0answers
22 views

begginer in quantified statements

so i stumble upon this proble on math discrete book by sussana and i dont know if my answer is correct so please check it for me assume that x and y is real for every X theres Y such that x^2 < y+...
0
votes
1answer
44 views

using the Greatest Common Divisor to find an integer.

I answered a question in my HW sheet and the last question was: Let g be the greatest common divisor of 9883529 and 759345. Find g using Euclid's Algorithm and find integers x and y so that g = ...
-1
votes
1answer
88 views

Show there exist gaps between primes which are arbitrarily large [closed]

Show that given any natural number $n$, there are two prime numbers $p$ and $q$ such that $q > p$ and $q - p \geqslant n$ , and all natural numbers strictly between $p$ and $q$ are composite (...
1
vote
2answers
24 views

Help with proof about primes

Show that, if $p$ is a prime number, then $\sqrt p$ is irrational. So far I have: FSOC assume $\sqrt p$ is rational where p, m, n are integers such that $\sqrt p = \frac{m}{n}$ where $n≠0$. WLOG $(...
0
votes
0answers
91 views

Graph coloring and prime numbers a not so fun mix

I have this assignment question and I was wondering if i could get some clarification from those more experienced then I. Let a be the number of ways in which C10 the cycle graph with 10 ...
0
votes
0answers
97 views

Chunk-Search Number of comparisons.

I never heard of chunk search before and my book barely talks about it. So, I am trying to understand how many comparisons are made. Given a ordered set of data, assuming we have chunks of 3. 1, 2, ...
2
votes
2answers
100 views

Bayes Theorem/Law of total probability question.

I'm having a hard time building intuition behind some Bayes Theorem/Law of total probability problems and understanding why my attempts are incorrect in the first place, for this question in ...
1
vote
1answer
21 views

Choosing between Conjunction and Implication

Let's say I want to express this statement using quantifiers : "For every two odd numbers, the sum of them is even." $\forall x,y \in \mathbb{Z}$ ( $(O(x)$ AND $O(y)$) $\rightarrow E(x+y) )$ ...