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

Geometric Progressions ratio

I don't really know how to find the ratio of 3/2, any ideas? thanks!
Tom1999
  • 117
2
votes
2 answers

Choosing balls from Urn

So suppose you have 7 red balls, 7 blue balls, and 7 white balls, what is the probability of choosing 4 balls of one colour and the last ball of another colour without replacement. Apparently the answer is…
Geralt
  • 313
2
votes
1 answer

An error in a proof due to variable creep?

I'm working through some exam practice questions and I came across this one: Identify the error in the following “proof.” Let u, m, n be three integers. If u|mn and gcd(u, m) = 1, then m = ±1. If gcd(u, m) = 1, then 1 = us + mt for some integers s,…
metisMusings
  • 49
2
votes
4 answers

Understanding delaying or advancing a discrete time signal

Suppose I have a discrete time signal x[n]. It is said that x[n-k], where K>0, is a delayed version of x[n]. I am trying to understand this intuitively. My observation is in the signal I am subtracting time in x[n-k], by k units. Means I am doing…
gpuguy
  • 631
2
votes
1 answer

How to tell if $f(n) = 2 \left\lfloor\frac n2\right\rfloor$ from $\mathbb{Z}$ to $\mathbb{Z}$ is onto?

How can we tell if the function $f(n) = 2 \left\lfloor\frac n2\right\rfloor$ from $\mathbb{Z}$ to $\mathbb{Z}$ is onto? Thanks!
user61867
  • 71
2
votes
1 answer

Transform $3^{n} \mod 7 $ to $ n \mod 7$ form

I want to go from that form $3^{n} \mod 7 $ to something that doesn't use exponent. it says, hint : you should use $ n \mod 7$ I listed the values from $3^0 \mod 7 $ to $ 3^{10} $ $$ 3^0 \mod 7 = 1\\ 3^1 \mod 7 = 3\\ 3^2 \mod 7 = 2\\ 3^3 \mod 7…
Dave
  • 525
2
votes
3 answers

Prove that number $\underbrace{11 \ldots1}_{100} \underbrace{22 \ldots2}_{100}$ is product of two consecutive numbers

Prove that number $\underbrace{11 \ldots1}_{100}$$\underbrace{22 \ldots2}_{100}$ is product of two consecutive numbers $\begin{align}\underbrace{11 \ldots1}_{100} \underbrace{22…
Marko Škorić
  • 1,271
2
votes
1 answer

The second term of an arithmetic series is the third term of a geometric series; etc, etc, etc.

Given the following concerning an arithmetic series and a geometric series: The second term of the arithmetic series is the same as the third term of the geometric series. Additionally, the fifth term of the geometric series is the same as the…
Eliza Q
  • 31
2
votes
1 answer

Modified NIM Game with more than one pile

The game is played at two tables; on the first table, there are N heaps containing A1,A2,…,AN stones and on the second table, there are M heaps containing B1,B2,…,BM stones respectively. Player1 must remove a positive number of stones from one of…
jolt
  • 21
2
votes
1 answer

Fibonnaci Sequence

Prove that $\forall n\epsilon N$ $$F(n+2) = 1 + \sum_{i=0}^n F(i) $$ I know this is strong induction. However I am new to it and not 100% familiar with how it works. The base case is $$ F(0+2) = F(2) = 1$$ and $$1 +\sum_{i=0}^0 F(i) = 1 $$ Then the…
Geralt
  • 313
2
votes
2 answers

What does this statement (and another) mean in discrete math? Let $P:\Bbb{Z}\times\Bbb{Z}\to\{T,F\}$, where $P(x,y)$ denotes "$x+y=5$"

What do these statements mean in discrete mathematics? Example 1: Let $P:\mathbb{Z}\times \mathbb{Z}\to \{T,F\}$, where $P(x,y)$ denotes "$x+y=5$". Example 2: Let $B=\{T,F\}$. Let $P(p,q,r,\ldots )$ be a proposition. Then, $$P:=(p\rightarrow…
VLD
  • 45
2
votes
3 answers

Is $\{\} ∉ A$ true or false, if $A = \{1, 2, 4, a, b, c\}$?

$A = \{1, 2, 4, a, b, c\}$. $\{\} ∉ A$ (true). My solution for this question is true. Since $\{\}$ is not an element of $A$. But at college I showed this question to my teacher and he said it is false because $\{\}$ is a subset of $A$ not an…
Mohamed Magdy
  • 673
2
votes
1 answer

$Y\subseteq X$ iff $X\cup Y^c=\Omega$, and $X\cap Y=\emptyset$ iff $X^c\cup Y^c=\Omega$

Let $X$ and $Y$ be subsets of the universe $\Omega$. Prove the following: 1) $Y\subseteq X$ iff $X\cup Y^c=\Omega$ 2) $X\cap Y=\emptyset$ iff $X^c\cup Y^c=\Omega$ Here $^c$ denotes the complement The statements do logically makes sense, however I'm…
Mictej
  • 95
2
votes
1 answer

Counting equivalence classe - proof theorem

THEOREM: (Counting equivalence classes) Let $R$ be an equivalence relation on a finite set $A$. If all the equivalence relation of a finite set $A$ have the same size, $m$, then the number of equivalence classes is $|A|/m$. First comment, I think…
Kapur
  • 489
2
votes
1 answer

Help understanding this definition please? Probabilistically checkable proofs

I'm having difficulty understanding the below. Does this mean that the language L is an element of PCP which is made from two functions f(n) and g(n) which if there exists the polynomial time randomized oracle machine it takes input x and a…
Lilz
  • 129
1 2 3
…
99 100