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

Prove that there are no integer solutions x,y to the following system of equations using mod 4 arithmetic:

So i was given a question stated in the title and I have to show this for A)$2x+7y=3$ B)$3x+ 8y = 3$ C)$4x + 9y = 5$ I understand how to use the linear diophantine equation to solve these ...
1
vote
2answers
20 views

Multiple choice: $S = {x | 0 ≤ x < 280 ∧ x ≡ 3 (mod 7) ∧ x ≡ 4 (mod 8)}$

The question is: Consider the following set of integers: $$ S = \left\{x \left| 0 \le x < 280 ∧ x \equiv 3 \mod 7 ∧ x \equiv 4 \mod 8 \right. ...
0
votes
1answer
38 views

Transitive relation that I don't understand

I have a relation $S$ on $A = \{1, 2, 3, 4, 5\}$, which isn't transitive, and I don't get why. $S = \{(1, 1),(1, 2),(1, 4),(2, 1),(2, 2),(2, 3),(3, 2),(3, 3),(3, 4),(4, 1),(4, 3),(4, 4)\}$ According ...
0
votes
2answers
45 views

Modular of big numbers

I have this question which I have trouble comprehending. I am asked to find $$111 + 11113 + 1111115 \mod{11}.$$ Apparently, according the results the answer is 8. But I just can't see how. I have ...
0
votes
3answers
37 views

For any two sets A and B, if $f: A \rightarrow B$ is injective, then if A is countable, B must be countable.

So i was given two questions you either prove or disprove them. A) For any two sets A and B, if $f: A \rightarrow B$ is injective, then if A is countable, B must be countable. B) For any two sets A ...
1
vote
2answers
28 views

Setting up a probability formula

I'm having a tough time understanding how combinations and permutations work in complex question. The question goes like this: If a board of 12 people is to be selected randomly from a pool of 15 ...
0
votes
1answer
29 views

How to discretize in space with periodic boundary conditions

How to discretize this equation in space $$u''-ku'-m u=0$$ with BCs $u(\pm c)=u(0)$ ? I tried to discretize in space like so: $$x_j=jh$$ $$u''=\frac{u_{j+1}-2u_j+u_{j-1}}{h^2}$$ ...
1
vote
1answer
23 views

Determining Injectivity, surjectivity, bijectivity, and inverses

I was given a question that begins like this. Suppose that $A$ is the set $\{a,b,c\}$ (these are just names for some three elements - you don't know anything about $a,b,$ or $c$). Consider the ...
3
votes
3answers
26 views

solving negative linear congruences

OK so I know how to solve linear congruences when they're positive but negative is a different story.. I have $$ 200x\equiv 13 \pmod {1001} $$ I got the inverse as $$ -5 $$ and then I multiply both ...
1
vote
4answers
66 views

Prove by induction: for $n \ge 0$, $\frac{(2n)!}{n!2^n}$ is an integer [duplicate]

Another prove by induction question: for $n \ge 0$, $$\frac{(2n)!}{n!2^n}$$ is an integer Base step: $$n = 0$$ $$\frac{(2 \times 0)!}{0! \times 2^0} = \frac{0!}{1 \times 1} = 1$$ Induction step: ...
3
votes
4answers
84 views

Fibonacci proof question $\displaystyle \sum_{i=1}^nF_i = F_{n+2} - 1$

The sequence of numbers $F_n$ for $n \in N$ defined below are called the Fibonnaci numbers. $F_1 = F_2 = 1$, and for $n \geq 2$, $F_{n+1} = F_n + F_{n-1}$. Prove the following facts about the ...
-2
votes
2answers
79 views

Prove by induction $4^n > n^2$ for $n \geq 1$ [duplicate]

I am in a critical problem with the following question. Please help me. Prove by induction: $$4^n > n^2 \text{ for }n >= 1$$ Base case: n = 1 $$4^1 > 1^2$$ 4 > 1 which is true and for some ...
1
vote
1answer
33 views

Genus and faces of a graph

I am trying to determine the genus of a simple, undirected, connected graph using Euler's formula. However, I'm having trouble computing the number of faces of this graph: I seem to be confused ...
-2
votes
0answers
50 views

BIG OH:$ f (x) = 3x^3 + 2x + 4$. One has

I have this question in my homework. Its an a multiple choice question and goes as following: Let $f (x) = 3x^3 + 2x + 4$. One has that $O(x^3)$ ** the answers have been checked with the teachers ...
0
votes
1answer
25 views

Truth set with an implies statement and an intersection of family of sets equals everything?

Suppose $A_0 = \{1,2\}, B = \{2,3\}, F = \{A_0, B\}$. $\cap F = \{x | \forall A (A \in F \implies x \in A)\}$ I am confused over the truth set in the intersection of $F$ because if $A \notin F$ then ...
1
vote
2answers
57 views

Let $f : \mathbb{N} → \mathcal{P}(\mathbb{N})$ be given by $f(n) = \{n+1 , n+2 , n+3 , . . . \}$

So i was given a question like this Let $ f : \Bbb N\to \mathcal P(\Bbb N) $ be given by $f(n) = \{n+1 , n+2 , n+3 , . . . \}$ (a) Is f an injection? Explain (b) Is f a surjection? Explain. I ...
0
votes
2answers
38 views

Proof: $ A - (B - C) \subseteq (A - B) - C$

Question: Prove or disprove the following statements: For all sets $A, B, C$: a) $A - (B - C) \subseteq (A - B) - C$ b) $(A - B) - C \subseteq A - (B - C)$ c) If $A - (B - C) \subseteq ...
1
vote
2answers
35 views

difference between some terminologies in logics

$$1) \alpha_1,\alpha_2,\alpha_3.......\alpha_{k-2}, \alpha_{k-1}, \alpha_k\vdash\alpha $$ Is a valid sequesnt. $$2) \alpha_1,\alpha_2,\alpha_3.......\alpha_{k-2}, \alpha_{k-1}, ...
0
votes
0answers
23 views

Meaning of valid sequent in logics

If $$\alpha_1,\alpha_2,\alpha_3.......\alpha_{k-2}, \alpha_{k-1}, \alpha_k\vdash\alpha$$ Here $\alpha_i$ are premises and $\alpha$ is conclusion .If I prove that sequent is valid using given rules in ...
-1
votes
2answers
57 views

Fill in the blanks with either $∈$ or $⊆$

So was given a question that begins like this Let $A=\{ \emptyset , 1 , \{2\} , \{1 , 2\} \}$ . Fill in the blanks with either $\in$ or $\subseteq$ . $\{ 1 , \{2\} \}$______ $P(A)$ ...
1
vote
1answer
59 views

Probability generating function of bivariate Poisson distribution!

Problem setup: $X_1=Y_1+Y_0,X_2=Y_2+Y_0$ where $Y_1, Y_2\text{ and }Y_0$ are independent Poisson random variables with parameters $θ_1, θ_2\text{ and }θ_0$, respectively. I know that the joint ...
0
votes
2answers
45 views

Relations, Equivalence class

Define the relation $R$ on the set $\Bbb Z^+$ of all positive integers by: for all $a, b \in \Bbb Z^+$, $aRb$ if and only if the largest digit of a is equal to the largest digit of $b$. For example, ...
1
vote
3answers
45 views

Show $a+(a+d)+(a+2d)+\cdots+(a+nd)=a(n+1)+d\frac{n(n+1)}{2}$

Show $a+(a+d)+(a+2d)+\cdots+(a+nd)=a(n+1)+d\frac{n(n+1)}{2}$, where $a$ and $d$ are real numbers and $n$ is an integer. Attempt: I first added twice $$a+(a+d)+(a+2d)+\cdots+(a+nd)$$ to itself ...
1
vote
1answer
57 views

$\forall x \in \Bbb Q, \exists y \in \Bbb Q$ so that $x + y \in \Bbb Z $

Let $\Bbb Q$ be set of all rational numbers. Proof: $\forall x \in \Bbb Q, \exists y \in \Bbb Q$ so that $x + y \in \Bbb Z $ This statement is true. Here is a proof: Suppose $x$ is some rational ...
1
vote
5answers
56 views

For all sets $A$, $B$, and $C$, if $A-B \subseteq A - C$ then $ A \cap C = \varnothing $

Prove the statement P: For all sets $A$, $B$, and $C$, if $A-B \subseteq A - C$ then $ A \cap C = \varnothing $ My attempt to answer: This statement is true, and here is a proof: Proof: ...
2
votes
5answers
53 views

Prove that $(A-B) \cap (A-C) = A \cap (B \cup C)^c$ for any three sets A, B, C.

I was given a question that says Prove that $(A-B) \cap (A-C) = A \cap (B \cup C)^c$ for any three sets A, B, C. I'm completely lost with this question. In a previous question that says $A \cap C ...
0
votes
1answer
18 views

Linear Diophantine equation in two variables

So I was given a question to find if there is any integer solutions. $6x + 15y = 79, x,y \in \Bbb Z$ Proof $3(2x + 5y) = 79$ implies 3|79 which is absurd because no such x,y exist Then I was given ...
1
vote
2answers
49 views

Find all Functions so that $f(1) = 1$ and $f(2) = 2$

Let $F$ denote the set of all functions from $A=\{1, 2, 3, 4\}$ to $B=\{1, 2, 3, ..., 10\}$. Find and simplify the number of functions $f \in F$ so that $f(1) = 1$ and $f(2) = 2.$ My attempt to ...
3
votes
5answers
63 views

Find inverse of 15 modulo 88.

Here the question: Find an inverse $a$ for $15$ modulo $88$ so that $0 \le a \le 87$; that is, find an integer $a \in \{0, 1, ..., 87\}$ so that $15a \equiv1$ (mod 88). Here is my attempt to answer: ...
-2
votes
1answer
36 views

Show that the propositions r → s and ¬r ∨ s are equivalent

The question given in my homework is: Is r → s and ¬r ∨ s equivalent. - True or False The answer is True, I can't see the logic in how these can even belong together? Can anyone please clarify this ...
0
votes
2answers
27 views

Determining bijectivity of a function

I was given a function from $f: \Bbb R \rightarrow \Bbb R \\f(x) = x^5 - 3\\$ I know this function is bijective because it is one to one, and onto. Then the question changes to $f: \Bbb Z \rightarrow ...
0
votes
2answers
45 views

Number of $k$ subsets of $S$ by choosing $i$ elements from $A$ and $j$ elements from $B$ where $S=A \cup B$

Let $A$ be a set with $m$ elements and let $B$ be a set with $n$ elements. Let $S=A \cup B$. Then the number of $k$-subsets of $S$ is clearly $C((m+n),k)$. However, if we want the number of $k$ ...
2
votes
0answers
34 views

Reflexive, Symmetric, Transitive

Let $X = \{0, 1, 2, ... , 10\}$, Define the relation $R$ on $X$ by: for all $a, b \in X, aRb$ if and only if $a + b = 10$ Is R reflexive? symmetric, transitive? Give reasons. Here are my answers, ...
1
vote
2answers
28 views

Listing all elements of a set [duplicate]

I was given a question like the following: Let $A = \Bbb Z$, $B = [-1,\pi]$ , $C=(2,7)$. List all Elements of $A \cap (B^c \cap C)$. I do not really understand how to got about this problem. I ...
5
votes
1answer
40 views

Question on recurring decimal digits

In my discrete maths class, I have come across an interesting phenomenon for which I can't find an explanation! If we divide $1$ by $13$ we obtain $0.07692307\ldots$ If we divide $3$ by $13$ we ...
1
vote
1answer
49 views

Count Orbits and stabilizer

Let $X$ be the set $\mathbb{Z}_9\times \mathbb{Z}_9$ and let $U_9$ denote the group of invertible elements in $\mathbb{Z}_9$. The group $G$ acts on $X$ defined by $u(x,y)=(ux,uy)$ where $u\in U_9$ and ...
-4
votes
3answers
47 views

Math trinom help [closed]

$9x^2-9$ its like $(3x+3) (3x-3)$ what about $9x^2-35$ ?
0
votes
1answer
21 views

Determining the image of a function [duplicate]

I was given a function that says: What is the image of the function $F: \Bbb Z \times \Bbb N \rightarrow \Bbb R$ given by $f(a,b) = \frac{(a-4)}{7b}$ I need help really understanding how to find an ...
0
votes
2answers
61 views

Power set empty set confusion

So the question is Let $T = \{a,b\}$ and $S = \{Ø,\{Ø\}\}$. So what $i$ would assume would be the power set of $T$ is $\{\varnothing,a\}$, $\{\varnothing,b\}$, $\{a\}$, $\{b\}$, $\{a,b\}$. ...
0
votes
0answers
22 views

Minimum vertex cover of two edge disjoint perfect graphs

How well can the minimum vertex cover of the union of a perfect graph and bipartite graph (the two graphs are edge disjoint but not vertex disjoint) be approximated?
0
votes
1answer
34 views

Find a recurrence to count paths in a directed graph

Suppose we have an unweighted directed graph with vertices numbered as $1...n$ From each vertex $i$ there are edges to $i+1$, $i+2$ and $i+7$. My task is to find a recurrence $f(i,j)$ to compute the ...
2
votes
2answers
53 views

Prove or disprove: If the positive integer m divides the positive integer n, then the Fibonacci number $f_{m}$ divides $f_{n}$

I have $f_{n}=f_{n-1}+f_{n-2}; f_{n}= [0,1,1,2,3,5,8,13,21,34,55,89,144,233,...]$ for which I note that indeed, 2 divides 4, and $f_{2}$ divides $f_{4}$. I am wondering if a proof by induction is ...
0
votes
0answers
36 views

Soviet Optimization books

I am aware of an answer on Soviet math books here: Soviet Russian Mathematical Books and the book by Boris Polyak on non linear optimization. I am also aware of a few books by Kantorovich which I do ...
2
votes
1answer
72 views

How many subgraphs does $K_5$ have? [closed]

How many subgraphs does $K_5$ have and how can we prove the result is correct?
0
votes
0answers
16 views

How many nodes in a K-ary tree with L leaf nodes

Assuming that we have a k-ary tree with L leaf nodes, can the average number of nodes in the tree be calculated if we were to know the average number of children for each node? If not, what other ...
0
votes
1answer
25 views

Dijkstra’s algorithm / path is this done correctly?

im doing this assignment and it seems as if my teacher has made a mistake. according to me in order to find the minimum spanning treee from a-z , you start from a and then go to : a,f,d,c,b,e,z,g ...
1
vote
0answers
14 views

Minimum vertex cover of vertex disjoint odd holes and antiholes

I am interested in knowing whether the minimum vertex cover of a graph that can be written as the union of vertex-disjoint odd holes and odd antiholes can be found exactly, in polynomial time. I could ...
3
votes
3answers
36 views

reflexive, symmetric, and transitive relations proof

Let $A = \{1, 2, 3, ... , n\}$ where $n$ is a positive integer. Let $F$ be the set of all functions from $A$ to $A$. Let $R$ be the relation on $F$ defined by: for all $g, f \in F, fRg$ if and only ...
-4
votes
1answer
34 views

Proof reflexive, symmetric and transitive relations

Let $A = \{1, 2, 3, ... , n\}$ where $n$ is a positive integer. Let $F$ be the set of all functions from $A$ to $A$. Let $R$ be the relation on $F$ defined by: for all $g, f \in F, fRg$ if ...
3
votes
3answers
50 views

What is the probability of rolling a 6-sided die 5 times, and getting at least 3 in a row?

I had been working on this problem, and ran into trouble because I couldn't easily use the "find the opposite probability and subtract from one" trick. So for example I think I can find the ...