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 that this function is onto and one-to-one

$f:Z \rightarrow Z$ $f(x) = x-5$ , when $x$ is odd $f(x) = x+3$ , when $x$ is even It seems that it is not onto, because not all integers are covered, but how do you show this?
George Steinberg
  • 11
1
vote
3 answers

How do you evaluate high powers in modulo expressions?

How would you evaluate $ 2^{2143} \pmod{17}?$ For instance, I was looking through my notes and the example I have is : $5^{131} \pmod{14}$ We look at the powers $ 5^i$ modulo $14$ and notice that they repeat at $i = 6$ Now since $131 = 5 \pmod{6}$…
Maggie
  • 41
1
vote
2 answers

Prove that the following function is onto and one-to-one

$$f:\Bbb Z^2\to\Bbb Z^2:{n\brack m}\mapsto\begin{bmatrix}3&2\\4&3\end{bmatrix}{n\brack m}$$ it is onto because: $$\left\{\begin{align*}&m = 9d - 4s\\ &n = 6d + 3s\end{align*}\right.$$ (after solving the system of equations) onto because m and n are…
Gladstone Asder
  • 1,051
1
vote
3 answers

Find closed form for $a_{1}=2, a_{n}=a_{n-1}+n+6$

I have determined that $a_{2} = 10, a_{3} = 19, a_{4} = 29, a_{5} = 40, a_{6} = 52,$ and $a_{7} = 65$. I can see that there is a pattern in that each value increases by 8, then 9, then 10, then 11, then 12, etc. but I am having difficulty making an…
Pizza Pizza
  • 89
1
vote
2 answers

Proof by Contradiction, Euler path

I know that with Contradiction I am suppose to supply a proof that says basically that we keep the first part true but the 2nd part false. For me, If an un-directed graph has more than 2 vertices of odd degree, it does not have an Euler Path. I…
J Crawford
  • 67
1
vote
0 answers

Shared rationals in base pi

Is there a theorem on rational numbers in irrational bases? For example $100$ in base $\sqrt{2}$ is $2$, so it's an integer in both bases, but are there shared integers and rationals in base $\pi$? Or even is there a polynomial evaluated at $\pi$…
Hovestar
  • 111
1
vote
1 answer

For $A,B\in\mathcal P(X)$, question about the relation of having an empty intersection

Let $X$ be a set. Define a relation $\rm R$ on the power set $\mathcal P(X)$ by $$A \operatorname{\rm R} B ~\iff~ A \cap B = \emptyset$$ for $A,B \in \mathcal P(X)$, do determine whether this relation is reflexive, symmetric, and/or transitive. Ok…
J Crawford
  • 67
1
vote
2 answers

Discrete Mathematics, Equivalence Relations

Give the specific reason why the following set $R$ does not define an equivalence relation on the set $\{1,2,3,4\}$. R$=\{(1,1)(2,2),(3,3),(4,4),(2,3)(3,2),(2,4),(4,2)\}$. Reflexivity For any a ϵ S, $aRa$. Symmetry For any a,b ϵ S, $aRb \iff…
J Crawford
  • 67
1
vote
4 answers

finding range from a function

I have a function: and the range the solution gave was: im having trouble figuring out how the range is obtained. i couldn't picture it and i need some explanation on how a range is obtained of a function given.
Electric
  • 323
1
vote
1 answer

Proving that every graph that each vertex at degree 2 must contain a cycle

Prove that every graph in which each vertex has degree at least 2 must contain a cycle. I know that a vertex is a node and the only way for it to have a cycle is that when there are three vertices and three edges and that the shape is of a triangle.…
a_student
  • 51
1
vote
1 answer

Proving exponential properties of sets

I am stuck halfway through this problem, and I feel like it should be easier than I am making it. :( I need to prove that $A^{B×C}$ and $(A^B)^C$ are a bijection where A, B and C are all sets. Anyway, this is what I have so far. $g \in A^{B×C}$…
babayaga
  • 85
1
vote
1 answer

Discrete math: create general formula

I am asked: For any real number $x$ and positive integer $k$, define the notation [x,k] by the recursion $[x,k+1] = (x-k) [x,k]$ and $[x,1] = x$. If n is any positive integer, one can now express the monomial $x^n$ as a polynomial in $[x,1],…
Nick
  • 489
1
vote
2 answers

Finding the cardinality of a set where $x$ is greater than $1$

Let $A = {2x : x ∈ Z, -16 <= x <= 4}$. What is the cardinality of this set? What would be the translation of this to plain english?
calimses
  • 185
1
vote
1 answer

How to find closed formula for the sum of the first n odd perfect squares?

I do know formula for finding sum of squares of n odd numbers but I am not sure how to find closed formula. Note: From closed formula I mean a reduced fraction in factored form, with no ellipses (“. . .”) in it.
Andre
  • 19
1
vote
1 answer

Is set $A$ transitive if $A$ only have urelement (or have urelements)?

For example, is $A=\{-1\}$ a transitive set? In wiki, it is said that: A set $A$ is called transitive if either of the following equivalent conditions hold: whenever $x ∈ A$, and $y ∈ x$, then $y ∈ A$. whenever $x ∈ A$, and $x$ is not an urelement,…
ENE KaIku
  • 21
  • 2
1 2 3
…
99 100