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

How would you solve this recurrence equation: $a_{n+1}-2a_{n}=6\cdot 5^n$ for $n\geq 1$

How would you solve $a_{n+1}-2a_{n}=6\cdot 5^n$ for $n\geq 1$ ? I don't understand the text in my textbook. I Would like somebody to explain it to me.
user50222
  • 978
5
votes
1 answer

Number of relations that are both symmetric and antisymmetric?

Because one relation cannot be symmetric and antisymmetric in relation to another, but is always symmetric and reflexive to itself, there are 2^n relations (relations in the diagonal only). Is that right?
Jane
  • 105
5
votes
2 answers

Direct Proof - Discrete Mathematics

I am given Prove that there are no integer solutions to the equation $$x^2=4y+3$$ I started off by proving the square of the integer is either $0 \pmod{4}$ or $1 \pmod{4}$. If $x$ is even then $x=2k$ for some integer $k$. Then…
user476504
  • 65
5
votes
0 answers

Discrete version of Intermediate Value Theorem

In this post the author states a discrete version of the Intermediate Value Theorem as follows: For integers $ a < b $, let $ f $ be a function from the integers in $ [a, b] $ to $ \mathbb{Z} $ that satisfies the property, $ |f(i + 1) - f(i)| \leq…
user392330
5
votes
3 answers

What is the number of all possible relations/intersections of n sets?

If n defines number of sets, what is the number of all possible relations between them? For example, when n = 2: 1) A can intersect with B 2) A and B can be disjoint 3) A can be subset of B 4) B can be subset of A that leaves us with 4 possible…
mathguy
  • 53
5
votes
2 answers

Fibonacci Number Proof

How can I prove this statement? Would I use induction? "Given $n \geq 11$, show that $a_n > (3/2)^{n}$. $a_n$ is the $n$th Fibonacci number."
user41419
5
votes
1 answer

Given sets A and B such that A ⊆ B, write down A ∪ B in a simplified form.

Here's how I did it: Let A = {1,2,3} Let B = {1,2,3,4,5} Since A ∪ B, everything in A would also be in B thus the simplified form would be B? If it's wrong, please let me know how to go about this, thanks.
potatofeast
  • 107
5
votes
1 answer

How many positive integers less than 1000 have distinct digits and are even?

I am not looking for an answer on this. Just need to clarify why my approach is failing - $N_1 + N_2 + N_3$, i.e. single digit, double digit, 3 digit single $= 2, 4, 6, 8$, i.e 4 double = X non-zero $= 8 \cdot 4 = 32$ X zero $= 9 \cdot 1 = 9$ Now…
totalmoksh
  • 51
5
votes
2 answers

proof by contradiction puzzle

Consider the following game between two players: • There is an initially rectangular grid of cookies. • The cookie in the upper left corner is poisoned. • The players take turns. On a player’s turn, he or she must eat some cookie, along with every…
Abhi
  • 237
5
votes
1 answer

Generalized way to solve $x_1 + x_2 + x_3 = c$ with the constraint $x_1 > x_2 > x_3$?

On my example final exam, we are given the following problem: How many ways can we pick seven balls of three colors red, blue, yellow given also that the number of red balls must be strictly greater than blue and blue strictly greater than…
MT_
  • 19,603
  • 9
  • 40
  • 81
5
votes
4 answers

Prove or disprove: if A is a subset of B and B is not a subset of C, then A is not a subset of C

Prove or disprove: if A is a subset of B and B is not a subset of C, then A is not a subset of C. I know it is false for the counter example: A = {1, 2} B = {1, 2, 3, 4} C = {1, 2, 6, 5} How can I prove that mathematically?
Franceia
  • 159
5
votes
1 answer

Is an empty set reflexive? Symmetric? Transitive?

Suppose $$A\neq\emptyset$$ Since, $$\emptyset\subseteq A\times A$$ the set $$R=\emptyset$$ is a relation on A. Is $R$ reflexive? symmetric? transitive? I remember hearing something can be "vacuously" true. So the empty set would be reflexive,…
Hare Krishan
  • 221
5
votes
3 answers

How many pairs of two distinct integers chosen from the set {1, 2, 3, ..., 101} have a sum that is even?

My Attempt: N(even numbers between 1-101) = 50 N(odd numbers between 1-101) = 51 Since pair of two distinct integers that have a sum that is even can only be 1. odd + odd 2. even + even Thus, the answer is 51C2 + 50C2 = 2,500 Is my answer…
Margo Eastham
  • 209
4
votes
0 answers

An interesting math problem I created for an old-school RPG game.

The point of this is to try to have the best stats as possible at the beginning of the game and stay at level 1 before doing any quests. Starting group at creation menu: Stat Cleric Sorcerer 1 Sorcerer 2 …
vxs8122
  • 239
  • 2
  • 7
4
votes
3 answers

How to prove that $4^m + 5^m$ is divisible by 9 when m is an odd number

I am trying to use congruence theorems, specifically Euler's Theorem for a proof.
user169080
  • 41
1 2 3
…
99 100