Questions on discrete mathematics generally: "the study of mathematical structures that are fundamentally discrete rather than continuous"
0
votes
0answers
32 views
graphs where distance between every two vertices is $\geq$2.
Are there any class of graphs where distance between every two vertices is $\geq$2.
I was wondering about the existence of such graphs. Because for counter examples I have Paths $P_n$.
Thank you ...
0
votes
0answers
16 views
Generating function question about arranging n objects with limitations
Generating functions question: There are n objects - rings, earring and bracelets. How many ways are there to arrange these objects, as the amount of earring is even and there are at most 4 bracelets.
...
1
vote
1answer
19 views
Prove that any circuit contains a cycle
This is a practice question (not HW)
Prove that any circuit in a graph must contain a cycle AND that any circuit that is not a cycle contains at least two cycles.
Note : This is for a first course ...
0
votes
1answer
41 views
Venn diagram related question
An analysis of the survey of $320$ school pupils highlighted the following facts:
• $50$ pupils live in New Town, travel to school by bus and have canteen lunch.
• $110$ pupils live in New Town ...
3
votes
2answers
44 views
Generating function: Find a closed form of $\sum_{k=0}^n (-3)^k(k+1)$
Find the closed form of $\sum_{k=0}^n (-3)^k(k+1)$.
So the generating function would be: $$A(x)=1-6x+18x^2-108x^3...$$ So what I did notice is that its closed form is perhaps some variation of ...
0
votes
0answers
8 views
Property of discrete Hartley transform?
I'd like to start by noting that for some fixed natural $N$ basis functions for my transform will be generated by $f(k,x)$ as defined and explained in Wikipedia:
$$f(k,x) = \sqrt2 \cos \left( \frac{2 ...
1
vote
1answer
57 views
number of ways to make $2.00
How many different ways can you make $2.00 using only 1 cent, 5 cent, 10 cent, and 25 cent pieces, and 1 and 2 dollar bills (there are 100 cents in a dollar)? I have worked out an equation:
$$p + 5n ...
0
votes
3answers
48 views
Pigeon holes principle
Let $P$ be a group that it's elements are 257 sentences in which only atomic sentences from $A,B,C$ exist (i.e. $A \iff B,\space\space A \wedge B \wedge C, \space\space...$) Show that there exists two ...
1
vote
2answers
52 views
Is my solution correct? Generating functions question: How many non-negative solutions does the equation $x_1+x_2+x_3+x_4+x_5+x_6=12$ have?
so we began studying this subject, and I tried solving this question: How many non-negative and whole ($\in \Bbb Z$) solutions does the equation $x_1+x_2+x_3+x_4+x_5+x_6=12$ have?
I would like to ...
1
vote
1answer
27 views
Reflexive, $s$, $t$ relations
$A=\{1,2,3,4\}$. Determine with reasons whether $R$ is reflexive, symmetric or transitive.
$R=\left\{(1,1),(1,2),(2,1),(2,2)\right\}$
How is this done?
Reflexive must contain every element to ...
3
votes
1answer
23 views
How do I apply partial fraction expansion on $\dfrac{K}{(a+bz^{-1})(x+yz)}$?
I want to apply partial fraction expansion on $\dfrac{K}{(a+bz^{-1})(x+yz)}$. I'm not able to do it in the standard way, because one term has $z^{-1}$ term and the other has $z$. What is the approach ...
2
votes
0answers
70 views
Prime numbers problem - discrete math
Show that natural numbers of the form $n^2+1$ are not divisible by primes of the form $p=4k-1$.
I can't really find a place to start.
Thank you very much in advance,
Yaron.
3
votes
2answers
51 views
Proving a statement about $k$-colouring of a graph
Prove that a graph is $k$-colourable iff its edges can be oriented in such a way that the resulting directed graph does not contain a path of length $k$.
It seems to me that the '$\Leftarrow$' ...
1
vote
1answer
19 views
How Entropy scales with sample size
For a discrete probability distribution, the entropy is defined as:
$$H(p) = \sum_i p(x_i) \log(p(x_i))$$
I'm trying to use the entropy as a measure of how "flat / noisy" vs. "peaked" a distribution ...
2
votes
5answers
66 views
Finding the number of non-neg integer solutions?
How would I find the number of non negative integer solutions to this problem?
$$x_1 + x_2 + x_3 + x_4 = 12$$ if $0 \leq x_1 \leq 2$.
0
votes
0answers
7 views
Closeness of a family of function under convolution.
I'm interested in functions defined over the non-negative integers that are a product of an exponential function and a polynomial. So a standard term of such a function is something like
$$
f(k) = ...
1
vote
2answers
46 views
Help solving recurrence relation, $a_n = 3a_{n-1} + 4a_{n-2} - 12a_{n-3}$
This is in my homework, and I am not sure how to go about this, I've read the book but I can't seem to grasp what to do. Help?
$$a_n = 3a_{n-1} + 4a_{n-2} - 12a_{n-3}$$
where $a_0 = 2$, $a_1 = -1$, ...
0
votes
1answer
36 views
find recursive solution $T(n)=2T(n/2)+n-1$
I want to solve this:
$$T(n) = 2 T\left(\frac{n}{2}\right) + n - 1 $$
I try :
\begin{align*}
n &= 2^m \\
T(2^m) &= 2T(2^{m-1}) + 2^m -1 \\
2 ^ m &= B \\
T(B) ...
5
votes
3answers
57 views
Solve the recursion, $a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$
Bring the following recursion relation to an explicit expression:
$$a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$$
$a_{0} = 0$, $a_1 = 1$, $a_2 = 2$
All the examples I have seen were with maximum 2 steps back ...
1
vote
1answer
19 views
Details about a Recurrence Relation problem.
I am trying to understand Recurrence Relations through the Towers of Hanoi example, and I am having trouble understanding the last step:
If $H_n$ is the number of moves it takes for n rings to be ...
0
votes
0answers
28 views
How do you calculate the angle of deflection of a plumb line towards a mountain?
How do you calculate the angle of deflection of plumb line being pulled down by the entire mass of earth, 5.89 x 10^24 kg and being pulled horizontally by the entire mass of mount everest, 6.399 x ...
2
votes
1answer
68 views
Solving a recurrence relation, $a_n = \sqrt{n(n+1)}a_{n-1} + n!(n+1)^{3/2}$
I'm trying to solve the following recurrence relation, but I have a problem with the factorial part. I would like to evaluate its particular solution.
I would like also to suggest a textbook for ...
1
vote
0answers
32 views
Expansion vs Sparsest cut
let $G=(V,E)$ and $S\subsetneq V$ then expansion of set $S$ is
$$\alpha(S)=\frac{|E(S,\overline{S})|}{\min\{|S|,|\overline{S}|)\}}$$
where $\bar{S}=V\setminus{S}$ and $E(S,\bar{S})$ are edges ...
13
votes
4answers
777 views
Are these 2 graphs isomorphic?
They meet the requirements of both having an = number of vertices (7)
They both have the same number of edges (9)
They both have 3 vertices of deg(2) and 4 of deg(3)
However, graph two has 2 ...
0
votes
1answer
29 views
Is there a formula to calculate the minimum height of an n-nary tree with L leaves?
I'm trying to figure out if there is a way to calculate the minimum height of an n-nary tree with L leaves. Is there such a formula?
0
votes
1answer
54 views
Prove that the existence of a bridge is an invariant
An invariant is a property $P$ that is shared by all isomorphic graphs. In other words, a property $P$ is an invariant provided that whenever $G_1$ and $G_2$ are isomorphic graphs, if $G_1$ satisfies ...
2
votes
3answers
58 views
Ball-counting problem (Combinatorics)
I would like some help on this problem, I just can't figure it out.
In a box there are 5 identical white balls, 7 identical green balls and 10 red balls (the red balls are numbered from 1 to 10). A ...
4
votes
4answers
78 views
Prove or disprove the following statements involving greatest common divisor
Help with prove or disproving either of these statements would be really appreciated, one or the other is fine, I just need a start or a solution to one and I'm sure I could probably figure the other ...
1
vote
3answers
49 views
Does the following graph have a Hamilton circuit?
A Hamilton circuit (or path) is a path that visits each vertex exactly once (except the start/end point) and ends at the starting point.
I've stared at this for quite a while and cannot find a ...
3
votes
4answers
65 views
Transitivity on Relations
I have a question concerning proving properties of Relations. The question is this: How would I go about proving that, if R and S (R and S both being different Relations) are transitive, then R union ...
0
votes
2answers
72 views
Show using induction (coupled linear recurrences)
Some homework help would be greatly appreciated, took a screenshot and made an image to make it easier to show and get help with.
(2) Consider the numbers defined recursively by $a_1=3$, $c_1=5$, ...
3
votes
2answers
56 views
How to show: if $b \mid a$ and $c \mid a$ and $\mathrm{gcd}(b,c) = 1$, then $bc \mid a$?
A little stumped on this problem, any help would be greatly appreciated.
Show that for all $a,b,c \in \mathbb{Z}$, if $b \mid a$ and $c \mid a$ and $\mathrm{gcd}(b,c) = 1$, then $bc \mid a$.
2
votes
0answers
38 views
Sum of squared/cube combinations [duplicate]
I was wondering if there is a closed formula for sum of cubed combinations. More precisely, I'd like to compute $$\sum_{k=1}^n \left ( \begin{array}{c}n\\k\end{array}\right )^3$$
Obviously, without ...
0
votes
0answers
22 views
The calculation of partitions p(n) [duplicate]
Can anybody help me with this in any sense.
Prove that $ p(n+2)+p(n)\ge 2p(n+1)$.
This question is from Biggs book on discrete maths but must have read the chapter so
many times and can't figure it ...
2
votes
0answers
20 views
functional dependencies
Consider the schema R(ABEFJK) with functional dependencies
{BE->JK, J->FA, F->B}.
I was told to find all the keys for this function this is what I did I dont know if im correct
...
0
votes
1answer
38 views
Partial linear relaxation yields an integer solution
Consider a binary integer program
\begin{align}
\min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\
\mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I ...
2
votes
1answer
43 views
Inclusion Exclusion Principle Problem
There are 28 people in your family consisting of 18 adults, 13 females, and 11 who have purple hair. There are 11 adult females, 6 of whom sport purple hair. There are 10 adults with purple hair. ...
1
vote
1answer
41 views
question about sets
I have this as a beggining to a question:
$A\subseteq Z^2$
$$
A = \left \langle \left ( 1,7 \right );\left ( 7,2 \right );(2,3) \right \rangle = \left \{ ...
1
vote
2answers
41 views
Trees with vertex set
I am having hard time understanding and solving the following question:
There are exactly three trees with vertex set {1,2,3}. Note that all these trees are paths; the only difference is which ...
2
votes
2answers
43 views
Let G be a graph in which every vertex has degree 2.
Is G necessarily a cycle?
I suspect not but I'm having hard time showing this.
Also,
Let be a tree. Prove that the average degree of a vertex in T is less than 2.
I know that the sum of degrees of ...
3
votes
2answers
41 views
Reducing Boolean expressions
Just learning mathematical proof writing and came upon this interesting question Writing an expression using logic.
$$(P \land Q \land \lnot R) \lor (P \land \lnot Q \land \lnot R) \lor (\lnot P ...
2
votes
1answer
29 views
Counting flower and committee questions
$1$) You want dozen roses. The florist has white, pink, red, and violet roses. How many possible ways could you make the order?
$2$) There are $35$ men and $15$ women. Committee needs to have four ...
2
votes
3answers
63 views
Use the Handshake Lemma to determine the number of edges in GK_n
In chess, a knight's move consists of two spaces either vertically or horizontally, followed by one space in the perpendicular direction. In this way, every knight's move results in an L shaped ...
3
votes
0answers
64 views
What is Algorithmic Graph Theory?
I'm an undergraduate and I signed up for a course next semester called Algorithmic Graph Theory. The course description doesn't give any details on the contents of the class, and there's no listing of ...
3
votes
2answers
26 views
Distribution of $n$ balls to 10 cells; Inclusion-exclusion problem
So I got another ( :[ ) problem I got stuck with. So before I get going with that, I would like to know if you know any places where I can learn the principles of these subjects (compositions, ...
1
vote
0answers
13 views
Discrete fractional fourier transform
I have written a code for producing matrix of fractional fourier transform with the help of eigen vectors of fourier transfom matrix. Does anyone know the elements of this matrix ( for example a 4 by ...
2
votes
3answers
54 views
Set Distributive Property Proof
Prove the distributive property for sets:
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
I'm not good with proofs but my understanding is that I have to prove 2 things:
(1) $A \cup (B ...
1
vote
3answers
109 views
Largest prime factor of 600851475143 [duplicate]
I'm trying to use a program to find the largest prime factor of 600851475143.
This is for Project Euler here: http://projecteuler.net/problem=3
I first attempted this with the code that goes through ...
-2
votes
2answers
60 views
Use the modular exponentiation algorithm to find $13^{277} \pmod {645}$
I need to solve this question using the modular exponentiation method.
-3
votes
1answer
28 views
Multiply $11010_2$ with $1011_2$ by working through each step of the multiplication algorithm
I need to multiply 11010 in its binary form with 1011 also in its binary form with the steps in detail.
