Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

0
votes
1answer
27 views

proof with divisibility

this is the original question prove: $\forall c \in Z, a\neq 0 $and b both $ \in Z$ $a|b \iff c\cdot a|c\cdot b$ Then he corrected himself by saying for problem 1: to show that ca | cb implies a | b ...
0
votes
1answer
16 views

from transition table to regular expression

So i have this transition table and i want to turn it into a regular expression. how do i go about doing that? i found this link, but i don't know what they are trying to do here. so here is the ...
-1
votes
2answers
38 views

Strong Induction and Well-Ordering Discerete question [on hold]

Find the smallest positive integer Y such that ∀ integer K great than or equal to Y, a postage of K cents can be formed using only 3-cent and 4-cent stamps. And prove that the Y value you find is ...
0
votes
1answer
15 views

How to build a finite state machine

I have this question that i have been working for a while for now. This is what i put down for my regular expression: a (a+b)* baa This is the question is asking: Construct the state digraph ...
0
votes
2answers
94 views

Every planar graph has a vertex of degree at most 5.

I am trying to prove the following statement, any help!? Prove that every planar graph has a vertex of degree at most 5.
0
votes
1answer
54 views

n-dimension hypercube!

An $n$-dimension hypercube $f(n)$ is defined as follows. Basis Step: $f(1)$ is a graph with $2$ vertices connected by a link, and with $1$-bit ID for each vertex. Recursive step: To define $f(n)$ for ...
0
votes
3answers
85 views

N-Dimension Hypercube question? (making sense of the question)

I just failed a test in discrete math. Here is the Question that cost me the most points: An n-dimension hypercube f(n) is defined as follows. Basis Step: f(1) is a graph with 2 vertices ...
-1
votes
1answer
89 views

Cut Edges Question [on hold]

I am having somewhat difficulty proving this: Show that every graph has an edge cut $[S, V \setminus S]$ such that $|[S, V \setminus S]| \geq \dfrac{|E(G)|}{2}$. Thank you for your time!
1
vote
1answer
28 views

Show that $\mathfrak c +{\aleph_0}=\mathfrak c$ using “presenters”

I need to prove that $\mathfrak c +{\aleph_0}=\mathfrak c$ using "presenters". For example, in order to prove that $\mathfrak c +\mathfrak c=\mathfrak c$ We can show that: $$\mathfrak c =\left| ...
0
votes
1answer
17 views

Show that for every integer n there is a multiple of n that has only 0s and 3s in its expansion. [on hold]

Show that for every integer n there is a multiple of n that has only 0s and 3s in its expansion.
0
votes
0answers
10 views

Why are these consequences (context discrete math)?

Our textbook gives this definition of a consequence: Let Σ be a (possibly infinite) set of propositions. We say that σ is a consequence of Σ (and write as Σ |= σ) if, for any valuation V, ...
-3
votes
3answers
55 views

Graph Theory - Proof - Isomorphism [on hold]

If anyone can help me prove the following: Suppose that $G$ is a plane graph which is isomorphic to its dual. Prove that $G$ has $2n-2$ edges. I thank you for your time!
2
votes
1answer
32 views

Smallest Graph that is Regular but not Vertex-Transitive?

I'm trying to find the smallest graph that is regular but not vertex-transitive, where by smallest I mean "least number of vertices", and if two graphs have the same number of vertices, then the ...
0
votes
1answer
23 views

Why does a 2-colourable simple graph with n nodes have no more than $(n^2/4)$ arcs?

Why does a 2-colourable simple graph with n nodes have no more than $(n^2/4)$ arcs? I would really appreciate for any kind of explanations.
1
vote
1answer
51 views

Minimzing the generalized dissimilarity measure

I am trying to solve the following problem for quite some time now, but with no progress. Here is the problem. Let $x_1....x_n$ be n samples in d-dimmensional space and let $S$ be a non ...
0
votes
3answers
28 views

Combinatorics/Probability, Choosing from group of People

I attempted to do this problem and I do have some guesses and trying to see whether they are right. Can you please correct if I'm wrong and explain. would really appreciate it. For a) I have ...
-2
votes
0answers
51 views

Graph Theory - Lower bounds [on hold]

I am trying to solve for the following problem: Find (and justify) a lower bound for 0(G) in terms of X'(G) and E|(G)| and alpha'(G). (where alpha'(G) represents the maximum size of a matching in ...
0
votes
0answers
48 views

Number of edges of a plane graph isomorphic to its dual [on hold]

I am having trouble proving the following statement: Suppose that $G$ is a plane graph which is isomorphic to its dual. Prove that $G$ has $2n-2$ edges.
1
vote
2answers
62 views

Graph Theory - Proof

I am need help to Prove the following statement: Let G be a $k$-regular graph with $n$ vertices and $k \geq 1$. Prove that $G$ does not have an independent set of size greater than $\dfrac{n}{2}$. ...
3
votes
4answers
73 views

Solving the non-homogeneous recurrence relation: $g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$

$g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$ With initial conditions $g_{0} = 23, g_{1} = 37, g_{2} = 42 $ This is a practice question I'm working on, and I'm running into absurd amounts of ...
0
votes
2answers
19 views

Bijection of a function.

Define the function f: $(2,\infty) -> (-\infty,-1)$ by $f(x)= \frac{-x}{x-2}$. Show that f is bijective. I know i need to prove both injective and surjective, and I was able to solve the equation ...
0
votes
1answer
69 views

Graph Theory - Complete graphs [on hold]

I am having trouble with this question... Find the expected number of copies of $k_k$ in $G(n,1/2)$. Can anyone help!?
4
votes
4answers
88 views

Combinatorial explanation for why $n^2 = {n \choose 2} + {n+1 \choose 2}$

An exercise in the first chapter of Discrete Mathematics, Elementary and Beyond asks for a proof of the following identity: $$ {n \choose 2} + {n+1 \choose 2} = n^2 $$ The algebraic solution is ...
0
votes
1answer
20 views

Combinations of bit strings of length 9

How many bit strings of length $9$ contain exactly three $1s$? $10*10*10*9^6=531441000$ But then those first $1's$ don't necessarily have to be the first 3 digits. They can be elsewhere in the digit ...
1
vote
1answer
45 views

Equivalence relation and equivalence class question

Show that the relation $\sim$ defined on the set $X = \mathbb{N} \times \mathbb{N} = \{(a, b) : a \in \mathbb{N}; b \in \mathbb{N}\}$ as $(a,b) \sim (c,d)$ if and only if $a + d = c + b$ is an ...
0
votes
0answers
9 views

How to proove these properties of compositions of relations?

From wikipedia: If R and S are injective, then S ∘ R is injective, which conversely implies only the injectivity of R. If R and S are surjective, then S ∘ R is surjective, which conversely implies ...
0
votes
1answer
29 views

Prove by induction $T_n$ is odd

Taken from MIT's OpenCourseWare site for Discrete Math: We define the following recurrence for $n ≥ 0$: $$T_{n+2} = T_{n+1} + 2T_{n}$$ where, $T_{0} = T_{1} = 1$ (a) Prove by induction ...
23
votes
2answers
816 views

A fascinating number chain.

Take a two digit number $10x+y$ of which both digits are different. now add $y-x$ to this number. By repeating this process you will get a chain of numbers $45,46,48,52,49,54,53,51,47,50.$ after $50, ...
0
votes
0answers
12 views

Representing trees in Set builder notation?

Is there a way to represent graphs and minimum spanning trees using set builder notation? e.g. I have a weighted graph of n nodes, all connected to each other in a mesh network manner. I am to ...
1
vote
2answers
33 views

Prove that $|x+y| \leq |x|+|y|$ [duplicate]

How to Prove the triangle inequality which says for all x (no matter how big or small) and for all y (no matter its size) in the set of irrational+rational numbers, this holds: $|x+y| \leq |x|+|y|$
0
votes
0answers
11 views

Set Relations, Partial Orders, and Hasse Diagrams Question.

A question about elements of a set, binary relations, and hasse diagrams. Bear with the set-up as I'm just copying the question from the assignment. Let me know how to improve my answers to be more ...
0
votes
1answer
22 views

Probability Discrete Math

{1,2,3,4,5,6,7,8,9} What is the probability that the sum of any of these three numbers is odd? I know that I should use $ n \choose k $ somehow and I know that my professor used this as his equation: ...
1
vote
2answers
59 views

Chromatic polynomial of a graph - might take a while

I'm currently struggling with graphs that require either adding edges, or removing them. Problem here being that the graphs I'm working on takes forever to complete and I don't really know if adding ...
2
votes
1answer
20 views

In how many ways can letters in mathematics be ordered with restrictions?

I've been stuck on these for a while. Please guide me through all the steps because I actually want to understand this. I've got an exam coming up. Consider the letters in the word "MATHEMATICS". In ...
0
votes
3answers
24 views

Big O question related to nested loop

So i have code that is a nested loop and the outside loop executes n times but the inside loop executes $n\sqrt{n}$ times. So would my worst case scenario still be $O(n^2)$?
0
votes
1answer
31 views

Combinations and Permutations

What is the probability that a poker hand has five cards each with a different rank? P(5 cards different rank)= P(No pair)+ P(Straight)+ P(Flush) $.50118+.00197+.00392= .50707 =50.7$ percent This ...
0
votes
1answer
20 views

Determine the languages for the given alphabet

I need some help figuring out this exercise. For the alphabet $\sum$ = $\{0,1\}$, let $A,B,C \subseteq\sum^*$ be the languages below. i. $A = \{1, 0, 00, 11, 000, 111, 0000, 1111\}$ ii. $B = \{w ...
1
vote
1answer
49 views

Permutations and Combinations

In a group of 30 ball bearings, 5 are defective. If 10 ball bearings are chosen at random, a) what is the probability that none of them are defective? b) what is the probability that two or more ...
3
votes
4answers
68 views

Generating Functions in Discrete Math

a)Find the coefficient of $x^3y^4$ in $(2x + 5y)^7$. b) Find the coefficient of $x^5$ in $(3x -1)(2x +1)^8$. I know this has to do with generating functions , but i'm not sure how to start with this ...
4
votes
3answers
50 views

Stars and bars (combinatorics) with multiple bounds

Count the number of solutions to the following: $$x_1+x_2+\cdots+x_5=45$$ when: $1$. $x_1+x_2>0$, $x_2+x_3>0$, $x_3+x_4>0$ $2$. $x_1+x_2>0$, $x_2+x_3>0$, $x_4+x_5>1$ ...
1
vote
2answers
29 views

Permutations and Combinations

Show that $\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - ...+(-1)^k * \binom{n}{k} = (-1)^k * \binom{n-1}{k}$. I know this has to do with permutations and combination problems, but I'm not sure how ...
9
votes
1answer
83 views

Which graphs can be drawn using straight lines with no disjoint edges?

What is the class of graphs that can be drawn using only straight lines with no two edges disjoint? Edges are disjoint when they don't cross and they don't share a vertex. Vertices should be in ...
0
votes
2answers
158 views

Discrete math: probability of picking certain hands with a preset condition

In 5-card draw poker, a player receives an initial hand of 5 cards, and is then allowed to replace up to three of her cards with the remaining cards in the deck. (b) Suppose that, among the initial 5 ...
1
vote
1answer
38 views

Permutations and Combinations

What is the probability that a 3-element subset selected at random from the set {1,2,3, … , 10} a) contains the integer 7? b) has 7 as its largest element? I know this deals with permutation and ...
0
votes
0answers
18 views

Variation of Nim: Player who takes last match loses

Here is a homework problem I can't understand the solution to. Can anyone help me understand why they are using "mod 4"? Can someone help me understand this strong induction example? Thanks everyone! ...
0
votes
1answer
29 views

Give an example of a relation R on $A^2$ which is reflexive, symmetric, and not transitive

I am just looking for some clarification on this exercise: Let $A = \{a,b,c,d\}$. Give an example of a relation $R$ on $A^2$ which is reflexive, symmetric, and not transitive. I understand that if I ...
1
vote
1answer
24 views

Symmetric relation , why are these symmetric?

$R_1 = \{(a,b)$ such that $a \leq b \}$ $R_2 = \{(a,b)$ such that $a>b \}$ $R_3 = \{(a,b)$ such that $a=b$ or $a=-b \}$ $R_4 = \{(a,b)$ such that $a=b \}$ $R_5 = \{(a,b)$ such that $a=1+b \}$ ...
1
vote
1answer
19 views

With how many ways can there be $n$ couplings between $n$ men and $n$ women?

Could you help me with the following exercise? Could you give me a hint? With how many ways can there be $n$ couplings between $n$ men and $n$ women?
1
vote
2answers
56 views

Combinations and Permutations

How many arrangements of the letters in DIGITAL have two consecutive I’s? I know this is a type combination, permutation problem but i'm a little unclear how to start with this problem.
2
votes
1answer
26 views

How does a cropping of a 2D matrix/image affect its DCT transform?

I apologize in advance: since I am not a mathematician, maybe my question is not well defined, but I hope that some of you will still understand my meaning. Given a 2D matrix, or an image of ...