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

what does this mean? ($ f : A \to B$)

I know that $f : A \to B$ means the function is mapping $A$ to $B$. My question is that when I say cardinality of $B$ is $x$, then does the x mean total numbers of elements present in $B$ or does it mean that total number of elements getting…
MacVimHelp
  • 21
  • 2
1
vote
1 answer

Prove that the intervals (0, ∞) and [0, 1] have the same cardinality

Help with this question would be greatly appreciated. At the moment, I cannot find an f(x) to map these sets. Also I'm just wondering to solve this problem, since '[]' brackets are used, do the numbers 0 and 1 have to be mapped to from the set (0,…
Jordan Solomons
  • 39
  • 1
  • 8
1
vote
3 answers

What does this math symbol mean $|$?

I came across this symbol in my discrete mathematics course. For example: $6 | n(n+1)(n+2)$
VLD
  • 45
1
vote
1 answer

Calculating factorials modulo a prime

I've been doing a programming (coding) exercise, where I'm implementing a method to calculate the remainder of $\frac{a!}{b!}$ divided by a prime number $p$. $a$ and $b$ are any integers between 1 and 1000 inclusive, while $p$ is the prime number…
leontp587
  • 149
1
vote
2 answers

Discrete Math - Recursive Relation problem

Passwords for a certain computer system are strings of uppercase letters. A valid password must contain an even number of X’s. Determine a recurrence relation for the number of valid passwords of length n. Note: 0 is an even number, so ABBC is a…
Botonox03
  • 11
1
vote
2 answers

Determing which sets are subsets of each other

I am in first year discrete math or key concepts is what it is called , i have a question about sets that states " suppose that $A=\{2,3,4,7\},B=\{3,7\},C=\{2,4,7\},D=\{3,5,7\}$. Determine which of these sets are subsets of which other of these…
Breanna
  • 21
1
vote
1 answer

Proof for any two numbers being manipulated with coefficients will equal the GCF? (Fundamental number theory)

Given any two values of $u$ and $v$, there exists values for $a$ and $b$ that would result in the greatest common factor between $u$ and $v$. $$\forall u,v \in \mathbb Z,\exists a,b \in \mathbb Z, au + vb = GCF(u, v)$$ This also effectively proves…
Celentia
  • 13
1
vote
1 answer

Discrete Math; BigO Notation: lease help me understand how this answer was arrived at.

Given f(n) = $(2^n+n^2)(n^3+3^n)$ the answer is O$|6^n|$ Can someone please explain to me how this happened? Thank you!
CodingMee
  • 187
1
vote
1 answer

confusion about recurrence relation

let us suppose that we have following recurrence relation $a_n-a_{n-1}=2*n$ where $a_0=0$ as i know solution is following $a_n=a_0+\sum\limits_{i=1}^n 2n $ which is the same as $a_n=2*\sum\limits_{i=1}^n n $ but this term $…
dato datuashvili
  • 9,194
1
vote
1 answer

Applied Combinatorics, Dominance Order

Suppose four teams, the Aces, the Birds, the Cats, and the Dogs, played each other once. The Aces beat all three opponents except the Birds. The Birds lost to all opponents except the Aces. The Dogs beat the Cats. Represent the results of these…
thebottle394
  • 129
1
vote
1 answer

How will you prove that there is only one unique way to expand any positive integer factorial in terms of prime factorial numbers?

Ex: Suppose that there exists two ways to write down $x!$, the two ways are $$(2!)^{a2}\times (3!)^{a3} \times (5!)^{a5} \times (7!)^{a7}$$ and $$(2!)^{b2} \times (3!)^{b3} \times (5!)^{b5} \times (7!)^{b7}.$$ How is there only one unique form of…
nishant_boro
  • 113
1
vote
2 answers

Bijection function from non-negative integers to integers

What is an example of a function from the set of non-negative integers (0, 1, 2, 3..) to the set of integers? The function has to be bijective.
Seung Pang
  • 19
1
vote
1 answer

Exact meaning of ∃x

I am a little bit confused about the meaning of quantifier ∃x Some definitions make it sound like There is exactly one x and some make it sound like There is at least one x I have this expression: ∃x (P(x)∧ Q(x)) Does it mean find exactly one x for…
Boris Grunwald
  • 431
1
vote
1 answer

8 ≡ 6 (mod 2)? Is the (mod 2) applied to both sides?

8 ≡ 6 (mod 2) Is this True or False? And why? Is the (mod 2) applied to both sides of the logical equivalence?
Hamish
  • 113
1
vote
2 answers

Using digits {1, 3, 4, 6, 7}, create the largest five-digit even number that is divisible by 3.

To clarify, no digits can repeat either. Can someone outline their thought process to solve? Here's mine: I used a process of elimination to determine what numbers I could use in the ten-thousands, thousands, and hundreds place. This gave me $7 6…
Ludwigthestud
  • 195
1 2 3
…
99 100