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

9 year old's Venn diagram homework

So, my daughter has been given this Venn diagram problem... buuut it's not solvable riiiiight?
Neilos
  • 111
1
vote
1 answer

Partition of odd $n$ into summands

For odd $n$, explain why there can be no partition of $n$ into summands such that each part appears an even number of times. Please help me, I don't have any idea
Eliz
  • 11
1
vote
1 answer

Super simple question I'm not understanding when I just started learning discrete maths (something with strings)

Let n be a positive integer. Given a finite set A, a string of length n over A is an ordered n-tuple of elements of A written without parentheses or commas. The elements of A are called the characters of the string. The null string over A is…
tommyd
  • 11
1
vote
0 answers

Show that cardinality of whole number is equal to cardinality of Natural numbers

Proof for cardinality of natural numbers is equal to the cardinality of whole numbers
Hashmi Sahib
  • 11
1
vote
1 answer

Does a property of Xor like this exist?

Is there a property on Xor that says basically $a = b \oplus (a \oplus b)$? I was thinking associative but I don't think that's correct.
Jose
  • 253
1
vote
2 answers

What do the symbols mean in this statement?

I am having problems breaking this down in order for it to make sense in my head. How would you read this? $f(S)=\{f(x)\,|\,x \text{ exists in }S\}$
user84833
  • 21
1
vote
1 answer

N invitations in Rashida's Birthdays

Rashida wanted to invite her friends to her birthday and she was born in April. In a leap year, she started sending invitations from February 16 and completed them by March 15. At least one invitation was sent each day but no more than 50…
Christopher Marlowe
  • 511
1
vote
1 answer

Suppose $P(n)$ is a predicate. Find the integers $n$ such that $P(n)$ is true.

$P(0)$ is true; for all positive integers $n$, if $P(n)$ is true, then $P(n+2)$ is true. So my understanding is that $n$ can be $0, 2, 4, 6, 8,...$ (all positive even integers bigger or equal to zero). Since $P(0)\implies P(2)$ $P(2)\implies…
FarmerZee
  • 417
1
vote
0 answers

Newton Interpolation formula- 3rd Degree with 5 points given- Intuition

I am trying to intuitively grasp the geometric meaning of introducing the third order term delta (Yo^3) to the graph of finite difference initially set only to second order. Till second order, I can imagine that Newton formula has given addition of…
Abbas
  • 11
  • 4
1
vote
1 answer

Use strong induction to prove piecewise function

$H_0 = 0, H_1 = 1, H_2 = 1$, for all $n \in \mathbb{N}$ where $n \geq 3$: Prove for all $n \in \mathbb{N}$, $$ H_n = H_{n−1} + H_{n−2} − H_{n−3}. $$ $$ H_n = \begin{cases} \dfrac{n}{2}, & \text{if $n$ is even} \\[2ex] \dfrac{n+1}{2}, & \text{if $n$…
bloomsdayforever
  • 485
1
vote
0 answers

Pigeonhole Principle: Suppose five cities on Earth are chosen. Show that there is a hemisphere contains at least four of the cities

Assume the Earth is a perfect sphere. There are infinitely many ways to divide the Earth into hemispheres, besides North and South. Any great circle will play the role of an “equator” between them. Suppose five cities on Earth are chosen. Show…
bloomsdayforever
  • 485
1
vote
1 answer

Find smallest positive $a\in\mathbb Z$ such $10a\equiv 7\mod 17$.

I found that the answer was $a=16$, I believe. Note that $10a \equiv 7 \mod 17 \iff 17 \mid 10a - 7 \iff 10a -7 = 17x, x\in\mathbb Z$. The way I went about it was running EEA for $$10a + 17(-x) = 7,\quad x\in\mathbb Z.$$ I found it to be $1 =…
user10101
  • 473
1
vote
0 answers

How would I go about proving that if any sets S, T⊆X have f(S∩T)=f(S)∩f(T) if function f: X -> Y is 1-1? Does my prove sound correct?

Does this sound kind of correct or at least am I on the right track here? Lets say: some x = f(x) for some a for which a ∈ S ∩ T, so x ∈ f(S∩T). And for some y = f(y) for some b for which b ∈ S and b ∈ T, so y ∈ f(S) ∩ f(T). And because f is 1-1…
Amber
  • 21
1
vote
2 answers

Prove a function is onto

Prove that the function $f(x)=x^5+2x^2+x$ is onto. My teacher did an example in class were he said $f(x)=y$ and then found the inverse of the function. He then plugged the inverse back into the function and found that it equaled y. And that was the…
user83906
  • 11
1
vote
0 answers

Property of Distance to Nearest Integer

I am trying to prove if $x,y,z \in \mathbb{R}/\mathbb{Z}$ with $x+y+z=0$ in $\mathbb{R}/\mathbb{Z}$, then \begin{align*} \|x\|+\|y\|+\|z\|=2\max(\|x\|,\|y\|,\|z\|) \end{align*} or \begin{align*} \|x\|+\|y\|+\|z\|=1 \end{align*} with $\|x\|$ is the…
Laurence PW
  • 839
1 2 3
…
99 100