Questions on discrete mathematics generally: "the study of mathematical structures that are fundamentally discrete rather than continuous"
4
votes
4answers
157 views
What sort of math is this, and how would I solve it?
I'm taking a computer science class after several years away from school and so far I'm doing all right. However, we're covering some math and I'm drawing a blank on what to even call this concept, ...
4
votes
1answer
82 views
Showing all rationals in $(0,1)$ are sums of certain reciprocals by induction
Help me please to understand this exercise and probably to solve it.
Show that every positive rational number $\frac{m}{n}\in (0,1)$ can be represented as
$$\frac{m}{n} = \frac{1}{q_1} + ...
4
votes
1answer
2k views
What is the prerequisite knowledge for learning discrete math?
To become a better computer programmer I would like to take the time to learn discrete mathematics, but I am positive that I do not have the required existing knowledge to do so. So I would like to ...
4
votes
1answer
50 views
Let's denote $|A|=n, |B|=r$. Calculate the following sum: $\sum_{f:A \rightarrow B} |f(A)|$.
Let's denote $|A|=n, |B|=r$. Calculate the following sum:
$$\sum_{f:A \rightarrow B} |f(A)|$$
As I understand, we must calculate cardinality of images of all different functions.
I was able ...
4
votes
4answers
87 views
Am not following algebra in a proof - what am I missing here?
So I understand the majority of the proof, but am not fully following why consequently $n^2=9a^2$. Is this because we can take our value for $n$ (which is $n=3a$) and square it, which gives us $9a^2$? ...
4
votes
1answer
122 views
How to begin Combinatorial Proof
The question states to give a combinatorial proof for:
$$\sum_{k=1}^{n}k{n \choose k}^2 = n{{2n-1}\choose{n-1}}$$
Honestly, I have no idea how to begin. I want to do a two-way counting proof, ...
4
votes
1answer
57 views
How to prove there exist a cycle.
Given a graph $G = (V, E)$, where degree of each vertex is at least $d$ and $d ≥ 2$, there must be
a cycle of length at least $d + 1$ in $G$.
Given that $d\geq2$ that proves that no of edges is ...
4
votes
2answers
121 views
How many 9 letter strings are there that contain at least 3 vowels?
I'm studying for my exams and stuck on this one question.
The way I'm thinking of doing this is by:
$$26^9 - \binom{26}3-\binom{26}2-\binom{26}1-\binom{26}0= 5,429,503,676,728$$
But that seems ...
4
votes
3answers
42 views
Verify my solutions to counting problems
I'm pretty sure I know the answers to these problems, but still want to double check.
How many different ways are there of arranging all the letters of the string CALCULUSBOOK?
Solution: $12!$ since ...
4
votes
2answers
92 views
What is the cross-product of the null set with another set? [duplicate]
Supposing that, for example, we have two sets $A$ and $B$ where $\;A = \varnothing \;$ and $\,B = \{a,b\}$.
What is the result of the cross product of those sets?
My first intuition would be to say ...
4
votes
2answers
152 views
Vertices and edges of a cube are assigned natural numbers in a particular way; can the sum of the vertices equal the sum of the edges?
At the vertices of a cube are written 8 different natural numbers, and on each of its edges is written the greatest common divisor of the numbers at the endpoints of the edge.
Can the sum of ...
4
votes
1answer
197 views
Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?
This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi.
Are there any starting and ending configurations of $n$ disks on three pegs that are more than $2^n - ...
4
votes
1answer
183 views
Questions about generating non-biased random natural number
A. Several years before, I was solving some problems, and one of problems was something like
Explain how you can get non-biased random natural numbers between 1~10, with a six-sided(normal) dice.
...
4
votes
2answers
551 views
6 Women and 5 Men number of positions problem I don't understand
I have my discrete math final coming up on monday and am trying to figure out how to do a few problems. The one I am having the most problem with is just very confusing because I don't know how to go ...
4
votes
1answer
40 views
Finding maximum score in a “bubble pop” game
Consider the following game: there is a n×n field, where each cell is randomly coloured in one of m colours. Let a group of cells be a set of same-coloured cells s.t. every cell in a group has at ...
4
votes
1answer
60 views
Knight tour problem??
Consider an n × n chess board. For what values of n is it possible to find a knight’s tour around the
board which uses every possible move just once (in one direction or the other).
Here on what ...
4
votes
2answers
129 views
How many ways can you create a password of 10 characters long that has at least one lowercase letter (a-z) and at least one number ($0-9$)?
Suppose you want to generate a password using ASCII characters ($128$ characters.)How many ways can you create a password of 10 characters long that has at least one lowercase letter (a-z) and at ...
4
votes
3answers
178 views
4
votes
2answers
140 views
Combinatorial Proof Of Binomial Double Counting
Let $a$, $b$, $c$ and $n$ be non-negative integers.
By counting the number of committees
consisting of $n$ sentient beings that can
be chosen from a pool of $a$ kittens, $b$
crocodiles and $c$ emus ...
4
votes
2answers
312 views
Problem about $n$ six-sided dice and the sum of the values
(AHSME 1994) When $n$ standard six-sided dice are rolled, the probability of
obtaining a sum of 1994 is greater than zero and is the same as the probability of
obtaining a sum of $S$. What is the ...
4
votes
1answer
883 views
Find a big-O estimate for $f(n)=2f(\sqrt{n})+\log n$
While self-studying Discrete Mathematics, I found the following question in the book "Discrete Mathematics and Its Applications" from Rosen:
Suppose the function $f$ satisfies the recurrence ...
4
votes
1answer
91 views
question about solving recurrences
I am self-studying Discrete Mathematics. Here is one question I am suppose to solve.
a) $x_{n+1}=2x_{n}+1,x_{1}=2$
When I tried to find the homogeneous solution to $x_{n+1}=2x_{n}$ I found ...
4
votes
1answer
203 views
Prove parity of binomial coefficient
The task is to find the parity of ${2n\choose 2k+1}$ where $n,k\in\mathbb{N}$. How can I do that?
4
votes
2answers
148 views
Does this generalisation of Latin squares have a name?
I am interested in looking at $n\times n$ tableaux (or matrices) in which (WLOG) each integer in $\{ 1, 2, \ldots, n \}$ occurs exactly $n$ times. This is a generalisation of a Latin (or even ...
4
votes
2answers
1k views
Set Theory: Proving Statements About Sets
Let A, B, and C be arbitrary sets taken from the positive integers.
I have to prove or disprove that: A ∩ B ∩ C = ∅, then (A ⊆ ~B) or (A ⊆ ~C)
Here is my disproof using a counterexample:
If A = {} ...
4
votes
2answers
47 views
Modular Exponentiation
Give numbers $x,y,z$ such that $y \equiv z \pmod{5}$ but $x^y \not\equiv x^z \pmod{5}$
I'm just learning modular arithmetic and this questions has me puzzled. Any help with explanation would be ...
4
votes
2answers
48 views
Probability that a string of $5$ characters from set$\{a,b,c,d,e,f\}$ contains exactly one '$a$', given that it contains at least one vowel
This is a past paper exam question.
It doesn't have a mark scheme, so I was hoping somebody could check this answer for me. It's non-calculator, but I don't expect that affects the method used.
My ...
4
votes
2answers
136 views
Real World Applications of Edge Coloring?
Does anyone have any real world applications for edge coloring in graphs?
4
votes
1answer
61 views
Stirling numbers, binomial coefficients
Could you help me prove the following:
$$\left\{n\atop k\right\} = \frac{1}{k!} \cdot \sum^{k}_{j=0} {k\choose j} \cdot j^{n} \cdot (-1)^{k-j}$$
It looks very scary to me. I've looked for it in ...
4
votes
2answers
224 views
Discrete math: How many solutions are there?
I wrote a prolog program to print out all of the possible solutions for the following problem:
You have eight colored balls: 1 black, 2 white, 2 red and 3 green.
The balls in positions 2 and 3 are ...
4
votes
4answers
425 views
Big-O notation Basics, is it related to derivatives?
I am having the hardest time with Big-O notation (I am using this Rosen book for the class I am in).
On the surface, Big-O reminds me of derivatives, rate of change and what not; is this proper ...
4
votes
2answers
109 views
How to compute the closure of a set of binary strings in term of the “AND” and “OR” operators?
Given a set of $n$ binary strings of length $m$, how many binary strings at least should we add to the set to make sure that the binary "AND" and "OR" operators are closed on the set? The output of ...
4
votes
3answers
341 views
Stirling numbers of the second kind on Multiset
Stirling numbers of the second kind S(n, k) count the number of ways to partition a set of n elements into k nonempty subsets.What if there were duplicate elements in the set?That is,the set is a ...
4
votes
2answers
52 views
Maximal Smallest Number
Ran into a interesting problem which I have no idea how to solve but have the desire to.
Let a and b be two positive real numbers and let $m$(a,b) be the smallest of the three numbers $a,$ $1/b$ ...
4
votes
1answer
39 views
$ (n-7)^2$ is $\Theta(n^2) $ Prove if it's true
$$ (n-7)^2 \, \text{is} \, \Theta(n^2) $$
Is this correct?
So far I have:
$ (n-7)^2 \, \text{is} \, O(n^2) \\
n^2 -14n +49 \, \text{is} \, O(n^2) \\
\begin{align} n^2 -14n +49 & \le \, C ...
4
votes
1answer
77 views
Necessary and sufficient conditions that the difference of two quadratic equations has no solutions in $\mathbb{N}$
Suppose you have an equation of the form
$$
a(n^2 - m^2) + b(n-m) + c = 0
$$
With given integers $a$, $b$ and $c$.
Is there a necessary and sufficient condition that the equation has no solutions ...
4
votes
2answers
94 views
Prove $((n+1)!)^n < 2!\cdot4!\cdots(2n)!$
so I know I need to prove this via induction, but I am somewhat stuck. Here is what I have does so far.
Let $p(n) = (n+1)!^n \le 2!\cdot4!\cdot\ldots\cdot(2n)!$
$p(2) = 3!^2\le 2!\cdot4!$
Assume ...
4
votes
3answers
85 views
Convergence - $\log(2)$
Denote
$$
t(n) := \frac{|\{ \sigma \in S_n \mid \sigma \text{ has a cycle of length > $\frac n 2$} \}|}{|S_n|}
$$
Then $\lim_{n \rightarrow \infty} t(n) = \log 2$. Can someone help ? I already know ...
4
votes
1answer
147 views
Optimal Yahtzee (Dice roll) decisions: Probability and weighting choices
I'm a senior in computer science, and I have a hobby of taking on little projects that I find interesting. My current one is a Yahtzee optimal play solver. One would enter their current roll, and it ...
4
votes
3answers
87 views
How to prove $ \space B-(A-C) \subseteq (B-C) \cup A \Leftrightarrow B \cap C \subseteq A $
Let $A,B$ and $C$ be any sets.
To prove $ \space B-(A-C) \subseteq (B-C) \cup A \Leftrightarrow B \cap C \subseteq A \space$ I began proving the implication $ \space B-(A-C) \subseteq (B-C) \cup A ...
4
votes
3answers
117 views
How do you solve this recurrence?
I have been trying to practice recurrence relations that can be solved by the master theorem and came across this.
Now the $4^{\textrm{th}}$ problem in that file is :
$$T(n) = 2^n ...
4
votes
1answer
155 views
Efficiently evaluating the Motzkin numbers
So I made an error on the question here: $T_N = 1 + \sum_{k=0}^{N-2}{(N-1-k)T_k}$
The correct formula I'm trying to solve is more complicated and as follows:
$$T_0 = T_1 = 1 $$
$$T_{N+1} = T_N + ...
4
votes
1answer
672 views
Quick sort algorithm average case complexity analysis
This is for self-study. This question is from Kenneth Rosen's "Discrete Mathematics and Its Applications".
The quick sort is an efficient algorithm. To sort $a_1,a_2,\ldots,a_n$, this algorithm ...
4
votes
2answers
225 views
Counting number of ways to split papers between four people
here's a question I had in an exam today:
Four people are checking 230 exams. In how many ways can you split the
papers between the four of them if you want each one to check at least
15?
...
4
votes
1answer
105 views
Convergence of a sequence of partial binomial sums
I have a sequence
$$a_n = (1-p)^n \sum_{\frac{n}{2}\le k \le n} \binom{n}{k} \left( \frac{p}{1-p} \right)^k.$$
I want to show that $a_n\to 0$ when $n\to\infty$ if $0\le p < \frac{1}{2}$. Here's a ...
4
votes
2answers
339 views
Number of combinations with repetitions (Constrained)
I would like to calculate the number of integral solutions to the equation
$$x_1 + x_2 + \cdots + x_n = k$$
where
$$a_1 \le x_1 \le b_1, a_2 \le x_2 \le b_2, a_3 \le x_3 \le b_3$$
and so on.
...
4
votes
1answer
182 views
Random permutations of Z_n
In http://www.springerlink.com/content/y19u81675243r237/fulltext.pdf, the author states the following without proof (equation 3.1):
Consider a random permutation $\pi$ of $\mathbb{Z}_n$. What is the ...
4
votes
1answer
301 views
Find the number of pairwise coprime triples of positive integers (a,b,c) with a<b<c
Find the number of pairwise coprime triples of positive integers $a,b,c$ with $a\lt b\lt c$ such that
a|bc−31, b|ca−31, c|ab−31
Details ...
4
votes
2answers
65 views
Given $f:\Bbb N\to P(\Bbb N)$, present two sets of naturals not in the image of $f$.
Let $f: \Bbb N \to P(\Bbb N)$. Present 2 different sets of natural numbers A, B that are not in Im(f)
What I did:
First idea:
I defined an injective function f that takes each n and returns it's ...
4
votes
1answer
125 views
to find the distance between vertices in power graphs of cycles
i am trying to find the power graphs of cycles $C_n$ and then calculation of distances between vertices. for cycles $C_n$ we can find power graphs upto power greatest integer function of n/2. Square ...
