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

Relations of functions

I am doing an assignment and I want to make sure I understood my definitions can someone check my table and if I went wrong please tell me where and why. Original question Determine whether the relation R on the set of all real numbers is reflexive,…
wolfcall
  • 401
1
vote
3 answers

the binomial theorem

the Question: Prove the critical Lemma we need to complete the proof of the Binomial Theorem: i.e. prove $(^{n}_{k})=(^{n-1}_{k-1})+(^{n-1}_{k})$ for $0\lt k\lt n$ (this formula is known as Pascal’s Identity) you can do this by a direct proof…
Mikky Davey
  • 225
1
vote
2 answers

Is $\frac{O(f(x))}{O(g(x))}=O\left(\frac{f(x)}{g(x)}\right)$?

Is the following true. $$\frac{O(f(x))}{O(g(x))}=O\left(\frac{f(x)}{g(x)}\right)$$ If not under what conditions is it? For example, the function, $$h(x)=\frac{x^3+2x}{2x+1}$$ has $O(x^3)/O(x)$. And the total function has $O(x^2)$. My concern is…
John
  • 1,149
1
vote
1 answer

Writting a proof for $\lfloor 4x \rfloor = \lfloor x+1/4 \rfloor + \lfloor x+1/2 \rfloor + \lfloor x+3/4 \rfloor + \lfloor x \rfloor$

I am working on an assignment and have to write a proof for the following: $$\lfloor 4x \rfloor = \lfloor x \rfloor + \lfloor x+\frac{1}4 \rfloor + \lfloor x+\frac{1}2 \rfloor + \lfloor x+\frac{3}4 \rfloor$$ I have to do by proof by case I know the…
wolfcall
  • 401
1
vote
2 answers

Finite sum of the fractional type

Some special manipulations involving finite sums. How to solve this sum? $\displaystyle{\sum_{k=1}^{n}}\frac{1}{4k^2 - 1}$
Paulo Sérgio
  • 1,151
1
vote
0 answers

Finding composition of relations

I've provided an example and my answer, however I am worried I have done $R\circ S$, or $S\circ R$, as I still mix them up at times. ex: Suppose $R$ and $S$ are relations on $\{a, b, c, d\}$ where $R = \{(a, b), (a, d), (b, c), (c, c), (d, a)\}$ and…
user138497
  • 11
1
vote
2 answers

Sets and inverse functions

I am working on an assignment and I want to know if my thinking is right for my answer. i have been giving the following functions and sets: $$f(x)=x^2$$ I found the inverse to be. $$f^{-1}(x)=\sqrt{x}$$ All $x\in…
wolfcall
  • 401
1
vote
2 answers

get gcd as a linear combination.

Suppose A has two unmarked containers, one holds 19 liters and the other holds 51 liters. Explain how A can use his two containers to measure exactly one liter? This is the problem. I use gcd(19,51)=1 to back trace it. Then I get 3 * 51 - 8 *19 = 1.…
SonicFancy
  • 541
1
vote
1 answer

Probability - discrete math

In a particular group of people, 10 people are right handed and 4 are left handed. If 5 of these people are chosen at random, What is the probability that exactly 1 left handed person is selected? I got 240,240 for all the possible outcomes. Can…
user124557
  • 159
1
vote
3 answers

What is the smallest positive integer n such that $2^5 · 3 · 5^2 · 7^3 ·$ $n$ is a perfect square

Is there some kind of rule that I need to solve this? Can someone give me some clue how to solve this? Thanks My teacher gave the solution as $42$. Can someone explain why?
hello
  • 79
1
vote
3 answers

How to identify an inverse of 101 modulo 4620

I use Euclidean Algorithm: 4620 = 101 * 45 + 75. long story short. I get 3 = 2 * 1 + 1. After that 2 = 1 * 2 + 0. gcd(101,4620) = 1. So I use back substitution. 1 = 3 - 1 * 2. Long story short, I work my way up to express the remainders as the…
Nicholas
  • 559
1
vote
3 answers

Proof by induction: $n! > n^2$ for $n\ge 4$

Proof by induction: $n! > n^2$ for $n\ge 4$ Basis step: if $n=4$ $4\cdot3\cdot2\cdot1 > 4^2$ $24 > 16$ I don't know how to do the inductive step.
user136245
  • 19
  • 2
1
vote
2 answers

mean for the amount of money won for flipping a coin n times and winning m dollars on the m-th flip if it is tails

I am flipping a coin n times. if it lands on heads, i win nothing but if it lands on tails on the m-th flip, i get m dollars. how much money can i expect to you at the end of the game. I looked at each coin flip on the m-th try. For example, using…
user3239138
  • 121
1
vote
3 answers

Discrete Math Testing Cardinality

$S$ denotes the set of real numbers strictly between $0$ and $1$. That is, $S = \{x \in R\mid 0 < x < 1\}$. Let $U = \{x \in R\mid 0 < x < 2\}$. Prove that $S$ and $U$ have the same cardinality. I am completely lost. How do I approach this problem?
Snowyace
  • 37
1
vote
0 answers

Discrete Math, Negation and Proposition

I hope we are all well. I'm having a little hard time understand what negation means in Discrete maths. Say I have "$2+5=19$" this would be a "Proposition" as its false. So how would I write the "negation". Would I say something like "$2$ plus $5$…
user133149
  • 95
1 2 3
…
99 100