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
1answer
25 views

Anti-symmetric if $AB= 1$ and $BA=0$ but every vertex has loops?

I'm creating a directed graph from an adjacency list. The $0$ present that there is no relation while the $1$ represent that there is. So i have a quick question regarding this. Lets assume that $AB ...
-1
votes
1answer
35 views

Excercise about Big-O notation [closed]

This is an exam question with the answers already released. I've been trying to read up about it, but it doesn't seem to make any sense to me, so I was hoping someone would point out why the correct ...
4
votes
2answers
64 views

Ordering of natural numbers

Show that it is possible to arrange the numbers 1, 2, . . . , n in a row so that the average of any two of these numbers never appears between them. Hint: Show that it suffices to prove this fact ...
1
vote
2answers
21 views

finding all solutions of an equation using counting

lets say I have $$ x_1 + x_2 + x_3 + x_4 = 17 $$ What are all the solutions for $$ x_i \ge 0? \quad \text{ where } i=1,2,3,4$$ How about if $$ x_i \ge 0 \text{ ?} $$ And if $$ x_i \gt 1 ...
0
votes
1answer
35 views

Purpose of Loop invariant

I have some small fairly easy questions regarding following procedure. My teacher has post some answers which I fairly understand but also have questions about. Note: I have taken a screenshot of the ...
-6
votes
1answer
35 views

can someone help me to answer this? [Mathematical expectation] [closed]

An attendant at a car wash is paid according to the number of cars that pass through. Suppose the probabilities are $\dfrac1{12},\dfrac 1{12},\dfrac 14,\dfrac 14,\dfrac 16$ and $\dfrac16$, ...
2
votes
2answers
55 views

mathematical induction proof of a square vs factorial

So lets say I have $$ n^{2} \le n! $$ For what positive integers is this not true? $n=2$ and $ 3$ Base case? $$n=4 \implies 16 \le 24 $$ What is the inductive hypothesis and how do I show the ...
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
19 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
37 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
35 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
27 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
26 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
22 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
64 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
83 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
78 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
54 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
54 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
55 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
42 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
42 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
50 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
62 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
32 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 ...
4
votes
1answer
36 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
60 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
32 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
48 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
35 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 ...