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.
31,670
questions
0
votes
1
answer
35
views
Number Theory Proof on Binomial Theorem
I was trying this proof.
If $2\le k\le n-2$
$${n\choose k}= {n-2\choose k-2}+2{n-2\choose k-1}+{n-2\choose k}$$
for $n\ge 4$.
It appears that we need to induct on n. But since it is given that 2<=k&...
1
vote
1
answer
36
views
Hall's marriage, a question
The question is below:
At a bakery the baker made 20 kind of cookies, from each kind he made exactly 20 cookies. Once baked, he randomly put them at 20 table pans, at each table pan he put exactly 20 ...
- 339
2
votes
1
answer
41
views
What does $\exists x\left(L\left(x,x\right)\wedge \forall z\left(L\left(x,z\right)\rightarrow \left(z=x\right)\right)\right)$ mean?
I translated "There is someone who loves no one besides himself or herself" as $$\exists x\left(L\left(x,x\right)\wedge \forall z\left(L\left(x,z\right)\rightarrow \left(z=x\right)\right)\...
- 45
0
votes
1
answer
27
views
Proof the cardinality of the set of all periodic functions from $ \mathbb{R} $ to $ \mathbb{R} $ is $ \aleph_1 $
Let $ A = \{ f \in \mathbb{R}^\mathbb{R} \mid f \text{ is periodic }\} $.
I want to prove that its cardinality is $ \aleph_1 $. Can you verify my proof?
First, $ A \subseteq \mathbb{R}^\mathbb{R} \...
- 805
0
votes
1
answer
47
views
kernel of subgroup homomorphism
Let $f:A \longrightarrow B$ be a group homomorphism, and note $C$ a subgroup of $A$ and $D$ a subgroup of $B$. Can we find a link between the kernel of $f$ and the kernel of the group homomorphism $g: ...
- 27
0
votes
0
answers
26
views
Given a n number of digits and a sum x, how can I count the amount of ways you can obtain x from the sum of the digits? [duplicate]
My problem originally was "Given a number of two digits, in how many ways can you obtain 12 as the sum of its digits?".
I could find the solution by counting:
93: 9 + 3
84: 8 + 4
75: 7 + 5
...
- 207
1
vote
0
answers
48
views
Reproducing an ordered list of numbers from partial sums
Given a list of (not necessarily distinct) positive integers, $a=(a_1,...,a_n)$, can one reproduce the list (up to reversing the order, i.e. reproduce $(a_1,...,a_n)$ or $(a_n,...,a_1)$) from the ...
- 73
1
vote
1
answer
97
views
I derived a formula for $[x!]^\prime$. Is it correct?
The starting point was that $ \Gamma'(x+1)=\Gamma(x+1)\psi(x+1)$ where $\psi(x+1)=-\gamma+H_{x}$ . Hence $$ [x!]' = x!\biggl[-\gamma+\sum_{k=1}^{x}\frac{1}{k}\biggl]$$ For example $ [4!]' = 24[-\gamma+...
- 29
0
votes
2
answers
29
views
Double-checking work on finding gcd with Euclidean algorithm
I'm still learning the Euclidean algorithm and am hoping that someone can check my work on this problem:
Find $gcd(1001, 11)$
$1001 = 91(11) + 0 = 90(11) + 11$
$gcd(1001, 11) = 11$
- 59
-1
votes
0
answers
31
views
Determining a statement's truth value from given definitions [closed]
Let the predicates $P(x)$ and $Q(x)$ be defined on set $\{a, b, c\}$ as
\begin{array}{|c|c|c|c|}
\hline
x& a & b & c \\ \hline
P(x) & 1& 1&0\\ \hline
\end{array}
\begin{array}{|...
- 1
-1
votes
0
answers
19
views
A recursive problem [closed]
Let S_n denotes the number of n-length strings constructed using {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} having even number of "1"s. Show the relation between S_n and S_{n-1} for n ≥ 2
-1
votes
0
answers
29
views
Using the Pigeon Hole Principle [closed]
Using the Pigeon Hole Principle: At a university of 20,347 students, at least how many must share the same 4-digit pin number for their ATM card (assuming that each student has an ATM card)? Do we ...
0
votes
0
answers
50
views
Prove using induction over the positive integers
Prove using induction that the sum of the first step $n$ positive even integers is $n(n+1)$. In other words, prove using induction that $2 + 4 + 6 + … + 2n = n(n+1)$.
So, for my base case I have: the ...
-3
votes
0
answers
24
views
Using natural deduction prove the validity of the sequent [closed]
Use natural deduction to prove that the sequent is valid.
$$\big(P \to ((P \vee R) \to (Q \to T))\big), \big((P \vee R) \wedge (P \wedge Q)\big) ⊢ T$$
- 1
-2
votes
1
answer
50
views
Prove that $3(n^2 + 2n + 3) - 2n^2$ is a perfect square [closed]
I'm taking Discrete Mathematics in my major, and I'm stuck with this question. I tried making
$3(n^2 + 2n + 3) - 2n^2 = n^2$
where $n^2$ would be a perfect square, but I got left with $n=\frac{-3}{2}...
3
votes
2
answers
57
views
Does a bijective function exists behind every recurrence relation?
Consider these 2 questions where recurrence relations can be applied:
Q1) Given an (nxm) where n denotes rows and m denotes columns of a grid, find the number of unique paths ($a_{n,m}$) that goes ...
- 53
0
votes
2
answers
52
views
I will like to understand whether Case 1 or Case 2 will be applicable in this scenario
Given that set A contains 10 distinguishable objects and set B contains 6 distinguishable objects.
I will like to choose 2 objects from set A (with replacement): ${10 \choose 1}^2$
I will also like to ...
- 53
0
votes
0
answers
29
views
Laplace Transform the following equations
Could you help me with transforming these equations using Laplace Transform, please? I am new to this topic, it would be great if you explain the solution step by step.
$T*(dy/dt)+y=k*u$
$T*(dy/dt)+y=...
2
votes
1
answer
55
views
Are these formulas equivalent?
I am solving the problem from the textbook, and g) part states "There is exactly one person whom everybody loves." L(x, y) is "x loves y."
(1) The first and easiest solution is: $\...
- 45
-1
votes
0
answers
44
views
$P\Leftrightarrow q$ is equivalent to $(p\lor q) \Rightarrow (p\land q)$. Where $p$ and $q$ are propositions. [closed]
Discrete Mathematics
$P\Leftrightarrow q$ is equivalent to $(p\lor q) \Rightarrow (p\land q)$. Where $p$ and $q$ are propositions.
-1
votes
0
answers
52
views
Consultation regarding my Undergraduate Thesis [closed]
I would like to ask if I can study an undergraduate thesis regarding adjacency matrix of a special types of digraphs. I want to study their special properties if there is a relation between its ...
0
votes
1
answer
55
views
Evaluating conditional expectation [duplicate]
Let $X$ be the random variable "number of tosses of a fair coin required to get 3 consequtive heads". From this answer:
Let $A$ be the event "the first toss is a heads". Then we ...
- 177
1
vote
3
answers
134
views
Probability of certain ordering of people around a round table
Given $20$ people - $10$ males and $10$ females that are sitting around a round table.
Find the probability for which the order of the sitting is the following:
Between any pair that consists of $2$ ...
- 163
-1
votes
0
answers
26
views
Describe the distinct equivalence classes resulting from R. [closed]
A relation R is defined on Z by aRb if 5a−b is even.
(a) Prove that R is an equivalence relation. (I've already completed this section)
(b) Describe the distinct equivalence classes resulting from R.
...
- 1
0
votes
1
answer
93
views
Statement is true but contrapositive is false?
It seems that the contrapositive of a true statement is true. Consider the following:
$A,B,C,K\in \mathbb{N}$
$\exists A,B,C: A^K+B^K=C^K→K≤2$
Take the contrapositive: $$K>2→∀A,B,C:A^K+B^K<C^K∨...
0
votes
0
answers
57
views
In the bag there are $n \geq 1$ black balls.Every second replace white ball.Let $T$ be first time that all balls are white.Find expected value of $T$. [duplicate]
In the bag there are $n \geq 1$ black balls.At every second we randomly choose $1$ ball and replace it with white ball(even if ball that we took was white). Let $T$ be first time that all balls are ...
- 859
6
votes
1
answer
73
views
Pigeonhole principle, a sum question
$$\text{Let }\space S\subset\{1,2,\ldots,101\}\text{ s.t }\space|S|=52.\\\text{Prove that there exist different values }a,b,c\in S\text{ s.t }\\a+b=c.$$
That question appeared at my last Discrete math ...
- 339
0
votes
1
answer
91
views
"No integers $x$ and $y$ exist for $28x+7y=8$"
What is the logical structure of this statement?
No integers $x$ and $y$ exist for $28x+7y=8.$
I'm not sure, but I think the answer is
$$¬∃x\;∃y\;(x ∈ \mathbb Z ∧ y ∈ \mathbb Z ∧ 28x + 7y = 8).$$
- 11
4
votes
2
answers
33
views
Confusion Over The Definition of a Transposition Cipher
In our Discrete Mathematics class, the way the textbook introduces the transposition cipher is as follows:
As
a key we use a permutation $\sigma$ of the set $\{1, 2, \ldots , m\}$ for some positive ...
- 217
2
votes
1
answer
86
views
Finding rational points on a circle such that $X^2+Y^2=r^2=k \in \mathbb{Z}$
I am interested in finding rational points on a circle with radius $r$, such that $r^2=k$ is an arbitrary integer. I tried reducing the problem to the unit circle, and maybe use pythagorean triples as ...
- 922
0
votes
1
answer
29
views
Why does this application of Jacobsthal numbers defined by the recurrence relation: $a_n$ = $a_{n-1}$ + 2$a_{n-2}$ work in 2D tiles / grids?
Problem Statement: Find the Recurrence Relation for $a_n$, where $a_n$ is the number of ways to tile a (2xn) rectangular board with (1x2) or (2x2) pieces.
.
.
Note: A (1x2) piece can be placed either ...
- 53
-1
votes
0
answers
50
views
Prove $(2n+1)+(2n+3)+\ldots+(4n+1)=3n^2+4n+1$ with induction [closed]
Prove $(2n+1)+(2n+3)+\ldots+(4n+1)=3n^2+4n+1$ with induction.
Can you please explain how to solve this? I don't get how even to start this solution.
I don't even know what the base step is.
What does ...
- 11
0
votes
1
answer
50
views
Name of a particular probability distribution
Suppose the probability mass function $\{p_n\}_{n \geq 0}$ takes the form
\begin{equation}\label{eq:p*n_example}
p_n = \left\{
\begin{array}{ll}
n\,p_0\,r^n, & \quad \text{if}~ n \geq 1,\\...
- 2,372
0
votes
1
answer
48
views
Dahlin (Digital) controller design
I have designed a digital controller to control a DC motor. The motor has the following parameters:
...
- 129
-4
votes
0
answers
27
views
For any sets 𝐴,𝐵,𝐶 within a universal 𝑈 set, prove that 𝐴∪𝐵⊆𝐶 iff (𝐴∪𝐶)∩(𝐵∪𝐶)=𝑈? [closed]
Need help with this one, not sure how to prove this. For logic class, and need a proof using set rules.
- 37
0
votes
0
answers
23
views
What is the intersection of this relation?
If I have to find the intersection of a relation: which per my class’ notes is a family, then the intersection of a family is defined as such:
∩F= {x : for all A, A ∈ F → x ∈ A}
Now if I have to find ...
- 1
1
vote
2
answers
100
views
For any sets $A, B, C$ within a universal $U$ set, prove that $A\cup B \subseteq C$ iff $(A \cup C)\cap (B \cup C) = U$ [closed]
For any sets $A, B, C$ within a universal $U$ set, prove that $A\cup B \subseteq C$ iff $(A \cup C)\cap (B \cup C) = U$
Confused on how to do this, any help would be great.
Correction: Accidentally ...
- 37
0
votes
1
answer
33
views
At a party of only 2 people, will these 2 people actually know each other? - Pigeonhole Principle
I am aware of the proof - Given that there are $n$ people in a party $\left(~\mbox{where}\ n \geq 2~\right)$, there are $2$ people who know the same number of people.
Assuming:
knowledge is mutual so ...
- 53
0
votes
0
answers
21
views
Intuition on $P_3$ and $P_4$-free graphs
I am struggling to understand the structure of $P_3$ and $P_4$ graphs. Could someone provide me a few examples of graphs from each of these two classes?
- 63
0
votes
0
answers
32
views
What if infinity comes in the final matrix of the Floyd-Warshall algorithm?
I was solving a problem based on the Floyd-Warshall algorithm to find the shortest paths between vertices in a directed weighted graph. However, in the end, I am getting $\infty$ in the final matrix. ...
- 4,236
4
votes
3
answers
69
views
Proving $(a → (b → c)) ∧ (∼ c) ≡ (a → ∼ b) ∧ (∼ c)$ confusion.
I have the following statement that I want to prove:$(a → (b → c)) ∧ (∼ c) ≡ (a → ∼ b) ∧ (∼ c)$
I think I can prove this using the law of equivalences, however I also noticed that both statements, the ...
- 509
-1
votes
0
answers
33
views
Soviet/Russian Textbooks for Discrete Mathematics? [closed]
I have been on the hunt for some Soviet/Russian textbooks to supplement my university coursework. I found them to be able to fill in the gaps that my university coursework disregards. I have been ...
- 1
0
votes
1
answer
39
views
Stuck on divides relation proof
I'm stuck on even where to start for this, as I just started learning about the divides relation.
Prove: For integers r, s, t, and u, if r|t and s|u, then rs|tu.
...
- 59
0
votes
1
answer
49
views
Discrete math - Pascal
Let $n \in \mathbb{N}$ s.t. $n > 4.$ Prove the following is true:
Those kind of proofs which I have no idea where to start at. It seems more "tricky" to me and I would like to some ...
- 339
-2
votes
0
answers
28
views
surjective or not [closed]
Can anyone provide me with the proof that the following function is surjective
- 17
3
votes
3
answers
87
views
Expected number of elements for the first of $n$ many hash tables to be filled?
This is a generalization of the questions: question 1 and question 2.
There are $n$ many hash tables each of size $m$. Each turn a random element in one of the hash tables is filled. If the element ...
- 53
-1
votes
0
answers
18
views
Proving Contrapositive oin proof by Induction [duplicate]
In Inductive step in proof by induction we assume that P(n) is true and show that P(n+1) is true, that is proving the implication (P(n) -> P(n+1)).
My question is can I prove the contrapositive of ...
-2
votes
0
answers
30
views
Write each of the following sets in set-builder notation. [closed]
I tried to write this set in set-builder notation and was unable to do it. I would appreciate some help.
{$3,6,11,18,27,38,...$}
-1
votes
0
answers
26
views
Solving Linear Non-Homogeneous Recurrence - where F(n) contains an exponential (2^n) and a polynomial (n+3)
.
.
.
What is the reason as to why we are allowed to "solve it one by one" (highlighted in red) ? - where we go on to consider 2^n (green) and n+3 (pink) of F(n) seperately and then find ...
- 53
0
votes
0
answers
35
views
Counting the possible spot in matrixe such that filled by to such conditions
Problem:
filling $(2n+1)\cdot(2n+1)$ matrix with integers from $1$ to $(2n+1)^2$
each row be an increase sequence from left to right
each column be an increase sequence from top to bottom
Count the ...
- 1