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

How to prove that only 4n x 4m rectangles can be tiled with T tetrominoes?

I have a problem tiling a rectangle with T tetrominoes. I can prove that 4n x 4m rectangles can be tiled.How can I prove that only these rectangles can be tiled with T tetrominoes?
Liana
  • 21
1
vote
0 answers

Arrange the functions in a list so that each function is big-O of the next function.

If 2 functions each big $\mathcal O$ of each other, then place them on the same level. $x^2 + x^3, 3^x, x!, x \log(x), x^2 + 2^x, 2^{x \log(x)}, \log(x^2), 6 \log(x), 2^x, x(1+2+\dots+x)$ My answer is: $x(1+2+· · ·+x) = x(x(x+1))/2 = x(x^2+x)/2 =…
ionics
  • 11
1
vote
1 answer

Conservative obfuscations

I am reading this paper. Could someone please explain, at a high level, what 4.2.1 Conservative Obfuscations does? How is it different to non-conservative obfuscation? Just a basic explanation is fine.
John Smith
  • 13
1
vote
1 answer

contrapositive of $a^2 + b^2$ is divisible by $8$ iff $a$ and $b$ are both even

I'm working on creating a contrapositive statement to the one above and this is what I've come up with: $a^2 + b^2$ is not divisible by $8$ iff $a$ or $b$ are not even. I know that typically a contrapositive setup follows something like If $A$ then…
Tunifish17
  • 87
1
vote
2 answers

Total Orders and Minimum/Maximum elements

How can I prove that for any given Poset $(A,\preceq)$, $\preceq$ is a total order implies that $\forall a\in\preceq$, if a is a maximal, then a is maximum? Same goes for minimal/minimum.
Mirrana
  • 9,009
1
vote
1 answer

Find recurrence or formula for all labelings

There is a sequence $x_1, x_2, \ldots , x_n$. A valid labeling from $[1, k]$ is defined as for any $i, j \in [1, n]$, such that $i < j$: $$ \mathrm{label}[i] \leq \mathrm{label}[j]. $$ For $n=2$ and $k = 2$, a valid labeling would be :- $$ 1…
user434345
  • 113
1
vote
1 answer

Prove by induction for a sequence

Consider a sequence $g(n)$ defined by $g(1) = 2, g(2) = 3$ and $g(n+1) = 3g(n) - g(n-1)$ for $n > 1$. Prove by induction that $$g(2n) \equiv 3 \pmod{5}\quad \text{and} \quad g(2n+1) \equiv 2 \pmod{5}$$ for $n > 0$. I'm kind of getting stuck at the…
Mint
  • 113
  • 3
1
vote
2 answers

Consider the identity kC(n,k) = nC(n-1,k-1) where 1 <= k <= n, provy the identity by induction on n, using Pascal's identity

I've tried looking everywhere to get a clear understanding of the answer, however I am at a loss. The book says if n=1 then k=1. Assume the identity is true for n-1 we will shot it for n. If k=n, then both sides equal n. Otherwise k ≤ n-1. kC(n,k)…
SirChryse
  • 51
1
vote
1 answer

How many numbers are greater than 250, use only digits 1,2,3,4,5 and all their digits are different?

How many numbers are greater than 250, use only digits 1,2,3,4,5 and all their digits are different? When I approached this question, I tried to do the relevant number of options for 3 digits numbers + 4 digit numbers +..., and this actually going…
M.Mitelman
  • 125
  • 6
1
vote
1 answer

form matrix using xor of rows and xor of columns

Given : Matrix consist of $n$ rows and m columns For each row the xor of all elements in that row (suppose if there are 5 rows in a matrix then 5 numbers will be given representing the xor of each row) For each column the xor of all element in that…
akashking
  • 83
1
vote
1 answer

Composition of relation and transitive closure

Am I right in the following? Let $$A = {1, 2, 3, 4, 5}$$ and consider the following relation on A: $$R = {(1, 2),(2, 3),(3, 4),(4, 5),(5, 1)}$$ a) Here I am to find the composition of R on R. I got…
Eventhorizon
  • 35
1
vote
0 answers

Truth value of these statements?

Am I right in the following? a) $$∀x ∈ N: ∀y ∈ N: x + y ≥ 0$$ T b) $$∀x ∈ Z: ∀y ∈ Z: x + y ≥ 0$$ F c) $$∀x ∈ Z: ∃y ∈ Z: x + y ≥ 0$$ T
Travitrinket
  • 55
1
vote
5 answers

Determine the number of ordered triple $(x, y, z)$ of integer numbers (negatives and positives) satisfying $|x| + |y| + |z| \le 6$

Determine the number of ordered triple $(x, y, z)$ of integer numbers (negatives and positives) satisfying $|x| + |y| + |z| \le 6$ I know that final answer is 377, but how? Edit: Drawing from David K's answer: One way to count the ways is to first…
Esmaeil
  • 121
1
vote
1 answer

Generating function of binary string

Let $A=\{10,101\}$ and $B=\{001,100,1001\}$.Write $AB$ and $BA$ ,determine if they are uniquely created and their generating functions with respect to length. If $A$ and $B$ are sets of binary string, then $AB= \{ab \}$ where $a$ is in $A$ and $b$…
mathsstudent
  • 181
1
vote
1 answer

can someone help me prove this

$$ 2^{(AΔB)}=\{S|S = X\cup Y\} $$ where $ X∈ 2^A, Y∈ 2^B$, and $$S= Z\cup W $$ where $Z∈ 2^{(A)^c}, W∈2^{(B)^c}$
Mahmood Jazmawy
  • 21
  • 4
1 2 3
…
99 100