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

Discrete Mathematics

I am having great difficulty trying to understand a question I have found and am keen to finding the solution and would appreciate any help. "Suppose that ten computer programs have been submitted for batch processing. Only one program may run at a…
dave collins
  • 25
2
votes
1 answer

Recursive function calculation.

Suppose $f(n)=3f(\frac{n}{2})+1$ when n is even, and $f(1)=5$, please find $f(2),f(4),f(10),f(14)$ and so on. I did $f(2)$ and $f(4)$ and answer is 16 and 49. But I am not sure if I am right about $f(10)$. So far I did: $f(10)=3f(5)+1 = 2(3f(2)+1)+1…
PeaceKing
  • 67
2
votes
1 answer

Finding a function into a closed form of the generating function

I have the following equation:$$a_n = n((-1)^n(1-n) + 3^{n-1})$$ How do I convert this into a closed form of the generating function?
Kadana Kanz
  • 163
2
votes
2 answers

Is this proof for 1/4 mod 9 = x, correct?

Find an integer x so (1/4) mod 9 = x Proof: > 1/4 mod 9 = x > 1 mod 9 = 4 * x > - using x = 7 - > 1 mod 9 = 28 > 28 mod 9 = 1 (to validate) > - using Euler division theorem m = nq + r - > 28 = 9(3) + 1 > r = 1, so 1 = 1 I appreciate the…
Juan Zamora
  • 127
2
votes
2 answers

Counting and solving bijection

Given the problem: Please count how many functions $f : D → \{0, 1 \}$ can be defined if the domain D is a finite set with the cardinality $|D| = n$. Is there a bijection between the set of all such functions and the powerset $\mathcal{P}(D)$? For…
Csci319
  • 779
2
votes
1 answer

Proving a property about modulus

I seem to be having a lot of trouble finding a place to start in proving that $$(a \cdot b) \mod m = ((a \mod m) \cdot (b \mod m)) \mod m$$ Any ideas on how I should go about doing this? I've been trying for about 30 minutes now with no progress.
user2789945
  • 153
2
votes
2 answers

A linear non homogeneus recurrence relation

Im using the minimax algorithm for a very simple game and when counting the tree nodes found the recurrence $T(n)=T(n-1)+T(n-2)+1$, with $0$ and $1$ as initial values. I tried generating functions: $G(x)=\sum_{n=0}^\infty T(n)x^n$ and…
Miguel Ángel Norzagaray Cosío
  • 79
2
votes
0 answers

Determine the possible grouping

Consider I have a set of $3$ object $1,2 $ and $ 3.$ What is the possible grouping? I'll have either $\{(1,2,3)\}$ or $\{(1),(2),(3)\}$ or $\{(1,2),(3)\}$ or $\{1,(2,3)\}$ or $\{(2,(1,3)\}.$ So, I'll have $5$ possible grouping. In the same manner…
elnaz irannezhad
  • 121
2
votes
1 answer

Distributing r identical obejcts into n distinct containers.

So, lets say I have $4$ burglars, and I have a custom pistol with $10$ bullets in it. How many possible ways can I put $10$ bullets into EXACTLY $2$ burglars and let the other $2$ get away? Note that I am NOT looking for an ANSWER, I am only asking…
Belphegor
  • 1,268
  • 6
  • 27
  • 51
2
votes
3 answers

How do I find equivalence classes?

Let A = {a, b, c, d, e} Suppose R is an equivalence relation on A. Suppose R has three equivalence classes. Also aRd and bRc. Write out R as a set. From my understanding an equivalence relation is reflexive, symmetric & transitive. I understand that…
Hare Krishan
  • 221
2
votes
3 answers

Is R reflexive? symmetric? transtitive?

Define a relation on $\mathbb{Z}$ as $xRy$ if $|x-y| < 1$ Is $R$ reflexive? symmetric? transitive? Okay so my reasoning is as such: $|x-y| < 1$ only when $x=y$ $R$ exists if $x=y$ If $x=y$ the relationship is reflexive. If $x=y$ the relationship is…
Hare Krishan
  • 221
2
votes
2 answers

discrete math: Big-oh notation

I'm confused about how to solve big-oh notation problems using the definition and basic algebra. for example, a problem like this: Prove that (x sin x + x log(2x + 4) + ((x^3 + 1)/(x^2 + 1)) is an element of big-oh(x log x). hint:This will require…
Cintra
  • 95
2
votes
3 answers

a question on an arithmetic progression with four terms

I am self-studying Discrete Mathemamatics and I've found the following example (in Portuguese). Find an arithmetic progression with four terms $(a, a+r,a+2r,a+3r)$ such that the sum of its terms is $16$ and the product is $105$. The author start…
user23505
2
votes
2 answers

Equivalence relation that has exactly two equivalence classes?

I just want to see if I am understanding this correctly. I have to create an equivalence relation on 1,2,3 that has exactly two equivalence classes. So I came up with S = {(1,1), (2,2), (3,3), (1,2), (2,1)}. So the equivalence classes would…
Xellic
  • 37
2
votes
4 answers

Show an example of a function from $\mathbb Z \to \mathbb Z$ that is surjective but not injective

The question I am working on is this... Give an example of a surjective function from $\mathbb Z \to \mathbb Z$ that is not injective. My question is simple, when it is worded as above, (which I can't seem to get a straight answer on from others)…
John
  • 21
1 2 3
…
99 100