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
4 answers

A store is selling 5 types of hard candies. How many ways are there to chose?

The choices are lemon, cherry, strawberry, orange, and pineapple. How many ways are there to chose $35$ candies? I thought it would be $35^5$ because there are $35$ choices with $5$ options but that is not correct. Next, how many ways can you get…
Chris
  • 23
2
votes
2 answers

If $a$ and $b $ are two integers, and $a \mid b$, then gcd$(a^2,b^2)$ =

If $a$ and $b $ are two integers, and $a \mid b$, then gcd$(a^2,b^2)$ = I think the answer is $a^2$. Is it correct?
user109886
  • 498
  • 1
  • 6
  • 12
2
votes
3 answers

Prove that either $(2^{10500} + 15)$ or $(2^{10500} + 16)$ is not a perfect square.

Prove that either $(2^{10500} + 15)$ or $(2^{10500} + 16)$ is not a perfect square. how should I solve this problem? what is the idea for solving this kind of problems? Thank you so much
user112636
  • 311
  • 2
  • 8
  • 13
2
votes
4 answers

How to determine if a function is Surjective quickly

I know how to determine if a function is surjective but it takes a lot of time and it's not always correct. So, are there any tricks? For Example: f : $\Bbb N$ x $\Bbb N$ → $\Bbb N$, $f(a,b) = \left(\dfrac{ab(a+b)}{2}\right) $ a surjection? I…
user109886
  • 498
  • 1
  • 6
  • 12
2
votes
1 answer

I am having a really hard time understanding NFAs as opposed to DFAs. I have a few questions about how they work.

Deterministic Finite Automata make perfect sense to me. They are essentially a flowchart and cover every possible input and transition from and to each state. Non-Deterministic Finite Automata, on the other hand, completely bewilder me. I don't…
Logan Shire
  • 123
2
votes
8 answers

Proving for every odd number $x$, $x^2$ is always congruent to $1$ or $9$ modulo $24$

A problem I have been presented with asks the following: Prove for every odd number $x$, $ x^2$ is always congruent to $1$ or $9$ modulo $24$. This seems odd and non-intuitive to me. Of course, it must be true other wise they wouldn't be asking for…
Bob Shannon
  • 1,561
2
votes
2 answers

find all integers x such that $4x^2 - 1$ is prime

I tried factoring it and got $(2x+1)(2x-1)$, however I do not know how to prove for all integers from here.
Bygonaut
  • 41
  • 3
2
votes
1 answer

Use the definition of a derivative to find $f'(x)$ when $f(x) = \frac{x}{(x+1)}$

Use the definition of a derivative to find $f'(x)$ when $f(x) = \frac{x}{(x+1)}$ the definition being: $$\lim_{x \to c} \frac{f(x)−f(c)}{x - c}$$
Bygonaut
  • 41
  • 3
2
votes
1 answer

Invalid operator in sequences

$V_n = n! + 2$ $n \ge 1$ Find $V_3$. I am just wondering what does the "!" operator after "$n$" mean?
Jasmine
  • 121
2
votes
0 answers

Big-O Notation question

Use the definition of $ "f(x) is O (g(x)) $ to show that $ x^4+9x^3 + 4x+7 is O(x^4) $ My answer was : I used divide and conquer $ x^4 \le cx^4 , when\; c = 1 $ $ 9x^3 \le cx^4 , when \; c=9 \; and \; x\gt 1$ $ 4x \le cx^4 , when \; c=4 \; and \;…
Out Of Bounds
  • 1,531
2
votes
3 answers

Recurrence Equations

Can someone explain how that Tn = 2Tn-1 + 1 sequence actually works?
Samuel Longgat
  • 21
2
votes
2 answers

Union and Intersection of Collection of Sets

I'm attempting a problem: Find $\bigcap_{i=1}^\infty Ai$ and $\bigcup_{i=1}^\infty Ai$, if for every positive integer $i$ $Ai=(0,i)$, that is, the set of real numbers $x$ with $0
Bob Shannon
  • 1,561
2
votes
2 answers

Why $p \leftrightarrow q$ is equivalent to $(p \wedge q) \vee (\neg p \wedge \neg q)$? Without using the truth table

I want to know why $p \leftrightarrow q$ is equivalent to $(p \wedge q) \vee (\neg p \wedge \neg q)$? Without using the truth table. Thanks all
user2849967
  • 331
2
votes
3 answers

Hamilton Path properties

As I understand a graph has a Hamilton Circuit if It has $n \ge 3$ vertexes degree of every vertex is at least $n/2$ $\deg u + \deg v \ge n$ for every pair of nonadjacent vertices $u$ and $v$ in the graph I can't seem to find a concrete set of…
Øyvind
  • 131
2
votes
0 answers

For what $n$ do we have $ F_{n}=\lfloor \frac{1}{\sqrt{5}} ( \frac{1+\sqrt{5}}{2})^n +\frac{1}{2} \rfloor $

For what $n$ do we have $ F_{n}=\lfloor \frac{1}{\sqrt{5}} ( \frac{1+\sqrt{5}}{2})^n +\frac{1}{2} \rfloor $ where $F_{n}$ is the nth element of the Fibonacci sequence. Naturally I have to use the formula $F_{n}= \frac{1}{\sqrt{5}}( (…
Arek Krawczyk
  • 2,114
1 2 3
…
99 100