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
2 answers

Binary numbers mod 3 without a calculator?

Binary number mod 3. Find: $1101101001010111010110111011111001_2 \bmod 3$ You may not use a calculator. I know how to convert a small binary number, but I do not know what approach to take with a larger one like this? Any thoughts on how you would…
Maxxie
  • 43
1
vote
1 answer

Cardinality of set well defined

Bit confused on this proof: I thought we needed to create a bijection from $\{{1,..,m-1}\}$ to $\{1,...,n\}$. So how does this proof work exactly?
helios321
  • 1,495
1
vote
2 answers

Prove by induction that for $n\geq 3$, $p_1 \to p_2, p_2 \to p_3, \dots p_{n-1} \to p_n \implies p_1 \to p_n$

I have proven the base case for $n=3$ by creating a truth table and verifying the implication. Now i need help with inducing a proof for every case. Please guide me on how i should approach this problem.
Zs11601
  • 43
1
vote
1 answer

Any relevance between the "amounts of denominators" which triangular numbers can't have

I will show triangular number with $k$. A triangular number is a number that applies to this formula :$$k=\frac{(n)(n+1)}{2}.$$ This $k$ can have different amount of denominators. But there are amounts of denominators which $k$ can never have. For…
Alireza Honarvar
  • 73
1
vote
2 answers

One to one correspondence between the set of even natural numbers ($2\mathbb{N}$) and the set of integers excluding 0 ($\mathbb{Z}\setminus \{0\}$)

Is there a way to make a one to one correspondence between the set of even natural numbers and the set of integers not including 0? What would that function be?
user717038
1
vote
0 answers

Need help with relatively abstract generating function problem

The task says: Find generating function for a series $a_n$ ($ n \geq 0$) where $a_n$ is subsets of some $n$-memeber set I tried to solve it but couldn't so I looked in solutions, this is a solution $$a_n=2^n \qquad f(x)=\sum_{n \geq 0}…
Petar 5
  • 111
1
vote
1 answer

How would I begin to check if the function is $O(x^4)$?

Use the definition $f(x) $ is in $O(g(n))$ if, for some constants $c$ and $n_0, f(n) ≤ g(x) $ for all $n > n_0$ To show that $ x^4 + 9x^3 + 4x + 7$ is $O(x^4)$ I know I need to find $c$ and $n_0$ and I thought $c$ needed to be $2$. The problem…
FredJacobs
  • 41
1
vote
1 answer

Discrete math chair problem

There are 9 distinct chairs. How many ways are there to group these chairs into 3 groups of 3?
YEET
  • 45
1
vote
1 answer

Having problems with big oh, Omega, theta

Show the following: $\ $ (a) $\, \sum_{i=1}^n(3i+2n)\text{ is }O(n^2)$ $\ $ (b) $\, \sum_{k=1}^n(k/3)\text{ is }\Omega(n^2)$ $\ $ (c) $\, \sum_{j=1}^n\sum_{k=1}^n 7n\text{ is }\Theta(n^3)$. Thank you.
Patamara
  • 35
1
vote
1 answer

Having an issue with this problem with an assignment

Suppose that an algorithm uses $2n^2+3^n$ bit operations to solve a problem of size $n$. Suppose that your machine can perform one bit operation in $10^{-9}$ seconds, how long does it take your algorithm to solve a problem of size given below. Note,…
Patamara
  • 35
1
vote
0 answers

Determining the truth value of a given statement

"There exist a,b ∈ ℝ such that {x ∈ ℝ | ax^2 = b} = ∅" I am not quite sure where to start. I do see many sets of a,b,x that satisfies ax^2 = b, but I am not sure what it means by it is equal to an empty set, ∅. Am I completely on the wrong track?…
Isaac Seo
  • 125
  • 3
1
vote
2 answers

Convert $31213111332_{4}$ to hexadecimal

I did $$31213111332_{4} = \\ 2*4^0+3*4^1+3*4^2+1*4^3+1*4^4+1*4^5+3*4^6+1*4^7+2*4^8+1*4^9+3*4^{10} = \\ 2*16^0+3*4^1+3*16^1+1*4*16^1+1*16^2+1*4*16^2+3*16^3+1*4*16^3+2*16^4+1*4*16^4+3*16^5 = \\ 2*16^0 + 3*4^1+7*16^1+5*16^2+7*16^3+6*16^4+3*16^5 =…
SilenceOnTheWire
  • 419
1
vote
3 answers

how to solve $\operatorname{rem}(6^{15},17)$ without using a calculator.

I am trying to solve $\operatorname{rem}(6^{15}, 17)$. I know that we have to use congruences but don't know how to go on. $6 ≅ 6 \mod 17$?? Can anyone please point me in the right direction? Do I have to use CRT in here?
sashank88
  • 13
1
vote
1 answer

Prove by induction on n the following statement $~∀~n ∈ Z \ge 0 ~~(~ ∃~x,~y ∈ Z~\ge 0~~ ( n = 0.5 ( x + y ) ( x + y + 1 ) + y ))~$

Prove by induction on n the following statement $$~∀~n ∈ Z \ge 0 ~~(~ ∃~x,~y ∈ Z~\ge 0~~ ( n = 0.5 ( x + y ) ( x + y + 1 ) + y ))~$$ I've managed to prove the base case of $~P(0)~$. However I'm stuck on the inductive cases. I've tried directly going…
CXY
  • 39
1
vote
1 answer

Determine a formula equal to the following summation

I have been trying to determine a general formula for the following summation for awhile now and cannot seem to make any progress: $$\sum_{k=1}^{n} 1/(n+k)$$ In a sense, what I am asking is similar to determining a summation for, say, the sum of all…
HtmlProg
  • 81
1 2 3
…
99 100