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

Donald Knuth Concrete Mathematics 2nd Edition page 75. I don't understand one of the step of SUM-manipulations

SUM-manipulations and author's clarifications I understand all this SUM-manipulations excluding one moment. Knuth wrote: The only 'difficult' maneuver is the decision made between lines 3 and 4 to treat n = 1000 as a special case. (The…
Vasilii K
  • 43
4
votes
3 answers

Prove a mod b = b mod a iff a=b

I'm just starting to learn the three types of proofs and I came across this question. a mod b = b mod a iff a=b I tried looking for solution to prove this but couldn't find it. Most examples I have are of the same divisor like: a…
RJ563
  • 43
4
votes
2 answers

Trying to understand a proof of Cantor's theorem: why was $B$ defined this way?

This comes from the textbook: Edward A. Scheinerman - Mathematics: A Discrete Introduction-Cengage Learning (2012) I understand everything in the proof except for why Dr. Scheinerman defined the set $B$ as he did. Informally, he says that B is a…
James Ronald
  • 2,331
4
votes
2 answers

Number of possible chess pairs where order and position matter

Given 11 chess players and 5 distinct tables, in how many ways can we pair them to play (color does matter)? My problem is that I have found two approaches, both of which give different numbers, and I am not sure what is missing in one or…
Nescio
  • 2,426
4
votes
2 answers

Find all finite sets $A$ so that $A\times\mathcal P(A) =\mathcal P(A)\times A$, where $\mathcal P(A)$ is the power set of $A$.

Find all finite sets $A$ so that $A\times\mathcal P(A) =\mathcal P(A)\times A$, where $\mathcal P(A)$ is the power set of $A$. Now I'm a beginner at Discrete Math so I'm not sure how to tackle this problem. I was expecting that a set with elements…
Brownie
  • 667
  • 1
  • 5
  • 17
4
votes
2 answers

Showing there are no integer solution to equation $\;2^x = 4y+3$

I am stuck on this problem and I'm not sure how to approach it. Can anyone help me out with figuring how to approach the proof? My task is to: Prove that it is impossible to find integers $\,x,\, y\,$ such that $\;2^x = 4y + 3$. I assumed a proof…
choloboy
  • 359
4
votes
4 answers

Homomorphic image of modular lattice is modular?

Let $L$ be modular lattice, $M$ be lattice and $f:L\to M$ be a homomorphism. I want to show $f(L)$ is a modular lattice.. We already know that homomorphic image of a lattice is a lattice. So we only want to show that if $f(a)\leq f(b)$ then $f(a)…
So Lo
  • 1,567
4
votes
2 answers

Recurrence exercise

Been stuck on this question for days... Would appreciate any help :) Devise a function $p(n)$ such that $p(n)$ is the number of different ways to create postage of $n$ cents using 3-, 4-, and 5-cent stamps. Prove that $p(n)$ is monotonic…
mzab123
  • 43
4
votes
2 answers

how to write boolean function in conjunctive form for f=1 only one of variables is 1

Given $n$ Boolean variables $x_1, x_2, \ldots , x_n$, write a function $f(x_1, x_2, \ldots , x_n$) in conjunctive normal form such that “$f = 1$ if and only if exactly one of the $n$ variables is $1$”. is some one know this question?
tywtyw2002
  • 89
4
votes
4 answers

Proving that $\lfloor a^2/2 \rfloor$ is even for all $a\in\mathbb{Z}$.

$\forall a \in \mathbb Z, \lfloor a^2/2 \rfloor$ is even. I am pretty sure this statement is true. The only suspicious cases to me are 0/2 and 1/2, but they also have even floors. How do I prove it though?
user60334
  • 717
4
votes
2 answers

As a high school student, what resources are there to learn discrete mathematics?

I am currently taking AP Calculus AB in high school, but I am very interested in computer science and mathematics as a whole. I understand that discrete math and computer science are very closely related. Although I am in high school and there is…
Lincoln Fuller
  • 55
4
votes
1 answer

If $a_i\geq 1\ \forall i\in\{1,...,120\}$ and $\sum_{i=1}^{120}a_i\leq 180$, there exist indices $i,j$ such that $\sum_{k=i}^ja_k=59$

Let's consider 120 numbers $a_1,a_2,...,a_{120}\in \mathbb{N}$ such that $a_i\geq 1\ \forall i\in\{1,...,120\}$ and $\sum_{i=1}^{120}a_i\leq 180$. Prove that there exist indices $i, j$ such that $\sum_{k=i}^j a_k = 59$. I think that I might…
user171110
4
votes
1 answer

A magic rectangle with the greatest size - original question

I filled in a $3\times k$ rectangle with non negativ integers, such that the sum of the three numbers in each column is the same number $n$, and in each row all the numbers are different. Find the maximum value of $k$. If you try for…
user173628192
  • 1,506
4
votes
1 answer

Number of polynomfunctions $\mathbb{Z}_3 \rightarrow \mathbb{Z}_3$

I need to determine the number of polynomfunctions over $\mathbb{Z}_3 \rightarrow \mathbb{Z}_3$. I have no clue how to attempt this problem. I know that $\mathbb{Z}_3 =$ {0, 1, 2}. The polynomfunction is defined as: $f(x) = a_kX^k + ... a_1X^1 +…
Just a Student
  • 157
  • 2
  • 8
4
votes
1 answer

Understanding a recurrence relation problem from Concrete Mathematics

I'm working through the Concrete Mathematics textbook (by Ronald Graham, Donald Knuth, and Oren Patashnik), and am confused about problem 1.7, which is below: Let $H(n) = J(n + 1) - J(n)$. Equation (1.8) tells us that $H(2n) = 2$, and $H(2n+1) =…
dylam
  • 145
  • 5
1 2 3
…
99 100