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
0answers
3 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
18 views

Quadratic congruence prime numbers

If $p$ is a prime number... a) show that $x^2 \equiv 1 \text{ mod } p$ has only the following solutions: $x \equiv 1 \text{ mod } p$ and $x \equiv -1 \text{ mod } p$ b) show that $(p-1)! \equiv -1 ...
0
votes
4answers
52 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
21 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
45 views

Discrete math of $i^3$ [on hold]

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.
-1
votes
0answers
7 views

Get a given string by concatenation of the minimal number of given words

Suppose you have an input string, say $s$, and a set of words $W$. The task is to find the minimal $N$ such that: $s = w_1 \cup w_2 \cup ... w_N$, where $w_i \in W$. Could you please name a handy ...
0
votes
0answers
18 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 ...
2
votes
5answers
68 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
12 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
13 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
15 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
83 views

Use mathematical induction to prove a statement [on hold]

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)$$
0
votes
1answer
24 views

Infinite Decision Problems [on hold]

How can I prove that there are infinitely many decision problems of natural numbers that cannot be soved?
1
vote
1answer
14 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
39 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
45 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
29 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
20 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 ...
1
vote
1answer
24 views

Prove that there exists a 2 by 2 sub square with odd number of white cells (i.e. 1 black, 3 white cells). [on hold]

I had previously asked a question similar to this but was told the question had an error, so this is the modification. Given a 200 by 200 board containing black and white squares prove there exists ...
6
votes
1answer
47 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
42 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
21 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
2answers
35 views

Hamiltonian cycle from adjacency matrix [on hold]

I'm finding it quite hard to answer this question I found; any help would be great. Find a Hamiltonian cycle in the graph G whose adjacency matrix is $$\begin{bmatrix} ...
2
votes
1answer
41 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
21 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
44 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 ...
-5
votes
1answer
19 views

Finding a solution to a recurrence relation [on hold]

Here is the setting of my problem $(a_k)$ is a sequence of numbers verifying : $a_k=4a_{k-1}+5$ for all integers k greater than or equal to 1. Initial condition: $a_0=2$. I need to find a close ...
1
vote
3answers
36 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
5 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 ...
4
votes
3answers
77 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
36 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
38 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
147 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
23 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
55 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
80 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
26 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
26 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
111 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
17 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
30 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
31 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 ...
1
vote
2answers
15 views

Finding the cardinality of a cartesian product of a set and a cartesian product.

$A = \{0, 1, \{2, 3, 4\}\}$ $B = \{1, 5\}$ $C = B \times \mathbb{N}$ What is the cardinality of $A \times C$? I know the enumeration of $A \times C$ is $\{(0,(1,0)), (0,(1,1)), (0,(1,2))\ldots ...