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

Can a surjective composition be made with 1 function that is not surjective (if they both share an identical domain and codomain)?

Let $X$ be a set, and let $f:X \longrightarrow X$ and $g:X\longrightarrow X$. Can you get a composition of $f$ and $g$ ($f\circ g$) that is onto (surjective), if $g$ is not onto? I can't seem to find an example of such a function. Thank you for your…
royvicproust
  • 13
1
vote
1 answer

Does a (simple undirected) graph have an Euler cycle if it has at least one vertex of odd degree?

Does a (simple, undirected) graph have an Euler cycle if it has at least one vertex of odd degree, or is that statement false? Since it has at least one vertex of odd degree, it has at least two, right? So it can but it mustn't, right?
Zap
  • 119
1
vote
1 answer

How can we use the derivative of f(x) to determine if its injective?

I'm not sure if I have the right idea: suppose you find the derivative of a function and $f'(x) > 0 $ or $f'(x)< 0$, does that mean it is injective? The derivative has to be one or the other to be injective? Thank you!
jaz
  • 13
1
vote
0 answers

If a and b are real numbers and a≠0, then there exists a unique real number r such that ar + b = 0

Two parts to this question: a) Use a CONSTRUCTIVE proof to show the existence of r and b)Use a proof by CONTRADICTION to show the uniqueness of r For a) I wrote: Consider ar+b =0, a≠0 and the premise that the real number r = -(b/a) will cause the…
Zevias
  • 109
1
vote
3 answers

Discrete Math: Equivalence relations and quotient sets

For each of the sets below and the corresponding binary relation, prove that the relation is binary relation and find the quotient set. (a) Let A={1,2,3,4,…} be the set of natural numbers. Consider the binary relation R on A defined by: for all…
Frodo Baggins
  • 89
1
vote
1 answer

Surjection and Injection

How can I prove that the following function is neither injective nor surjective? How can I change the domain and codomain in order to make the function both injective or surjective? All finite subsets of Z→ Z given by h(L) = |L|. My main…
Bob_Bobb
  • 339
1
vote
3 answers

You are asked to evaluate a proof attempt of a proposition p which begins with the assumption:

You are asked to evaluate a proof attempt of a proposition p which begins with the assumption: Suppose if p is false and performs a set of correct derivations and ends with the conclusion: Therefore, we conclude that p is true. Does this attempt…
Comp Droid
  • 13
1
vote
2 answers

Inverse function mod

$$ y = 3x + 7 \pmod 4,\quad x,y \in \mathbb{Z}_4 $$ $x = 2, y =$ ?? Find the inverse function and verify the value of $y$. I solved only the first question $y = 13\bmod 4 = 1 \bmod 4. How to solve the second question for inverse?
Eleni Kara
  • 11
1
vote
1 answer

Finding the number of possible anagrams for $n$ lettered words

Let's say we have a $n$ letter word, and we want to find the number of possible anagrams. For example, "cat" would have $6$ possible anagrams, because: "cat", "cta", "act", "atc", "tac", "tca" are the possible rearrangements. Another example would…
K.Hu.1106
  • 71
1
vote
1 answer

Inverse function and cardinalities

Question: We'll define a function between two sets A and B: $H: ((A \cup B )\to ${0,1} ) $\to ((A \to ${0,1}) $\times (B \to ${0,1})) $H= \lambda f \in (A \cup B ) \to ${0,1}$.<\lambda a \in A . f(a),\lambda b \in B.f(b)>$ If H is invertible, what…
jreing
  • 3,297
1
vote
0 answers

Extending Binomial Theorem property for combinations with repetitions allowed

So today in my lecture my prof went over this property of the binomial theorem when dealing with combination problems that allow repetitions The number of nonnegative integer solutions of the equation: $x_1 + x_2 + · · · + x_n = r$ where you can use…
Zach Lederman
  • 91
1
vote
0 answers

Question about equivalence classes having values not in given set and missing given set values.

I think I'm missing something about equivalence classes here. My answer is very different from the books answer and I'm confused as to what is happening. The task: On the set of nonnegative integers, we can define a relation x (triple bar) y if and…
Eric W
  • 11
1
vote
2 answers

How many students must be in class to guarantee that at least two students get same score on exam if the exam is graded on scale 0 to 100 points?

I have done n=101(pigeon holes) k+1=2 k=1 k.n+1(pigeons)=1.101+1=102 please! can anybody help to find this is right or wrong.
Gone Lastvirus
  • 59
1
vote
2 answers

Question about the particular part in a non homogeneous recurrence

Question about the particular part in the following non homogeneous recurrence : $$a_n - 6a_{n-1} + 9a_{n-2} = n * 3^n $$ I have the following particual part : $$ a_n = n * 3^n$$ Now the solution of the homogenous part is $$x_1 = 3, x_2 = 3$$ and…
kokayy
  • 49
1
vote
3 answers

For ax % b = c, where a, b, and c are known, how do I find a compliant x?

I just asked this question on stackoverflow.com and had it closed before I could get any reasonable help, with the suggestion to move it to a math site. I don't understand the math, and don't speak the math speak, and need an algorithm, not simply…
Steven
  • 13
1 2 3
…
99 100