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
2answers
46 views

Find all perfect squares of the form aaa…a (n digits) bbb…b (n digits)

Find all perfect squares of the form $\underbrace{a \ldots a}_n \underbrace{b\ldots b}_n$. This is my homework for Discrete Mathematics. All I'm asking for is to better understand what exactly the ...
1
vote
2answers
53 views

Graph with Cycle and Two-Colorable

i think if the graph G has an odd cycle, it's not two-colorable, otherwise it can be two colorable. i read in one notes that the following is True: we couldent two-colorable any graph G that has ...
2
votes
0answers
79 views

Derive a Recurrence

Could really use some help with this. For an integer $m \geq 1$ and $n \geq 1$, consider $m$ horizontal lines and $n$ non-horizontal lines, such that no two of the non-horizontal lines are parallel ...
0
votes
1answer
53 views

Maximum number of edge in simple diagraph

Could anyone describe for me why the maximum number of edge in simple diagraph with no cycle is $\text{combination}(2,n)$? My thought: If you have $N$ nodes, there are $N - 1$ directed edges than ...
3
votes
1answer
89 views

filling up numbers in a matrix

Suppose you have a $k.n \times 2$ matrix. You have to fill up the numbers $1,2,3, \cdots, n$ as entries in such a way that in each column it is non-decreasing, in each row it is strictly increasing ...
1
vote
1answer
79 views

What is an example of pairwise independent random variables which are not independent?

I've just read in a stochastics textbook: Let $(\Omega, P)$ be a discrete probability space. (a) The events $A_i \subseteq \Omega, i=1,2, \dots$ are called independent, if $$P(A_{i_1} \cap ...
5
votes
2answers
137 views

Prove $n^2+4n+3$ is not prime for $n \in \mathbb{Z}^{+}$.

I am trying to write a proof for this theorem: For every positive integer $n$, $n^2+4n+3$ is not a prime. Proof: Let $n \in \mathbb{Z}^{+}$. Note that $$n^2+4n+3=(n+1)(n+3)>1\text{,}$$ and ...
2
votes
4answers
39 views

How did author reach the conclusion tm $\equiv$ 0($\bmod$ m)?

This is a proof of a theorem from my book, Discrete Mathematics and its Applications Here is theorem 6 of Section 4.3 The first part of the proof, "because gcd(a, m) = 1" makes sense because the ...
0
votes
1answer
39 views

How does author reach step of $sa + tm \equiv 1 \pmod m$?

This is a proof of a theorem from my book, Discrete Mathematics and its Applications Theorem 1 If $a$ and $m$ are relatively prime integers and $m>1$, then an inverse of $a$ modulo $m$ ...
0
votes
1answer
154 views

Injective/Surjective/Bijective question

Given a constant function $f: \mathbb R \to\mathbb R$ given by ex: $f(x) = 3.14$. Is a constant, injective, surjective or bijective? I don't know how the mapping works for a constant.
1
vote
1answer
70 views

How to prove uniqueness of |a - c| = |b - c|

So I'm working on a problem, and the problem asks to prove that |a - c| = |b - c| has one unique integer solution for any odd integers a and b. I have proven that there exists a number (a + b)/2 ...
0
votes
0answers
83 views

Law of one price theorem proof

There are two subparts to Fundamental Asset Pricing theorem. The LOOP (Law of one price) holds if and only if there exists a state price vector. In a market in which the LOOP (law of one price) ...
3
votes
1answer
126 views

Isomorphic but not equivalent actions of a group G

This is in some sense a continuation of this problem. Given a group $G$ I would like to exhibit two actions of $G$ on a set $[n] =\{1,\ldots,n\}$ such that the two actions are isomorphic yet not ...
4
votes
2answers
356 views

Distributing 6 oranges, 1 apple, 1 banana and 1 pineapple among 3 children

if we were to have 6 oranges, 1 apple, 1 banana and 1 pineapple. On how many ways can we distribute this to 3 children (each child must receive at least one fruit)? I was trying to do it in a way ...
0
votes
3answers
44 views

Generating Function for a Recurrence Relation $a_n=a_{n-1} + n$

Find a generating function for $\{a_n\}$ where $a_0=1$ and $a_n=a_{n-1} + n$
0
votes
0answers
93 views

A room contains n people. Everybody wants to shake everyone else’s hand (but not their own).

(a) Suppose that n people require hn handshakes. If an (n + 1)th person enters the room, how many additional handshakes are required? Obtain a recurrence relation for hn+1 in terms of hn. (b) ...
0
votes
2answers
72 views

Regular expresson a's and b's

Need to construct a regular expression that recognizes the following language of strings over the alphabet {a,b}: - The set of all strings over alphabet {a,b} in which every occurrence of b is ...
0
votes
1answer
248 views

Well-formed formula, Inductive Definition

So I have to inductively define: The number of propositional variables of a "Well-formed formula" The set of propositional variables of a "Well-formed formula" The set of parenthesis in a ...
0
votes
3answers
88 views

Show that if $\bar{A} \cap \bar {B} \subseteq C$ then $A \cup B \cup C$ is the universal set

For any subset $A$ of the universe $U$, we denote $\bar{A}$ as $U - A$. Show that for any subsets $A, B, C$ of the universe $U$, if $\bar{A} \cap \bar {B} \subseteq C$ then $A \cup B \cup C = U$. ...
2
votes
1answer
26 views

Find the expectancy of $X$

Let $p,q \in (0,1)$. Let $Y$ be the R.V denotes the number of days of the storm in the ocean. $Y\sim \text{Bin}(n,p)$. Let $X$ be the number of ships drowned during the storm and we know that the ...
1
vote
4answers
166 views

How to prove this modular multiplication property to be true?

I am watching a youtube video on modular exponentiation https://www.youtube.com/watch?v=sL-YtCqDS90 Here is author's work In this problem, the author was trying to calculate $5^{40}$ He worked ...
0
votes
2answers
75 views

How to prove that the composition of two surjective functions is surjective [duplicate]

I know that the map $f:A\to B$ is a surjective function (onto) if for all $b$ in $B$, there exists an $a$ in $A$ such that $f(a)=b$ But I am having trouble getting started with this proof since it ...
3
votes
1answer
88 views

If there are $n$ number of males and $n$ number of females, how many ways to seat them about a round table if sexes alternate?

If there are $n$ number of males and $n$ number of females, how many ways can they be seated about a round table if the sexes alternate and arrangements are considered the same when one can be ...
1
vote
1answer
53 views

What is the difference between “$\forall a :\forall b:P(a) \implies Q(b)$” and “$(\forall a:P(a))\implies(\forall b:Q(b))$”?

The type of a is proper subset of the type of b. “$\forall a:\forall b:P(a)\implies Q(b)$" and "$(\forall a:P(a))\implies(\forall b:Q(b))$” Are they equal?
1
vote
1answer
39 views

How to get to the next step in the procedure?

This is from https://courses.cs.washington.edu/courses/cse311/14au/slides/lecture12-filled.pdf, This procedure is used to solve a modular exponentiation problem, say Here is the procedure How ...
0
votes
0answers
25 views

How to prove this property for repeated squaring?

This is from https://courses.cs.washington.edu/courses/cse311/14au/slides/lecture12-filled.pdf This property is used for modular exponentiation, that is to do a problem like this (from slide 6) ...
0
votes
0answers
49 views

How are these terms algebraically equivalent?

This is from https://courses.cs.washington.edu/courses/cse311/14au/slides/lecture10-filled.pdf slide 25. This is the definition of a is congruent to b modulo m. (from slide 24) This is an example ...
4
votes
0answers
94 views

Prove that for all integers, if $a$ is even and $b$ is odd then $a^{2}+3b$ is odd.

Theorem: For all integers, if $a$ is even and $b$ is odd then $a^{2}+3b$ is odd. So far my proof is as follows: Let $a$ be any even integer Let $b$ be any odd integer By the definition of even ...
0
votes
0answers
35 views

Second order Fibonacci numbers

Let's consider a recurrence: $A_{0}=0$, $A_{1}=1$, $ A_{n}=A_{n-1}+A_{n-2}+F_{n}$, where $F_{n}$ is the $n$th Fibonacci number. How to express $A_{n}$ in a closed form? Despite the fact that it ...
-1
votes
2answers
163 views

Derive a recursive form of the function f(n) = 2n(n-6).

The Function f: N -> Z is defined by f(n) = 2n(n-6) , for each integer n >= 0. Derive a recursive form of this function f. Please help :[
7
votes
1answer
181 views

Occupying seats in a classroom

Here's a nice probability puzzle I have thought about for a class I'm TAing, I'm curious to see different solutions :) It goes like this: We have a classroom with $n$ seats available and $m \leq n$ ...
1
vote
2answers
78 views

NFA construction problem

I need to construct an automaton that recognizes the following language of strings over the alphabet $\{a,b\}$: The set of all strings over alphabet $\{a,b\}$ with the subsequence $abba$. (A ...
2
votes
3answers
67 views

How can I compute $\sum\limits_{k = 1}^n \binom{n - 1}{k - 1}$?

I know what $n \choose k$ equals, but I don't see how that would help me solve the sum of $n - 1 \choose k - 1$ from $k = 1$ to $n$. Is there any special trick I should know?
0
votes
1answer
210 views

How many binary sequences of length 7 have at least two 1's?

How many binary sequences of length 7 have at least two 1's? Can someone please explain the procedure in detail please. I tried solving it using the "count what you do not want" procedure, but I got ...
0
votes
1answer
45 views

Contruct an NFA

Construct an automaton that recognizes the following language of strings over the alphabet {a,b}: {a,bb} that is only a and bb Do anyone think that this might be the right approach or has any ...
3
votes
1answer
124 views

Battleship game - logic for positioning ships

I'm working on a project where I'm programming a battleship game using objected-oriented principles of programming. I got stuck at one problem that is purely mathematical and relates to the ...
1
vote
3answers
73 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 ...
6
votes
1answer
94 views

Probability no two pairs are grouped together twice in a row?

There is a room with 48 people divided into 16 groups of 3 in round 1. In round 2, the group is again randomly divided into 16 groups. What is the probability that no two groupmates in round one are ...
0
votes
0answers
75 views

How many pairs of primes $p$ and $q$ are there such that $p − q = 3$?

How many pairs of primes $p$ and $q$ are there such that $p − q = 3$? Then we have $$p=q+3$$ But, $2$ is the only even prime (if not would not be prime). If $5,2$ were not the only then $$p=(2n+1) + ...
20
votes
6answers
4k views

Why is mathematical induction a valid proof technique? [duplicate]

Context: I'm studying for my discrete mathematics exam and I keep running into this question that I've failed to solve. The question is as follows. Problem: The main form for normal induction over ...
0
votes
2answers
98 views

Determine whether set forms an orthonormal basis

Consider the three vectors $x^{1} = (1/\sqrt2, 0, −1/\sqrt2)^T$ , $x^2 = (0, 1, 0)^T$ , $x^3 = (1/\sqrt2, 0, 1/\sqrt2)^T$. Does the set $A = {x^1, x^2, x^3}$ form an orthonormal basis of ...
0
votes
2answers
105 views

$f(f(f(a)))=a$ but $f(f(a))\ne a$ how many function similar exists?

Let A be a set, $|A|=12$ let $f$ be a function from $A$ to $A$ ($f:A\to A$ ) For each $a\in A$ $f(f(f(a)))=a$ But $f(f(a))\ne a$ $f$ is bijection, How many similar functions exist? I am not sure ...
0
votes
1answer
54 views

Transitive Elements on Set

i get trouble in one problem... if we have relation R={(a,b), (b,c), (b,d), (c,e), (d,e), (c,f), (e,a)}, on set {a,b,c,d,e,f}. how many elements the transitive closure of R has? I try ...
-1
votes
1answer
81 views

How many triple satisfy in inequality

I found an Entrance Exam question like as: How many triple like (A,B,C) from subsets of set {1,2,3,4} is true in following inequality : $ A \cap B \subseteq C \subseteq A \cup B $ any hint or ...
2
votes
1answer
36 views

Find the variance using the Law of total variance

Let a bacteria which behaves in one of two following ways: In the end of the day it may die but bring $2$ descendants with the probability of $p$ or die without bringing any descendants with the ...
1
vote
0answers
403 views

Expected number of cards you should turn before finding an ace

NOTE: I want to check my solution only Same question here The question is this: Shuffle an ordinary deck of 52 playing cards containing four aces. Then turn up the cards from the top until the ...
0
votes
1answer
33 views

Hamilton cycles with only 3 vertices

if a graph has only 3 vertices, can it have a Hamilton cycle. I know it has a Euler cycle because you can hit every edge at least once without doubling. If a graph only has 3 vertices though can you ...
0
votes
1answer
19 views

CompSci Math Proof Contrapositive Method

The question is "Using the contrapositive prove for all integers n, if n^2 is a multiple of 5 then n is a multiple of 5". I know that the contrapositive is "if n is not a multiple of 5 then n^2 is not ...
0
votes
2answers
70 views

Show that for $\mathbb{N} = \{ 1, 2, 3, \ldots \}$, $s: \mathbb{N} \to \mathbb{N}$ where $s(n) = n + 1$ has infinitely many left inverses.

The exact textbook question is: Let $\mathbb{N}$ denote the set $\{1,2,3,\ldots,\}$ of natural numbers, and let $s:N \to N$ be the shift map, defined by $s(n) = n + 1$. Prove that $s$ has no right ...
4
votes
1answer
99 views

Express the quantified logical statements using the predicates

I just started learning predicates and quantifiers. I am pretty confused so I was wondering if someone can help me. Using the predicates $P(x)$ to denote “x is a pro baseball player”, $R(x)$ to ...