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

How to prove not an integer?

The question I am trying to figure out is Let n and m be positive integer and let d = gcd(n,m). Define l = nm/d Let k > d. Prove that at least one of the following statements must be false. a) nm/k is not an integer b) n | (nm/k) c) m | (nm/k) I…
Gaurav
  • 113
  • 4
1
vote
2 answers

Size K subset sum problem?

I am trying to solve the following problem - I have a set of $n$ elements consisting of objects say from $O_1$ to $O_n$ ($\{O1_,O_2,O_3,........,O_n$}). Each of those elements are mapped to an integer in a specific range (for the sake of simplicity…
AnkitSablok
  • 510
1
vote
1 answer

Discrete On Recurrence Sets

Find a recurrence relation for the number of ways to select a subset (any size, including the empty set) from the set {1,2,3, … ,n} that does not contain a pair of consecutive numbers? Would this problem be similar to induction? not sure how to…
user142743
  • 127
1
vote
1 answer

Discrete Math On Recurrence

Suppose that a geometric sequence starts with and satisfies the recurrence $a_n = ra_{n -1}$ for every positive integer $n$. a) Show that $a_n = a_0rⁿ$. b) Find the 100th number in the sequence 3,6,12,24,48, … . I know this is a another…
Alex
  • 23
1
vote
1 answer

Discrete Math On inductions

Show that the sequence defined by the formula a_n = n+3, satisfies the recurrence relation a_n = 2a_n-1 - a_n-2 ,for all n ≥ 2. I know this is a induction problem and I think I have to set n= n+1 but I'm not sure that how would I show the…
Alex
  • 23
1
vote
2 answers

How to Solve: $2014 ^{2015} \pmod 7$

$$2014^{2015}\pmod 7$$ How do you find the mod of above without using a calculator.
Jason
  • 31
1
vote
1 answer

How many edges does a full binary tree with 1000 internal vertices have?

Following my textbooks definition of a full binary tree, which is: If T is a full binary tree with i internal vertices, then T's total vertices = 2i + 1. So with 1000 internal vertices, there would be 2001 total vertices. I then used this formula…
bangsauce
  • 133
1
vote
2 answers

set problem subsets of function

Let $f \colon A \to B$ be a function and let $p$ and $q$ be subsets of $A$. How can we prove by counterexample that $f(p) \cap f(q)$ is not a subset of $f(p \cap q)$? Could anyone show me how to solve this problem? Please?
chris
  • 11
1
vote
1 answer

put numbered balls in four similar boxes of a specific capacity...

With how many ways can we put $12$ numbered balls in $4$ similar(not numbered) boxes of capacity $3$ each one? Is it maybe $3^4$ ?
evinda
  • 7,823
1
vote
1 answer

put balls in boxes with specific capacities

We have $10$ numbered balls and $3$ boxes with capacities: $5$, $3$ and $2$ balls. With how many ways can we put the balls in the boxes? The boxes are distinguished. I thought that it is like that: $\binom{10}{5} \cdot \binom{5}{3} \cdot…
evinda
  • 7,823
1
vote
2 answers

choice of integers,so that a condition is satisfied

With how many ways can we choose the integers $x_1,x_2, \dots , x_k$ such that the condition $1 \leq x_1
evinda
  • 7,823
1
vote
1 answer

how many different choices exist?

If we choose $k$ objects from $n$ with replacement and we don't ignore the order of the choices(e.g if we choose $3$ objects of $A,B$ with replacement,the results $AAB$ and $ABA$ are considered as different ones),how many different choices exist? Is…
evinda
  • 7,823
1
vote
4 answers

arrangement of digits

With how many ways can we arrange the digits $1,2, \dots, 9$,so that $1$ precedes $2$ and $2$ precedes $3$? Also,with how many ways can we arrange these digits,so that between $1$ and $2$ there are three digits?
evinda
  • 7,823
1
vote
1 answer

Are every prime (except 2,3,5) divisor of some of 10^n+1?

Referring to Is it true, that every prime (except 2) can be found as a divisor of enough long series of 1-s? , I have the same question. I have the intuitive hyptohesis, that every prime can be found as a divisor of at least one of 11, 101, 1001,…
peterh
  • 2,683
1
vote
2 answers

Probability of rolling at least 2 sixes

Okay I do know the answer is $$ \frac{6^5 - 5^5}{6^5} $$ which gives you the probability of at least one six. But then how can you find the probability of at least "Two" sixes? I think this should be related to choosing from a set? I'm not sure…
Roy Kesserwani
  • 383
1 2 3
…
99 100