discrete-math

[weary tiger]

yeah its not

because g(f(x)) is not the same as f(g(x))

yes

but monoids don't require commutativity

dont i need to show its closed under composition too

@weary tiger

f and g are functions from A -> A, so f(g(x)) will also be A -> A

and the set A^A, contains all functions from A -> A by definition

right

t!rep @weary tiger

[uncut grove]

🆙 | yami has given @weary tiger a reputation point!

[weary tiger]

thank

uwu

[stray reef]

$\circ$ btw

[vital dew]

Ann:

[weary tiger]

fucking hell

lmao

[weary tiger]

lmao

[modest zealot]

can a relation be neither symmetric or anti-symmetric?

also, wtf does an antisymmetric definition have to do with the matrix relation, its like they somehow are NOT related at alll

[quaint river]

yes

[modest zealot]

wait how so

🤔

oh wait nvm

for second question, how do the asymmetric definition and matrix connect?

[quaint river]

say you have

(1,2,3,4)

[modest zealot]

mhm

[quaint river]

{(3,4),(4,3),(1,2)}

[modest zealot]

yup

[quaint river]

example of one

[modest zealot]

not symmetric or asymmetric

[quaint river]

yes

[modest zealot]

so the only 3 possibilities, are, either it is symmetric, antisymmetric, or neither symmetric/antisymmetric

[quaint river]

idk what you mean by matrix

[modest zealot]

lemme link something ginmme a sec

[quaint river]

it also can be both symmetric and antisymmetric

[modest zealot]

wait how tf

oh

if theres nothing

[quaint river]

like

no

[modest zealot]

like there are no relations, then its technically symmetric and antisymmetric

cuz there is no initial condition to begin with

[quaint river]

like equality

[modest zealot]

from the definition of symmetric and antisymmetric

[quaint river]

a = b -> b = a

equality is an example

¯_(ツ)_/¯

[modest zealot]

hmmmm

gotcha

ok so for example

u know the transitive relation

the definition

and matrix representation make sense logically

but for asymmetric, that shit dont make sense for soem reason

like the definition of asymmetric states that

if (a,b) and (b,a) are relations, that implies a=b

how tf is that related to

this

i dunz get it

[quaint river]

so im assuming if row,column is 1 that means they are related

in that order

yes?

[modest zealot]

ye

using matrices to represent relations

like i understand the connection between the defiinition and matrix of transitive, symmetric, and reflexive

i just dont get assymmetric

[quaint river]

so you have (a,b) , (b,a) -> a = b

[modest zealot]

yes

[quaint river]

so that means if $ a \ne b$ then (a,b) = 0 or (b,a ) = 0

[vital dew]

Victoria:

[quaint river]

which is what its doing there

[modest zealot]

im assuming its an exclusive or then

[quaint river]

reflecting across diagonal gives you the corresponding symmetric relation

like (a,b) reflected across diagonal gives you (b,a)

[modest zealot]

oh wait no

its not exlusive or

its inclusive or

ok

that mkes a LOT of sesnse

[quaint river]

so they're just making sure

when reflected

you dont have two 1's

[modest zealot]

oooOOOOHHHH

but having two 0's is okay

gotcha

[quaint river]

the diagonal doesnt matter because

along the diagonal the values are just (a,a)

[modest zealot]

cuz they never match the initial condition anyways

only way for an implication to be false is when the intiial condition is true and conclusio nis false

[quaint river]

uhhh

yes? i think you mean statement

idk

[modest zealot]

p-> q

T T T
T F F
F T T
F F T

P/Q/p->Q

[quaint river]

but anyways thats why antisymmetric is like that

[modest zealot]

ye ye ye ye

gotcha gotcha

[modest zealot]

is there a method to check transitivity of a matrix using boolean square?

[modest zealot]

I heard u have to keep doing the boolean squarw til its the same or something

[modest zealot]

actually let me rephrase, how to you take the transitive closure of a matrix by using boolean squre

square*

cuz the only thing i know is to keep taking the boolean square til you get the same matrix, and then take the disjunction of all those matrices to get the transitive closure

[modest zealot]

Warshall's algorithm

oooooooo

apparently this is the transitive closure algorithm

hmmmmm

[west crater]

Which proof method should I use?

for the ExAy stuff I'm not sure how to go about it

[stray reef]

do you know what $\exists$ and $\forall$ mean?

[vital dew]

Ann:

[west crater]

yeah, so that statement would translate to "There exists an X such that for all Y P(x,y)"

So I have either find an X that works with all Ys or show that it doesn't somehow

[stray reef]

or show that no such x exists

[west crater]

right, that's where I'm confused

how do I show that?

[stray reef]

can you state the negation of $\exists x \forall y (x+2y=xy)$?

er

[vital dew]

Ann:

[stray reef]

there. fixed the quantifiers.

[west crater]

$\forall x \exists y not (x+2y = xy)$

I think

[vital dew]

Frank:

[west crater]

i dont know how to write the not part, sorry lol

but i think thats how it works, right?

[stray reef]

you may as well replace $=$ with $\neq$

[vital dew]

Ann:

[stray reef]

but yes

try proving that the way you would prove a "for all x ..." statement

[west crater]

okay thanks lemme try that

umm this proof seems even harder to play with. So now I have to show that will all X this is true, this is true there exists a Y but there are a lot of things that will make the inequality true for any x but I don't know how to prove it for all of them

I guess, because usually I would try to just find contradictions, but I'm not sure what I can do when I have to go through all of them and can't think of a contradiction at the top of my head

I remember there's a couple of proof methods, proof by cases and proof by contraposition ( which I think that's what we were trying to do) but I'm not that strong in using those proofs when I have a universal generalization

[sour arrow]

@west crater
Still looking for it?

[west crater]

yeah

well kind of, I think i might have an idea, where I could find an x value and that x value should be true for all the Ys

i think

if it isnt, then its false

im just reviewing this method to see how to do it

unless you have another idea, it could help

[sour arrow]

Anyway, use this:
x + 2y = xy
x - xy = -2y
x(1 - y) = -2y
x = -2y / (1 - y)

Let's say y = 1. What's x?

[west crater]

-2/0

or undefined

[sour arrow]

So, there's no x for THAT y

[west crater]

OH

okay so if im trying to prove a universal like this, I can try to put it so that y has a part that isnt defined

So that would make it so that p(x,y) doesnt exist from x -> y

i see

that actually helped a lot, is this proof method pretty useful for all of these quantifiers?

[sour arrow]

Let's do this a different way:
x = -2y / (1 - y)

If y = 0, x = 0
If y = -1, x = 1

This shows that there's no single x for all y

There's a few ways to go about it

[slow socket]

in graph theory, theres a theorem that says
D_1(G) + 2D_2(G) + 3D_3(G) + ... = 2 * |E(G)|

how do i find D_1, D_2, etc..

i think i have to find the degree sequence but idk how

[slow socket]

nvm, got it

[weary tiger]

hey folks, just wanna verify that I know why we can use proofs by contradiction

i'll type out my reasoning here, and if you see that its correct/incorrect please let me know

normally, in a direct proof we'd be interested in evaluating something in the lines of p -> q

that is "p implies q"

if p is false, we know that the statement is vacuously true

so we're interested in cases where p is true

now, if p is true and q is true, then p -> q is true and we're good

but if q is false, then p -> q is false

now, the contradiction involves first noticing (via a truth table) that the statements p -> q and (p ^ ~q) -> (r ^ ~r) are logically equivalent

where ~ is negation, and r is some conclusion

we note that r ^ ~r is always false

so if we can show that p ^ ~q is false, then we get F -> F which is true, thus proving p -> q is true

in other words, we then first negate the original conclusion (q) and keep the original hypothesis (p)

if we're able to arrive to a conclusion as r ^ ~r (for example, we start off by assuming n^2 is even and at the end we get to n^2 is odd) then we've successfully shown that it is a F -> F (true)

and thus the original claim p -> q is true

i'm still working out more problems so pls tag me for feedback - thanks!

[sour arrow]

@weary tiger
Contradiction isn't usually for statements of the form A → B, you're usually better off using another method in those cases. Contradiction is useful in that it proves statements without an "if then" form

Contradiction goes like this:
Take a statement you want to prove, call it A. Assume A is false

Take a statement that you know is false, we'll call it B.

Show that ¬A → B. That is, show that our assumption on A will prove a statement we know is untrue. This obviously can't be the case, and so our assumption must be wrong; A is true.

[weary tiger]

We’ve mostly used them on ones with if them form, but also for ones like prove sqrt(2) is irrational, etc

Your nomenclature is confusing me a bit, but I think I get the overall picture

You’re basically stating the same thing that if the end result (what you call B and I used r ^~r) is something known to be false, then the original claim (which you call A) will make A -> B true only if A is false as well

[mossy palm]

@weary tiger perhaps another explanation is, in classical logic, there are two truth values T and F, and that every proposition is either T or F

that is, the law of excluded middle holds for every proposition P, (LEM): (P or not P)

then for a proof by contradiction you assume not P, obtain a contradiction C somehow, then as a consequence of LEM, for LEM to hold, you are then justified to conclude P

[weary tiger]

👍

[slow socket]

how can i figure out if graphs are isomorphic

[neon pasture]

sounds hard in general

if they are small you can just check some special properties

like how an isomorphism preserves degree

and loops

and cycles

[mossy palm]

@slow socket do you know what a graph isomorphism is?

[slow socket]

is not just edges and vertices u have to check im pretty sure

theres other stuff

[slow socket]

This is wat i got.

[slow socket]

i can check the cycles ?

[neon pasture]

check the degree of the vertices

and for the rest of them build an isomorphism

if you suspect they are isomorphic

[twilit wadi]

can any one explain transitive in this example

transitive

[stray reef]

what do you need explained here

[twilit wadi]

in (i) it is said reflexive and transitive

I understand reflexive in (i)

I do not understand transitive

R = {(4,4), (5,5), (6,6), (4, 6)}

to prove transitive

(a, b) belongs to R

(b, c) belongs to R

then there has to be (a, c) that belongs to R

from the example (4, 4) and (4, 6) I think (a, b) and (b, c)

where is (a, c)

[stray reef]

if (a,b) = (4,4) and (b,c) = (4,6) then (a,c) = (4,6)

so transitivity is not broken there

@twilit wadi

[twilit wadi]

so we do not need extra (4, 6) in the set

[stray reef]

wdym

(4,6) is already in there

[twilit wadi]

@stray reef thanks

I mean (4, 4), (4, 6) and again (4, 6)

[stray reef]

from (4, 4) ∈ R_1, (4,6) ∈ R_1, and transitivity of R_1, you would deduce (4,6) ∈ R_1, but that's one of the premises anyway.

[twilit wadi]

thanks

[weary tiger]

Can someone tell me what this does?

[craggy gale]

it recognises a language

or rather, it accepts or rejects words

this one looks like it recognises the language of words over the alphabet {0,1} which lengths are odd, but I'm not sure

[neon pasture]

yeah

but its not minimal so thats dumb

[weary tiger]

is there such thing as an asymmetric digraph?

i don't understand what one would look like

i can see it on matrix's or functions

i guess all you can do is the reflexive one

for anti symmatry

[weary tiger]

@weary tiger i thought of an asymetric digraph, all it would look like would be 4 points

with 4 loops relating to themselves for example

[echo lintel]

quick question

if X = {{1} , 2 , {3}}

why is {{3}} a subset of X

and not {3}?

[velvet spire]

if {3} was a subset of X that would imply 3 is an element of X, which it isnt

but {3} is an element, so {{3}} is a subset

[echo lintel]

ahh makes sense, thank you

that would also make {{1}} a subset then

thanks

and would {2} be a subset then?

because 2 is an element

[stray reef]

exactly

[echo lintel]

thanks a bunch

[void valve]

Hello all, I have a hard time understanding why the number of solutions to equations of the type ax≡ b (mod n) is the same as gcd(a,n)

Like i get that theres probably some simple fact that I'm missing from the fact that it can be rewritten as ax-ny=b (it can, right?)

[hexed rune]

Fix a solution to ax-ny=b. Given another solution how can we get a solution to ax - ny=0?

[azure lichen]

for the solutions you also mean modulo n I assume, otherwise there ought to be infinitely many

[void valve]

So adding the gcd you mean?

Yeah b is the remainder

I'm not sure if I understood you guys correctly

I mean yeah, there are infinitely many but just all the ones that are relevant in Z_n

[hexed rune]

So first (assuming there is at least one solution) you can show a correspondence between the solutions to ax-ny = b and the solutions to ax - ny= 0

Then ax-ny=0 iff ax =ny, so iff ax is congruent to 0 mod n

[void valve]

Sorry man I don't understand any of that. How can ax-ny equal 0?

Do you mean rewriting it as gcd(a,n)=ax-ny?

[hexed rune]

suppose a x_1 - n y_1 = b and a x_2 - n y_2 = b

Then (x_1 -x_2, y_1 -y_2) is a solution to ax-ny =0

Similarly given a solution to ax-ny=0 we can fix a solution to ax-ny = b and get another solution to ax-ny = b

So if you fix one solution to ax-ny = b you get a correspondence to the solutions to ax-ny=0

Similarly in mod n, there is a correspondence between solutions to ax Congruent to b and ax Congruent to 0

So it makes sense that the number of solutions will be fixed no matter what b is

[void valve]

Ok, sorry may I ask you to walk me through this example with real numbers? For 8x=10 in Z_14 we have that 8(10+7k)-14(5+4k)=10. How can I create the correspondence to ax-ny=0?

Two different values for k don't produce 0 as you suggested

[hexed rune]

We know 3 is a solution to 8x = 10 mod 14. Now given another solution n consider (3-n), which will be a solution to 8x = 0 mod 14

Now given a solution m to 8x = 0 mod 14 consider 3+m. It is a solution to 8x = 10 mod 14

[void valve]

aha! like (3-10)?

3+m for any m or solutions?

[hexed rune]

Solution to 8x=0 mod 10

So you just have to figure out how many solutions there are to 8x = 0 mod 10

In this example

[void valve]

You're blowing my mind, perhaps I'm missing some prerequisite but how did you conclude so easily that for another solution n, (3-n) would be a solution to 8x=0 mod 14?

[hexed rune]

Have you taken Linear algebra?

This is how you solve systems of linear equations

[heady sedge]

can i get some help with this

[void valve]

Ok, @hexed rune, thanks for helping me. I'll think about it for myself a bit and work up the linear algebra

[hexed rune]

After this you just have to figure out the number of solutions to ax = 0 mod n

I was just referencing linear algebra because it's the same method

[void valve]

Ok so there are gcd(a,n) solutions for n|ax in Z_n they're all multiplied by 0

like there is a row of zeroes?

or no

I don't know I probably have to sleep on the issue, it is probably very trivial. At least according to my book that left out the answer to the question

[hexed rune]

https://brilliant.org/wiki/linear-diophantine-equations-one-equation/

Read the section on general solutions to linear diophantine equations

[void valve]

ah, ok I never had such a formula for finding all solutions, I just added and subtracted the lcm, but so the intuition is that as lcm is m*n/gcd. There are gcd number of solutions before it wraps over so to speak, correct?

[hexed rune]

Yeah basically

[void valve]

because their abm/gcd(a,b) is the same as the lcm

or at least any multiple of the numbers

ok, I think I get it, thanks a lot 😃

On a completely unrelated note, how do you find brilliant? Is it wort getting to practice this type of stuff? Do they provide lots of practice questions?

[hexed rune]

I just searched for an explanation of the general solution to linear diophantine equations online and they were the first link lol

I don't usually use them

It seems alright though

[void valve]

alright, got you. I might give them I try sometime

[heady sedge]

number of total bitstrings is 25

then to find P(B) it is 2^n-1 so 16 P(B)=16/25

then to find P(A and B) I find number of bitstrings for 0 1's, 1 1's 3 1's

that also gives me 16

so 16/25 again

and I don't know what I'm doing wrong

[opal crescent]

25 total bitstrings

you sure lad?

[heady sedge]

2^5

oh

woops

32

god

[opal crescent]

"then to find P(A and B) I find number of bitstrings for 0 1's, 1 1's 3 1's" and 0 ain't odd either

[heady sedge]

my brain is busted sorry

[opal crescent]

time to debust your brain

💤

[echo lintel]

https://gyazo.com/29150a80484469b2d78dd736b2140408

hey quick question

is it a/(b+c)

because it would be set up as

a(k+j) = (b+c)

then you divde the (b+c) over

to make it a(k+j) / (b+c)

but you dont need to write out (k+j)

[analog sonnet]

???

[tranquil jungle]

what was the original question @echo lintel

[iron bloom]

@echo lintel a|(b+c) is read as "a divides (b+c)", which means (b+c) is divisible by a

Its not the same as a/(b+c)

[wispy vortex]

ft fs

[dense thicket]

Yes

[wispy vortex]

ok

ft fs lt

[dense thicket]

Perhaps.

[wanton sable]

can anyone help me understand this please? :(

i don't get the second calculation mainly

they're trying to do 0 - f, and to do that you have to borrow, right

but if you're borrowing the top number should change to 0x1ef0, right

and then do f-f to get 0

instead they have 0x1f10?

i don't know where that 1 came from

[stray reef]

the second calculation is doing 10-f already having borrowed

the 1 represents said borrowing

@wanton sable

[wanton sable]

yeah I got it, I mistook f as being 16 when it's 15

ty though

[echo lintel]

does anyone know anything about structural inductions?

https://gyazo.com/770cb3d4732987b5082dcc4ae64b0116

i can't find any good videos

[wooden swift]

Does anyone know how to do this in excel because I have no idea, the book just says a spreadsheet

[sour arrow]

@wooden swift
You can grab/drag the bottom right corner of a cell to "extend the pattern" and excel should be able to do each with that

[narrow heron]

why is the converse equal to inverse ?

https://cdn.discordapp.com/attachments/290271171818029056/568616488169111552/unknown.png

example they used

[sour arrow]

@narrow heron
The converse is the contrapositive of the inverse

p → q = ¬q → ¬p
You can always switch the order and apply a ¬

So, do that to the inverse:
q → p = ¬p → ¬q

[narrow heron]

OHHHHH

Thanksss man now i understandd :)))

[azure lichen]

how was that in any way an explanation?

oh, I guess it is if you understood the contrapositive

[narrow heron]

With the explanation, now i understood mathemathically why inverse is equal to the converse.

Also from computer science server, someone explained logically to me as shown below :))

Rlly appreciate the help from you guys ;)

[marble mason]

I would like to find a point such that its distance to any lattice point is unique (unique in that its distance to any other lattice point isn't the same). Does such a point exist?

@narrow heron isn't the inverse just the contrapositive of the converse

...and that's why they're the same...

[narrow heron]

Yes agree!! Didnt see that at first 😂

you guise pointed it out so i found out ;))

[mossy palm]

@marble mason can you tell me what u mean by lattice or link a wiki page? i forgot and there seems to be multiple concepts with the same name

[weary tiger]

lattice point

point with integer coordinates i mean

[marble mason]

yea

that

[azure lichen]

intuitively I'd say any point with irrational coordinates should do the trick

[marble mason]

why?

[azure lichen]

because my intuition says so

[weary tiger]

lol

[marble mason]

ok...

[languid drift]

I think you could argue that a point rational coordinates is on a line with rational coefficients, and if that is so, then it's on a line whose every point is the same distance from two lattice points.

[mossy palm]

does this work? pick the red dot

[azure lichen]

there's more lines than those

anyway, reasoning is this:

(my reasoning is flawed)

(I stand by my intuition tho)

[weary tiger]

i mean this question is equivalent to asking: does there exist a point such that, for all circles drawn with this point as the center, at most one lattice point lies on any circle?

so i don't think it can be true

[stray reef]

hmmmmmm

i have a sledgehammer argument for the existence of a point of the kind sought

[weary tiger]

pls give sledgehammer

[mossy palm]

i dont think understand what lattice is then. its it not just the set of points (x,y) with x,y being integers?

[stray reef]

the lattice is Z^2, yes.

call a point "bad" if there exist two lattice points from which it is equidistant, and "good" otherwise.
now, for each pair of lattice points, their perpendicular bisector will consist entirely of bad points.

let B be the union of all such perpendicular bisectors

claim 1: B is exactly the set of all bad points in the plane
claim 2: B has area 0, so its complement is nonempty

[azure lichen]

oh yea that works

neat

[stray reef]

not constructive tho

[azure lichen]

I was trying to invoke the structure of R^2 as a Q-vector space so

[marble mason]

What is B?

[azure lichen]

but yes, your argument seems fine

what ann just defined it as

[marble mason]

Is it a set?

[stray reef]

B is the set-theoretic union of all the bad-point lines

yes, it is

[marble mason]

What is its area tho?

[azure lichen]

and it's a countable union of lines

[stray reef]

0

[azure lichen]

0, because it is a countable union of sets of area (lebesgue measure) 0

[marble mason]

What do you mean by the area of a set

[azure lichen]

lebesgue measure

[marble mason]

I'll look that up

[stray reef]

😂 see i told you it was a sledgehammer argument

[azure lichen]

hang on

don't look up lebesgue measure

lebesgue nullsets are explainable without all the theory

[marble mason]

Ok

[azure lichen]

a lebesgue nullset is a set which you can cover with (at most countably many) squares of arbitrarily small volume

that is, the sum of the areas of the squares can be chosen to be as small as you want

[stray reef]

i think the set of all lines that comprise B is exactly the set of all lines with equations expressible in the form ax + by = c with a, b, c rational.

[azure lichen]

so eg R seen as a subset of R^2, you can pick squares as follows:
-enumerate the rationals somehow
-for the n-th rational, pick a square with it in the middle and side length ɛ*2^{-n}

then the sum of the areas will be ɛ, and it covers the whole line as the rationals are dense in R

you can choose epsilon as small as you want and this construction will work

so R is a nullset inside R^2
and the lines ann is using are just rotated versions of R

[stray reef]

yeah ok so if you choose x and y so that {1, x, y} is algebraically independent over Q, then (x,y) will not lie on any of those lines and as such will be a good point

so... (sqrt(2), sqrt(3)) is one

🔨

yeah sorry i'm kinda... using overly advanced terminology here

[wintry hawk]

would {a} x {(a,b)} = {(a,(a,b))}

[stray reef]

yes

[wintry hawk]

ok cool

[bitter latch]

could anyone kindly explain why xH = 110

[stray reef]

just do the matrix multiplication lol

(modulo 2 ofc)

[bitter latch]

wouldn't xH = 111

[stray reef]

nope, the third entry is 0

1 + 1 = 0

[bitter latch]

how do you calculate it? cause the notes didn't list down on how it works

I kept do XOR and sum

this is what i've done

[stray reef]

h

okay sorry i need to go now

[bitter latch]

I got it now, the later calculations were that, which confuses me

[compact basalt]

Hey guys. I know this is a really bad question because of how incredibly unspecific it is, but does anyone have any useful tips or techniques when it comes to proving anything? I've got my discrete math final coming up in 2 weeks and while I know all of the material and I understand it, whenever it comes to actually proving something I always fumble and make stupid mistakes. So yeah, does anyone have any tips or literally any helpful advice for constructing formal proofs.

[fickle fable]

There's not a lot that can be said in general, you use very different techniques in different subjects

e.g. graph theory/combinatorics, you're often using induction. Analysis you wanna think about yourself as playing a game against the thing you're trying to bound and you're sorta wrestling for control

For discrete, again induction is key

Counting things two different ways is usually helpful

In graph theory, drawing pictures is a double-edged sword

Remember a lot of your identities and try to apply them when possible if you can make some things look like other things

Also note the logic of the situation and in particular, when deciding to prove a statement or its contrapositive, or whether you should gun for a direct proof vs contradiction, it helps to see which set of assumptions each gives you to work with, and in particular, whether a method of proof "gives you an object to work with"

For example, if you're trying to prove a statement of the form "Every X satisfying P also satisfies Q", then contradiction is good, because then you can say "Assume there's an X which satisfies P and not Q". So now you have an object with certain assumptions, and you can explore that objects properties, and fuck something up

(These aren't hard and fast rules but like, if you're stuck on a problem, an attempt with a non-zero probability of either success or failure is better than nothing)

[proven shard]

@compact basalt just practice coming up with proofs

Don't read or look up the proof

Prove it yourself

Or at least attempt to each time you need a proof

[compact basalt]

ok, wow that is a lot of very helpful information
thanks guys 😁

[echo lintel]

How many different passwords are there that contain only digits and lower-case letters such that the length is 6 and the password contains at least one digit ?

[stray reef]

count the number of possible passwords w/o restrictions and subtract the number of passwords with no digits

[echo lintel]

yeaah

i have to put it in

terms of P(x,y) * P(x1,y1)

@stray reef

Digits = 10
Letters = 26
Total symbols = 36
Total possibilities - Only digits possibilities - Only letters possibilities
36^6 - 10^6 - 26^6

sounnd right?

[stray reef]

why are you subtracting off the passwords that contain digits only?

the problem doesn't say your passwords should also contain at least one letter in addition to containing at least one digit

[echo lintel]

36^6 -  26^6

so it should be like this

[stray reef]

yes

[echo lintel]

ahh i read the problem wrong thank you

[slow socket]

when doing logic networks, when i go do the output boolean expression do i simplify, factor? or anything?

for example i got
x,y,z [OR] = x + y + z
x,y' [AND] = xy'
then
x + y + z [OR] xy'

is it just
x+y+z + xy'

[analog sonnet]

Seems right

[celest raptor]

In graph theory, could anyone tell me how I could prove that if Nodes v and w are connected by any path, they can also be connected by an empty path?

Imo it already answers itself but idk

[analog sonnet]

An empty path is a path with no edges, right? Then if two vertices are not the same, how can they be connected with an empty path...?

[edgy plume]

Connected by an empty path ? Not at all.

[celest raptor]

Hmmm

"Prove: If the nodes v and w of a graph can be connected by an arbitrary path, they can even be connected by an empty path."

Am I understanding this wrong?

[analog sonnet]

Ohhh I get it

Well

The empty path is an arbitrary path

Case closed

[celest raptor]

That's what I was thinking

But it also defines "simple path" as a path with 2 different nodes

That wouldn't work, right?

[analog sonnet]

It all comes down to how "empty path" is defined in your context

Well, when two nodes are connected by a simple path, then they're not the same node by definition lol

[celest raptor]

I would translate it but the 3 different words and definitions of path in German are all translated to path

[analog sonnet]

What are the German words

[celest raptor]

Kantenzug, leerer Kantenzug, Weg, Pfad

[analog sonnet]

Hmm

Oh

[celest raptor]

Kantenzug is a series of nodes, leerer Kantenzug is (an empty) series of nodes with v0, if the edges are different in pairs the Kantenzug is called Weg, if even the nodes are different in pairs, the Kantenzug is called Pfad

[analog sonnet]

It's not even agreed upon in the German mathematical community

[celest raptor]

Also these definitions vary from literature to literature

[analog sonnet]

Der Begriff des Weges wird in der Literatur nicht einheitlich verwendet. Die angegebene Definition folgt im Wesentlichen den Büchern von Diestel und Lovász. In unmissverständlichen Zusammenhängen – und vor Allem im Falle der schlichten Graphen – wird in der graphentheoretischen Fachliteratur ein Weg auch direkt über die Folge der benachbarten Knoten angegeben, so etwa bei Aigner und Kőnig. Gelegentlich wird auch der Begriff Pfad für einen Weg verwendet (Steger), wohl deshalb, weil in der englischsprachigen Literatur Weg als path, teilweise aber auch als simple path bezeichnet wird.

[celest raptor]

Yes

It's fucking stupid

My professor uses them differently in his fucking class

[analog sonnet]

That's kinda bad

Really kinda bad

[celest raptor]

I know

"Hahah yeah sometimes I have to check if I'm using the correct word, so please be kind if I use the wrong one"

Yeah no shit if I use the wrong one I won't pass this course

[analog sonnet]

Pfad and Weg seem to mean the same though, according to Wikipedia

A Kantenzug is known as a walk in the English literature

[celest raptor]

Ahh

[slow socket]

how do i find how many spanning trees there are for a givengraph

[neat siren]

You could compute the minimum spanning tree and see how many other edges are available

[azure lichen]

it seems highly nontrivial to me. you can get an upper bound easily, which is (|E| choose |V|-1), but not every set of edges with cardinality |V|-1 is a tree...

you can probably do some dynamic programming algorithm where, say, you count the number of spanning forests only allowing a certain subset of edges or vertices and add them one by one, but I don't see an obvious way to implement it rn

[slow socket]

I have these

It says the answers. Idk is confusing for me

In my notes it says. You remove some of the edges but keeping all the vertices

The first one makes sense but idk the rest

[neon pasture]

you just do it by hand since they are small

and you abuse symmetry to count fast

for number two: the middle vertex separates both parts

so a spanning tree for the whole thing is a spanning tree for top and a spanning tree for bottom

it reduces to counting the spanning trees on the square with a diagonal

which is number three

for number three: divide it by cases
case 1) you drop the diagonal. this reduces to the square, so you know it's 4
case 2) you do not drop the diagonal. then you have to drop one edge on each side, 4 ways
total 8

[modest zealot]

wuts the difference between euler path and euler circuit

wait nvm

can something both have a euler path AND circuit?

or is it strictly one or the other

[sour arrow]

I hate the names for euler path, cycle, and Hamiltonian path, cycle. Why not "edge subgraph" or "vertex subgraph" and we can use the word "closed" if it's a circut?

Also "vertex" sucks. "node" is a much better term

[analog sonnet]

You mean Euler trail* and tour*

Node is shorter but vertex makes more sense when you're dealing with Platonic graphs :3c

I guess it's a more historic naming convention

[modest zealot]

Can a graph be both an euler circuit and euler path?

[lucid ingot]

ehh?

wot

[final surge]

i don't understand this exercise because If Ben, then Alice, if Cindy then Ben and if Don then Cindy, i think if someone is not going to the lecture then the others wont either

[analog dagger]

the truth of Q does not imply P

So alice could still go if ben doesnt

[final surge]

oh i thought i could not use that

oh okay, also i have a question when i say

if ben then alice is ben --> alice, and that means if ben occurs is because alice occurred first ?

[analog dagger]

If P then Q, if P is true then Q is true

[final surge]

so ben --> alice is incorrect ?

because it should be alice --> ben

[analog dagger]

if alice goes ben will go

would be the direct translation

if i am correct

[final surge]

hmmm well that means i can say ben --> alice and alice ---> ben, right ?

[analog dagger]

No

[ivory badge]

Not nececessarily

[analog dagger]

that would be ben will go if and only if alice will go

[ivory badge]

You only know Alice -> Ben

the other arrow isn't given

so no

Can't make arrows that arent there

[analog dagger]

Do you know the truth table for material implication?

[final surge]

yes

[analog dagger]

We have A -> C, B -> C, C-> D

[final surge]

i think it's not clear for me what should i put first and after the arrow

[analog dagger]

Yeah its worded in a strange way

If alice goes then Cindy will go

if ben goes cindy will go

wait

no

ugh

[iron nest]

A->B, B->C, C->D

[final surge]

i have a question if i write

ben --> cindy

what occurs first ? ben being true or false ?

[analog dagger]

that means that if ben goes cindy will go

What do you mean by what occurs first exactly

[final surge]

i don't understand what does

ben ---> cindy

means, i don't know if it means that if ben is true then cindy is true or if cindy has to be true first then ben will be true

[analog dagger]

If ben is true then cindy is true

[dapper rose]

A -> B -> C -> D
Thus, A cannot go because then all 4 will go.

Same with B: 3 will go.

So we get C and D go.

[analog dagger]

^

modus ponens

[iron nest]

I may be wrong here but if we have C and D going, D only goes only when C goes (so C would have to go first), but doesn't C only go when B goes?

[analog dagger]

no

A consequent can still be true if the premise is false

[dapper rose]

You are asking about B -> C. Write out the truth table for ->...

It is possible for B to not go and C to go.

Same with C -> D.

[analog dagger]

If instead we were given B <-> C it would be true

[iron nest]

ah cool

Im interested, what CS topic is that question from @final surge ?

[analog dagger]

I assume its just in one of the CS math classes

We studied propositional logic in my Discrete Structures class(CS250)

[final surge]

@iron nest im using a book called transition to advanced mathematics and one of the topics is logic

[wild harness]

anyone know how to prove this is a equivalence relation?

[analog dagger]

Do you remeber the definition of an equivalence relation?

[wild harness]

let me look in my notes

An equivalence relation R on the set A is a relation R c A x A which is reflexive, symmetric and transitive?

[ivory badge]

ye

[analog dagger]

Yes

so you need to prove that (x,y) ~ (w,z) is reflesive, symmetric, and transitive

[wild harness]

okay so how would I go about for that

[ivory badge]

Well, do you know what those word would require?

[wild harness]

not really when it comes to relations like this

my professor is expecting us to read through the textbook and understanding it

his notes are vague

[ivory badge]

then did you do it

[analog dagger]

basically it follows that x^2 + y^2 = w^2 + z^2

[wild harness]

for which

[analog dagger]

for the relation

thats the relation rewritten

[wild harness]

(x,y) ~ (w,z)?

[analog dagger]

yes

[ivory badge]

For reference, reflexive means $w ~ w$, symmetric means $a ~ b \implies b ~ a$, and transitive means $a ~ b$ and $b ~ c \implies a ~ c$

[vital dew]

Darkrifts:

[analog dagger]

or in this case $(x,y) \cdot (y,x) \implies (y,x) \cdot (x,y) $

[vital dew]

agentnola:

[wild harness]

ok so how would you connect the relation of x^2 + y^2 = w^2 + z^2 to reflexive

so is that all for reflexive or there’s more to it

[analog dagger]

well

[ivory badge]

well show that it holds when you apply it to itself

[analog dagger]

addittion is associative

[wild harness]

i mean it’s the same written on both sides

just flipped

[ivory badge]

oof

[wild harness]

yeah i’m not handling this well as you can see 🤒

[analog dagger]

Yes you are correct

and by the laws of addition a+b = b+a

[wild harness]

but how would laws of addition be applied to this if there’s multiplication

[modest zealot]

how to tell if a graph is isomorphic

[ivory badge]

oh dear

[analog dagger]

oh dear

[modest zealot]

im scared

[ivory badge]

@wild harness Addition applies because there's addition

not much else needed

[wild harness]

so i’m doing x+y = y+x ?

[analog dagger]

there are squares but yes

x^2 + y^2 = y^2 + x^2

[wild harness]

ok so is there anything further to show from that?

[analog dagger]

No, you have proven that the relationship is symmetric

[wild harness]

oh wait I thought we were still proving reflexive

or are we still? i know we still had to do symmetric and transitive

[analog dagger]

I misspoke

I meant reflesive

[wild harness]

okay so after you applied the laws of addition, what’s next

[modest zealot]

uhhhh sooo anyone got a clue how to tell if two graphs r isomorphic or naw

[analog dagger]

nah

[ivory badge]

@modest zealot They have to have the same number of vertices and edges, for one

[modest zealot]

total vertices + edges uh huh

[ivory badge]

@wild harness Now i'd try transitive

@modest zealot In isomorphisms, a vertex with k connections has to map to a vertex with k connections

[modest zealot]

uh huh

is that it?

[wild harness]

wait so this isn’t all for reflexive?

like do i have to prove it reflexive as well for w and z?

[analog dagger]

no

you set w=y, and z=x and verified that they are indeed equal

[wild harness]

so just plug it in and do the same thing?

[ivory badge]

@modest zealot the simplest way to show a graph is isomorphic is to find an isomorphism, and it's nasty sometimes

[modest zealot]

o so essentially an isomorphic graph is really the exact same graph drawn differently

i mean drawn significantly differently

[ivory badge]

Not necessarily

[modest zealot]

like wat

[ivory badge]

a graph is isomorphic to itself

[modest zealot]

how tf do u do this

ok i dont get isomorphism

rip

[ivory badge]

So, in order to show it's isomorphic, just define an isomorphism and show where it sends all points

[wild harness]

so is that how it’s written?

[ivory badge]

like u3 -> v2

[modest zealot]

mmmm could u give an example?

with the question above

[ivory badge]

I did, u3 goes to v2

[analog dagger]

So assume that $(x,y) \cdot (y,x)$

[modest zealot]

o ok

[vital dew]

agentnola:

[analog dagger]

wait

sorry

[ivory badge]

and from that point, you can find where the points connected to u3 can go I think

[modest zealot]

so question, if u3 connects to u2 and u4, does u2 and u4 correspond to v5 and v3?

cuz v2 connects to v5 and v3

[ivory badge]

I'd have to look at it a bit but possibly

[wild harness]

would it be assume w,z • z,w?

[ivory badge]

I'm p sure yeah

[modest zealot]

hmmmm

o wait so isomorphism is really just, u can map a vertex to another vertex in another graph, for all vertexes

and they have same edges

[ivory badge]

isomorphism means you can move the points around to get the same graph if I remember correctly

[modest zealot]

ok yea thats wat i vaguely remember too

[ivory badge]

I'd hope your textbook or whatever could provide a more formal def since my graph theory is weak

[modest zealot]

this the only definition i got

it works tho

[ivory badge]

Ye

basically, it conserves connections

so you can find one by simply moving the points

[modest zealot]

gotcha

kk tyty

another question

how do you coutn the number of possible paths with given length?

or actually, how do u work with adjacency matrixes

[ivory badge]

@modest zealot no fucking clue

[modest zealot]

o

same

hahahahaha

so much material in graph theory

[ivory badge]

I don't even know what the hell an adjacency matrix is

is it like a thing that shows 1->2, 1->3 etc?

[modest zealot]

i only got a picture

gimme asec

[ivory badge]

oh that thing

ew

[modest zealot]

like i have no clue wat it s tlkaing about

[ivory badge]

I don't know what the A4 is

clearly it's something to do with the matrix

graph theory makes me sad

[dapper rose]

$A^4$ is the matrix that represents all paths of length 4. You can get intuition just by multiplying $A$ by itself and noticing that the resulting matrices count the number of paths of length $n$ in $A^n$.

[vital dew]

EpicGuy4227:

[dapper rose]

@modest zealot

[modest zealot]

multiply A by itself 4 times?

so AAA*A?

[dapper rose]

That's what $A^4$ means yes

[vital dew]

EpicGuy4227:

[modest zealot]

kk

[ivory badge]

That's awfully nice that it counts the number of paths, though that does make sense given the definition

[dapper rose]

Yeah I thought it was cool when I noticed it just then.

[final surge]

i have two questions about the exercise i posted earlier

1. of the exercise doesn't say explicitly that if x doesnt go then y wont either, then i could do this ?

A => B => C => D
F F V V

2. when we say an implication is true, what does it mean ? does it mean that A and B are true (in this example that both A and B goes to the talk ? even when both are false?)

||also how do i solve multiple implications like the one in the exercise ?||

[ivory badge]

Well, you know you have exactly 2 people going

and you know that if you have, say, Ben, then it's guaranteed that Cindy goes, which guarantees that Don goes

so there's only one possibility in which only 2 students go

[final surge]

okay so if the exercise doesnt say 'if Ben doesnt go then Cindy wont either' then i can imply that cindy will go even if ben doesnt ?

[ivory badge]

Yes

the arrows only go one way

If you have $P \to Q$ and $P$ is false, then you cannot say anything about $Q$

[vital dew]

Darkrifts:

[final surge]

so if i say P is true then i have to follow strictly the direction of the arrow ?

[ivory badge]

ye

you can't go backward

there's a fancy two-sided arrow $\iff$ but you don't have that

[vital dew]

Darkrifts:

[final surge]

okay but what does it mean when we say an implication is true ? or the truth table for the implication is to have a reference of what we can imply when P is true or false ?

[ivory badge]

$P\to Q$ is true if $Q$ is true when $P$

[vital dew]

Darkrifts:

[ivory badge]

we know the arrows are true in this case, so that means the object at the end of the arrow is definitely true if the first one is

[final surge]

so when we have

P Q P=>Q
F F T

then Q is true ?

[ivory badge]

I can't really tell what that is too well, but i'm gonna take a guess
P is false
Q is false
$P\to Q$ is true

Q is false already

[vital dew]

Darkrifts:

[ivory badge]

The statement $(P \to Q)$ being true only means that if P is true, then Q is definitely true

[vital dew]

Darkrifts:

[ivory badge]

it doesn't mean Q is necessarily true, it just means that knowing P helps you to know Q

[final surge]

oh okay

[analog dagger]

Another thing is that $P \implies Q$ is not casual

[vital dew]

agentnola:

[analog dagger]

So we dont know that P causes Q, all we know is that from P we may deduce Q

[neon pasture]

what do you even mean by causal?

[analog dagger]

P causes Q

which is not what $P \implies Q$ means

[vital dew]

agentnola:

[neon pasture]

what do you mean by P causes Q is the question

[analog dagger]

Im not talking about the question specifically im saying that material implication is totally independent of causality

[neon pasture]

I'm asking what you mean by causality

jeez

the point is that it has nothing to do with math

[analog dagger]

If we know a proposition P to be true, the fact that P is true will necessarily force Q to be true

[neon pasture]

that's what P -> Q means

[analog dagger]

No its not

[neon pasture]

go away

[analog dagger]

That means that from P we may logically deduce Q

'the material conditional statement p → q does not conventionally specify a causal relationship between p and q; "p is the cause and q is the consequence from it"'

why are u being so mean to me 😦

[weary tiger]

i have a quick question
in the congruence of first degree that is this:
i can already tell there will be 4 results, but how to determine exactly which are those ?

[neon pasture]

you are solving 768x + 412y = -1240

use extended euclid

[weary tiger]

oh

but isnt the extended euclid only for gcd ?

i already figured that out but i dont see how to determine the actual 4 solutions

[neon pasture]

express the gcd and then multiply

[weary tiger]

but the gcd is already 4 which tells me there are to be 4 possible result values to this

for x

what should i multiply ? im meant to divide by the gcd to proceed

oh well, i figured out, bezout's equation did the trick, multiplied the given number for x with the number of y while they are both divided by 4

afterwards i did the result with its respective mod

[final surge]

i have a question i asked yesterday but i didn't understand that much, what does it mean when we say that an implication is true or false ? for example

p q p => q
T T T

what does p => q being true mean ?

does that mean that p/q is true ?

[hexed rune]

It means p is false or q is true

[final surge]

ehm

[hexed rune]

That's the definition

[final surge]

okay

but why does it mean p is false ? both can be true

there are three possibilities, right ?

for the implication to be true i mean

[hexed rune]

Do you know the mathematical definition of or?

[final surge]

but i'm talking about implication

and yes

[hexed rune]

Alright here's another equivalent definition

We return true unless p is true and q is false

In which case we return false

[final surge]

yeah but when i know an implication is true i can think of three possibilities, right ? so my question is more about what does it mean for an implication to be true ?

[hexed rune]

It means one of those 3 possibilities is true

If you also know that p is true you can conclude that q is true

[final surge]

true for my case i suppose, okay i have another question if i have multiples implications like

a => b => c => d

how do i do the truth table ?

[hexed rune]

You run home and cry

That's not well defined

[final surge]

oh

hahaha

thanks anyways

[hexed rune]

You can plug in your values, that's often easier than a truth table

If you put parentheses in that expression so it actually means something you can find the truth table if you want

By testing all the 16 combinations and seeing what happens

Or just doing some manipulation

You can write a=> b as -a or b

So just keep doing that until you have an expression only in terms of - and or

And then it's very easy to get your truth table

[final surge]

hmmm i have a question about this

If you also know that p is true you can conclude that q is true

i can conclude that because there is another possibility but that would mean that my implication is false ?

[hexed rune]

p implies q iff p is false or q is true

If p isn't false

Then q must be true

This is called modus ponens

And it's very important

[final surge]

omg this is hard to understand for me, i have a question in the truth table if p is true there's the possibility that q is false, right ? why you can conclude if p is true then q is too ?

[hexed rune]

No, it's the opposite

If p is true q must be true as well

Hence the word implies

We say a implies b if b is true whenever a is true

b can be true when a is false however

[final surge]

and how could i write the case in which p is true and q is false ?

[hexed rune]

That would be false

[final surge]

so i only writes those cases in which the implication is true ?

[hexed rune]

What do you mean?

[final surge]

i mean, you just told me that if p is true and q is false then that is false, and yes but there's no way to express it ? you said we use implies when we want to define a case in which p is true and q is too or p false and q true because those two are true implications

okay i just read some examples and when we say an implication is false then does that mean we can not imply it ?

[analog dagger]

Basically the only time we can say $P \implies Q$ is false is when Q is false

[vital dew]

agentnola:

[final surge]

i don't get this example, S is the set of all triangles or S is the set of all equilateral and isosceles triangles ?

i guess it's the second one, if not P(T2) => Q(T2) would not be correct, right ?

[analog dagger]

I would probably say S is the set of Isoceles triangles

So if Q(T) is always true

[final surge]

oh okay

[analog dagger]

Then P(T) => Q(T) is always true

[final surge]

yea

i was like

[analog dagger]

I agree that's worded very weirdly

I'm not 100% on it

[final surge]

logic is more difficult than i thought

[analog dagger]

It can be strange yes

[weary tiger]

Basically the only time we can say P \implies Q is false is when Q is false
when P is true and Q is false*

[analog dagger]

Yes

[buoyant orbit]

I

I needdd helppp

[edgy plume]

I can help you

First of all, you want to know what are P(X=x) for each x between 1 and 6. And the sum of each of these probabilities is equal to 1, since they are elemental probabilities.

@buoyant orbit ?

[buoyant orbit]

Ya

P=0.15

[edgy plume]

Good

[buoyant orbit]

Then I died from there..

[edgy plume]

Once you've done that, you know that the opposite event (that means not having a 4) is equal to 1-P(X=4).

Or, you can use the binomial law

[buoyant orbit]

W8 its a binomial law?

Qns

[edgy plume]

It can be interpretated as a binomial law, since you repeat the same thing 3 times, without changing it.

[buoyant orbit]

Oh..

So w8 y do I need to find the oppsite event?

[edgy plume]

No, I was thinking about it once, but I changed my mind

[stray reef]

what problem are you doing

[edgy plume]

The one with the biased dice

By the way, there is a typo

[buoyant orbit]

Hmm?

[edgy plume]

It is said "the biased die"

[buoyant orbit]

Oh ya that

[stray reef]

okay so first off clearly p=0.15

$P(N\leq 1) = P(N=0) + P(N=1)$, where $N$ is the number of fours in three throws

[vital dew]

Ann:

[stray reef]

so... $0.85^4 + \binom41 \cdot 0.15 \cdot 0.85^3$, it seems

[vital dew]

Ann:

[echo lintel]

hey question

when do i do P(n,r) vs C(n,r)

like what would the question ask differently

[oak creek]

so permutations are when order matters, for example a phone number

555-5656 is unique compared to 555-6565

those are different

but for combinations, it's when order does not matter

such as a hand of cards

a royal flush in any order is a royal flush

@echo lintel

[echo lintel]

than kyou, that makes more sense

[echo lintel]

https://gyazo.com/eabb027cbbbabe496f845fdd28f5f7db

is it answer 1

[glossy adder]

ye

[echo lintel]

could you explain why?

the do not begin is throwing me off

[stray reef]

count the strings that do begin with 000

and then subtract that from the total number of 8-bit strings w/o restrictions

[echo lintel]

Oh

ok makes sense ty

https://gyazo.com/7bfc3323095914f25d470c0d9b3cb7de

ok so this one is 2^8 obv because the others dont make sense

but idk why it would be 2^8

WAIIT

nvm it's 2^8 - 2

2 because 10101010 and 01010101

[shell jewel]

not sure if this is the right channel...
is it correct to say, given some x and y. (x * 3 == y*2) implies that x is in the form 2n and y is in the form 3n, for some natural number n

or this is not necessarily the case?

<@&286206848099549185>

[azure lichen]

only if x and y are intended to be naturals

[shell jewel]

yes they are

[azure lichen]

in general, n could be any number and you’d get the same relation

[shell jewel]

aha

alright, thx alot 😄

[slow socket]

i need to find the complete sum of products for this
xy(x'y' + y)

i got
xy

idk if is right

[slow socket]

nvm, i got it

[versed hemlock]

Hey guys

I need direction on how to solve a recurrence

Basically I want to convert the recurrence to closed form

f(0)=0

f (1) = 1×1 + f(0)

f (2)= 2×2 + f(1)

[hexed rune]

f(n)=n^2 +f(n-1)?

Do you know how to use generating functions?

[versed hemlock]

Correct

No I dont

[hexed rune]

Ok so this is actually pretty easy

[versed hemlock]

I want help understanding rather than an answer

I really suck at stuff like this

Basically it's from a problem on SPOJ

[hexed rune]

What do you think f(3) is?

[versed hemlock]

14

[hexed rune]

I mean

In terms of squares

f(2)=1^2+2^2

[versed hemlock]

Oh right

[hexed rune]

And f(3)=3^2+f(2)

[versed hemlock]

Right I get that part

I came up with a recursive O (N) algorithm to solve this

[hexed rune]

Okay, now do you know the formula for sum of squares

[versed hemlock]

But it can be done in O (1)

With closed form

[hexed rune]

So do you know that formula?

Or is that what you're asking about?

[versed hemlock]

No, the closed form is what I'm having trouble deriving

Yea that's what I'm asking about

Basically I'm not sure how to go about solving the recurrence

[hexed rune]

Okay so the online way I know how to derive it is in terms of generating functions

But I'll show you how that works

[versed hemlock]

#include <bits/stdc++.h>

typedef long long llint;

using namespace std;

llint numSquares(llint n){
    if(n <= 1) return n;
    return (n * n) + numSquares(n - 1);
}

int main(){
    llint n = 0;
    while(cin>>n){
        llint result = numSquares(n);
        if(n > 0) cout << result << endl;
    }
    return 0;
}

[hexed rune]

Basically consider some infinite polynomial whose nth coefficient is f(n)

[versed hemlock]

this is using the recurrence

thank you

[hexed rune]

So f(0)+ f(1)x + f(2)x^2+ ...

[versed hemlock]

i've never done generating functions

[hexed rune]

It's not very hard

And it's pretty cool

[versed hemlock]

hmm what is the x^2 part

[hexed rune]

We're basically using the polynomial for bookkeeping

Alright so we have f(n)=n^2+f(n-1) implies f(n)x^n = n^2 x^n + f(n-1) x^n

[versed hemlock]

hmm

so you added x^n right?

[hexed rune]

This gives us $\sum_{n=1}^\infty f(n)x^n = \sum_{n=1}^\infty n^2x^n + \sum_{n=1}^\infty f(n-1)x^n$

[versed hemlock]

right ok

i see how that matches what you wrote above

[hexed rune]

Now we pull out an x from the last sum

This gives us $\sum_{n=0}^\infty f(n)x^n = \sum_{n=0}^\infty n^2x^n + x\sum_{n=0}^\infty f(n)x^n$

[vital dew]

Liquid:

[versed hemlock]

a little confused on where the + x came from

i see the -1 went away

[hexed rune]

Notice that f(0)=0

I should have indexed from 1 actually

Hold on

[versed hemlock]

ok

yea f(0) is like our base case

[vital dew]

Liquid:

[hexed rune]

This was the first one

[versed hemlock]

right

[hexed rune]

Then we reindex the sum for the last term

This gives us $\sum_{n=1}^\infty f(n)x^n = \sum_{n=1}^\infty n^2x^n + x\sum_{n=0}^\infty f(n)x^n$

[vital dew]

Liquid:

[versed hemlock]

could you please clarify what you mean by re-index?

[hexed rune]

Like instead of starting from 1

We start at 0

[versed hemlock]

OH

[hexed rune]

And move up n by 1

[versed hemlock]

O i see

I see now in the sum

sorry i didnt notice

[hexed rune]

That's why we pulled out the x

[versed hemlock]

because for f(0) we dont need f(-1) right?

its the base case

[hexed rune]

f(-1) isn't actually defined

So we have to start at 1

In order to have reindexing make sense

[versed hemlock]

but now in the last sum we start at 0

[hexed rune]

But that's fine

Because f(0)=0

So we can just get rid of the 0 term

[versed hemlock]

ok im curious to see where you're going with this

so what is the next step