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.

Filter by
Sorted by
Tagged with
-1 votes
0 answers
35 views

How to prove an inequality by induction [closed]

I am having difficulty proving this by induction: $$\sum_{k=1}^n \frac{k}{k^2 +1} \le \frac{n}{2}$$ Any tips on how to approach the problem? Thank you!
elguero's user avatar
  • 25
-1 votes
0 answers
10 views

If $F(x, y, z) = z(x' + y'z)$, what is the complement of $F$? You need to simplify it as much as possible.

If $F(x, y, z) = z(x' + y'z)$, what is the complement of $F$? You need to simplify it as much as possible. Also have a second question: Simplify the function $F(x,y,z) = y(x' + y')$ by using ...
Alothinson's user avatar
3 votes
3 answers
66 views

Number of binary strings of length $56$ vs number of permutations of English alphabet

This is exercise $1.2$ in Nicholas Loehr's book "Combinatorics". Which is larger: the number of binary strings of length $56$, or the number of permutations of the English alphabet ($26$ ...
pyridoxal_trigeminus's user avatar
0 votes
0 answers
15 views

Let $n$ be the number of vertices in a graph. Prove that for every $n \equiv 0,1 \pmod 4$ there exists a self-complementary graph of order $n$. [duplicate]

Our professor told us to do it by induction, for the cases $n = 0 \pmod 4$ and $n = 1 \pmod 4$. We know, that for the case $n=4$, the only self-complementary graph is $P_4$ which is a path of four ...
anon's user avatar
  • 625
1 vote
2 answers
44 views

Explain the double sum step by step

I'm looking at the following: But when I try to reproduce the result, I get: For $n=1$, $$\sum_{i=0}^{n} \sum_{j=0}^{i} (i+1)(j+1)$$ $$= \sum_{i=0}^{n} (i + 1) \cdot \sum_{j=0}^{i} (j+1)$$ $$= \sum_{...
Darvid's user avatar
  • 83
-3 votes
0 answers
18 views

The language of words in {0, 1} ∗ that start exactly with 11, end exactly with 00 and in the middle have substring of ones, zeroes with even length. [closed]

The language of words in {0, 1} ∗ that start exactly with 11, end exactly with 00 and in the middle have a substring of ones and zeroes with even length.(Tip: 0 is an even number.) Accepted: 1100, ...
frvar's user avatar
  • 1
0 votes
0 answers
42 views

Least number of years to make unique pairs

Here is the question: we want to hold a math contest for 8 groups, giving each group 6 questions with the following condition : no group has more than one question from each year and each possible ...
itspaspas's user avatar
-1 votes
0 answers
11 views

How to use resolution to solve compound propositions? [closed]

How to prove this step by step using resolution to show that the compound proposition (p ∨ q) ∧ (¬p ∨ q) ∧ (p ∨ ¬q) ∧ (¬p ∨ ¬q) is not satisfiable?
Zainab Alturaiki's user avatar
-4 votes
0 answers
21 views

How do I find the element with the maximum order in a ring? [closed]

I have a ring of deductions modulo 360. The maximum order of an element in it is 12. How do I find an element with this order? Please Help Me
Sindi Hall's user avatar
2 votes
1 answer
75 views

Summing the heights of every simple non-left-moving paths $(0,0)\to (n,m)$

There is a challenging question assigned regarding Counting. here is the question: Consider a square lattice $(\mathbb{Z}_{\ge 0}^2)$ with point $A$ on its bottom left (the origin) and point $B$ on ...
itspaspas's user avatar
-1 votes
0 answers
27 views

We have a tree T on n vertices. Prove that the centre of the tree T is isomorphic to a complete graph on 2 vertices if and only if diam(T)=2*rad(T)-1

I know that the tree $T$ has $n-1$ edges, one component (it is connected), and does not contain a cycle (that is, from each vertex to each there is a single path, or between every two vertices of the ...
Zam's user avatar
  • 17
-2 votes
0 answers
60 views

Proof of a formula to calculate $1^p+2^p+\dots+n^p$ with induction [closed]

How can I prove this formula with induction? $$1^p+2^p+\dots+n^p \simeq \frac{n^{p+1}}{p+1}$$ I know that the formula is correct for $p = 1, 2, 3$. But I can't prove it for $p = k + 1$ using $p = k$....
Web program's user avatar
0 votes
1 answer
29 views

In how many ways we can arrange $n$ men and $m$ women in a circle such that between every $2$ men we can have at most $m -1$ women?

First, this not a question from any academic resource, I thought about it and I'm just wondering if it can be solved. The question : In how many ways we can arrange $n$ men and $m$ women in a circle (...
DanielMa's user avatar
  • 115
-1 votes
0 answers
52 views

Count all possible states of a binary sequence [closed]

The question is counting all possible binary sequences which have exactly 5 pieces of 00, 3 pieces of 01,3 pieces of 10 and 3 pieces of 11. I actually found that the number of bits should be 15 and ...
Mehran Hashemi's user avatar
-1 votes
2 answers
35 views

Finding formula for sequence [closed]

Find an explicit formula for a sequence of the form $a_1$​, $a_2$​, $a_3$​,… with the initial terms given below. $\frac{1}{5}$, -1, $\frac{1}{6}$, -$\frac{1}{2}$, $\frac{1}{7}$, -$\frac{1}{3}$, $\frac{...
Grant Wu's user avatar
0 votes
0 answers
28 views

Concrete Mathematics — Avoiding Clairvoyance to the Towers of Hanoi Simplification

In Concrete Mathematics (Graham, Knuth, Patashnik), to prove that the Tower of Hanoi problem resolves to $T_n-1$ from: $T_0 = 0$ $T_n = 2_{n-1} + 1$ for $n > 0$ we add one to both sides of the ...
hideme's user avatar
  • 65
-2 votes
0 answers
22 views

Without using truth table prove logic

¬(p⟺q) is logically equivalent to (p∨q)∧¬(p∧q) is also equivalent to (p∨¬q)∨(¬p∧q). Please help me to solve this
M.Mohana Prasath's user avatar
1 vote
2 answers
75 views

$2n$ knights around a table with namecards, is it possible that for every rotation there is exactly one person with a correct namecard?

I need help with the following puzzle: Consider a round table which hosts $2n$ knights. At each seat, there is a namecard of one knight. The knights don't necessarily sit in front of their own ...
Steve's user avatar
  • 174
0 votes
0 answers
36 views

Application of Permutation

I have this problem below: In a row of six houses (numbered, in order, 1–6) live six married couples, each consisting of a woman and a man, a couple in each house. Each of the women also has (exactly) ...
user1295782's user avatar
0 votes
0 answers
48 views

How can I assert that two sets are subsets of eachother given that they are equal? [closed]

While proving " $A\setminus (A\setminus B) = A\cap B$ ", I reached the point of $A\cap B = A\cap B$, however in order to determine the sets are equal, I have to find a way to show that the ...
Andre Athari's user avatar
-1 votes
0 answers
25 views

Let $I$ be the collection of all involutions (for all $n \geq 0$). Find the EGF for $I$. [closed]

A permutation $\pi$ of $[n]$ is said to be an involution if its cycle decomposition consists of only $1$- or $2$-cycles. Let $I$ be the collection of all involutions (for all $n \geq 0$). Find the EGF ...
Beehunter7's user avatar
2 votes
1 answer
61 views

In how many ways it is possible to take out balls from the basket , such that will take out at least one from each color?

The question: In a basket there are $20$ black balls, $15$ white balls and $18$ red balls. All balls with the same color are identical to each other. In how many ways it is possible to take out balls ...
DanielMa's user avatar
  • 115
1 vote
0 answers
64 views

Proof by induction that $3^{2n}-1$ is divisible by 8. [duplicate]

Proof by induction Let the property $P(n)$ be the sentence $$ 3^{2n}-1 \text{ is divisible by 8} $$ Base case: Let $n = 0$ and we have $$ 3^{2 \cdot 0} - 1 = 3^0 - 1 = 1 - 1 = 0 $$ and $0$ is ...
Jacob's user avatar
  • 11
3 votes
1 answer
109 views

Find two coins of weight a, among n coins, where n-2 coins are coins of weight b

Task: Among the n coins there are exactly 2 coins of weight a, and exactly $n − 2$ coins of weight $b, a < b$. It is allowed to compare the weight of any two coins in one turn (there are three ...
Peter Griffin's user avatar
0 votes
1 answer
32 views

Maximum independent set of a residual graph

Given a graph $G$ and a maximum independent set (MIS) $I$, can we comment on the size of a maximum independent set of the residual graph $G\setminus I$? Note that $G\setminus I$ denotes the induced ...
codeR's user avatar
  • 1
-4 votes
0 answers
27 views

Prove that the given equation in the image is a boolean algebra.

This question is about boolean algebra. But I can't identify it. Prove that $\langle S_{30}, D \rangle$ is a Boolean algebra.
XYZ4114's user avatar
2 votes
1 answer
184 views

Number of possible relations with following restrictions | Discrete Mathematics

I am new to math. stack exchange, I am really not sure how I am supposed to ask this but I need a logical explanation and a way to logical way to approach questions like these. I tried doing it myself....
Alwaysneedhelp's user avatar
0 votes
0 answers
47 views

Which element in $\Bbb Z_{2024}$ corresponds to the triple of numbers $(1,3,22)$ in the product $\Bbb Z_8 \times \Bbb Z_{11} \times \Bbb Z_{23}$? [duplicate]

I know all 8 idempotents in $\Bbb Z_{2024}$ are: $1265, 760, 1288, 737, 1496, 529, 0, 1$. I hope this helps somehow. Please help me, this question failed me in the exam (((
Sindi Hall's user avatar
0 votes
1 answer
63 views

Learning effective

today I got my midterm test result of Discrete math (It can only raise the grade). I got 63, which is above the average, but still I don't feel comfortable with that. I have 7 courses in the semester, ...
miiky123's user avatar
  • 109
2 votes
2 answers
76 views

How to prove the existence of this progression? Struggling with a BDMO problem.

This problem is from Bangladesh Mathematical Olympiad $2023$, The problem statement is as follows- Prove that there is sequence of $2023$ distinct positive integers such that the sum of the squares of ...
Sonia Sultana's user avatar
0 votes
2 answers
119 views

Exponential generating function of the sequence $1,0,1,0,\dots$

I'm currently learning exponential generating functions and am working on a problem that needs me to find the corresponding closed form expression to a given sequence. I've been given the sequence $1,...
Gyro's user avatar
  • 3
-1 votes
1 answer
67 views

Let $a_{n}$ be the sequence defined inductively by $a_{1} = 2$ and $a_{n+1} = 1/2 ( a_n + 2/a_n)$. Prove this sequence is decreasing [duplicate]

I have already inductively proven that $a_n∈[1,2]$ and found that $(a_{n})^2⩾2$ for all $n ∈ N$ I think I need to prove that the sequence converges to the greatest lower bound root 2 but i havent a ...
mathmath's user avatar
0 votes
0 answers
36 views

Sequence of degrees of a graph with two colors

With respect to the graph Another concept central to an understanding of fractional isomorphism is that of the iterated degree sequence of a graph. Recall that the degree of a vertex $v\in G$ is the ...
Tomais's user avatar
  • 509
-1 votes
1 answer
35 views

Proof: If connected graph G has only one cut-vertex, then every longest path contins the cut vertex.

This is one of exercises from my uni's Discrete math problems. (Non-mandatory) And the job is to either found a counterexample or prove it. I considered approaching this problem using proof by ...
runtotherescue's user avatar
-1 votes
1 answer
85 views

Show that ${n^n}^{n}>n(n!)((n!)!)$ where n is a positive integer greater than or equal to $3$.

Show that ${n^n}^{n}>n(n!)((n!)!)$ where n is a positive integer greater than or equal to $3$. My attempt: Rewrite ${n^n}^{n}=n^{n} n^{n} … n^{n} n^{n} $ and $n(n!)((n!)!)=n(n)(n-1)(n-2)…1(n!)(n!-1)...
Chanhyuk Park's user avatar
0 votes
0 answers
52 views

How do you prove the Multi-Factorial formula.

For $n\in\mathbb{Z}_0,m\in\mathbb{Z}^+$, $n!_m=n\underbrace{!\cdots!}_{\text{m}}=\displaystyle\prod_{k=0}^{\lceil{n/m-1}\rceil}(n-km)$ Using this formula, we can indeed find the m-th multi factorial ...
sakura's user avatar
  • 11
0 votes
0 answers
26 views

Union of Sigma Fields (Borel)

Let $\Omega$ $= \mathbb R$, $A = [0,1]$ and $F_A$ be the $\sigma$ field generated by $A$. I believe that this means that $F_A$ is the sigma field generated by all open intervals of $A$. Is this ...
adisnjo's user avatar
  • 91
0 votes
0 answers
43 views

Software for finding a closed formula from a list of triples of positive integers

Suppose we have a finite list of $n$ triples of positive integer numbers, as: $$ \mathcal{L}=\{(a_{i1},a_{i2},a_{i3}):a_{ij}\in \mathbf{N}\setminus\{0\}, \text{ for } j=1,2,3\}_{i=1,\dots,n}.\ $$ Is ...
Hola's user avatar
  • 151
4 votes
3 answers
122 views

How many natural numbers $a\le100$ are there such that $a=[\frac a2]+[\frac a3]+[\frac a5]$, where [.] represents the greatest integer function?

A natural number $a$ is selected from the first $100$ natural numbers. The probability that $a=[\frac a2]+[\frac a3]+[\frac a5]$, where [.] represents greatest integer function, is $\frac mn$ where $m,...
aarbee's user avatar
  • 8,226
-1 votes
2 answers
61 views

Let $a, b, c \in \mathbb{Z}$. Show: If $a \shortmid b$ and $a \shortmid (b+c),$ then $a \shortmid c.$ Hint: $c = (b+c)-b.$ [closed]

I'm working on my discrete math homework, and I come to this problem: Let $a, b, c \in \mathbb{Z}$. Show: If $a \shortmid b$ and $a \shortmid (b+c),$ then $a \shortmid c.$ Hint: $c = (b+c)-b.$ I've ...
Hayden's user avatar
  • 99
-1 votes
1 answer
63 views

Solve the recurrence relation $a(n) = 2a(n/2) +n $ with $a(1) = 1$ [closed]

I tried doing the first few calculations. ...
nate3535's user avatar
0 votes
1 answer
152 views

Which pairs can go on infinitely?

Given a pair of different integers $a$ and $b$ and operation: $$(a,b) \rightarrow \begin{cases} (a-b,2b), &\text{for}\; a>b \\ (2a,b-a), &\text{for}\; b>a \\ \text{stop}, &\text{for}\...
4-4's user avatar
  • 13
1 vote
2 answers
152 views

Birthday problem with shared birthdays among males and female students

There are $m$ male and $f$ female students in a class (where $m$ and $f$ are each less than 365) What is the probability that a male student shares a birthday with a female student? I have attempted ...
Starlight's user avatar
  • 1,570
0 votes
1 answer
92 views

Sum of the fifth powers of the first n numbers

Prove that $1^5+2^5+\dots+n^5= \dfrac{n^2(n+1)^2(2n^2+2n-1)}{12}$ I think we use induction to solve this problem. Base case: When $n = 1$, we have $1^5 = 1$. The formula gives $1$, which is correct. ...
Nurkhaji's user avatar
0 votes
1 answer
42 views

about logical equivalence

so the question is like this: Define a new logical connective □ as p □ q ≡ p → ∼ q. Use the Laws of Logical Equivalence, the equivalence of → to a disjunction, and the definition of □ to show that (p □...
Brynn's user avatar
  • 9
0 votes
0 answers
42 views

Is there a way to find if there relationship of numbers

I have a challenge. This may be little tricky or even not possible but wanted to check if anyone has any thoughts on this? PS : This question is in general and not related to only to R. May be I can ...
manu p's user avatar
  • 111
0 votes
0 answers
52 views

Prove that will all ways of distribution, we need to use at least 10 colors. [closed]

We take 30 marbles and distribute them into 5 boxes (each box may have zero marbles). a) Ask how many ways there are to distribute? (I think this is the Euler's candy division problem) b) After the ...
Kii's user avatar
  • 167
0 votes
0 answers
57 views

Generalization of Pólya Enumeration Theorem by de Bruijn

I need help with this question. Suppose that G is a group acting on a set of objects S, and that C is the set of colorings of elements of S using the colors in a set R. Let $\overline c$ denote the ...
ssd500's user avatar
  • 1
1 vote
2 answers
104 views

How many times is the light bulb turned on?

A light bulb is automatically turned off for 21 secs. Next, it lights up automatically for 15 secs. Once again, it is automatically turned off for the following 21 secs. The process keeps repeating. ...
x89's user avatar
  • 189
1 vote
0 answers
80 views

what math concept would this be called?

Assume that I am trying to use reference values to evaluate an analysis of an unknown sample in order to determine what the nature of the sample is and the attribute value is an 8-bit string of binary ...
Sam Levi's user avatar

1
2 3 4 5
656