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
3
votes
1 answer

Real number comparisons: must a number be less than or equal to or greater than another number?

I've been reading Knuth's Surreal Numbers recently and came up with this question about real numbers. Is is true that among all three relationships (=, >, <), a real number must be of one, and only one relationship with another real number. If this…
wlnirvana
  • 133
3
votes
4 answers

Generating Functions in Discrete Math

a)Find the coefficient of $x^3y^4$ in $(2x + 5y)^7$. b) Find the coefficient of $x^5$ in $(3x -1)(2x +1)^8$. I know this has to do with generating functions , but i'm not sure how to start with this problem in order to find the coefficient of part…
user142743
  • 127
3
votes
2 answers

Learning Mathematics through Programming.

I am about to embark on a 'comprehensive' and thorough study of undergraduate mathematics. In the interests of efficiency and a desire to improve my programming skills, I ask: In oppose to the pen and paper approach, would it be advisable to…
user123082
  • 31
3
votes
2 answers

Prove that G is abelian if and only if the function $f:G\to G $defined by $f(a)=a^{-1}$ is a homomorphism

I need to prove that $G$ is abelian if and only if the function $f : G \to G$ defined by $f(a)=a^{-1}$ is a homomorphism. Assuming that $∀a ∈ G, (a^{-1})^{-1} = a.$ I don't quite understand how to do or approach the proof. The only thing I…
user138974
  • 33
3
votes
2 answers

Prove by induction on $n\geq k$ that $n^3 \lt 3^n$. What is the value $k$?

Prove by induction on $n\geq k$ that $n^3 \lt 3^n$. What is the value $k$? It looks like $k$ should be $0$ after trying random values but obviously that is a terrible way of doing things. Proof: P(n): n^3<3^n Assume k holds Prove k+1 P(k+1):…
A A
  • 585
3
votes
1 answer

Finding a Closed Form of a Two Dimensional Recurrence

In a problem I'm working on, the following two-index sequence keeps popping up: $a(1,m) = 1$ for all $m$. $a(n,m) = 1$ if $n = m$. $a(n,m) = n(a(n,m-1) + a(n-1,m-1))$, $1 < n < m$. And if $n > m$, $a(n,m)$ is not needed to be defined. The sequence…
Bob Knighton
  • 434
  • 2
  • 11
3
votes
1 answer

There's only one pair of positive integers $x,y$ such that $n=\frac{(x+y)(x+y+1)}{2}+x$.

We have $n \in \mathbb{N}$. I need to prove that for any $n \in \mathbb{N}$, the number $n$ can be expressed as $\frac{(x+y)(x+y+1)}{2}+x=n$, where $x,y$ are two positive integers, and that this representation is unique. Can anybody give me a hint…
Arek Krawczyk
  • 2,114
3
votes
2 answers

Strong Induction - Understanding the lateral conditions.

I dont want the proof of this statement unless it is necessary for my questions, I just want some clarification. If cr = 1 would cr-1 = 0? How is cj 1 or 0? I understand cj is an arbitrarily picked number within the theorem 'line' but why is it…
Sad CRUD Developer
  • 452
3
votes
3 answers

8-element set question

Consider an $8$-element set $X$ with elements $\{x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8\}$. How many subsets of $X$ contain $x_2$ and $x_3$ but not $x_5$? Please give an arithmetic expression if possible. Any ideas guys? I have absolutely no clue…
kiasy
  • 127
3
votes
3 answers

Find the sequence.

I am given generating function $\ f(x)=\frac{1}{x-3} $ I have to find formula of the sequence which is generated by this function. Have to achieve this? I find some tutorials but it was hard for me to understand this. In some of them people where…
Marcin Majewski
  • 487
3
votes
2 answers

How many ways are there of rearranging the letters MATH such that each letter is replaced by a different one?

How many ways are there of rearranging the letters MATH such that each letter is replaced by a different one? In other words, no letters can be in the same place. So it starts as MATH. It could be THAM or AMHT. But it could not be MAHT because M and…
user3003255
  • 107
  • 1
  • 1
  • 4
3
votes
2 answers

Let ${a_n}$ be the sequence given by $a_1 = 3$ and $a_{n+1} = 2a_n + 5$. Use induction to prove that $a_n > 2^n$ for all $n \in N$

Let ${a_n}$ be the sequence given by $a_1 = 3$ and $a_{n+1} = 2a_n + 5$. Use induction to prove that $a_n > 2^n$ for all $n \in \mathbb{N}$ Attempt: For $n = 1,$ we have $3>2$ so the base case holds. Assume $a_k > 2^k$ for some k For $n = k+1$ we…
John
  • 99
  • 1
  • 6
3
votes
1 answer

Upperbound on harmonic number discrete math

How do I show $H_{2^k} \leq k + 1$ for each $k \geq 0$? I don't know how to do this question so can anyone help me?
user110344
  • 51
  • 2
3
votes
1 answer

compatible total order of hasse diagram

So I was assigned this problem for homework and I was able to all of them except for part D I would really appreciate any help or hints I have no clue where to start I looked through my book and everything anything would be appreciated
Will Jamieson
  • 301
3
votes
4 answers

Why is $2^n$ the maximum number of subsets of a set of size $n$?

There is a set with $n$ elements. Why is the maximum number of subsets that can be formed out of it $2^n$?
Shaurya Gupta
  • 4,339
1 2 3
…
99 100