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
1
vote
0 answers

Discrete mathematics: Question about finite automata

I have four questions about finite automata like these: This is what I thought (I do not know it is correct or not): (a) $L(M)$ is a set of strings which each of the string that the numbers of $1$ in the end is a multiple of $3$. (b) $2$ (c)…
Sun Hao Lun
  • 143
1
vote
4 answers

Can a known sum and average determine a set of natural numbers?

Say we are given a predetermined sum and average of $n$ distinct natural numbers ranging from $0-50.$ Knowing the sum and average of any such set of natural numbers, is it be possible to determine what that set is? If so, would the solution be…
MathematicalMemester
  • 15
  • 1
  • 4
1
vote
7 answers

Suppose that today is tuesday. what day of the week will it be in $3^{100000} + 3^{10000} + 3^{1000}$ days?

Suppose that today is tuesday. what day of the week will it be in $3^{100000} + 3^{10000} + 3^{1000}$ days ? I figured that, eventually, I will add $3^{100000} + 3^{10000} + 3^{1000}$ and $\mod\ 7$ that answer... I tryed with the Fermat little…
Dave
  • 525
1
vote
2 answers

About a bijective function with the disjoint sets

In this video by 0:55, it says Lemma: Let $A,B,C,D$ be sets with $A\cap B=\emptyset$ and $C\cap D=\emptyset$. Suppose that $F_1:A\to C$ and $F_2:B\to D$ are both bijections. Define $F:A\cup B\to C\cup D$ by $$ F(x)=\begin{cases} F_1(x) & \text{…
UnknownW
  • 2,008
1
vote
4 answers

Cardinality of two finite sets

Definition: Let $A$ be a set, and define $I_n=\{m\mid 1\leq m\leq n\}$ for $n\in\mathbb{N}$. It is said that $A$ is finite if there exist $k\in\mathbb{N}$ such that $A$ and $I_k$ are equinumerous. In this case, the number $k$ is called the…
UnknownW
  • 2,008
1
vote
1 answer

Does the empty set count as an element?

We're asked the number of elements in a power set and I for {} is the number of elements 1 or 0?
happysaint
  • 21
1
vote
3 answers

Divisors of $-1$ are only $1$ and $-1$?

I'm working through a discrete math textbook and I've come across this question with answer: Prove that the only divisors of $−1$ are $−1$ and $1$. Answer: We established that $1$ divides any number; hence, it divides $−1$, and any nonzero number…
metisMusings
  • 49
1
vote
3 answers

$a \bmod 2x-a \bmod x$

I am trying to find the possible values of the expression $$a \bmod 2x-a \bmod x.$$ I suspect they might be $0$ or $x$, but I'm really not sure. I can't seem to be able to write down a proper argument.
user1377000
  • 73
1
vote
1 answer

For a set M with x ∈ M being the only minimal element on that set, is x the least element as well? Show your answer for finitie and infinite set M.

I came across this question in a refrence book for discrete mathematics: For a partially ordered set M with x ∈ M being the only minimal element on that set, is x the least element as well? Show your answer for finitie and infinite set M. After…
Harold J. Fike
  • 13
1
vote
2 answers

Proof: There are no positive perfect cubes less than 1000 that are the sum of the cubes of two positive integers

The question: "Prove that there are no positive perfect cubes less than 1000 that are the sum of the cubes of two positive integers." How would you go about picking a method to prove this? Is there a better way to do it other than by exhaustion?
nucleic
  • 83
1
vote
1 answer

Let P be the set of all prime numbers. Prove that $| \mathbb{P}| = |\mathbb{N}|$

I am trying to prove a bijection between the two. I know it is one to one, since if $f: \mathbb{N}\to \mathbb{P}$ $f(n)$ = nth number prime How do you prove it is onto?
21rw
  • 281
1
vote
1 answer

Show that $1.222 \le 1 + 3^{-2} + 5^{-2} + ... \le 1.252$

Show that $1.222 \le 1 + 3^{-2} + 5^{-2} + ... \le 1.252$ without calculate the value of $1 + 3^{-2} + 5^{-2} + ...$ Can I do in this way? $$\lim\limits_{n \to \infty} \int_2^n (2x+3)^{-2} \,dx \le 7^{-2} + 9^{-2} + 11^{-2} + ... \le…
RLee
  • 33
1
vote
1 answer

Inclusion Exclusion principle question

What is the number of surjective (onto) functions from the set [3] to the set [3].
Alison
  • 21
1
vote
4 answers

I would really appreciate some help solving this induction problem!!

$3.$ for all $n\ge1$, $\displaystyle\sum_{i=1}^n(2i)^2=\frac{2n(2n+1)(2n+2)}{6}$ I have $$\frac{2n(2n+1)(2n+2)(12(n+1)^2)}6= \frac{2n(2n+1)2(n+1)12(n+1)(n+1)}6.$$ I think I need to do something with the $(n+1)$. However, I'm not sure where to go…
Bill Ngo
  • 21
  • 1
1
vote
3 answers

Why does $n(n+1)(2n+1)+6(n+1)^2=(n+1)(n(2n+1)+6(n+1))$?

I'm not sure how my professor got from: $$n(n+1)(2n+1)+6(n+1)^2 ~\text{to}~ (n+1)(n(2n+1)+6(n+1))$$ I have a feeling it's an algebra thing but I just can't seem to get it. Would really appreciate the help.
Bill Ngo
  • 21
  • 1
1 2 3
…
99 100