what
#discrete-math
stray reef
what
what
what
what
what
what the fuck did you just say
what the fuck was that about
faint narwhal
It's like assigning a variable a name while coding
stray reef
"=" means "these two things are one and the same"
what other symbol could you possibly use
except maybe := to emphasize that this is a definition
unreal berry
is the name of a set that is {}
faint narwhal
That's what they use in programming too lmao
stray reef
what the fuck was this firing squad thing though
unreal berry
nah I can just have the definition in brackets?
unreal berry
I'd rather use a shitty method that I know works than a good method that I can't understand(I do now though, thanks teacher)
Anyways, I have another question for you from an examination.
stray reef
what
unreal berry
I will translate it for you.
unreal berry
same shit different smell.
stray reef
is the concept of giving names to things so alien to you
unreal berry
no it's a cricle apparently.
stray reef
it's a set
a set of points
that just so happens to be a circle due to exactly the kind of set that it is
unreal berry
so C = (x,y)?
stray reef
no
unreal berry
then it's crap.
stray reef
C = the set of all points (x,y) such that x^2+y^2=1
no, YOU'RE crap. quit it with this defeatist attitude.
learn english mathematician
and this shit
cut it
unreal berry
anyways, I think I got it now.
the other question. I will translate it.
Basically, I need to redefine f(but actually not, and A is supposed to be {1,2,3,4} not {1,2,3,4,5} cus it appeared as the former during the actual examination) so that h becomes bijective.
if it says C = f(A), does that mean the set C can be any subset of the set A?
stray reef
no, that's not what that means at all
unreal berry
then what does it mean?
stray reef
f(A) is the set of all points of the form f(x), where x is taken from A
unreal berry
so C can be ANY of the x points in the set A?
unreal berry
so C is all points in A at the same time?
stray reef
NO
A SET IS AN OBJECT IN ITS OWN RIGHT, AND YOUR CONTINUED REFUSAL TO ACKNOWLEDGE THAT IS DRIVING ME CRAZY
unreal berry
so C = {1,2,3,4}?
stray reef
NO!
stray reef
no, C is not {a,b,c,d}
stray reef
that's a different f, then
unreal berry
but f(A) always produced {a,b,c,d}
stray reef
YOUR CONTINUED REFUSAL TO ACKNOWLEDGE THE MOST SIMPLE AND OBVIOUS OF THINGS HAS DONE EXACTLY NOTHING TO HELP ME BE MORE FUCKING ATTENTIVE WHEN READING YOUR DAMN SCREENSHOT
unreal berry
it was never redefined.
when I read it the f is literally the same in the beginning as after it is redefined.
this question isn't even the same as the one that appears at the examination.
nor does it make sense even if it did.
cerulean ore
what is path matrix?
stray reef
context?
cerulean ore
Graph theory
maiden forge
Does anyone know if there's a way to find a bijection from Q to N without the fact that Q is countable
faint narwhal
1/1 goes to 1
1/2 goes to 2
2/1 goes to 3
2/3 goes to 4
3/2 goes to 5
-1 goes to 6
want me to keep going
maiden forge
ah yes
I see
are you sure there would be an explicit formula for this that worked properly? what would it be explicitly, because I think it's a bit more complicated than that
I think you definitely have to use a composition
proven shard
There is an explicit recursive formula for a different bijection
dull tinsel
what would the graph be if L = ALL strings in {a, b} with no conditions? even empty strings
would it be this?
hearty crane
@dull tinsel all strings in {a,b} could just be start node = accept state, with a,b looping back to itself
just one node
unreal berry
Looking for someone who can help me understand a question(not solve it)
pale epoch
reef thistle
@unreal berry ?
obtuse lance
no, they're onnly asking you if that's a true statement. just go one line up and you'll see ARB is true iff |A|=|B|.
it's basically a way of asking you if |{a,b}| = |{b,c}| or not
it does happen to be an equivalence relation though, but none of those questions are actually asking that
@unreal berry
unreal berry
|{a,b}| = |{b,c}| isn't equivalent, right?
cus I don't know what A and B actually contains.
stray reef
@unreal berry a, b and c are just three objects, nothing else
they might as well just be the letters a, b and c
|{a,b}| is the number of elements in {a,b}
which is 2
unreal berry
so 2 -2 = 0
2= 2
| blabla | means number of elements
so a. is true b. false and c. false?
stray reef
???
unreal berry
reflexiv, anti-symmetric and transitive
stray reef
no, those are the axioms of a PARTIAL ORDER relation
which is a special type of binary relation
unreal berry
ok so what type of relation was the one above?
was it for checking numbers of elements in a set?
I kind of want to make a P(x)
stray reef
...
what
P(x)? what?
whether R belongs to a class of relations with a special name is of no concern here
unreal berry
yeah java and C
stray reef
yeah so
stray reef
you know what strings are in those languages
unreal berry
yeah
stray reef
sequences of characters
unreal berry
yuhp
stray reef
p much the same thing here
unreal berry
ok
stray reef
except that your strings here can only have the letters a and b
bc that's your alphabet
stray reef
correct conclusion wrong reasoning
ab R ba and ba R ab are both true
but ab != ba
THAT'S what disproves antisymmetry
unreal berry
how is ba <= ab?
stray reef
$2 \leq 2$
vital dewBOT
Ann:
unreal berry
right since we are checking length
but if that's the case, then shouldn't ab = ba?
since same length
stray reef
no look
IF your relation was antisym
THEN you could conclude that ab = ba
but ab and ba are clearly not the same string
so the relation is NOT antisym
there is literally nothing else to it
unreal berry
string.equals(string) is different from method string.compareto(string)?
unreal berry
one checks for same string while the others checks length of chars?
stray reef
,,,,,
no
look
you are overthinking this
you have a relation
again called R
defined as
s R t if and only if length(s) <= length(t)
the definition of an antisymmetric relation is
stray reef
NO!
FOR ALL s and t, IF s R t and t R s, THEN s = t
IF this criterion is met
THEN we say R is ANTISYMMETRIC
unreal berry
if s R t and t R s AND s = t? then true
stray reef
NO!
unreal berry
so FOR ALL s and t, IF s R t and t R s -> s = t
unreal berry
I mean I know how AS works, but there is not THEN s = t
all three conditions have to be met.
for it to be AS
stray reef
no
you don't know how AS works
there are not three conditions
there is one condition
which is an IF statement
but i guess i'm just not able to explain to you what that actually means
stray reef
no
that's not the definition
not even close to it
we say that a definition is symmetric if, for all a and b, IF a R b, THEN b R a
but i guess i'm just not able to explain to you what that actually means
unreal berry
then if IF a R b, THEN b R a is the same as IF b R a, THEN a R b then wouldn't that work just like the AS one?
anyways
I am going to guess no.
since 1 + 0 is not even
reef thistle
let's use the definition of a partial order
unreal berry
3 <= 4 but 4 !<= 3
so it's not AS
so it's not POSET
cus not R,AS,T
right?
speaking of n R n
why so?
going to go no because of the same reason as above.
stray reef
3 <= 4 but 4 !<= 3
no
first off
stop denoting it as <= when it isn't
second, 3 R 4 is false
as is 4 R 3
unreal berry
<_>?
stray reef
3 <= 4 but 4 !<= 3
this proves nothing
to prove that R is NOT antisym, you need to find two points a and b such that a R b and b R a but a != b
unreal berry
I see.
unreal berry
but wouldn't all relations always be AS then?
unreal berry
show me an example then with Z
stray reef
in problem 19.2
m R n iff m+n is even
this fails to be antisym
0 R 2 because 0+2=2, and 2 is even
2 R 0 because 2+0 = 2, and 2 is even
but 0 != 2
therefore R is not antisym
unreal berry
erm you have to find IF a R b and b R a THEN a !=b
stray reef
hhhhh
do you know what the negation of p -> q is
it's not p -> not q
it's p & not q
no
NO
$\neg(p \to q)$ isn't $q \to p$!!!!!!!!!!!!
vital dewBOT
Ann:
unreal berry
-(-pVq) = -q AND p
stray reef
well there you have it
$\neg(\forall a, b (a R b \land b R a \to a=b)$ is $\exists a, b (a R b \land b R a \land a \neq b)$
vital dewBOT
Ann:
unreal berry
would it be possible to say p AND -q too?
unreal berry
then -p -> q? is the same as -q -> p right?
stray reef
no, $(\neg p) \to q$ and $q \to p$ are not the same.
vital dewBOT
Ann:
reef thistle
you might be looking for the contrapositive
stray reef
neither are $\neg(p \to q)$ and $q \to p$.
vital dewBOT
Ann:
stray reef
@reef thistle can you take this over
reef thistle
okay can you show it?
reef thistle
but this isn't a counterexample for antisymmetric
unreal berry
ann said that if both are true, then m = n
and I said that AS will always be true
since then only way to show a contradiction is m != n
and that can never be true if m <= n AND n <= m are true
since m = n must ALWAYS be true
reef thistle
antisymmetric is a global property
you need to check that it works for everything for it to work
and we only need a local counterexample to stop it
unreal berry
local counterexample? global property?
in problem 19.2
m R n iff m+n is even
this fails to be antisym
0 R 2 because 0+2=2, and 2 is even
2 R 0 because 2+0 = 2, and 2 is even
but 0 != 2
therefore R is not antisym
but we are using <= not even
reef thistle
what ann said yeah
unreal berry
yeah but she used + not <=
reef thistle
what do you mean there "<= not even"?
Let's not use <= anywhere
there's no <= anywhere
let's just use R
unreal berry
ok soz nvm is +
then why do they keep going on about < <= and =
if we are just going to use whatever appears.
unreal berry
well
reef thistle
we don't want to bring preconceived notions of <= into this
unreal berry
m R m
oh wait m + n is even
right
so 2 + 4 and 4 + 2 is even but they are not equal
so it's not AS
reef thistle
that's sort of the idea
unreal berry
ok
well they could be negative
so still not AS
-1^2 and 1^2
hmmm.
is this good?
unreal berry
() this?
unreal berry
reef thistle
erm
unreal berry
cus 0,1 can go to 1,0?
maybe we can just add/change one number at a time
maybe that is the idea.
unreal berry
reef thistle
yeah that's all
unreal berry
did we solve the question?
reef thistle
yeah that's the hasse diagram
unreal berry
a = c and b = d?
unreal berry
sour arrow
@unreal berry
Still looking for it?
unreal berry
@sour arrow nah I am good. is the hesse diagram right? if not, plz tell me if you feel like it
sour arrow
The picture there is not correct no
@unreal berry
A line upwards represents "greater than", which in this case means "divides". 4 does not divide (1,4)
unreal berry
@sour arrow so do I need to remove 2 4 8 and 1?
sour arrow
(1,4) is not an element of the set and shouldn't be in the diagram
1,2,4,8 should be the only things there
unreal berry
@sour arrow what about (1,2) and (1,8)?
clever nacelle
Does anyone know where I can find resources to answer this questions. It is not covered in the Discrete book I am going over
a. 1 + 01
b. 1*01* + 01
c. {00, 10, 01}
d. {Λ, 0, 1, 00, 11, … 0n, 1n, (01)n, …}
e. All strings which have an odd number of 1’s```
cerulean sentinel
I've got hw to make a total order out of the set of polynomials in two variables w/ integer coefficients
Should it be enough to order them by total degree (aRb <=> total degree of a >= total degree of b) ?
stray reef
no, that fails to be antisym
clever nacelle
Does anyone know the concepts covered in my post
pastel wolf
$$\exists x \exists y \exists z(P(x, y) \land P(z, y) \land P(x, z) \land \neg P(z, x))$$
vital dewBOT
SpiderString:
pastel wolf
`Under each of these interpretations, is this formula true? R is the relationship corresponding to P."
$$U=\mathbb{N}, R={(x, x+1) : x \geq 0}$$
vital dewBOT
SpiderString:
pastel wolf
I'm not even sure what the relationship it's specifying is supposed to mean, can someone clarify?
<@&286206848099549185> Anyone who can just give me an idea of how to start would be appreciated
neat siren
if i split an n sized array into bins of sqrt(n) size then sort each bin, is that O(sqrt(n))?
dapper rose
Are there naturals x,y,z such that y=x+1=z+1, z=x+1, and x!=z+1? @pastel wolf
pastel wolf
But then where does the x>=0 part come in? Sure, it's the set of naturals so that'd be implied in your interpretation but then why put it anyway?
I was thinking it might be a way of writing the predicate {(x, y) : x>=0 and y>=1}, but I'm not sure. I guess I'm just asking if you're sure that's right and if so, what's the rule behind it
clear canopy
Anyone know much about the orchard visibility problem? Need help with the RHS of this inequality
Where s is the orchard radius and rho is the tree radius
floral wind
How can I rewrite
$ \sum_{n=1}^{k} (k - 1) $
vital dewBOT
JohnkaS:
stray reef
as written, $\sum_{n=1}^{k} (k-1) = k(k-1)$
vital dewBOT
Ann:
stray reef
did you really mean that and not $\sum_{k=1}^n (k-1)$?
vital dewBOT
Ann:
floral wind
yes i meant that my bad
stray reef
then that's $\frac12n(n-1)$.
vital dewBOT
Ann:
outer shard
I'm lacking in a fundamental understanding of these concepts, and I'd like to know what these represent and how to prove that a certain function posses a Big Theta, O, or Omega of a given value. So, my question is what do Big O, Theta, and Omega represent? And how would one prove that a function does or doesnt have a Big O, Theta, or Omega of a given value?
static pagoda
in a string of 10 bit binary, how many possible strings are there of 4 1's when non of them are touching
and then a second part of at most 4 1's
shut rivet
olive dragon
I wish I could help man, I usually post my questions on Chegg to but my recent questions are left un answered for days
I am working on a project called "Paper Coding Activity" with Big-O estimate calculations
So far I have did the paper coding exercise and I'm stuck with Big-O estimate calculations
"If the floor was of size n-by- n, give a big-Θ estimate for the length of the program needed to paint the same pattern. Explain how you derived your estimate."
scarlet rose
what'd u get for ur big O
olive dragon
I don't know how to calculate the big-O estimate for this.
scarlet rose
what's an upper bound for the number of commands/operations ur gonna have to do?
given that your checkboard is nxn
olive dragon
Upper bound is big-Omega and lower bound is big-O correct?
olive dragon
I wish I learned this earlier. My project is due in an hour
scarlet rose
hm, it's unfortunate you didn't begin earlier
read the definitions, if your book has some examples, that should help
olive dragon
Does this work for that first big-O estimate?
stray reef
$n^2 \leq 4n$?!
vital dewBOT
Ann:
vital dewBOT
TGroup:
olive dragon
sorry for the confusion
scarlet rose
how are you getting this as big O estimate
scarlet rose
do you know what big O estimate is? I am also confused by n x n <= 4n
scarlet rose
in your picture that is what it says
olive dragon
4n is coming from 4 commands which is where the four n's coming from
n+n+n+n are basically the 4 commands
scarlet rose
why do you have 4n commands?
olive dragon
the C value doesn't really matter
scarlet rose
in the example, how many commands does it take for n=4?
scarlet rose
why do you have 4n commands though
if i have 50x50 checkerboard, i have 2500 squares. just the painting of half the squares consists of 1250 commands, where 4*50 is clearly much less
Clearly, 4n is not an upper bound
olive dragon
Its too late for this, Lets discuss it another time
I clearly need further knowledge of this material
Thank you for all your help!
scarlet rose
np, gl
dull tinsel
I need help with making DFAs (direct finite automota) for the following situations.
Given the alphabet Σ{a, b}, I need to make a DFA graph/model/diagram for Σ (all possible inputs) and Σ - lambda (all possible inputs EXCEPT an empty string).**
So this is the DFA diagram I made for Σ*. Since even an empty string is allowed as input, I put the final state right after the initial entering arrow. If there are any letters, so be it, but an empty string is good enough to reach the state.
Is my reasoning correct? Is this good?
For the next one (which I am more unsure of), Σ* - lambda, this is what I got: This time, the final state is at S_1 and not S_0 since an empty string is not valid input. Only if the string contains a and b should the final stage be reached. I have a feeling that I am missing something though. Should there be a "death" state for an empty string? Or is that not needed since an empty string has no contents inside of it?
and yes, the ",b" got cut off in my image above for the loop, my bad
opal crescent
second one is fine
Are you really sure for the first one though?
feels like only the empty string would be accepted tbh
dull tinsel
I am not sure, that is why I am posting here
opal crescent
the problem is, when the word has at least a letter, you get stuck in state 1
never getting back to state 0, ie doesn't get accepted
dull tinsel
Oh! That makes sense. Thanks
ruby hull
Anyone has permutation and combinations knowledge?
robust mango
yes
ruby hull
When i use each one of these?
I know the difference between the right and left column but not the rows
mint salmon
I'm trying to prove a logical implication, but I'm stuck. M,N,P are sets and N ⊆ P. This is what I have so far:
` ¬∀x : x ∈ M ⇒ x ∉ N ⟹ ∃x ∈ M : x ∈ P
¬∀x : x ∈ M ⇒ x ∉ N
⟺ ¬∀x : x ∉ M ∨ x ∉ N
⟺ ∀x : x ∈ M ∧ x ∈ N
⟺ ∀x : x ∈ M ∩ N
⟺ ... more steps ...
⟺ ∃x : x ∈ M ∩ P
⟺ ∃x : x ∈ M ∧ x ∈ P
⟺ ∃x ∈ M : x ∈ P`
I think that I need to use a property of ⊆ in order to progress further
stray reef
hang on, what are you proving exactly
mint salmon
well, unless I'm not reading it correctly, I'm proving that ¬∀x : x ∈ M ⇒ x ∉ N logically implies ∃x ∈ M : x ∈ P
mint salmon
my mistake
stray reef
this is... mighty overcomplicated though
like why not go from $\neg \forall x: x \in M \Rightarrow x \notin N$ to $\exists x: x \in M \land x \in N$
vital dewBOT
Ann:
vital dewBOT
Ann:
stray reef
that's the defn of $N \subseteq P$
vital dewBOT
Ann:
mint salmon
I knew I was doing something wrong when it started getting longer and longer
I didn't negate the quantor properly
stray reef
quantifier
mint salmon
ah right; I didn't know the english word
dull tinsel
hey, sorry if this is a stupid question. so for direct finite automota diagrams, there are multiple ways to draw the diagram so they show how to deal with a language, right? there isn't just "one" right way, depending on the complexity of the language?
static pagoda
how do you count cases where 2 parts of a strings arent touching?
granite wyvern
Hi does anyone here have experience with ramsey theory?
Because I have a problem that I can't quite figure out
faint narwhal
granite wyvern
Can you conjecture and prove a value for R(Cn,C3)
faint narwhal
What does Cn mean
granite wyvern
In general R(s,t) =n means the Minimum n such that any 2 coloring on Kn must have either a complete subgraph Ks whose edges are monochromatic in color 1 or a complete subgraph Kq whose edges are monochromatic in color 2
faint narwhal
So you want R(n,3)?
granite wyvern
yea basically
slender dome
hi
i want to prove this
where R and S are binary relations
but im stuck on (y,x)cR^-1
oh, didnt see that room
thanks
lean creek
@granite wyvern are we in the same class lol
This is one of my homework problems for this week
on rereading, well, hm, basically the same problem I think
bounds are here
analog sonnet
Ramsey 
dapper rose
<@&286206848099549185>
runic mauve
is anyone here able to double check for me that 43 is the only prime for which 5p+1 is a perfect cube? i think i did this problem correctly but for some reason i was expecting an infinite number of them
the original problem was asking to find all primes that when written as 5p+1 are a perfect square and prove that there are no others after that
faint narwhal
Uh, perfect cube or perfect square?
runic mauve
cube
so like 43(5) + 1 = 216 = 6^3
im pretty sure that's the only answer but im just double checking
faint narwhal
I mean, do you have a proof that there are no others
runic mauve
well i think i might but i'm just not entirely sure if i went a direction that would allow me to get that proof
ya know
faint narwhal
Well then I can just check your proof
runic mauve
well the proof relies on the rest of the problem but ill do my best to put it here
5p + 1 = x^3 => 5p = x^3 - 1 = (x - 1)(x^2 + x + 1)
so you now have 4 cases:
- 5 = (x - 1) and p = (x^2 + x + 1)
- p = (x - 1) and 5 = (x^2 + x + 1)
- 5p = (x - 1) and 1 = (x^2 + x + 1)
- 1 = (x - 1) and 5p = (x^2 + x + 1)
sorry didnt mean to send early
but this is the direction and then i rule out 3 of the four and the only case left works out so that p = 43
all the ones i rule out are cases where p is a fraction or decimal or smth
since primes have to be whole numbers
this seemed to be the way the professor nudged us before but im not 100% sure
faint narwhal
Yeah this seems right
runic mauve
ok sweet
so ruling out all but #1 is correct then i guess
for some reason i thought i heard him say we only rule 1 out but i only had like 15 seconds to talk to him about this question
because the original wording was this "Find, with proof that there are no others, all prime numbers p, for which 5p + 1 is a perfect cube (i.e. the third power of a positive integer)."
weary tiger
can someone help explain this? I got the first part (I think) but the rest is confusing
analog sonnet
I need a rundown of all the notation please
weary tiger
sure
The program will have two stages. In the training stage, the program will compute the relevant log
probabilities over the training set. In the testing stage, it computes the classification attribute over
each instance in the test set and tallies the accuracy, precision, and recall.
The log probabilities is the negative log probability of a 0.1 Laplacian correction of the relevant
frequencies. That is:
In the formulas above T is the training set; |T| is the number of instances in T; and #T (φ) is the
number of instances in T that satisfy condition φ.
In the testing stage, for each instance X.a1 = u1 . . . X.a5 = u5 in the test set, compute the value of
the sum
In the formulas above T is the training set; |T| is the number of instances in T; and #T (φ) is the
number of instances in T that satisfy condition φ.
In the testing stage, for each instance X.a1 = u1 . . . X.a5 = u5 in the test set, compute the value of
the sum
for v = 1, 2, 3; choose the value of v with the smallest sum; and compare it to the labeled value
X.a6.
It is altogether unlikely that you will ever run into a tie, but if you do, break it arbitrarily.
Format for verbose output
lp(X.a6=1) lp(X.a6=2) lp(X.a6=3)
lp(X.a1=1|X.a6=1) lp(X.a1=2|X.a6=1) lp(X.a1=3|X.a6=1) lp(X.a1=4|X.a6=1)
lp(X.a1=1|X.a6=2) lp(X.a1=2|X.a6=2) lp(X.a1=3|X.a6=2) lp(X.a1=4|X.a6=2)
lp(X.a1=1|X.a6=3) lp(X.a1=2|X.a6=3) lp(X.a1=3|X.a6=3) lp(X.a1=4|X.a6=3)
lp(X.a2=1|X.a6=1) lp(X.a2=2|X.a6=1) lp(X.a2=3|X.a6=1) lp(X.a2=4|X.a6=1)
lp(X.a2=1|X.a6=2) lp(X.a2=2|X.a6=2) lp(X.a2=3|X.a6=2) lp(X.a2=4|X.a6=2)
lp(X.a2=1|X.a6=3) lp(X.a2=2|X.a6=3) lp(X.a2=3|X.a6=3) lp(X.a2=4|X.a6=3)
lp(X.a3=1|X.a6=1) lp(X.a3=2|X.a6=1) lp(X.a3=3|X.a6=1) lp(X.a3=4|X.a6=1)
lp(X.a3=1|X.a6=2) lp(X.a3=2|X.a6=2) lp(X.a3=3|X.a6=2) lp(X.a3=4|X.a6=2)
lp(X.a3=1|X.a6=3) lp(X.a3=2|X.a6=3) lp(X.a3=3|X.a6=3) lp(X.a3=4|X.a6=3)
I've managed to calculate some of the values for the training bit
int PredictSeenInTesting = getPredictCount(predict);
double Numerator = (double)PredictSeenInTesting + .01;
double Denomerator = (double)SampleSize + .04;
return -1*NaiveBayes.log2(Numerator/Denomerator);
@analog sonnet
the data is 10 rows of 6 numbers, 1-5 being data and 6 being what it's trying to predict. For the testing it wants me to compute the sum for values 1-4 (which is all the first 5 can be) for each of the 1-3 that the predict can be
helps just to have to explain it lol tomath ppl
weary tiger
what is a algebraic proof (how do you do it) and same with combinatorial proof?
how are those done?
I've googled but still lost and can't even find anything for algebraic proof
How did they start this?
stray reef
algebraic proof = proof by algebraic manipulation
weary tiger
could someone explain why this left graph is a subgraph of the graph pointed at with the green arrow and not of the graph below?
or atleast it says so, which by definition of what a subgraph is doesn't really make much sense to me
yea beings they're both to the degree of 3...
I'd also like to know
ah i'm blind
no connection here
yea but beings there isn't then it shouldn't change the degree value for any. Unless that being there determines whether or not its a subgraph?
plucky wasp
can someone explain this i cant understand
weary tiger
Just each line that joins two circles
So everywhere that the circles are joined by a segment
@plucky wasp
plucky wasp
thanks @weary tiger
weary tiger
No prob
plucky wasp
why -16
plucky wasp
okk thanks
plucky wasp
okk sorry
plucky wasp
👍
runic mauve
Show that for any natural number, there is a natural number whose square root starts with the same digits in its decimal as said original natural number
^ bonus problem for our class
I’m pretty sure that he got this particular problem from a challenge book he has so idk lmao
hearty crane
one way: take some natural number n
now construct some number that when squared, you get some natural number.
try see how squaring a number with some decimal effects its decimal
and see what you'd need to make the 1s, 10s, etc place to the left to give a natural overall when squared
knotty thunder
Is there any general algorithm for determining whether a graph is unilateral? (if and only if for every two vertices u, v exists a directed path from u to v or directed path from v to u)
knotty thunder
But that's for strongly connected components only, isn't it?
analog sonnet
If your graph consists of one strongly connected component, then it is automatically unilateral
knotty thunder
Here's the kind of graph I have in mind, I don't think it consists of any strongly connected components.
I might me using the wrong term
analog sonnet
A strongly connected component of a graph, by definition, is an induced subgraph of a directed graph such that there exists a directed path between any two vertices in the vertex set of said subgraph
So you're not using the wrong term
And you're correct that there are no non-trivial strongly connected components in the graph that the picture shows
In particular, the entire graph itself is not a strongly connected component
analog sonnet
Weakly connected is usually just called connected, 1-connected or 1-vertex connected, and is characterized by the number of components that make up the graph as a whole
In this case, the entire graph is just one (connected) component, so yeah, it's connected
knotty thunder
From my language it translates to something like "unidirectional" or "one-way". Apparently the distinctive feature is that for any pair of vertices u, v, at least one is reachable from the other.
knotty thunder
So given a graph I need my program to determine whether it's "unidirectional" or just weakly connected.
analog sonnet
Scratch that, I didn't
It's always tricky to characterize things in digraphs
I'm used to undirected graphs
knotty thunder
I've done the weakly connected part by transforming it into undirected graph and doing a depth first search
But it's possible that the graph could be like in the image in which case I need to output a different answer
analog sonnet
a <-- b --> c
is connected in the undirected case, but not weakly connected in the directed case (again, by some definition of weakly connected)
knotty thunder
Oh, I guess the definitions are a bit different in my textbook. They go like this:
Weakly connected - If a directed graph transformed to an undirected graph is connected
Unidirectionally connected - If for any pair of vertices u, v in a directed graph, at least one is reachable from the other
Strongly connected - If for any pair of vertices u, v in a directed graph, both are reachable from one another
analog sonnet
Ahh, perfect
Then, by your textbook: the graph I drew is weakly connected but not unidirectionally connected
knotty thunder
Yes
I guess I could just do a depth first search from each vertice, but I'm wondering if there's a better way
analog sonnet
Idk
somber gorge
Could someone help with this question? I think I've calculated it for injective total functions (4! = 24), but I don't know how to calculate it for surjective total functions
somber gorge
I think it might be that there are 24 different total functions, all of which are surjective?
thick vessel
what's a total function?
most importantly injective and surjective are equivalent in this case
faint narwhal
It's the normal function you're used to
It's in contrast with partial functions, which are only defined on part of their domain
thick vessel
oh
I know those as operators
and then you use dom(A) to denote their domain
although often operator will often just refer to (linear) functions aswell
@somber gorge You are correct that there are 24 surjective functions, however there are a couple more functions which aren't
somber gorge
Can you explain please?
thick vessel
you can map multiple different values to the same one
you didn't include the map that just sends all 4 elements of A to a single element of B for example
thick vessel
there are in fact a ton more maps
somber gorge
Is there a logical way I could calculate the number of ways?
I guess if I label them like
thick vessel
just consider that where the "2nd element" maps to is completely independent of where the "1st" element maps to
thick vessel
there is a very simple formula
somber gorge
4! * 4!
thick vessel
no
remember how you came up with the faculty
the faculty came from the consideration that if you map the 1 somewhere you only have 3 options left for the 2
however now there are still 4 options left
that should give it away 😄
thick vessel
correct
thick vessel
yes
somber gorge
Okay that makes sense, thanks for the explanation
quaint pike
If anyone here is willing to voice chat with me to help explain stuff about Congruence Module stuff and Equivalence relations, I'm in a voice channel
Appreciate it
quaint pike
73
hallow eagle
wintry rock
Is there a way to do a "factorial" but with addition instead? Like 70 + 69 + 68...
last sigil
Summation notation
last sigil
never heard of handshake formula
wintry rock
oh its like n(n + 1) / 2
wintry rock
oh cool
last sigil
n(n+1)/2
indigo spear
hello?
last sigil
indigo spear
Alright Im trying to figure how to start this problem
Show that the sequence 4, 16, 64, 256, ..., 4^n, defined for n≥1, is a solution to the recurrence relation:
a_0=1
a_k=4a_(k-1), for all integers k≥1.
last sigil
What are you learning in class so far/current lesson?
indigo spear
recursion and sequence
indigo spear
yeah that how it stated which is why I am having trouble with it
last sigil
I mean you can probably do induction on the sequence
indigo spear
Ill give it a try I am not certain that the way they want it
clever nacelle
Can anyone on this channel help with regular grammars, regex and turing machines?
a. 1 + 01
S -> 1|0A
A -> 1
b. 1*01* + 01
Simplified to 1* 01* as 01 is apart of 01*
S->1S|0A
A->λ,1S|0S
c. {00, 10, 01}
S->0A|1B
A->1|0
B->0
d. {Λ, 0, 1, 00, 11, … 0n, 1n, (01)n, …}
S->λ,0S,1S
e. All strings which have an odd number of 1’s
S->1A|1
A->1S
2. Find a context-free grammar for each of the following :
a. Palindromes of even length
S->0S0 | 1S1
b. All string with the same number of 0’s and 1’s
S->0S1S | 1S0S | λ```Cmon guys doesn't this math look fuuuun
analog sonnet
It does, but sadly I don't know much about formal language theory
indigo spear
anyone here know what to do when you get the same roots using characteristic equations to find an explicit formula?
sour arrow
@indigo spear
Have an example?
indigo spear
sour arrow
Generally, you make a new basis solution by multiplying it by x. This can be weird for certain solutions though
sour arrow
This isn't one of those weird cases. Your general solution is Ae^(3x) + Bxe^(3x)
indigo spear
can you explain you get there?
sour arrow
No I can't rofl. It's a thing to memorize. Get the same real root twice, the other basis solution is the same as the first but multiplied by x
You can prove it with a reduction of order argument
This doesn't apply to repeated complex roots, or euler DEs
grave glacier
@clever nacelle i can help you with regex
clever nacelle
@grave glacier I would really appreciate that. I am driving to the airport right now but I'll let you know when I am back on
grave glacier
Alright, My TOC exam is on tuesday and all of this is in the syllabus
clever nacelle
What degree are you in that you are learning TOC?
@grave glacier This is my Google Doc, IT would probably be easiest to look at this. And make comments. I am "Finished" but not sure on things.
hearty crane
also @unreal nova $\frac{17}{72(1-x)} = \frac{17}{72} \frac{1}{1-x} = \frac{17}{72}(1+x+x^2+\dots)$
vital dewBOT
em:
hearty crane
then you can use the distributive property
unreal nova
Oh ok
Thanks
How would u convert from the generating function to the expression normally
Like
For example
1/(1+x)
Which is (1-x+x^2...)
Ok bad example
$ \frac{2-x-x^2}{9(1-x^3)}$
vital dewBOT
Jbao:
hearty crane
basically, you see what you can expand and then you just multiply everything through
in the above example, you can expand 1/(1-x^3) then just multiply it by (2-x-x^2)/(9)
but there is always more than one way to do things
finding the closed form from an expansion is generally harder (and often open for harder generating series!), but there are various methods depending on what you are doing and what you want.
sonic ferry
Can someone help me with probability/combination? This question, im not sure how to tackle the restriction of just an ace. But there are 10200 ways for just a straight w/o straight flush.
stray reef
there are only two straights with aces
A2345 and TJQKA
multiply that by the number of ways to assign suits to the cards in a way that doesn't result in a straight flush
that'll give you the number of possible ace-containing straights
sonic ferry
(4c1)(13c4) @stray reef will this work because there are 4 suits, 13 choose 4(total aces in a 52 deck of card)
stray reef
uh
,,,no?
it sounds like you've either glossed over or ignored everything i said lmao
sonic ferry
i understand there can only be two because there is a high and low ace @stray reef im stuck after that.
sonic ferry
yes
stray reef
each such straight is determined by which suit each card has
there are 4 options for the ace's suit, 4 options for the two's suit, 4 options for the three's suit, 4 options for the four's suit, and 4 options for the five's suit
does that make sense to you
stray reef
??
you're going for a straight and not a straight flush
so you're gonna have to subtract off the straight flushes afterwards
sonic ferry
ah okay so they can be diamond, hearts, etc.
stray reef
i feel like you're either overthinking or clueless or both and i can't tell at all
sonic ferry
honestly im lost in this chapter
stray reef
alright so do you mind if we set this problem aside for a moment and i ask you a simpler question
sonic ferry
@stray reef yea sure
stray reef
you have two cards from a poker deck, and you know one of them is an ace and the other is a king
how many options are there for what your hand could be
sonic ferry
11
stray reef
how'd you get 11?
sonic ferry
11 - (2 known card), there are 13 ranks.
sonic ferry
ohhh
stray reef
no no
look
one of the possible hands would be Ad Kd
another would be Ah Ks
another still would be Ac Kh
sonic ferry
can you explain to me what a "hands" mean
stray reef
here i just mean your hand of two cards
about which we know that there's an ace and a king
sigh
ok looks like i'm not gonna be able to explain much to you rn
sonic ferry
ok let me think through this
sight im too stupid for this. im gonna go reread the chapter ._.
is it 121 @stray reef
stray reef
no it's not
sonic ferry
last try... 24 @stray reef because there are 12 other cards you can combine with A, or K
sonic ferry
@stray reef ._. wow im lost
analog night
stray reef
a good strategy for deciding whether these are true is to draw a venn diagram
rancid siren
Hello
craggy gale
for (a), which one do you go for ? do you think it's true ? do you think it's false ?
hearty crane
@rancid siren there is a single theorem in particular that will help you out here
What must be true about the vertices of a graph for it to be eulerian?
also, if it helps, you may need to remove more than one edge...
errant bear
i have a question regarding N x N, i am supposed to express it as the union of a countably infinite family of countably infinite sets. Since elements of N x N take the form ( n , n ), would stating this work
or would i have to break it up so that its the union of the union
hearty crane
it does specify you have to express it as the union of sets, so might want to be just a little bit more specific in your notation
I personally would fix one element then iterate, then your outer union would iterate over the fixed elements
errant bear
so like, fixing x and iterating for all y, then unioning that with fixing y and iterating for all x?
as the union of two countable infinite families?
also my understanding of families is meh, since we barely covered it
hearty crane
$\bigcup_{a\in\Bbb N} {(a,b) : b\in \Bbb N}$ should do it
vital dewBOT
em:
hearty crane
the inner one is a family of (a,b) with fixed a for all b
then the union will union all different fixed a
giving the entirety of N x N
errant bear
yeah, because the inside set is equal to {a x N}
hearty crane
In fact, I would probably say let $S_a={(a,b): b\in \mathbb N}$ then $\bigcup_{a\in \Bbb N} S_a$
vital dewBOT
em:
hearty crane
just to be totally clear
errant bear
and the union gives all ordered pairs with a in N
hearty crane
yeet
errant bear
that makes sense
hearty crane
But really, that's an icky way to represent N x N
since you can just say $N\times N = {(a,b): a,b\in \Bbb N}$
vital dewBOT
em:
hearty crane
but if the problem states countably infinite union of countably infinite sets, then you need to use the one above the above
errant bear
the way that i gave seems wrong because doesnt it imply that i will always equal j, so i would end up with just (1,1), etc like the same numbers
hearty crane
to fix it you could just say $\bigcup_{i,j\in \Bbb N}$
vital dewBOT
em:
hearty crane
❤️
errant bear
thank you
hearty crane
np
static pagoda
. Find the number of nonisomorphic simple graphs with
six vertices in which each vertex has degree three.
versed hemlock
Can someone describe to me how this formula determines the number of balanced bracket sequences?
This is the catalan number formula
so for example given a sequence ))((
n is the number of bracket pairs
so there are n opening and n closing brackets
the formula above calculates the number of possible balanced sequences of n pairs of brackets
for example ()()
or (())
im confused about the 1/n+1 part
what is that doing in this case
shrewd spindle
could someone help me find a euler circuit from this graph? Unless I am missing something, I can't seem to find one.
obtuse lance
you have to start and end on an odd degree vertex, because otherwise you will enter it but not be able to leave at some point
so start out by locating the starting and ending points
shrewd spindle
That's what I was trying to do, but say I start on F, I still have a problem since I go to c once, leave c, and then return to c with no way out again.
obtuse lance
that's what I'm telling you
F and C are your starting and ending points
so make sure you pass through everything else first
shrewd spindle
yeah so a circuit wouldn't be possible though correct?
obtuse lance
no, it's possible
maybe you're thinking you can't go through the same vertex more than once
that's allowed
Euler circuit just means go through every edge once without repeating edges
shrewd spindle
A circuit being ending on the same vertex u started with tho
shrewd spindle
ok that makes sense thank you
obtuse lance
cause you can definitely find an euler path through the graph
shrewd spindle
ok thank you
obtuse lance
yep you're welcome
sonic ferry
is a straight flush and straight considered together?
cerulean ore
Guys, with 4 different nodes how many non-similar trees can be made?
stray reef
when are two trees considered to be similar?
cerulean ore
What our book says is : "When they have same shape"
stray reef
pff
that's nowhere near a rigorous definition.
are they necessarily binary or can each node have as many children as desired? if they're binary, does it make a difference whether the lone child of a node with only one child is considered as its left or right child? are the trees rooted or not?
these will all affect the answer.
cerulean ore
It was asked in our final examination, let me write the exact question.
"List all possible non-similar binary trees having four nodes."
stray reef
okay so binary
for nodes with only one child, is a distinction made between cases where it is the left child vs where it is the right child?
again, the answer depends on that
cerulean ore
I don't know, it wasn't taught in the class. 
stray reef
then the question as asked is impossible to answer, because it is too vague.
cerulean ore
Let me quote my book:
"Binary tree T and T' are said to be similar if they have the same structure or, in other words, if they have the same shape."
cerulean ore
stray reef
what's the "shape" (or "structure") of a tree defined as?
cerulean ore
That's the "only" text available in book regarding the similar trees.
stray reef
...ok so
for nodes with only one child, is a distinction made between cases where it is the left child vs where it is the right child?
i asked you this question
and to my surprise, the book ANSWERS it.
cerulean ore
stray reef
do y'all not usually read the book?
stray reef
how did you arrive at 8 for your answer?
also
you weren't asked to count them
but to LIST them
which six of these did you miss?
stray reef
you're welcome
slender skiff
Im using, Euclides algorithm to calculated gcd of 2 numbers, but the first remainder calculated is 0, I have never experienced that before, if the first remainder is 0, what would gcd be?
slender skiff
Ah okay, idk why i didn't think about that, Thanks!
warm minnow
Hey, I got a problem, were I got numbers 5,6,7,8,9, I need to find how many possiblities are of making a random two digit number and it doesnt say that they can not repeat. Not sure how they get 25 as the answer.
old sparrow
for the first digit you can choose 5, 6, 7, 8 or 9 (5 choices), then for each of those choices, for the second digit you can choose 5, 6, 7, 8 or 9 (5 choices)
so 5 * 5 = 25 choices in total
warm minnow
Lmao I'm so dumb, somehow I was calculating and thinking as if I need 3 digit even tho I need 2 digit number 
Thanks
slender skiff
I was given this exercise, I don't understand the solution, it says in the exercise at MOST two consecutive 0s, that means that the input can ONLY have 00, twice, but by the looks of the drawing, it can continue running the machine.
languid drift
This doesn't mean that there can be only two zeroes in the whole string. @slender skiff
It's just not possible to have more than two consecutive zeroes.
0010010010101010011111 is perfectly fine
100010010111 is not
rapid herald
hey guys, i need to understand and be able to explain the floyd warshall algorithm. its for a math exploration, where do u guys suggest i go? are there any good websites or yt videos?
whole cobalt
induction proofs are the bane of my existence
sour arrow
Many people here love induction
whole cobalt
its probably really easy, im just extremely bad at it
i 100% believe you have all been stockholm syndrome'd then
sour arrow
No, it's fine here. Might one argue that multiplication is associative so the brackets don't matter?
sour arrow
I'm just wondering if it's allowed lol
whole cobalt
ill accept an answer that assumes so
sour arrow
Okay, let's go through the steps of an induction.
Base case first. Show me that P(1) is true
sour arrow
I wasn't clear oop. I'm using P(1) to mean "the proposition at 1 real number". The proposition says that this should take 0 multiplications, which is true.
So we say P(1) is true
But yeah you can see why the base case holds
whole cobalt
yeah i get its any numbers, i just usually start from one
sour arrow
Now, the inductive step. Assume P(n) is true. Prove that P(n + 1) is true
sour arrow
Yeah this is the hard one for many
"P(n) is true" says that multiplying n numbers takes n - 1 multiplications.
What happens if we multiply this by another real number?
whole cobalt
then it takes n multiplications
sour arrow
And there's n + 1 numbers
stray reef
you're told to use strong induction tho kx
whole cobalt
right i get the logic behind induction in general i suppose
sour arrow
Oh wait what's strong again?
whole cobalt
strong is when we research more P(n) cases (is how we were presented it as)