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.

learn more… | top users | synonyms

1
vote
1answer
46 views

This question is from my discrete math. So far i have no idea how to solve it. Can anyone help me with this? [duplicate]

Let n be a prime. 1. If (G,+) has order 2n, prove that every proper subgroup of (G,+) is cyclic. 2. If (G,+) has order n^2, prove that (G,+) has a subgroup of order n.
1
vote
2answers
43 views

Is transitive closure defined uniquely?

I'm encountering questions where I'm required to find a transitive closure (and the questions seem to suggest that there is only one), but I probably don't understand something in the definition, ...
1
vote
2answers
73 views

Equivelence classes, how many there are, and how many elements they have.

I've been struggling to understand equivalence classes. Say I have a set T, the set of all binary strings, and the relation S on T = {(a,b) | length(a) = length(b)}. How would I write down the ...
1
vote
2answers
77 views

Proving isomorphism between graphs

If I'm asked to prove two graphs are isomorphic by constructing an isomorphism E.g for these two graphs if I start from $u_1$ I have an option to send $u_1$ to any of $v_1$ to $v_6$ and I start by ...
1
vote
1answer
182 views

What is reverse inclusion?

I'm learning about posets for the first time. What does it mean for a collection of sets to be "ordered by reverse inclusion"? Thank you.
1
vote
1answer
33 views

Power Set of a Power Empty Set

Find ℙ(ℙ(ℙ(∅))). I know that ℙ(∅) = {∅}. Then, ℙ(ℙ(∅)) = {∅, {∅}, {∅,{∅}}? so, ℙ(ℙ(ℙ(∅))) = {∅,{∅, {∅}, {∅,{∅}}}? Is it? Will it be ok if someone explain to me this concept?
1
vote
1answer
38 views

Summation Sequence

I'm supposed to use Gauss' law to find the summation of $6k$ from $k=5$ to $n$. Here is my work: $$6(5)+6(6)+6(7)+⋯+6(n)\\+6(n)+6(n-1)+6(n-2)+...+6(5)$$ When these are added together I get $2S=(30+...
1
vote
1answer
57 views

Showing $(¬P\wedge¬Q)\vee(¬P\wedge Q)\equiv¬P\wedge(¬Q\vee Q)$ by distributive law(s)

I want to show that $$(¬P\wedge¬Q)\vee(¬P\wedge Q)\equiv¬P\wedge(¬Q\vee Q)$$ by one of the two Distributivity Laws: $$P\wedge(Q\vee R)\equiv(P\wedge Q)\vee(P\wedge R)$$ $$P\vee(Q\wedge R)\equiv(P\vee ...
1
vote
2answers
57 views

Proof related to maximum degree of node in a graph

So I'm given this problem - Prove that in every graph with 25 vertices, in which holds that in every 3-subset of vertices, at least two of them are connected, there exists a node of degree at least 12....
1
vote
2answers
35 views

Sum with non unit increment

Let's consider the sum $$\sum_{i=4t+2} {\binom{m}{i}}$$. It's equivalent to the following $\sum_{s}{\binom{m}{4s+2}}$, but i got stuck here. How to evaluate such kind of sums? For instance, it's ...
1
vote
2answers
54 views

How to prove if $A \times C \subseteq B \times D \implies A \subseteq B$

My proof Given $(x,y) \in A \times C \implies x \in A$ and $y \in C$ since $A \times C \subseteq B \times D$ then $(x,y) \in B \times D$ then $x \in B$ and $y \in D$ since $x \in A$ and $x \in B$ ...
1
vote
1answer
39 views

Writing an equivilant expression in combinatorics

I need to write an equivalent expression to this : $$\sum_{i = 0}^{15} \binom{20}{i}\binom{30}{15 - i}$$ I'm thinking about $$\binom{50}{15} \cdot 2^{15}$$ Am I even close ? Thanks in advance !
1
vote
1answer
120 views

How many teams of $5$ players out of $15$ girls and $10$ boys can be formed with at least $2$ boys and $2$ girls [with complement]

How many teams of $5$ players out of 15 girls and 10 boys can be formed with at least 2 boys and 2 girls? The solution has to be with complement. This is related to: How many ways to assemble a team ...
1
vote
2answers
48 views

$F_{2n} = F_{2n-2}+2F_{2n-4}+\dots+n$ rigorous proof

Let $F_{n}$ be n-th fibonacci number($F_{0}$ = 0) and $g_{n} = F_{2n}$ if $n > 0$ $g_{0} = 1$. I want to prove that $g_{n} = g_{n-1}+2g_{n-2}+\dots +ng_{0}$. It's obviously seen from direct ...
1
vote
1answer
43 views

How many different committees with at least one man and woman and no spouses

In a building with 10 couples of man and woman, how many different committees of 6 people we can make such that it will have at least one man and at least one woman and no spouses? My attempt with ...
1
vote
4answers
45 views

Selection Sort Summation Simplification

I am trying to simplify the summation for selection sort. Starting out with: $$\sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}1$$ I am able to get: $$\sum_{i=0}^{n-1}n-i-1$$ However, I don't understand how to ...
1
vote
2answers
31 views

Need help understanding partial solution for sum $\sum_{1\leq i \leq j \leq n}(j-i)$

Let's consider the following sum: $$\sum_{1\leq i \leq j \leq n}(j-i)$$ Here are some progressions from my Discrete Math lecture: $$\sum_{1\leq i \leq j \leq n}(j-i)=\sum_{i=1}^n\sum_{k=0}^{n-i}k=\...
1
vote
2answers
74 views

Why does a set of m elements have 2$^m$ subsets?

Note: This example is from Discrete Mathematics and Its Applications [7th ed, prob 2, pg 576], shout out to @crash. I understand why $A \times A$ has $n^2$ elements(because every member of set $A$ ...
1
vote
2answers
43 views

Prove that $B = \bigcup\{A_\alpha \mid \alpha \in[1,2]\}$

I am working this question: Set $B = \{(x, y)\mid 1 \le x^2 + y^2 \le 4\}$, $A_\alpha = \{(x, y)\mid x^2 + y^2 = α^2\}$. Prove that $\bigcup\{A_\alpha\mid \alpha \in [1, 2]\} = B$. because this ...
1
vote
1answer
208 views

How to make sure Player 2 always wins in 23 NIM game?

Game begins with a pile of 23 toothpicks. Players take turns, withdrawing either 1, 2, 3 toothpicks at a time. The player to withdraw the last toothpick loses the game. We need to make player 2 to ...
1
vote
3answers
68 views

Solving recurrence equation with generating indices of positive indices [duplicate]

I don't know how to solve recurrence equation with positive indices like $$a_{n+2} + 4a_{n+1}+ 4a_n = 7$$ by generating functions. How to solve such kind of problems.
1
vote
1answer
182 views

Prove that every minimal edge cut in a simple connected graph $G(V,E)$ is even, then $G(V,E)$ has no odd degree vertex.

I need to prove/disprove the following statement -- If every minimal edge cut in a simple connected graph $G(V,E)$ is even, then $G(V,E)$ has no odd degree vertex. I am a bit confused about one of ...
1
vote
2answers
84 views

Fourier Series of $\frac{\sin(x)}{x}$

Good afternoon! My teacher of signals and systems put in my test that calculate the Fourier coefficients for the function $f(x) = \frac{\sin x}{x}$. But ... How I can do? I know that the function is ...
1
vote
1answer
56 views

Prove $R$ follows from premises $(\lnot R\rightarrow\lnot Q),\;(P\lor Q,),\; (\lnot(P \lor T))$

I'm preparing for an exam and we weren't given an answer sheet. I'd like to know if my reasoning for the given conclusion is correct? Premises: $(\lnot R) \rightarrow (\lnot Q),\;\; (P \lor Q),\;\; \...
1
vote
2answers
32 views

Express this with an existential quantifier and universal quantifier

Can someone verify I'm doing this correctly? English: No Humans live in the Ocean H(x): x is a human O(x): x lives in the ocean ...
1
vote
2answers
50 views

Can someone verify the reasoning of why these two congruences are equivalent?

I've wondered why two congruences like $x\equiv81\pmod {53}$ and $x\equiv28\pmod{53}$ were equivalent. I've come up with this proof. I am not sure if this is how you prove it though I know that $x\...
1
vote
2answers
70 views

Seeking combinatorial proof for $F_{n+1} -1=\sum\limits_{k=0}^{n-1} F_k$

In order to give a combinatorial proof for this equation, we need to find what these two count for. But I don't know what they count for and how I can pivot the RHS to show that it actually counts ...
1
vote
1answer
382 views

How to prove connecting 3 dots to three squares without overlap is impossible? [duplicate]

I was given this problem to solve by a professor who promised an A if anyone could solve it. I'm nearly certain it is impossible, because at some point you have too many vertices and inevitably box ...
1
vote
3answers
92 views

fast modular exponentation doubt

Compute 3^1048576 mod 7 using fast modular exponentiation. I found that 1048576=2^20 so i got 3^(2^20) mod 7 fast modular algorithm is to reduce the powers. Please guide me the initial steps to ...
1
vote
2answers
32 views

Induction and Statements

I'm having trouble with induction in my discrete math course. We are given a statement we know (∀k)(P(k)⇒P(k+2)), where k is an element of N. After that we have a series of statements, I'll give one ...
1
vote
1answer
103 views

Find the coefficient of $x^{15}$ [closed]

How do you find the coefficient of $x^{15}$ from $x^{3}$$(1-2x)^{10}$? Thank you.
1
vote
1answer
74 views

How many bit strings oft length k have more than one 1?

The question seems rather simple, but I am not able to get a closed formula. e.g. for k=2 it is 1 (11), for k=3 it is 4 (111,101,110,011) I thought that it maybe could be $\frac{1}{2} \cdot 2^k $ ...
1
vote
2answers
67 views

Propositional Logic : Absorption - Why is it so?

Why is the Absorption Law of Propositional Logic so ? p $\lor (p \land q) \equiv$ p Would appreciate an intuitive explanation and not one using a Truth Table
1
vote
1answer
34 views

The $5\times 5$ matrix whose $(i,j)$th entry is $1$ if $j$ is a multiple of $i$, and $0$ otherwise

The $5\times 5$ matrix whose $(i,j)$th entry is $1$ if $j$ is a multiple of $i$, and $0$ otherwise. I know that I’m supposed to show the work I’ve done, but I just have no idea what to do with this. ...
1
vote
1answer
56 views

Find Planar Graph fromVertices and Faces

Could you find a 3-Regular Connected Planar Graph on 10 vertices with 8 faces? If so, explain carefully. I dont know what does regular mean. I think that 3-connected graph on 10 vertices with 8 ...
1
vote
2answers
85 views

Combinatorics - too much combinations ? where is my mistake?

Problem : A person has 7 friends . How many combinations exists so that he would be able to invite different groups of ...
1
vote
1answer
129 views

I'm Confused About Size, Combinatorial Classes and Counting Sequences

My Teacher tried to explain these concepts like so: My Problem I'm quite confused by the definition given. How can "the size" which is a function mapped from our countable set A to all the non-...
1
vote
1answer
155 views

Asymptotic behaviour of a recurrence relation - How to solve

I'm going over a chapter in recurrence relations in preparation for job interviews and came across the following. I'd like to gain some better understanding of how to solve such a question. Find a ...
1
vote
2answers
76 views

$N=2^7\cdot3^5\cdot5^6\cdot7^8$. How many factors of $N$ are divisible by $50$ and not by $500$?

My attempt: $50=5^2 \cdot 2$ $500=5^3 \cdot 2^2$ Factors divisible by $50=5 \cdot 7 \cdot 6 \cdot 9=1890$ Factors divisible by $500=4 \cdot 6 \cdot 6 \cdot 9=1296$ So, the answer is $=1890-1296=...
1
vote
1answer
56 views

Reference request: comprehensive handbook of combinatorial formulae

I am searching for an handbook that collects a comprehensive list of formulae in combinatorics. Could you point out one such reference?
1
vote
2answers
39 views

Permutations and Combinations Doubt

Question: How many words, with or without meaning, can be made using the letters of the word DEBOTRI such that there are always two letters between D and E? I got $4 \times 2 \times 5P_5 = 960$, ...
1
vote
3answers
135 views

Distributing $N$ distinct objects in $R$ distinct boxes when order matters

There are $P(r+n-1,r-1)$ ways to distribute $n$ objects in $r$ boxes when the order of objects in each box matters. I tried to find out why but I failed. when the order of objects in each box doesn't ...
1
vote
2answers
111 views

Connections of theory of computability and Turing machines to other areas of mathematics

The question is quite straightforward: Could you point out some reference papers that highlight (in a way that is fairly accessible) the connections between (1) theory of computability, algorithms, ...
1
vote
2answers
112 views

Find the transitive closure of a relation

Let the relation $R=\{(0,0),(0,3),(1,0),(1,2),(2,0),(3,2)\}$ Find the $R'$ the transitive closure of R. I honestly don't understand this question at all. Am I being asked to first find $R'$ ...
1
vote
1answer
72 views

Simple connected bipartile graph $G=(V,E)$ with $10$ vertices of degree 3 cannot be a planar graph

Why a simple connected bipartile graph $G=(V,E)$ with $10$ vertices of degree 3 cannot be a planar graph? In my notes, it says it is easy and leave as an exercise with a hint which want us to show the ...
1
vote
1answer
125 views

Verification of a proof that the difference of two odd integers is not odd

Prove or disprove the difference of two odd integers is odd. Here was my answer: $m = 2s+1$ $n = 2t+1$ $m - n = (2s+1) - (2t+1)$ $= 2s - 2t$ $= 2(s-t)$ I then wrote the following: Since $...
1
vote
2answers
185 views

Express a Proposition In Formal Logic

I am doing a question where I have to express: There is no largest prime number, in formal logic. This is the solution given: Of course this is a true statement, so it could be expressed by the ...
1
vote
6answers
78 views

Solving recurrence relations?

How do I solve $$ a_{n} = a_{n-1} + n, a_{0} = 1$$?? I solved for n=1 thru n=5: 1: 2 = a0 + 1 2: 4 = a0 + 1 + 2 = a0 + 3 3: 7 = a0 + 3 + 3 = a0 + 6 4: 11 = a0 + 6 + 4 = a0 + 10 5: 16 = a0 + 10 + 5 = ...
1
vote
1answer
36 views

John sold some books at $24 each, and used the money to buy some concert tickets…

John sold some books at 24 dollars each, and used the money to buy some concert tickets at $50 each. He had no money left over after buying the tickets. What is the least amount of money he could have ...
1
vote
1answer
71 views

Existence of infinite subsequence of trees with a subtree contained in the sequence

Assume a statement: For every infinite sequence of rooted trees $\{T\}_{i=0}^\infty$ there is an index $j\geq0$ such that there are infinitely many trees in $\{T\}_{i=0}^\infty$ which contains $...