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

Need help using the Inclusion-Exclusion Principle to count the overlaps between 4 sets?

In a class, 18 students like to play chess, 23 like to play soccer, 21 like biking, and 17 like jogging. The number of those who like to play both chess and soccer is 9. We also know that 7 students like chess and biking, 6 students like chess and…
Chloe
  • 21
2
votes
1 answer

Infinite bit strings with property

For an element $x \in \{0,1\}^{\mathbb{Z}}$, define $S(x) = \{ (x(i),x(i+1), \dots , x(i+r)) : i \in \mathbb{Z} , r \in \mathbb{N} \}$, where $x(i)$ is the $i^{th}$ coordinate. $S(x)$ denotes arbitrary $\{0,1\}$ $r$-tuples such that it matches a…
user100101212
  • 2,066
2
votes
2 answers

Find the recurrence solution of this relation

How would we find the solution of the recurrence relation: $a_n = 2a_{n−1} + 3 · 2^n$ ? After trying it, I've found it to be $a_n = 2^{n-1} (c_1 + 6n)$ Not sure if this is right.. Thanks!
tekman22
  • 642
2
votes
4 answers

Discrete Math: Writing Proofs

1) How do I prove the following: Let A = {6a + 4b ∈ Z : a, b ∈ Z} and B = {2a ∈ Z : a ∈ Z}. Show that A = B. Thank you all for the help!
oreo
  • 33
2
votes
1 answer

Showing a bijection between binary string sets.

I am working on showing a bijection between two sets: $B^6$ and $E_{10}$. Here is the problem: Let $B = {0, 1}$. $B^n$ is the set of binary strings with $n$ bits. Define the set $E_n$ to be the set of binary strings with $n$ bits that have an even…
GainzNerd
  • 279
2
votes
0 answers

How to round binaries

I was given this question as homework but unfortunately amid this COVID time schools are down and so prof is not too clear in his explanation and the book does not mention anything regarding rounding, only how to convert. Books: "Fundamentals of…
Intern
  • 51
2
votes
1 answer

Need Help Simplifying Set Expression Using Set Identities

one of the questions in our textbook requires us to simplify a set expression using set laws such as distributive laws, associative laws and so on. $$ ((A\cap (B\cup C))\cap (A-B))\cap (B\cup C') $$ Here's what I have so far. $$ ((A\cap (B\cup…
Jacynth Tham
  • 21
2
votes
1 answer

Clarifying the definition of antisymmetry (binary relation properties)

An anti-symmetric relationship says that there is no pair of distinct elements of set $A$ which are related by $R$ to the other. A relation is anti-symmetric if for every pair of distinct elements in the domain one of the following situations…
GainzNerd
  • 279
2
votes
2 answers

Im not even sure what this questions means, im totally lost on this one.

Show that $\gcd(n,\theta)=1$, and find the inverse $s$ of $n$ modulo $\theta$ satisfying $0 < s < \theta$ for $n=7$ and $\theta=20$.
Chandler K Sharp
  • 39
2
votes
2 answers

can the number $x^2 +y^2$ when with x and y positive integers

can the number $x^2 +y^2$ when with $x$ and $y$ positive integers, end in $03$? I know that $x^2+y^2$ can never end with unit digit 03 but am not sure how would I show the proof of that.
Victor Leinad
  • 25
2
votes
4 answers

Injection and surjection of a function

Let $f:(−1,\infty)\to (−1,\infty)$ be defined by $f(x)=x^2+2x $, study the injection and surjection of $f$ , then find the inverse function if exist . So i showed that the function is not $1-1$. my problem is am struggling with showing whether it’s…
user749680
  • 21
2
votes
1 answer

How many 4 digit numbers without $0$ between $1000$ and $9999$ are divisible by $3$?

Determine the number of numbers we can make between $1000$ and $9999$ of $4$ different digits without $0$. How many of those numbers are divisible by $3$? To calculate how many numbers there are between $1000$ and $9999$ of $4$ different…
Henkie
  • 363
  • 1
  • 9
2
votes
1 answer

What does this equal to???

From Rosen's Discrete Mathematics and Its Applications, 3ed, chapter 6 p. 390: There seems to be something missing at the place underlined in red. Could this be ∅ (null symbol)?
J. Doe
  • 405
2
votes
1 answer

Hasse Diagram for cube functions

How do you draw a hasse Diagram for the following example Consider a relation $R$ defined on the set $A = \{-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7\}$. Determine for the $R = \{(a, b) : a^3 = b^3\}$ if the relation is reflexive, symmetric, anti…
jack
  • 113
2
votes
1 answer

mathematical induction natural number

Tell me about this exercise, I try to solve it but it was confusing A bank gives 20\$ and 50\$. I must use mathematical induction so that the bank will create whatever amount of money bigger or equal to 40\$, that it is multiple to 10. Prove that…
ek.Sek
  • 497
1 2 3
…
99 100