Questions on discrete mathematics generally: "the study of mathematical structures that are fundamentally discrete rather than continuous"
0
votes
0answers
3 views
Combinatorics - Letter Ordering
Considering the letters STUVWXYZ, how many strings can be formed with the letters Y, U, T and S appearing in that order but not necessarily together?
0
votes
1answer
24 views
Reflexivity, Transitivity, Symmertry of the square of an relation
$\def\p{\mathrel p}$If $\p$ is a relation on a set $A$, define $\p^2$ by $a \mathrel{\p^2} b$ if and only if there exists $c$ with $a \p c$ and $c \p b$.
If $p$ is reflexive/symmetric/transitive ...
0
votes
1answer
22 views
Symmetric, transitive and reflexive properties of a matrix
Say I had a relation A = matrix
| a b |
| c d |
where a,b,c,d elements of R (real numbers)
Where X is related to Y if and only if det(X) = det(Y) (where det(A) means ad-bc)
So I say its ...
1
vote
0answers
31 views
Find Total number of ways out of N Number taking K numbers every M interval
I have been stuck in a problem, that has thrown my brain out of the coding. This problem is at very high priority and I need the solution as early as possible. Problem is as :
There are exactly N ...
3
votes
1answer
31 views
Interpretation of generating function infinite product
Let $P$ denote the set of primes and let $s\in\{-1,1\}$. How can you interpret the coefficient of $x^n$ in the power series expansion of $$\prod_{p\in P} (1+sx^p)^s$$
for either choice of $s$?
I ...
2
votes
1answer
30 views
Linear equation of 4 variables
I'm stuck on this Math problem :
How many solutions does the equation
$x_{1} + x_{2} + 3x_{3} + x_{4} = k$
have, where $k$ and the $x_{i}$ are non-negative integers such that $x_{1} \geq 1$, ...
0
votes
1answer
20 views
Similar statements for expressions
Is there an easy way to find out which 3 are similar from the left and right side, it will be nice with some tricks to find it out, or if you have some rules that can be followed.
$$
{lg\,n +\frac12} ...
0
votes
0answers
9 views
simple trend measure/score
I am looking for a very simple (potentially ‘parameterisable’) measure to determine the trend of a discrete time series where the measurements are not necessarily equidistant. The output of the ...
0
votes
2answers
36 views
Can anyone solve this discrete math proof?
A hint given was: What are the possible remainders for n after dividing by 4? Break into the cases where you have each remainder.
3
votes
2answers
68 views
Proving that there are infinitely many prime numbers of the form $4k+3$
Anyone wanna help me solve this one? Been at it for a little bit but haven't really gotten anywhere..
1
vote
1answer
35 views
Determining if this relation is an equivalence relation
$$R=\left\{(f,g)\,\Bigg|\, \exists c\in\Bbb Z,\forall x\in\Bbb Z, \frac{f(x)}{g(c)}\le 2\right\}$$
I can show that this relation is reflexive by showing that $(f,f)$ is in $R$
and so $f(x)/f(c) \le ...
0
votes
2answers
46 views
Words counting problem
What is the number of words, which are made by shifting all lower case letters in the english alphabet and none of them contains any of the four subwords (null, one, two, three)?
1
vote
1answer
28 views
Generating functions combinatorical problem
In how many ways can you choose $10$ balls, of a pile of balls containing $10$ identical blue balls, $5$ identical green balls and $5$ identical red balls?
My solution (not sure if correct, would ...
0
votes
0answers
50 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 ...
1
vote
1answer
37 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
26 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
47 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
51 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
23 views
Discretizing a cosine function?
I'd like to start by noting that for some fixed natural $N$ basis functions for my system will be generated by $f(k,x)$ as defined and explained here or in numerous other sources:
$$f(k,x) = \sqrt2 ...
1
vote
3answers
73 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
49 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
54 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
24 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
73 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
55 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
20 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
67 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
8 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
48 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
60 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
20 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
48 views
+50
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
819 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
30 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
57 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
64 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 ...
5
votes
4answers
85 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
67 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
58 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. ...
