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

Handshake Variant

Twelve business associates meet for lunch. As they leave to return to their offices a couple of hours later, one of them conducts a small mathematical experiment, asking each one in the group how many times he or she shook hands with someone else in…
Alex
  • 134
  • 8
1
vote
0 answers

Solve linear congruence with two variable with different mod

My question is as following: How do I solve: $$3x+2y \equiv 2 \ \ (mod 5) $$ $$x+y \equiv 3 \ \ (mod 4)$$ My thought is to use Chinese remainder theorem to first find a solution such that: $$z \equiv2 \ \ (mod5)$$ $$z \equiv 3 \ \ (mod…
aawangas
  • 39
1
vote
1 answer

Show $|u^n| = n|u|$ for all strings $u$ and all $n$

Can anyone please help me with this homework question on automata from Peter Linz? Use induction on $n$ to show that $|u^n| = n|u|$ for all strings $u$ and all $n$.
sowmya
  • 13
  • 1
  • 3
1
vote
1 answer

Show that $g(X)=\{f(x)|x\in X\},X\subseteq A$ is bijective.

Let $f:A\to B$ be bijective. Show that $g:P(A)\to P(B)$, defined as $$g(X)=\{f(x)|x\in X\},X\subseteq A$$ is also bijective. Let's first try to show that $g$ is injective. So we need to show that if $g(X_1)=g(X_2)$, then $X_1=X_2$.…
Math Student
  • 2,656
1
vote
0 answers

Is this Hasse Diagrams correct?

I have the following problem: Given set A={a,b,c,d,e} and R={(a,a),(a,c),(a,d),(a,e),(b,b),(b,c),(b,d),(b,e),(c,c),(c,d),(c,e),(d,d),(e,e)} This might be easy but I'm trying to draw the Hasse Diagram for this problem but don´t fully understand how…
jaguirre.
  • 11
1
vote
1 answer

The question is about listing all the elements of a set given some conditions for the elements.

List the elements of each of the following sets: $\{x | x ∈ \mathbb{Z}^+ , x | 36\}$. So, I understand what $\mathbb{Z}^+$ and $x | 36$ means; however, confusion has risen when I saw two slightly different solutions to this question. A tutor has…
Talal Farhoud
  • 21
1
vote
0 answers

Double Summations with a Table

I am working on a problem that states: Find a closed form expression for the following double summation in terms of n: $\sum_{j=1}^n\sum_{k=j}^n\frac{1}{k}$ My professor said I should be solving this with a table, but I cannot find any examples of…
Matthetart
  • 11
1
vote
2 answers

Why does the solution to this problem includes (2,3) and (3,2)

There is this problem: "What is the smallest equivalence relation on the set {1, 2, 3, 4, 5} containing the relation {(1,2), (1,3), (4,5)}?" Per my understanding, an equivalence relation need to satisfy three properties, reflexivity, transitivity,…
nguyen quanganh
  • 11
1
vote
0 answers

Let A be the set of English words that contain the letter x

Q: Let A be the set of English words that contain the letter x, and let B be the set of English words that contain the letter q. Express each of these sets as a combination of A and B. (d) The set of English words that do not contain either an x or…
Eric
  • 135
1
vote
0 answers

To find all subsets contain 7 elements from the set $ [{1, 2, ..., 14} ]$ such that the sum of the elements is divisible by 14

anyone can help solve this problem? How many subsets contain 7 elements from the set $[ {1, 2, ..., 14}]$ such that the sum of the elements is divisible by 14
Idham Muqoddas
  • 29
1
vote
1 answer

Counting odd and even compositions of integers

A composition of the number $n$ with $k$ summands is the representation $$ n = a_1 + \cdots + a_k$$ with integers $a_i \geq 1, 1 \leq i \leq k$. The order of the summands is important. Prove: There are as many compositions of n with k even…
muffel
  • 2,879
1
vote
1 answer

Construct completely multiplicative function with range ±1 and prefix sum between ±k

Consider a completely multiplicative function ($f(mn)=f(m)f(n)$ for positive integer $m$ and $n$) with a range of $\{-1, 1\}$. The prefix sum of it is $S(x)=\sum_{i=1}^x f(i)$. Let $k$ be a given positive integer. If $|S(x)| \le k$ holds for every…
Alex-Github-Programmer
  • 535
1
vote
1 answer

A simple question about "discrete" hypercubes and their self-mappings

Let $n$ be a positive integer and consider the set $\{0,1\}^n$. What is this set usually called? I've seen some authors refer to it as the $n$-dimensional hypercube, whereas others typically use that name for the compact set $[0,1]^n$. Now consider…
raving-bandit
  • 175
  • 7
1
vote
2 answers

Find the least significant digit of $2^{3A}$, where $A=10^{100}$

Can anyone please tell me - What is the least significant digit in $2^{3A}$? How do we define least significant digit?
abipc
  • 123
1
vote
2 answers

$\forall x {\in} \Bbb R\; \exists y {\in} \Bbb R \;\,2y^2(x-5)<1$

Prove or disprove that $\forall x {\in} \Bbb R\; \exists y {\in} \Bbb R \;\,2y^2(x-5)<1.$ Since $2y^2(x-5)<1 \Rightarrow y^2(x-5)<\frac{1}{2}.$ Take $y=\frac{1}{\sqrt {x-5}}.$ Then $\left(\frac{1}{\sqrt {x-5}}\right)^2(x-5)=1<\frac{1}{2},$ which…
RV math
  • 67
  • 6
1 2 3
…
99 100