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

GCD(a,b) as a linear combination of a,b

I know that the GCD(a,b) can be written as a linear combination of a,b (ma + nb = GCD(ab)). How can I select which coefficient (m or n) is positive? In other words, for example, if after executing extended euclidean division, I obtain the…
baba
  • 299
2
votes
3 answers

Help with Set Theory/ Proofs

Can you conclude that $A = B$ if $A$, $B$, and $C$ are sets such that (a) $A \cup C = B \cup C$ No, the sets $A=\{1,2\}, B=\{3,4\}, C=\{1,2,3,4,5\}$ disprove this, because $A \cup C = B \cup C$ but $A\neq B$ (b) $A \cap C = B \cap C$ No, the sets…
user155456
  • 21
2
votes
1 answer

Need help with discrete mathematics (two player games)

I am having trouble with this Tac Tix game.Any help or hints would be greatly appreciated.
user152063
  • 159
2
votes
3 answers

Discrete Mathematics - Is my answer correct?

$x_1 + x_2 + x_3 = 15$ where $x_1$ and $x_2$ and $x_3$ are non negative integers. How many solutions are there when $1\le x_1\le 6$? the solution i came up with is = $\binom{15+3-1}{15} - \binom{6+3-1}{6}$ Is this correct?
sam
  • 23
2
votes
1 answer

How many numbers with $3$ digits can be formed with the digits $1,2,3,4,5$?

How many numbers with $3$ digits can be formed with the digits $1,2,3,4,5$ if there is no restriction at the repetition of the digits how many if no digit can be repeated more than twice and how many if repetitions are not allowed For the first…
evinda
  • 7,823
2
votes
2 answers

feedback on my solution regarding eqivalence relations.

For all $x, y \in \mathbb{R}$ define that $x \equiv y$ if $x^2 = y^2$. Then $\equiv$ is an equivalence relation on $\mathbb{R}$, there are infinitely many equivalence classes, one of them consists of one element and the rest consist of two…
user129834
  • 21
2
votes
0 answers

Problem of badminton singles tournament

In a badminton singles tournament, each player played against all the others exactly once and each game had a winner. After all the games, each player listed the names of all the players she defeated as well as the names of all the players defeated…
Ruddie
  • 436
2
votes
2 answers

How find a example such this set condition?

Assmue that the set $$S=\{a_{1},a_{2},\cdots,a_{8}\}, 1\le a_{i}< 100,a_{i}\in N$$ there for any subset $A=\{b_{1},b_{2},\cdots,b_{p}\}$ and $B=\{c_{1},\cdots,c_{q}\},A\neq B$ (mean that $A\subset S,b\subset S$) and such…
math110
  • 93,304
2
votes
1 answer

How to guess an explicit formula using iteration

EDIT: Adding in more information that is hopefully useful. This is part of a multi step question I'm trying to answer for my homework. First we were given a1 = -3 and a formula ak+1 = ak -1, for all integers k >= 1 Using this formula we then had to…
Daniel Love Jr
  • 123
2
votes
3 answers

How many even functions are there from $\{-n, \dots,n \}$ to itself?

If $A=\{-n,-n+1, \dots, n-1,n \}$, how many functions $A \to A$ are there,that are even,so they satisfy the condition $f(-x)=f(x), \forall x \in A$? Is it maybe $(\frac{|A|}{2})^{|A|}$ ?
evinda
  • 7,823
2
votes
0 answers

Finding the number of relations on set S

I know the number of reflexive relations on a finite set is: $2^{n^{2}-n}$ The number of symmetric relations is: $2^{n+1 \choose 2} $ The number of antisymmetric relations: $2^{n}3^{n \choose 2}$ But, how do I find the number of relations that…
CloudN9ne
  • 349
2
votes
1 answer

Difference in choosing probability and fraction probability.

a) probability of choosing 3 of same color? I am aware that the probability is 3*C(5,3)/(15,3). But how would you do it fraction wise? The first pick would be 15/15 because its any of the 15 objects. Then it would be 10/15 and 5/15. So fraction…
Roy Kesserwani
  • 383
2
votes
3 answers

Proof by Direct Method

If $(3n+2)$ is odd then, prove $n$ is odd. $$3n+2 = (2n+1)+(n+1)$$ We already have a fact that $2n+1$ is always odd. So, for $3n+2$ to be odd, $n+1$ should be even (For $x+y$ to be odd then either $x$ or $y$ should be odd not both) As, $n+1$ is…
Arun Poudel
  • 123
2
votes
1 answer

Spelling has deteriorated by the year of 2075, how many spellings are possible?

By the year 2075, spelling has deteriorated such that the dictionary now defines the spelling of the word “RELIEF” to be any combination (with repetition allowed) of the letters F, L, R, I and E subject to these constraints: The number of letters…
494928770
  • 21
2
votes
2 answers

Finding $n$ such that $\phi(n)=34$ (where $\phi$ is Euler's totient)

How can I find $n$ such that $\phi(n)=34$ (where $\phi$ is Euler's totient) or prove that it does not exist? And how can I find $c$ for which $\phi(n)=c$ if $n$ does exists for $c$?
jack
  • 21
1 2 3
…
99 100