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

Show that the set $\mathbb{N}\times\mathbb{N}\times\mathbb{N}$ is countable infinite

I've proven that $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ given by $f(m,n)=2^{m-1}(2n-1)$ is a bijection. How do I show that the function $g:\mathbb{N}\times\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ given by $g(k,m,n)=f(k,f(m,n))$ is a bijection…
Ben French
  • 135
2
votes
2 answers

What is an example of function f:Z→N that is a bijection?

I tried to look at the cases and find a function, but I could not find a bijective function. I know that we should check the cases when x is a positive number and when x is negative. Can you help me to find one?
user502206
2
votes
3 answers

Can floor functions have inverses?

R to R $f(x) = \lfloor \frac{x-2}{2} \rfloor $ If $T = \{2\}$, find $f^{-1}(T)$ Is $f^{-1}(T)$ the inverse or the "image", and how do you know that we're talking about the image and not the inverse? There shouldn't be any inverse since the function…
PopularScience
  • 131
  • 1
  • 2
  • 5
2
votes
3 answers

Bijection between natural numbers and set of finite rows of natural numbers

I have to construct a bijection between $\Bbb N$ the natural numbers and $\Bbb S$, where $\Bbb S$ is the set of finite rows of natural numbers. S=$\{(n_0,n_1,...,n_k)|k\in \Bbb N,n_i\in \Bbb N\}$ I did a similar problem here:bijection between…
yolo expectz
  • 363
  • 2
  • 13
2
votes
4 answers

How come $2 \times 3^k + 3^k = 3 \times 3^k$

I get something else $$\begin{align*} &2 \times 3^k + 3^k=\\ &2 \times 3^k \times 2=\\ &4 \times 3^k \end{align*}$$ What does $3^k + 3^k$ give exactly?
question
  • 113
  • 1
  • 6
2
votes
2 answers

Finding number of distinct terms when collected in $(x+y+z)^{20}(x+y)^{15}$

Find the number of distinct terms when expanded and collected in $(x+y+z)^{20}(x+y)^{15}$ How would I do this nicely? I know that the first expansion has general algebraic term of $$\frac{20}{b_1!b_2!b_3!} x^{b_1}y^{b_2}z^{b_3} $$ where…
Natash1
  • 1,379
2
votes
2 answers

Proving a modulo statement

If the statement is true, then prove it, otherwise provide a counter example. If $x,y \in \mathbb{Z}$ such that $x = y^2$, then $x\equiv y \pmod 2$ Could someone just check to see if my proof is correct or that i made a mistake somewhere. Thank…
user3365751
  • 49
2
votes
0 answers

Why can I not do this substitution when counting integer solutions?

$$a_1 + \ldots + a_5 = 10$$ where $2\leq a_k \leq 6$ for all $k=1,2,\ldots,5$. Let $x_k := a_k - 2$, so $0 \leq x_k \leq 4$, and has the same number of solutions as $$ x_1 + \ldots + x_5 + 2\times 5 = 10$$ $$x_1 + \ldots + x_5 = 0.$$ However, this…
Natash1
  • 1,379
2
votes
2 answers

Counting number of filled squares

recently I came across the following problem: Consider a string of $n \geq 3$ blank squares. Start by colouring the leftmost square and rightmost square. Now, consider the following protocol to colour squares: at each iteration, you colour the…
Todd Chavez
  • 45
2
votes
1 answer

Is there a way to see if a function is invertible without proving it is onto and one-to-one?

For any function? Right now, I try to find the values of x and y for the function to see if it is one-to-one, but it doesn't work for some of the more complex and unusual functions.
mathnoob
  • 51
2
votes
3 answers

$2^{\{1,2,3\}}$ explained

Can someone explain me this: $2^{\{1,2\}}$ I know this equals to: $\{\varnothing, \{1\}, \{2\}, \{1, 2\}\}$ Right? So $\{1\}$ for example is an element of $2^{\{1,2\}}$, $\{1\} \in 2^{\{1,2\}}$ But can someone explain me to what this notation…
O'Niel
  • 239
2
votes
2 answers

Discrete Math (Proof Techniques)

I'd like to get a bit of an explanation with the correct answer, for the following questions that I missed on my hw. Consider the following proof that all squares are positive: Let $n$ be an integer; $n$ is either positive or negative. If $n$…
I'm Hungry
  • 181
2
votes
2 answers

Find the lowest $\mathbb{Z}$, $x \geqslant 100$ that when divided with 83 and 47 gives a rest of 3

I try to apply the chinese rest theorem. This is how I tried to do it. $$ \begin{cases} x \equiv 3(mod \quad 83)\\ x \equiv 3(mod \quad 47) \end{cases} $$ First I want to know if a solution exists, so I take $sgd(83,47)$. Applying Euklides…
Salviati
  • 357
2
votes
2 answers

How many relations are on the set (a,b)?

Is it 16 (2^4)? I completely forgot how to calculate the number of relations on a given set.
Jane
  • 105
2
votes
4 answers

Discrete math $A\,\triangle\, B = C$ implies that $A\,\triangle\, C = B$

$A\,\triangle\, B = C$ implies that $A\,\triangle\, C = B$ I understand that the delta is the symmetric difference and that the symmetric difference of $A$ and $B$ is the set of elements that belong to exactly one of $A$ and $B$. How do I prove the…
noslov
  • 31
1 2 3
…
99 100