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

Prove P( A intersect B) is greater than 0.4

Hey guys, so $P(A) = 0.8$ and $P(B) = 0.6$. Since we know $P(A \cup B) \leq 1$ then if we add $P(A) + P(B)$ we get $1$. So because it exceeds 1, that means $A$ and $B$ are NOT mutually exclusive? Is that right? And since they are not mutually…
Stuy
  • 1,149
1
vote
1 answer

how to prove $T(n) \le 2^{n-1}$ , $T(n)$ is the number of way that write n as the sum of 1's and 2's

how to prove $T(n) \le 2^{n-1}$ , $T(n)$ is the number of way that write n as the sum of 1's and 2's such as n = 3, T(n) =3, because 3 = 1+1+1, 3=1+2 ,3 =2+1.
tywtyw2002
  • 89
1
vote
1 answer

Negation - Some operating systems always crash

I am trying to find the negation of the statement "Some operating systems always crash" I know that the negation of "some" is "all" so: All operation systems always crash ? Or: All operation systems never crash ? I don't understand what to do with…
CUPA
  • 79
1
vote
2 answers

Problem with solving the recurrence relation $a_n=a_{n-1}+6a_{n-2}+30$ for $n\geq2$, $a_0=0$, $a_1=-10$

My task: $a_n=a_{n-1}+6a_{n-2}+30$ for $n\geq2$, $a_0=0$, $a_1=-10$ My solution $x^{2}-x-6$ $\Delta=25$ $x1=-2 $ $x2=3$ So I am gonna use following…
Gorosso
  • 85
1
vote
4 answers

Solve recursion $a_n=a_{n-1}-6\cdot3^{n-1}$ for $n>0, a_0=0$

$a_n=a_{n-1}-6\cdot3^{n-1}$ for $n>0, a_0=0$ So I calculate first terms $a_0=0$ $a_1=-6$ $a_2=-24$ $a_3=-78$ I don't see any relation so $a_n=a_{n-1}-6\cdot3^{n-1}$ $a_{n-1}=a_{n-2}-6\cdot 3^{n-2}$ . . . $a_2=a_1-6\cdot3^{1}$ $a_1=a_0-6\cdot…
Gorosso
  • 85
1
vote
1 answer

Determine the sequence generated by a generating function

$A(z)=2z-1+\frac{1}{2z-2z^2}$ I have no clue how to solve this, I tried looking at other examples but I am just stuck, could anyone be so kind and explain how to solve this step by step?
Gorosso
  • 85
1
vote
1 answer

Find the least value of A+B

111A09201B/9 has a remainder of 5. find the least value of A+B This is from a competitive mathematics contest and I have no idea how to go about solving it. If anyone here would like to help me not only help with this question but help improve my…
Tylor Gonzalez
  • 11
1
vote
2 answers

Countable set - $\aleph_0$ or finite?

I have 100 sets $A_1,\ldots,A_{100}$. They are all subsets of $\Bbb R$. For each $A_i$ the complement of $A_i$ in $\Bbb R$ is a countable set. $A= A_1 \cap A_2 \cap \ldots \cap A_{100}$. $B$ is the complement of $A$. What is the cardinal number of…
user3523226
  • 109
  • 1
  • 10
1
vote
1 answer

How to understand the rule of product in discrete mathematics?

Proposition 2.6 (Rule of Product). Let T be a set of ordered k-tuples ($a_1$, ..., $a_k$), with the property that there are $r_i$ choices for each coordinate between 1 $\leq$ i $\leq$ k. Then |T| = $r_1$$r_2$ ... $r_k$. I am taking an introductory…
Metaozis
  • 177
1
vote
1 answer

Consider $X$ a countably infinite set, is $\{X \cup x\}$ with $x \notin X$ countably infinite?

$x$ represents an element, not a set. Assume $S:=\{X \cup x\}$ is countably finite. This means that there is a bijection between $S$ and a subset of $\mathbb{N}$. This is clearly not the case since $X$ is infinite. I don't really know how to write…
MyWorld
  • 2,398
1
vote
2 answers

Given a relation $R$, what is the $R^{-1}$, and what is the complement of $R$ on $A$?

For example if I have the following group $A$ and a relation $R$: $$A= {1,2,3}$$ $$R= \{(1,1)(2,2)(3,3)(1,2)(3,2)\}$$ $$R^{-1} = ?$$ $$R^C = \;?$$ Thanks.
user3523226
  • 109
  • 1
  • 10
1
vote
2 answers

When is A a subset of the power set p(A)?

I can across a video (here's the pic: [Discrete Math 1] Subsets and Power Sets) and the author mentioned the following: Is A ⊆ p(A) for any A? No. Is A ∈ (A) for any A? Yes. p(A) is the power set of A in this example. I agree with these two…
supmethods
  • 117
1
vote
1 answer

Logic problem: Truth value of statement the product of $x^2$ and $x^3$ is $x^6$

I want to understand why these statements below are false. I assumed that the statements are true because they are real numbers The product of $x^2$ and $x^3$ is $x^6$ The $x^2>0$ for any real number $x$
Sam
  • 865
1
vote
0 answers

What is the expected number of matching pairs in a stable matching problem

What is the expected number of matching pairs in a stable matching problem involving n companies and n applicants where each company and applicant has their own independently generated preference list?
hussain sagar
  • 175
1
vote
3 answers

Need Help With Elementary Proof

Prop: For sets A and B, say A ~ B iff there exists a bijection from A to B. Then ~ is an equivalence relation on sets. I understand that an equivalence relation holds the properties of reflexive, symmetric, and transitive. I am also aware of their…
Zdravstvuyte94
  • 101
1 2 3
…
99 100