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

How many 4-permutations of the positive integers not exceeding 100 contain three consecutive integers in the correct order

Question:How many 4-permutations of the positive integers not exceeding $100$ contain three consecutive integers in the correct order a.) where consecutive means in the usual order of the integers and where these consecutive integers can perhaps be…
JoeyAndres
  • 1,269
4
votes
2 answers

Use a proof by cases to show that $\lfloor n/2 \rfloor$ * $\lceil n/2 \rceil$ = $\lfloor \frac{n^2}{4} \rfloor$ for all integers $n$.

Question Use a proof by cases to show that $\lfloor n/2 \rfloor$ * $\lceil n/2 \rceil$ = $\lfloor \frac{n^2}{4} \rfloor$ for all integers $n$. My Attempt: I can only think of two cases, $n/2 \in \mathbb{Z}$ $n/2 \notin \mathbb{Z}$ First case is…
JoeyAndres
  • 1,269
4
votes
1 answer

What is the difference between these two subsets in Discrete Math?

Let $U = \{1, 2, 3, 4, 5, 6, x, y, \{1, 2\}, \{1, 2, 3, 4\}, \{1, 2, 3\}\}$ $A = \{1, 2, 3, 4\}$ Can anyone explain to me the difference between these 2 pairs of things? $$A\subseteq U \text{ and } \{A\} \subseteq U $$ And how come $\{A\}$ is not an…
Belphegor
  • 1,268
  • 6
  • 27
  • 51
4
votes
2 answers

Adding combinations

Show non-numerically that: $${2\choose2} + {3\choose2} + {4\choose2} + {5\choose2} = {6\choose3}$$ The answer is as follows, but I have no idea how it was done: $$ \begin{eqnarray} &\phantom{=}& {2\choose2} + {3\choose2} + {4\choose2} + {5\choose2}…
user120920
  • 303
4
votes
2 answers

Finding a formula to sum natural numbers up to $n$

Possible Duplicate: What is the term for a factorial type operation, but with summation instead of products? I got this question in homework: Find an expression for the sum ‫‪ $\sum k = 1 +\cdots + n‬‬$. and prove it using an induction. I'm…
yotamoo
  • 2,753
4
votes
3 answers

Another proof by strong induction problem

I am trying to solve the following problem using proof by strong induction. the problem is: Assume that a chocolate bar consists of n squares arranged in a rectangular pattern. The entire bar, or any smaller rectangular piece of the bar, can be…
destroted
  • 41
  • 1
  • 1
  • 4
4
votes
3 answers

Solving Recurrences

My class and I were introduced to recurrences last week, and we took up this example (see link) in class. Unfortunately I find it really tricky still, and I apologize in advance if this question is...pathetic(?) From the steps shown class, solving…
user3428
  • 43
4
votes
1 answer

Counting Relation Functions

I have a set $S = \{ 1,2,3,4,5,6,7 \} $ I know that the number of bijective functions $S\rightarrow S$ without any restrictions is $7!$, but how can I count the number of bijective functions $ \phi : S \rightarrow S$ such that $\phi (x) \not= x$ for…
theta
  • 189
4
votes
1 answer

Why do we use another variable in the inductive step of mathematical induction?

I tried to find this answer on google and stackexchange but did not find any clue. Why is it that we use another variable like $k$ in $P(k)$ rather than the original $P(n)$ in the inductive step of mathematical induction? Why can't we just use $n$?…
user128344
  • 55
4
votes
2 answers

Discrete Mathematics - Understanding Proof by Contrapositive

I am just trying to understand proofs by the contrapositive method. I do know that the contrastive method is taking the negation of the second argument implies the negation of the first argument. For example: Show that the square of an even number…
Sentrl
  • 311
4
votes
2 answers

When does a dual of a compound proposition equal itself?

So I am studying computer science and right now I am stuck on a problem. When does s∗ = s, where s is a compound proposition? So far the only thing I can come up with is: s* = s when the compound proposition is composed only of the same …
Greg
  • 145
4
votes
1 answer

Book stacking problem with consecutively lighter books

I'm currently working on problem 6a of this problem set from MIT Open Course Ware. It's a spin on the book stacking problem. In this scenario, any additional books you stack beyond the first one has half of the weight of the previous book, and you…
user886596
  • 263
4
votes
1 answer

Need Help With Strong Induction

Let $(X_n)$ be a sequence given by the following recursion formula: $$X_1 = 3, X_2 = 7,\text{ and }X_{n+1} = 5X_n - 6X_{n-1}$$ Prove that for all $n\in\Bbb N$, $X_n = 2^n + 3^{n-1}$. Attempt: For $n = 1$, we have $2^1 + 3^0 = 3 = a_1$ TRUE For $n =…
user109886
  • 498
  • 1
  • 6
  • 12
4
votes
3 answers

How do you find the number of vertices on a graph?

A graph with 21 edges has seven vertices of degree 1, three of degree 2, seven of degree 3 and the rest of degree 4. How many vertices does it have?
user3003255
  • 107
  • 1
  • 1
  • 4
4
votes
2 answers

Prove $m=3k+1 \quad m,k \in \mathbb Z \implies m^2=3l+1 \quad m,l \in \mathbb Z$

Suppose we call an integer "throdd" $\iff$ $m=3k+1$ for some integer $k$. Prove that the square of any throdd integer is throdd. So here is what I have so far: $$(3k+1)^2 = 3k+1$$ $$(3k+1)(3k+1) = 3k+1$$ Am I going in the right direction? 2nd…
John
  • 61
1 2 3
…
99 100