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
2answers
27 views

Discrete math functions proof

Let $\mathbb N_{\text{even}}$ be the set of all natural even numbers, and $\mathbb N_{\text{odd}}$ be the set of all natural odd numbers, the function $f:\mathcal P(\mathbb N)\to \mathcal P(\mathbb ...
0
votes
1answer
31 views

Simplification of Boolean Algebra

$$F = (w,x,y,z)= (xy'z) + (wxy'z') + (wxy) + (w'x'y'z') + (w'x'yz')$$ I need to simplify this equation as much as possible, using Boolean identities. The prime($'$) represents the negation of the ...
0
votes
1answer
20 views

Next step to show that these matrice expressions are equal?

This is a problem from Discrete Mathematics and its Applications I know invertible means it is possible to take the inverse of this matrix. This is definition of a power of a square matrix from my ...
1
vote
2answers
27 views

Number of 5 letter words with at least one double letter

How many 5 letter words have at least one double letter, i.e. two consecutive letters that are the same? Answer is: $26^5 – 26*25^4 = 1,725,126 $ But how can i solve? I don't understand. The book ...
-1
votes
3answers
97 views

There exists irrational numbers $x$ and $y$ such that $x^y$ is rational. [on hold]

I'm having trouble understanding this from the textbook I am reading. 2.2.3 Nonconstructive proofs In a nonconstructive proof, we show that a certain object exists, without actually creating it. ...
0
votes
0answers
29 views

How to display one to one correspondence for all bit strings not containing the bit O?

This is a problem from Discrete Mathematics and its Applications From the onset I saw that this set was countable was that you could physically count these out - 1, 11, 111, 1111 and perhaps ...
1
vote
1answer
35 views

Clarification on Cantor Diagonalization argument?

My book is Discrete Mathematics and its Applications. This is its section on Cantor's Diagonalization argument I understand the beginning of the method. The author is using a proof by ...
2
votes
3answers
55 views

How to approach this proof problem, what proof to use, what assumption to use?

This is a problem from Discrete Mathematics and its Applications Here is the definition of rational that my book uses Usually when I approach this type of a problem, I can find a type of proof to ...
0
votes
0answers
20 views

Would it be necessary to have another proof within the proof by cases in this problem?

This is a problem from Discrete Mathematics and its Applications I am using Proof by Cases. This is my book's definition on it. Here is my work so far I tried to leverage without of generality ...
1
vote
1answer
28 views

Problem understanding analysis of greedy maximal weighted matching algorithm

Greedy Algorithms for Matching $M = \emptyset$ For all $e \in E$ in decreasing order of $w_e$ add $e$ to $M$ if it forms a matching Theorem The weight of the matching $M$ returned by the ...
0
votes
0answers
30 views

Solving a proof by combinatoric method

Any good questions you guys have in mind?: prove the following equation by coming up with a combinatoric problem and solving it step by step (Solve combinatoric method): $$ {n \choose 1} + 14{n ...
0
votes
1answer
13 views

SDR (system of distinct representatives) from Venn Diagram

I want to learn what is SDR (system of distinct representatives) today. SDR (system of distinct representatives): SDR = System of distinct representatives. Given a finite family of sets ...
-2
votes
0answers
22 views

Recurrence relation -unique question? [on hold]

How to solution please? Thanks…^^
2
votes
1answer
47 views

tricky question in combinatorics - deck of cards [on hold]

A deck of cards with $4$ sets, each set contains $13$ cards. We want to create a new sequence of $n$ cards: each time we choose a card, write it down as the next element in the sequence, put it back ...
0
votes
2answers
26 views

Big-O math Question

I'm having trouble with this question: Suppose that $f(x), g(x)$ and $h(x)$ are functions such that $f(x)$ is $O(g(x))$ and $g(x)$ is $O(h(x))$. Prove that $f(x)$ is $O(h(x))$. I have tried ...
-3
votes
2answers
32 views

a Combinatorics problem in series [on hold]

Hey everyone i was having a problem with the following question: in how many ways is it possible to solve the following equation using natural numbers: $$ x_1+x_2+x_3...+x_{15}=300 $$ that for every ...
0
votes
1answer
12 views

Is it an example of bilinear pairing?

Consider a bilinear pairing $e: G_1 \times G_2 \rightarrow G_T$. Let's assume, $G_1 = G_2 = G_T = (\mathbb{Z}_n,+)$, i.e. additive group of integer modulo $n$ and $e(x,y) = xy$ mod $n$. Isn't it an ...
0
votes
2answers
29 views

Next step to take in this proof by contradiction?

This is a problem from Discrete Mathematics and its Applications Here is my work so far It's similar to this other question I had Next step to take to reach the contradiction?. I am assuming ...
0
votes
0answers
34 views

How to approach solving multi-variable continuous probability distrobution problem

You are taking the subway in an unfamiliar city. You are told to take the Blue Line train to central station and then transfer to the Green Line train, which is just on the other side of the platform. ...
2
votes
3answers
46 views

Can someone verify my direct proof that if A is a subset of B, AU B = B?

This is a problem from Discrete Mathematics and its Applications I am trying to use a direct proof to do this problem. Here is my book's explanation/section on direct proof Here is my work so ...
2
votes
3answers
74 views

Proving with Big O Notations

Is there a way I can prove that $O(3^{2n})$ does NOT equal $10^n$? How would that be done? Also, is it okay to simplify $O(3^{2n})$ to $O(9^n)$ to do so?
1
vote
2answers
50 views

combinatorics dice question

There are $10$ identical dice ($1$ - $6$). How many different results can we get so that the set of results will be exactly $3$. for example: $7$ dice will be the number $2$, $2$ dice will be $3$ and ...
0
votes
1answer
24 views

Define a recursive function

How to Define a recursive function is-bst : EBT(N) → Bool in such a way that is-bst(t) = true if, and only if, t is a binary search tree.
1
vote
2answers
19 views

Understanding the logic behind this summation

The following is an excerpt from a proof that $\sum_1^n {i^k} = \theta(n^{k+1})$: $$\sum_1^n{i^k} \ge \sum_{\lceil n/2 \rceil}^n{i^k} \ge \sum_{\lceil n/2 \rceil}^n{\lceil n/2\rceil^k}$$ The first ...
1
vote
1answer
39 views

Adjacency matrix and existence of triangle

Show that a graph $G$ contains a triangle (1) if and only if there exist indices $i$ and $j$ such that both the matrices $A_G$ and $A^{2}_{G}$ have the entry $(i, j)$ nonzero, where $A_{G}$ is the ...
0
votes
0answers
13 views

Expressing a vector in terms of an Arbitrary Vector?

Ive been working on vector questions and this one seems to have gotten me stuck. Im unsure on how to express v in terms of i and j such as: (v . i)i + (v . j)j Can somebody provide some help?
0
votes
0answers
16 views

Discrete mathematics - ways of seating

In how many ways can you seat 8 people around a round table such that person A will be in front of B, and person C will not be next to D? Two orderings that are different by a cyclic round are counted ...
1
vote
2answers
36 views

Discrete mathematics - pigeon hole principle

given sets A = {1,2,...12} ; B = {1,2,...15} Let S ⊂ A x B , |S| = 21 Prove that there exist two different pairs (x1,y1) , (x2,y2) in S such that |x1 - x2 | + |y1 - y2| ≤ 4 I think this ...
0
votes
1answer
16 views

Maximum of sum of $k$-th powers with sum of bases equal to $n$

For some positive integer constants $n, k$ and $t$, I want to find the values for $n_1, \ldots, n_t$, all positive integers, that maximize the following sum : $$ \sum_{i = 1}^t (n_i)^k $$ such that ...
1
vote
1answer
29 views

Combinations with Repetition

I am looking the basics of combinations with repetition. The other name is Stars and Bars problem. On MIT OCW I found this: An ice-cream store specializes in super-sized deserts. They offer a ...
0
votes
0answers
21 views

Getting Linear sum from sum of squares

I have sample space Ri = (44.19, 35.14, 57.23, 74.27, 47.27, 32.06, 21.75, 66.49, 25.01, 30.10, 77.53, 61.40, 74.45, 21.93, 20.84, 73.36, 82.62, 52.36, 40.23, 31.88, 1966.79, 2112.71, 1836.88), n = 23 ...
0
votes
0answers
14 views

(a) Find the number of all 2-element chains in Bn. (b) Find the number of all 2-element independent sets in Bn. [closed]

(a) Find the number of all 2-element chains in Bn. (b) Find the number of all 2-element independent sets in Bn.
1
vote
1answer
33 views

how do I parenthesize the product of abcdef??

This is about catalan number and parenthesizing. a)Determine the list of five 1's and five 0's that corresponds to each of these: (((ab)c)(d(ef))) = (what I did: 1110010110) (a(b(c(d(ef)))))) = ...
1
vote
0answers
29 views

What function to use to show that the set of positive rational numbers is countable? [duplicate]

This is from Discrete Mathematics and its Applications Here is the definition of countable that the book uses and how to determine if two sets have the same cardinality Here is the example that ...
-2
votes
1answer
61 views

Given $B \cup A = B$ and probability and set theory axioms, prove $\mathbb{P}(A) \leq \mathbb{P}(B)$.

I need to prove that $\mathbb{P}(A)$ is less than or equal to $\mathbb{P}(B)$ using only this three things: $B \cup A = B$ The three axioms of probability: a) $\mathbb{P}(A)$ is greater or equal to ...
0
votes
1answer
33 views

Conditional probability of an inspector having prior training, given the failure to detect a weapon

Ninety percent of new airport-security personnel have had prior training in weapon detection. During their first month on the job, personnel without prior training fail to detect a weapon 3% of ...
1
vote
1answer
13 views

How to interpret algebraic relationship/ next step to take to prove function is onto?

This is a problem from Discrete Mathematics and its Applications Book's definition on bijection Book's definition on onto Book's definition on one to one I am trying to do problem 23D. Here ...
2
votes
3answers
53 views

Prove that {$r_n$} satisfies $r_n = 7r_{n-1} - 10r_{n-2}, n \geq 2$

Problem: For the sequence $r$ defined by $$r_n = 3 \cdot 2^n - 4 \cdot 5^n, \ \ \ n \geq 0$$ Prove that {$r_n$} satisfies $$r_n = 7r_{n-1} - 10r_{n-2}, \ \ \ n \geq 2$$ Can this problem be ...
1
vote
1answer
36 views

mutually exclusive and independent for two dice problem

i'm working on this problem and I'm not sure if I did it correct The question is, a random man rolls 2 dice. (a)Sum = 5 (b)first die is 4 (c)sum = 7 (d)two dice have same # So I drew a 6x6 graph ...
1
vote
1answer
40 views

Can someone verify my proof by contraposition?

This is a problem from Discrete Mathematics and its Applications Is there a way to tell right away what type of proof to use or does that just come with practice (build intuition - oh here i ...
3
votes
2answers
46 views

How would the intersection of two uncountable sets form a countably infinite set?

This is based off my last question How would the intersection of two uncountable sets be finite? Here is the problem(from Discrete Mathematics and its Applications) The book's definition on ...
2
votes
4answers
60 views

Proof By Induction Help? [closed]

I've been working through proof by induction and i'm stuck on this question. Can somebody provide some help? $$\huge 2^n-1=\sum_{i=0}^{n-1}2^i\text{ for }n\ge 1$$
1
vote
1answer
29 views

Proving Set Operations

I'm trying to prove that if $A$ is a subset of $B$ then $A \cup B = B$, but I am having trouble trying to proves this mathematically. I know that since $A$ is a subset, then $A$ has an element $x$ ...
1
vote
1answer
21 views

The $5\times 5$ matrix whose $(i,j)$th entry is $1$ if $j$ is a multiple of $i$, and $0$ otherwise

The $5\times 5$ matrix whose $(i,j)$th entry is $1$ if $j$ is a multiple of $i$, and $0$ otherwise. I know that I’m supposed to show the work I’ve done, but I just have no idea what to do with this. ...
1
vote
3answers
56 views

How would the intersection of two uncountable sets be finite?

This is a problem from Discrete Mathematics and its Applications Here is my book's definition on countable and definition of having the same cardinality The only example that my book gave of ...
0
votes
0answers
25 views

How to find an injuctive function for not divisible by 7 but divisible by 5?

This is based off my other question - How to write a function to express not divisible by 3? This is a problem from Discrete Mathematics and its applications I am currently on 4B. Here is my work ...
3
votes
1answer
38 views

Way to show divisibility without using Euclid's lemma.

The generalized version of Euclid's lemma states that if $k|mn$ and that $\gcd(k, m) = 1$ then $k|n$. However, I noticed an alternative way of proving questions such as: if $2|n$ and $3|n$ show $6|n$ ...
1
vote
0answers
16 views

Definition of minimal presentation of a group

I'm working on a problem on the braid monodromy of complex lines arrangements in $\mathbb{C}^{2}.$ I have the following question. It's just a simple definition. However, I didn't find anywhere. Let ...
0
votes
4answers
34 views

Surjectivity and injectivity of $\lceil n/2\rceil$

Problem: is this one-to-one, onto, or both? $$f:\mathbb Z\to\mathbb Z; n \mapsto \left\lceil \frac n2\right\rceil$$ With help I arrived at the answer is that $f$ is onto. However, I'm confused ...
1
vote
1answer
18 views

Find Planar Graph fromVertices and Faces

Could you find a 3-Regular Connected Planar Graph on 10 vertices with 8 faces? If so, explain carefully. I dont know what does regular mean. I think that 3-connected graph on 10 vertices with 8 ...