discrete-math

[ivory badge]

is Q the same as q?

in the hallucinating thing?

[spring helm]

Oh yes, it is

[ivory badge]

is Q the same as q on the paper?

Also, as for you dreams thing, if you assume that each of your 3 premises are true, then "I am hallucinating" must be true, right?

[spring helm]

But it makes no mention of elephants running down the road

So it could be either

Right?

[ivory badge]

well, if you assume the premise of Q -> R is true, then you don't need there to be elephants, right?

Wrong wording, rather
You know that $P \lor Q$ and you have that $\neg Q$ is true, right?

[vital dew]

Darkrifts:

[ivory badge]

So you have that P must be true, yes?

[spring helm]

Oh your right! I didn't even think of that

[ivory badge]

Yeah

I'm assuming your "premise" is an assumed statement, ofc

[spring helm]

So I do not see elephants running down the road must also be true

[ivory badge]

Not necessarily

[spring helm]

Because of the (neg)q

Wait that relates to the bad dreams

My bad

So it could be true also

[ivory badge]

You have $\neg Q$ and $Q \to R$
because $(Q\to R) \iff (\neg Q \lor R)$ if i remember correctly, the right hand side must be true by assumption

[vital dew]

Darkrifts:

[ivory badge]

which provides no information on R

[spring helm]

Gotcha

[ivory badge]

yeah, this all stems from me assuming "premise" is an assumed true statement, so make of that what you will

[spring helm]

And does the proof look good?

[ivory badge]

i see a q and a Q so if they're the same thing I'd recommend being consistent with notation

[spring helm]

gotcha

[ivory badge]

But yeah as long as Q is equivalent to q you're good

maybe work on some neatness and a bit of it feels meh to me, but seems ok

[spring helm]

Looking a the dreams thing again

(neg)q is stating I am not having bad dreams

so would that instead prove "I am hallucinating" to be true?

[ivory badge]

You have P or Q

so that means at least one is true

and knowing that Q is not true tells you that P must be

[spring helm]

Understood

[weary tiger]

proof in real meffmememticics for you, @ivory badge

[ivory badge]

Still can only barely read anything in agda

[weary tiger]

That's Coq.

[ivory badge]

Further proof I can't read it

What's the star in your name for @weary tiger

[weary tiger]

Represents the "type of all types"

[ivory badge]

ah

[ruby hearth]

Hello people 😄 could anyone explain to me why this is the outcome of this problem?

[stray reef]

incl-excl

[ruby hearth]

?

[stray reef]

inclusion-exclusion formula

[ruby hearth]

which is?

nm found it, thanks!

the thing is that i tried for so long to do this logically and i couldnt find why he subtracts one while adding the other

[ruby hearth]

nm kinda found it

[tacit garden]

Are we advised to practice discretion while we participate in this field of math?

[dapper rose]

[spice sandal]

How do I keep my brain from exploding whilst trying to learn this subject?

[ivory badge]

by reading through any text you're handed twice

[spice sandal]

Good plan

[spice sandal]

https://www.people.vcu.edu/~rhammack/BookOfProof/index.html

This one helps

The author made it free which is 👍++

[ruby hearth]

Hello! could anyone help me solve this problem?
G simple planar graph with at least 4 vertices. We need to prove that G has at least 3 vertices of degree lower than 6

[ruby hearth]

if anyone has an answer, please ping me

[faint narwhal]

What have you tried?

@ruby hearth

[ruby hearth]

i tried some stuff with euler but to no avail

im just starting in graph theory so im no expert

[faint narwhal]

Think about using Kuratowski's theorem

[ruby hearth]

will look it up

w8, isnt that just for proving that a graph isnt planar?

[faint narwhal]

you can think of it that way yes

[ruby hearth]

i am really not sure how that would help, i havent seen any similar problems solved so i dont know how you are supposed to go about it, if you have any material (like solved problems on graphs) that would be greatly appreciated (or even the solution or the way to go about solving this one).

the thing is i have to go now so i cant really chat about it rn .-.

[faint narwhal]

Think about it. If you know your graph is planar, combined with Kuratowski's theorem, it tells you something about your graph

[ruby hearth]

that it doesnt contain a subgraph that is a subdivision of k5 or k3,3?

[faint narwhal]

Right

[ruby hearth]

so?...

[weary tiger]

Here is the book I used

@spice sandal this is the book I used

[spice sandal]

Thank you very much @weary tiger

[weary tiger]

No problem

[opal obsidian]

someone help pls

[stray reef]

lol wtf is this

is this a meme

[craggy gale]

lmao I thought it was upside down for a moment

now that I've had a closer look at it, it looks like physics

[stray reef]

this is also their first and only message

[craggy gale]

very mysterious

[glossy adder]

[ruby hearth]

could anyone maybe take a look at the problem i posted above? :p

[ruby hearth]

nm i found the solution, but it didnt have anything to do with kuratowski's theorem though

[torpid void]

can someone walk me through the process of doing this:
express {xy: where x ∈ {0} ∪ {0}^2 and y ∈ {1} ∪ {1}^2} using the roster method

[weary tiger]

@opal obsidian is that tensors lol?

[opal obsidian]

Yeah 😂😂

[naive saffron]

Oh god that looks scary af

[spice sandal]

looks like art

Like Marco Fusinato

Mass Black Implosion

[spice sandal]

Is there any way to prove by strong induction by hand?

Or would you just need a computer program to verify it

[glossy adder]

huh

[dapper rose]

what

[ivory badge]

what

[glossy adder]

I've never heard of a computer program doing that

I mean they must exist

[ivory badge]

You can defo prove things using strong induction by hand

how tf did they prove shit back then

[spice sandal]

they shouted really loudly

[glossy adder]

I've never used a computer program while using strong induction

[dapper rose]

I've heard of programs that can process math concepts in general

[glossy adder]

[spice sandal]

so how does one prove by strong induction if there's no way to test every possible variable n?

[glossy adder]

just test the first n

that's the whole point of induction

[ivory badge]

^

[spice sandal]

strong induction

isn't that different?

[ivory badge]

I forget strong induction, but does that say that 1 being true implies that for some a, n < a is true?

[spice sandal]

Strong Induction. Instead of assuming S(k) to prove S(k + 1), we assume all of S(1), S(2), … S(k) to prove S(k + 1). Everything that can be proved using (weak) induction can clearly also be proved using strong induction, but not vice versa.

[glossy adder]

you might need like 2 base cases in some weird instances but generally 1 is enough

[dapper rose]

like we are just more complicated versions of computer programs :))))

[ivory badge]

What you have to do is show that s(1) implies s(2)

[spice sandal]

no

[ivory badge]

and then that s(1) and s(2) implies s(3)

etc

[spice sandal]

computer programs are less complicated versions of us

it's not symmetrical

[ivory badge]

show that if everything behind it is true, then k+1 is

[spice sandal]

Would that be enough, @ivory badge ?

[dapper rose]

whenever I use induction, I just call it induction no matter how many base cases I use and no matter how many things I use in the inductive step

[stray reef]

regular induction:
show that you can climb the first rung, then show you can climb from one rung to the next

[ivory badge]

That's literally the point

Show that everything else being true implies k+1

[stray reef]

strong induction:
show that you can climb the first rung, then show that if you've climbed all the way up to some rung then you can climb the next

[spice sandal]

huh

thanks @stray reef

[stray reef]

strong induction does not per se require the presence of a computer

[spice sandal]

This course needs more simple analogies

[stray reef]

and every inductive proof can also be framed as a strong-inductive proof which just happens not to use any of the hypotheses but one

[glossy adder]

strong induction is like a shonen anime where the villain of the current week joins the protagonist for every following week

[dapper rose]

[stray reef]

[glossy adder]

[ivory badge]

tbh that's not a bad analogy

[spice sandal]

[dapper rose]

I see, and with the power of k villians we can beat the k+1th villian

[glossy adder]

weak induction is like a seinen anime where the villain of the current week is killed

only after helping with the death of the next villain

[ivory badge]

oof

sacrificial death

[spice sandal]

@stray reef do you have a simple(ish) way of explaining how to write proofs?

It's been tripping me up for months

I feel like they pull out numbers from thin air

[stray reef]

what, like proofs in general?

[dapper rose]

so to overcome the k+1th villian we require the kth villain, but the kth villain dies in the process

[spice sandal]

😬

[stray reef]

or what

[spice sandal]

Inductive proof

[stray reef]

reading a proof, it can sometimes feel like some numbers are pulled out of thin air

but really it's only because no scratch work is shown

can you show a proof of the kind that's been tripping you up though

bc i feel like there isn't much i can say in the general case

[spice sandal]

yeah hang on

[stray reef]

and i'd rather have an example i could point at

[glossy adder]

pulled out of thin air

[stray reef]

ha nice

[stray reef]

uh

[spice sandal]

These two have just been annoying

[stray reef]

well those aren't proofs

[spice sandal]

they need to be proven

by induction

[stray reef]

ok

[dapper rose]

it is obvious to see that...

[stray reef]

i was expecting you to provide a proof you were having trouble grasping

[spice sandal]

ah

[dapper rose]

the proof is trivial and left as an exercise to the reader

[spice sandal]

:V

[glossy adder]

I was about to say "use induction" but I realised that probably wouldn't be very helpful

[stray reef]

#12 is basically just messing around algebraically

[spice sandal]

I'll give it another shot I guess

It's difficult to ask questions to something that I can barely wrap my head around

Because I don't even know where to begin

[stray reef]

well

proofs by induction always follow the same pattern

• prove the base case
• write out the inductive hypothesis (i.e. the statement for n=k)
• write out what you need to prove (i.e. the statement for n=k+1)
• prove it

[spice sandal]

uhm

Is this right?

[craggy gale]

it's 2 indeed

[spice sandal]

the one element, and the empty set?

[craggy gale]

yes

[spice sandal]

ah

frustrating but understandable

I suppose it is 2^n

so if there's one element, the answer should be 2

[craggy gale]

In general, yes

[spice sandal]

I am doing myself a big learn

Thanks @craggy gale

[craggy gale]

You're welcome

[torpid void]

anyone got any tips for memorizing identities

[stray reef]

tip #1: don't

what identities do you mean though

[torpid void]

most of the ones ill use in proofs, like absorption and de morgan's law

My class has been pretty heavy on set theory

[slate marlin]

hi guys

i need a bit of help with an induction proof

lemma: (m + n)! > m^n

[stray reef]

@torpid void generally, 1. understand where each identity comes from, and 2. do exercises that make you use 'em, a lot

[slate marlin]

prove (2k^2)! > k^(2k^2)

hints will do

especially if its actually doable and not an error in the book

i got up to (2(k+1)^2)! = ((k+1) + (2k^2 + 3k + 1))! > (k+1)^(2k^2 + 3k + 1) from the lemma

but that doesnt prove the k+1 case

[analog sonnet]

it follows directly from the lemma where m = n = k^2

@slate marlin

k^(2k^2) = (k^2)^(k^2)

[slate marlin]

lol

[stray reef]

[slate marlin]

thank you

[analog sonnet]

np 🍮

[weary tiger]

🍮

[candid mountain]

Hey a question about binary relations

If I want to refute that relation R is symmetry

I have to find x,y,z that to A which xRy and yRz but then show that x!Rz?

It means (x,z) doesn't belong to R

[craggy gale]

that would be to refute transitivity

[stray reef]

^

[candid mountain]

yeah sorry I meant transitivity

[stray reef]

to refute that R is symmetric, you'd need to find points x, y such that x R y but not y R x

[candid mountain]

I meant transitivity

and about symmetric-I read there is weak symmetric and strong symmetric. If I want to prove weak symmetric, I have to show for general x,y ∈A that if x R y and y R x then x=y?

[craggy gale]

I think that's antisymmetry
I've never heard of weak/strong symmetry

[candid mountain]

and what about the refunding transitivity

[tired temple]

hello guys can u explain how do i turn this result

to this

i = log2n

thanks in advance

[cobalt trench]

I love descreet maths

Wussup guys

So u guys discuss graph theories and stuff

?

[spice sandal]

Just finished my Discreet Structures exam

Pretty sure I passed

So thanks to you all who helped me out with my relentless, frantic questioning

<3

[ivory badge]

nice

[weary tiger]

I do a lot of Proof and Logic in my Discrete Math class, which channel is right for me here?

[ivory badge]

pick one, ideally the one you think is more applicable

[twilit wadi]

a)The statement P->Q has a truth value Tall possible truth values of P and Q.
b)The  statement P->Q  has  a  truth  value  F  when  Q  has  truth  value  F and  P  has  the  truth value F; otherwise it has truth value F.
c)The statement P->Q has a truth value F for all possible truth values of P and Q
d)The  statement P->Q  has  a  truth  value  F  when  Q  has  truth  value  F  and  P  has  the  truth value T; otherwise it has truth value T.```

[weary tiger]

what is the question

you just want the answer?

[twilit wadi]

answer

[weary tiger]

d

write down the table of values and it should be obvious

F F T, F T F, T T T, T F T

[twilit wadi]

ok

The disjunctive normal form of P/|(Q->R

[stray reef]

that doesn't look syntactically valid

did you mean $P \land (Q \to R)$

[vital dew]

Ann:

[twilit wadi]

yes

[stray reef]

$P \land (\neg Q \lor R) = (P \land \neg Q) \lor (P \land R)$

[vital dew]

Ann:

[stray reef]

this should be its DNF

[twilit wadi]

thanks

[weary tiger]

what exactly is the difference between images and co-domains in relational functions

ok got it

ok in this piece of text, there is an explanation for inverse functions there is the statement

the function f is a function there g must be injective

I have no idea what this means.

[ripe ferry]

if f wasnt injective then g wouldnt be a function

since the first number in the ordered pair can only show up once

[weary tiger]

yup it just popped in my head

how about the third statement

why must the image of g be X?

[ripe ferry]

same reason pretty much

remember, image =/= codomain

[weary tiger]

yeah but it doesn't really help, like it makes sense on a diagram

but these phrases seem useless to me

like I get that it defines a function but what's the point of including that 3rd statement

it's a given

[ripe ferry]

its given in this situation, but you need it in other situations

[novel spire]

Quick question about graphs

If a vertex has a loop, is it considered adjacent to itself?

[pale epoch]

generally, yes

[ripe ferry]

non simple graphs
🤢

[spring helm]

Can someone help me form this into an equation? "n^2-n is even for all integers n >= 1"

the LHS is "n^2-n" which is given

but im not sure how to structure the RHS

[ivory badge]

you can't really structure it like an equation nicely

you can do $n^2 - n = 2k$

[vital dew]

Darkrifts:

[ivory badge]

but I don't think that's the most useful for you

[spring helm]

thats what i was thinking, I have to prove it by induction though so I was trying to have it in terms of only n

[ivory badge]

In fact, you're better off with taking $n$ is even $\iff n \in (2)$ and using fundamental theorem of arithmetic and how $a, b \nin (2), a+b \in (2)$

[vital dew]

Darkrifts:

[ivory badge]

but that's cheating I guess if you want induction

Show it's even for 1, then manipulate $(n+1)^2 - n - 1$ to show that it's still even

[vital dew]

Darkrifts:

[ivory badge]

you don't really need a rhs

[spring helm]

gotcha so make it fit the equation for an even number

[ivory badge]

You could have a rhs of 2k

but since you wholly manipulate the n^2-n expression it's a moot point

btw it's like ultra super trivial, esp with (2)

[spring helm]

so that LHS reduces down to k^2+k

[ivory badge]

it should not reduce down to what it was originally i'm p sure

but uh, with the + probably

which of course you still have to show that that is even

[spring helm]

so that can be k(k+1)

and im trying to get that into k^2-k so i can say it =2(any integer)

[ivory badge]

$n^2 - n = 2k \ (n+1)^2 - (n+1) = 2m$

[vital dew]

Darkrifts:

[ivory badge]

so expanding it out might be a start

[spring helm]

so that turns into $n^2+2n+1-n-1$

[vital dew]

Garfoofsner:

[ivory badge]

simplify

[spring helm]

which further simplifies to $n^2+n$

[vital dew]

Garfoofsner:

[spring helm]

which then goes to $n(n+1)$

[vital dew]

Garfoofsner:

[ivory badge]

so, at leas one must be even, no?

[spring helm]

Yeah, is it legal to just say that?

[ivory badge]

Technically that's not a proof by induction if you do that

the proof by induction would be to say that n^2 + n = n^2 - n + 2n, which is a sum of even numbers

the n(n+1) is a proof by some number stuff and how $\forall a, b( a\nin (2) \land b \nin (2) \implies a+b \in (2))$

[vital dew]

Darkrifts:

[ivory badge]

(2 odds make an even)

so you could argue that it's even if n is even, or if n is odd then n+1 is even and you are done

But that's not quite inductive so they probably would squint at it

[spring helm]

I understand now, I just didnt even think of changing n^2+n to n^2-n+2n

as then i can substitue my 2m into n^2-n

which gives me 2m +2k which will always be even

[ivory badge]

or just inductive hypothesis that n^2-n is even

[spring helm]

thats forgetting the +2n though?

[ivory badge]

Alternatively, you can make a trivial non-inductive proof:

$(n \in (2) \iff n^2 \in (2)) \land \forall a,b(a\nin (2) \land b\nin (2) \implies a+b \in (2))$ therefore $n^2 - n \in (2)$

[vital dew]

Darkrifts:

[ivory badge]

formatted horribly but you should probably get it

[twilit wadi]

can anyone tell what is left identity and right identity

on * binary operation

[stray reef]

an element e is said to be a left identity for * if e*x = x for all x

and a right identity if x*e = x for all x

for example, 1 is a right identity for exponentiation

[twilit wadi]

thanks

[zenith sundial]

How would you guys prove an empty set is a subset of every other sets?

[stray reef]

by using the definition

and the principle of explosion

[zenith sundial]

@stray reef how do I do this? Can you help out with the solutions please?

[stray reef]

i literally just said everything that you need

can you state the definition of $A \subseteq B$, where $A$ and $B$ are sets?

[vital dew]

Ann:

[stray reef]

if you cannot, then there is nothing else i can do for you besides telling you to go back to your notes

[zenith sundial]

Yes..

What I can think of re the proof is to use the definition of power set.

I don't know how much that would be correct though.

@stray reef my course lecturer is a real pain in the arse. He literally want ua to fail. He wouldn't tell us what exactly he wants.

[stray reef]

definition of power set???

[zenith sundial]

Yes

[stray reef]

why would you need that

[zenith sundial]

Cause the power set of any set has empty set as a member/subset.

[stray reef]

that's equivalent to the thing you were asked to prove.

and that gets you exactly nowhere.

you're massively overthinking this

[zenith sundial]

Please let me know whT exactly to write when exam comes...

What*

[cerulean crypt]

How do you usually prove {1;2} is a subset of {1;2;3}?

[weary tiger]

from the definition

[pliant kiln]

hey guys, quick question: we're currently doing graph theory and one of the question was "how many ways are there to make a specific path" (may be incorrect, i'm not a native english speaker but I hope the terms are right). Anyways we have a graph with 4 vertices, which then produces a 4x4 adjacency matrix. The length of one path should be 8 (meaning it goes through 8 vertices). I raised the matrix to the power of 8, but where/how do I get an actual number of possible paths? Do I multiply all of the numbers with each other or what? Thanks for any help

[faint narwhal]

Well what does each number in the matrix represent?

[pliant kiln]

the basic adjecency matrix gives the number of connections between vertex a and b

afaik

...so the matrix A^8 means there are 8 ways between two vertexes?

means I sum up all of the numbers?

[faint narwhal]

Yep

[pliant kiln]

lul, simple enough haha

thank you

by the way, can you use the matrix also to check whether or not the graph is planar and if it has an euler path or circle?

[faint narwhal]

You can't use it to check it it's planar all the time

Look up kuratowskis theorem

You can use it to check if it has an Euler path or cycle though

[pliant kiln]

how to do that?

[pliant kiln]

well you can just sum up all of the edges listed in the matrxi for each vertex and if it's divisable by 2 its an euler graph

i really need to start thinking on my own instead of asking dumb questions.... sorry

[analog dagger]

dumb questions are good

[sick lagoon]

hey so i am doing a project on interval graphs and i am thinking whether all directed graphs are actually interval digraphs

does anyone have a counter example

[obtuse minnow]

Er what are you defining as the source for each directed edge in the interval digraph? Without direction, you can define an undirected edge as sharing, but how does that translate to directed graphs?

[sick lagoon]

you have a source interval and a destination interval for each vertex

say (S,T)

and (u,v) is an edge iff Su n Tv =/= empty

In my case U is the real line

[obtuse minnow]

uh, but in the directed case, doesn't that always mean both directions must occur for any two intervals where at least one direction occurs?

[sick lagoon]

no (u,v) is the directed edge u -> v

sorry should have clarified

Sv n Tu can be empty even if Su n Tv is not

for each vertex you have two intervals Sv and Tv

[faint narwhal]

Hint: think about how many odd integers there must be

Yeah that works too

[stray reef]

there's an even simpler argument

if it was possible to split the list into two sub-lists of equal sums, then the sum of the whole thing would be twice the sum of one sub-list and hence even

but it's not

[candid mountain]

Hey

I have a question predicate logic. This is the right place?

[stray reef]

sure, it fits here

[candid mountain]

I have this thing

I know I was supposed to show it’s wrong (always false) but someone how I managed to show it’s always true

[thorny willow]

How does one begin with proofs on graphs?

For example, I have this problem
Let G be an (n,m)-graph. Show that δ(G) <= 2m/n <= Δ(G)

I know what's it saying but idk how to even begin

[faint narwhal]

show each of the inequalities separately

[thorny willow]

By induction?

[faint narwhal]

Try it

[thorny willow]

I'll try and hopefully don't get stuck

[faint narwhal]

Do you understand how to find all subsets of a given set?

you should figure that out first

It's not equivalent

And think about it, this is something you can figure out

[faint narwhal]

A hint is to do it recursively

[faint narwhal]

By choosing one of the sets of your partition, you've now reduced it down to the same problem of finding partitions

But just on a smaller set

[dapper rose]

I would choose a number, then consider all the subsets that contain that number.

then for each subset, consider the set take away that subset, then find all the partitions of the resulting sets

uh did you choose a number first

then all the subsets that contain 4 are (4),(43),(42),(41),(432),(431),(421),(4321)

because writing commas is hard

I'm only on the 2nd step of my method

then consider each subset separately

for (4)

you need to find all the partitions of (321)

for (43), you need to find all the partitions of (21)

etc

ig we say {{1},{2,3,4}} is a partition of {1,2,3,4}

here's a maybe better method than mine @icy fractal https://stackoverflow.com/questions/19368375/set-partitions-in-python

top answer

[normal pasture]

you write it with a pencil

[weary tiger]

😂

[normal pasture]

i mean, not to be a dick. but that's really it

you just write the things as you see them

there are five lines that are the obvious answer

[dapper rose]

write all the partitions of a {1,...,n-1}

[weary tiger]

actually

katesi's method was 200% a systematic method

[normal pasture]

iirc generating partitions is actually notoriously a pain

[dapper rose]

then add n systematically to each subset for each partition, or add {n} to each partition

[normal pasture]

you can draw a tree diagram if you like

[dapper rose]

say we have the partition {{1},{23}}

[normal pasture]

you can see by the five lines that there are 3 size 1, then three size 2 and 1, and, then one size three

so it went by size

1+1+1, 2+1, 3

[dapper rose]

then we can make {{14},{23}},{{1},{234}},{{1},{23},{4}}

[normal pasture]

the tree diagram would be horrible

[dapper rose]

you need to know all the partitions of {1,...,n-1}

partitions*

rip the run time, you would need to generate partitions of {1,2}, then use that to generate 3, then 4, etc

wait my other way you need to know the partitions of n-1 as well

for {4} we need to find the partitions of {3,2,1}

I think stackoverflow's (SO) way is better

well using SO's way

partitions of (1,2) are

(1)(2)

(12)

add 3

(13)(2)

(1)(23)

(1)(2)(3)

(123)

(12)(3)

add 4

(134)(2)

(13)(24)

(13)(2)(4)

etc

[prime steeple]

https://youtu.be/FVc-UOHcajc

Discussing and using public-key cryptography

[gentle nebula]

any group where discrete log is hard can be used for signing/key exchange just that finding such groups aren’t easy

[south marten]

@gentle nebula how would you go about finding such a group ?

[mighty plume]

im stupid bad at combinatorics / elementary counting problems how do i git gud

[faint narwhal]

Do problems

[mighty plume]

θωθ

[gentle nebula]

@south marten well you just wait for people to find such groups, currently its like multiplicative group over integers mod n and elliptic curve group

[weary tiger]

@lucid ingot

ok so this is an exam question

$ F(x) = \frac{5+4x^2}{1+3x-4x^3}.$

[vital dew]

yami:

[weary tiger]

find the series expansion via partial fractions

the PF part is easy

but afterwards?

[lucid ingot]

wot is the pf part?

[faint narwhal]

What is the partial fraction decomposition?

[weary tiger]

$ F(x) = \frac1{1-x} + \frac4{(1+2x)^2} $

[vital dew]

yami:

[faint narwhal]

Well do you know the series expansion of the first fraction?

[weary tiger]

thats just a bunch of 1s

[lucid ingot]

use negative binomial theorem

(bt but for neg powers)

[weary tiger]

i dont know how

[lucid ingot]

(1+x)^(-n) = 1 + nx + n(n-1)/2 x^2 + ....

[faint narwhal]

For the second one, can you find the series expansion of 2/(1 + 2x)?

[lucid ingot]

(where n is a non-neg integer)

[weary tiger]

no @faint narwhal, i dont know how and thats what i was asking about in here

[faint narwhal]

Can you find the series expansion of 1/(1 + 2x)?

[weary tiger]

i cant find the series expansion of anything because i dont know how it works

[lucid ingot]

uh

[faint narwhal]

You know the series expansion of 1/(1-x)

What if you just substitute -2x for x in that series expansion

[weary tiger]

literally no idea

well i mean i guess i could do the long division this guy is doing

[lucid ingot]

expand 1/(1-x)

then sub x = -2y

[weary tiger]

uh

$ 1 + (-2x)^2 + (-2x)^3 + (-2x)^4 + ... $

like this you mean?

[vital dew]

yami:

[lucid ingot]

ya

that's 1/(1+2x), right?

[weary tiger]

i suppose

[lucid ingot]

u missed (-2x) term

but meh

[weary tiger]

o yea

[lucid ingot]

wot do u get on differentiating 1/(1+2x)?

[weary tiger]

$ -\frac2{(2x+1)^2} $

[vital dew]

yami:

[lucid ingot]

ya

[weary tiger]

so now what

[lucid ingot]

u know expansion of 1/(1+2x)

cant u differentiate it

[weary tiger]

$ 0 - 2 - 4x - 6x^2 - 8x^3 - ... $

[vital dew]

yami:

[weary tiger]

like so you mean?

[lucid ingot]

why is it -4x?

[weary tiger]

the derivative of -2x^2 is -4x

[lucid ingot]

it is (-2x)^2 tho

[weary tiger]

that makes it still

$ 2 \cdot (-2x) ^ 1 $

[vital dew]

yami:

[weary tiger]

no?

[lucid ingot]

obv not XD

(-2x)^2 = 4x^2

[glossy adder]

hmmst

[weary tiger]

but thats not the differentiation

[lucid ingot]

ye

btw, the thingy u wrote is derivate of (-2x)^2 wrt -2x

[weary tiger]

i still dont know how to move on

you asked me to differentiate the series, i thought i did that

wait

xd

i should have just wrote out the terms

$ 0 - 2 + 4x - 6x^2 + 8x^3 - ... $

[vital dew]

yami:

[weary tiger]

this good now?

[lucid ingot]

uh

derivative of 4x^2 wrt x is 8x

uh

scratch all that

u know series expansion of 1/(1-x), right?

now its derivate (wrt x) is 1/(1-x)^2

wots derivative of its expansion?

[weary tiger]

the expansion is just a bunch of 1s, so the derivative should be all 0s

[lucid ingot]

:o

[weary tiger]

but itsnot

its all 1s as well

no?

[glossy adder]

this is so discrete

[weary tiger]

i have no fucking idea what im doing

[lucid ingot]

expand 1/(1-x)

1+x+x^2+......

now take its derivative

[faint narwhal]

What he's essentially trying to say is that if you have something like

1/(1-x) = 1 + x + x^2 + ....

It's legal to take the derivative of both sides

[weary tiger]

sure

[faint narwhal]

To get an equality like 1/(1-x)^2 = 1 + 2x + 3x^2 +...

And this is exactly what you can do to find 1/(1+2x)^2

Because you know the expansion of 1/(1+2x)

[lucid ingot]

in the above eqn u can directly sub

[weary tiger]

ok so

the series expansion of the derivative of 1/1-x is 1+2+3+4+... then

no?

[glossy adder]

remember the powers of x

[weary tiger]

[lucid ingot]

did u just make x shoo away?

[glossy adder]

what's the derivative of x² with respect to x

[weary tiger]

i made shoo'd the 1 in front i guess

2x

[lucid ingot]

"1/1-x is 1+2+3+4+... "

[weary tiger]

?

[lucid ingot]

1+2x+3x^2+4x^3+...*

[weary tiger]

im just gonna go

my mental is boom

ty for helping ig

[lucid ingot]

@weary tiger look up negative binomial series; cud be more 'helpful'

[weary tiger]

like i will understand that

lol

[lucid ingot]

just look it up once

[weary tiger]

ill just skip

get more time to study for the next one

[lucid ingot]

sounds gud

good luck for co then

[sterile bear]

So what does it mean for a tree to be nonisomorphic?

[pale epoch]

that makes no sense

an object can only be (non)isomorphic to another object

[sour arrow]

Two trees are isomorphic if there is a way to arrange one's points so the two trees look alike

Without cutting edges ofc

[pale epoch]

more formally, G=(V,E) and G'=(V',E') are isomorphic iff there is a bijection f: V -> V', such that {a,b} in E <=> {f(a), f(b)} in E'

[sterile bear]

this is from ETS ^^^

thanks

[haughty garden]

Perhaps, it'll help by thinking about ways to arrange a tree based on the "maximum number of adjacent nodes" one particular node may take.

On one end, we may have a tree with a vertex degree of 4.

On the other end, we may have a tree with a vertex degree of 2. (Why doesn't vertex degree of 1 make sense?)

[cerulean ore]

Guys, this semester we have discrete mathematics and I am scared.

What is the best way to score a full?

Which textbook to follow?

[haughty garden]

I’d say you would want to focus more on graph theory and proofs when it comes to discrete. They tend to be one of the more difficult topics in my opinion.

[cerulean ore]

Thank you!

I will surely focus on that part, I've heard that graph theory and trees are toughest.

[next valley]

Definitely focus on tree and proof

Are you doing comp sci?

[cerulean ore]

Yes, doing computer science.

I am finding a great source to start with, I have 15 days left before the classes start.

[next valley]

Discrete Mathematics - Richard Johnsonbaugh - 8th ed.pdf

@cerulean ore Maybe this will help?

[cerulean ore]

@next valley Thank you man! Let me start with this!

[next valley]

👍

[ivory badge]

Discrete is really not all that bad, gotta say

[haughty garden]

Discrete was really interesting when I took it, and although I would like to have done better, it was one of my favourite first year courses I took

[thin heron]

I'm trying to do a "n choose k" problem, where each selection of k can not contain any two elements that have been selected together before - and I'm looking for the optimal solution where each element is a member of as many selections as possible (e.g. "Given 30 students, how many groups of 3 can you make such that no person is grouped with a person they have been grouped with before"), I have some code (https://pastebin.com/i1zSyKHU) which is not optimal (e.g. for 9 choose 3, numbers 8 and 9 can only be part of 1 group, but there exists a solution where each number can be a part of 3 groups), where should I look to find out more about this problem?

[thin heron]

so, this seems closely related to steiner triples, but I'm having an issue verifying my heuristic - a S(2,3,7) should (if I understand wikipedia correctly) have 7 triples, but I'm having trouble constructing more than 5

[cerulean ore]

According to book's definition "If X is a subset of Y and X does not equal Y, we say that X is a proper subset of Y and write X ⊂ Y."

How {a,b,c} is *a proper subset of A?

We can clearly see that A= {a,b,c} and {a,b,c} = A

Hence, {a,b,c} is a subset of A not a proper subset

[stray reef]

it says ALL BUT {a,b,c} are proper subsets of A

every one of those things is a proper subset of A, except {a,b,c}.

[cerulean ore]

Aah, thank you!

I was thinking that but, English being not my native I ignored the intuition.

[sterile bear]

@haughty garden wouldnt it be the case that if a vertex is only connected to 1 other vertex then its degree is 1? I dont understand

[shell nexus]

Barry19102004

[haughty garden]

@sterile bear yes, but we're considering a tree with 5 vertices. A maximum degree of 1 doesn't form a tree of 5 vertices

[cerulean ore]

@next valley Hey! Thank you for the book. Do you also have solutions manual for it?

I am currently solving 1.1 exercise.

[candid mountain]

Hey

If A={Ø}

Then P(A)={Ø, {Ø}}?

[glossy adder]

yes

[candid mountain]

So A Intersection P(A)={Ø} which is NOT = Ø

?

[glossy adder]

yes

[candid mountain]

Like this right?

[sterile bear]

isnt they're intersection just Ø? @glossy adder

[glossy adder]

Ø is in A and in P(A)

so their intersection is {Ø}

[sterile bear]

ah so the intersection has to be a set with those elements itself, right ok nvm

trying to study for math gre and getting stuff mixed up in my head

[haughty garden]

A set containing the null element isn’t the same as a set of a set containing the null element

[sterile bear]

^^^

[torpid void]

I just had a hmmm moment, I don't particularly understand the way my teacher explained something and would like an alternative explanation
for subsets the n choose r is equal to (the n choose r for r-permutations)/(r!)
so basically 10 choose 3 has (10!)/(7!) permutations and (10!)/(7! * 3!) subsets
Im not sure why this math works, I understand that since order doesnt matter with subsets the combinations are less, but I dont understand why the math works

[dapper rose]

from n distinct objects, there is n ways to select the 1st object, n-1 ways to select the 2nd, .... n-r+1 ways to select the rth object. So nPr=n!/(n-r)!.

For nCr, notice in nPr we counted all permutations of a set of r objects as different, to count them the as same we divide nPr by the number of these permutations, so nCr=nPr/r!

@torpid void

[torpid void]

oh so like for a set of 3 theres 3 permutations of 3, 2 of 2, and 1 of 1, so you divide by 3! in the case of C(10, 3)

[dapper rose]

3P3=3!

I wouldn't say 3 permutations of 3 etc...

the number of permutations of a set r is rPr=r!

[nova star]

how to draw graphs fast?

[modest zealot]

who said nobody would respond

LOL

[nova star]

from adjacent tables

lol sup m8

[modest zealot]

im going to assume its an undirected graph? because i have no clue which is going to which

[stray reef]

starting with highest-degree vertices first is generally a good idea

[modest zealot]

https://cdn.discordapp.com/attachments/269573202018041856/597010098996379654/unknown.png

this was his pic

[stray reef]

weighted?

[modest zealot]

shud be

[nova star]

broo i dont think

discreete is for me

cuz i suck

[modest zealot]

shut up

[nova star]

at drawing

[modest zealot]

lets continue

[nova star]

u look at my graph

[modest zealot]

so (A,A)

[nova star]

u cant tell if its two or three edges

lol

[modest zealot]

implies it goes to itself

[nova star]

yea i made it

i think easiest way

is to just make 4 points

[modest zealot]

yes make 4 points first

[nova star]

then go through table one by one

[modest zealot]

label them A B C D

[nova star]

yea

[modest zealot]

and one thing to note

[nova star]

but i messed up one line, and then i redrew it, and it looks shit

lol

[modest zealot]

this graph should DEFINITELY be undirected, because this table possesses transitive property? i thinkit was called transitivity

notice how A,B has 2, and B,A has 2

that means two goes from A to B, and two goes from B to A

[nova star]

yea its undirected

[modest zealot]

its a mirror image across the diagonal

[nova star]

yea

[pale epoch]

it's called symmetric

if the adjacency matrix is symmetric, the graph is undirected

(usually)

[modest zealot]

ah symmetric

[nova star]

thafaq??

[modest zealot]

its starting to come back

hahahaha

[pale epoch]

it has nothing to do with transitivity

[modest zealot]

for some reason my brain told me transitivity lmao

but yes, Loch is right

[nova star]

symetric along diagnol i assume

[pale epoch]

symmetric of a matrix A just means A^t = A

[nova star]

yea

[pale epoch]

but yeah, you can interpret it as mirror symmetry along the main diagonal

[nova star]

btw

i still dont get

how that is this :

shudnt b have 2 loops to itself?

[next valley]

No

[nova star]

thafaq? why

ahhh

i figureed it out

ok

ok so i think im figuring it out

basically u look at all the numbers after the diagnol and ignore the rest in a undirected graph

so if it just says to draw graphs using adjavent tables, i dont have to care about hamilton n shit right?

[next valley]

Yeah

[nova star]

fuck, one of the graphs was directed on one segment

its like they make these problems to make u feel stupid

so two get degrees from table i guess i just go along the row and add everything?

ohhh nonono, wut if it connects to itself

why does c have a degree of 2?

[pale epoch]

it doesn't?

[stray reef]

c looks like it has a degree of 3

not 2

where did you get it from that it has degree 2

[pale epoch]

also if a vertex connects to itself

[pale epoch]

you usually count it twice towards the degree

[nova star]

yea so now im making sure at first that none of the diagnols have 1, if they do then i make mental not of it

note*

yea but c has degree of two according to textbook answers

[pale epoch]

then the textbook answers are wrong

[nova star]

hmmmm

[pale epoch]

the number of verteces with odd degree is even

so this cannot be right

[nova star]

they r never wrong, uptill now

and i have done 1000s of sums

but if u say so, they probably are

so i got 23322

? is that correct?

[pale epoch]

yea

[nova star]

so maybe just the C was wrong lol

[pale epoch]

yes

[nova star]

people who write textbooks get it wrong, wut hope do i have..

[pale epoch]

just that

[nova star]

so if its a digraph

and u going from c to d

do both c and d have degree 1?

or just c?

[pale epoch]

depends how you define degree

[nova star]

lol

[pale epoch]

usually its not defined for digraphs

[nova star]

how its usually defined

[pale epoch]

there is an indegree and an outdegree

usually degree is not defined at all for digraphs

[nova star]

so i guesss pretty much same as normal graphs

[pale epoch]

if you defined it that way, then yes

[nova star]

unless they specificly ask for out and indegrees

[pale epoch]

but thats harder to determine from a matrix

specifically the indegree

[nova star]

lol they got tierd

and didnt even include answers for 3

just tell me for fitst one

is it 35454?

[next valley]

The deg of E is not 4

[pale epoch]

the degree of C is also not 4

[next valley]

The degree of B is not 5

[nova star]

fuck..

why?

how?

[pale epoch]

B is correct though

[nova star]

fuckk.. i suck

yea B is 5

right?

[pale epoch]

again with the convention that loops are counted twice

[nova star]

e isnt 4?

[pale epoch]

which i dont know if your textbook is doing

[nova star]

c isnt 4?

how?

yea loops count as 2

[pale epoch]

C has a loop

[nova star]

so 1+1+2

[pale epoch]

E does not

[nova star]

yea

c = 1+1+2

[pale epoch]

C is adjacent to A, D, E and C

[nova star]

e = 1+1+2

but c is looped and connected to a and d?

[pale epoch]

wait a second

this is a digraph

[nova star]

it is?

[pale epoch]

i just noticed

[nova star]

it is yea

[pale epoch]

so disregard wtv i said

[nova star]

and the fuckin textbook doesnt even hve a answer lol

[pale epoch]

your answer is probably still wrong

the degrees will be higher

[nova star]

yea

so wut the degree??

i guess i calculated out degree

and not degree

[pale epoch]

not if you counted loops twice

[nova star]

i did count loops twice

so i guess c is degree 5

[pale epoch]

loops contribute 1 to outdegree and 1 to indegree

[nova star]

yea

ok

so i got c wrong

it shud be 5?

[pale epoch]

why 5

[nova star]

cuz its connected to E

for degree

degree out + in degree

[pale epoch]

C has outdegree 3 and indegree 4

[nova star]

fuck imma ask my teachers once

fuckin hell....

so id have to do that for all?
indegrees + outdegrees? @pale epoch

The number of edges coming out of a vertexis calledthe degree
of that vertex. For example, in Graph 2:
deg(A)

5, deg(B) = 2, deg(C) = 1.
Notethat when calculating the degree, we count the edge
joiningA to A twice, as each edge has to have two ends.
However, in the adjacency table thenumberin the (A, A) cell
is 1,becausethereis only one edge joining A to itself. The list
of degreesofalltheverticesofthe graph is called its degree
sequence. It is usuallygivenin descendingorder;for example,
Graph 2 has degree sequence 5,2, 1.

from our textboox^^

idk how accurate this is though tbh

[pale epoch]

what do you mean 'how accurate'?

i'm not sure what "edge coming out of a vertex" is supposed to mean

especially in regard to digraphs

[nova star]

i mean idk if thats how the actual exam goes

the info may be wrong

imma ask my teacher later i guess

[nova star]

connectd graph means all vertices are connected or wut? @pale epoch

[pale epoch]

it means that there is a path between any two vertices

(at least for undirected graphs)

[nova star]

yea ok

[nova star]

@pale epoch so smallest simple connected graph has 1 vertice? how so

?

i just conncected abc and looped b into itself once and c twice

is it wrong?

[pale epoch]

it depends how exactly you define connected

[nova star]

fuckin definitions lol

[pale epoch]

the way i just defined it, the empty graph is connected

that's what math is

[nova star]

according to this definition i guess si

[pale epoch]

yes

because if a graph has no vertices, all of them are connected

[nova star]

hmmm

i think its not defined like that in book

cuz it states minimum degree in simple graph connectedis 1

[pale epoch]

then they are not using the definition given here

but then the graph with 1 vertex isn't connected either, so 🤷

[nova star]

yea

but u can have two vertices

with 1 edge

i guess thats wut they mean

[pale epoch]

1 vertex with no edge should definitely be connected though

otherwise you lose important theorems

[nova star]

?? thafaqqq

yea i gotta call up my teacher later for these two things

degree of assymetric graphs

and degree of conected/simple graphs

[stray reef]

what is unclear to you in the picture you posted?

[nova star]

it was that min degree of connected graph is 1

and of simple graph is 0

which i found odd, and @pale epoch pointed out that even an empty graph would be connected

especially according to the books rules

[pale epoch]

well, for the empty graph it doesnt really matter i think

[stray reef]

but the picture does not even once mention connectedness

[pale epoch]

you can exclude it in your definition

[stray reef]

what are you talking about

[pale epoch]

the graph with 1 vertex should 100% be connected

[nova star]

degree

[pale epoch]

otherwise you are doing something wrong

[nova star]

yea the picture before

i understand the simple graph, having 0 degree as minimum

dont get why connected is 1 if simple is 0 though

either they think empty graph != graph

in which case both should be 1

or they think empty graph = graph

in which case both shud be 0

[pale epoch]

the min degree in a connected graph is at least 1, unless there is 0 or 1 vertex total

[nova star]

yea but if its 1 vertex

then minimum degree is 0?

and if its 0 vertex too?

[pale epoch]

if there is no vertex there is no minimum degree

[nova star]

k well imma ask maam later i guess

[pale epoch]

if there is just 1 vertex it's connected no matter the degree

[nova star]

so wuts the technically minimum degree of connected graph?

[pale epoch]

0

[nova star]

textbook says 1

[pale epoch]

because the graph with 1 vertex and no edges is connected

[nova star]

now textbook may be wrong

[pale epoch]

and yeah, it might be that your book wont call the "graph" with 0 verteces a graph

[nova star]

but since its used in alotta proofs, i might as well ask maam once

[pale epoch]

just to formulate a few theorems easier

i.e. not having to state "Let G be a non-empty graph ..."

it could also be that it defines the empty graph as the graph having no edges

there aren't really that many universal definitions in graph theory

[nova star]

hmm yea

i guess i just gotta follow wut textbooks say and crosscheck

[pale epoch]

using your textbook definitions is a good idea

although that definition of connected you posted is not very rigorous, so 🤷

[nova star]

yea

but i gotta score somehow lol

imma crosscheck with teacher

[pale epoch]

that is a good idea

[nova star]

lol wtf?

[next valley]

What proof is this for?

[pale epoch]

i assume that the number of verteces with odd degree is even

if you have a more descriptive question than "wtf?", maybe someone can help

[nova star]

does e> or = 3/2v -3 hold for any graph with hexagon or higher polyygon?

and it is impossible to make triangles in bipartile graphs?

[faint narwhal]

prove it

[nova star]

yea i did

just wanna know if my proofs true

so for bipartile u cant make a triangle cuz u need two edge between vertices of same group

and for the hexagon one

(wherever its > it means > or =

e>6f/2 (as each cycle has 6 edges but each edge will cut graph into two regions)

replacing into euler forumla

e<v+2e/6-2

2e/3<v-2

[stray reef]

>=

[nova star]

yea

i just dont know latex

[stray reef]

the latex code is \geq. >= is an acceptable substitute in plaintext. > or = looks weird in an equation.

[nova star]

hmm ok

\geq.

\geq

...

[stray reef]

$ e \geq \frac{3}{2}v - 3$

[vital dew]

Ann:

[nova star]

wut am i doing wrong? i got degrees as 22233

[stray reef]

can you show the problem exactly as stated

[nova star]

ik this is dumb but..

idk im getting this wrong.. so somethin wrong in my fundamentals somewhere

i thought it has 6 edges and degrees of 22233

so the total degree is 15, and edges are 6

but 6*2 = 12

12 =/= 15

[stray reef]

where did you get it from that the total degree is 15

[nova star]

A2 B2 C2 E3 D3

unless im wrong ofc, which i probably am

[stray reef]

2 + 2 + 2 + 3 + 3 = ?

[nova star]

🤦

🤦

🤦

so a planar graph is graph whos edges dont intersect?

[stray reef]

it makes no sense to speak of the edges of a graph "intersecting" or not. nodes and edges are abstract objects.

a planar graph is a graph that CAN BE DRAWN in a way that makes none of its edges intersect.

[nova star]

so any tips on redrawing a graph as planar? im finding it slightly hard and time consuming

also mistakes..

ofc practise is one, but i bet theres a trick

[stray reef]

none that i know of

besides, well, maybe starting with the highest-degree nodes

[nova star]

hmm the textbook says somethin but i dont get it

[stray reef]

...ok, post it then

[nova star]

yea sorry was doin that

wut does it mean by closed path>?

[stray reef]

a path that starts at the same point where it ends

[nova star]

hmm ok

fuck this is wierd shit

but i guess ill do a few and it ll start making sense

idk tbh, to me it seems easier to just visualize an unwrapping of sorts

may be harder in more complex graphs though

does this work as plannar of:

this?

[stray reef]

yes

[nova star]

cool thnx

[nova star]

would a triangle and a line be accurate graph for this degree sequence?

also any tips on how to draw degree sequence graphs

[nova star]

proof by contradiction? 25 <= 3(10)-6

how do u find complement of adjacency matrix? do u have to first draw it?

[nova star]

isnt ABAD a solution to first one? textbook says no