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

What can be said about $A$ if $P(A) = \{ \emptyset, \{x\}, \{y\},\{x,y\}\}$

What can be said about $A$ if $P(A) = \{ \emptyset, \{x\}, \{y\},\{x,y\}\}$ I'm not entirely sure what this question is asking, but here is what I would assume my answer should be: $A=\{x, y\}$ Am ...
2
votes
2answers
33 views

Next step in proof of sets

Proposition to prove : (A-B)∩(B-A) = 0 So, I understand why this is 0, I'm just not sure what propositions should be used in proving so. I have this so far 1)(A-B)∩(B-A) :Premise ...
1
vote
1answer
30 views

Triangulating a convex Catalan Numbers.

Problem: Let $t_n$ denote the number of ways of triangulating a convex $(n+2)$-gon by drawing $n-1$ diagonals. Show that $t_n=C_n$ as follows. Label the vertices $1,\ldots,n+2$, and consider the ...
0
votes
1answer
36 views

finding probability of X and Y by given joint PMF

Let random variables X and Y have the joint PMF $\mathsf p_{X,Y} (x,y)$ given below. $$\mathsf p_{X,Y} (x,y) = \begin{cases}0.05 & : x=1,2,3,4 \land y=1,2,3,4\\ 0 & ...
2
votes
2answers
38 views

Use modular arithmetic to show that a number is divisible by 11 iff the sum of its alternating digits is divisible by 11

We can expand the number $n = n_0 + 10n_1 + ... + (10^s)n_s$ Then we have $10^k ≡ (-1)^k \mod11$. How do we go from here to here: $n ≡ n_0 - n_1 + ... + (-1)^s n_s \mod 11$ I do not understand ...
1
vote
2answers
77 views

Describe the following set by giving a characteristic property $\{1, 3, 5, 7, 9, 11, …\}$

Describe the following set by giving a characteristic property $\{1, 3, 5, 7, 9, 11, ...\}$. The book I'm reading doesn't describe how to do this, but do I basically need to describe the pattern I ...
1
vote
1answer
33 views

Cardinality of the power set $\mathcal P\left(S\right),$ where $S$ is a set of $15$ elements?

What is the cardinality of the power set $\mathcal P\left(S\right)$ where $S$ is a set of $15$ elements? I think the power set is a set of all the subsets of a given set or $2^n$. So would the ...
1
vote
1answer
92 views

Proving function statement true or false

I am trying to determine if the following statement is true or false. Please can you help and tell me why it is the case. If $f:\mathbb{N}\rightarrow \mathbb{R}^{+}$ and $g:\mathbb{N}\rightarrow ...
0
votes
1answer
29 views

Prove a function

Let $f(n)$ and $g(n)$ be arbitrary functions from $\mathbb{N}$ to $\mathbb{R}^{+}$. Prove the following: $$\max\left \{ f(n), g(n) \right \} = \Theta (f(n)+g(n))$$ Please help me prove (or disprove) ...
3
votes
5answers
2k views

If $p$ and $q$ are prime numbers larger than $2$, then $pq + 1 $ is never prime

I am trying to prove the following: If $p$ and $q$ are prime numbers larger than $2$, then $pq + 1 $ is never prime. Any ideas?
0
votes
2answers
43 views

Prove the result is always a rational number

I am trying to prove the following: If $a$ and $b$ are non-zero rational numbers, then $a^{b}$ is rational. Any ideas or hints how to prove this?
0
votes
1answer
37 views

Proving function complexity

I am trying to prove the following: Let $$f(n)=\sum_{i=2}^{n}\frac{1}{i \log i} $$ Where log denotes the natural logarithm. Show that: $$ f(n)=\Theta (\log \log n)$$ I am not sure how to go about ...
1
vote
1answer
85 views

Proving congruence class

Let $a$ and $m$ be integers such that $m ≥ 1$. Consider the congruence class of $a$, $[a]$ modulo $m$. It follows that $∀ x ∈ [a], \gcd(x, m) = \gcd(a, m)$. I have my algebra midterm in two ...
0
votes
1answer
47 views

Integer representation of a (fraction) modulo (integer)?

Is there an integer that would satisfy an expression that looks like (fraction) MOD (int)? For example, if we have the expression (1/5) MOD 10, could this expression have an integer result? If so, ...
1
vote
1answer
237 views

Lattice of a POSET Realtion

Given a set $S=\{1,2,3,4,5,6,7,8\}$, defined by a partial order relation Divisibility. Now consider all 4 elements containing sub-graphs, out of which $\{1,2,4,8\}$ is a Lattice obviously . Is ...
1
vote
1answer
62 views

How to establish a bijection

The question: Show that the function $f : \mathbb{R} − \{−1\} → \mathbb{R} − \{2\}$ defined by $f(x) = \dfrac{4x + 3}{2x + 2}$ is a bijection, and find the inverse function. How would I establish ...
-3
votes
1answer
36 views

Matrices, Sets, Relations

I have the solution I still don't get it, does anyone know where 15*9 come from ?
1
vote
2answers
42 views

Clarification of the notation $f: \mathbb{R} \setminus\{3\} \to\mathbb{R}\setminus\{2\}$

I have a question that uses the following notation: the function $f: \mathbb{R} \setminus\{3\} \to\mathbb{R}\setminus\{2\}$ is defined by $$f(x)=\frac{2x-3}{x-3}.$$ I understand that the left side ...
0
votes
3answers
232 views

How many 7-digit ID numbers do not contain three consecutive sixes.

I have a homework question in a discrete mathematics class that asks me to determine how many 7-digit id numbers do not contain three consecutive sixes. It seems clear that I should approach this by ...
2
votes
5answers
139 views

How to give a good guess to the recurrence relation problem [duplicate]

I have been trying to solve the following recurrence relation $$T(n)=2T(\frac{n}{2}) + nlgn$$ by using substitution method. I started to compute $T(1)$ ,$T(4)$,$T(8)$,$T(16)$ to guess a solution as ...
3
votes
2answers
229 views

some combinatorial proofs

These were simple induction proofs, so I decided to try and prove them combinatorially. I think I nailed the first one, not so sure about the second one. $\sum_{i=1}^n(i)(i!)=(n+1)!-1$ Have $n+1$ ...
1
vote
1answer
78 views

Maximise the product of $k$ integers such that the sum is $n$

Maximise the product of $k$ integers such that their sum is $n$ The solution for two integers, I think, $a + b = n$ is $a = \lfloor{n/2}\rfloor$ and $b = n-a$ For $k$ integers,I think that there ...
2
votes
2answers
56 views

Discrete Math Proof Method

Give a direct proof of the fact that $a^2-5a+6$ is even for any integer $a$. Suppose $a$ and $b$ are integers and $a^2-5b$ is even. Prove that $b^2-5a$ is even.
1
vote
2answers
57 views

Prove: $A \cap(B\cup C^*)=(A\cap B)\cup C^*$

How do you prove this mathematically, when $C^*$ is the complement of C? I know from drawing a Venn diagram that this equation should hold. $A \cap(B\cup C^*)=(A\cap B)\cup C^*$ Thanks!
1
vote
2answers
46 views

How to prove this $\theta$ notation

How do you prove that the folowing function is equal to $\theta(n^2)$? $$f(n)=\frac{n^3+n+1}{2n+\ln(n)}.$$ Then $f(n)=\theta(n^2)$. Thanks!
0
votes
1answer
61 views

Assume that A is a subset of some underlying universal set U.

Prove the domination laws in Table 1 by showing that a) A ∪ U = U. here is the answer but i have no idea how to come up with this answer and where does T come from?:O A ∪ U = {x | x ∈ A ∨ x ∈ ...
0
votes
1answer
28 views

How to tell if the following function is one to one

Let f:A→B where A = X∪Y with X∩Y=∅. If f|x and f|y are one-to-one, does it follow that f is one-to-one? I am unsure how to figure this out. I have gathered from the info provided that X and Y are ...
0
votes
1answer
136 views

$O(n\log^2(n))$ algorithm for finding closest pair of points between two sets.

For example, say that we are given a set of points where each point is labeled White or Black. How can we compute the pair of ...
1
vote
1answer
60 views

Proving property of congruence - help needed

Let $c,d,m,k ∈ \mathbb{Z}$ such that $m ≥ 2$ and $k$ is not zero. Let $f = \gcd(k,m)$. If $c \equiv d \pmod m $ and $k$ divides both $c$ and $d$, then $$ \frac{c}{k} \equiv \frac{d}{k} ...
0
votes
1answer
125 views

List the members of these sets.

List the members of these sets. a) {x | x is a real number such that x2 = 1} What does this symbol mean | ? the answer is (-1,1) but how do you find the answer? Thanks
1
vote
0answers
92 views

Taylor Series Expansion for Function of Two Variables (with Countable Discontinuities)

Given a real-valued function of two real variables, under certain conditions of smoothness in a closed ball about some point, we can obtain a Taylor series for the function about that point. I want ...
0
votes
1answer
50 views

Generalize discrete Lyapunov equation for n-th order linear dynamics system

My specific application is analysis of dynamic textures using linear dynamics systems of the form $$ I(t) = Cz(t) + w(t) \\ z(t + 1) = Az(t) + Bv(t), $$ where $I(t)$ is the original signal, $z(t)$ ...
2
votes
2answers
77 views

Dividing students into teams-combinatorics

In how many ways can $n$ number of students be divided into two teams such that each team has at least one student. This is what I did: Let $x_1$ be the number of students in the one team and $x_2$ ...
1
vote
0answers
43 views

Can you use chinese remainder theorum to convert hex to dec in your head?

At one time I was able to convert hex to decimal in my head, using a trick I learned in college. I have not used it in years, and forgot how. Does anyone remember how to use the Chinese remainder ...
1
vote
2answers
58 views

6th Grade Problem

Here's a problem from a 6th Grade textbook: A project was carried out by a 3-man brigade working for 5 days and a 4-man brigade working for 4 days. $390 was paid for the whole project. How much was ...
1
vote
1answer
46 views

drawing diagram for binary relation

im working on the practice problem on unit about sets and relations The question is: Let a = {1,2,3,4} and R be a binary relation on A x A given by: ((a,b),(c,d)) ∈R if and only if a divides c and b ...
0
votes
2answers
126 views

Finding the subsets in a set that contains x or y but not z

Let S be a set of size 37, and let x, y, and z be three distinct elements of S. How many subsets of S are there that contain x or y, but do not contain z? $(a) 2^{36} − 2^{34}$ $(b) 2^{36} − 2^{35}$ ...
0
votes
1answer
40 views

Question about Anti Symmetricity

If there are no relations on the set R where (a,b) ∈ R and (b,a) ∈ R is it anti symmetrical because you can't evaluate if a = b or is it not anti-symmetrical because you can't evaluate if a = b? ex) ...
3
votes
2answers
107 views

How to count the amount of subsets within a set

Let S be a set of size 37, and let x, y, and z be three distinct elements of S. How many subsets of S are there that contain x and y, but do not contain z? (a) $2^{33}$ (b) $2^{34}$ (c) $2^{35}$ ...
1
vote
1answer
71 views

how to fnd if R is an order?

hello i have a upcoming quiz and I was solving practice problems that the instructor gave us. But Im not sure how to approach this problem the problem is: Let $A = \{1,2,3,4\}$, and $\mathcal{R}$ be ...
2
votes
2answers
128 views

$\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$

Please help! I need help on my assignment for discrete mathematics! Prove the following identity: $\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$ I need to ...
3
votes
2answers
52 views

Equivalence Relations on Set of Ordered Pairs

Let $\mathbb{R}$ be the relation on $\mathbb{Z} \times \mathbb{Z}$, that is elements of this relation are pairs of pairs of integers, such that $((a,b),(c,d)) \in \mathbb{R}$ if and only if $a-d = ...
0
votes
1answer
33 views

Make a list of pairs given sets of a relation

Make a list of pairs for the relation R from the set A = {0, 1, 2, 3, 4} to the set B = {0, 1, 2, 3} such that (a, b) ∈ R if and only if a - b < 1. How would "a - b < 1" play into determining ...
1
vote
0answers
55 views

Solving matrix equation of the form $(AX)^2+(BY)^2=D$

Is there any method that can solve the matrix equation of the form $(AX)^2+(BY)^2=D$? $A$ and $B$ are matrices, $X$, $Y$ and $D$ are column vectors. (Solve for $X$ and $Y$) I originally have two ...
1
vote
1answer
51 views

How to show if A (A△B)△C=A△(B△C) [duplicate]

im working on problem that asks me to show that for any set a,b,c (A△B)△C=A△(B△C) In my opinion, I can just use associative law of set theory and just conclude that left equals the right. But then ...
0
votes
1answer
100 views

How to show that R(binary relation on A x A) is an order?

im working on the practice problem on unit about sets and relations The question is: Let a = {1,2,3,4} and R be a binary relation on A x A given by: ((a,b),(c,d)) ∈R if and only if a divides c and b ...
0
votes
2answers
133 views

Relation that is only symmetric, reflexive, antisymmetric or transitive?

What could be a possible example of a relation that's symm, reflex, antisymm, transitive? I am working on practice problems on the unit about Sets and Relations. The question asks me to give a ...
1
vote
2answers
22 views

Solve for x when x is on both sides of modular equation

This question is purely out of curiosity. My little brother got a question for homework to find a rectangle where the Area = Outline. Both sides must also be integers, obviously. He found the square ...
2
votes
2answers
100 views

How many ways can 40 people be split into 10 quartets?

"A certain music school has 49 students, with 10 each studying violin, viola, cello, and string bass. The director of the school wishes to divide the class into 10 string quartets; the four students ...
1
vote
2answers
25 views

How can I prove that a graph with a required amount of edges per node is invalid?

For the following example I assume that no node may be connected to itself. Nodes: A, B, C, ...