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

With how many ways can there be $n$ couplings between $n$ men and $n$ women?

Could you help me with the following exercise? Could you give me a hint? With how many ways can there be $n$ couplings between $n$ men and $n$ women?
Mary Star
  • 13,956
1
vote
2 answers

Combinations and Permutations

How many arrangements of the letters in DIGITAL have two consecutive I’s? I know this is a type combination, permutation problem but i'm a little unclear how to start with this problem.
user142743
  • 127
1
vote
2 answers

Proving that a set is denumerable without using a particular theorem

this question may seem like a duplicate of another one that I asked, but it is not. In this question, I am not allowed to use the Theorem which states: Every infinite subset of a denumerable set is denumerable. The Problem: Prove that $S=\{(a,b):…
mrQWERTY
  • 595
1
vote
2 answers

Solving a Linear Non-Homogeneous Recurrence

How can I solve the following recurrence? $$a_n = 121a_{n-2} + 14400 n$$ I derived this: $$\frac{1228}{11} (-11)^n + \frac{-4044}{11}11^n + 4800n$$
lambda
  • 159
1
vote
1 answer

Finding formula for a series and proving

Find a formula for $\displaystyle\sum_{i=1}^n \frac{i}{(i+1)!}$ and prove that it holds for all $n \ge 1$. How do you find an equation for this formula? Is it common sense or is there a way to find it? I'm not very good with sequences or series.…
Roy Kesserwani
  • 383
1
vote
1 answer

Finding the radius of a sphere touching other spheres inscribed in n-dimensional spaces

I know for certain that the radius of the first one is $r=(\sqrt2-1)/2$. I assume the radius of the other dimensions are the same but I don't know how I would create an equation to prove that. Lastly I have no idea what the last part is asking, I…
user142627
  • 11
1
vote
2 answers

Induction And Proofs

Find a formula for $\sum_{i=1}^{n} \frac{1}{(2i-1)(2i+1)}$ and prove that it holds for all $n \geq 1$ I don't know how to solve this particular problem, can someone help me please. Thanks
Alex
  • 29
1
vote
1 answer

Number theory, proving or finding counterexample.

Prove or find a counterexample: The product of any three consecutive natural numbers is divisible by 6. Answer True, because product of three consecutive natural numbers can be divisible by 6. Thus, $(n)\dot{}(n+1)\dot{}(n+2) | 6$ Can i get a…
KRISSH
  • 139
1
vote
0 answers

Transitive relations.

"A relation R on a set A is transitive if whenever aRb and bRc then aRc, that is, if whenever (a,b), (b,c) is an element of R then (a,c) is an element of R. Thus R is not transitive if there exist a,b,c is an element of R such that (a,b), (b,c) is…
user71181
  • 253
1
vote
1 answer

Proving the harmonic number

For $n \in \mathbb N^{+}, H_n = \sum_{i=1}^n \frac{1}{i}$ is called the $n$-th harmonic number. (a) Prove: $$\forall{n \in \mathbb N}: 1+ \frac n2 \le H_{2^n} $$ This is one of my homework questions and I do not know how to even begin. I was perhaps…
CloudN9ne
  • 349
1
vote
1 answer

Boolean function proving contradiction ,tautology or neither

Determine whether $((p \Rightarrow q) \Rightarrow r)\Leftrightarrow (p \Rightarrow(q \Rightarrow r))$ is a tautology, a contradiction, or neither. $$\begin{array}{cccc} \underline{p}&\underline{q}&\underline{r}& \underline{((p \Rightarrow q)…
KRISSH
  • 139
1
vote
1 answer

Prove the claim

Prove the following Claim: "Claim: Suppose sets $A$ and $B$ are finite subsets of a finite set $U$ Then $|A| \cap |B| \ge |A| + |B| - |U|$" By subtracting $|A| \cap |B|$ from both sides and adding $|U|$ to both sides I get $|U| \ge |A| + |B| - |A…
WhatsAGuitar
  • 109
1
vote
2 answers

Inductions and proofs

Let $(h_n)$ be a sequence defined by $h_0 =1 , h_1 = 2, h_2 =3$ and $h_n = h_{n-1} + h_{n-2} + h_{n-3}$, for all $n\ge 3$. Prove that $h_n\le 2^n$ , for all $n\ge 0$ Not sure how to go with this problem?
Alex
  • 29
1
vote
1 answer

How do you know how many coins to start off with on each side of a "find the counterfeit coin using a 2-pan weigh scale" problem?

The fake coin is defined by either having a lesser or greater weight than all of the other coins in the problem. Say there are 12 coins, 1 out of the 11 which is the fake coin. How does everyone know to start off by initially weighing 4 coins…
user3451821
  • 57
1
vote
1 answer

Discrete Math on Induction and proof 1

A ball is dropped from a height of 4 feet, and each time it hits the ground it rebounds to ¾ of the previous height. What is the total distance that the ball will have traveled when it reaches the top of its twentieth rebound? I know that I have to…
Alex
  • 31
1 2 3
…
99 100