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

the nonexistence of the minimum of max(|a/b-1|,|a/(b+c)|)

I want to prove that this formula ||f-r||=max(|a/b-1|,|a/(b+c)|) does not have a minimum? for a/b=1
chayma
  • 31
1
vote
3 answers

How to show that $R$ is an equivalence relation？

For all $p, q, m, n\in N$, we define $R$ as follows:$$(p,q)R(m,n)\Leftrightarrow pn=qm$$ Prove that $R$ is an equivalence relation on $N$.
Voonting
  • 11
1
vote
2 answers

How to prove $\frac{(-1)^{(n-1)}}n-1$ is Cauchy

So I've got to prove $\frac{(-1)^{(n-1)}}n-1$ is a Cauchy sequence, but I can't do that if I can't simplify it to the point at which 1 is the numerator (so I can cross multiply with $\frac{2}{\epsilon}$), which I'm not sure you can. I get as far as…
James M
  • 17
1
vote
3 answers

how to prove the identity that $2^{ab}-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+.....+2^a+1)$

I am really confused. The identity is given but I really want to know why$?$ Show that if $2^n -1$ is a prime , then $n$ is a prime . [Hint : Use the identity] $$2^{ab} -1 = (2^a-1)\cdot(2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^a +1 )$$
Dreamy
  • 15
1
vote
2 answers

function $g: Q\times Q \to Q\times Q$ such that $g(x,y) = (2x + 3y, 3x + 2y)$ if $ x,y\in Q$, need to prove that g is reversible function

I know that a reversible function is a function that is onto and injective, how can I prove that?
Elior Dadon
  • 47
1
vote
2 answers

Prove that the function $f: \mathbb{Z}\times \mathbb{Z}\to \mathbb{Z}\times \mathbb{Z}$ defined by $f(m,n) = (2m+3n,3m+2n)$ is not onto

I'm a student and I came across this problem, first I had to prove that this function is injective, which I did. But I really struggle to prove that this function is not onto. I'll appreciate the help!
Elior Dadon
  • 47
1
vote
2 answers

Eulerian Graphs

If we have two Eulerian graphs $H = (V,E)$ and $H' = (V, E')$ that are on the same set of $n \geq 5$ vertices and do not share any edges. Is the disjunction of $G$ and $H$ also Eulerian.
user732092
1
vote
1 answer

I want to understand how to show a clear bijection from the unit circle to the real number line.

I took my first class in Discrete Math this semester and I was given a problem to explain why there is a bijection between the points on the unit circle and the real numbers. I initially thought the points on the unit circle were a subset of the…
Sal Moe
  • 11
1
vote
1 answer

If a "rating" is based off of the last 100 yes/no answers, looking to see how my rating would be affected based on a number of factors outlined below.

My rating is based off of the previous 100 ratings, which consists simply of of "Yes" or "No". It is calculated as such so that when you receive the 101th rating, the 1st rating falls off, 102nd rating the 2nd falls off, and so on. I am currently…
wardr
  • 113
1
vote
0 answers

Questions in Discrete Mathematics- help needed

Suppose that each male/female pair of rabbits in a farm produces two new male/female pairs of rabbits at the age of 1 month and six new male/female pairs of rabbits at the age of 2 months and every month afterward. Assume that there is only one…
Ting
  • 11
1
vote
1 answer

Sequence, convergence

Show that the sequence, $E_{n=0}^∞ (\exp\{-(E_n)/((k_B)T)\})$ is convergent and find its sum. I usually know how to do this with other functions, but I feel kind of lost in this one since it is an exponential function with different variables?
Lioness Queen
  • 57
1
vote
1 answer

Concrete Mathematics: Josephus Problem: Understanding 1.9 proceeding explanation.

Preceding the proposed recurrence solution 1.9 we have the very clear table and I understand that we can group by powers of two, that $J(n)$ is always 1 at the start of the group, and it increases by 2 within a group. I'm having trouble…
Friedrich 'Fred' Clausen
  • 387
  • 2
  • 12
1
vote
1 answer

Relations on {F,T} are reflexive, irreflexive, symmetric, anti-symmetric and transitive?

This is not homework or a test. I just want to better understand when a relation on a set is reflexive, irreflexive, symmetric, anti-symmetric and transitive. https://i.stack.imgur.com/HkxOk.jpg AND How can it be antisymmetric and symmetric? Why is…
user726315
1
vote
2 answers

Find amount of steps.

I need to calculate the amount of steps the person needs to take to have a probability of 50% to be aleast 10m away from his starting point (in both directions). He has a probability of 50% of moving in either direction. Could someone tell if I'm…
Yeonsan
  • 13
1
vote
1 answer

A Discrete Mathematics question

A door lock has 5 buttons labelled with the letters A, B, C, D, E. To open the lock we must enter a code by performing a sequence of 3 operations. Each operation involves either pressing a single letter key or a pair of letter keys simultaneously.…
Tower Bridge Dry Cleaners
  • 11
1 2 3
…
99 100