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

Graphs Isomorphisms Degrees

I'm not exactly sure if I'm right but I wanted to double check on how I approached this problem. If its wrong, can you please provide me with hints or suggestions or maybe an answer which an explanation? So since there are 12 * 5 = 60 / 2 = 30…
Roy Kesserwani
  • 383
1
vote
2 answers

Which of these functions $\mathbb N\to\mathbb N$ are strictly increasing?

$f(n) = (1+n)^2$ $f(n) = \lfloor\log(n)\rfloor$ $f(n) = \lfloor\sqrt{n}\rfloor$ $f(n) = (1-n)^2$ I am having a hard time understanding what strictly increasing means. Aren't all of these functions increasing? I know the squared ones are decreasing…
djhunterx
  • 21
1
vote
3 answers

Composition and Onto Functions

Exercise: If $f:X\rightarrow Y$ and $g: Y\rightarrow Z$ are both onto functions, prove or disprove, $g\circ f:X\rightarrow Z$ defined by $(g\circ f)(x)=g(f(x))$ is an onto function. Just a little confused on how to do this problem. I know what an…
Roy Kesserwani
  • 383
1
vote
2 answers

finding boolean function truth table

Can anyone explain this $P \rightarrow Q$ and how do we get true,false,true,true from the truth table in the third column? I know the first two colums but i am confused how to get the third row.can anyone help me I am really confused. Furthermore,…
nelson
  • 33
1
vote
2 answers

Counting techniques problem

How many numbers greater than $50,000,000$ can be formed by rearranging the digits of the number $13,979,397$? Can someone give me a hint?
user124557
  • 159
1
vote
1 answer

Quantified statement with contrapositive

I have this statement $$\forall x: P(x) \implies Q(x)$$ If I want to take the contra positive with the $\forall$ change to an $\exists$.
wolfcall
  • 401
1
vote
1 answer

what is the cardinality of each of these sets?

I am confused on these questions I feel like that are too easy. I just need to find the cardinality of each of the 3 problems. I believe that the first one and third one is a zero with a slash through it. Then the second question I believe is 3. Can…
rick
  • 197
1
vote
3 answers

Prove or disprove that if one root of a quadratic equation is rational, then the other root must be rational as well.

I'm taking an introduction to discrete math course and I'm having some trouble with this homework problem. I think we're supposed to assume that the coefficients are integers based on other examples we've been given and if they are I think I…
Nathanial
  • 11
1
vote
1 answer

Set Theory Principle of Inclusion and Exclusion

1000 households were surveyed. 275 households own a desktop computer, 455 households own a DVD player, 405 households own two cars, 145 households own a desktop computer and DVD player, 195 households own a DVD player and two cars, 110 househods…
Kot
  • 3,273
1
vote
1 answer

Help mathematical induction

Prove by mathematical induction. I was hoping if someone could give me a hint on how to solve this problem. $$\frac{1}{1^2}+ \frac {1}{2^2} + ....+ \frac{1}{n^2} < 2 - \frac {1}{n} $$ for all integers $n\geq 2$.
user124557
  • 159
1
vote
1 answer

Prove for any $n \geq 1$...Recursion?

I am practicing review problems to practice from what what we last learnt in lecture, and I admit I am very lost. I have no idea how to start these sort of problems Prove for any $n \geq 1: F_1 + F_3 + F_5 + \cdots + F_{2n-1} = F_{2n}$ where $F_n$…
user3248
  • 11
1
vote
1 answer

Set notation & Identities (Proof)

The following questions require a true/false statement as well as a supporting claim. I'm having a hard time understanding set notation as well as their identities. This is my understanding (tentative answers) so far: False, $A\cup B$ intersects…
petrov
  • 335
  • 2
  • 5
  • 12
1
vote
1 answer

Calculate $\sum_{A,B \subset X} |A \cup B|$ for $|X|=n$

I need to calculate the sum $\sum_{A,B \subset X} |A \cup B|$ for $|X|=n$ Well I guess we can think of $X=\{1,...,n\}$. Well, in my opinion this is basically this. $\sum_{k=1}^n {{n}\choose{k}}*2^{k-1}$, because first we choose which elements…
Arek Krawczyk
  • 2,114
1
vote
2 answers

How many different ways of putting circles on $OX$.

I can draw $n$ circles on a straight line $OX$. I can either draw two circles some distance from each other (can't touch each other), or I can draw a circle inside another circle. Two arrangements of circles are the same iff there exists a bijection…
Arek Krawczyk
  • 2,114
1
vote
0 answers

Prove that |R[0,1)| <= |F| where F is the set of all functions from N to {0,1}

I believe that I need to show that there's a one-to-one function from R[0,1) to F and that I can do this by associating the decimal expansion .b_1b_2b_3... etc with a function f(n) that is either 0 or 1 based on some property of the digit b_n in the…
user126571
  • 11
1 2 3
…
99 100