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

Logic and proof

I had an assignment from class, to proof for all real numbers $R$, $x$ is subsets of $R$, if $x^2 - 2x\ne -1$, then $x\ne 1$. in contrapositive proof and contradiction. So far with my knowledge, I should construct a direct proof, and show that it…
Minjae
  • 207
3
votes
1 answer

Applications of propositional logic

I'm working on this propositional logic question and I did not understand the book answer at all. The book says the hostess knows to bring back two drinks for the first two professors. When three professors are seated in a restaurant, the hostess…
user1238097
  • 107
3
votes
2 answers

proving a function as surjective

How can I prove a function is surjective? In the function $f: \Bbb{R}\to \Bbb{R}$, $$f(x) = 4x+7$$ we take $x = y-\frac{7}{4}$ and show that $f(x)=y$. How can this method prove that this function is surjective. Could someone explain this please?
Ampatishan Arun
  • 121
3
votes
0 answers

Understanding $\sum^n_{k=0}\binom nk x^k y^{n - k}$ combinatorially

In a class of $n$ students, each student is given the choice of solving either one of $x$ different algebra problems or one of $y$ different geometry problems. How many different outcomes are possible? I'll consider a special case where $n =…
Shaniqua
  • 31
3
votes
2 answers

When do we use multiplication instead of addition?

In a class of $n$ students, how many ways can we choose a size $k$ committee that contains a size m subcommittee? The committee can be chosen in $\binom nk$ ways and subcommittee can be chosen in $\binom km$ ways. So the answer is $\binom…
shake-up
  • 67
3
votes
3 answers

How to prove this argument valid?

I was just wondering if some helpful person wouldnt mind helping me with this discrete maths question that has had be stuck for about a day now. The argument is: p or q q implies ~p q implies r conclusion: r I cant for the life of me figure out how…
Fishingfon
  • 559
3
votes
2 answers

How to simplify expression with Fibonacci numbers

I have to simplify the expression $\sum_{n=0}^\infty \sum_{k=0}^n \frac{F_{2k}F_{n-k}}{10^n}$. I only noticed that $\sum_{n=0}^\infty \sum_{k=0}^n \frac{F_{2k}F_{n-k}}{10^n} = \sum_{n=0}^\infty \frac{1}{10^n} \sum_{k=0}^n F_{2k}F_{n-k}$. What to do…
alex
  • 33
3
votes
2 answers

Power Set of a Power Empty Set

Find ℙ(ℙ(ℙ(∅))). I know that ℙ(∅) = {∅}. Then, ℙ(ℙ(∅)) = {∅, {∅}, {∅,{∅}}? so, ℙ(ℙ(ℙ(∅))) = {∅,{∅, {∅}, {∅,{∅}}}? Is it? Will it be ok if someone explain to me this concept?
eLg
  • 221
3
votes
2 answers

Can I cancel out factorials in proofs?

I encountered the following question in a discrete math course: Prove that $ \binom{2n}{k-1} < \binom{2n}{k} $ for $k = 1, 2, \ldots , n$. Hint: This should be a very cleanly written proof. I'm working through this proof and I'm at a step…
Cintra
  • 95
3
votes
2 answers

Find the five different equivalence relations on the set {a,b,c}

What is the best way and easiest way to approach this problem? My first relation is going to be defined as such R = {(a,a), (b,b), (c,c)} which is reflexive, symmetric, and vacuously transitive. My second relation will be defined as such R = {(a,a),…
Hare Krishan
  • 221
3
votes
2 answers

Help with the Basis Step of a strong induction proof

I have to determine whether the following definition is valid and, if so, find a formula for $f(n)$. $f(0)=1$, $f(1)=0$, $f(2)=2$, $f(n)=2f(n-3)$ for $n \geq 3$ I know it is valid because I successfully get a result for $f(3)$, $f(4)$, $f(5)$ and so…
JORGE
  • 341
3
votes
5 answers

Direct proof for $\left (1+ \frac11\right )\left(1+ \frac12\right )\left(1+ \frac13\right )\cdots\left(1+ \frac1n \right) = n+1$

I have a question where I need to use a direct proof to show that: $$\left (1+ \frac11\right )\left(1+ \frac12\right )\left(1+ \frac13\right )\cdots\left(1+ \frac1n \right) = n+1$$ I am not allowed to use mathematical induction. I have no idea where…
Rachel
  • 85
3
votes
1 answer

Battleship game - logic for positioning ships

I'm working on a project where I'm programming a battleship game using objected-oriented principles of programming. I got stuck at one problem that is purely mathematical and relates to the positioning of the battleships. I would like to ask you…
luqo33
  • 157
3
votes
1 answer

Deduce the conclusion from the premise.

Use the valid argument form to deduce the conclusion from the premises, giving a reason for each step. A. ~p v q ➵ r B. s v ~q C.~t D. p ➵ t E. ~p Λ r ➵ ~s F. (conclusion) ~q So Far this is my work. p➵ t ( p implies t, if p then t, modus…
Jon
  • 1,920
3
votes
2 answers

Discrete Math Proof: $A \cup B$

I'm preparing ahead for a Discrete Math course coming up this year by doing some practice problems supplemented by online notes. The problem I'm having trouble proving is the following: $A \cup B = (A \cap B^C) \cup (A^C \cap B) \cup (A \cap B)$,…
xxyyzz
  • 45
1 2 3
…
99 100