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

Proving an inequality by induction and figuring out intermediate inductive steps?

I'm working on proving the following statement using induction: $$ \sum_{r=1}^n \frac{1}{r^2} \le \frac{2n}{n+1} $$ Fair enough. I'll start with the basis step: Basis Step: (n=1) $$ \sum_{r=1}^n \frac{1}{r^2} \le \frac{2n}{n+1} $$ $$ \frac{1}{1^2}…
Bob Shannon
  • 1,561
1
vote
1 answer

Show that the natural number $n$ with base ten representation ($r_{k}r_{k-1}$. . . $r_{1}r_{0}$)$_{10}$ is a multiple of $4$

Show that the natural number $a$ with base ten representation ($r_{k}$$r_{k-1}$. . . $r_{1}$$r_{0}$)$_{10}$ is a multiple of 4 if and only if the number ($r_{1}$$r_{0}$)$_{10}$, consisting of the rightmost 2 digits of $a$, is a multiple of 4,that…
Mark
  • 335
1
vote
3 answers

Proving an inequality by induction, how to figure out intermediate inductive steps?

I'm working on proving the following statement using induction: $$ \sum_{r=1}^n \frac{1}{r^2} \le \frac{2n}{n+1} $$ Fair enough. I'll start with the basis step: Basis Step: (n=1) $$ \sum_{r=1}^n \frac{1}{r^2} \le \frac{2n}{n+1} $$ $$ \frac{1}{1^2}…
Bob Shannon
  • 1,561
1
vote
1 answer

Determining whether function is a bijection onto its range and if it is finding $f^{-1}(5)$

Answer if each of the following functions is a bijection onto its range. For any function that is a bijection, identify $f^{-1}(5)$. Justify all of your answers. a) $f(n)$ = $2n$ mod 10. The domain is $\mathbb{Z}_{10} = \{0,1,2,3,4,5,6,7,8,9\}$ Ok…
Timonse
  • 139
1
vote
0 answers

How many permutations (bijections) are there on the set B = {0,1}^(8) of bytes?

How many permutations (bijections) are there on the set B = {0,1}^(8) of bytes? Prove that this set forms a group under the composition operation: g • f is defined by (g • f)(x) = g(f(x)).
user108441
  • 19
  • 1
  • 2
1
vote
1 answer

Question on properties of relations on sets of integers

I have a question that I've been struggling with: Define a relation $M(A,B)$: $A \cap B = \varnothing$. Domains for $A$ and $B$ are all subsets of $\Bbb Z$. What properties does the relation $M$ satisfy? I think I'm confused because I keep…
Misha
  • 21
1
vote
1 answer

Is a string with the null character the same as the same string without the null character?

Is this { Λ, 1 } the same as this { 1 }? For instance if you have the following grammar: S -> 0X|Y1 X -> 1|Λ Y -> 0|Λ Will every string created by it be ambiguous?
DumbQuestionAsker
  • 11
1
vote
1 answer

Show that inclusion-exclusion principle applies to finding max.

Show, that : $\text{max} \{x_1,x_2,...,x_n\} = x_1+x_2+...+x_n-\text{min}\{x_1,x_2\}-...-\text{min}\{x_{n-1},x_n\}+\text{min}\{x_1,x_2,x_3\}+...\pm \text{min}\{x_1,x_2,...,x_n\}$ In a way I'm supposed to prove, that the inclusion-exclusion principle…
Arek Krawczyk
  • 2,114
1
vote
2 answers

Proving that a function is 1-1 to show that it is invertible

I want to prove that $h(x)=x^3 +2x+1$ is a $1-1$ function to show that it is invertible on all of $\mathbb{R}$. This my attempt: Let $x_1,x_2\in \mathbb{R}$ where $x_1\neq x_2$. Suppose for contradiction $h(x_1)=h(x_2)$. Then $h(x_1)=x_1^3 +2x_1+1$…
user87274
1
vote
1 answer

Find all positive integers $n$ such that..

Find all positive integers $n$ such that $1!+\ldots+n!$ divides $(n + 1)!$ I think I know that the only two positive integers are $1$ and $2$. Proving it inductively has been a problem for me though. So far.. $$\frac{(n+1)!}{1!+\ldots+n!} <…
user105751
  • 11
1
vote
3 answers

Postage Stamp Problem with 3 stamp types

The Baker does not sell individual bear claws, but sells them in boxes of 6, 9, and 20. Assuming an unlimited supply, what is the largest number of bear claws that I cannot buy from the baker. I'm not sure how to attack one of these problems…
Jerrod
  • 155
1
vote
3 answers

Discrete Mathematics Notation

I am having difficulty understanding the notation of discrete math. Here (x | y) means “x evenly divides y” i.e. divides without a remainder. ∃S ⊆ Nat: (∀y ∈ S : (∀x ∈ Nat : (x | y ) ⇒ (x = y) ∨ (x = 1)))) Can someone explain this equation to me…
ztoolson
  • 33
1
vote
4 answers

True or False problem on sum principle

If A $\cap$ B $\cap$ C = $\emptyset$, then the sum principle applies so |A $\cup$ B $\cup$ C| = |A|+|B|+|C|. I think it would be true since there is nothing in common among A,B and C, but just wondering if there is any exceptions to this problem…
SSS
  • 397
1
vote
1 answer

How many telephone numbers have no $0$ in the prefix (first three numbers)

I got that the total number of telephone numbers: $10^{10}$, but should I do the number of one $0$ in prefix, number of two $0$ in prefix and number of three $0$ in prefix, and subtract them. But I don't know how to count the number of $0$ in the…
SSS
  • 397
1
vote
1 answer

Need a little help

I have a question, suppose that $S_{n+2}=13S_{n+1}+48S_n$. How do I find a general solution for this recurrence equation and how do I find the particular solution where $S_0=1$ and $S_1=5$. Here is what I've got so far, I brought everything to the…
Rich Sanchez
  • 69
1 2 3
…
99 100