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
4 answers

is $(x+y)^2\neq (x^2+y^2)$ correct if we consider the integers mod $2$?

In general $(x+y)^2 \neq (x^2+y^2)$. Is this still correct in the case of mod $2$? Can anyone share some insight?
tonix
  • 79
2
votes
2 answers

a, b, c, d are reals and a < b < c < d. express the set $[a,c] \cap [b, d]$ as difference of two intervals.

I'm struggling to solve the problem stated above. To help clarify the question I let a = 1, b = 2, c = 3,and d = 4. If that were the case then the interval I am interested is [b, c]. What does it mean to express that as the difference of two…
ponderingdev
  • 558
2
votes
1 answer

Distributing n identical balls in k distinct boxes

In how many ways can $20$ identical balls be distributed in $4$ distinct boxes, subject to the following conditions: Each box has at least $2$ balls, Each box has an even number of balls? The distribution of $20$ identical balls in $4$ distinct…
MathLover95
  • 81
2
votes
1 answer

How do I find "Big Oh," "Big Omega," and "Big Theta"?

I need help studying for an exam. How do I find "Big Oh," "Big Omega," and "Big Theta"? How do I combine this with Induction? Prove that $f(x)$ is $O(x^n)$, where $$f(x) = a_n x^n + a_{n-1} x^{n-1} + a_{n-2} x^{n-2} + \cdots + a_2 x^2 + a_1 x +…
Math Student
  • 405
2
votes
2 answers

How many are exposed to two of the three? (venn diagram problem)

Q: A survey has shown that of 100 people chosen at random, 80 watch TV commercials, 70 read newspaper ads, 40 read magazines. Only 10 do none of these things, and 20 do all three. How many of these people are exposed to exactly two of the three…
Dan Qualins
  • 21
2
votes
0 answers

domain and range discrete math

Define the relation T on ℝ+ by T = {(x, y):y=7/2X-5} (i) State the domain and range of T. (ii) Is T a function? State your reason. i)for domain: 2x-5>0 -> x>5/2 (domain of T) Range: o
Mohd Saleem
  • 69
2
votes
1 answer

A simple floor function conditional proof

I have to prove the following: There exists a positive real number $a$ so that for all real numbers $x$ if $x$ -$\lfloor x \rfloor < a$, then $\lfloor 3x \rfloor = 3 \lfloor x \rfloor$. I have attempted to do this in several ways. I got the…
monevus3
  • 25
2
votes
3 answers

How do I describe a set of names?

I want to describe the following set... { "Person1", "Person2", "Person3"... } ... where the number is from 1.. 100. How do I do this using mathematical set description?
Ian Warburton
  • 129
2
votes
0 answers

Erdős-Szekeres theorem on monotone sequences

Given a sequence $S$ with $21$ different numbers. It is known that there isn't any monotone subsequence in the length of $6$. Prove that there exists $2$ monotone subsequences, one decreasing and the other increasing, in the length of $5$. Solution:…
Charles Carmichael
  • 595
2
votes
1 answer

Upper limit for Big O notation isn't established?

We say that a function $f(x)=O(g(x))$ if $\exists x_0\in \mathbb{R}_+$ and $\exists C\in \mathbb{R}_+$ such that $\forall x\geq x_0$, $|f(x)|\leq C g(x)$. So with this definition, the function $f(x)=3x^2+2$ can be said to be $O(x^2)$, because…
Arturo don Juan
  • 3,908
2
votes
6 answers

Solving the recurrence relation that contains summation of nth term

$$T(n)=1+2\sum_{i=1}^{n-1}T(i) , \quad n > 1$$ $$T(1)=1$$ any hint or how to solve?
Eric
  • 31
2
votes
3 answers

How would the intersection of two uncountable sets form a countably infinite set?

This is based off my last question How would the intersection of two uncountable sets be finite? Here is the problem(from Discrete Mathematics and its Applications) The book's definition on countable And the definition of having the same…
committedandroider
  • 1,884
2
votes
2 answers

Discrete Math - Sets and Complements

I have the following problem: List the elements of the set $\overline{A\cap B}\cup C$, where $\overline{X}$ denotes the complement of an arbitrary set $X$ and $U$ denotes the universe under consideration. The considered sets are as follows: $U =…
natur3
  • 89
2
votes
1 answer

Equivalence relation on $\mathbb{N}\times\mathbb{N}$

Define a relation on $\mathbb N\times \mathbb N$ by $$ (a,b)\sim (c,d) \iff a+d=b+c. $$ Prove that if $(a, b)\sim(a', b')$ and $(c, d)\sim(c', d')$, then $(ac+bd,bc+ad)\sim(a'c'+b'd',b'c'+a'd')$ Here's what I've tried: Given that…
Jay
  • 352
2
votes
6 answers

Discrete Mathematics: $mn + 2m + 2n + 2 = n$ proof of uniqueness of $m$, $\forall n \in \mathbb{Z}$

Prove: There exists a unique integer $m$ such that for every integer $n$: $$mn + 2m + 2n + 2 = n$$ However I am not sure if my proof is correct. How do I prove uniqueness of $m$? I prove it by solving the equation for $m$. For every $n$ there is a…
Nadia S
  • 259
1 2 3
…
99 100