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
4
votes
3 answers

Did I answer these counting method questions correctly?

A six person committee composed of Alice, Be, Connie, Dolph, Egbert, and Francisco is to select a chairperson, secretary, and treasurer. a) How many selections exclude Connie? b) How many selections are there in which neither Ben nor Francisco is…
J. Doe
  • 421
4
votes
1 answer

How do we prove or disprove 3 statements together in discrete math?

From my understanding what the question asks for is for us to prove them by $$p_1 \to p_2,\quad p_2 \to p_3,\quad p_3 \to p_1$$ But how do we actually do this? The question is as follows: The following statements are equivalent for all non-negative…
user315656
  • 53
4
votes
2 answers

Why is {1, 2, 3} an equivalence relation?

"The equality relation (=) on a set of numbers such as {1, 2, 3} is an equivalence relation." I know the equality relation = is an equivalence relation in the set of real numbers. Because it can satisfy all three conditions of equivalence relation.…
buzzee
  • 1,530
4
votes
2 answers

Pigeonhole Principle - Floor versus Ceiling

I realize this question will not have an "answer," but I would really like to hear what anyone might know about this topic. In class today my professor stated that if there are $m$ pigeons and $n$ holes, then there are at least $\left…
fullyhip
  • 436
4
votes
1 answer

Find integer a,b > 1 such that $2^a + 3^b = 2^{a+b} +1$

I would like to know if it is possible to find an integer solution to $2^a + 3^b = 2^{a+b} +1$ with $a,b > 1$
gw653
  • 41
4
votes
3 answers

Prove by contradiction $a,b,c>0$?

Suppose $a,b,c$ are real numbers such that $a+b+c>0$, $ab+bc+ca>0$, and $abc>0$. Prove by contradiction that $a,b,c>0$. I have tried to solving it case by case like: case $1$: $a,b,c<0$; case $2$: exactly $1$ or $3$ variable(s) from $a,b,c$ is $<0$,…
rrozamelo
  • 41
4
votes
2 answers

How to find the amount of binary digits in a decimal number?

This seems like such a simple question but I can't seem to come up with an answer. I know the formula for the number of digits of $2^n$ is $1+[nlog(2)]$. So the amount of decimal digits of $2^{100}$ would be $1+[100log(2)] \approx 70$. How would I…
Jaken
  • 546
4
votes
1 answer

How many bitstrings of length 8 contain 5 consecutive 0's?

I worked this problem using a recursive sequence, i.e. it can end in $1$, leaving $a_{n-1}$, or $10$, leaving $a_{n-2}$, $100$ leaving $a_{n-3}$, $1000$ leaving $a_{n-4}$, $10000$ leaving $a_{n-5}$, and finally $00000$ leaving $2^{n-5}$…
Jabernet
  • 1,724
4
votes
3 answers

How many permutations of cycle-shape $(3,2^2,1)$ are there in $S_8$?

I am not familiar with this kind of counting problem, so I googled the key words. From what I found it looks like Stirling Numbers of First Kind do the job(?). These numbers are denoted [$\frac nk$ ] where $n$ is the length of permutations and $k$…
Kyle
  • 95
4
votes
1 answer

question about solving recurrences

I am self-studying Discrete Mathematics. Here is one question I am suppose to solve. a) $x_{n+1}=2x_{n}+1,x_{1}=2$ When I tried to find the homogeneous solution to $x_{n+1}=2x_{n}$ I found $a_{n}=2^{n}$, but it shoud be $a_{n}=2^{n-1}.$ I don't know…
user23505
4
votes
3 answers

Associative, but non-commutative binary operation with a identity and inverse

Can there really be an associative, but non-commutative binary operation with a identity and inverse?
Ishan Madhusanka
  • 143
4
votes
2 answers

State if it is a function or relation .

Let $A=\{1,2,3,4\}, B=\{1,5,9,11,15,16\} $ and $f=\{(1,5),(2,9),(3,1),(4,5),(2,11)\}$ Are the following statements true ? $1.)$ $f$ is a function from $A$ to $B.$ $2.)$ $f$ is a relation from $A$ to $B$ For the first part as $(2,9)\…
R K
  • 2,635
4
votes
4 answers

Bound on size of subset of $\{1,2,\ldots,2n\}$ where no member is a multiple of another

Use mathematical induction given a set of n+1 positive integers, none exceeding 2n,there is at least one integer in this set that divides another integer in the set. I can't understand why when n= 1 that this equation is correct .I think I can put…
Luke Tsai
  • 41
4
votes
3 answers

Prove that $14322\mid n^{31} - n$

Im trying to prove that $ 14322 \mid n^{31} - n $, $ \forall n \in \mathbb{Z}$ My thought was to rewrite $n^{31} - n$ which a got to $$ 2(n-1)\sum_{i=0}^{n} i \sum_{k=0}^{14} n^k \sum_{j=0}^{14} (-1)^kn^k $$ but this didnt (in my opinion) contribute…
Olba12
  • 2,579
4
votes
4 answers

Strong induction with Fibonacci numbers

I have two equations that I have been trying to prove. The first of which is:F(n + 3) = 2F(n + 1) + F(n) for n ≥ 1.For this equation the answer is in the back of my book and the proof is as follows:1) n = 1: F(4) = 2F(2) + F(1) or 3 = 2(1) + 1,…
Lucas Jablonski
  • 43
1 2 3
…
99 100