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
2
votes
1 answer

Derangments of N Elements Given That One Specific Element Remains In Its Original Position

Some context: Our teacher gave us a classroom exercise and it was returned to us this week. I am revisiting all the questions in the exercise, particularly the ones I got wrong. I am stuck at a particular problem whose answer involves the…
Mercado
  • 197
2
votes
1 answer

Does $\lfloor x\lceil y\rceil\rfloor = \lceil x\lfloor y\rfloor\rceil$ have non-integer solutions?

Does $\lfloor x\lceil y\rceil\rfloor = \lceil x\lfloor y\rfloor\rceil$ have any non-integer solutions? If so, how do you find them?
SalsaTaco1
  • 63
2
votes
4 answers

Which function is one to one

The question is as follows: Let $A = B = \{0, 1, 2, 3\}$. Which function $f: A \to B$ is one-to-one? There are three answers to choose from: (a) $\space f(x) = x + 1 $ (b) $\space f(x) = x \bmod 3 $ (c) $\space f(x) = 3 - x$ I know its not (b),…
Diehardwalnut
  • 427
2
votes
0 answers

List the elements in the sets

I'm getting caught up in the notation here. Not entirely sure what it is saying. My interpretation: (a,b) is an element of (the binary product) N x N then this "|" trips me up My guess: the "a" element in the set is less than the b, the b is less…
aero26
  • 599
2
votes
2 answers

How do I change ∃x, ∀y, P(x, y) into ∃y, ∃x, P(x, y)?

I'm very confused as to how to even begin, any explanation or help would be really appreciated. I understand Universal and Existential Quantifiers but the actual process of proving it is what confuses me.
John S.
  • 21
2
votes
1 answer

Count the number of strings of length 8 over A = {w, x, y, z} that begins with either w or y and have at least one x

Count the number of strings of length $8$ over $A = \{w, x, y, z\}$ that begins with either $w$ or $y$ and have at least one $x$ So here is what I came up with..Can someone check my work? $A = \{w,x,y,z\}$ $U = \{w,y\} * A^7$ $S = \{w,y\} *…
Yusha
  • 1,631
2
votes
1 answer

Finding the smallest number a such that $a! > 3^a$ for the naturnal number $n$ in statement $n! > 3^n$

I'm doing discrete maths as a subject at my uni and I've been asked to solve the following equation, yet I'm having trouble understanding both what it's asking me to do and how I need to go about getting the answer. I need to find the smallest…
SteppingHat
  • 123
2
votes
2 answers

mathematical induction proof of a square vs factorial

So lets say I have $$ n^{2} \le n! $$ For what positive integers is this not true? $n=2$ and $ 3$ Base case? $$n=4 \implies 16 \le 24 $$ What is the inductive hypothesis and how do I show the inductive proof? Thanks
Rickz0rz
  • 71
  • 6
2
votes
2 answers

Setting up a probability formula

I'm having a tough time understanding how combinations and permutations work in complex question. The question goes like this: If a board of 12 people is to be selected randomly from a pool of 15 people, and the pool consists of 2/3 men and 1/3…
Probably confused
  • 21
2
votes
4 answers

Prove by induction: for $n \ge 0$, $\frac{(2n)!}{n!2^n}$ is an integer

Another prove by induction question: for $n \ge 0$, $$\frac{(2n)!}{n!2^n}$$ is an integer Base step: $$n = 0$$ $$\frac{(2 \times 0)!}{0! \times 2^0} = \frac{0!}{1 \times 1} = 1$$ Induction step: please help
Mainuddin
  • 151
2
votes
5 answers

For all sets $A$, $B$, and $C$, if $A-B \subseteq A - C$ then $ A \cap C = \varnothing $

Prove the statement P: For all sets $A$, $B$, and $C$, if $A-B \subseteq A - C$ then $ A \cap C = \varnothing $ My attempt to answer: This statement is true, and here is a proof: Proof: Suppose A, B, and C are sets such that $A-B \subseteq A -…
2D3D4D
  • 147
2
votes
2 answers

Prove or disprove: If the positive integer m divides the positive integer n, then the Fibonacci number $f_{m}$ divides $f_{n}$

I have $f_{n}=f_{n-1}+f_{n-2}; f_{n}= [0,1,1,2,3,5,8,13,21,34,55,89,144,233,...]$ for which I note that indeed, 2 divides 4, and $f_{2}$ divides $f_{4}$. I am wondering if a proof by induction is sufficient, and exactly how would I go about doing…
Jabernet
  • 1,724
2
votes
3 answers

reflexive, symmetric, and transitive relations proof

Let $A = \{1, 2, 3, ... , n\}$ where $n$ is a positive integer. Let $F$ be the set of all functions from $A$ to $A$. Let $R$ be the relation on $F$ defined by: for all $g, f \in F, fRg$ if and only if $f(i) \lt= g(i)$ for some $i \in A.$ Let $I$A :…
2D3D4D
  • 147
2
votes
3 answers

Determine $A ∩ B ∩ D, (A \setminus D) ∩ B$

I am just starting a discrete math course at university and this is the first question on my first assignment. Sorry you will think it is extremely simple. Funny part is I can do most of the questions after this one. Let $A = \{n \in \mathbb{N} : n…
Greg
  • 23
2
votes
2 answers

Shortcut for composing cycles

Let $\pi = (15)(14)(13)(12).$ To compose the cycles of $\pi$, I rewrite $(15)(14)(13)(12)$ as $[(15)(2)(3)(4)][(14)(2)(3)(5)][(13)(2)(4)(5)][(12)(3)(4)(5)]$ which is tedious. Is there any way to shortcut the composition of $\pi? $
number
  • 35
  • 4
1 2 3
…
99 100