Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [discrete-mathematics]

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.

Discrete mathematics is not the name of a branch of mathematics, like number theory, algebra, calculus, etc. Rather, it's a description of a set of branches of math that all have in common the feature that they are "discrete" rather than "continuous".

The term "discrete mathematics" is therefore used in contrast with "continuous mathematics," which is the branch of mathematics dealing with objects that can vary smoothly (and which includes, for example, calculus). Whereas discrete objects can often be characterized by integers, continuous objects require real numbers.

Though there cannot be a definite number of branches of Discrete Mathematics, the following topics are almost always covered in any study regarding this matter −

  • Sets, Relations and Functions
  • Mathematical Logic
  • Group theory
  • Counting Theory
  • Probability
  • Mathematical Induction and Recurrence Relations
  • Graph Theory
  • Trees
  • Boolean Algebra

For an overview, see the Wikipedia entry on Discrete mathematics.

and http://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf

Consider using a more specific tag instead, such as: , , , , , , , , etc.

32903 questions
2
votes
0 answers

Let and be positive integers, show that $\gcd(, ) \cdot \mathrm{lcm}(, ) = b$

So far I have tried this: Let $c = \gcd(a,b)$. We can say that $a = cx$ and $b = cy$ such that $x$ and $y$ are positive integers that are relatively prime. Then we have that $$ab = (cx)(cy) = c(xyc) = gcd(a,b)(xyc)$$ In order to show that $\gcd(, )…
agarg
  • 31
2
votes
1 answer

How to draw the Hasse diagram of the following poset?

Which are the minimal and maximal elements? The poset is: $(\{\emptyset,\{{\emptyset,1 \},\{1\}},\{1,2\}\},\subseteq) $ I assume, that it will look like a vertical chain, at the first stage from below with $\emptyset$, the second, $ \{\emptyset,1 \}…
Herrpeter
  • 1,326
2
votes
2 answers

Struggling with Equivalence relations

I am currently studying for my exams this summer. I have a hard time getting to grips with the following question on discrete mathematics: Consider the relationship $T$ between ordered pairs of natural numbers such that $(a, b)$ is related to $(c,…
Aashish Rathod
2
votes
2 answers

Discrete math into plain English help $1$.

Given Statement: $\forall x \in \Bbb N\left(x > 1 \to \exists k \in \Bbb N \exists m \in \Bbb N\left(m \equiv 1\pmod 2 \land x = 2^k \cdot m\right)\right)$ So far I have written it as: For all $x$ in the set Natural numbers where $x$ is larger than…
user430574
2
votes
4 answers

Direct Proof Discrete Math

Original Question: Show that if $n$ is an odd integer, then $n^2$ is odd. Possible Solution: Proof : Assume that $n$ is an odd integer. This implies that there is some integer $k$ such that $n = 2k + 1$. Then $n^{2} = (2k+1)^{2} = 4k^{2} + 4k +…
Agent 0
  • 669
2
votes
1 answer

Independent and dependent events with drawing 2 cards without replacement

Independence and dependence with events like first card red and second card black and of course, without replacement. I believe they are dependent but have not found the best way to explain this. A few of my very bright students in discrete math…
meldolly
  • 21
2
votes
1 answer

If $f(x) = -3x^2 + 6x + 2$, prove that $f(x)$ is $O(x^2)$

I had a question on Big-O. If $f(x) = -3x^2 + 6x + 2$, prove that $f(x)$ is $O(x^2)$ Generally my teacher gave us these strategies to follow: 1. Eliminate Negative Terms 2. Multiply to match highest order term. So in this case Would I be getting…
Istiak Khan
  • 31
2
votes
2 answers

Proof C(n,r) = C(n, n-r)

Hello just want to see if my proof is right, and if not could someone please guide me because I am not clearly seeing the steps to this proof. I don't know if I correctly solve the proof in the second to last step. If I did any mistake it would be…
Alan
  • 21
2
votes
1 answer

Discrete math(Divisors and primes)

Is the following statement true or false?Explain. There are integers $x,y,$ and $z$ such that $14$ divides $2^x × 3^y × 5^z$. My guess is false but I don't know how to explain it?Does it have anything to do with the fundamental theorem of…
Lim Sook Yee
  • 105
2
votes
3 answers

Show that if $A \oplus B = A \oplus C$, then B=C

Prove that if $A \oplus B = A \oplus C$, then $B=C$ Note: $ A\oplus B= (A \cup B) \setminus (A \cap B)= (A \setminus B) \cup (B \setminus A)$ This is what I have done so far: Claim: B=C Proof: Case 1: show that $B \subseteq C$ Case 2: Show that $C…
Lily
  • 395
2
votes
2 answers

Finding the coefficient for binomial expansion

Hello I was trying to find the coefficient for the member $x^5$ for the expansion: $(1-2x)^{-2}$
Grangj
  • 123
2
votes
2 answers

Meaning of the symbol $\oplus$

Anybody who knows/can explain what this character means?
Mauran Muthiah
  • 139
2
votes
2 answers

Let $R$ be the binary relation on $\mathbb{N}$ defined by $xRy$ ($x$ is in relation to $y$) defined by: $xRy$ if $xy=49$

Let $R$ be the binary relation on $\mathbb{N}$ defined by $xRy$ ($x$ is in relation to $y$) defined by: $xRy$ if $xy=49$ A) $R$ is reflexive and $R$ is symmetric B) $R$ is reflexive and $R$ is not symmetric C) $R$ is not reflexive and $R$ is…
pkim
  • 89
  • 9
2
votes
4 answers

Floor Function. Let x and y be rational numbers

let x and y be rational numbers. A. $\left \lfloor x \right \rfloor + \left \lfloor y \right \rfloor = \left \lfloor x+y \right \rfloor$ B. $\left \lfloor x \right \rfloor + \left \lfloor y \right \rfloor \le \left \lfloor x+y \right…
pkim
  • 89
  • 9
2
votes
1 answer

Find coefficient of generating function f(x).

Find coefficient of generating function. $ f(x) = \frac{2x}{1-x^{2}} +x$ MY WAY OF SOLVING SIMILAR PROBLEM: 1) $ g(x) = \frac{2x}{1-x^{2}}$ 2) partial fraction $g(x) = \frac{A}{1-x} + \frac{B}{1+x} $ 3) $ g(x) = \sum\limits_{n=0}^\infty Ax^{n} +…
Nowak Grzegorz
  • 507
1 2 3
…
99 100