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

Prove that $\left\lfloor \frac {n+3}{2} \right\rfloor=\left\lceil \frac {n+2}{2}\right\rceil$

Prove that $$\left\lfloor \frac {n+3}{2} \right\rfloor=\left\lceil \frac {n+2}{2}\right\rceil$$ I have tried to solve this on my own, and I want to check my solution. My steps: Set $x=\left\lfloor \frac {n+3}{2}\right\rfloor $ then, for an integer…
Noussa
  • 135
1
vote
0 answers

Finding the possible numbers in sets

The set S contains some real numbers, according to the following three rules. (i) $\frac{1}{1}$ is in S (ii) If $\frac{a}{b}$ is in S, where $\frac{a}{b}$ is written in lowest terms (that is, a and b have highest common factor 1), then…
Aadhavan Srinivasan
  • 11
1
vote
1 answer

How can we construct an 8x8 grid with minimal squares

Links to similar questions: What is the minimum number of squares needed to produce an $ n \times n $ grid? How can we draw $14$ squares to obtain an $8 \times 8$ table divided into $64$ unit squares? The second link is a similar question, but at…
user437703
1
vote
0 answers

Hasse Diagram of Poset

The values I were given are {1,3,4,5,6},{1,2,4,5,6},{1,2,3,6},{1,2,3},{1,5,6},{1,3,6},{1,2},{1,6},{3,5},{1},{3},{4}. For the Hasse diagram, would {1,2,4,5,6} cover {1,5,6} even though there is a difference of two values, i.e. 4 and 2 are both…
Kevin
  • 11
  • 2
1
vote
3 answers

discrete maths graph, vertices edges

I have connected graph has 13 edges, 2 vertex of degree 2, 2 vertex of degree 3, 1 vertex of degree 6, and all others of degree 5. But with an unknown vertices. I read an online article and it says that for it to be a graph, the total number of…
whyme
  • 19
1
vote
1 answer

Distribute $27$ balls evenly among three boxes, transferring exactly $n$ balls in the $n$-th move

There are $3$ boxes, namely, $A$, $B$, and $C$. There are $27$ balls in box $C$. You have to make equal the number of balls in each box. At every $n$-th move, you must transfer exactly $n$ balls from one box to another. You cannot transfer balls…
Abhinav
  • 450
1
vote
0 answers

proving that affine cipher is injective

It is said that for the affine cipher to be injective the affine function $e(X)=ax+b(mod26)$ , just taking 26 for this case, the $GCD(a,26)=1$. Now, I understand why is this the case, but, what I don't understand is the way that it is proven in my…
mathmaniage
  • 596
1
vote
1 answer

Principle of I/E exercise

$10$ ladies drop off their red hats at the hat check of the museum. As they are leaving, the check hat attendant gave their hats back randomly. In how many ways exactly $6$ of the ladies receive their own hats (and the others not)? I guess applying…
Unknown X
  • 47
1
vote
2 answers

Prove whether the function $\left\lfloor\frac{\left\lceil x\right\rceil}{2}\right\rfloor: \mathbb{Z}→\mathbb{Z}$ is surjective, injective or bijective

So my logic to this up until now has been that for any $x$ the function $\left\lfloor\frac{\lceil x\rceil}{2}\right\rfloor$ will return an integer that is an element of $\mathbb Z$. Thus since you can map any $x$ in the domain to any y in the…
Brownie
  • 667
  • 1
  • 5
  • 17
1
vote
5 answers

Show that for all $n ∈ \mathbb Z$ , $n^2 ≥ n$.

Show that for all $n ∈ \mathbb Z$ , $n^2 ≥ n$. Hi, I'm trying to do this question. Does this mean I have to take any integers? Do I suppose its true and try to prove it. Is there a way to intuitively see if it's true or false even before beginning…
soso xoxo
  • 15
1
vote
1 answer

Prove or disprove: for any $n \in \mathbb{N}$, for any $r_1,r_2, \ldots, r_n \in R$ then there exists $a_j, 1 \leq j \leq n$ such that $r_j > 1$.

I have to prove or disprove: For any $n \in \mathbb{N}$, for any $r_1,r_2,\ldots, r_n \in R$ such that $\forall i, 1 \leq i \leq n, r_i > 0$ and such that $r_1 r_2 \cdots r_n = 1$, if there is an $i$, $1 \leq i \leq n$ such that $r_i < 1$, then…
NaiMomo
  • 13
1
vote
3 answers

How to prove these two functions are always equal?

If $a$ and $b$ are positive integers and $/$ stands for integer division, we have these two functions: $$f(a,b) = (a + b - 1) / b$$ and $$g(a,b) = \begin{cases} a/b, & \text{if $a \mod b = 0$} \\[2ex] a / b + 1, & \text{if $a \mod b \neq…
Joseph Tesfaye
  • 227
1
vote
1 answer

How to prove that there is at least one student at the round table whose two neighbours both cheated on the exam

A English exam was taken by $50$ students, the teacher found out that $25$ students had cheated on the exam, if the teacher was to place all of them in a round table show that there is at least one student two neighbours (at the table) of whom have…
Danny_007
  • 33
1
vote
1 answer

Minimum of a Venn diagram

A spot has three kinds of activities to choose, there are canoeing, fishing, and swimming. People who chose canoeing are 15, 22 chose swimming, and 12 chose fishing. If 9 didn't choose anything, what is the minimum number of visitors? I've tried to…
Godlixe
  • 333
1
vote
0 answers

Quotient Set of an Equivalence Relation

Let $A = \{1,2,3,4\}$ and $R = \{(1,1) , (1,2) , (2,1) , (2,2) , (3,3), (3,4) , (4,4)\}.$ Is $R$ an equivalence relation on $A$? If so, find its quotient set. I know that it is an equivalence relation. I found that it was Symmetric, Reflexive,…
Grover
  • 11
1 2 3
…
99 100