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

Proving that all numbers between two numbers are composite

I am having trouble with this problem: Assume $p_1, p_2 \ldots p_{n+1}$ be the first $n+1$ primes in order. Prove that every number between $(p_1\cdot p_2 \cdot \ldots \cdot p_{n}) + 1$ (exclusive) and $(p_1 \cdot p_2 \cdot p_3 \cdot \ldots \cdot…
user186358
  • 11
1
vote
3 answers

Proof involving quantifiers

Prove or disprove: $(\forall x \in \mathbb Z) (\exists y \in \mathbb Z)(\forall z \in \mathbb N)(x + y \lt z)$ I am unsure on how to 'read' this statement. I would say take y = (z - x) - 1, then x + (z-x) - 1 < z, thus z < z + 1. But I don't feel…
Alexei
  • 27
1
vote
1 answer

Recursion and Counting

If $2$ numbers $n$ and $m$ are given, how can be found out the number of numbers with zero between and including $m$ and $n$ ($m \leq n$)?. For example, if $m=10$, $n=100$ the numbers with zeroes are $10,20,30,40,50,60,70,80,90,100$ .i.e 10…
Shahed Al Mamun
  • 71
1
vote
1 answer

Why is the number of anti-chains always equal to the number of up-sets

For my thesis I'm working on a program to count the number of upsets in a lattice. My professor gave me a tip via e-mail that the number of upsets in a lattice equals the number of antichains in a lattice. (Antichains are often shorter so when…
Roy T.
  • 437
1
vote
1 answer

License plate combination

California's license plate is made up for a number, followed by 3 letters, and 3 more numbers. If you cannot have the word BOB then how many license plate can be made in total? I'm guessing it's $10^4 * 26^3 - 10^4$ because the word BOB is…
bodygued
  • 297
1
vote
3 answers

Discrete mathematics proof that I have been stuck on

So I have been working on these proofs for a while and finished 13 of 14 of them but I was never able to figure this one out so I thought I would ask for help on how it would be done:S Here is the question: Let $n\ge$ be an integer. Consider $2n$…
user144808
  • 143
1
vote
4 answers

Prove that if both $ab$ and $a + b$ are even, then both $ a$ and $b$ are even.

Let $a$ and $b$ be integers. Prove that if both $ab$ and $a + b$ are even then both $a$ and $b$ are even. I've seen some solutions but they're not worded in a very simple way. Any help would be much appreciated!
hchenn
  • 105
1
vote
2 answers

How to prove the following $\Theta$notation

If the following function is given: $f(n)=n^2+ n \ln(n)+1$. How do you prove the $\Theta$ notation? I assume that is must be $\Theta$($n^2$). But I'm not sure how to solve it.
Jody
  • 39
  • 3
1
vote
3 answers

Number of edges in a graph

I was wondering, is it possible to find the number of edges in a graph when given the number of vertices and the degree of each vertex?
Johnny Andrea
  • 83
  • 6
1
vote
1 answer

Coconuts problem

I am trying to solve the following problem and I would appreciate any help on where I am wrong Problem Five men crash-land their airplane on a deserted island in the South Pacific. On their first day they gather as many coconuts as they can …
εν οίδα ότι ουδέν οίδα
  • 1,138
1
vote
1 answer

Need help proving a mathematical induction problem

I am having a bit of trouble proving assumption a & b, specifically b though. Could you guys walk me through the solutions for part a & b? Thanks.
user3367265
  • 71
1
vote
2 answers

Given that $p$ is prime, $\gcd(a, p^2) = p$ and $\gcd(b, p^3)=p^2$ find $\gcd(a+b, p^4)$

Given that p is prime, $\gcd(a, p^2)=p$ and $\gcd(b, p^3)=p^2$ find $\gcd(a+b, p^4)$. I'm really not sure how to approach the problem. My intuition from looking at it makes me think that the answer would simply be p. But I have no idea if that's…
user133707
  • 257
1
vote
0 answers

Are all of these proofs solved the same way?

$\forall x \in \Bbb R , \exists y \in \Bbb Z$ so that $\lfloor xy \rfloor = \lfloor x \rfloor \lfloor y \rfloor $. Assume that $x \in \Bbb R, y \in \Bbb Z.$ Let $\lfloor x \rfloor = n$ for some integer $n$ such that $n \le x \lt n+1,$ and let…
Travis
  • 13
1
vote
1 answer

Help coming up with a optimal function

I am working on solving this problem: https://open.kattis.com/problems/tractor Bessie the Cow has stolen Farmer John’s tractor and is running wild on the coordinate plane! She, however, is a terrible driver, and can only move according to the…
Jonny
  • 2,519
1
vote
2 answers

Determining whether or not a set contains an element, and proving set equalities.

I have two problems that are giving me a bit of a difficulty. I've already completed one of them, but I have a feeling I'm doing something wrong, and would greatly appreciate feedback. For the other one, I'm lost entirely. For each of the following…
Faraam
  • 13
1 2 3
…
99 100