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

Discrete math assignment and pigeon-hole principle.

Assume that at the end of the semester there will be 30 students receiving grades for this class. Prove that some group of 3 students will get exactly the same letter grade (eg 3 students all earning an A-, or 3 students all earning an F). Prove…
xxx
  • 11
1
vote
3 answers

Let A and B be sets. Show that A is a subset of B if and only if for any set C, one has A union C is a subset of B union C.

Can you verify my proof if it is right? Let $A$ and $B$ be sets. (a) Show that $A$ is a subset of $B$ if and only if for any set $C$, one has $A$ union $C$ is a subset of $B$ union $C$. (b) Show that $A$ is a subset of $B$ if and only if for any…
Joe
  • 143
1
vote
1 answer

Show that the product of $n(n+1)\cdots(n+k-1)$ is a multiple of $k!$.

my solution is to re-write the statement into $n(n-1)\cdots(n-k+1)$. Therefore, $[n(n-1)\cdots(n-k+1)]/(k!) = {n \choose k}$ which yields an integer therefore it is a multiple of $k!$. Or should i do by mathematical induction? If MI , how so? For MI…
TBX
  • 51
1
vote
3 answers

Is an irrational to an irrational rational?

I am working on this logical proof for class and trying to either prove or disprove that an irrational to an irrational power is also irrational. Please don't answer the problem for me but I'm completely stuck on how to begin. Any hints would be…
Logical Failicy
  • 11
1
vote
2 answers

Proof by cases. Formulate a conjecture. I don't get it. Question inside.

I don't understand this math question for my discrete math 2 class. FOrmulate a conjecture about the decimal digits that appear as the final decimal digit of the fourth power of an integer. Prove your conjecture using a proof by cases. So that is…
Mandy Marie
  • 21
1
vote
1 answer

Diameter of a tree

$$T=(V,E) \text{ tree }$$ $$\text{diameter of a tree } = \max_{u,v \in V} \delta(u,v)$$ $$\delta(u,v)=\text{the length of the shortest path from the vertex u to the vertex v}$$ How can we calculate the diameter of a tree,when we are given the…
evinda
  • 7,823
1
vote
3 answers

Prove that $\forall k\in\mathbb{Z}$, $3|k-2$ implies $3|k^2-1$

I'm looking to answer this question Prove $\forall k\in\mathbb{Z}$, $3|k-2$ implies $3|k^2-1$. I'm not sure what to do. I'm trying to study but now I am getting stuck on these questions that don't give a lot of information. Thanks for the help!
John
  • 57
  • 2
1
vote
0 answers

Minimal vertex cover in bipartite graph question

How one can check for every vertex of bipartite graph whether it(vertex) belongs to every minimal vertex cover?
Evgeny Savinov
  • 586
1
vote
1 answer

Let $x_1, x_2, \dots, x_n$ be sequence of integers such that $\dots$

Question: Let $x_1, x_2, \dots, x_n$ be sequence of integers such that $-1 \leq x_i \leq 2$ for $i = 1, 2, \dots, n$. $x_1 + x_2 + \dots + x_n = 19$ ${x_1}^2 + {x_2}^2 + \dots + {x_n}^2 = 99$ Determine the minimum and maximum possible values…
Joey Andres
  • 143
1
vote
1 answer

Is $\{a,c,e,g\}$ an equivalence class?

If the set $\{a,b,c,d,e,f,g\}$ is is partitioned into these three partitions: $\{a, c, e, g\}$ $\{b, d\}$ $\{f\}$ and an equivalence relation is produced by these partitions, is $\{a,c,e,g\}$ an equivalence class?
Josh1billion
  • 127
1
vote
1 answer

Domination and Contraposition Laws - Discrete Math

Im having quite a bit of trouble understanding the Domination and Contraposition Laws in the instance below. I just do not see how the Domination Law, $\rho \wedge \mathrm{F} \leftrightarrow \mathrm{F}$ or $\rho \vee \mathrm{T} \leftrightarrow…
woody
  • 17
1
vote
1 answer

Why is this directed graph strongly connected?

From what I can see, there is no vertex path that goes to 1 so why is it strongly connected? Shouldnt every vertex be reachable from every other vertex? In this picture the 1 is not reachable.
Belphegor
  • 1,268
  • 6
  • 27
  • 51
1
vote
1 answer

GCD proof - one way solved

Let a,b be positive integers. Prove there exist positive integers $c$, $d$ such that $cd = a$ and $\gcd(c,d) = b$ if and only if $b^2\mid a$. Proof exists $cd=a$ and $\gcd(c,d) = b \Rightarrow b^2\mid a$: Let c = bm, d = bn. Then $cd = b^2mn = a$…
miniparser
  • 1,197
1
vote
2 answers

Permutations and Discrete Math

can someone explain to me this permutations problem from my desicrete math textbook? Q: The board of directors of a pharmaceutical corporation has 10 members. Three members of the board of directors are physicians. How many different slates…
Belphegor
  • 1,268
  • 6
  • 27
  • 51
1
vote
1 answer

The amount of closed binary operations on A under these conditions are what?

I have this problem and I would love some feedback on some of the answers that I have gave if they are incorrect. For some that I couldn't explain can someone explain to me how answers were achieved?. Let: $$A = \{a,b,c,d,x\}$$ Q: How many closed…
Jake
  • 13
1 2 3
…
99 100