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

How many 0,1 bit strings of length 10 are there which do not contain a string of 1001001?

I've never been asked a question involving how many do not contain a specific string and I'm not quite sure how to go about answering this question.
Anthony
  • 177
1
vote
1 answer

Bijective Correspondence Between function and cartesian product

What I'm asked to do is to find a bijective correspondence between $\mathcal F$ (set of functions with domain {0,1} and codomain $\Bbb N)$ and $\Bbb N$ X $\Bbb N$. What I was thinking first of all was for each function, f(0) would be the first…
Pwned1760
  • 75
1
vote
2 answers

Proof by Contradiction: let a,b $\in$Z . Prove that if 3 $\nmid$ a and 3 $\nmid$ b then $3 | a^2 - b^2$

Just wondering if this works for this question, book had a different answer and I couldn't find another answer for the question. Assume, to the contrary, that 3 | a and 3 | b, then a = 3k, and b = 3x for x,k $\in$ Z, then $a^2 - b^2$ = $(3k)^2 -…
Jacob B.
  • 19
1
vote
1 answer

Solving proposition calculus problem without truth table

Show that the next conditional statement is a tautology without using truth tables: $$ \big((p \ \vee q) \wedge(p \ \rightarrow r) \wedge(q \rightarrow r)\big) \rightarrow r $$ How to show it without truth table?
Koki
  • 21
1
vote
2 answers

Which integers are congruent to $51 \pmod{14}$?

Which integers are congruent to $51$ mod $14$? a. 15 b. -19 c. -9 d. 9 e. 121 f. 135 Mod is new to me... but I know $51 = 14 \times 3 + 9$. This in return $= 9 \pmod{14}$. So the numbers would be: $9, 23, 37, 51, 65, 79, 93, 107, 121, 135, 143,…
I'm Hungry
  • 181
1
vote
3 answers

Prove that $\{(i, j, k)$ in $\mathbb{N}\}$ is countable

I have the following definition... $$T=\{(i,j,k)\mid i, j, k \in\mathbb{N}\}$$ How do I prove whether it is countable? My understanding is that I need to prove that every subset of $(i,j,k)$ maps to some number $n$. For example... $1$ maps to…
buydadip
  • 819
1
vote
2 answers

Prove that $m_n \leq 3^n$ for all $n\in \Bbb{Z}_+$

Given that $m_1= 2$ and $m_2 = 9$ and that $m_n = 2m_{n-1} + 3m_{n-2}$ for $n \geq 3$ This is what I've done so far. $3^{n+1}$ = $3^n \cdot 3$ $3^{n+1} \geq 3 \cdot (2m_{n-1} + 3m_{n-2})$ $3^{n+1} \geq 6m_{n-1} + 9m_{n-2}$ $m_{n+1} = 7m_{n-1} +…
Eric
  • 11
1
vote
0 answers

Principle of Inclusion and Exclusion question, "Some but not necessarily all" confusion.

After a round of "trick or treating", Candice has 13 KitKats and 14 Twix in her pillow case. Her mother asks her to share some (but not necessarily all) of the loot with her three younger brothers. (A) How many different ways can she do this? (B)…
Jacob Duggan
  • 11
1
vote
1 answer

Discrete Maths - need help

I have a question which i got on my discrete maths coursework and i'm struggling to solve it. The question is: Represent the statement that: “A car is either moving or stationary; if a car is stationary then its brakes are applied; the car does not…
DarkArmy
  • 3
1
vote
1 answer

Solving recurrence relations using characteristics root techinque

During solving recurrence relations using characteristics root techinque why do we assume $F(n) = r^n$?
user487644
  • 23
1
vote
2 answers

Determining if $f(x) = 7x + 11 \pmod{10}$ is invertible

Is the function $$f(x) = 7x + 11 \pmod{10}$$ invertible for all positive integers? I don't know how to go about it, mainly because I have never dealt with functions such as this one.
Steinberg
  • 11
1
vote
0 answers

composition of power relations

maybe easy answer but i have to be sure.. I used search and did not find this. So Lets say i have set R:{(1,2)(2,3)(3,1)(3,4)}. And i want to make a composite relation of it. So R²(R◦R) is {(1,3)(2,1)(2,4)(1,2). But now the question, how i count R³…
Johnny
  • 11
1
vote
2 answers

binary relation that is both symmetric and irreflexive

I was asked to find a binary relation on $A$ that is symmetrical and irreflexive, and which is also a function from $A$ to $A$ where $A=\{1,2,3,4\}$ so i don't know if its correct but i came up with these $\{<1,2>, <1,3>, <1,4>, <2,1>, <2,3>, <2,4>,…
j77
  • 11
1
vote
0 answers

Ranking functions in order of increasing complexity.

I have a list of functions here that I need to rank in order of increasing complexity. They are: n!, $n^2$, 3$n^3$, 1000n + 2, n$\log_{10}(n)$, 20$\log_2(n)$, $3^n$ + $n^2$, $2^n$ + $n^3$ This is how I have ranked them in order of increasing…
Broadsword93
  • 567
  • 6
  • 21
1
vote
0 answers

$\mathcal F\subset 2^{[n]}$ and $\forall F_1, F_2\in\mathcal F : |F1∩F2| \neq0$. What is the amount of $\mathcal F : |\mathcal F| = 2^{n−1}$?

$\mathcal F \subset 2^X$, where $ X = \{1\ldots n\} $ and $ \forall F_1, F_2 \in \mathcal F$ : |$F_1 \cap F_2 $| $ \neq 0$. I need to find the amount of such $\mathcal F$ such that |$\mathcal F$| = $2^{n-1}$. Can anyone help?
John Smith
  • 11
1 2 3
…
99 100