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
7
votes
10 answers

Prove that if n is a perfect square, then n+2 is not a perfect square

I'm working on proving the following statement: If n is a perfect square, then n+2 is not a perfect square. I also need to state this in first order logic with arithmetic, but have no idea what that looks like. The only start I have so far in terms…
Bob Shannon
  • 1,561
7
votes
3 answers

How to integrate simple discrete function

Let $n\in\mathbb{Z}^+ $ I have a simple discrete function: $$ \mathrm{acc}(n) = 8n $$ The discrete integral (is that the right term?) of that is: $$ \mathrm{vel}(n) = \sum_{i=0}^n \mathrm{acc}(i) $$ the formula for which is: $$ \mathrm{vel}(n) =…
Rocketmagnet
  • 213
7
votes
4 answers

Not understanding the concept of equivalence class

Let $U$ be a set defined: $U=\{(x,y)\in \Bbb R^2\mid x^2+y^2=1; xy\neq 0\}$, and let $R$ be relation defined: $(x_1,y_1)R(x_2,y_2) \iff (x_1 \cdot x_2>0∧y_1\cdot y_2>0)$. I was to prove it's an equivalence relation - which I did. Then I was asked…
ohad
  • 633
7
votes
5 answers

When does a proof need to be proved both ways?

I am very sorry I understand that the title is confusing, but I am not totally sure how to reword it because I am completely lost on this subject. I am taking a discrete mathematics course right now, and one subject that is confusing me is proofs. I…
user7706318
  • 79
  • 1
  • 3
7
votes
1 answer

In any set of n different natural numbers, exists subset of more than n/3 numbers, such as there are no three numbers in it : a+b=c

I need to prove, that in any set of n different natural numbers, exists subset of more than n/3 numbers, such as there are no three numbers in it, one of which is the sum of two others. Can anyone help me with this?
yet_another_student
  • 71
7
votes
1 answer

Recurrence relation satisfied by $\lfloor(1+\sqrt{3})^n\rfloor$

This is a follow up to a question I had asked earlier about a linear recurrence relationship satsified by $\lfloor(1+\sqrt{5})^n\rfloor$. I messed up there, and I actually meant to ask about $L(n)=\lfloor(1+\sqrt{3})^n\rfloor$. Following Douglas'…
Derek Scavo
  • 1,983
6
votes
1 answer

The well-ordering principle can be used to show that there is a unique gcd of two positive integers...

Question The well-ordering principle can be used to show that there is a unique gcd of two positive integers. Let $a$ and $b$ be positive integers, and let $S$ be the set of positive integers of the form $as+bt$, where $s$ and $t$ are integers. a)…
JoeyAndres
  • 1,269
6
votes
2 answers

Show that $\sum_{\{a_1, a_2, \dots, a_k\}\subseteq\{1, 2, \dots, n\}}\frac{1}{a_1*a_2*\dots*a_k} = n$

Question: Show that $$\sum_{\{a_1, a_2, \dots, a_k\}\subseteq\{1, 2, \dots, n\}}\frac{1}{a_1*a_2*\dots*a_k} = n$$ (Here the sum is over all non-empty subsets of the set of the $n$ smallest positive integers.) I made an attempt and then encountered…
JoeyAndres
  • 1,269
6
votes
1 answer

Prove this is an equivalence relation.

Define a relation of $\mathbb{Q} -$ {$0$} as follows: $x$ ~ $y$ $\Leftrightarrow$ $\dfrac {x} {y} = 2^k $ for some $k \in \mathbb{Z}$ Prove this is an equivalence relation. ATTEMPT: Reflexive: For any $x\in\mathbb Z$, $\dfrac {x} {x}=1$ and $2^0 =…
user114795
  • 115
6
votes
1 answer

Why is the total number of binary relations $2^{n^2}$

Why is the formula for finding the total number of binary relations in a set A equal to $2^{A^2}$ ? I have looked on the web (including here) and find the answer is because the relation can be in or out. This is the exact thing my professor told me…
Jinzu
  • 819
6
votes
2 answers

What does it mean to "determine" an equivalence relation?

I don't understand the following problem: What does it mean exactly that a number of pairs can "determine" an equivalence relation? Say if I have the following set: {1, 2, 3}, and a relation R that's true for (a, b) if a=b. Then would the pairs {1,…
user886596
  • 263
6
votes
3 answers

Proving statements by its contrapositive

Prove the following statement by proving its contrapositive: “If $n^3 + 2n + 1$ is odd then n is even” Therefore: $\lnot q \rightarrow \lnot p =$ "if $n^3 + 2n + 1$ is even then $n$ is odd. So for this I began assuming that: $n=2k+1$ $(2k+1)^3…
Dimitri
  • 1,287
6
votes
2 answers

Number of permutations of a specific cycle decomposition

Let $X(n)$ denote number of all permutations of $\left\{1,\ldots,n \right\}$ that have only cycles of even length. Let $Y(n)$ denote number of all permutations of the same set that have only cycles of odd length. Count $X(2n)-Y(2n)$. I don't know…
michaels
  • 61
6
votes
2 answers

Prove that a relation is symmetric and anti-reflexive

I have the set $V = \{ -n, -(n-1), -(n-2), ... , -2, -1, 0, 1, 2, ... , n-2, n-1, n\}$ and the relation over it $xRy \iff x + y$ is a power of $3$ and I need to prove that it is symmetrical and anti-reflexive. So $x + y$ is the same as $y + x$, and…
N3X
  • 127
6
votes
5 answers

Calculate number of small cubes making up large cube given number in outermost layer

I have a large cube made up of many smaller cubes. Each face of the cube is identical, and all of the smaller cubes are identical. I need to calculate the number of small cubes that make up the large cube. Just to make it clear, the cube is solid…
eskimo
  • 163
1 2
3
…
99 100