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

0
votes
2answers
37 views

what is the difference between linear transformation and affine transformation?

Recently, I am struglling with the difference between linear transformation and affine transformation. Are they the same ? I found an interesting question on the difference between the functions. But ...
0
votes
2answers
48 views

Find equivalence relations and classes for a given set

Find how many equivalence relations on the set: $\{1,2,3,4,5,6,7\}$ contain the set $\{\langle6,4\rangle,\langle4,7\rangle,\langle3,3\rangle,\langle5,1\rangle\}$ And do not contain the set ...
5
votes
1answer
47 views

Lattice Paths problem

I was assigned to determine the number of "lattice paths" that are in a 11 x 11 square. Recalling that I can only go upwards and rightwards, here is my approach: Note: The red square is the ...
2
votes
0answers
21 views

Need a hint with permutations and pigeonhole-principle question

let $\pi_1,\pi_2,\pi_3\in S_{28}$. Help me prove that there are two sub-sequences of 28 with length 4 $i_1< i_2 <i_3<i_4,\ and\ \ j_1<j_2<j_3<j_4$ so that $\pi_q(i_n)=\pi_p(j_n)$ ...
0
votes
2answers
67 views

Need hint about with pigeonhole principle problem

$a_i$ and $b_i$ are two sequences with $2n$ elements where $\forall i:\ 1\leq i\leq 2n\implies\ 1 \leq a_i , b_i \leq n$ . I need to show that there are two subsets of indexes $I,J\subset [2n]$ so ...
1
vote
1answer
33 views

Counting review(permutations); Discrete Structures [closed]

You are given $6$ distinct books and $5$ identical blocks of wood. How many ways are there to arrange these books and blocks in a straight line? (a) $\dfrac{11!}{4!}$ (b) $\dfrac{11!}{5!}$ (c) ...
0
votes
1answer
31 views

Sets of irrationals whose square contains a rational

Let $S$ be a subset of the irrationals. Also, lets assume that $S$ has infinitely many elements. My very general question is, under what non-trivial conditions does there exist an element $x\in S$ ...
0
votes
0answers
53 views

The cube of at least one irrational number is rational

I am supposed to prove the statement above. Here is what I have so far Suppose that the cube of at least one irrational number $n$, is rational. By definition of rational, there exists ...
2
votes
1answer
23 views

Special Binary Relations/ Empty Relation, Universal Relation And identity Relation?

The universal relation U = A × A. (Correct me if I'm Wrong). I believe that the Universal Relation is an Equivalence Relation The empty relation E = ∅. From my understanding, a Empty relation on a non ...
2
votes
1answer
27 views

language generated by a grammar

I was wondering if someone could look over this problem set and tell me if my answers are wrong and if so how. Thanks in advance Let V = {S,A,B,a,b} and T = {a,b}. Find the language generated by the ...
2
votes
1answer
29 views

Prove $\sum_{r=0}^n 6r=3n(n+1)$ using induction

Prove$$\sum_{r=0}^n 6r=3n(n+1)$$using Induction I'm a little confused as to how I would calculate the latter
0
votes
1answer
44 views

In how many ways can you distribute 18 fruits among 18 pirates so that each gets 1 piece of fruit?

Assume you have 5 oranges, 7 limes, and 6 lemons. How many ways can you distribute these among 18 pirates so they can each get 1 fruit and avoid scurvy? (This is a homework problem) My first ...
2
votes
1answer
83 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: ...
0
votes
1answer
22 views

Solving a nonhomogeneous reccurence relation

I have a nonhomoheneous recurrence to solve $a_{n+3} - 2a_{n+2} - 5a_{n+1} + 6a_n = 2^n + n, n>=0$ I've already managed to get solution for the homogeneous part $a_n=u1^n + v3^n + w(-2)^n$ but ...
0
votes
3answers
36 views

Solve for the unknown

$31x-21^{21} \equiv 21+31^{31} \pmod 5$ The provided answers are: $$ \left\{ 3,8,13,18,... \right. $$ but I don't know how to get there. Can someone walk me through this please?
0
votes
2answers
19 views

phrase structured grammar

find a phrase structure grammar for each of these languages: the set consisting of the bit strings 10, 01, and 101 the set of bit strings that start with 00 and end with one or more 1's the set of ...
0
votes
2answers
18 views

Language of Grammar

Let $G = (V,T,S,P)$ be the phrase structure grammar with $V = \{0,1,A,S\}$, $T=\{0,1\}$, and a set of productions $P$ consisting of: $S \to 1S$ $S \to 00A$ $A \to 0A$ $A \to 0$ What is the ...
0
votes
0answers
15 views

Minimal Cover across Functional Dependencies

I'm attempting to compute the minimal cover for the functional dependencies F { A->B AFE->GHI ACEF->JKMEB BD->LNB ACFEBD->GIK } ...
0
votes
2answers
47 views

Proof for consecutive integers

Prove that if $n$ is an odd integer, $n^3$ is the sum of $n$ consecutive integers. I'm confused on how to prove something with consecutive integers.
1
vote
2answers
18 views

Describes Equivalence Classes

Let $R$ be the relation on the natural numbers defined by $(a,b)\in R$ if and only if $2\mid(a+b)$ I already proved this was an equivalence relation, but how do I determine the number of equivalence ...
0
votes
1answer
28 views

Greatest Common Divisor Proof

Show that if $r_k = q_i r_{k+1} + r_{k+2}$, then $\gcd(r_k,r_{k+1}) = (r_{k+1},r_{k+2})$
0
votes
1answer
28 views

inclusion-exclusion principle - possible ways

I am trying to solve out this problem. I have a square net and I need to get from the point $(0,0)$ to $(15,20)$, but I can only go up or to the right, and I mustn´t go through $(5,6), (10,9), (7,13)$ ...
1
vote
1answer
23 views

Power set statement validity

If A is a set and P(A) is the power set of A. Why is the following statement is true: ∃C[(C is a set) ∧ (∀A[A is a set → C ∈ P(A)] )]
0
votes
4answers
41 views

Induction Proof with a $\neq$ 1 [duplicate]

For $a \neq 1$ and $n>0$, $(1-a^{n+1})/(1-a)=1+a+a^2+...+a^n$ How do you prove this by induction?
0
votes
3answers
31 views

A test contains 10 T/F questions, 5 must be marked true, and 5 false…

A quiz consists of ten true/false questions. a) In how many distinct ways can the quiz be completed if no answers are left blank? b) In how many ways can the quiz be completed if five questions must ...
1
vote
1answer
31 views

Calculating connected components in an undirected graph

Suppose that we have a graph $G$ with $n$ vertices and $n-k$ edges, such that it does not include any cycles. How many connected components does it have?
0
votes
2answers
37 views

floor function problem

Prove that if $m$ and $n$ are positive integers, and $x$ is a real number, then: $$\left\lfloor\frac{\lfloor x\rfloor+n}m\right\rfloor = \left\lfloor\frac{x+n}m\right\rfloor$$
1
vote
1answer
22 views

How many different vertical arrangements are there of 10 flags if…?

How many different vertical arrangements are there of 10 flags if 4 are white, 3 are blue, 2 are green and 1 is red? I know the answer is 12 600 but am not sure how to get to it. Could someone walk ...
0
votes
3answers
44 views

Prove/disprove: If $n\in \mathbb N$ with $n>2$ not prime, then $2n + 13$ is not prime.

Prove/disprove: If $n\in \mathbb N$ with $n>2$ not prime, then $2n + 13$ is not prime. From the context in which this question was set, I believe I have to prove/disprove it using ...
1
vote
1answer
45 views

discrete maths-combinatorics

**Hi..i have a doubt in permutation and combination.. i already know permutation is an a method of arrangement of a set of n objects in a given order that means in permutation order of objects is ...
0
votes
1answer
17 views

What is a Euclidean Graph? Can edges be negative in a Euclidean Graph?

To my understanding a graph is Euclidean if each edges connecting two vertices represents the distance between those two vertices, where the vertices are points in a plane. This is all I found in the ...
1
vote
1answer
18 views

Prove that a planar bipartite graph on n nodes has at most 2n−4 edges.

I know that we have to use Euler's formula ( v−e+f=2) but I don't understand how f = e/2.
0
votes
0answers
21 views

prove strong induction implies weak induction

So trying to prove: $[s(n_0)\wedge s(n_1)\wedge\cdots \wedge s(n_k)\wedge\forall_n[s(n-k)\wedge s(n-k+1)\wedge\cdots \wedge s(n-1)\wedge s(n)\rightarrow s(n+1)]\Rightarrow \forall_{n_0\le n}s(n)]$ ...
1
vote
0answers
38 views

Help me finding closed form of sum of 4 elements

I've been reading Wilf's Gfology and tried to calculate some complicated sum Let's say $0<k \le n$ $$f(k,n) = \sum_{i} i(-1)^i \binom{n}{i} \binom{i}{k-i} $$ I will write down my calculations, i ...
-1
votes
3answers
22 views

PIN number consists of four letters, how many different PINs are possible?

The personal identification number (PIN) used by a certain automatic teller machine (ATM) is a sequence of four letters. a) How many different PINs are possible? Write the answer in exponential ...
1
vote
2answers
24 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 ...
0
votes
1answer
18 views

Understanding the total number of possibilities w/ at least

I'm having difficulty understanding a problem when they give the length and say AT LEAST x amount of numbers or letters. For example: (Includes case sensitive letters and numbers) Length 8 at least ...
0
votes
3answers
38 views

Mike works 5 days then takes 4 days off, will he be working in 220 days?

Mike is a security worker. He works 5 days and then takes 4 days off. If today is his third day of the working schedule, determine will he be working after 220 days from today? Was he working 197 days ...
1
vote
4answers
47 views

Prove using induction $2^{3n}-1$ is divisble by $7$ for all $n$ $\in \mathbb N$

Show that $2^{3n}-1$ is divisble by $7$ for all $n$ $\in \mathbb N$ I'm not really sure how to get started on this problem, but here is what I have done so far: Base case $n(1)$: ...
1
vote
0answers
33 views

need to know if this is correct [duplicate]

Use strong Principle of induction to prove that the amount of postage greater than or equal to 8cents cents can be made using a combination of 3 cent and 5 cent postage this is what i have so far: ...
0
votes
1answer
47 views

Elements of the Set of Rational Numbers

The set of rational numbers is defined as $\mathbb{Q} = \left\lbrace \frac{a}{b} \mid a, b \in \mathbb{Z} \land b \neq 0 \right\rbrace$. This apparently means that $\frac{1}{2}$ and $\frac{2}{4}$ are ...
2
votes
3answers
30 views

Weak principle of induction for $5+10+15+\ldots+5n= \frac{5n(n+1)}{2}$

Show that $$5+10+15+\ldots+5n= \frac{5n(n+1)}{2}$$ Proving the base case $n(1)$: $5(1)= \frac{5(1)(1+1)}{2}$ $5 = \frac{5(2)}{2}$ $5 = 5$ Induction hypothesis: $n = k$ ...
0
votes
1answer
23 views

strong induction postage question

Use strong Principle of induction to prove that the amount of postage greater than or equal to $30$ cents can be made using a combination of $10$ cent and $3$ cent postage this is what i have so ...
0
votes
4answers
44 views

Use the principle of induction to show $2+6+18+\ldots+2\cdot 3^{n-1}=3^n-1$

Show that $$2+6+18+\ldots+2\cdot 3^{n-1}=3^n-1$$ Proving the base case when $n=1$: $2\cdot3^{1-1}=3^1-1\Leftrightarrow 2=2$ Now doing the induction: $2\cdot 3^{(n+1)-1}=3^{n+1}-1$ $2\cdot ...
3
votes
4answers
50 views

Solving $3x\equiv 4\pmod 7$

I'm trying to learn about linear congruences of the form ax = b(mod m). In my book, it's written that if $\gcd(a, m) = 1$ then there must exist an integer $a'$ which is an inverse of $a \pmod{m}$. I'm ...
0
votes
2answers
59 views

Flipping a fair coin until either H or TTTT appears; what is the probability of getting at most two T's?

We flip a fair coin repeatedly and independently, resulting in a sequence of heads (H) and tails (T). We stop flipping the coin as soon as this sequence contains H or T T T T. What is the probability ...
2
votes
6answers
50 views

Prove that $n^2 > n+1 \quad\forall n \geq 2$ using mathematical induction

Prove $n^2 > n+1$ for $ n \geq 2$ using mathematical induction So I attempted to prove this, but I'm not sure if this is a valid proof. Base case, $n = 2$ $$ 2^2 > 2+ 1 $$ $n = k + 1$, ...
0
votes
0answers
17 views

Showing relation is transitive (a,b) $\in$ R iff 2|(a+b)

Let R be the relation on natural numbers defined by (a,b) $\in$ R iff 2|(a+b) show it is transitive.
0
votes
1answer
37 views

How do you determine if balls distinguishable- TwelveFold way

In the TwelveFold Way questions how do you determine if the balls are distinguishable or indistinguishable? Here is an example question: "From a set of 10 different sport magazines, 5 different car ...