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

Huffman Code Proof

Suppose we have an optimal prefix-free code on a set $C = \{0, 1, \dots , n − 1\}$ of characters and we wish to transmit this code using as few bits as possible. How to represent any optimal prefix-free code on $C$ using only $2n − 1 + n\lceil\log…
AccurateEstimate
  • 143
  • 1
  • 3
3
votes
4 answers

Prove that $1 + 4 + 9 ... + n^2 = (n/6)(n+1)(2n+1)$

I know that it is true but not sure how to write the proof for: $1 + 4 + 9 ... + n^2 = (n/6)(n+1)(2n+1)$. I need help to guide me in the right direction. Thanks in advance. edit: Okay at n=k I have $ 1+4+9 ... + k^2 = (k/6)(k+1)(2k+1)$ and at…
Slae
  • 277
3
votes
2 answers

Show that for any integer a, a^2 + 5 is not divisible by 4.

My solution is: Assume by contradiction that there is at least one number a such that $a^2$ + 5 is divisible by 4. Then a is either odd or even. Consider the case when a is odd. Then a= 2k+1 for some integer k. Then $a^2$ = $4k^2$ + 4k + 1 so $a^2$…
Joe
  • 143
3
votes
1 answer

A room and a spider

A room has the shape of a rectangular cuboid. The edges are 3, 4 and 5 metres. There is a spider in one of the corners. The spider now walks to the corner on the other end of the space diagonal using the shortest possible route. How much distance…
user176791
  • 335
3
votes
4 answers

Have I negated the statement "for every prime number $p$, $p+7$ is composite" correctly?

This is the original statement: For every prime number $p$, $p+7$ is composite. This is my negation: There exists a prime number $p$, where $p+7$ is prime. Have I negated this correctly?
user178415
  • 31
3
votes
2 answers

Finding the integers between {1, 2, ..., 100} that are divisible by 2 or 3 but not both.

I'm having trouble determining this problem. I need to find the integers in the set {1, ... , 100} that are divisible by 2 or 3 but not both. The way I tried to approach it was: If a number is divisible by both 2 and 3 then we can say it is…
Pandamonium
  • 975
3
votes
3 answers

Domain and Function Relationship

This is a very basic question I guess, if I have something like f:A->B, should all the elements in set A be used for f to be a function?
lueenavarro
  • 131
3
votes
5 answers

prove that any integer greater than or equal to 8 can be represented as the sum of nonnegative integer multiples of 3 and 5

This problem asks to use Well Ordering Principle to prove any integer greater than or equal to 8 can be represented as the sum of nonnegative integer multiples of 3 and 5. Here's where I'm at: For the sake of contradiction assume that there is a…
user3761743
  • 87
3
votes
3 answers

How should I continue on with this proof by contraposition?

I've been working on this question, but I am not sure if I am actually doing it right or wrong. So far, I have these steps down, about which I am not entirely sure. Show that if $n$ is an integer and $n^3 + 5$ is odd then $n$ is even using the…
Belphegor
  • 1,268
  • 6
  • 27
  • 51
3
votes
3 answers

Show that in a group of 10 people (where any 2 are either friends or enemies), there are either 3 mutual friends or 4 mutual enemies$\dots$

Question:Show that in a group of 10 people (where any 2 are either friends or enemies), there are either 3 mutual friends or 4 mutual enemies, and there are either 3 mutual enemies or 4 mutual friends. I'm really lost in this question. After hours…
JoeyAndres
  • 1,269
3
votes
3 answers

Celebrity problem, discrete math

so for my problem I have A guest at a party is a celebrity if this person is known by every other guest, but knows none of them. There is at most one celebrity at a party, for if there were two, they would know each other. A particular party…
Mike
  • 51
  • 2
  • 5
3
votes
1 answer

Problem involving recurrence equation

I have a problem involving two recurrence equations and I can't find an algebraic solution for it. I can however use Excel to determine its solution by generating their terms and check when their difference goes to zero. The problem The population…
Eugen Mihailescu
  • 175
  • 1
  • 2
  • 8
3
votes
3 answers

Proof by induction that $\sum_{i=1}^{n} \frac{2^i}{i} \leq n!+1$ for $n\ge 3$

Prove that $\forall n, n\geq 3$, $$ \sum_{i=1}^{n} \frac{2^i}{i} \leq n!+1 $$ By induction, I have that: For $n=3$: $\displaystyle\sum_{i=1}^{3} \frac{2^i}{i} = 20/3 \leq 3!+1=7$ Suppose that the proposition is true for $n=k$. Then, for…
Jeybe
  • 1,222
3
votes
1 answer

Number of ways to partition a set into three subsets with given sum.

Given a set S, with n elements out of which if any element is repeating then it is repeated at maximum 2 times. How to count the number of ways in which S can be partitioned into 3 subsets such that the sum of elements in each subset is required to…
user155768
  • 41
3
votes
1 answer

idempotent rule, distributive rule, and the absorption rule

Show that $p\vee(p\wedge q)=p$ follows from the idempotent rule, distributive rule, and the absorption rule $p\wedge(p\vee q)=p$. for this question i have spent 2 hours but still don't understand where to start. help here pleas!! can this also be an…
KRISSH
  • 139
1 2 3
…
99 100