0 is also acceptable
#discrete-math
worn vale
Does a * after a parentheses mean that said state is acceptable?
last timber
(101)* means {λ, 101, 101101, 101101101,...}
worn vale
So basically an expression followed by an asterisk means that it occurs: never(λ), once -> infinite?
worn vale
Hmm yeah mb, I understand what you meant.
I was just trying to express it in words and my poor english screwed me over I think
last timber
i mean (a)* just means that any string of the form {a.aa.aaa.aaaa....} and also empty string is in lang
that is all possible concatenations
worn vale
Yeah exactly, thanks for the explanation. Much clearer now.
last timber
yw
olive swan
Could anyone help me with part b. I believe the first equation is the one which holds if R is non commutative but I dont know how to give a counter example for the other equation.
languid cradle
need to find a way to show
that a set of n-1 edges from a graph with n vertices is connected
fluid remnant
In graph theory, if X is a set of vertices, should I assume that normal set notation applies and |X| is the cardinality of X?
mystic moss
that a set of n-1 edges from a graph with n vertices is connected
are there other restrictions? idt you can prove this as stated
languid cradle
oh yeah i messed up
the graph contains no circuits
I think i proved it tho
w induction
mystic moss
yeah this is the "trees must have n-1 edges" thing then right
dry reef
hey i'm an idiot and have suddenly forgotten, what graph is represented by E?
like K4 is the complete graph on 4 vertices, what's E4 again?
languid cradle
no a little different
I would think E4 just means the edges of K4
but idk ive never seen that notation
dry reef
this is a question in my homework and i literally have no idea what E4 is lmao
tight lotus
graphclasses.org "all classes" search isn't working for me 🤷
crisp ridge
hi, im having a hard time trying to make the truth table for this if its a Tataulogy
(P <-> Q) <-> [(P -> Q) ^ (Q -> P)]
heres the given truth table
P Q
T T
T T
T F
T F
F T
F T
F F
F F
paper parrot
what do you mean that's the given truth table. That doesn't make any sense
It's wrong
crisp ridge
yah our teacher gave that truth table wait so whats the correct one?
paper parrot
Well first off that's not a truth table, its just 2 columns for the truth values of p and q except each row is repeated for no reason
there should only be 4 rows for a truth tables with 2 statement variables
If you don't know what a truth table is you should just look up an explanation
and then if you have a more specific question ask it
crisp ridge
ik the truth table but its just there so i thought I have to use that given truth table
paper parrot
I feel like I'm looping. This is what a truth table looks like
I don't understand your question
crisp ridge
oh so it doesnt exceed to 4 rows?
stable temple
hello 👋
im new to strong induction; i understand that we have base case n=1, and then inductive hypothesis where we are assuming n = k, but then i dont understand the last part. usually in normal induction we prove it for n = k + 1, but here they are doing something else
(there may be errors in the picture above because thats just what i wrote based on my understanding from reading other sources)
faint narwhal
They're just relabeling a little
In (weak) induction, you could instead have an inductive hypothesis where you assume the n = k - 1 case, and then prove the n = k case
This is basically what they're doing here
stable temple
but, here,
they first have n = k in the inductive hypothesis
and then, idk, they're just using n?
oh wait i found smth else
they use 2N in the proof and it seems to work out nicely
faint narwhal
They say that (assume that N is a power of 2) at the beginning
So you can think of it as setting N = 2^k and inducting on k i guess
stable temple
like this, right?
hidden yacht
ik how to find max flow but how do u find min flow
worn vale
Is it true that this regular expression would accept binary strings with an even amount of 0's and an even amount of 1's?
(00+11)*[(01+10)(00+11)*(01+10)]*(00+11)*
weary tiger
why if 5 and 7 have the same rest mod 2 and 3 and 5 have the same rest mod 2 then 5+3 and 7+5 also have the same rest mod 2?
errant bear
what
weary tiger
Can someone help me on this problem?
coral raven
what do you think
weary tiger
I think its a bijection but idk
coral raven
why
weary tiger
Well because I know its not A, or C
weary tiger
yes its that its both injective and surjective
I think from the info we have we can predict that f is not one-to-one
coral raven
yeah that's a better guess
tepid fulcrum
f(x) 1/x^2 is this one to one, onto, neither, both?
minor dagger
is f:R -> R?
errant bear
do you want a proof @weary tiger
weary tiger
like intuitively
not like a written proof
cause that's useless tbh
written proofs are kinda useless
@errant bear
lol
not if you understand them
intuitively its obvious since b modm modm = b modm
tight lotus
i feel like formalizing all proofs at least once is a useful move
twin badger
Hey so how do you make a partition of a set {0,1}^5
I understand a partition but I don't get how to make a proper partition of an N-ary set
coral raven
just partition it into one whole part with every element 
twin badger
Ah so am I basically forced to write out all 32 elements and partition them into groups? I was trying to figure out how to define the partitions in set builder notation instead of roster notation
weary tiger
intuitively its obvious since b modm modm = b modm
b modm modm is m
like 7 mod 2 is 1 ,1 mod 2 is 1
??
?
you said b mod m mod m is b mod m but that is wrong
split smelt
I think Godel's right and your example backs him up, no?
errant bear
7=1 mod 2
weary tiger
intuitively its obvious since b modm modm = b modm
this is equals not equivalence
(b mod m) mod m is not equal b modm lol
weary tiger
I think Godel's right and your example backs him up, no?
yep
coral raven
(b mod m) mod m is not equal b modm lol
give an example?
weary tiger
like 7 mod 2 is 1 ,1 mod 2 is 1
errant bear
7 is 1 mod 2
weary tiger
1 sec
coral raven
ya dun goofed
weary tiger
7 mod 2 is 1 right?
coral raven
yes
weary tiger
1 mod 2 is 1 right?
coral raven
yes
coral raven
yeah.
weary tiger
7 *is* 1 mod 2
yes
(b mod m) mod m is b mod m indeed
so b mod m mod m equivalent b mod m (mod m)
anyways nvm I understood it
vestal python
Hi i have a question about what counts as a distinct denomination in a poker hand? lets say i draw 4 cards, i want 2 distinct denomination, does A, B, C, C count as 2 distinct denomination? or does A, A, B, B count as 2 distinct denomination?
turbid nacelle
Should be the latter
but it is dependent on what you define as a denomination
Do you want numbers:picture cards? Or Diamonds:Clubs:Hearts:Spades?
worn vale
Does the following machine recognize the language generated by this expression (00+11)*
obtuse lance
does your language contain the word 00011?
worn vale
Not sure what you mean @obtuse lance.
candid pier
what about the word 11
i'm assuming the state with a double circle is a final state
and the initial state
it's been a while. does this machine have to recognize only those strings in the expression? i thought with a DFA it "recognizes" a language if and only if it accepts valid strings of the language. in your case it looks like the DFA accepts strings not contained in the expression
worn vale
@obtuse lance I just started reading about state machines etc so I'm no expert. But I'd say that the machine would not accept the word 00011 because it would get "stuck" in state 3.
@candid pier Hmm, wouldnt the expression I wrote accept the word 11 or am I mistaken?
candid pier
- indicates "0 or more instances of" and + indicates "1 or more instances of", right?
candid pier
generally in languages those symbols are quantifiers. do you have a different definition of them?
obtuse lance
yeah I asked because + to me means at least one and * means 0 or more
as a regular expression I read (00+11)* as allowing 00011 but your FSM doesn't allow it
worn vale
Yeah you are right
candid pier
ah, well it would depend on how it's defined
worn vale
I mixed it up with boolean algebra
candid pier
mathematicians are lazy. so you'll find the same symbols overloaded in every field of study
worn vale
No wonder ive struggled with the frickin state machines
😆
so (00)*(11)* would be more like it?
mystic moss
In this context I’d think + means or
candid pier
are you given the expression, or are you given a description and you have to generate the expression?
mystic moss
Because one or more ‘a’s is usually denoted by aa*
candid pier
worn vale
@candid pier all im given is the picture of the machine and im asked to formulate the regular expression that represents the machine
candid pier
ohh ok
worn vale
The machine only accepts a 0 followed by another 0 or a 1 followed by another 1, 0 or more times, right? ex) 001100110000 would be recognizable
obtuse lance
so (00)\*(11)\* would be more like it?
yeah yours is close
but yours only accepts 0s first then 1s last then stops
mystic moss
https://en.wikipedia.org/wiki/Regular_expression
Right, exactly—I think the problem writer wrote + for | which does happen a lot
It might have been clearer with a space
But again idk what the statement was supposed to be cause I didn’t write it 🤷
candid pier
😄
glacial musk
The machine only accepts a 0 followed by another 0 or a 1 followed by another 1,...
I guess it's 0 (0+1)*
obtuse lance
I was going to say ((00)*(11)*)*
worn vale
I guess it's 0 (0+1)*
Wouldnt that only accept strings that begins with a 0?
glacial musk
Wouldnt that only accept strings that begins with a 0?
Yeah but that is what your language say.
You said it starts with 0
candid pier
"Some As are C", one of the options doesn't match this restriction
worn vale
I was going to say `((00)*(11)*)*`
Hmm yeah that makes sense.
obtuse lance
the problem is start from the FSM and make the regex so what's written doesn't matter actually lol
worn vale
Yeah but that is what your language say.
I said it could start with a 0 followed by a 0 OR a 1 followed by a 1
glacial musk
Then followes by 0,1 (0+1) and so on this making it (0+1)*
worn vale
the problem is start from the FSM and make the regex so what's written doesn't m...
Thanks for the explanation.
glacial musk
It would be great if you could post actual questions.
So I can see what you trying to say .
obtuse lance
you should sort out the notation in your book if + means kleene plus or OR
glacial musk
Regex have very fine langauge thus altering any grammatical wo d will change the regex too .
glacial musk
"Some As are C", one of the options doesn't match this restriction
Which one
glacial musk
you should sort out the notation in your book if + means kleene plus or OR
It's never an issue as one is raised to power while other is normal plus .
worn vale
you should sort out the notation in your book if + means kleene plus or OR
Yeah my bad. I just hopped onto regular languages and i had boolean algebra stuck in the back of my head.
obtuse lance
Don't know what was funny but lol
you're saying there's some kind of universal when it comes to notation when there isn't, you're just wrong
glacial musk
~~the one where none of the As are C~~ oh sorry i misread your diagram
Ohk how did you do that .lol .the edit if line.
glacial musk
you're saying there's some kind of universal when it comes to notation when ther...
That is okay
obtuse lance
if someone writes ^+ but ^ also has a meaning when written in regex
mystic moss
In latex you will usually see it raised above like a power
But like you can’t do that with code
glacial musk
@worn vale can you post your question again . It's making me dizzy lol . Coz I didn't understand what you said or may be because my regex was wrong .
candid pier
Ohk how did you do that .lol .the edit if line.
hm.. i'm not sure which one is "best". both of the diagrams satisfy the conditions o_o
worn vale
I have this picture and I want to formulate a regular expression to represent it.
worn vale
<@187599326124441600> can you post your question again . It's making me dizzy l...
So I wrote the expression I formulated and asked if it was correct(it was not).
glacial musk
Ah thanks
candid pier
I was going to say `((00)*(11)*)*`
this seems right.
glacial musk
Firstly you must tell which is the start state ( though obvious but it affects the answer ) .I see it's s0
Also your regex (00+11)* was right too .
So was ((00)(11))*
worn vale
u can write \ before * to prevent discord from making text cursive. @glacial musk
worn vale
Also your regex (00+11)* was right too .
but i thought "+" meant something else
glacial musk
@worn vale no it's standard in regex to represent OR with +
But if raised to power it's kleen's closure
candid pier
depends on what formalism is used. if your textbook or instructor uses + to indicate boolean or, then yes.
but if your textbook or instructor uses + to indicate "one or more instances of [what comes before]" then no
glacial musk
@candid pier that is okay
worn vale
My book gave a pretty scuffed explanation. But I found this if it makes stuff any clearer.
Where + and · is used to describe the meaning of kleene*
candid pier
yeah in that case you can consider it a boolean or
glacial musk
Where + and · is used to describe the meaning of kleene*
I don't thing it needs and argument from my side.
Here '+ ' means "or"
slow jewel
How to i check if this is a graph
obtuse lance
you could construct it directly
well, there's no unique graph satisfying that, so construct an example
slow jewel
im not sure if it is even possible
obtuse lance
I constructed 3 simple graphs that satisfy that
there are more if you don't restrict to simple graphs
just play around a bit
the degrees are only 1 and 2 so it's not really that crazy to try to find one
slow jewel
ok thanks
alpine hull
How does someone find out how many loop-free (not multigraphs) graphs exist given a degree pattern?
obtuse lance
well the only way I could think to try to rule out if it was not a graph was using the formula,
$$\sum_{v \in V} \deg (v) = 2 |E|$$
vital dewBOT
Merosity
obtuse lance
so I just did the check first, if the sum of degrees is odd, there can't be a graph
obtuse lance
I assumed you were asking about the previous problem, I didn't do anything
alpine hull
but
obtuse lance
I just explicitly could construct all 3 because it was so restricted
pastel mica
how woudl it be possibel to add 2 sets tho
like wouldnt it be something like A=(1,2, 3) and B=(4, 5, 6)
so (1+4, 3+5, 3+6) -----> (5,6,9)
but how could that = 11
weary tiger
hmm?
|P(A)| is an integer
| A | means number of elements of A, |P(A)| means number of subsets of A, in fact you can show that if |A|=n, then |P(A)| = 2^n.
@pastel mica
slow jewel
Not really sure how to go about proving this. Any hints?
faint narwhal
take an isomorphism from G_1 to G_2 and extend it to an isomorphism between their complements
slow jewel
i did, i assumed you can use the same bijection
faint narwhal
so what are you having trouble with?
slow jewel
it makes sense now
bronze cosmos
Given a positive integer n, how many binary strings of length n are there such that neither “11” nor “000” is a substring?
Bonus: how many of such strings do not begin with “00” and do not end with “00”?
weary tiger
Show that if a, b, k, and m are integers such that k ≥ 1,
m ≥ 2, and a ≡ b (mod m), then a^k ≡ b^k(mod m)
I saw a proof by induction online but I came up with a proof but idk if it is correct
my proof is that if a congruent b (mod m) then a modm =c and b modm =c so a^k modm = (a modm x a modm x a modm ... k times) modm and a modm =c so a^k modm = c^k modm and same for b we have that b modm=c so b^k modm = (b modm times b modm times b modm (k times)) modm = c^k modm hence a^k congruent b^k (modm)
pale epoch
what does "a modm =c" mean
weary tiger
a mod m
is equal to c
the remainder of the division of a by m equal c
@pale epoch
pale epoch
then this is just stating a special case of what you are asked to prove
(you just replace a and b by some other representative c mod m and claim you can do this)
weary tiger
sorry I didn't understand what you mean
weary tiger
(you just replace a and b by some other representative c mod m and claim you can...
why not?
I didn't quite get it can you clarify more
pale epoch
you claim a mod m = c implies that a^k = c^k mod m
this is a special case of what you want to prove, i.e. a = c mod m implies a^k = c^k mod m
weary tiger
you claim a mod m = c implies that a^k = c^k mod m
yes I proved this
pale epoch
how
weary tiger
so I have a equivalent b (mod m) correct?
pale epoch
yes
weary tiger
ok so a mod m = b mod m = some constant c right?
pale epoch
thats not what this means
you are conflating the ideas of modular arithmetic and division with remainder
weary tiger
the congruence ? doesn't it mean that if I have a congruent b (mod m) meaning the remainder of the division of a by m and b by m are the same?
pale epoch
usually you define it as (a-b) is divisible by m
weary tiger
yes true also that a mod m = b mod m
pale epoch
you can phrase it via division with remainder but its not a good idea
but even if you do, your "proof" does not work
then you get that a and b have the same remainder when divided by m
call it c if you want
weary tiger
then you get that a and b have the same remainder when divided by m
yes this is what I did
pale epoch
and now you have to prove that a^k and b^k also have the same remainder when divided by m
weary tiger
yes exactly
pale epoch
so now you have to perform division with remainder
pale epoch
ok
weary tiger
so a^k mod m = (a modm * a modm *a modm (k times)) modm
weary tiger
well there is a formula saying that if we have (a.b) modm it is also equals to ( ( a mod m ) times (b mod m )) mod m
weary tiger
a^k mod m = (a \* a \* ... \*a) mod m
yes I also used this
pale epoch
well, ok
then you have to prove this first
and then you have to prove that every number has a unique representative mod m
also that modular arithmetic defines an equivalence relation, but i guess you already have that anyway
and then this works i think
stable temple
there's this part in generatingfunctionology
i was wondering why they can just replace the summation with the infinite sum of a converging geometric series?
its only valid for |x| < 1, but not for any other x, right?
stable temple
hmm it explains this in the second chapter on series but i didnt really understand it but another book says that this is valid because we never actually use the value of x and are just interested in the coefficients of the series
ig that works ¯_(ツ)_/¯
fallow pawn
does anyone know what tool i can use to build truth tables for these two expressions? cant find one that has both the triple = and the <->
fallow pawn
yea i understand that but i have to build one for each to "show"
minor dagger
Alright then write out the truth tables
fallow pawn
and i cant find a generator that has both operator
fallow pawn
yea thats tru, only two variables
minor dagger
Was this from a test?
weary tiger
yeah has trouble on these ones
weary tiger
If I have a= qd+r how to prove that (q+1)d >a
I mean it is obvious but how to prove it
weary tiger
ops fixed
stray reef
142 = 8 * 10 + 62 but (8+1)*10 is not greater than 142
weary tiger
hmm
stray reef
either you're missing something or you're asking us to prove a false statement
weary tiger
looks like I am missing something
let me think
ok you wrote it wrong
142=14x10 + r
stray reef
i wrote nothing wrong, you didn't say r was supposed to be the remainder
i.e. you didn't say 0 ≤ r < d
weary tiger
here What I mean by q is the quotient and r the remainder
stray reef
anyway, now that 0 ≤ r < d has been made explicit
weary tiger
yes
stray reef
it should be obvious that qd + r < qd + d
weary tiger
yep
but where is a < (q+1)d
ops
qd+r is a
and qd+d is (q+1)d
lol
well that was obvious
xD\
ok cool thanks @stray reef
rigid hedge
the answer is D
tepid fulcrum
how
stray reef
definition of an equivalence relation
rigid hedge
An equivalence relation is one which is reflexive, symmetric and transitive
rigid hedge
R is just a symbol
stray reef
no, R is just a name
tepid fulcrum
this is B correct?
stray reef
yes
tepid fulcrum
is this D?
stray reef
yes
errant bear
why are u copying and pasting questions in test format without caring ab reasoning
rain stone
there are countries that are not in the americas lol, it's not the middle of the night everywhere
stray reef
^
tepid fulcrum
im coping and paste them because i need help on these question and no its not a test
can someone explain to me how to answer the this question
stray reef
recall the definition of an equivalence relation
tepid fulcrum
reflexive, symmetric and transitive.
stray reef
- is every person the same age as themself?
- if i'm the same age as you, are you the same age as me?
- if i'm the same age as you and you're the same age as this other person, are me and the other person the same age?
tepid fulcrum
yes
stray reef
yeah so
stray reef
bingo
recall the definition of a partial order relationship
reflexive, transitive, and anti-symmetric
in particular, notice that for R to be reflexive we would need (d,d) in R, which we don't have
tepid fulcrum
so false?
stray reef
yes
quaint star
@tepid fulcrum I think I helped you before! Anyway, do you know the definitions of those terms?
alpine hull
Given this degree sequence (5,5,5,4,4,4,3) how do i show its nonplanar using the complete bipartite graph K_3,3
glacial musk
Which option is correct ?
The second one is correct( my point of view ) but i am asking about the first one .
deft current
@past gate do you know how to start?
balmy hornet
Correct me if im wrong:
So
f(x) = x -> injective and surjective, since injective and surjective then bijective
f(x) = x/2 -> injective and surjective, since injective and surjective then bijective
f(x) = x^2 -> not injective and not surjective, not bijective
**f(x) = 1/x **-> injective and not surjective, not bijective
mint bane
you working within the reals?
balmy hornet
you working within the reals?
i dont know if this mesage is ment for me but the reals?
faint narwhal
to talk about these things you need to specify the domain and codomain
balmy hornet
all functions are defined as f: R-> R
faint narwhal
how is f(x) = 1/x defined from R to R?
balmy hornet
how is f(x) = 1/x defined from R to R?
wait that may not be possible since x cannot equal 0. if it did it would make it undefined
past gate
<@!658669379604447233> do you know how to start?
I do not sadly...the professor was really bad explaining this...
faint narwhal
it's just manipulating the exponents
on the right side, you have e * e^(-n)
so that's the e^(1-n) on the left hand side
weary tiger
anyone want double check my question?
balmy hornet
Which of the following are NOT the official rules for a function?
A. Every input in the domain maps to come output in the codomain
B. Equal input produces equal output
C. If the inputs are different, the outputs are different
D. For every possible output, there’s at least one possible input that produces it
Ok im confused. So i have my intial thought that A and B are correct, but C and D are not because it should be producing 1 output with 1 input?
balmy hornet
i mean, just an element of the codomain?
Those are just the given statements so thats why im kinda confused on how specific or lenient this is
balmy hornet
i mean D seems either false or obviously true
I guess when can there but multiple inputs?
coral raven
snore
quiet steeple
How do I find the factor group (ZxZ)/H the standard from from the subgroup H={(5a+8b,10a+20b), a,b element of Z}
faint narwhal
This is probably more suited for #groups-rings-fields
quiet steeple
okay
fleet latch
hi does anyone know how to solve this? all i've gotten so far that R is an order
weary tiger
jaunty aurora
Hi! Does anyone in here know how to do graph theory?
jaunty aurora
Oh what is this
stray reef
a way of saying you should ask your question right away rather than wait for someone knowledgeable in graph theory to show up
jaunty aurora
Oh well it is very advanced so I didn't want to spam with pictures. It's shapes not questions.
I was trying to be decent . Sorry.
I want to learn how to do it.
prisma cypress
uh... am i overthinking this sequence? have to get first 10 terms, but the only thing it tells me is that nth term is 3, and... im lost as to whether it just means everything is 3 or if im missing something that should be obvious
stray reef
picture?
prisma cypress
only instructions i have regarding a starting point is assume that first term is 1, beyond that
prisma cypress
wait i may have misread it.. is index of 1 meaning it starts as 1
stray reef
dunno. whoever wrote this needs to express themselves better.
or you're cropping out some instructions that would make it all fall into place.
prisma cypress
its from my textbook on the class lol the instructions i have are as follows: give first ten terms of the following sequences, assume the sequences start with an index of 1, logs are to base 2
the rest is determining whether its increasing, decreasing, etc but i gotta get the sequence itself before i can determine that
got all of em except E
stray reef
okay so. yeah
it should be all threes then
but in that case, why the 1 in the beginning?
or was that put in by you?
prisma cypress
i assume i misread it initially as assuming the first number is supposed to be 1 because that was put in by me
stray reef
starting with an index of 1 means you consider the term at the start of the sequence as the 1st term (rather than the 0th)
prisma cypress
this stuff probably confuses me more than it should but its also my first experience with a strictly discrete math class and i haven't touched sequences or what-not in a while since for longest time i was in programming stuff instead of math classes
prisma cypress
@stray reef do you have any good sources of info on dot multiplication or whatever it is with matrices, im still struggling to really get how to do it without a graphing calculator... initially learned how to multiply them on one back in 2 year college or high school but now in uni i can't use the graphing calculator on the tests
stray reef
dot multiplication?
prisma cypress
some weird thing encountered in the last chapter that dealt with matrices and graph powers, this kind of stuff as an example
candid pier
like determining which rows/cols of A and B to dot product?
prisma cypress
im gonna be honest that i don't understand dot products or how to do it without a graphing calculator
candid pier
a dot product is a sequence of multiplications and additions on two vectors. you multiply the corresponding elements in each vector and add them up.
e.g., (1, 0, 1) * (0, 0, 1) = 1*0 + 0*0 + 1*1
for two dimensional vectors it might be easy to see:
(2, 5) * (3, 6) = 2*3 + 5*6
you just walk through the vector and multiply the corresponding value. the first element of vector A is multiplied by the first element of vector B. the second element of vector A is multiplied by the second element of vector B, etc. etc. and you take the sum of everything to yield the dot product
once you understand how a dot product works, it's just a matter of figuring out which vectors you need to determine the dot products in a matrix multiplication , as in your example
prisma cypress
okay... uh.. next question. is this how a recursive sequence is supposed to work, or...
candid pier
the first equation looks like a recurrence relation. , the last equation looks like you have the initial values of g2 = 2 and g1 = 1?, so g3 = 7?
prisma cypress
g1 is 2 and g2 is 1 which makes me feel like it should be going down, i have no limitation that says it has to be over 3 or something similar
must've put em backwards initially
agh
prisma cypress
question, how would it be 5 for third index though, doesn't it end up being either 7 or 9? cause one way is gonna end up with 3 * 2 for 6 then + 1 as 7, or 2 + 1 for 3 then * 3 to get 9?
candid pier
i thought you said g2 = 1?
prisma cypress
oh right i forgot the one above had them backwards
candid pier
if g2 = 1 and g1 = 2
then g3 = 3 * g2 + g1
= 3 * 1 + 2 = 5
prisma cypress
would the 6th one be 351 then
candid pier
g6 = 6*g5 + g4 = 6 * 110 + 21 = 681
prisma cypress
oh right
okay i think this may be right then for the next one now that i've got a better... understanding
candid pier
c3 = 20
c4 = c3 * c2 = 20 * 5 = 100
for that one make sure you re multiplying the previous two terms
prisma cypress
oh whoops
candid pier
but yeah looks like you're getting the idea of recursion.
prisma cypress
this shit was confusing the few times i encountered it in programming and it still is now to an extent
candid pier
so long as you have a base case (initial conditions),you'll find recurrence relation just refers back to an earlier value in the sequence. one that is either defined by initial values, or one that can further be recursed. in programming you'll find recursion useful for breaking a problem down into (hopefully) easier to solve subproblems
pallid belfry
Could someone help me with a conjecture for the problem in red?
plucky thunder
does anyone know how to solve this?
I know i have to use Fermat's Little Theorm (a ^ p - 1 = mod p ), but the other steps im a little lost on
errant bear
break apart 9^45
plucky thunder
So how would I do that?
Wouldn’t it be (9 ^ 22) ^ 18) and 9 ^5?
Or am I wrong there
errant bear
2^5 = 2 * 2 * 2 * 2 * 2 = 2^2 * 2^3 as example, you're breaking it apart wrong
plucky thunder
but how would I get a and b tho?
errant bear
you have a+b = 45
and you're working mod 23, so what do you think one of them should be?
hasty raptor
Is anyone able to help me out with the highlighted, I have the first one as reflexive and symmetric, but for b and c I proved everything false
plucky thunder
do you have a graph?
errant bear
for what
deft current
so which one in particular are you unsure about
hasty raptor
@deft current b and c
I feel as though there was definitely an error in the way I disproved them
deft current
well presumably if they're false, you give a counterexample
hasty raptor
Correct, and I gave a counterexample for each one
deft current
so what's the problem lol
hasty raptor
If they’re all false, what’s the final answer? Are there just no relations?
deft current
so for b, are you saying it's neither reflexive, symmetric or transitive
deft current
what was your counterexample for transitivity
hasty raptor
X = 0, y= 1, z=3
deft current
you sure that works
deft current
it does, I'm being slow
hasty raptor
Oh okay😂 ur good
deft current
yeah I mean, seems fine what you're doing
hasty raptor
Ok so that final answer is just no relation?
deft current
well it is a relation
says it in the question
just it doesn't satisfy those properties
wooden acorn
Does the line over each A mean the complement of A?
plz help I gotta do this homework fast before I pass out
that's all I need to know
I never seen it written that way
last flicker
yes.
wooden acorn
thank you!
last flicker
nw
wooden acorn
I can do my work now!
grave moon
where can i find questions for forward chaining and back substitution for recurrence ?
robust mango
A relation is a set R which is a subset of A x A. Since A has only 4 elements, so you can find A x A and see which ordered pairs (x,y) satisfy x > y + 1
solemn fossil
yall im so confused in my discrete class
my professor's lecture notes and the textbook dont align at all
stray reef
how so
faint narwhal
can you say exactly what the difference here is?
faint narwhal
Then why are you saying they don't align?
solemn fossil
because the content is completely different
faint narwhal
so what exactly are you asking
stray reef
the slides talk about sets as in a data structure
the book talks about sets as in set-theoretic objects
solemn fossil
the slides talk about sets as in a data structure
the book talks about sets as i...
thanks for clarifying
i didnt know how to say it myself
solemn fossil
i understand the math stuff
i just dont understand how to turn it into computer stuff
vernal linden
May be a dumb question, but the first index in $A_{k}={2^0, 2^k, 2^{2k},2^{3k},... }$ is $A_{1}=2^0$ right?
vital dewBOT
therealcain
vital dewBOT
Ann
vernal linden
Here is my exercise: $A_{k}={2^0, 2^k, 2^{2k},2^{3k},... } = { 2^{nk}|n\in \mathbb{N}} \
Find\ a\ natural\ number\ k\ so\ the\ set\ will\ be\ equal\ to\ A_k: \
- \bigcup^{\infty}_{k=0}A_k \
- \bigcap^{5}_{k=2}A_k \
- \bigcap^{\infty}_{k=1}A_k \
- { x/8, x \in (A_1 - A_2) \cap A_3}$
vital dewBOT
therealcain
vital dewBOT
therealcain
vernal linden
Now i wonder if the value of $A_0$ is $\emptyset$ since his index does not exist in the $A_k$ set
vital dewBOT
therealcain
vernal linden
That's why i want to know if the index counting is starting from 1 rather than 0 ( as programming languages do )
@stray reef
stray reef
$A_0$ still makes sense with the definition they gave, it'll just be ${1}$
vital dewBOT
Ann
vernal linden
Is this correct? $\bigcup^{\infty}_{k=0}A_k = {2^0}\cup { 2^0, 2^1 } \cup { 2^0, 2^1, 2^2 } \cup ...$
vital dewBOT
therealcain
quaint star
No
vernal linden
Then i did not understood the big union 😫
stray reef
you seem not to have understood the A_k themselves somehow
quaint star
No, you are not understanding the definition of the sets
$A_1$ is the set where you replace all the k's with 1's so it is
$${ 2^0, 2^1, 2^2, 2^3, \dots } $$
And $A_2$ is the set where you replace all the k's with 2's, so it is
$${ 2^0, 2^2, 2^{2(2)}, 2^{3(2)}, \dots } $$
vital dewBOT
Lunasong
quaint star
So each A_k has infinitely many elements, except A_0 because then all the elements become the same one since it's always 2^0
vernal linden
So the big union essentially unions $A_1 \cup A_2 \cup A_3 \cup ...$ ?
vital dewBOT
therealcain
clever sage
yes
vernal linden
It makes so much sense now, Thank you!
clever sage
big intersection is essentially the intersection equivalent
vernal linden
Yeah it didn't occur to me like that, my brain confused the behaviour of it with arrays from programming languages
vernal linden
**therealcain**
in the third exercise, i showed that $A_0 \subseteq A_k$, but i can't figure out how to show that $A_k \subseteq A_0$ to show that they're equals.
vital dewBOT
therealcain
vernal linden
Can i get a hint please?
vital dewBOT
Ann
stray reef
of course you can't figure out how to show $A_k \subseteq A_0$! it's false! you can't prove a false statement!
vital dewBOT
Ann
vernal linden
Then what $\bigcap^{\infty}_{k=1}A_k = ?$
vital dewBOT
therealcain
vernal linden
I need to prove that it indeed equals to that. And to prove equality i need to show that both of them are subsets of each other
stray reef
okay so you just went and omitted the intersection symbol
and expected whoever replied to you
to just magically know
vernal linden
I did a replay to the image, and said "in the third exercise"...
stray reef
still, there's a big difference between saying $\bigcap_{k=1}^{\infty} A_k \subseteq A_0$ and just $A_k \subseteq A_0$
vital dewBOT
Ann
stray reef
anyway, whatever, not that anyone ever listens to me...
you need to show that if x is a member of every A_k at once then x=1
vernal linden
still, there's a big difference between saying $\bigcap_{k=1}^{\infty} A_k \subs...
You're right, i did that also on my paper, i should change that
stray reef
mirza, i didn't mean listen in the literal/auditory sense
weary tiger
Can anyone here help with coding theory?
paper parrot
last timber
how is weight of codeword defined
weary tiger
the number of 1's in it
weary tiger
I thought about it indeed
last timber
that if w(x)>75 then you are forced to violate either i) or ii)
weary tiger
can you elaborate a bit?
last timber
well assume you have codeword x with w(x) > 75
last timber
you have to show that either it has substring of the form ...1111...
or ..101.. 01... ...10
last timber
hmm
so let x be our codeword with w(x)>75
let us denote w(x) by just w
then if first symbol of w is 0 you then are forced to have second symbol as 0
thus 123 symbols and w ones
otherwise
weary tiger
then if first symbol of w is 0 you then are forced to have second symbol as 0
the first symbol of x you mean
weary tiger
thus 123 symbols and w ones
weary tiger
sure
vital dewBOT
Commander Vimes
last timber
i guess your argument should use it
weary tiger
are we assuming here w>75?
last timber
well yes since we want to show that counterexample code does not exist
last timber
weary tiger
if first symbol is 0
then in the 123 remaining symbols we'd need to have at least 76 bits of 1
last timber
oh
probably i got the hook
in each group of 5 symbols you can put at most three ones'
weary tiger
yup
vital dewBOT
Result:
25
,calc 25*3
vital dewBOT
Result:
75
oh
so basically if we want to maximize the number of ones in a codeword of C
we'd need to divide it into 5 substrings of the form 11100
last timber
well you have to be careful here
weary tiger
there are 25 such substrings
last timber
but yes
weary tiger
Thanks a lot !!
last timber
yw
distant bobcat
anyone heard of non-graph clustering algorithms? I have a homework question which asks something about the possibility of clustering a graph, but with a non-graph algorithm. Im not sure I understand what a non-graph algorithm is?
weary tiger
How can I show that the binary code C with a number of 1's divisible by 3 is linear?
stray reef
be more precise please?
if you're considering the code of all, say, 8-bit words with hamming weight a multiple of 3, then this won't be closed under addition
weary tiger
Actually I don't know if my counterexample is correct
I found that for $n=6$ the codewords $x = 111000$ and $y =110010$ we have $x\oplus y=001010$ which clearly doesn't have a number of 1's divisible by 3
vital dewBOT
Laïka
weary tiger
if you're considering the code of all, say, 8-bit words with hamming weight a mu...
its a general case here, so I guess I can disprove it for a particular value of n
weary tiger
My bad, I haven't tried for some values greater than 3
stray reef
you can construct similar counterexamples for all n > 3
weary tiger
thanks!
pallid belfry
I have a question about graph theory. If you have 5 edges and 2 colors, what can you say about the 5 colored edges? At least ... what?
pallid belfry
I have not learned that before but I just read into it
How does it apply to this situation/what is the pigeon and what is the pigeon hole?
kind geode
hey can somone help me with bayes theorm, my prof introducing it but im really confused, i dont know how he derived the equation at the top and when i search up the formula i get somehting completly different
wise parcel
Hmmmm
kind geode
I also have no clue how he can conclude the probability of E is = to the p(E|F)p(F) + p(E|(complement of F)p(F)
kind geode
uhhh 😅
wise parcel
@wise parcel
kind geode
How does it apply to this situation/what is the pigeon and what is the pigeon ho...
pigeonhole theory is like if i have 5 pigeonholes, and 6 pigeons, it must mean that at least 2 pigeons are in the same hole, i think that the person was saying is that u can say that at least 3 edges will reside in one of the colors
kind geode
hey can somone help me with bayes theorm, my prof introducing it but im really c...
oh and nbm i got it
wooden acorn
Does anyone have a fun math problem that I can try to solve?
Also not super difficult but a cool concept. Prerequisite of combinatorics and below
Maybe a challenge will be good though
weary tiger
How does it apply to this situation/what is the pigeon and what is the pigeon ho...
For $n,m,k \in \mathbb{N}$, if $n=mk+1$ objects are assigned to m places then at least one place is assigned at least k+1 objects
vital dewBOT
Laïka
weary tiger
An important result of discrete mathematics to keep in the back of your head especially when doing counting problems
lost pivot
just the way, we represent a poset on a set A by (A, <). what's the general notation for a lattice. Since a lattice is also a poset, we can use the same representation. But is there a stronger way to even record the lattice properties?
weary tiger
Does anyone have a fun math problem that I can try to solve?
In a class with 280 students, how many students have their birthday the same week
young field
prisma cypress
remind me, how do i get the lcm of two numbers, without using a graphing calculator or some other device, i guess using this one i gotta do as an example
prisma cypress
i figured that one out... um... somewhat struggling to get the prime number theorem down
it gave an example with 10^3 which had a formula that looked like that except for having 3 instead of 5... but im unsure if this is the right approach
balmy nova
i need some help
stray reef
parentheses
and yeah, combinations, but it's not quite that
not 15C5
it'd be... 20C5 if i didnt do a fucky wucky
look up stars and bars
also uh
19C5 my bad
19C5 not 20C5
15 stars, 4 bars
or
15 objects, 4 separators
coral raven
i think i got 20c5 by brute-forcing it
coral raven
yes
weary tiger
multinomial coefficient maybe?
wooden acorn
@weary tiger 228? Pigeon Hole principle.
weary tiger
<@456226577798135808> 228? Pigeon Hole principle.
Not quite
wooden acorn
people
coral raven
no, 3 3 3 3 3 is valid
wooden acorn
it's how many is a plus 1 of 52 weeks right?
fast umbra
weary tiger
What do you mean by inversible?
kind geode
can someone help with this bayes theorm question, the handwriting is shit but the question is basically trying to probability of F given E, (E and F and their complements are listed in the bottom left). But i dont understand how the probability of you having the disease given that you test positive (P(F|E)) to be such a low number (right side). Even though the probability that a test gives a positive result 99% of the time if the person has the disease. i get the math behind it but it doesn't make sense intuitively
gilded wadi
\
coral raven
can someone help with this bayes theorm question, the handwriting is shit but th...
basically there are so few ppl who have the disease as a proportion of the whole that there's just gonna be way more false positives
even if the test is mostly accurate
1 million ppl take the test, 100 ppl have it
then 99 of those 100 will get a positive result
but also 0.01 * (1000000 - 100) = 9999 will get a false positive
kind geode
basically there are so few ppl who have the disease as a proportion of the whole...
so dispite the accuracy of the test (being close to 100%) the chance of you having a disease when u test POSITIVE for it will be 0.002% dont these statments contradict eachother, dispite the rarity of the disease.
coral raven
bruh
basically there are so few ppl who have the disease as a proportion of the whole that there's just gonna be way more false positives
the test is quite accurate, but not accurate enough to compensate for the rarity of the disease
the smaller the thing you're looking for the more precise you gotta be
kind geode
the smaller the thing you're looking for the more precise you gotta be
ohhhh okk i see this kinda makes it mroe understanable
tyty
coral raven
like, 99% accurate
but 0.01% chance of having the disease, so it's not enough
fun times
kind geode
but also 0.01 * (1000000 - 100) = 9999 will get a false positive
also how did u calculate this if 1 in 100,000 get the disease the chance of getting it is 0.001% so it would be 0.00001 * (1,000,000 -10) = false positives?
coral raven
so 1% of the time the test is wrong
1000000 - 100 ppl don't have the disease
so the test will be wrong about 0.01 * (1000000 - 100) people who don't have the disease
kind geode
ohhhoh mbmb ty
heavy edge
Does the universal set contain the universal set?
stray reef
yes
worthy patrol
In how many ways can 12 otherwise-identical socks be hung on a clothesline if there are 6 black socks, 4 brown socks and 2 blue socks and the brown socks must be kept together?
quick folio
When two numbers dont have similar modular residue classes
how do we prove that they have gcd of 1
last timber
can you be more explicit on first part
quick folio
oh sure like
lets say an aribtrary number
and another number n^2+1 is 1 mod 50
need to prove that they are coprimes
thats what i have got the problem down to rather
stray reef
At what point would that end then?
what are you talking about
the universal set is a subset of itself, just like any other set is a subset of itself
quick folio
since they dont have similar residue classes they have gcd of 1 right
insert russels paradox
last timber
meliodas sorry still not really clear what you mean
n+7 = 7 mod 50 means n is congurent to 50
last timber
n^2+1 = 1 mod 50 means n^2 is congruent to 50
quick folio
yessir
quick folio
basically
unreal stump
Just use bezout?
last timber
who says you can't
quick folio
how would you implement it then
cause only place i have seen bezouts is for solving congruence equations ahhaa
unreal stump
Ok, That's not very simple
quick folio
yeahh
i was thinking of ways to prove gcd of 1
bezouts did pop but like the implementation didnt
quick folio
uhhhh
last timber
or you know
prolly you can do induction
@quick folio i got it
prolly
ah no
nvm
quick folio
what was ur thought process anyway
last timber
well
let a = 2500k^2+1
b = 50k+7
denoting gcd(a,b) by (a,b)
(a,b)=(a-b,b)
a-b has to be even
and b is odd
but we are not guaranteed they do not share common odd factors
amber prism
I think this falls under discrete (tried in calc, Ann questioned it)
Im assuming that A_n is suppose to be natural numbers =< n, but I'm struggling understanding how a function would map 1 number to infinitely many
$f_1:{1}\to S$
vital dewBOT
moshill1
last timber
what is S
last timber
what it means set of natural numbers leq than N
amber prism
Yeah, joining a call with the prof in half an hour to ask for clarification, but I assume it's meant to be $A_n ={x\in\mathbb{N}|x\leq n}$
last timber
ok this is more readable
vital dewBOT
moshill1
last timber
so A_n = n^+
stray reef
last timber
<:thonkflip:532148342860546049>
well i use von neumann construicton of naturals
so n = set of all naturals less than n
amber prism
Yeah, just not sure how I would define f_1 from the singleton to some arbitrary set
given idk what S is aside from infinite cardinality
stray reef
well
you can use the very arcane and hard to prove fact
that if a set is infinite
then it is not empty
amber prism
woaaaaaaaaah crazy
But I'm still stuck on how 1 element can map to infinitely many, cause in my mind i just have a vertical line in R^2, but if S is like, a set of not-numbers, then I struggle
stray reef
you dont need f1 to be surjective, moshill...
last timber
what exactly confuses you
amber prism
$f_1 : {1}\to S$ How can you make a function when you only have 1 input and infinitely many outputs?
vital dewBOT
moshill1
last timber
that is that S always contains equinumeruous to n subsets
last timber
but cant figure out the base case
f(1) = arbitrary element of A
left yarrow
if f(n)=2f(n-1)+6, f(0)=3 how would i find f(2)=?
last timber
you prolly need aoc here
amber prism
what's aoc?
last timber
axiom of choice
amber prism
if f(n)=2f(n-1)+6, f(0)=3 how would i find f(2)=?
find f(1) then f(2)
last timber
and also recursion
amber prism
Yeah still no clue
unreal stump
Pick an element in S
left yarrow
@amber prism how do i find f(1)?
amber prism
<@!186109587366215691> how do i find f(1)?
plug in n=1
last timber
moshi1 if you are struggling with induction you can do contrapositive
unreal stump
Repeat this infinitely
left yarrow
@amber prism for f(1) is it 12?
last timber
assume exists n s.t no injective function from A_n to S exists
show then that S is finite
unreal stump
And then map {1} to {a} ,{1,2} to {a,b} and so on
amber prism
but {a} isnt S?
last timber
no
unreal stump
{a} is a subset
last timber
{a} is subset of S
last timber
basically you want f_n to be f_{n-1} U {(n, some element not in ran f_{n-1}}
left yarrow
@amber prism is f(1) = 12?
amber prism
ok wait want to make sure I fully understand, how is a point injective (for the n=1 case)?
given the definition of injective needs 2 points/values?
last timber
for n = 1 it is injective because no two distinct point are possible for input
amber prism
right cause only 1 point exists?
amber prism
<@!186109587366215691> is f(1) = 12?
yes
last timber
right cause only 1 point exists?
yes
amber prism
Ok it finally clicked lolol
left yarrow
@amber prism then whats next?
amber prism
find f(2) by a similar method
left yarrow
30?
amber prism
ty @unreal stump @last timber
vital dewBOT
Commander Vimes
Let $T=\{n \in \omega | \exists f_n : n^+ \to S, \text{ f_n is one-to-one}\}$.
$0 \in T$ since $f_0 : 1 \to S$ can be defined by $f(0) = c$ where $c$ is arbitrary element from $S$ (such a function obviously exists by an axiom of choice and injectivity is obvious). Now assume $n \in T$, we show $n^+ \in T$.
Let $f_{n^+} : n^{++} \to S$ be defined by
$$f_{n^+}(k) = \begin{cases} f_{n}(k) \text{, if } k \in n^{+} \\ \text{ some element of } S - \text{ran } f_{n} \text{, otherwise}\end{cases}$$
```Compilation error:```! Missing $ inserted.
<inserted text>
$
l.65 ...f_n : n^+ \to S, \text{ f_n is one-to-one}
\}$.
I've inserted a begin-math/end-math symbol since I think
you left one out. Proceed, with fingers crossed.```
stray reef
$n^{++}$? what a dumb way to say $n+1$
vital dewBOT
Ann
last timber
where tf i have missed $
stray reef
or would that be n+2
stray reef
$n^{++} + n^{++}$
amber prism
idk, seems like a plus to me
vital dewBOT
Ann
stray reef
${}^{++}i + {}^{++}i$
vital dewBOT
Ann
stray reef
amber prism
vimes is struggling more than I did 
quick folio
-i--;```Commander Vimes
last timber
@amber prism so here remains to show that f_n+ is injective
left yarrow
Let S be the subset of the set of ordered pairs of integers defined recursively by: Basis step: (0, 0) ∈ S. Recursive step: If (a, b) ∈ S, then (a + 2, b + 3) ∈ S and (a + 3, b + 2) ∈ S. a). Which of the following ordered pairs is an element in S?
A. (2,2)
B.(0,3)
C.(5,5)
D.(2,0)
is this one B?
minor dagger
so if you have (0,0) in S then (0+2,0+3) and (0+3,0+2) are in S aswell as (0+2+3,0+3+2) and (0+3+2,0+2+3)
pallid belfry
How would I figure out the number of different edge colorings of a K_102 graph using 2 colors? Each vertex would have 101 edges correct?
stray reef
what counts as an edge-coloring in this case?
just any assignment of colors to edges?
coral raven
2^(51*101)?
pallid belfry
just any assignment of colors to edges?
Yes
pallid belfry
2^(51\*101)?
Wher does the 51 come from and is the 101 just n-1
stray reef
51*101 is the number of edges in K_102
coral raven
wait
it might be 50*101
ok look so it's n(n+1)/2
sum to 101
ok so yeah it's 51*101
pallid belfry
When I do (102(102+1))/2 I get 5253 but when I do 51*101 I get 5151
coral raven
yeah so there's 102 vertices
so from the first vertex to every other vertex there's 101 paths
then from the second vertex to every vertex except the first there's 100
then from the third to everywhere except 1st and 2nd, 99...
sum to 101, not to 102
pallid belfry
Oh okay that makes sense. So every vertex just has one less path than the one before it. But where does the 51 come from, I am still confused about that
coral raven
sum as i goes from 1 to n of i is n(n+1)/2
here, we're summing from 1 to 101
101(102)/2 = 101 * 51
pallid belfry
Ohhhh okay. I see what I did wrong. So there are 101*51 edges in the K_102 graph right?
coral raven
think so
pallid belfry
So then there are 2^5151 colorings of K_102?
coral raven
yep
pallid belfry
Hmmm. So if I am trying to calculate how long it would take a computer to calculate if K_102 has an orange k_6 or a black k_6 for every coloring...how would I convert that large number to a time
coral raven
bruh
pallid belfry
Because my calculator cannot give me that large number
wait no. I think I got it
Thank you for your help
vernal oriole
How many distinct permutations are there of the four letters C, C, Z, Z? List them. Of these, how
many are distinct circular permutations? List them
any ideas guys?
Should the first one be 4!/4
so 6
pale epoch
by what?
valid wave
oops
sorry my message didnt fully send
basically
if element b is in the partition of a
thats not a partition anymore is it?
because Pa U Pb wouldnt give us the set of S anymore?
pale epoch
it doesn't have to?
P_a and P_b are parts of the partition, not necessarily all parts