discrete-math

[snow sleet]

because it says to find the rule for the inverse function

[narrow trench]

the inverse is really just asking : "i got here using f, and i know i can go back to one and only one point because f is a bijection, so then how do i do that"

[deft dock]

so then i should just set f(x) = y, and then solve for x?

[snow sleet]

yea so you have to swap x and y and then solve for y

[deft dock]

and thats my inverse?

[snow sleet]

yup

[deft dock]

so then what is also this bs???? it seems like symbols makes things 4 times mroe confusing...

[snow sleet]

so this is saying

[narrow trench]

(if you ignore all the stupid case-switching)

[snow sleet]

For any y in Y, the x that caused f(x)=y, is the same x that causes F^{-1}(y)=x

and there is only one such x

[deft dock]

OHHHHHHHHHHH

okay okay

plain english nice

[snow sleet]

pretty much things are flying back and forth

[deft dock]

also i just realized

that the inverse

[snow sleet]

between codomain and domain

[deft dock]

it was we used to prove on-to

Let y∈R be any real number. Let x = ∛(y+4)

[snow sleet]

well not really

we weren't yet allowed to assume the inverse existed, at that point in the proof

[narrow trench]

well, this is just a more cumbersome way to get the proof done imo

[deft dock]

yeah i thought so because onto doesnt prove one to one and we need that to make an inverse

i was just pointing it out to make sure it wasnt just a coincidence

[snow sleet]

yup he knows

[deft dock]

yeah i wanna be technical becase like

weird prof

and also first proof class and i have no clue what happening lmfao

[narrow trench]

(in the wild, one of the most convenient ways to prove a function is bijective is to just go "look, here's an inverse and it works!")

[snow sleet]

yeah so a function f is bijective if and only if it's invertible

[deft dock]

wait wait

inverse proofs bijective?

[narrow trench]

they're the same thing

[deft dock]

...

[snow sleet]

read this

[narrow trench]

see my comment here

[deft dock]

oh.

wait so

is one to one subjective then?

since onto is injective?

[snow sleet]

huh?

[narrow trench]

it's the opposite i believe

and *surjective

[deft dock]

ohhhh

[snow sleet]

onto isn't necessarily injective

[deft dock]

so onto is surjective

[snow sleet]

yes

[deft dock]

and one to one is injective

[snow sleet]

yes

[narrow trench]

i think it's shit terminology

[deft dock]

ohhhhhhhhhhhhhhh

oh that makes sense

surjective + injective = inverse possible

thus bijective as well

okay okay

[snow sleet]

one-to-one (aka injective). And onto (aka surjective). And one-to-one correspondence (aka bijective)

[narrow trench]

You can see each of those as guaranteeing any potential inverse makes sense

Like, there are two things about functions

It has to be defined at every point of its domain

I can't just plug in a value and have the function tell me nope

[snow sleet]

yeah this is called everywhere defined. We also require well-defined

[narrow trench]

otherwise it's not part of the domain

And second thing, you can't have one input sent to two different outputs

this goes wildly against everything we want functions to be

if you picture these two scenarios in your mind with arrows

Then reverse the arrows

The first one cannot happen if the function is surjective

and the second one can't happen if the function is injective

let me draw it

[deft dock]

okie

actually no that makes sense its fine

i was looking at this as you were explaining

okay finally this all makes sense

now as long as i can actually retain this info

[snow sleet]

@deft dock Another cool fact, showing that a bijective function exists between two sets (the domain and the co-domain) shows that the size of the domain equals the size of the co-domain

[deft dock]

ohhhhhhhhhhhh that also makes sense

since every Y must have an X

okay cool

thanks guys

[snow sleet]

well it's cuz each Y must have exactly one X and those X's will never be the same for another Y since f is a function is injective

You're welcome!

[deft dock]

ah

wait actually can we do one final check?

[snow sleet]

sure

[snow sleet]

read this edited comment^

I made it more clear

[deft dock]

yup saw it

[snow sleet]

good

looks good

[deft dock]

now i gotta start graph theory

[snow sleet]

dope

[deft dock]

wait actually hold on

is this inverse correct for

this?

because im looking at this question and all the inverses are in terms of x...

[narrow trench]

well, setting it equal to y is convenient because it helps you keep track of what is what

but the name actually does not matter

f(x)=x or f(y)=y are both the same thing

[deft dock]

okay dope so this is fine then?

[narrow trench]

yes

now you may reconsider your other answer

[deft dock]

the one with the big x? if so gotcha

[narrow trench]

this one

[deft dock]

yup yup

[narrow trench]

oh also, beyond trying to actually invert the equation, you can also just check that f(f⁻¹(x))=x

that's what the inverse is meant to do

[snow sleet]

to find the inverse you swap x and y and solve for y @deft dock

[narrow trench]

(though be careful, the other way around doesn't work : you can have f(g(x))=x without f and g being inverses ; heck, they may not even be bijective)

[deft dock]

okie

[deft dock]

gotcha

[narrow trench]

(if you want a convincing example, f(x)=floor(x/2) and g(x)=2x, on the integers)

[deft dock]

is my understanding of this correct?

[zinc marsh]

are you dealing with directed or non directed graph ?

[snow sleet]

this is because the sum of the degrees isn't even

[remote cosmos]

prob nondirected

[snow sleet]

The first requirement is that the sum of the degrees be even.

[deft dock]

"No such graph exists, as there is an odd number of vertices with an odd degree rather than an even number. Also the sum of the degrees isn’t even"

?

[deft dock]

unsure it just says graph everywhere

[snow sleet]

you can state it in an easier way

[deft dock]

yes please

[snow sleet]

you can say. The sum of the degrees is odd. So this can't possibly be a graph.

[zinc marsh]

how a non directed graph with 5 vertices can have a vertex of degree 5 though, it can only be maximum 4 right?

[deft dock]

wait dont i have to include the other part?

the prof does

[snow sleet]

okay, then include the other part

my prof would be fine with just the sum

but def do what your prof suggests

[deft dock]

okie

[zinc marsh]

@snow sleet sum of degree = 2 * number of edges right ?

[snow sleet]

yes

@zinc marsh

[deft dock]

but both have to be true correct?

[snow sleet]

yes

[deft dock]

okay

[snow sleet]

otherwise the sum isn't even

this is why you can just focus on the sum

because what happens with the terms, affects the sum

[deft dock]

ah understood

also is there a difference between simple and just graph?

simple graph vs just graph?

[snow sleet]

yeah if I'm remember correctly, I think simple graphs don't allow loops and doesn't allow multiple edges between a pair of vertices

a quick google search confirms this

[deft dock]

ah okay

do the same rules apply?

in terms of finding out whether or not it exists?

[snow sleet]

yes

[deft dock]

yeah it'd be even anyway if im understaning correctly

oop nvm

[snow sleet]

So loops don't change the test for whether it's not a graph because it adds an even number, 2, to the degree sum. @deft dock

[zinc marsh]

It comes from the fact that whenever you add an edge, there are two nodes that increases degree by one

[deft dock]

yes understood

[deft dock]

?????

why did she draw two between v1 and v2...

[snow sleet]

wait

[deft dock]

LMFAO

[snow sleet]

good question.

[deft dock]

[snow sleet]

wtf

[deft dock]

she says:

"We took advantage of the idea of parallel edges"

idk what that means

in the video

[snow sleet]

that is a graph, but not a simple graph

because a simple graph doesn't allow multiple edges between any two vertices

[deft dock]

yeah thats what im thinking

its the last day of the semster and she hasnt responded to any emails so wtv ig

ill just keep it in the back of mind

[snow sleet]

yeah I'm not sure what she's thinking

[deft dock]

yeah she doesnt mention the not being allowed to have multiple edges between two verticies

only the loop part

[snow sleet]

when I took graph theory, all we talked about was simple graphs and my prof always made it clear that we weren't considering graphs with loops or parallel edges

[deft dock]

and google confirms that

[snow sleet]

yeah no multiple edges are allowed between any two vertices

[deft dock]

wait what

[snow sleet]

wym

read it^

[deft dock]

ohhhhh i read it as "yeah no, multiple edges are allowed between any two vertices"

[snow sleet]

oh

[deft dock]

instead of "yeah, no multiple edges are allowed between any two vertices"

[snow sleet]

put the comma right after yeah

[zinc marsh]

I have an exam on graph theory and network theory tomorrow

[deft dock]

also what

[zinc marsh]

it is giving serious headache

[deft dock]

hee hee i finish the semster today and my final is on Thursday

[snow sleet]

are you asking how to do this?

[snow sleet]

yup sounds like graph theory lmao

[deft dock]

yeah

[snow sleet]

okay, so first off note that if the sum of the degrees isn't even, that can't be a graph. This doesn't mean that if the sum of the degrees is even, that it can be a graph.

[deft dock]

oh.

[snow sleet]

Since the sum is even, you need to go further and look at whether (5,3,3,3,2) is a valid degree sequence

there's a method for this that I'm blanking on cuz it's been a fat minute since I took graph theory, but there's a method that allows you to reduce those numbers down so you can determine if it's a graph

[deft dock]

does it involve any of the answer choices up there?

[zinc marsh]

it's multiple choice question

look at other alternatives

rule them out

always harder to explicit construct a graph with given property

[deft dock]

well i have no clue because our prof did not give us rules for simple graphs

literally did two questions and left out an entire rule (which im now just learning)

oh lol made a guess

[snow sleet]

I think the third one is correct

[zinc marsh]

yeah

[deft dock]

yup got it; is that a rule i should keep in mind?

[snow sleet]

oh cool, that's what you put

yes

do you know why it's true?

[deft dock]

and only for simple graphs right

[deft dock]

nope

[snow sleet]

right

Okay let me explain

so consider a complete graph...all of it's degrees are maximized

a complete graph is a simple graph too

you know what a complete graph is, right?

[deft dock]

no...

prof only mentioned a graph and barely mentioned a simple graph

[snow sleet]

okay, then think about it this way:

[deft dock]

and then moves on to something called Euler something idk

[snow sleet]

if some degree is >= the number of vertices, what does that mean?

doesn't that mean a loop occured or multiple edges?

[deft dock]

is that greater than or equal to?

[snow sleet]

yes

[deft dock]

wait let that sink in one second

[snow sleet]

okay

times up

[deft dock]

ohhhhhh yes yes

[snow sleet]

lmao

jk jk

[deft dock]

multiple for different verticies

makes sense

ah so if that happens its no longer simple

[snow sleet]

so if some degree is >= the number of edges, then the pigeon hole principle guarantees the graph isn't simple anymore, a contradiction

[deft dock]

pigeon hole

[snow sleet]

yup it's very helpful in counting

[deft dock]

this means there are 6 verticies correct

because 9 edges means 18 total degrees

and if each verticie has 3 degrees, then 6 verticies

[snow sleet]

yeah this is because each edge contributes to the degree sum at each edge. Hence the degree sum is 2*9=18

and then divide by 3 since all vertices are of degree 3.

yup good @deft dock

[zinc marsh]

is shortest path in directed graph preserved under positive length scaling ? yes right ?

[snow sleet]

I'm not sure on that one @zinc marsh

[deft dock]

jeez are you guys in a like discrete math on steroids class?

[snow sleet]

<@&286206848099549185> Anyone know the answer to @zinc marsh 's question?

[deft dock]

half the stuff you guys mention ive never heard of

[zinc marsh]

I have a proof in my head

[snow sleet]

lmao no it's graph theory

[zinc marsh]

for that

[deft dock]

ohhhhh lmao

[zinc marsh]

writing that down

[snow sleet]

I took graph theory a couple semesters back

I didn't like it all that much tbh

too many definitions

[zinc marsh]

Call the original length function c. Let m1,m2,m3,... the possible path lengths under c. Say m1 is the the minimum length. Under scaling it becomes km1,km2,km3,... for some positive constant k

we already know that m1 <m_i because it is the minimum by assumption.

Then we have km1 <km_i

so it is preserved

sounds good ?

[snow sleet]

sounds good to me from an algebraic standpoint. I'm still not sure if that holds in a graph theory perspective

[zinc marsh]

Well i will know the answer after I submit it 😄

[snow sleet]

LMAO

[zinc marsh]

I slacked off too much during semester

Now doing all the exercises

this night

it's 2h13 AM now ))

[snow sleet]

wow

just wow

😂

[zinc marsh]

it is correct

But wow

shortest path is not preserved under length addition

ah yeah of course

now that i think about it, some paths can pass throughs more node than others

so under length addition it will stretch out more

[deft dock]

this doesnt have an Euler trail correct?

because more than two points have an odd # of degrees?

and could someone check this?

[deft dock]

<@&286206848099549185>

[zinc marsh]

Does there always exist non-negative integer m,n s.t: mp+nq=1 when p,q are coprime?

By bezout we know that m,n exists when it's only integers

we know (m+kq, n-kp) is also a solution, so it should be possible to force m to be positive

but I don't think we can always force n to be positive

ah

nvm

i understand it

[civic horizon]

Not necessarily

See the chicken nugget theorem for an explicit bound

Assuming p and q are positive

[zinc marsh]

@civic horizon Yeah you are right. The problem was my translation of the verbal problem to mathematical problem, it was wrong there is a sign error. The statement itself is false.

[cerulean wind]

is that the actual name of the theorem?

[civic horizon]

Thats the name i know

[cerulean wind]

that’s awesome lol

[civic horizon]

Its pretty cool

I think the name comes from a numberphile video where they try to buy 43 nuggets

Which is impossible given how many nuggets mcdonalds sells at a time or smth

[zinc marsh]

the coolest theorem name i have heard of: Monstrous moonshine theorem = )

[civic horizon]

Moonshine is cool

Unfortunately i dont understand the statement :D

[weary tiger]

i:=1 definition ? can someone help me out rq so i dont have to search through my textbook

[stray reef]

??

[weary tiger]

i := 1 to n

[stray reef]

is this part of an algorithm description or something?

[weary tiger]

the " := " is what i dont understand

[stray reef]

is this Pascal code?

if it is, := is the assignment operator

and generally, := is used when you're either assigning a value to some variable or introducing a new notation by defining it to be equal to something

[weary tiger]

here is whole code

for i := 1 to n

print a[i]

[stray reef]

okay great

yeah

this is just a for-loop with the variable i going from 1 to n

incrementing by 1 at every iteration

[weary tiger]

gotcha thanks, the ":" through me off

[pallid lintel]

what does a loop of a matroid look like in its geometric representation?

its only proper subset is the empty set, which is independent and so contained in every basis, but what would that look like in a drawing of a matroid?

[long mica]

Is there a biconnected eulerian graph which is not Hamiltonian?

[weary tiger]

Hi, how to know whether a group is isomorphic to another or not?

[spiral grove]

Try to find a group isomorphism (bijection that respects group properties) or show that there cannot be one :)

[weary tiger]

Ok thanks

Isn't there a way to check with something like checking whether they're relatively prime or not?

I heard about that

Also, are all groups with a prime order cyclic?

[spiral grove]

You might want to look into the Chinese Remainder Theorem

[weary tiger]

Okay I'll do that

[weary tiger]

And about this?

[civic horizon]

true

its a good exercise

[weary tiger]

Also, can one use Euler's method for gcd in polynomials?

[stray reef]

euler's method?

[red nest]

Maybe you mean euclid’s method? In that case yes you can

[tired jacinth]

please help

[waxen nest]

hi what is the in order and post order for this tree?

[stray reef]

@waxen nest do you know how to construct in- and post-order traversals?

it's a simple algorithm

[waxen nest]

nope

[stray reef]

so you don't know what those things even are...

for an in-order traversal, you:

• traverse the left subtree
• visit the root
• traverse the right subtree

in that order

traversal of both subtrees happens recursively of course

[waxen nest]

so what will you get for the post order and in order for the tree? I think it would be easier for me to understand if you could explain it based on the tree example

[stray reef]

i'm going to construct an example of my own so as not to just give out the answer

if you visit the vertices by the numbers in increasing order, you get the in-order traversal

if you visit them by the letters in alphabetical order, you get the post-order traversal

does that help clarify things for you?

[loud copper]

shouldnt vertex B be 3 for in-order traversal ?

[waxen nest]

not really.. i kinda understand how to do the traversal in this one but not the example hmm

[waxen nest]

ye i was thinking this too lol

[stray reef]

shit you're right

3 and 4 should be swapped

good catch

[loud copper]

[stray reef]

okay, RZ, do you have an image-editing tool?

like MS paint?

[waxen nest]

yea

[stray reef]

okay

do you want to do the in-order first or the post-order first

[waxen nest]

in order

[stray reef]

okay

[stray reef]

look at this tree

we need to identify the left subtree, the root, and the right subtree

what letter is at the root of your tree?

[waxen nest]

U

[stray reef]

correct

now, use MS paint to highlight the left subtree of the root by surrounding it with a rectangle

note that either subtree may turn out to be empty at any point within our process

[waxen nest]

?? theres no left subtree of the root?

[stray reef]

and that's exactly why i said subtrees may be empty

the left subtree of the root is empty. there is nothing there

[waxen nest]

ohh okay

[stray reef]

so since we're doing in-order, after the (currently empty) left subtree comes the root

[waxen nest]

yes

[stray reef]

so for our traversal, we will now write down U at the beginning

[waxen nest]

okay

[stray reef]

and now we traverse this tree in-order

highlight the left subtree of this tree

[waxen nest]

oooookay

whats next

[weary tiger]

ok thanks

[stray reef]

okay sorry i just came up with a better way to visualize this i think

so we started with this, when we identified that U will come first in our traversal

now we split that big tree into its left subtree, right subtree and root

and just keep doing that until all the nodes are alone

does this make more sense to you?

[waxen nest]

so theres 2 root here? S and I?

[stray reef]

what are you talking about...

no there aren't two roots

[waxen nest]

so we have U N I and then whats the next letter

[stray reef]

well then we have that subtree that i haven't broken down yet

i was expecting you to keep going on your own

suppose i was wrong to do that

the next two steps are this

[waxen nest]

oh okayy nice

but what if we are given the inorder and postorder

and then asked to construct a tree based on it

what is the thought process behind it, like how do we know when to go left or right since its not as easy as inserting numbers in BST

[stray reef]

in the post-order traversal the root always comes last

in the in-order traversal the root comes between the left and right subtrees

start with that

@waxen nest

[waxen nest]

ohh can i dm you?

[stray reef]

no, say whatever you wanted to say here.

[shut basin]

What’s a good book to start with

[cinder sail]

ik a vvveeeeery nice book for proofs n logic (but none in a broader field for discrete)heh

its "how to solve it" by g. polya :D

its like so 🤌 when u read through the logic its amazing

[shut basin]

Thanks

Can I get it on Amazon?

[next thorn]

@dim geyser yo bro

@dim geyser hello

Hello anybody

@median dagger hello

@rugged forge hey

@cerulean wind its u again

[cerulean wind]

stop mentioning people. do u have a question or not

[next thorn]

I do

[cerulean wind]

go ahead and ask it then

[next thorn]

How was the length incorporated??

@cerulean wind so it's like this now I just wait😬😭

[cerulean wind]

i’m not entirely sure what this is so i don’t want to answer. im sure somebody else does tho.

however, this feels more like a calculus/multi-variable calculus question to me. definitely not discrete math

[gritty crescent]

@next thorn Don't ping users at random without their prior consent.

[next thorn]

@gritty crescent consent to ping people
Hey csn I ping u lmfao

[limber token]

kicked

this is annoying

[stray reef]

thank god

[deft dock]

would this be an appropriate proof?

my prof did sum weird bs and brought in arguments so im trying to see if my way works

[cerulean wind]

yea this works. every element of A is in A U B

[deft dock]

pog

[snow sleet]

This works. Not sure why any one's proving this though because this proof is trivial

[deft dock]

no clue either im just studying for my final and making sure i know everything

because i made some stupid mistakes on the last test we had

Exhibit A:

i cried after seeing i got this wrong

[snow sleet]

Ah gotcha

Lmao way to go

[tight radish]

somebody knows how to solve it?

alguien sabe soluciar este ejercicio?

solucionar

[snow sleet]

It would help if you posted that in english @tight radish

I'm guessing you're trying to prove those equations by induction

[tight radish]

yes

[snow sleet]

okay I can help you with this then

[tight radish]

"for all natural n large enough"

[tight radish]

thanks!

[snow sleet]

what do they mean large enough? Shouldn't it be for all natural n?

induction only works if we know where n starts from

[tight radish]

a predicate p (n) is said to be true for all n large enough if there exists a n0 E N such that:
An E N ....: p (n) is true.
Determine which of the following three predicates are true for all natural n large enough

[remote cosmos]

@tight radish como va

this is strong induction

[tight radish]

yes very hard

[snow sleet]

@tight radish @remote cosmos will help you as I can't speak spanish and @remote cosmos can

[remote cosmos]

si viste inducción antes, lo que significa strong es que es más estricto que lo normal

significa que no es verdad para todos los valores de n

en vez, es verdad para los valores de n después de un valor específico

no sé cómo le dicen en español ya que todo mi entrenamiento matemático fue en ingles

pero me entiendes?

ah si, justo me fije y tiene el mismo nombre: inducción fuerte

un ejemplo muy típico, la diferencia entre n! y 2^n

cual es más grande?

[tight radish]

2^n??

[remote cosmos]

miremos

2^1 =2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32

y n!?

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120

parece que empezando n=4, n! es más grande...

entonces para éste tipo de situación sirve la inducción fuerte

porque podemos decir que, empezando n=4 en adelante, n! > 2^n

y basta nada más comprobar el caso de n+1

como se hace en la inducción regular

entiendes?

entonces lo que busca tu pregunta es: esas ecuaciones tienen algún valor n al cual empiezan a ser verdad desde ahí hacía el infinito?

@tight radish, dime si te queda alguna duda

y si no: suerte!

[tight radish]

muchas gracias!

tambien tengo este ejercicio

[tight radish]

y este

[tight radish]

somebody know how to solve it?

[red nest]

What does the question translate to in english?

[cerulean wind]

for a predicate p(n) we say that “p(n) is true for all natural numbers n sufficiently large” if there exists an n_0 in N such that for all n>= n_0, p(n) is true.

consider the following inequalities:
….
which of the inequalities are true for all n sufficiently large?

that is what is says up to “Orientacion”

the bottom choices give options like only 1 and 3, or only 1, none of them, etc

[deft dock]

do circuits always have to have the least amount of gates?

like for this one, for P and Q and ~R, could we have done them all separately and feed them all at once into an AND gate?

as in getting rid of the black one

[red nest]

Thanks

[deft dock]

wait actually...

if we did that we'd have less gates

so im guessing they dont always have to have the least amount of gates?

and we can just draw however?

[remote cosmos]

It depends

Different gates schemes will have different time complexity

[remote cosmos]

Usually have to draw to some specification

But also does this go in discrete math? This is a computer arch question

[unreal stump]

Let's see. This doesn't go in any other channel

So it goes into discrete math

[deft dock]

[tight radish]

@remote cosmos bro viste la ultima que envié? sabes resolverla?

[remote cosmos]

Qué probaste lucas?

[abstract iron]

what was that

version of fermat's little theorem

where p is prime and b is a positive integer less than the value of p

[red nest]

b^p=b mod p?

[abstract iron]

I legit forgot

[tight radish]

esta

con 10

[abstract iron]

but I know there were different forms

[tight radish]

@remote cosmos

[red nest]

Some people write b^(p-1)=1 modp but these are really the same pretty much

[abstract iron]

ok thanks saketh

[red nest]

Np

[abstract iron]

do you know how to use the probabilistic primality test?

trying to figure out if 11 is prime

[red nest]

No i don’t

[red nest]

I think it might be

[abstract iron]

rip

I think so too but I want to make sure

proof wise

[faint narwhal]

There are a lot of probabilistic primality tests, which one do you mean?

[abstract iron]

the main one. I just want to prove if 11 is prime or not.

[tight radish]

thanks bro

[abstract iron]

have you used the probabilistic primality test before?

[cerulean wind]

no hay un problema bro

shit i dont actually speak spanish lmao, sorry if that sounds weird or whatever

[abstract iron]

lmao

[faint narwhal]

there is no main one

[tight radish]

ajjajas

"no hay problema" that's how it is

[tight radish]

no

how is that?

[errant bear]

11 is odd and doesnt end in a 5 so its probably prime

[deft dock]

why is this the case...

[cerulean wind]

try using the fact that $(P\rightarrow Q)\leftrightarrow (\neg P\vee Q)$ and the idempotent law, assuming its allowed, that $\neg(\neg P)\leftrightarrow P$

[vital dew]

coycoy

[weary tiger]

(red bit)

does anyone know what 'ordered r-tuple' mean

I feel like skipping the section because the book

[pale epoch]

basically an ordered list of length r

[weary tiger]

oh

[pale epoch]

so order matters and duplicates are allowed (unlike for sets)

[weary tiger]

so (a,b) is not equal to (b,a)

?

[pale epoch]

ye

unless a=b

[weary tiger]

understood

[deft dock]

well no its not a question; shes saying to just do it in general...

also how does the bottom part make any sense???

shouldnt it be (p -> q ) and (q -> p) = p < - > q ?

instead of r?

[stray reef]

yes it should

[wary scarab]

I got the answer as 1023×4 can someone check?

[deft dock]

okay this is a little confusing

i can write a formal proof saying that it is one to one

but also find a counterexample?

beacuse i can say:
Let x1 and x2 be any elements Z such that h(x1) = h(x2)
Thus, (x1)^4 = (x2)^4
Hence, x1 = x2 so this is one to one

But a counterexample would be to let n = 2 and n = -2. n(2) = 16 = n(-2)

all of a sudden its not one to one

could someone clear up if im doing something wrong?

[proven silo]

The thus (x1)^4=(x2)^4 and therefor x1=x2 is wrong because of for example your counterexample

[deft dock]

but how would ik its wrong?

[proven silo]

Because a number raised to an even power is always greater or equal to 0

[deft dock]

what?

but how does that help me?

like im trying to say that if i started to write a proof, and i saw that x1 = x2, i would have just said its one to one without trying to look for a counterexample

[proven silo]

Well you can’t just go from (x1)^4=(x2)^4 to x1=x2 just like that

What made you think you could

[deft dock]

taking the 4th root of both sides

[proven silo]

Just like x^2=1 has two solutions, x=+- 1 so does x^4=1

[deft dock]

oh yeah

just realized...

[proven silo]

When taking root you have to add +-

[deft dock]

hmph okay just realized thanks

[proven silo]

Can you show how you arrived at that?

[wary scarab]

a1 can be 2,4,6,8 - 4 choices

a2 can be anything so cases:
i) 1 then a3....ak can take (9 C k) numbers where k varies from 0 to 9
(We choose k number and arrange it in ascending order)
ii) a2=2 now the rest can take 8 C k numbers so proceeding similarly I get: sum 9 Ck + sum 8 C k +... upto a2=9 so a3 has to be 9 so answer =4(2^9+...+2+1)

[wary scarab]

is this correct

[proven silo]

Logic seems good

[waxen nest]

can someone help with b ii AVL tree?

[vital dew]

abs_0

[marble pivot]

ignore

[cerulean wind]

no. just take x = y = z = 1 to see that it’s not 8

[wary scarab]

Can someone explain why the last line is true

[wary scarab]

<@&286206848099549185>

[mystic moss]

Each strip contains 2rt(n) vertical side lengths and the total length of all strips is 1

Do you have the rest of the proof btw?

[wary scarab]

I do

[mystic moss]

Can I see it? 👀

[wary scarab]

Ahh i get it, idk why i was so confused

yeah 1 sec

[mystic moss]

Thanks!

[tranquil flint]

how do we solve recurrence relation when its raised to a power?

like b{n+2}*b^3{n} = 4b^4{n+1}

[unreal stump]

You don't

[tranquil flint]

😭

[unreal stump]

There is no known standard technique for that

Oh wait that's easy

[tranquil flint]

theres a hint to use bijection

[unreal stump]

Take logarithms on both sides

[tranquil flint]

f(x) = a^f(x)

for all real function f, and real a>0

[unreal stump]

Preferably log 2

You reduce that to a linear reccurence

[tranquil flint]

so itd be log(bn+2) + 3log(bn) = 16log(bn+1)?

[unreal stump]

No

log(b_{n+2})+ 3 log(b_n)= 4log(b_{n+1}) + log 4

[tranquil flint]

oh fuck yea

then treat logbn as my new an?

[unreal stump]

Yes

And do your usual manipulations

[tranquil flint]

so an+2 +3an = 4an+1 + 2

[unreal stump]

Yes

[tranquil flint]

omg ty

is that the same thing as substitution

of f(x) --> 2^f(x)?

since its bijection^

[unreal stump]

you find a_n and 2^(a_n) will be the solution

So maybe

[tranquil flint]

how to count # of bijective functions

from {1,2,...n} to {1,2,...n}

such that f(f(x)) = x

for all x in {1,2,...n}

using reccurence*

like suppose an = # of bijective functions satisfying this property

then # of bijections w this property from {1,2,...n-1} to {1,2,...n-1} is an-1

and # of bijections w this property from {1,2,...n-2} to {1,2,...n-2} is an-2

is it just an = n*an-1?

since we picked the first element

[unreal stump]

Yes

[tranquil flint]

Any hints how to solve such recurrence

very much stuck

[grave totem]

doesn't this imply f(a)=b => f(b)=a

[tranquil flint]

yea

[grave totem]

so say Tn is the number of such func for 1..n

[tranquil flint]

the way to count it is

Tn = nTn-1

i think

[grave totem]

then Tn+1 😦 that n+1 goes to n+1) + n+1 doesn't go to n+1,

tf

$T_{n+1} = T_n + nT_{n-1}$

[vital dew]

Ryuzaki

[tranquil flint]

Uh isnt that just

[stray reef]

wait do you have to use a recurrence relation

[tranquil flint]

Tn = n Tn-1

[stray reef]

i believe i can come up w/ an explicit formula

[tranquil flint]

Uh im using a generating function

probably have to but maybe not

[stray reef]

well, explicit-ish

[tranquil flint]

i was using tn x^n/n!

[grave totem]

he did ask for recurrence

[tranquil flint]

err yea before, but i found it, now need a formula for tn haha

[stray reef]

$\sum_{k=0}^{\floor{n/2}} \frac{n!}{2^k k! (n-2k)!}$

[vital dew]

Ann

[grave totem]

$T_{n+1}-T_n = nT_{n-1}$ and adding them up may give an explicit one

[stray reef]

i think it's this

[vital dew]

Ryuzaki

[stray reef]

i might be wrong

im trying to do it combinatorially

[tranquil flint]

assuming tn = ntn-1 is it?

LOL WTF

Oh wow

[stray reef]

each term in the sum is the number of permutations which swap exactly k pairs of points

or at least, each term is meant to be that

i am strongly suspecting i might have gotten something wrong

[tranquil flint]

is this formula correct? shouldnt it be$T_{n} = nT_{n-1}$

[vital dew]

Ramtin

[tranquil flint]

i think i need to provide closed formula 🥲

but ur a genius for coming up w that on spot LMFAO

[grave totem]

T1=1, T2=2, T3=4? am i correct?

[grave totem]

your formula gives T3 = 3*T2 = 6

Well i might be wrong idk

[tranquil flint]

Uh not sure what Tn values are xpt

T0 = 1

[grave totem]

like if we have n+1 things, we can map the n+1 th to n+1, so that gives us Tn

[tranquil flint]

Noo that gives Tn+1

err

[grave totem]

Now if we map n+1 to any of 1,2...n, we have Tn-1, but as we can choose that to by n ways so nTn-1

[tranquil flint]

Ummm

[grave totem]

that's why Tn+1 = Tn+nTn-1

[tranquil flint]

it should be Tn = nTn-1 cuz we map first object

then n-1 objects left count them in Tn-1 ways

[grave totem]

no because after u map the first object, where it maps to also must be mapped back to 1

so we loose 1 DOF there

[tranquil flint]

yea like you have nC1 options to map

then u map it as an input

but the output loses one option too

and we need the rest of the [n-1] to [n-1] to map according to restraint

in Tn-1 ways

[grave totem]

calculate first few values of Tn then compare ig

also you may be forgetting that we can map 1 to 1 also, i.e. f(1) =1

[tranquil flint]

its f(f(1)) = 1

but yea

like pick one element

then map it according to

[grave totem]

either f(1)=1 or f(1) = a which case f(a)=1

[tranquil flint]

Hm

[quaint star]

This is correct, just to confirm.

Suppose you have n+1 elements. Fix one of them and call it x. If x maps to itseld, then you just need to construct f for the other n elements (T_n ways of doing this). If x maps to something else, say y, then y also needs to map to x. So you need to construct f for the other n-1 points, and also take into account there are n choices for y.

So T_(n+1) = T_n + nT_(n-1)

[tranquil flint]

Hm

Oh i see

[grave totem]

good

[tranquil flint]

I was

doing it only consixering 2nd case it seems?

[quaint star]

Yeah, I think something like that

[grave totem]

Tn = (n-1)Tn-1

[tranquil flint]

Wellll if thats case time to change my reccurence formula

w generating functions

ty guys

[tranquil flint]

wait is this true too?

[grave totem]

no only considering 2nd case

leave it it's done

[tranquil flint]

So tn = tn-1 + ntn-2, any idea how to solve it explicitly

[grave totem]

.

[quaint star]

It would be (n-1) in the second term

[tranquil flint]

oh yea

[quaint star]

I mean T_n = T_(n-1) + (n-1)T_(n-2)

[tranquil flint]

Damn they only give t0, i need to solve t1 aswell

cuz this reccurence only defn for n bigger than 2

or equal

[quaint star]

Number of bijective functions from {1} to {1} isn't hard to find

[tranquil flint]

t1 = 1

t2 = 2

ok true

[stray reef]

let me graph my thing

[tranquil flint]

yikes im supposed to use exponential generating function to solve it

and take derivativez

🙃

[stray reef]

this is what my formula gives

[tranquil flint]

LMAO im so dumb

if it was tn = n*tn-1

tn would just be n!

😐

[quaint star]

[stray reef]

,w T(n+1) = T(n) + n*T(n-1)

bruh

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by Ann#0413

[stray reef]

yeah this isn't the right recurrence then

or is it?

[grave totem]

think it's wrong for n=0

if we set T1=1,T2=2 then it'll be correct ig

[quaint star]

,w T(n+1) = T(n) + n*T(n-1), T(1) = 1, T(2) = 2

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by Lunasong#7197

[quaint star]

Cry

Idk how to input it

[stray reef]

lmao rip

[kind tapir]

Does anyone know of an example of a not-too-difficult result about finite graphs that makes sense for and happens to also be true for infinite graphs, but requires a different - more difficult - proof?

[grave totem]

that's a strange type of question

[faint narwhal]

Menger's theorem might be such an example

[tranquil flint]

On same question

This cant be right...

e' = e(1+x) + 1

is like

not solvable on any ODE calculator

[unreal stump]

This is definitely solvable by parts

[tranquil flint]

NVM

im an idiot

b1 = 1

and

then theres no +1 at the end

and then its very easy ODE

otherwise

it was ODE that needed erf(z) function or somethin

😭

[runic blade]

kindly help please anyone.

[sour arrow]

Let's go at a simpler question first. Given that you flip a coin 7 times, what is the probability of exactly 4 heads? @runic blade

[low carbon]

Im confused by g.

oh its an empty set nevermind

[dense geyser]

If you ever see a symbol you don't recognize, you can (usually) go to http://detexify.kirelabs.org/classify.html and draw it, and it'll tell you what it is

[marble pivot]

that is fantastic thank you

[fierce osprey]

can someone point me in the right direction to start this?

do I need to prove that it works for all n in N and all r not equal to 1, or do I only need to prove the part about r?

either way I’m a bit stuck on what to do with the two variables..

[cerulean wind]

fix a real number r not equal to 1 and show that the claim is true for all natural numbers using well ordering and then induction

there is also a direct proof without using induction or well ordering

[fierce osprey]

Do you mean just prove it for all n, and not worry about proving it for all real numbers, r?

Because I can prove the part without having to specify r super easily…

i’d just do something like this

base case:
1 = (1-r^(1))/(1-r) = (1-r)/(1-r) = 1

inductive step (n => n+1)

1 + r + r^2 + r^3 + ... + r^n = (1-r^(n+1))/(1-r)

add r^(n+1) to both sides...

1 + r + r^2 + r^3 + ... + r^n + r^(n+1) = (1-r^(n+1))/(1-r) + r^(n+1)

= (1-r^(n+1) + r^(n+1)(1-r))/(1-r)

= (1-r^(n+2))/(1-r)

[proven silo]

Fix a real number not equal to 1 just means r is an arbitary value not equal to 1 which value doesn’t change (so fixed).

You could also just add for all r not equal to 1 in every line but that is rather annoying

[cerulean wind]

once you use it for any arbitrary r not equal to one, you will have proven the statement for any r not equal to one, just as scape prof said

[dreamy sky]

Open-ended question: Can you deduce Plancharel’s formula for the Fourier Transform from the Parseval relation for the Discrete/Finite Fourier coefficients, using a limit argument?

Can someone help with specific answer.

[fierce osprey]

Thanks so much @proven silo and @cerulean wind

if you guys are still interested in my little problem, I’d appreciate a quick glance over what I’ve come up with for the well ordering part

[cerulean wind]

do you mind just sending an image?

[fierce osprey]

ah sure I didn’t do so at first because it’s a bit lengthy, what with all the proper etiquette :)

[cerulean wind]

hmm. not sure why you have the contrition that r >= 2 when you have just fixed r in the set C

[fierce osprey]

Oh that was from something else weird I was playing with

Should be all r not equal to 1

[pallid lintel]

is there a software program that generates duals of planar graphs (as a picture)

[slim bone]

why is n^2log(x^2) big-O simplified as n^2log(x) and not n^3? Shouldn't log(x) just be O(x), then the product rule would multiply them?

[vale cairn]

I mean ig that's technically correct too, but loses precision?

I assume you mean n not x in any case

[slim bone]

i'm just asking because the expected answer of a question is x^5log(x) and not x^6. is there a rule of when to keep log(x) and when to simplify it?

[primal wing]

log(x^2)=2 log(x)

so n^2 log(n^2) is just 2 n^2 log(n)

[slim bone]

i know, then the 2 is irrelevant

i'm asking why xlog(x) isn't further simplified to x*x then x^2

[primal wing]

oh, it is but it's less accurate

it's basically in O(x^a) for any a>1

[slim bone]

so is there a rule determine when one should, or should i just never simplify log(x)

[primal wing]

always keep it I'd say

[slim bone]

sounds good

well should xlog(x) stay but log(x) be simplified to O(x)? my professor didn't tell us when to simplify and when not to

[vale cairn]

i don't see why you'd ever want to change log x to x unless i'm missing something

ig it's more complicated functions you might simplify?

[slim bone]

i honestly learned everything i know about big-O simplification in the last 6 hours, ive had to simplify log(x) for some prior questions but now I don't

so i'm assuming i just should avoid it

[remote cosmos]

sometimes in an induction proof you want to do this to get a certain expression

but in general the log(x) says more about the behavior

than not having it

[slim bone]

good to know, i'll be learning induction proofs later today

[weary tiger]

guys

don't know where else to ask this

but uh

for transitive relations

if a R b and b R a and b R c and a R c but a not R a, is A transitive

[primal wing]

Well, if aRb and bRa, and R is transitive, then aRa

So if you don't have aRa then R is not transitive

[iron marsh]

Quick fix: the goal is to determine if R is transitive, I don't entirely know what A is.

[last timber]

it is false

consider empty relation

vacuously transitive but not reflexive

@iron marsh how dare you miss this

[minor pumice]

((p ∧ q) ∧ r) ∨ ((p ∧ q) ∧ ¬r)) or ¬q)→ s

how to I get started on simplifying this?

[last timber]

well for beginning you can denote p ^ q as t

so you have

[minor pumice]

we haven't learnt that

[vital dew]

Commander Vimes

[last timber]

it is not some particular method you learn

it is just way to simplify writing

[minor pumice]

ok

is that specifically for p and q

or a variable

[last timber]

if you have long ass expression A nested in long ass expression B you can denote this expression by single letter A or whatever

to simplify writing

[minor pumice]

oh yeah we use a and b

[last timber]

and i used t here

simplify this now

[minor pumice]

dont know how

[last timber]

firstly simplify premise

use distributive properties

[minor pumice]

I dont know how to apply them

they seem different

[fiery hare]

Does this mean to say that a single element b serves as the inverse for both operations?

If so, can someone help me prove it?

[faint narwhal]

no it doesn't, its pretty badly worded

the b's in the two equations can be different

Think about F_3 with a = 1 for example, you have that 1 + 2 = 0 but 1 * 2 = 2 not 1

[fiery hare]

Alright yeah. It seemed weird because I could not confirm it from google.

Thanks for the counterexample as well :)

[pine star]

for j
Basis: delta, b elements of S
Induction: If x is an element of Sm then a(2x), b(2x+1) are elements of S
Is that a correct answer?

[stray reef]

what's delta?

also what is 2x+1 if x is a string?

[pine star]

Delta is an empty string

Should it be 2x + b ?

[weary tiger]

I'm not familiar with this notation for strings, but wouldn't you get e.g. aab using this definition?

[pine star]

Hmm

I guess I should specify that strings are homogeneous

[stray reef]

are you sure the symbol your course uses for the empty string is δ and not λ?

also i still don't know what you mean when you write "2x"

[weary tiger]

Yeah that is quite strange

I think you're allowed to condition on whether the string contains a or b

[stray reef]

if x is a nonempty string in S, then the string formed by attaching two copies of the first symbol of x to the beginning of x is also in S

and the initial elements of S will need to be "", "aa" and "b"

[marble osprey]

any Discrete math for beginner ?

trying to find one but ended up no result

[weary tiger]

How to prove it is pretty good I'm told

But it depends on what you want to do, discrete math is not one thing

[median jackal]

Eight people including A and B seated around two identical tables, each having capacity of 4, The number of seating arrangements possible so that A and B are not on the same table is.....

[distant glade]

dev1ce you're asked this in 5 different channels already

have you even attempted the problem? @median jackal

[remote cosmos]

show your attempts and some ppl might be willing to help

[weary tiger]

The phrasing of the question makes me less likely to attempt it, seems as if you're demanding an answer

[tired jacinth]

<@&286206848099549185> could someone help me with this question

[median jackal]

@distant glade I solved it 🙂

[iron marsh]

So first, try to find the probability of a flush. This should not be too hard.
Next, note that the second condition really isn't as bad as it looks. For instance, 3,4,5,6,8 is NOT a sequence

[tired jacinth]

i think i figure it out thank for your help

if anyone know this one

pls help

[weary tiger]

These just require an understanding of the definitions involved

Which one don't you get

[pine star]

We have been using an upside down V symbol to indicate empty strings.
Also, I revisited the problem today. I did two conditional if statements:

Basis: Δ, b elements of S
Induction: If x is an element of S, and a is an element of x, then aax is an element of S.
If x is an element of S, and b is an element of x, then bbx is an element of S.

hmm wait that wouldn't work because a is not an element of Δ

instead of 'a is an element of x' I could just say 'b is not an element of x'

[weary tiger]

Upside down v is capital lambda

$\Lambda$

[vital dew]

cpl

[weary tiger]

And why not just add aa to your basis

In any case, either of those is good

[pine star]

good point

[warped pecan]

Can someone offer some guidance here

I tried doing by cases but there are way too many combinations to consider

[faint narwhal]

Assume (b) is false (because if it were true then you'd be done), and try to show that (a) must be true

@warped pecan

[warped pecan]

@faint narwhal then there are no three vertices I can choose such that there are no edges between any two of them

[faint narwhal]

I'd think more about the contrapositive

In other words, for any three vertices, there is an edge between at least two of them

[warped pecan]

Isn’t that the definition of a cycle

Ahh no

At least two

Does this have to do with choosing?

[faint narwhal]

I'm not sure what you mean by that

[warped pecan]

Like 6 choose 3 and then so,etching about the two vertices that have an edge between them?

[faint narwhal]

not really

Pick a single vertex and look at if its connected to the 5 other vertices

[warped pecan]

I mean it has to?

[faint narwhal]

why?

[warped pecan]

So say yo7 form two groups of 3

There has to be at least one edge in each

But then we said we are not in b so we need to add an edge in each group because I can always grab the two unconnected vertex in one group and one from the other and have them not be connected

[faint narwhal]

But this doesn't tell me why every vertex must be connected to some other vertex

[warped pecan]

Oh hmmmm okay I’m not sure

I thought I had something but no

[faint narwhal]

The idea is to look at a single vertex

there are 5 other vertices

[warped pecan]

Yes

[faint narwhal]

so you must have at least three that are either connected to this vertex or not connected

by the pigeonhole principle

[warped pecan]

Wait why

[faint narwhal]

there are 5 vertices

each one of them is either connected or not

Imagine trying to put 5 balls into two boxes

one of the boxes must have at least 3 balls

[warped pecan]

Ahhhh yes

So for each vertex there are three vertices that are either connected or not to it

[faint narwhal]

okay so how do you conclude?

[warped pecan]

Ehhhhh

I know you can’t have all of them not be connected to at least three?

[faint narwhal]

Again, think about your first vertex

You know there are at least three connected or three not connected to this

split it into two cases

[warped pecan]

If there are at least three connected that does not imply a cycle right because it can be like a-b a-c and a-d

When we say at least two not connected the other three can still be connected right

[pine star]

fpr b and j, How do my answers look?

[red nest]

b looks good, but j seems to be a bit wrong. Firstly you have two different things you are calling t, the tail of the list and the size of the list. Secondly, your definition will always just give us a list of size 2, infact your definition doesn’t even mention x_t and x_(t-1) on the left hand side but then uses those two things on the right.

[pine star]

to create a list of size n of entries <x_1, ..., x_n> , I would do:
j(n)= if n>1, then j(n-1)::(x_n)

so for this I might do something more like:
f(g,h,t) = if t>1, then f(g,h,t-1)::(g(x_t),h(x_t)

I suppose I could just do f(t) right?

f(t) = if t>1, then f(t-1) :: (g(x_t), h(x_t))

or:
f(g(x_t), h(x_t)) = if t>1, then f(g(x_t-1), h(x_t-1)) :: (g(x_t), h(x_t))

[red nest]

Look, f as a function will take g,h and a list (say x::t). What you’ve written here doesn’t particularly make sense. So if f(g,h, x::t) is given to you do you see how to recursively make a list? Something along the lines of (g(x),h(x))::f(g,h,t) will work. You can make your idea work too, but you’ll have to write it up differently, you need to write the list as b::e where e is the ending of the list and b is the entire list except the lasf part. Then you can do something like f(g,h,b::e)=f(g,h,b)::(g(e),h(e)). Its just that usually lists are inductively defined with the head as the first element followed by tail of the rest of the elements

Sorry for the late response

[kindred portal]

any hints on how to prove the theta portion of the question?

[pine star]

the textbook uses x::t and I guess I just don't understand how that is a list. Maybe I need to read more.

a list beyond <x,t>

**

[red nest]

Ah ok, so here is an explanation for the notation, a list [1,2,3] can be written as 1::[2,3]. So basically what it means is that x is an element, t is a list and x::t is the list you get by putting x at the start

[pine star]

so x::t = <x,t> ?

or is it <x,t,...,t_n>

my book doesn't explain this, at least not in this chapter. it's just gleaned vaguely in the answer key once

[red nest]

Ok, then let me define some notation, it might be different from your book but it shouldn’t be too much of an issue. My lists will be elements separated by commas in a square bracket. So [1,2,3,4,5] is a list. Now given a list t=[t1,t2,..,tn] and an element x. The list x::t is the list [x,t1,t2,…tn]

[pine star]

that makes sense, thanks

[weary tiger]

So a list [1,2,3] is actually defined internally as 1::2::3::[]

It's just the ::, or cons, operator all the way down

[fossil ember]

Does anyone recognize this sequence set? {(7,4),(6,3,4,0),(0,0,0,6,2,2,3,4)} the sets are ordered so 7->4->7->... etc

[pallid lintel]

what do you get if you take the set who's only element is the empty set and delete the empty set from it

?

[faint narwhal]

I'm not sure what you mean by delete, but it seems you would just get the empty set

[pallid lintel]

${ \emptyset }$ - $\emptyset$

[vital dew]

stroggoz

[pallid lintel]

you dont get something like ${ }$ ?

[vital dew]

stroggoz

[pallid lintel]

i dont know any set theory

[queen lichen]

You do get that yes

,,\emptyset = {}

Lol

[vital dew]

mymoomin

[pallid lintel]

ya latex did same thing for me

[queen lichen]

[pallid lintel]

nvm

[stray reef]

@bold relic

[bold relic]

thanks

Hi

anyone knows how to derive this formula?

C(n+r-1,r)