# 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
Filter by
Sorted by
Tagged with
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
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
41 views

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
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
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).$$
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
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 ...
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 ...
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
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,\\...
48 views

### Dahlin (Digital) controller design

I have designed a digital controller to control a DC motor. The motor has the following parameters: ...
• 129
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.
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 vote
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 ...
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 ...
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?
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
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
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 ...
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. ...
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
28 views

### surjective or not [closed]

Can anyone provide me with the proof that the following function is surjective
• 17
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 ...
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 ...
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,...$}
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 ...