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
2
votes
1 answer

How many integers in $M$ are neither odd nor multiples of $6$?

I am having trouble understanding this exercise from my study guide: Let $M = \{5k + 1 \mid k \in \mathbb{Z}, 0 \le\ k \le\ 240\}$. How many integers in $M$ are neither odd nor multiples of $6$? Given Answer: Let $A = \{x \in M \mid x \text{ is…
user92986
2
votes
4 answers

Proving that $n^2 + n$ is even for any integer $n$

This type of question often shows up in introductory abstract math courses, computer science discrete math, or an introduction to logic course. Show that $n^2 + n$ is even for any integer n.
nodebase
  • 476
2
votes
1 answer

Modulus at its finest(what is definition of modulus?)

Found this question on a previous exam: What is the answer of the following expression? $$(1!+2!+3!...+100!)\pmod{18} =$$ The answer $0$ isn't right! If you know the answer please explain me it step by step. Any help will be appreciated!
Gil
  • 707
2
votes
2 answers

Prove that $t$ is a one-to-one correspondence.

I am having problems with this discrete math proof. I have made it this far, but I do not understand how to go from here. Problem: Define a map $t: \mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R} \times \mathbb{R}$ by $t(a, b) = (a + b, a -…
Dan Hill
  • 23
2
votes
1 answer

Negating logical statement of continuity

I need help negating the following statement please, or if anyone could help putting it into words: $$\forall \epsilon > 0 (\exists d>0(\forall x_0 (\forall x(|x - x_0| < d \implies |f(x) - f(x_0)| < \epsilon))))$$
Emilio B.
  • 79
  • 5
2
votes
2 answers

(Dis)Prove $\forall x \in \mathbb{R}, \sqrt{x^2} = x$

I'm in my discrete math class, and I'm being asked to prove or disprove: $\forall x \in \mathbb{R}, \sqrt{x^2} = x$ I think that would be false because I know that when you square a negative number, the result is positive. HOWEVER the reason that…
Hayden
  • 97
2
votes
0 answers

Proof for Discrete Math Noticing

The other day while biking I realized that if you multiply a single digit number by a multi digit number, and then add the digits together until you got to a single digit number, it would have the same final digit as if you added the multi digit…
Hannah Goldberg
  • 31
2
votes
1 answer

Why is the relation $∣x-y∣ \geq 1$ on a set of positive integers not transitive?

Why is the relation $∣x-y∣ \geq 1$ on a set of positive integers not transitive? According to my professor it is not a transitive relation but I'm having a hard time finding cases to satisfy this.
Ryan Garcia
  • 33
2
votes
1 answer

Proof for Inclusion-exclusion doesn't make sense

Im currently trying to grasp my professors proof for Inclusion-exclusion, and there is one part of his proof that just doesn't make sense to me and I was hoping for some help here. Theorem: Let $A_1,A_2, ... , A_n$ be finite sets. Then…
uoiu
  • 593
2
votes
2 answers

Non-decimal base conversion algorithm

I'm looking for a general method of radix conversion, that might be performed without using decimal system at all. Given a number $x$ in base $b_1$, and I want to convert it to the base $b_2$, where $x, b_1, b_2$ are positive integers and $b_1, b2…
Elena
  • 117
2
votes
1 answer

Subset product series

I have the following series: S3 = 1/1 + 1/2 + 1/3 + 1/1*2 + 1/1*3 + 1/2*3 + 1/1*2*3 The question is to find a formula to produce this series (Sn) I'm kinda stuck here. I know you can determine the number of subsets of a set A by 2^|A| but I'll need…
Christophe De Troyer
  • 157
2
votes
1 answer

What is a function $f : 2^n \rightarrow n$ such that for each $y \in n$ and $A \in 2^n$ there is $x \in n$ such that $f(\tau(x,A)) = y$?

We first set up some notations and definitions: We view each positive integer $n$ as a (particular) set of $n$ elements. We also pick some bijection $\phi_n : 2^n \xrightarrow{\approx} \mathcal{P}(n)$, where the codomain denotes the power set of…
I.A.S. Tambe
  • 2,431
2
votes
2 answers

Trouble solving Non-Homogeneous Recurrence relations

The following is the prompt I am working on: Suppose you have an investment account which grows by 10% every year, and you want to, in perpetuity, withdraw an increasing amount of money from this account, starting with 1 dollar at the end of the…
user1154312
2
votes
1 answer

Proof of additive counting principle?

In my "Discrete Structures" textbook, the Additive Counting Principle is defined as: If $\{S1, S2, . . . , Sm\}$ is a partition of a finite set S, then $|S| = |S1| + |S2| + · · · + |Sm|$. However, it goes on to say that A formal proof would…
Merlin04
  • 123
2
votes
1 answer

Number of balanced partitions of a set

Question: A balanced bipartition of set $X$ splits $X$ into two parts $A$ and $B$ so that the sizes of $A$ and $B$ differ by at most $1$. In particular, when $X$ is even, $|A| = |B| = \frac{|X|}{2}$; when $|X|$ is odd, $|A| = |B|—1 = \lfloor…
Node.JS
  • 1,119
1 2 3
…
99 100