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
3
votes
1 answer

Does $\lfloor\frac{(n+1)^2}2\rfloor$ equal $\lfloor\frac{n^2}2\rfloor + n$?

By expanding the left, I found that $\lfloor\frac{(n+1)^2}2\rfloor$ = $\lfloor\frac{n^2}2 + n + \frac{1}2\rfloor$. I am not sure how to relate $\lfloor n + \frac{1}2 \rfloor$ to n so as to show that the right is true/false. Any ideas?
Payal Ahuja
  • 101
3
votes
6 answers

Whether $2^{38}$ or $3^{33}$ is greater without needing a calculator

My question is about figuring out whether $2^{38}$ or $3^{33}$ is greater without needing a calculator, by using the Mobius function or by other means?
Mehul Murali
  • 49
3
votes
2 answers

Does anyone recognize this sequence?

I was wondering if anyone has come across this sequence and if so if they have a formula for it. $$\frac{1}{2},\ \frac{1}{6},\ \frac{2}{30},\ \frac{8}{210},\ \frac{48}{2310},\ \frac{480}{30030},\ \frac{5760}{510510},\ \frac{92160}{9699690},\…
Colin
  • 33
3
votes
2 answers

Counting problem: digit sequences with restricted digits and fixed digit sum

How many different six digit positive integers are there (duplicates allowed), where each digit is between 0 and 7 (inclusive), and the sum equals 20? I know that there are 229,376 total possible 6 digit numbers which do not have an 8 or a 9. But…
Daniel Powell
  • 33
3
votes
1 answer

Discrete Mathematics, Equivalnces"

The "≡ mod 3" relation is an equivalence relation on the set {1,2,3,4,5,6,7}. List the equivalence classes. I understand "≡ mod n" relation on Z is transitive. I just cant see how to start this problem, Thanks for any tips.
J Crawford
  • 67
3
votes
2 answers

Four scientists combinatorial problem.

Four scientists are working on a secret project. They wish to lock up the documents in a cabinet such that the cabinet can be open if and only if 3 or more scientists are present. a. What is the smallest number of locks needed? b. What is the…
Bruce Berentsen
  • 123
3
votes
5 answers

Predicates and quantifier

I am working on predicates and quantifier and got confused. Can someone explain this? “All lions are fierce.” “Some lions do not drink coffee.” “Some fierce creatures do not drink coffee.” Let P(x), Q(x), and R(x) be the statements “x is a lion,” “x…
Jay Choi
  • 31
3
votes
3 answers

When to use implication and when to use conjunction?

This is a mathematical logic question. "All men are mortal" seems to be represented as ∀x (Man(x) ⟶ Mortal(x)). "Some trigonometric functions are periodic" is represented as ヨx(Trigonometric(x) ⋀ Periodic(x)). Why isn't the latter represented as…
Ciado
  • 181
3
votes
1 answer

Prove that $\operatorname{Spec}\sqrt2$ contains infinitely many powers of $2$.

$\newcommand{\spec}{\operatorname{Spec}}\spec\sqrt2=\{\lfloor k\sqrt2\rfloor: k \ge 0\}$. I have no idea of how I can prove the statement in the question. Prove that $\spec\sqrt2$ contains infinitely many powers of $2$.
learner
  • 905
3
votes
2 answers

Recursive Sequence "3, 5, -2, 7, -9, 16, -25, 41"

How would I start in solving this recursive sequence? Thanks! Sequence: 3, 5, -2, 7, -9, 16, -25, 41, ...
user6726
3
votes
3 answers

Finding the Units Digit to 7 to the 2945

How would I go about finding the Units Digit to 7^(2945)? I know that: 7^0 = 1 7^1 = 7 7^2 = 49 7^3 = 343 7^4 = 2401 ... 7^9 = 40353607
JDog
  • 45
3
votes
5 answers

Use mathematical induction to prove an assertion

The assertion: $n^3 + 5n$ is divisible by $6$ I have completed the basis step $(n=1)$ and the first part of the induction step $(n=k)$, but I am stuck on the second part $(n=k+1)$. This is what I have so far: For $n=k$: $k^3 + 5k = 6t$ For $n=…
user1861051
  • 357
3
votes
1 answer

Least or Highest Element in a non-empty set

I have to prove or disprove that every non-empty set on non-negative rational numbers has a least element. I thought this may be pretty straight forward but I thought what if the non-empty set contains only one element. For example; A = {2}. Does…
Chance Gordon
  • 381
3
votes
2 answers

What is a discrete set exactly?

I'd appreciate the comments/answers including some examples in this regard. In addition, one may also ask that any infinite discrete set is a countable set?
user370634
3
votes
3 answers

Equivalence Classes of this Relation on the integers : $a + b^2 \equiv 0\pmod{2}$.

Let $R$ be the relation defined on $\mathbb{Z}$ where $a\; R\; b$ means that $a + b^2 \equiv 0\pmod{2}$. How would I go about finding the equivalence class $[-13]$?
Krysten
  • 779
1 2 3
…
99 100