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

What are the steps to simplify the following modulus expression?

I have no clue how to do this exactly. Is there a systematic way of doing this or you just have to do it by trial and error? $n^2 \equiv 9 \pmod {72}$ to $n \equiv a \pmod b$?
Gladstone Asder
  • 1,051
1
vote
3 answers

Count how many number are there from $1$ to $N$ who have all $10$ digits in it at least once.

Count how many number are there from $1$ to $N$ who have all $10$ digits in it at least once. Can we have a generalized method to solve this problem?
0123456789101112
  • 113
  • 10
1
vote
1 answer

Find a closed sum: $\sum_{j=1}^{n}(j-1)\,2^{j-1}\,\left(\frac{k}{2}\right)^{\underline{j-1}}\,(k-j)^{\underline{n-j}}$

While analysing the run time of an algorithm, I used a counting argument to arrive at this expression: $$\sum_{j=1}^{n}(j-1)\,2^{j-1}\,\left(\frac{k}{2}\right)^{\underline{j-1}}\,(k-j)^{\underline{n-j}}=k^{\underline{n}} -…
Ricbit
  • 1,080
1
vote
2 answers

Recurrence Relations - discrete math

This is my work so far: $D(n)$ is the number of ways the set $\{1,2,3,\ldots,n\}$ can be partitioned into two sets. $D(n-1)$ is the number of ways the set $\{1,2,3,\ldots,n-1\}$ can be partitioned into two sets. $n-1$ can be divided into two…
Robert Miller
  • 317
1
vote
3 answers

Subtract 11011001 from (00100011 + 00001101) using 8-bit signed magnitude arithmetic

Subtract using 8-bit signed magnitude arithmetic 11011001 from (00100011 + 00001101 ) The result also should be signed magnitude format. I do it like this (+0 0001101 ) + (+0 0100011)=+0 0110000 then (+0 0110000)- (-1 1011001)= -1 0001010 is…
Flower Ahmed
  • 71
  • 4
1
vote
4 answers

How can I prove/disprove that if n is an integer which is not divisible by 3, then $n^3+n^2+2n+1 ≡ 2 \pmod 3$?

By doing a few examples, it seems as if the statement is true. However, I'm having trouble proving (or disproving) it. I know that the numerical value of some $N$ can be written as $n_{0}10^{0}+n_{1}10^{1}+n_{2}10^{2}+\dotsb$ and $10\equiv 1…
Payal Ahuja
  • 101
1
vote
4 answers

Prove that for $n\geq3$, $n^3\geq3n+5$

Prove that for $n\geq3$,$$n^3\geq3n+5$$ My try: Let $f(x)=x^3-3x-5$. Clearly $x=1$ and $x=-1$ are critical points where $x=1$ is the local minima so the function $f(x)$ is an increasing function for $x>1$ and the result follows. Please check and…
MatheMagic
  • 2,386
1
vote
1 answer

Foundation for Discrete Mathematics

I just went through a 4 week Discrete Mathematics course and I passed by the skin of my teeth. I was wondering how I can cover my foundations by learning what would normally come before such a course. If someone could point me in the right…
Above the first two
  • 11
1
vote
3 answers

Show $\pi: A \times B \to A$ defined by $ \pi (a,b)=a$ is a surjection, but not an injection.

Let $|A|>1$ and $|B|>1$. Show $\pi: A \times B \to A$ defined by $ \pi (a,b)=a$ is a surjection, but not an injection. My attempt: Surjection: For any $(a,b) \in A \times B, \exists a \in A$ such that $\pi (a,b)=a$. Thus, $\pi$ is surjective. …
Lily
  • 395
1
vote
2 answers

how to simplifying this euler expression?

given this equation: $(1-2e^{-jw} + e^{-2jw})$ how does that simplify to this? $(1-e^{-jw})^2$ I'm not sure what algebraic steps to take to get the 2nd equation.
a wee little worker
  • 187
1
vote
2 answers

solution to an equation involving natural numbers

Suppose $a,b$ are real numbers and we have $$ 1 = b + an \; \; \; \; \forall n \in \mathbb{N} $$ My book says that only solution is $b=0$, $a=1$. But, this does not make sense to me since if we put $n = 1$, we have $$ 1 = b + a $$ And $a=b=1/2$…
ILoveMath
  • 10,694
1
vote
4 answers

Show that if $f: X \rightarrow Y$ and $g: Y \rightarrow Z$ are injective, the $g \circ f$ is injective.

Show that if $f: X \rightarrow Y$ and $g: Y \rightarrow Z$ are injective, the $g \circ f$ is injective. Firstly, we have $g \circ f:X \rightarrow Z $. If $g \circ f$ is injective, suppose $(g \circ f)(x) = (g \circ f)(x')$ where $ x, x' \in…
Retty
  • 487
1
vote
3 answers

Prove $1/2^1 + 2/2^2 +....+ n/2^n < 2$ using induction

This is another problem with induction that I'm sure requires some "thinking outside the box" which is something I cannot apply with my way of solving these problems. I need to now how I can complete the induction step and I need a solution using…
Karma Cool
  • 43
1
vote
3 answers

Intersection Notation and its Function in Probability

Suppose event $A$ is flipping a coin, $A = \{H, T\}$ Suppose Event $B$ is rolling a die, $B = \{1, 2, 3, 4, 5, 6\}$. Next, suppose we flip the coin and roll the die. If we want to find the probability of getting, say, a head $H$ (denoted by…
Retty
  • 487
1
vote
1 answer

Island and Bridges proof using strong induction

There are n islands and initially all islands are separated and each form their own group. When a bridge is constructed between two arbitrarily chosen islands they become a connected group. As long as there are separated island groups, arbitrarily…
H. Davies
  • 41
  • 4
1 2 3
…
99 100