Tagged Questions

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
23 views

question about a combinations problem involving big n and k

I have the following sample space $\Omega = \{ \omega = (\omega_1, ..., \omega_{77}) \in \{1,...,999\}^{77}: \omega_1 \leq ... \leq \omega_{77}\}$ and want to calculate the probability of $A = \{ ...
1
vote
2answers
50 views

Prove by induction the predicate (All n, n >= 1, any tree with n vertices has (n-1) edges).

I'm stuck on this problem, posting my progress so far below. I've looked at similar questions here and here, but neither seem to directly prove the predicate by induction, with a base case followed by ...
0
votes
3answers
55 views

Recurrence relation sequence problem

For the following recursively defined sequence, evaluate the first few terms, conjecture a formula for $t_n$ and then use induction to prove your formula is correct. $t_1 = 2$, $t_n = t_{n-1} + ...
3
votes
0answers
38 views

Does $\theta(n)$ = $1/x$ make any sense?

So, I asked this question on a discrete structures exam today, which I apparently didn't give enough thought to: $f(x) = (5x^2 + 6x + 2)/(x^3 + 4x^2 +x)$ Find the correct theta notation for the ...
8
votes
0answers
83 views

Algorithm to compute fastest method of collecting $k$ re-spawning items which spawn at $n$ specified points

Let $V = v_1, \dots, v_n$ be the locations the items can spawn at, and let $U = u_1, \dots, u_k$ be the current positions of the items. We will assume a new items spawns instantly every time we ...
0
votes
1answer
33 views

Cardinality of a Cartesian product

If the set $S$ has cardinality $\#S$ and the set $T$ has cardinality $\#T$, what is the cardinality of $S \times T$? The value of $\#T$ and $\#S$ are unknown, so how is this possible? In my case the ...
1
vote
0answers
10 views

Relations Notation

Classify the following relations, all of which have signature R : {1,2,3,4} ↔ {a, b, c, d} R = {2→a,3→b,1→a,4→b}=many-1 R = {3→a,2→a,3→c,1→c,2→c}=many-many R = {2→a,3→b,1→d,4→c}=one-to-one ...
1
vote
2answers
46 views

Solving the equation $a+e+2ae=a$ for $w$

Just need a quick answer of how my tutor got $e$ to $= 0$ from this equation. (I'm trying to find the identity of a binary operation) $$a+e+2ae=a$$ I feel like this is a very easy problem but I'm ...
0
votes
1answer
13 views

trying to find associativity

Is the binary operation define by: $x*Y = x+y-1$ what my tutor has done: $x*(y*z) = x *(y+z -1) = x+(y+z-1) = x+y+z-2$ My question: how did he get $x+y+z$-2 Where did the '-2' come from? I am ...
0
votes
1answer
47 views

Shifted Fourier transform

Please can some one help and give me a direction to evaluate the following shifted Fourier transform: \begin{alignat}{2} s(x_c) =&\frac{1}{\Delta x_0} \int_{x_c-\Delta x_0}^{x_c+\Delta ...
2
votes
2answers
38 views

Mathematical Induction Proof - Exponent with n in denominator

Use mathematical induction to prove the following: $$\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+...+\frac{n}{2^n}=2-\frac{n+2}{2^n}; n ∈ N $$ I am having trouble figuring out how to solve this with an ...
5
votes
4answers
360 views

Give a combinatorial argument

Give a combinatorial argument to show that $$\binom{6}{1} + 2 \binom{6}{2} + 3\binom{6}{3} + 4 \binom{6}{4} + 5 \binom{6}{5} + 6 \binom{6}{6} = 6\cdot2^5$$ Not quite where to starting proving this ...
1
vote
1answer
28 views

Is this quantifier is true?

"Every mail message larger than one megabyte will be compressed". Let $M(x) = x$ mail message $L(x) = x$ larger than one megabyte will be compressed $ \forall x \space (M(x) \rightarrow L(x))$
1
vote
1answer
16 views

Another quick induction question for a recursively defined sequence (with closed form formula given)

I was given: A sequence is defined recursively by $a_0 = 1$, $a_1 = 4$, and for $n\ge2$, $a_n = 5a_{n-1} - 6a_{n-2}$. Use induction to prove that the closed form formula for $a_n$ is $a_n = ...
0
votes
3answers
54 views

Determine the Number of Integer Solutions $x_1 + x_2 + x_3 + x_4 = 32$ with restrictions

The Question My Problem Part a is straight forward, just $C(35,32)$. I'm having a little difficulty with the restrictions and understanding what they mean. $x_1 > 0$ means we shouldn't have any ...
1
vote
2answers
34 views

Picking 3 random books probability problem

So the question is: Suppose a bookcase holds 6 chemistry, 5 math, 3 physics, and 8 computer science texts. if 3 books are selected, find the probability that none of the math texts are selected. My ...
-1
votes
4answers
65 views

The negation of “today is Friday” is “today is Saturday” Is it true? [closed]

The negation of "today is Friday" is "today is Saturday" Is it true ?
4
votes
4answers
98 views

Flipping coins probability of $6$ flips having more heads than $5$ flips.

I have $6$ fair coins and you have $5$ fair coins. We both flip our own coins and observe the number of heads we each have. What is the probability that I have more heads than you? Not sure how to ...
0
votes
1answer
19 views

Learning question: to find whether a function is injective

Let F: z -> z such that: f(n)= $\lfloor(1-6n)/3\rfloor$ To find injectivity i did: suppose $f(n_1) = f(n_2)$ therefore $\lfloor(1-6n_1)/3\rfloor$ = $\lfloor(1-6n_2)/3\rfloor$ therefore ...
0
votes
1answer
27 views

How can i learn when to use which multiplication rule: Probability

Hey guys im studying for a math exam and was wondering if anyone has some easy techniques to remember in what kind of scenario to use these equations. These are I believe called multiplication rules. ...
0
votes
2answers
25 views

divisibility relation $a|b^2 + 10c.$

Use divisibility relation to show that for all integer $a$, $b$, $c$, $a \ne 0$ counts if $a|b$ and $a|c$ then $a|b^2 + 10c$. Use direct proof. Ok, $a|6$ then there is integer $k$. $$a*k=6,$$ ...
0
votes
2answers
48 views

Show there is no solution to this equation

I have to show that $2x^4-20x+8$ cannot be divided by $16$ without remainder. The only thing comes to my mind is to write $16$ as $4^2$ which hasn't been of any help. Could you give me some hints to ...
1
vote
2answers
27 views

Probability of finding a prize in the box?

There are $7$ concealed boxes, and $6$ of the boxes are empty while $1$ of the boxes contains a nugget of gold. You are required to select two boxes out of the $7$, and after selecting two boxes the ...
0
votes
0answers
73 views

Compute Shannon and Simpson index as a function of time and compute amount of time to stabilize

Suppose a_i(t) for i=1,2,...,n, represents species density at time t As the system evolves, smaller a_i's, than a critical value, get still smaller and ultimately vanish while the others keep ...
0
votes
0answers
21 views

What is the expectation of the number of collisions when inserting elements into a hash table?

If the table is of size $N$, and the hash function is $f(x) = x\mod N$, and linear probing is used to solve collisions, what is the expectation of the number of total collisions when inserting $k$ ...
1
vote
3answers
33 views

Mathematical Induction divisibility

So I'm trying to use mathematical induction to show that for all integers $n \ge 1$ , $$ 8|(3^{2n} - 1)$$ (is divisible by 8) I have my base case: [P(1)], $3^2 - 1 = 9 - 1 = 8$, since $8|8$, the ...
2
votes
1answer
40 views

Show $e^x / (1 - x)^n$ is the exponential generating function for a specified sequence

Show that $e^x/(1-x)^n$ is the exponential generating function for the number of ways to choose some subset (possibly empty) of $r$ distinct objects and distribute them into $n$ different boxes ...
1
vote
0answers
26 views

PageRank algorithm explanation

I'm currently suffering from a case of terrible professor and need someone to explain this algorithm for me. I'll just post a question and would appreciate if someone could walk me through how to ...
1
vote
3answers
39 views

Show that $n! = O(n^{n})$

As the title says, how would you show that $n! = O(n^{n})$? I'm not really understanding how one "shows" the Big O notation of a function mathematically (at least when you're dealing with things that ...
0
votes
2answers
19 views

For all $n \in \mathbb{N}, |A_n|<|\bigcup_{n\in \mathbb{N}} A_i|$

For all $n \in \mathbb{N}, |A_n|<|\bigcup_{n\in \mathbb{N}} A_i|$ Proof, If $A_n \subseteq \bigcup_{n\in \mathbb{N}} A_i$ then $A_n \lessapprox \bigcup_{n\in \mathbb{N}} A_i$. By transitivity we ...
0
votes
1answer
33 views

Determining if a function is onto or one-to-one

Let $P$ be the power set of $\{a,b,c\}$. A function $f: P \to \mathbb Z$;the set of integers, follows: For $A$ in $P$, $f(A)$=the number of elements in $A$. I'm not sure how to get started with this ...
2
votes
1answer
32 views

Disagreement over Discrete Math Property

I know I'm probably wrong, maybe someone can explain it to me. I'm doing practice problems in preparation for a test that is coming up. Let u and v be two vertices in a graph G. Show that if G ...
0
votes
0answers
5 views

Switching theory word problem. (Minimal representations)

A shop sells postage stamps for collectors in six different packets. Packet #1 contains European and African stamps. #2 has American and Asian stamps. #3 has American and European. #4 has only ...
0
votes
1answer
59 views

General form of iterates $f^{n}(x)$ for $f(x) = \frac{x}{1-x}$

Let $f: \mathbb R\to\mathbb R$, $f(x) = \frac{x}{1-x}$. Define $f^{2}(x) = f(f(x))$, $f^{3}(x) = f(f(f(x)))$, ... Guess the form for $f^{n}(x)$ and prove your answer is correct using ...
0
votes
0answers
22 views

How to solve this discrete-time equation?

How do I find a sinc function $f(l,k)$ such that: $$\sum_k \sum_i a_i g((k-m)T/2 - i(T+\Delta T)) f(l,k) = \sum_k a_k g((l-m)T/2 -kT)$$ where $g(t)=\frac {\sin(2\pi t/T)}{2\pi t/T}$, $a_k \in ...
0
votes
0answers
8 views

Reconstructing symbols from another set of symbols

I have a discrete-time signal as: $r_l = r(lT/2) = \sum_m h_m \alpha_{l-m}$ where $\alpha_l = \sum_k a_k g(lT/2 -k(T+\Delta T))$ where $a_k \in \lbrace\pm 1\rbrace$, $g(t)=\frac {\sin(2\pi t/T)}{2\pi ...
0
votes
1answer
38 views

Prove: [∃xp(x)->∃xq(x)]->∃x[p(x)->q(x)]

$[∃xp(x)\to∃xq(x)]\to∃x[p(x)\to q(x)]$ So I understand that if $∃x(p(x)\to q(x))$ is false then the whole statement would be false since it is an implication. In that case $∀x p(x)\wedge∀x \neg ...
2
votes
1answer
59 views

Statement about divisibility

Let's consider such function: $$f(N) = 1^1\cdot 2^2\cdot 3^3 \dots (N-1)^{N-1}\cdot N^N.$$ Does the expression $$\frac{f(N)}{f(r)\cdot f(N-r)}$$ is always integer? Can you give me any hint about ...
0
votes
0answers
15 views

Counting-Box problem-finding a conditional subset

a) for how many integers between 1,000 and 9,999 is the sum of the digits exactly 9? $n=8;k=4; $ ${n+k-1\choose k-1} = {11 \choose 3} = 165$ b) For how many of the integers from part a) have all ...
1
vote
1answer
21 views

A modular congruence of higher degree

How can I prove that for all $n$ naturals and $p$ primes, $p \geq 3$, it holds that $(1+p)^{p^n}=1+p^{n+1} \pmod{p^{n+2}}$?
2
votes
1answer
52 views

Number of words not having a subword of length k with only one letter

Let $f_k(n,t)$ be the number of words of length $t$ over the alphabet $\mathcal{A} = \{1,\ldots,n\}$ such that no word contains $i^k$ as a substring for $i \in \mathcal{A}.$ I am looking to find the ...
0
votes
2answers
45 views

Prove $k\binom{n}{k} = n\binom{n-1}{k-1}$

The Problem: I want to prove $k\binom{n}{k} = n\binom{n-1}{k-1}$ algebraically My Work So Far: $n\binom{n-1}{k-1}$ $= n(\frac{(n-1)!}{(k-1)!(n-k+1)!})$ (By definition of $\binom{n-1}{k-1}$) $= ...
2
votes
2answers
49 views

Proving a Combinatorial Theorem

The Theorem My Problem I don't really understand how the $RHS$ counts the number of final positions for a $1$. I understand how summing all of these cases would be the same as counting all the ...
0
votes
0answers
20 views

Determine whether each function is one-to-one, onto, or both

$g:\mathbb Z \times \mathbb Z$ where $g$ is defined by $g(x)=x-1$ My guess is that this is onto and one-to-one. But is the correct interpretation of this problem that $g$ is a function of an ...
0
votes
1answer
40 views

Element of the set

Given the set $A=\lbrace 1,2,3,4\rbrace$, list all the elements of the set: $$\lbrace (a, n) \in A × \mathbb N: a = n\rbrace$$ Do I substitute each of the elements in to $a$?
-2
votes
1answer
57 views

In a game you receive three cards, ω, from a well-shuffled deck.. [closed]

In a game you receive three cards, ω, from a well-shuffled deck. You then receive \$30 per face card contained in the hand. That is if the hand contains 1 face card you get \$30, 2 you get \$80, 3 ...
1
vote
0answers
27 views

Contrapositive verifications

The contrapositive of: The product of an irrational number and a non-zero rational number is irrational. is: If the product of two numbers is rational, then it cannot be the case that one ...
-3
votes
2answers
41 views

Cardinality of Cartesian product of two sets [duplicate]

If the set $S$ has cardinality $\#S$ and the set $T$ has cardinality $\#T$, what is the cardinality of $S × T$? Ive tried $S=\{S\}, T=\{T\} = S \times T= \{S,T\}$ therefore the cardinality is $2$.
-1
votes
1answer
26 views

Trouble conceptualizing discrete math problem

I'm studying for discrete math and I'm looking for my professor's test problems and their solutions. There is one in particular I am having trouble conceptualizing, maybe someone could help me out. ...
0
votes
6answers
64 views

A = B, True or False

$$A = \{2m + 1\mid m \in \mathbb{Z}\}$$ $$B = \{2n + 3\mid n \in \mathbb{Z}\}$$ I've proved set equality such as $A = A \cap B$, by showing $A \subseteq A \cap B$, $A \cap B \subseteq A$ and ...