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
3answers
44 views

How to find the solution of $T(n,m) = T((n-1),m) + T(n,(m-1))$ in terms of big $O$ notation?

I would like to solve the recurrence $T(n,m) = T((n-1),m) + T(n,(m-1))$. I think the solution is $$O(2^{n+m})$$ because in every step you can reduce either $n$ or $m$ by one or not, but I can not ...
1
vote
1answer
24 views

Find number of circular arrangements possible

If 20 persons were invited for a party, in how many ways will two particular persons be seated on either side of the host in a circular arrangement? According to me the answer should be $17!.2!$. But ...
1
vote
3answers
29 views

For $x,y \in \mathbb R - {2}$, $x * y = xy - 2x -2y + 6$. Find the identity element.

I'm struggling to answer these kind of questions. In general, the way I set up these kind of problems is $a * e = a$, apply the particular operation to $a$ and $e$ and see if I can arrive at value for ...
1
vote
3answers
27 views

Find the function, f such that the graph of f contains the point () [closed]

Okay so I recently ran into this problem and I have no idea how to do it. How do I solve for the following question? Find a function f such that the graph of f contains the point ( 1,2 ) and ...
3
votes
2answers
68 views

What is a good book for reviewing high school math, and preparing for university?

I'm signing up for University soon (Compsci program) as a mature student. It's been a long time since I've done any math, and I went as far as grade 11 in high school. So, I'm looking for a book that ...
3
votes
4answers
316 views

Prove that the graph is connected

I was wondering if someone can help me understand how prove that this graph is connected. Given a graph with n vertices, prove that if the degree of each vertex is at least $(n − 1)/2$ then the graph ...
0
votes
1answer
15 views

How to find out transient response of z-transform (discrete)

Given z-transform transfer function $H(z) = \frac{Y(z)}{X(z)}$, with the corresponding linear ODE, how does one find out transient response of such a transfer function given a certain input?
0
votes
1answer
35 views

Quadratic congruence prime numbers [closed]

If $p$ is a prime number... a) show that $x^2 \equiv 1 \pmod{\!p}$ has only the following solutions: $x \equiv 1 \pmod{\!p}$ and $x \equiv -1 \pmod{\!p}$. b) show that $(p-1)! \equiv -1 ...
0
votes
4answers
64 views

if $f:X \to Y$ is 1-1 and $|X| = |Y|$, does that imply $f$ is onto?

Similarly, if $f$ is onto and both sets have the same cardinality, does that imply $f$ is 1-1? I'm pretty sure both statements are true but I'd rather not assume. Thank you for your time.
2
votes
1answer
48 views

How do I find nine messages which are unchanged by RSA encryption using the public key $(3869, 3)$.

I understand how RSA crytosystem works, however I am not sure how to apply it to answer these questions. Can someone explain please? Let $N=3869$ and be the product of two distinct unknown odd prime ...
-1
votes
1answer
54 views

Discrete math of $i^3$ [closed]

Show that $$ \sum_{i=1}^n i^3=\frac{n^2(n+1)^2}4 $$ I don't understand how to do this, any help would be appreciated.
0
votes
0answers
25 views

How to use mobius-inversion to solve this problem?

Currently, I'm trying to solve this problem using mobius-inversion. the function f(d) means the number of (i, j, k) equals d, and function g(d) means the numbers that satisfying: d | (i, j, k). Then ...
3
votes
6answers
124 views

(14^2014)^2014 mod 60 without a calculator

Calculate without a calculator: $\left (14^{2014} \right )^{2014} \mod 60$ I was trying to solve this with Euler's Theorem, but it turned out that the gcd of a and m wasn't 1. This was my ...
1
vote
1answer
13 views

When can you not do a mapping composition?

Suppose I have $\alpha:\mathbb R^3 \to \mathbb R$ and $\beta:\mathbb R \to \mathbb R^+$. Looking over my notes, it says $\alpha \circ \beta$ can not be done but $\beta \circ \alpha$ can. What is the ...
1
vote
2answers
14 views

Are they using Vandermonde's Identity here?

Consider a set of $5$ men and $7$ women. Then there are $\binom 53 \binom 72$ groups consisting of $3$ men and $2$ women. What they are doing looks very much like this identity: $\binom {m + n}{k} = ...
0
votes
1answer
16 views

Find $x$ for $[809x] = [214]$ in $\mathbb Z_n$ where $n= 5124$ s.t $0 \le x < 5124$.

The following is dealing with equal classes under congruence modulo $n$. I was told to use my answer for $[809x] = [1]$ in $\mathbb Z_n$ where $n=5124$ s.t $0 \le x < 5124$, so basically it's ...
0
votes
1answer
8 views

Choosing subsets out of a set by using lists

Suppose we need to choose sets of size $2$ out of $\{A, B, C\}.$ The answer is given by $\frac {n!}{ (n - k)! k!}$. So, $n! = \{\text {ABC ACB BCA BAC CAB CBA}\}.$ What lists do $(n - k)!$ and $k!$ ...
-1
votes
3answers
94 views

Use mathematical induction to prove a statement [closed]

Use mathematical induction to prove that: $$A\cap\left(\bigcup_{i=1}^nB_i\right) = \bigcup_{i=1}^n\left(A\cap B_i\right)$$
1
vote
1answer
15 views

proving property of polynomial that is composite

Show that $a^m+1$ is composite if $a$ and $m$ are integers greater than 1 and $m$ is odd. [$Hint:$ Show that $x+1$ is a factor of the polynomial $x^m+1$] So I tried doing it and got a result which ...
0
votes
2answers
44 views

Prove by induction that for a natural number a there exists integers $x, y$ where $a = 7x + 2y?$

I am trying to get my head around induction at the moment and found this problem in a textbook. I think that I should be doing induction on a, but I can't even see where to start the proof.
3
votes
5answers
52 views

Sets $A,B,C$ with $B\subseteq C$, prove that $(A-B)-C=A-C$

Ran across this and couldn't figure out how you would give a formal proof. It seems intuitive, in that $(A-B)-C$ is the elements in $A$ but not in $B$, and then also remove the elements from $(A-B)$ ...
0
votes
2answers
39 views

Find the probability that an integer selected between 1 and 5000 is divisible by at least one of 3, 5 and 7

I'm having a hard time finding the solution. I can find integers that are divisible by only one of them, but there are many that are divisible by two of them. That's the problem. Find the probability ...
2
votes
0answers
24 views

Hasse Diagram Correct?

I've had to make Hasse Diagrams before, but they've always been, for lack of a better word, pretty. The lines haven't had any complicated back and forth or the like. The jump that 4 and 6 have to do ...
6
votes
1answer
50 views

Generalized way to solve $x_1 + x_2 + x_3 = c$ with the constraint $x_1 > x_2 > x_3$?

On my example final exam, we are given the following problem: ...
3
votes
1answer
44 views

Number of hairs of inhabitants and the population of a city

There is a town T where the population is greater than the number of hairs of each inhabitant. That is, if we count the number of hairs on the head of any inhabitant of the town, the amount will be ...
1
vote
2answers
24 views

Are Cartesian Product and Multiplication (kind of) equivalent?

Example(not trying to prove anything): $|\{X, Y, Z\}| \times |\{A, B\}| = |\{XA, XB, YA, YB, ZA, ZB\}| = 3 \cdot 2 = 6.$
2
votes
1answer
58 views

Discrete Mathematics

I am having great difficulty trying to understand a question I have found and am keen to finding the solution and would appreciate any help. "Suppose that ten computer programs have been submitted ...
0
votes
1answer
37 views

Discrete Mathematics Sets Help

Hi i'm having difficulties working this question out I found, any help would be appreciated :) Let $A = \{1,2,4\}$ and $B = \{1,2,3\}$. Define the function $f: A\to B$ by the rule. What is the ...
0
votes
1answer
12 views

Bijection between lists and sets

Multiplication Principle as given in my textbook: Consider two element lists for which there are $n$ choices for the first element, and for each choice of the first element there are $m$ choices ...
0
votes
1answer
30 views

Cardinality multiplication in counting problems

Multiplying things seems to be my weakest point, so I am trying to understand as much as possible. Consider $\sum^k_{j = 0} \binom mj \binom n{k - j}$. It's the answer to the question: "from a class ...
2
votes
2answers
50 views

Experiment: Roll three 6-sided dice.

Are the following probabilities correct? I'm not very confident with probabilities and would just like these double checked please. Thank you. Experiment: Roll three 6-sided dice. a) Find the ...
0
votes
2answers
14 views

Lattice orders and number of elements in a set

My discrete mathematics lecture notes give the following definition of a lattice order: A 'Partial order R is a lattice order if the set of lower bounds for any two elements $x, y ∈ X$ has the ...
1
vote
3answers
37 views

Suppose $k$ is even and $4 \nmid k$, please explain why $k/2$ is odd

Assume integer $k$ is even and $k>2$. In order for $k/2$ to be odd, $k$ cannot be divisible by $4$. Can someone please explain why this is true, or point me in the right direction? I don't need to ...
0
votes
0answers
7 views

Find minimum number of uniformely colored rectangles in a colored grid

I have an MxN grid. In each square of the grid there is color taken from a set of color C. I can describe the whole grid with MxN statements that say something like: the square (Mi,Nj) has the color ...
6
votes
4answers
109 views

Inductive Proof that $k!<k^k$, for $k\geq 2$.

Call $P(k): k!<k^k$, for $k\geq 2$ Test it out with 2, and it's true ($2<4$). Assume that $P(k)$ is true for some $k\geq2$. Then show that $P(k+1)$ is true. $P(k+1): (k+1)!<(k+1)^{k+1}$ ...
3
votes
2answers
50 views

14 pencils handed out to 6 people. Each person has at least 1 pencil. Person 6 no more than 3 pencils.

We have 14 indistinguishable pencils and we want to hand out all of the pencils to 6 people and we want everyone to get at least one pencil. However, we do not want person 6 to get more than 3 ...
1
vote
2answers
40 views

How many different ways can 14 pencils be passed out to 6 different people? Some people are allowed no pencils.

There are 2 questions that are very similar and I have the same answer to both but I don't think that's correct. Can you help me see the difference between the 2 questions. We have 14 ...
3
votes
4answers
162 views

Four 6-sided dice are rolled. What is the probability that at least two dice show the same number?

Am I doing this right? I split the problem up into the cases of 2 same, 3 same, 4 same, but I feel like something special has to be done for 2 of the same, because what if there are 2 pairs (like two ...
2
votes
2answers
25 views

Equivalence Classes Output

I understand that an equivalence relation is a set that is reflexsive, symmetric, and transitive. I don't quite understand equivalence classes though. For example: What would the equivalence class be ...
-3
votes
1answer
56 views

Prove by induction $\frac{a_{1} + a_{2} + a_{3} +…+ a_{n}}{n} \geq \sqrt[n]{a_1 \cdot a_2 \cdot a_3 \cdot …a_n}$. [duplicate]

Let $a_1$ $a_2$,..., $a_n$ be positive numbers. Prove that $\frac{a_{1} + a_{2} + a_{3} +...+ a_{n}}{n} \geq \sqrt[n]{a_1 \cdot a_2 \cdot a_3 \cdot ....a_n}$. Mine is about trying to understand how ...
0
votes
0answers
37 views

Proof by induction [duplicate]

$\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} +\cdots+\frac{1}{n^2} < 2 - \frac{1}{n}$. Proof: Let $p(n)$ be a proposition. $$p(n):\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} ...
1
vote
2answers
25 views

Making sense of a combinatorial answer

$\frac {\sum^n_{k= 0}k\binom nk}{2^n}$ is the average size of a subset of $\{1, 2, \ldots, n\}$. We add up the sizes of all subsets and divide by the total number of subsets. Why is the $i$th term ...
3
votes
1answer
219 views

Euler's theorem: [3]^2014^2014 mod 98

Calculate without a calculator: $$\left [ 3 \right ]^{2014^{2014}}\mod 98$$ I know I have to use Euler's Theorem. As a hint it says I might need to use the Chinese Remainder theorem too. I know ...
0
votes
2answers
27 views

How to create a moment generating function for $Y$?

Consider a discrete random variable defined as follows: When $X=0$, $P(X=x) = .25$. When $X=1, P(X=x) =.4$. When $X=2, P(X=x) = .35$. The moment generating function for $X$ will be: $$Mx(t) = .25 + ...
0
votes
1answer
29 views

Permutation and combination.

I have started learning permutation and combination. I am looking at the question below. It has given the answers also but I didn't understand how? I have looked at many examples online it just made ...
3
votes
3answers
116 views

Proof verification for proving $\forall n \ge 2, 1 + \frac1{2^2} + \frac1{3^2} + \cdots + \frac1{n^2} < 2 − \frac1n$ by induction

Prove by mathematical induction: $\forall n \ge 2, 1 + \frac1{2^2} + \frac1{3^2} + \cdots + \frac1{n^2} < 2 − \frac1n$ Basis Step: (We want to show, $P(2)$, which is 1 + ...
0
votes
1answer
36 views

Computing the Value of a minimax tree

I am asked to compute the value of a minimax tree, which each node labeled with its initial value. I am just unsure how to do it. I know that it is a minimax tree if: the root is a min node, the ...
0
votes
0answers
31 views

Probability With 52 Playing Cards

I am trying to answer the following questions as practice, however I am unsure on whether this is correct! 1) Probability of first card is $Heart$ is $13/52$ 2) Is the probability of getting a King ...
0
votes
2answers
35 views

How many elements in $X$ are of the form $3k + 1$ for some integer $k$?

Consider the set $X={300,301,302,...,29999,30000}$ (the set of all integers from $300$ to $30,000$ inclusive.) You do not need to simplify the numeric answers. How many elements in $X$ are of the ...
1
vote
0answers
35 views

How to find the upper bound of a binomial coefficient by using binomial theorem?

I have a task to find a upper bound of the binomial coefficient for all $r \leq \frac{n}{2}$. I've already obtained by using such relation: $$\frac{\sum_{k=0}^{r}\binom{n}{k}}{\binom{n}{r}}$$ Which ...