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

Show that ~ is an equivalence relation on the graph properties. (Discrete math)

We're learning about Isomorphism, relations on graphs and graphs in general. I read this question in the book and this was the proof: Clearly, a connected graph has a single component. On the other hand, any two vertices x, y in the same component…
user481197
1
vote
4 answers

Large Remainders with Mod

Determine the remainder of $5^{2017}$ when divided by 7. I know that we need to use mod 7 to find all of the different remainders but I am not sure what specific steps to take and how to finish it out. Please use Mod 7 as this question is very…
Bret Hisey
  • 223
1
vote
1 answer

prove or disprove that $(A - B) - C = A - (B \cup C)$

Prove or disprove the following: for any sets A, B, and C we have (A − B) − C = A − (B ∪ C). (If the statement is false, then construct an explicit counterexample.) Correct Answer (1 of many I suppose): Let A = B = C; then (A − B) − C = ∅ − C =…
I'm Hungry
  • 181
1
vote
2 answers

Prove that for every $n$ it is possible to find $n$ consecutive positive numbers that are not prime

My teacher only wrote this on the board. \begin{align*} k \mid (n + 1)! &\implies k \mid (n + 1)! + k \\ &\implies (n + 1)! + k\text{ is not prime} \end{align*} Not exactly sure what he means by this and how it relates to the problem.
Ashivs
  • 23
  • 2
1
vote
0 answers

Number of name combinations

I am working on the following problem... An early BASIC compiler recognized variable names according to the following rules: Numeric variable names had to begin with a letter and this letter could then be followed by another letter or a digit or by…
user510622
1
vote
1 answer

Countably Infinite Cross Product.

Let $A$ be countably infinite and $B = \{x,y\}$. How do I prove that $A×B=\{(a,b):a∈A,b∈B\}$ is countably infinite? I understand that we must show that there is a one to one correspondence from A x B to $Z^+$ So the question becomes, is there a…
Bret Hisey
  • 223
1
vote
1 answer

Countably Infinite Set Proof

Let A be a countably infinite set and B = {x,y}. Prove that A x B is countably infinite. I am not sure what I need to prove here. Is this a disjoint union, I could prove that a disjoint union of any finite set and any countably infinite set is…
Bret Hisey
  • 223
1
vote
1 answer

How do you know if a function only yields a certain kind of number?

Let's say that we have a function $3n^2-3n+13$. How do I know if the function only yields prime number without exhausting all the possibilities by trial and error?
PopularScience
  • 131
  • 1
  • 2
  • 5
1
vote
2 answers

Card Counting Problem

I tried these homework problems but think I ended up double counting on a few. I will post the question followed by my answer. I need help checking that they are correct or what the answer really is. Consider a game where 4 cards are dealt from a…
Joseph Schmidt
  • 25
  • 4
1
vote
1 answer

Optimal Coding Scheme for given Weights

I'm having trouble with this homework problem. Do I create the tree by beginning with each weight being a leaf? Then combining the lowest weighted leaves, and their parent becomes the sum of their weight? I got 85 as my answer for (b) but I'm not…
Joseph Schmidt
  • 25
  • 4
1
vote
2 answers

Algebra of Propositional Logic

How can I rewrite the following propositions in their simplest equivalent forms i.e. Least atomic propositions $(p \land \neg p) \Rightarrow \neg p$ $\neg ((p \land\neg p) \Rightarrow \neg q) $ $\neg ((p \land q) \Rightarrow r)$ Thanks
user450432
1
vote
2 answers

bijection between natural numbers and set of strictly growing finite rows

I have to construct a bijection between $\Bbb N$ and $\Bbb S_+$ ,where $\Bbb S_+$ is the set of strictly growing finite rows: $\Bbb S_+ = \{ (n_0,n_1...n_k) \;|\; k \in \Bbb N,n_i \in \Bbb N, n_0
yolo expectz
  • 363
  • 2
  • 13
1
vote
1 answer

Expected Area of Triangle from larger segment

Take a stick of length one and pick a point from it randomly. This will obviously divide the stick into two pieces. Pick another point from inside the larger interval and divide the larger interval into two pieces. If we assume this is a case where…
John Smith
  • 187
  • 2
  • 3
  • 13
1
vote
0 answers

Probability problem of flipping coin, roll dice and roulette wheel

An experiment consists of flipping a coin, rolling a 11 sided die, and spinning a roulette wheel. What is the probability that the coin comes up heads and the die comes up less than 4 and the roulette wheel comes up with a number greater than 14 ?…
jmike
  • 133
1
vote
1 answer

query on finding numeric function of a generating function

For the given generating function $A(z)=1/(1-x^3)$ what will be the numeric function.. I can find out for $A(z)=1/(1-x^2)$ but in the first case we get two factor in the denominator $(1-x)$ and $(x^2+x+1)$, now how do we find the numeric function…
shadow kh
  • 953
  • 5
  • 15
1 2 3
…
99 100