discrete-math

[coarse token]

which rule of inference are you trying to apply

[cobalt mason]

Inverse (A + A') = 1 ?

Idk im conflicted about that Z along with ~(XY) so idk if inverse would actually do

[coarse token]

the multiplier at the bottom would make z negative as well wouldnt it [-(xyz)]? so the equation at the end would end up being: xy + z -(xyz).

[keen oxide]

Hey guys I hope you’re all doing good, can anyone advise me in a book in combinatorics and combinatorial proofs and where I can find a lot of exercises so I can practice.

[coarse token]

https://faculty.ksu.edu.sa/sites/default/files/rosen_discrete_mathematics_and_its_applications_7th_edition.pdf

[coarse token]

you can also try and find books by RD. Sharma. He is an Indian mathematician that makes books for their school system. You wouldn't find a combinatorics book as they like to teach a bit of every kind of math every year (So chapters related to discrete math will be found in multiple books). His questions go from very easy to very very hard, that's his whole thing. I believe almost every problem has a solution in the back too. GL

[keen oxide]

Thank you very much I found what i was looking for in this book

[sweet granite]

Can someone show me how to solve these questions?

[fading plover]

can someone do a combinatorics problem for me

In how many ways can you place 4 math textbooks and 3 physics textbooks if any 2 physics textbooks cant touch each other
keep in mind that all books are different

[haughty garden]

Inclusion-exclusion principle

The total number of ways is 7!, then count the number of ways where at least two physics textbooks touch each other

[loud wing]

can anyone help

[wraith jolt]

Is the (c) correct?

[fading plover]

ye, but 7! is 5040, and the greatest out of the theoretically possible answers from the inclusion exclusion principle is 1944

[fallow stratus]

bro the only thing that you need to do is count the number of vertices in each graph ( vertices are points that represent the graph) second thing number of edges are the total number of lines in the graph. the degree of a vertix is how many lines out each vertix comes out. for example deg of vertix a is 2 !

[brave rock]

Btw it's vertex, not vertix.

Good answer tho

[fallow stratus]

well sorry english is not my first answer

[brave rock]

Quality

[fallow stratus]

thx

well i need self a help in real analysis

so searching for help

because there is a question and know the answer of but do not feel it

[pale valve]

ive got a discrete math question here #help-21｜아리스킨충1 (at the bottom, the top question was answered); think anyone could help me? its regarding function growth and big-O

[sweet granite]

So for a are there 6 vertices , and 6 edges?

[fallow stratus]

yes indeed

you are right!

@sweet granite

keep going Graph theory is so interesting

[sweet granite]

Ok thank you so much!

[fallow stratus]

no worry!

and the degree of each vertix

[timber leaf]

Quick question! When you are finding let's say the first five terms for a recursive arithmetic sequence would it include the initial condition as the first five terms like a0 -> a4 or would i calculate a0 -> a5

as I am given the initial condition

[errant bear]

a0 is the first term

so unless they asked for the next 5, a0-4 should suffice

[timber leaf]

okay ty!

[timber leaf]

I was just confused because when I wanted to check by calculating the sum of the sequence using the arithmetic series equation it didn't give me the same sum as my first five terms

when I plugged in 5

So my sequence was 2, 7, 12, 17, 22 with a0 = 2.So I calculated (5+1/2) (2(2)+5(5)) I didn't get the same as 2 + 7 + 12 + 17 + 22

[errant bear]

what is that formula

[timber leaf]

For the recurrence relation?

It is an = an-1 + 5 (assume n and n -1 are subscripts)

[errant bear]

no

what is that (5+1/2)(2(2)+5(5)) thing and how did you get it

[timber leaf]

The arithmetic series equation

[errant bear]

thats not the formula i have

can you show where you got that formula

[timber leaf]

Sure

It is just from my prof's notes

[errant bear]

some extra parentheses would help, (5+1/2) does not read as (5+1)/2

[timber leaf]

ohh okay sorry

[errant bear]

this is the sum for the 6th term

you have n=5 but are using the sum for the n+1th term

[timber leaf]

but in my prof's example she asked to find the first 15 so she did n + 1?

and I did that as well

[errant bear]

s_15 is probably the sum of a0 thru a15

idk what ur prof did

[timber leaf]

she's very confusing

and races through the lectures

[errant bear]

yeah, s_n is defined as the sum of a_0 through a_n

which is n+1 terms

as 0 is included

[timber leaf]

Okay so if I wanted to find the sum of this series would it be correct

one sec

[errant bear]

seems so

[timber leaf]

Okay thank you

[rocky grove]

Hi idk what to do for the inductive step, could someone help pls

[viscid pike]

how do i do this

[upbeat flame]

hi

[simple cedar]

can anyone help

[stoic wasp]

Can anyone help me with this?

3x + 1 ≡ 5( mod 7)

[sudden torrent]

sure, so 3x ≡ 4 (mod 7) right

now 4 is congruent to -3 mod 7

[urban talon]

I'm reviewing my online exam, and I'm not quite sure how to do this problem:

I took this a while ago lmao, but I remember not knowing how to do it bc I couldn't apply the formula directly? Like it was more roundabout than what we learned in class...

[errant bear]

do you know how to calculate inverses mod n

[acoustic pond]

Hi what is 1/7 (mod 5)?

[cerulean radish]

3

You could use a calculator btw

,w inverse of 7 modulo 5

[vital dew]

Results provided by WolframAlpha

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

Requested by alonelybean

[acoustic pond]

Could it be 1/7 as well?

I say 7 * 3 = 1 (mod 5), so 21%5 = 1

It can also be 7 * 1/7 = 1 (mod5)?

But 3 is better I guess

[acoustic pond]

Oh thank you

[cerulean radish]

Well you would need to find which element 1/7 is if you wanna work nicer with it

[sudden torrent]

recommend you learn the extended Euclidean algorithm if you haven't already

so let 56 = (1, 0) and 33 = (0, 1)

so 56 - 33 * 2 = -10 = (1, 0) - 2 * (0, 1) = (1, - 2)

and 33 + (-10) * 3 = 3 = (0, 1) + (3, -6) = (3, -5)

finally, -10 + 3 * 3 = -1 = (1, -2) + 3 * (3, - 5) = (10, -17)

this tells us that -1 = 56 * 10 - 33 * 17

or that 1 = 56 * -10 + 33 * 17

[sudden torrent]

this is so much easier than the regular Euclidean algorithm

no need for back-substitution

[urban talon]

oh my, i didn't see this till now, yeah when I took the exam i used extended euclidean algorithm, but I didn't quite figure out how to solve for it

[urban talon]

i appreciate your help !

[sudden torrent]

no worries!

[acoustic pond]

Is this statement: ∀(n, m ∈ N | n < m ⇐⇒ n< n+m/2 < m) correctly written in Python?

def statement(n, m):
average = (n + m) / 2
return n < m and n < average < m

[cerulean radish]

Not quite

p <-> q isn't true only when p and q are true

p <-> q means that both statements, at all times, are either both true or both false

[acoustic pond]

is this better?

all(n for n in N1 for m in N1 if ((n < m) == (n < (n + m/2) < m)))

N1 = {1,2,3...100}

[cerulean radish]

Yeah, should be (n+m)/2 though

Also is this all command something new? I don't remember seeing it back when I'd code in python

[vestal bronze]

super old

[acoustic pond]

one more question, is this statement true? ∀(n, m ∈ N | n < m ⇐⇒ n< n+m/2 < m)

so for every values for n and m from 1 to 100 it is always true? because either both statements are false or true which is true

or am I wrong, is there a case when one statement is true and the other false?, then it would be a false statement

[cerulean radish]

The statement
[ n < m \iff n < \frac{n+m}2 < m ]
Is true for all $m, n \in \bR$

[vital dew]

A Lonely Bean

[acoustic pond]

okay good, I will now break it down to two implications and then I think I can prove it

[upper lichen]

(Source - Mathematics for CS by Lehman Leighton and Meyer)
I have a problem showing the last statement - which says if k is not relatively prime to n, then we can show that it isn't cancellable in Z_n. I assume that this means, we have to show for all pairs (k,n) when gcd(k,n)>1, there exists a pair (a,b) for which ak=bk mod n holds, but a=b mod n does not. But I have tried a variety of methods and am unable to come up with one which shows this (the method described in 9.14 seems like it works just for k=3, but not any k). Would be grateful for any help.

[stray reef]

you can make your life a little simpler by finding a number a not divisible by n such that ak = 0 (mod n)

[upper lichen]

got it! such a number a would be n/gcd(k,n)
thank you

[wind peak]

Why are there 43 different strings of 6 bits that contain the string "11"?

[obsidian cradle]

@wind peak count based on the number of ones in the string:
any string with at least four ones work (this can be justified by splitting the string like [XX][XX][XX])
so we have so far: 1+6+15=22
now, if there are 2 ones, there are 5 strings, so 27 so far
if there are 3 ones, we have to consider some cases:

Case 1. the strings X1XXXX
We count how many such strings do NOT work: for this, the neighbours of 1 must be 0, so we have 010XXX... and the only such string that doesn't work is 010101.
So the number of sequences that work is 10-1=9

Case 2. the strings X0XXXX

Subcase 2.1. the strings X0XX1X
And let's count again the number of strings that do not work: so we have X0X010, so 101010, so only one doesn't work
---> 6-1=5 work

Subcase 2.2 the strings X0XX0X
in order for such a string to work we must have 11 in the middle, so X0110X, so two strings work

So the total is 27+9+5+2=43

not sure if this is the most efficient way, but it's quite handy nonetheless

[wind peak]

so we have so far: 1+6+15=22
Where do these numbers come from

[obsidian cradle]

for 6 ones you have one way (111111)
for 5 ones you have 6 ways
for 4 ones you have 15 ways

it's easier to look for 0s in this case

[wind peak]

oh its just 6 choose n

[obsidian cradle]

yes

[tidal kindle]

Can someone explain me this exercise? Dont understand anything

[vernal wave]

You gotta have a more focused question than that. Otherwise someone would have to teach you an entire theory of computation course through Discord ...

[vernal wave]

But to just explain the last bit: You need to show that, for any given string $w$, one of the following must hold: $w\sim \varepsilon$ or $w\sim a$ or $w\sim b$ or $w\sim ab$, where $\sim$ is short for $\sim_L$.

[vital dew]

addem

[tidal kindle]

I want to die

[night narwhal]

can someone give me some leads on this

[vernal wave]

A given sub-multiset will have to choose 0 or 1 or 2 instances of the number 1. And then likewise for 2, and then so on until 10.

[night narwhal]

does that make the answer 3^10?

thanks

[vernal wave]

Yep!

[acoustic pond]

Is the negation for "∀(a1, a2 ∈ A|(a1, a2) ∈ R → (a2, a1) ∉ R) ⇒ ∀(a3 ∈ A|(a3, a3) ∉ R)" correct?

here´s the negation: "∃(a3 ∈ A|(a3, a3) ∈ R) ⇒ ∃(a1, a2 ∈ A|¬((a1, a2) ∈ R → (a2, a1) ∉ R))"

[bleak mason]

does this look right

im unsure if a graph has to cycle to be considered for euler paths/circuits

i want to classify it as both since all the vertices have an even degree

[willow halo]

if each node in a tree has a degree > 0, that tree must have infinite vertices right?

[vernal wave]

Imagine a tree with vertex A adjacent to B and nothing else. The degree of A is 1, the degree of B is 1.

[sage pelican]

i tottaly forget how any of the R^2/R^3 is done, can anyone explain it step by step lol

[vernal wave]

(2,4) in R, and (4,8) in R, so (2,8) in R^2.

[worldly depot]

can anyone conform this is the correct solution please ?

[fossil mural]

that answer is... complete nonsense

x isn't defined

also P(2, 1) expresses the proposition that 2 is the biological parent of 1

also "=" doesn't really make sense between two propositions

and if we interpret everything as having the closest reasonable meaning i can think of (because otherwise the statement doesn't mean anything at all), then since in fact the number 2 is not the biological parent of the number 1, this would be asserting that P(x, y) = false, in other words nobody is a biological parent of anyone

[fossil mural]

so basically that's completely wrong and doesn't even mean anything

[worldly depot]

Thanks I had no idea and I'm struggling with it , can you help me with the answer please

[coral parcel]

To build up to it in stages, can you express "everyone has a biological parent (but possibly more than one of them)"?

[sage pelican]

how did u get the 2,4 and 4,8. thats the most confusing part to me

yo nvm i get it, shit clicked

[wind peak]

a function f : N->N is inyective, does it have to be defined for every N?

[brave rock]

That is part of the requirement of being a function. Injectivity is irrelevant.

[cerulean radish]

If by "being defined for every N" you mean being defined for every natural number, then what Boyt said

[dim burrow]

Hey can someone double check that I shaded the Venn diagrams correctly

also what does the (AB)’ mean

[vale cairn]

Usually means the complement of AB

[dim burrow]

well

is it like union then

i know complement i just dont know what exactly AB means

[brave rock]

Without any context we cannot really tell.

It may simply be a typo.

[dim burrow]

i mean thats how it was posted

[brave rock]

Again we can't really tell, but I'm leaning more strongly towards it being a typo.

[dim burrow]

Alright all good

I shaded the others correctly tho right?

I wanna make sure, there’s no answer key

[brave rock]

You shaded in two colours so it is quite unclear if you have actually done so correctly.

[dim burrow]

the darker one is the final

exceot c where there only one color

[misty storm]

so my question is about relations. when we're checking if a binary relation has reflexive, symmetry, antisymmetry and transitive, if all members of the set are reflexive except one member, we say the entire set isn't reflexive right. is it the same for symmetry, antisymmetry and transitive?

like do all the members of the set need to have symmetry in order to be able to say the set has symmetry or does just one pair of members need to have symmetry and thats good?

sorry i hope i'm making sense 😭

[cerulean radish]

The properties should hold for all elements, yes

[misty storm]

so lets say we have a set {a, b, c, d} and we are told that c and d are transitive, that means the entire set is transitive. yes?

[cerulean radish]

There is no such thing as elements being transitive

Relations can be transitive

[misty storm]

oh okay, lemme reword myself. lets say cRd is transitive but aRb is not transitive. do we say R is transitive or not

[cerulean radish]

Still bad wording, but, whatever you meant by that, no, like I said, the property should hold for all elements (in this case, for all triplets of elements)

[misty storm]

what would be the right wording 😭

[misty storm]

ahh okay this makes sense

[cerulean radish]

I think what you wanted to say is something of the sort "Let's say we have aRb, bRc and aRc (which would make it appear as if transitivity holds), but meanwhile we have bRc and cRd but not bRd"

And the latter contradicts transitivity

[misty storm]

oh i see what mistake i made

thank you!

pls correct me if i'm wrong,
reflexive ❌ becaue of f
symmetry ❌ because of c
antisymmetry ✅ ig? not sure cuz if its not symmetry then it has to be antisymmetry right
transitive ❌ no cuz of c again cuz doesn't have a relation with any of the other members of the set

[cerulean radish]

How does c contradict symmetry?

Antisymmetry doesn't mean lack of symmetry

There are relations that are both symmetric and antisymmetric

And neither symmetric not antisymmetric

Symmetry and transitivity don't require every element to be related to some other element

c being related to only itself doesn't contradict symmetry or transitivity

[misty storm]

gosh i need to revise this again 😭

thanks for pointing out my mistakes

i appreciate it 🤝

[eternal thicket]

Let T be a tournament graph built on 7 vertices, each of which has an outgoing degree equal to three. Hwo to prove that in such a graph there are two vertexwise non-intersecting cycles?

[uncut ferry]

i need help w my assignment I'm outside house n i dont have time doing them

das alot but would b appreciated if u help

[cosmic moss]

how did he get the result?

[gilded nest]

First question:
a(n)=a(n-1)+2a(n-2)
a(2)=a(1)+2a(0)
a(2)=2+2•1= 4
In the same way a(3)=8 and a(4)=16
So this is the first proposal

[cosmic moss]

is there a formula for that?

[gilded nest]

Second question: n²-2
But I think there's a problem somewhere - theoretically it should be 34 instead of 36.

[gilded nest]

He just wrote that?

[haughty garden]

sum of the first n integers is n(n + 1)/2

so sum of the first 10 integers is (10 * 11)/2

[gilded nest]

The third question is just a sum to be calculated

[cosmic moss]

🫰

[cosmic moss]

why this one is not 5^n-1*(5^n)/2?

[haughty garden]

that’s the sum of a geometric series

which has its own formula

[cosmic moss]

i can also write as 5^3 *(1-5^n)/1-5?

[errant bear]

im confused what you're confused about

[gilded nest]

Yep

[simple sky]

the upper component does have an Euler circuit, but if you consider the graph as a whole, with both components in it, it cannot have a trail nor circuit as it is not even connected (example: you just cannot go from V to P)
(plz correct me if i am wrong)
--> question: does the upper component have an Euler Trail? (idk this-one)

[dim burrow]

would this be 26^3 x 4

chat gpt gave me 5 diff answers

the way i did it was 1x26x26x26 times four because the x can be in one of the four positons at least

[brave rock]

Don't use chatGPT.

Hint: how many strings are there which don't contain x?

[dim burrow]

too late, theres no answer key for my review questions and i dont wanna spam yall

uh

25^4

wait

am i wrong

fr

[brave rock]

The point of a hint is that you think about it

[dim burrow]

so i was wrong

i dont get it the one is the x

idk man

i actaully dont know

GENERAL PERMUTATION PRINCIPLE

26!/(26-1)!

yes or no

@brave rock

[brave rock]

You've gone off the rails

[dim burrow]

dude can you just help

plz

[brave rock]

I suggest thinking about my hint here.

[dim burrow]

i obvi dont knw it lmao

i did

[brave rock]

.

[dim burrow]

isaid 25^4

25x 25 each one isnt x

[brave rock]

And now you need to think about how that's going to give you the answer.

[dim burrow]

so ur saying its jstu 26^4 - 25^4

[brave rock]

Why would that be true? Explain it.

[dim burrow]

idk i think my answer was correct

think about it you have four sports

spots*

1(x) x 26(all other letters) x 26 x 26

26^3 where x is the first letter

all that times four for each spot x can be in

how is that wrong

[brave rock]

That overcounts massively.

E.g. you could xxaa twice.

[dim burrow]

hm

[brave rock]

You didn't answer this

[dim burrow]

i dont think thats true i jsut said it

[brave rock]

OK

[dim burrow]

its that formula

permutation

that you said wasnt correct

i feel like

as i sadi 26!/ 1!(26-1)!

dude no

i actaully dotn know can oyu just give me the answer so i can go backwards from the answer

[brave rock]

To count the strings that contain x, find all strings, and subtract those that don't contain x.

I will say nothing more.

[dim burrow]

idk the strings that dont contain x

can you just say if its 26^4 - 25^4

@brave rock

[brave rock]

Please don't ping me

[dim burrow]

wow dont ping in a discord server LMFAO oh no

whatever youre not helping

its not even ahrd to say yes

[haughty garden]

[bleak mason]

the top component does have a euler path

it ended up being neither since it was not cyclical

[snow sleet]

A 4 letter string either contains x or it doesn't. So if I throw out the ones that don't contain x, I must be left with the ones that DO contain x. Does that make sense? Also, yes in general because not everyone is fine with being pinged, don't ping them. And we don't just give answers for ppl to "work back from." We help ppl achieve their answer by working through the problem WITH them, not just giving out answers.

[snow sleet]

Lastly, I will say this^ is such a rude comment to make to someone who took the time to help u and was offering good advice. They weren't getting paid to help u either so they're not obligated to help u. Yet u say things like this to them. Be respectful or don't bother asking your questions here.

[oblique raven]

Can someone help me w a discrete math problem plz I can’t figure out what the correct answer is

[warm quest]

Did I prove this correctly?

Mainly just trying to make sure my approach of taking an arbitrary set and showing it is in the other set is good enough

[vernal wave]

Right basic approach but there are some steps I would say are not adequately justified.

[crisp nova]

The number of surjective functions f with domain {1, 2, 3, 4, 5, 6, 7} and codomain {0, 1} is this 2**7?

[haughty garden]

no this counts functions that all map to 0, for example

[crisp nova]

ya i ended up getting it

how about
An inverse of 44 modulo 101

how do I do this?

euclidean alg?

[crisp nova]

anyone?

lol

[little prism]

yes extended euclidean alg

[frozen mason]

Im working on this proof, apparently there exists a graph with a single vertext and a single edge... and it's a loop how is that even possible? if im not mistaken the edge-sets are specifically 2-susbets of the vertex set. so it's not possible to have an edge {a,a} where a is in V for example, or am I missing something

[little prism]

well it really depends on what definition of a graph you are working with

sometimes edges just like that are allowed

or edges instead are directed, which means they are pairs (a,b). so the pair (a,a) could also be allowed

[frozen mason]

ok thanks

[warm quest]

How would I go about this?

I think there is some 'trick' with the exponents because I can only think of the euclidean algorithm, which is NOT the intended solution

also open to being told what to look up for this to learn it, because i can only find algebra 1 videos searching it up

I imagine it has something to do with them all being prime numbers

lcm I am thinking is 3^6 5^2 7^12 11^2 13^1 17^5

as those are the lowest exponents

^this is not correct

gcd is actually 3^6 5^2 7^12 11^2 13^1 17^5

and lcm is 3^8 5^3 7^14 11^2 13^2 17^7

I know this because of a way too fucking chad prealgebra textbook that had these kids prove it, basically the gcd is the smallest powers these primes are raised to while the lcm is the highest powers of the primes

working on 3)

so the number of positive common divisors is another way of asking how many divisors our GCD has

which is (6+1)(2+1)(12+1)(2+1)(1+1)(5+1)

[coral parcel]

All of that sounds right.

[vernal wave]

I'm trying to understand the runtime of finding all the prime divisors of a number, $a$, by checking for divisibility for each number $2\le x<\sqrt a$. Say that the number of digits of $a$ is $k$ so that approximately $k=\log_2 a$. Suppose that we estimate that the number of digits for each candidate factor is also $k$. To check whether $x$ divides $a$ I assume we use the basic division algorithm, which runs no slower than just multiplying $x$ by each $y$ until the product is too large, and I think that can't be worse than $k^3$ although I could think harder about exactly what the bounds are. But for my question that's probably close enough. And if we do this for every $x$ then we can set the runtime up to $k^4$ I guess.

[vital dew]

addem

[vernal wave]

Anyway, mostly what I want to confirm is that the runtime is polynomial in $k$, right? And $k=\log_2 a$ so in terms of the size of $a$ the runtime is logarithmic, right?

[vital dew]

addem

[vernal wave]

I'm clearly not thinking about this correctly in some way though because famously this algorithm is supposed to be exponential.

[haughty hamlet]

Guys can someone please explain

how

or operation is 0 preserving and 1 preserving

[fossil mural]

And if we do this for every x then we can set the runtime up to k^4 i guess
well this is definitely wrong

the number of factors we're checking isn't k, it's sqrt(a), which is roughly 2^k

more concretely: if you try to check if 1,000,000,000,000 is prime using this algorithm, and you check every x in 2 <= x < 1,000,000, that's not 12 operations, it's 1 million operations

also i think the algorithm you gave for division is also exponential in k? if i'm interpreting it correctly, your suggested method to check if 100 is divisible by 3 is to go "well 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, well we got past 100 and never hit exactly 100 so no it's not divisible"

which is 100 / 3 operations

[crisp nova]

The number of four-card hands from a standard deck that have at least three red cards

I am thinking 26C3 + 26C4

is the case of 3 reds + the case of 4 reds

[crisp nova]

anyone?

[warm quest]

with or without replacement?

[crisp nova]

doesnt specify so without

[warm quest]

looks right off hand

havent done these in a few months

[crisp nova]

ok thanks

[timber leaf]

Can anyone help with this question

I actually have many questions since my prof is challenging us with a few practice problems since most of them are above my level.

[brave rock]

The hint is very good.

Remember that squares are nonnegative.

[timber leaf]

Mhm

i am kind of rusty with my skills using the equality symbol

Do I have to move something to the other side?

[brave rock]

Why don't you try and see

[timber leaf]

So that means a, b, c also have to be >= to 0

[timber leaf]

Is this remotely correct at all?

I am unsure how to communicate it better if it is right though. not completely confident that it is right though

[brave rock]

What you have written is correct but I hope you don't think this is a proof yet

[timber leaf]

nope definitely not

[brave rock]

Great.

[inland apex]

If two trees are isomorphic, then the two trees have the same number edges. True?

[obsidian lintel]

You're almost there, I think you can solve it on your own, but if you need a hint:||You can note that because $(a-b)^2+(b-c)^2+(c-a)^2 =a^2+b^2+c^2-(ab+ac+bc) \geq 0 \therefore a^2+b^2+c^2 \geq ab+ac+bc$||

[timber leaf]

i'm sorry I can't understand what you have provided.

[obsidian lintel]

Maybe easier to read with latex:
$\frac{1}{2}((a-b)^2+(b-c)^2+(c-a)^2) =a^2+b^2+c^2-(ab+ac+bc) \geq 0 \therefore a^2+b^2+c^2 \geq ab+ac+bc$

[vital dew]

consiridk

[timber leaf]

yup that is easier thank yoU!

[timber leaf]

I am just wondering would it have been better if I started the proof the other way around?

Like with the hint

that was provided

[obsidian lintel]

Whichever way makes most logical sense to you

[brave rock]

I think pedagogy would be better served if hints did not consist of the solution

[obsidian lintel]

Sorry

[timber leaf]

Would I need any let statements for this proof?

I am assuming not

but that seems kind of odd

[obsidian lintel]

Yes

I think so at least

Because if two trees were isomorphic but had a different number of edges then they wouldn't have essentially the same shape

[inland apex]

Ty

is the dual of 1+y+z equal to 0yz?

x(not y)z equals to x+(not y)+z

[obsidian lintel]

I actually forgot this, but you need to add a 1/2 term to the beginning. But you will figure it out as u write the proof

[timber leaf]

wait didn't I do that?

[obsidian lintel]

I think you did. But I didn't 🙂

[timber leaf]

Ohh okay but now I am a bit confused because the hint doesn't include the 1/2

[obsidian lintel]

Yeah, I made a mistake. It should be this:
$\frac{1}{2}((a-b)^2+(b-c)^2+(c-a)^2) =a^2+b^2+c^2-(ab+ac+bc) \geq 0 \therefore a^2+b^2+c^2 \geq ab+ac+bc$

[vital dew]

consiridk

[glass tulip]

1/2(x-1)^2-1 graph from vertex form and favored form. How would u solve this

[crisp nova]

Did I do the bipartition correct?

like I get every edge must have an endpoint in the other V set, but is it allowed to additionally have it to the same V set?

anyone?

[upper lichen]

(source - Lehman, Leighton and Meyer - Maths for CS)
I cant figure out why the answer should be different.
In a) given there is 1 ace, we have to figure out the probability that there is atleast one more ace in the remaining 12, which is 1 - prob(no ace in remaining 12). There are 48 non aces and 51 total cards, so it would be 1 - 48/51 * 47/50 * ... 12 times.
Doesn't the same reasoning hold for b)? There are still 48 non aces and 51 total cards in the first step, and the remaining steps are the same. Where does the difference come in?

[crisp nova]

can someone help with my question

[vestal bronze]

your approach maybe works for b instead of a

[upper lichen]

could you help me figure out why it doesnt work for a?

[vestal bronze]

maybe it works for neither

i don't know

[upper lichen]

uh

[vestal bronze]

i will calculate the answer, it won't help finding what goes wrong

[upper lichen]

id appreciate help with the question as is too, i can figure out what went wrong with my approach later

[crisp nova]

yo can you check my question if ur familiar with graph theory

[vestal bronze]

i'm not

[crisp nova]

ok nws

[vestal bronze]

your approach should work for b), you essentially divide hands of 12 with another ace, by all hands of 12

for a) you would kinda double count both sides if you do that, so it's wrong

hands with As: 51c12
hands with only As: 48c12

that's your answer, so you got b)

[crisp nova]

For this isnt the Hamiltonian cycle 1-2-3-5-6-3-4-5-1??

[upper lichen]

thanks! and what should i do for a)?

[cerulean radish]

You shouldn't visit the same vertex twice in a Hamiltonian cycle

[crisp nova]

shouldnt? or you cant

[upper lichen]

you cant

[vestal bronze]

hands with any ace: 52c13 − 48c13
hands with only one ace: 4 × 48c12

[cerulean radish]

Can't

[crisp nova]

in my textbook the definition is like this which is why I wasnt sure:

Let G be a simple graph. A Hamiltonian cycle on G is a cycle C that contains all the vertices of G

[upper lichen]

so it would be (any ace - only one ace)/(any ace)?

a), i mean

[vestal bronze]

i think so

[upper lichen]

it should be all the vertices of G exactly once

[cerulean radish]

,w Hamiltonian circuit

[upper lichen]

thank you!

[vital dew]

Results provided by WolframAlpha

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

Requested by alonelybean

[crisp nova]

ya that makes alot more sense

[cerulean radish]

"Visits each node exactly once"

[crisp nova]

also can you answer this for bipartitions

[upper lichen]

its really trippy that the two have different answers lol... altho i get why the answers are the answers

[vestal bronze]

yes it's counterintuitive

@upper lichenlike imagine the hand comes sorted, so that all aces are at the start, and ace of spades is the first one
your approach describes that situation, you look at the first card and it's ace of spades
but in a) it wouldn't be the first card that's revealed, it would be like first 4 cards, you don't know which cards remain, so you can't count them

it probably doesn't help, it shouldn't, it's not intuitive

[upper lichen]

hmmm kinda makes sense i guess

i guess the bigger lesson is to not trust my intuition in probability lol

[fossil mural]

here's how i'd think about it
a hand with two aces is more likely to contain specifically the ace of spades than a hand with only one ace, because you get two chances for it to be spades
a hand with two aces isn't any more likely than a hand with only one ace to contain an ace, both of those events are probability 1
so "the hand contains an ace" is not evidence for two aces over one ace, but "the hand contains the ace of spades" is

as a more extreme example: suppose i flip a coin and then deal either only a single card, or the entire deck

"what is the probability that i dealt the entire deck, given that there is at least one card" and "what is the probability that i dealt the entire deck, given that there is the five of clubs" clearly have very different answers

[upper lichen]

okay yeah, this makes sense, a specific card existing encodes more information than just any card existing, thank you sm!

[vestal bronze]

@upper licheni think i understand it now

let's just think there's a 2 card hand, and only black aces count as aces
so 50+50 hands have one ace and one hand has both
if someone tells you we're in the left circle, there's more chance we're in the middle than if they told you we're "somewhere in the circles", that's the basic part

the counterintuitive part is like, someone tells you "there's an ace, and also the first ace is spades, I've heard that's important to know"
that information is random, so how come we're truly in the left circle, but the result must be as if we're only "in the circles"

that's because if there's only ace of spades, they have 100% chance to pick spades to tell us, and if there's 2 they only have 50%, that's where the bias is, that's what makes the information useless

if instead, they don;t tell the suit, and you ask them "is there an ace of spades" and they say yes, then we're in the left circle cleanly, you guessed the right suit, which is evidence that both aces are present

this is pretty insane

[coral parcel]

There's a genre of these probability paradoxes where someone randomly decides to tell you something that appears to be irrelevant, and as a result the probabilities arguably change.
I think what's really going on is that conditional probability are not really a good model for the "someone randomly decides to tell you such-and-such".
The standard concept of conditional probability depends on the assumption that in all relevant worlds" where such-and-such is true, that is what I would get told. But if instead there's a larger selections of truths that someone could pick to tell me and they randomly pick just one of them to disclose, then it doesn't make sense to update my beliefs to P(event|such-and-such).

[warm quest]

Hi, I would like help thinking about How many ways are there to arrange the letters in ANTEATER so that the word ANT appears somewhere in the arrangement? iii: How many ways are there to arrange the letters in ANTEATER so that each T is immediately preceded by a consonant?

Nevermind on the first part, I made up my mind.

There are in essence, 3 options for both Ts to be preceded by a consonant.

trying to figure out an answer to this

[timber leaf]

Can anyone verify that this is correct or not

[coral parcel]

Right, so rearrange ANEAER first, and take the three variants of each possibility.

[warm quest]

3(6!/2!2!) is correct here? as we have NT RT and NTTR

6 characters that aren't Ts, 4 repeats 2 Es and 2 As

[coral parcel]

Sounds fair.

[mental pecan]

The last line might be wrong

you can have linear combinations of x, y that are bigger than the gcd and smaller

But the gcd is the smallest positiveo ne

[timber leaf]

yup i redid the whole thing actually

[timber leaf]

How does this look?

[mental pecan]

Very clever! Looks great to me

[indigo rapids]

anyone know how i would go about this?

[lean crescent]

Honestly idk if this should go in discrete math or linear algebra since I learnt induction in linear algebra but am doing this for a discrete mathematics exercise problem

[fossil mural]

induction has nothing to do with linear algebra so yeah this is probably the best channel
or possibly #elementary-number-theory since there are natural numbers here, idk

[lean crescent]

Alright, thank you

[upper lichen]

hint: check cases seperately for numbers <2^(n-1) and numbers >2^(n-1) when trying to prove it for numbers between 2^(n-1) and 2^(n)

[upper lichen]

yep, i was thinking on similar lines after the previous person explained, makes a lot of sense, thanks again

[indigo rapids]

Can i assume this whe doing out a proof?
$$P \wedge Q \rightArrow P \vee Q$$

$$P \wedge Q \RightArrow P \vee Q$$

breh

(P and Q) implies (P or Q)

[lean crescent]

I’ll give that a go, thanks

[mild temple]

,,P \land Q \implies P \lor Q

[vital dew]

vin100

[mild temple]

\verb+\Rightarrow+ and \verb+\implies+ gives $\Rightarrow$ and $\implies$ respectively.

[vital dew]

vin100

[upper lichen]

yes, u can show it by saying if P and Q is true then P, Q are true individually, so P or Q must be true
and id P and Q is false, then implies is already true

[young star]

Guys

Im given "If A, then B"

But A is never possible

[young star]

Does it mean this is always true?

[brave rock]

Yes

[young star]

All of these relations are transitive, right?

[cerulean radish]

Yes

[young star]

thx

[twin zealot]

Hey guys, im going to take a course in discrete math next sem, and I want to get ahead on studying. Any good resources for it?

[coral parcel]

"Discrete math" is an umbrella term for a rather disparate collection of topics, and different institutions have courses by that name that teach different selections of it.

If you want to read ahead, why not investigate which textbook your school's "discrete math" course uses (or has used in past years) and then start on that?

[tight vessel]

^ this is good advice - you'll find after reading through a few books that there's not a standard regimen for discrete math. some schools will emphasize one topic heavily and barely cover another

[wary vortex]

i've been stumped on this question since yesterday. I don't fully understand the concept of catalan numbers so i feel like im missing something to really connect the concepts, can anyone help me understand where to approach questions like these with catalan numbers?

[restive root]

For physics major, do I have to take discrete math?

I am not physics major yet but want to transfer to physics major one day. Thank you

[flint hawk]

my guess would to plug and chug

k={1,5}

plug in each value look for a correlation

there’s probably a better way to do it

[sick grail]

after you pick the first handshake, you split the remaining table in two, because no handshake can cross that one

you can then treat each part as the same problem with a smaller k

[rugged tapir]

Question in the first picture and answer in the second, i have to use the pumping lemma to proof L is not regular, is it alright? Any tips / hints?

[upper lichen]

nope

[warm quest]

real answer: look up institutions you may attend and check yourself. It is unlikely to be required but no one here has knowledge of your intentions

[fringe fable]

Is this part of math harder or easier than the rest?

[meager prawn]

What even is "the rest"

[little prism]

discrete math is a huge topic which can range from easy to extremely hard. just like all the other fields in math

[lean rover]

Anyone that knows temporal logic and explain just something that has been kinda hard for me to understand

[novel ore]

If f: A -> B is a bijection can any set in B be expressed as an image set f(C) for some subset C of A

[grand totem]

For any f : A → B, the image of the preimage of any subset B' ⊆ B will be equal to B' just in case f is surjective

[mental pecan]

Yes try looking at the list of set theory identities

[novel ore]

oh yeah wait DUH

LMFAO

just take the preimage 💀

[mental pecan]

This is actually true for every bijective function (f(f^{-1}(A)) = A)

Yeah

[novel ore]

bruh

[mental pecan]

Yeah it does need to be bijective

[fossil mural]

i think it should work as long as it's surjective actually...?

f(f^-1(A)) is always a subset of A no matter what f is, and if f is surjective then it will be equal to A

it's just that for an arbitrary surjective function some proper subsets of f^-1(A) might also work

[mental pecan]

Yes ur right I was tired when I sent that

Way I remember is left inverse iff injective and right inverse iff surjective, and these hold for single elements but are in fact equivalent for whole sets

[lyric flax]

$cos(\lim_{x \to 0} \frac{1}{x})$

[vital dew]

wub-dub-shub-cub

[lyric flax]

[sweet granite]

Hi can someone help me understand concepts for these topics: Properties of relations, graphs and equivalence relations? I have the lecture notes but i need to know like what stuff is important and i should remember for my exam. If anyone could help that would be amazing!

[placid knot]

Any1 here who is good at discrete mathematics? 😷😭 would be down to pay for tutoring 😋🥰

[fierce granite]

I don't think you are supposed to ask for or advertise paid tutoring so you will probably not get a reply.

[coral parcel]

We don't allow advertising for it. Asking is not forbidden but also not really condoned, and the server wants no part in any subsequent disputes about whether the help was really worth the price asked.
Come to think of it, I think most of the prolific helpers here would rather explain stuff for free in the server rather than worry about being involved in such a dispute (not to mention the tax bureaucracy that comes from accepting money privately).

[solar marsh]

help with (b) pls 🥺

[coral parcel]

"(c)" doesn't seem to refer to anything?

[solar marsh]

its (a)

[coral parcel]

Ah.

[solar marsh]

a typo

[coral parcel]

The natural strategy would be to find a way to generate sequence pairs of every length where there's no both-monotonic subsequence longer than n^(1/4).

Do you already have a tight bound on monotonic subsequences of a single sequence you can use for inspiration?

[vital dew]

Kevin
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[solar marsh]

This is for part (a) and maybe it can be useful

my bad attempt

[coral parcel]

Hmm, afraid I don't immediately get any idea that feels useful.

[little prism]

is there an example of erdös-szekeres which shows that it is optimal? and can you build your counterexample from that?

[solar marsh]

yes

in the finnal remark

[little prism]

ah so thats your example

yeah I dont see anything either

[wraith mist]

Hey can't the intersection of sets be expressed by the union and set differences?
Like $A\cap B = ((A\cup B)\setminus A)\setminus B)$
It's pretty clear from the ven diagram this should work.

But when I try to distribute I keep getting the empty set. $(A\cup B)\setminus A \setminus B = (A\cup B)\cap A^c \cap B^c = ((A\cap A^c)\cup (B\cap A^c) )\cap B^c =(B\cap A^c)\cap B^c =0$ is this identity not true or am I distributing wrong?

[vital dew]

HausdorffT1

[brave rock]

You haven't got it right, no

A\cap B = ((A\cup B)\setminus A)\setminus B)
This is false.

In fact ((A\cup B)\setminus A)\setminus B) is the empty set.

This should be pretty clear: A \cup B contains only elements in A or in B, so if you remove all elements from A and B you get nothing left.

You're probably getting this confused with de Morgan's law, which states (in one form) that $((A \cup B)\setminus A) \cup ((A \cup B) \setminus B) = (A \cup B) \setminus (A \cap B)$.

[vital dew]

Boyt

[wraith mist]

I was just about to write that yes I did get confused with that one lol

Thank you

[brave rock]

A nicer form is $(B\setminus A) \cup (A\setminus B) = (A \cup B) \setminus (A \cap B)$.

[wraith mist]

Or I guess the one I'm interested in is $A\cap B=A\cup B \setminus (A\setminus B)\setminus (B\setminus A)$ which is probably the same thing

[vital dew]

Boyt

[brave rock]

No what you've written is very odd

(B \setminus B)?

[vital dew]

HausdorffT1

[brave rock]

I can see what you're trying to say at least

Yes

It is the same thing

[solar marsh]

Any recommended bibliography to study the posets and see important examples?

[night sinew]

Isnt this set theory

[brave rock]

No it's an armadillo

[night sinew]

woahhhh

[sweet granite]

Can anyone explain how to get this solution?

[haughty garden]

An equivalence relation must firstly contain the elements (a, a), (b, b), (c, c) because it is reflexive. By the symmetric property, we know that we only need to look at about half of the elements because if (a, b) \in R, then so must (b, a). Therefore, we really only need to care about the elements (a, b), (a, c), (b, c) -- the remaining elements must follow by including at least one of these elements, so transitivity is really all you need to worry about.

Choose two pairs and include them into your relation, see what you can build from it

[snow sleet]

and I will add this note: You know there must be exactly 5 relations (not more and not less) since that is the number of partitions of a 3-element set

@sweet granite ^

[sweet granite]

So R1 always has (a, a), (b, b) and (c, c) format?

[haughty garden]

any equivalence relation must contain those three elements

[sweet granite]

I dont understand what to you mean for the rest

[snow sleet]

yes because the relation must be reflexive! (x,x) if and only if x is related to x remember

[sweet granite]

Okay good to know thanks

[sweet granite]

I thought reflexive was when its like (a, b) (b, a)

[snow sleet]

and this is for all x=a,b,c

all elements of the set

[snow sleet]

symmetric

let me cite the definitions

[sweet granite]

Yeah symmetric i mixed them up 😭

[sweet granite]

Okie

[snow sleet]

Reflexive: For all x in S, (x,x) in R.

Symmetric: For all x,y in S, (x,y) in R implies (y,x) in R.

Transitive: For all x,y,z in S, (x,y),(y,z) in R implies (x,z) in R.

ALL three properties must be satisfied for the relation R on S to be a calld an equivalence relation

[sweet granite]

Ohh

So first one R1 has to be always reflexive? Like (aa) (bb) (cc)?

[snow sleet]

all equivalence relations must be reflexive. That's why (a,a), (b,b), (c,c) are in all of the relations

[sweet granite]

And then R2 has to be symmetric. Like (aa) (ab) (ba) ? I dont understand we didnt do the rest for b and c

[sweet granite]

Ok that makes sense now

[snow sleet]

let's look at the first one actually and work from there.

[sweet granite]

Okay

[snow sleet]

R_1 is reflexive.

is it symmetric?

[sweet granite]

Yes i think

[snow sleet]

(a,a) is in there so (a,a) is, right?

same with (b,b)

and (c,c)

[sweet granite]

Yrah

Yeah*

[snow sleet]

great now if (a,a) and (a,a) are in there, is (a,a) in there?

[sweet granite]

In R1?

[snow sleet]

same with (b,b) and (c,c)....

[snow sleet]

yes

[sweet granite]

Yeah

[snow sleet]

I'm checking transitivity

[sweet granite]

Ohh

[snow sleet]

great so R_1 is an equivalence relation

so now let's just throw in an ordered pair

to great R_2

[sweet granite]

Oh so each has to be checked and found separately?

[snow sleet]

each relation u create u must verify that it's an equivalence relation yes

so now for R_2, let's keep going

[sweet granite]

Okay its starting to make more sense now

[snow sleet]

so R_2 must have (a,a) (b,b), and (c,c) to satisfy reflexivity

now let's toss in (a,b)

[sweet granite]

And it has them. If it has extra characters do we have to check them too?

[snow sleet]

but then since we must have symmetry, we must also have (b,a)

[sweet granite]

Okay understood

[snow sleet]

if S had more than three elements, then yes. Since S only had a,b,c. we just need to check (a,a), (b,b) and (c,c) for reflexivity

but

now let's verify R_2 is transitive

if (a,b) and (b,a) are in there, is (a,a) in there?

[sweet granite]

Yes

So its transitive

[snow sleet]

perfect and if (b,a) and (a,b) in there, is (b,b) in there?

[sweet granite]

And equivilance

[sweet granite]

Yup

[snow sleet]

remember, transitive is checking this^ for all x,y,z in S such that (x,y) and (y,z) in R.

[sweet granite]

Okay i’ll remember that

[snow sleet]

perfect checking just two ordered pairs isn't always sufficient.

[sweet granite]

question

But why didnt we do (bc) and (cb) to r2?

[snow sleet]

I'm just giving u an idea of how to go about checking some of these properties on specific elements.

[sweet granite]

Okay

[snow sleet]

because we will do it for R_4.

we're trying to make the MOST equivalence relations

[sweet granite]

So like how do i know if i should add that in r2 or r3 and so on?

[sweet granite]

Ohh ok

[snow sleet]

notice what they add. They add (a,b) in R_2. Then they add (a,c) in R_3 and then R_4 has (b,c) added. Those are all pairs of elements from S.

but as u add (b,c) u must add (c,b), etc.

because we must satisfy all three properties for the relation to be an equivalence relation

@haughty garden sorry sort of took over this.

[sweet granite]

So would the answer be correct if i added (ab) (ac) but in different orders?

[snow sleet]

if u add (a,b) u must add (b,a) and if u add (a,c) u must add (c,a)

[haughty garden]

all good! I kinda got busy with something soon after ._.

[snow sleet]

and actually u must add (b,c) as well!

[sweet granite]

Like (ac) in r2 and (ab) in r3?

[sweet granite]

To r4?

[snow sleet]

u must add (b,c) as well since (a,b) is in there so (b,a) is in there. and if we also have (a,c), then for transitivity, since (b,a),(a,c) is in there, we must have (b,c)

and then since (b,c) is in there, we must have (c,b)

for symmetry

[sweet granite]

No i meant like (bc) in r2 and (ab) in r3

Like do i have to follow the order in the solution?

[snow sleet]

that wouldn't be there R_2, but yes that is another way to create a relation. The goal is to come up with equivalence relations. It doesn't matter that your R_2, isn't exactly their R_2. as long as u have an equivalence relation ur good

[snow sleet]

no. hopefully I just answered that^

[sweet granite]

Yeah you did

[sweet granite]

I should be good as long as i have r5’s that are equivilance relations right?

[snow sleet]

as long as u have a list of 5 distinct equivalence relations, ur good

[sweet granite]

Also for this question they said three elements. Would the number of R increase if the number of elements in the questions increase?

[snow sleet]

yes.

and

[sweet granite]

Dang

😭

[snow sleet]

given |S|=n, the number of equivalence relations on S is equal to the number of partitions of S

so that's how u know there are no more than 5 for ur problem |S|=3

[sweet granite]

So if there were 4 elements in a question there would be 7 Rs?

[snow sleet]

nope

15

[sweet granite]

15 omgg

That would fry my brain

How do i know the number of partitions?

[snow sleet]

B_n is the bell number that is the number of partitions of an n element set

B_4=15

B_3=5

[sweet granite]

Whats B?

[snow sleet]

i just said

bell number

https://en.wikipedia.org/wiki/Bell_number

[sweet granite]

Thank you so much for helping and bearing with me

[snow sleet]

thanks for being easy to teach!

[sweet granite]

Easy to teach i think i was asking the dumbest questions repeatedly

[snow sleet]

meh we've all been there especially when we're confused. I've been there before all too often! ahaha

[lean rover]

(| b + c = 0 /\ b > 0 |)
a = b + c;
(| p |) which of the following is true for p, I said everything except the 2nd. Is it correct in hoare logic?```
a = 0 /\ a - c > 0

b + c = 0 /\ b > 0

a = 0 /\ b > 0

a = 0 /\ c < 0```

[lofty sluice]

Can someone pls explain what a total order relation is in discrete math. I understand what a partial order relation is but the books definition for total order relation does not make sense to me.

[coral parcel]

A total order is a partial order where additionally it's guaranteed that one of a<b, a=b, or a>b holds for each pair of a and b.

(It would be easier to answer usefully if you'd quote the definition that doesn't make sense to you, so we don't just repeat it ...)

[steep ether]

Im getting super confused by premises and conclusion, when can we determine whether a conclusion is true or false? For example in this problem, what am I supposed to compare r to? whether a premise is true when r is true?

ik its a dumbass question im just having a major brain fart

here is the answer if it helps to visualize it

So like as long as 1 premise has the correction answer for the conclusion, i.e. here in row 4 the ∼ q ∨ r is True while R is false, it doesnt matter since p → q is False?

[fossil mural]

"when all of the premises are true, is the conclusion true"

so yeah if any of the premises are false it doesn't matter

[sweet granite]

How do you solve these type of questions?

I figured out how the vertices are created but i dont get how to draw the edges

[errant bear]

do you not know what an adjacency matrix is?

[sweet granite]

Isnt that in the problem?

Like this one?

[errant bear]

... im assuming that response means to imply that you do know what an adjacency matrix is. which if that was the case, you would know how to construct the graphs

[sweet granite]

Yeah i think i dony

Dont*

But i thought matrices like these were called adjacency matrix

[errant bear]

what would a non adjacency matrix look like?

define "looking like these"

[sweet granite]

Idk about that

[sweet granite]

Like 1s and 0s instead of other numbers in the matrix

[errant bear]

im assuming you dont have a math background?

[meager prawn]

except it's literally not 1s and 0s only

[sweet granite]

So it can have other numbers too?

[errant bear]

in this case, the number at row n and column m corresponds to the number of edges from node n to node m

[meager prawn]

it doesn't take long to notice there's even a 4 in f's matrix
So you can have arbitrarily large integers

[sweet granite]

Yeah youre right it does have other numbers

[steep ether]

Can anyone explain how we can make this step? I'm looking at all the probability equations I have and I'm not sure what my professor has done here

thanks

Is it that P(A^c n B) can be written as P((1-P(A)) n B) and that can then be interesected to create P(B) - P(A n B)?

[haughty garden]

(A^c n B) and (A n B) form a disjoint union of B, so P(B) = P((A^c n B) U (A n B)) = P(A^c n B) + P(A n B); rearranging gives you the result: P(A^c n B) = P(B) - P(A n B)

[steep ether]

ok that makes a lot more sense that what i said, essentially in words, the intersection of A with B and the intersection of the complement of A and B is the same thing probability of B, since the probability of A and A's complement = 1?

Also I read ur bio, what do you think the best way to determine whether a problem requeries permutations or combinations? I know one is whether the order matters or not but it isnt always that clear

[weary tiger]

Is this how you do conditional proofing?

[cedar abyss]

vowels. How many strings of six lowercase letters of the
English alphabet contain
b) exactly two vowels?

I did C(6,2)* 5 * 5 * 21^4 - C(6,2) * 5 * 21^4 because we need to choose 2 spots out of the 6 to put the vowels, there are 5 options for the 2 vowels, and 21 options for the 4 consonants, and I thought that we are counting twice the strings that have the same 2 vowels so I subtracted them, the solution on the book is equal to C(6,2) * 5 * 5 *21^4, so the same as mine but without the subtraction. Why is that? arent we counting them twice??( the solution according to the book is 72,930,375)

[vestal bronze]

@cedar abysswe're not counting any strings twice

because we don't

i guess i have literally no helpful information

[cedar abyss]

yeah I think I get it now

It was a stupid mistake, I took a brake and now that I looked at it again it makes sence

[novel raptor]

Hi guys

Can someone explain why R○R = ....

Why (y^2-1)/4

[tropic vigil]

can someone help me with discreet math tomorow 1-3pm?

[stray reef]

1. timezone?
2. why the specific timeframe?

it sounds as if you might be trying to solicit test cheating

[rigid oriole]

99%

[steep ether]

Did my exam today I know I really shouldnt but I'm curious if i got a question correct

Relation R produces a set = {(1,1),(1,2),(2,1)}

I said it is symmetric, it is not transitive, and not anti symmetric

im pretty confident on antisymmetric but for transitive my reasing was based off the definition that if (a,b) e R, and (b,c) e R, then (a,c) e R does not hold if we do (2,1), (1,2) therefore we would need 2,2 for it to be transitive

but im not sure

[steep ether]

I mean if your exams are online everyone is cheating

[cerulean radish]

Your answers are correct

[steep ether]

Might have gotten a 100/100 then :o

[half fern]

hey guys. I'm looking for some resources on discrete mathematics, just needing to catch up for my upcoming algorithms class as I missed discrete math last semester and it is a recommended preparation.

not the best at just reading a textbook and jamming it out with discipline, prefer something interactive like khan academy style. practice questions, good lessons, flash cards are a major bonus

not opposed to pay if its really worth

[errant bear]

what from discrete would you need for algos?

like graph theory stuff or

[half fern]

im not sure , all i know about discrete is that sets is a big thing

so im keen on something that starts from the beginning and i can just bust it all out

like discrete 1

[errant bear]

sure, but if you know what a set is thats all you need to know imo

the only overlap with discrete from algos is graph theory.. which you should know/learn from algos

[real tiger]

I have to create a formal regex that only accepts all binary strings of all odd lengths but cannot have any consecutive 1s. I came up with this automaton and I planned to use elemination technique to remove the nodes and create a regex from the removed nodes one at a time. I can easily remove q4, but I get stuck on how to remove q2 properly.
Am I even going in the correct direction? Or am I making things more difficult than they need to be? The lecturer said this is really easy and didn't even bother to give a hint of where to start.

[haughty garden]

I teach algorithms at my university, and we really only emphasise that discrete math is useful because it helps you settle into some of the notation that we introduce throughout the course — you’re not going to need a whole lot from discrete, but being somewhat comfortable with reading mathematics and some basic understanding of proofs would be helpful. The level of proofs would vary depending on how rigorous your algorithm curriculum is, as well.

[half fern]

okay thanks a bunch. do you happen to know any good resources anyways?

so far ive only found quite dreary videos or super large textbooks

[haughty garden]

Do you have an outline of what your algorithms class is going to cover?

[half fern]

when i did calculus i found there to be a bunch of really solid material online, blackpenredpen, 3blue1brown, etc

[haughty garden]

The discrete math that would be relevant would be: set theory (for ease of notation and makes everything simpler to understand), proofs (particularly pertinent to the study of greedy algorithms), graph theory (understanding basic concepts of graph theory would make it easier to navigate the later topics), and probably recurrence relations. So you can probably find small bite-sized videos for each of those topics online and that should set you up nicely for the course

[half fern]

ya bloody legend thx so much

[fresh hull]

I start discrete math next semester too

Its a common course with differential equations

[weary tiger]

Is there a source that properly derives the Euler Summation Transform? I'd appreciate it if someone links it

At least in this context. Wikipedia shows a more general version but I don't find its derivation (rather verification) appealing
(Below image is not mine)

Wikipedia link: https://en.m.wikipedia.org/wiki/Euler_summation

[weary tiger]

Okay I like the wiki proof now

[zealous stone]

Hi, does anyone have any tips on how to simplify this?

[weary tiger]

You can simply LHS as said in the image, using the distributive law

[zealous stone]

I tried that but got stuck sadly

[weary tiger]

It's similar to distributive law in Real numbers

[zealous stone]

I get to (A or B ) and (not B or B) and (A or not C) and not(B and C)

But from there I dont know

[weary tiger]

It is correct

Okay consider (not B or B)

You can simplify this

||(hint: OR truth table will help)||

I am unsure about (A or not C though)

Actually, it can still simplify further

[weary tiger]

First try simplifying this one @zealous stone

[zealous stone]

Ok

So I get that to a tautology and am left with (A or B ) and (A or not C) and not(B and C)

[weary tiger]

Yes

[zealous stone]

But how do I get rid of (A or not C)

[weary tiger]

I compared the truth tables of ((A or B) and (A or not C) and not(B and C)), and the RHS in the given image, and they both match, but sorry I am unable to assist you from here

[zealous stone]

Np at all, thank you very much for the help

I guess I will just have to think on it for a bit more

[spring quartz]

Hello this is probably like the most stupidest question asked but I need help with but how would I go about writing a suitable expression for this practice question? It's discrete maths for computer science and it involves set theory and Relations. I feel like I could just as easily write a fatherOf b but it would just completely disregard the 2nd part of the question they want me to write about

[vale cairn]

Write it in terms of childOf and the sets Male and Female

[spring quartz]

So childOf = Male and Female?

[spring hound]

Do you know how to write that someone is male?

[spring quartz]

a is an element of male?

[spring hound]

Right.

How would you write that a is the parent of b?

[spring quartz]

ohh a fatherOf b?

[spring hound]

You don't have "fatherOf". You only have "childOf".

How do you write that a is the parent of b?

[spring quartz]

a parentOf b?

[spring hound]

There is no "parentOf". You only have "childOf".

[spring quartz]

srry im thinking

im just looking backa nd forth

[coral parcel]

Looking back and forth is not what you need. It's right in front of you, you just need to pick it up.

[spring hound]

As a hint: you have "a childOf b". What is a in that relationship? What is b?

[spring quartz]

okay sorry I was a little distracted

a is the parent and b is the child

-a child of b?

[spring hound]

No.

"a childOf b" can be read like "a is the child of b".

[spring quartz]

oh

im sorry im not picking it up

b is the parent of a

[spring hound]

Right.

[spring quartz]

b parentOf a? but there is no parent

[spring hound]

If you want to say that a is the parent of b, you say "b childOf a".

You don't have "parentOf".

[spring quartz]

wth

omg

[spring hound]

You can only use the relations they give you unless you define more.

[spring quartz]

im overthinking it so much

im sorry

[spring hound]

It's OK. When you're new to it, it can be mindbending.

So, a father is a male parent.

So, the father would be in the set Male.

Also, the the father would be "child childOf father"

So, which variable do you want for father and which do you want for child?

[spring quartz]

f for father and c for child

[spring hound]

OK, so f is in Male and c childOf f.

That's how you'd check if f is the father of c.

Does that make sense?

[spring quartz]

yes

[spring hound]

OK, so you can write that as (f \in \text{ Male } \land c \text{ childOf } f).

[vital dew]

Chai T. Rex

[spring hound]

So, you can define "fatherOf" like this:

(f \text{ fatherOf } c \Leftrightarrow f \in \text{Male} \land c \text{ childOf } f)

[vital dew]

Chai T. Rex

[spring hound]

So, if f is male and c is their child, the f is the father of c.

Does that make sense?

[spring quartz]

it does

[spring hound]

OK, I'd recommend a break before going on.

[spring quartz]

okay thank youu im thinking for the rest

[spring hound]

No problem. The others use quantifiers.

So, they're a bit more complicated.

[coral parcel]

(And you'll need to make a decision about whether half-siblings count, since the problem doesn't seem to specify).

[spring quartz]

(s \text{ siblingOf } c \Leftrightarrow \exists s \in \text{Male} \lor {Female}

wow thts embarrassing

I can't think of the last part

for siblingOf

[spring hound]

OK, forget how to write it. If I was an alien who knew about someone being a child of someone else, how would you explain siblings to me?

[spring quartz]

if the parent has 2 children they are siblings

[spring hound]

OK, but I mean how do I tell if two people are siblings?

[spring quartz]

if they have the same parent

like mother or father

[spring hound]

OK, so you say there's a person they're both the child of.

[spring quartz]

oh yes

[spring hound]

How would you write that?

[spring quartz]

do i write the expression

[spring hound]

Yes, how would you write that?

[spring quartz]

f fatherOf c ^ c?

[spring hound]

c isn't true or false, so you can't use it with ^.

^ has true or false on both sides.

[spring quartz]

oh i was trying to type 2 children and I thought that was the and sorry

[spring hound]

Well, let's look at it closer.

There's a person that they're both the child of.

How would you write "there's a person"?

[spring hound]

Oh, ^ is and, but only with true and false things.

[spring quartz]

Person from the person = male and female right

[spring hound]

Well, we haven't said anything about whether they're male or female.

You can just use the set Person.

[spring quartz]

so Person?

[spring hound]

OK, what variable do you want to use for the parent?

[spring quartz]

p

[spring hound]

OK, how do you say there's a p that's a person?

[spring quartz]

p is an element of person i think

[spring hound]

OK, but that's missing something.

[spring quartz]

the male or female part?

[spring hound]

The "there's" part.

You have "a siblingOf b" or something like that.

[spring quartz]

yea

[spring hound]

p isn't included as a variable there, so you have to introduce it with a quantifier.

The quantifiers are (\forall) and (\exists).

[vital dew]

Chai T. Rex

[spring hound]

How would you introduce p?

[spring quartz]

all male and female are a person

[spring hound]

That's not involved in what we're doing.

[spring quartz]

o

[spring hound]

Give an example of a quantifier.

I mean using a quantifier.

[spring quartz]

there exists a male or female that is a person

so exists

[spring hound]

How do you write that?

[spring quartz]

p \exists {Male} ^ {Female}

[spring hound]

No, (p \exists \text{Male} \land \text{Female}) is not proper notation.

[vital dew]

Chai T. Rex

[spring hound]

Have you actually seen a quantifier used somewhere?

[spring quartz]

im looking at this one from my lecture notes

[spring hound]

OK, so you have the quantifier, then the variable you're introducing, then the set that the variable is from.

Does that make sense?

[spring quartz]

yeah so could we do any of the quantifiers, then p and p is the set person

[spring hound]

OK, so (\exists p \in \text{Person}.)

[vital dew]

Chai T. Rex

[spring hound]

So, we have "there's a person".

How do you write that a and b are children of p?

[spring quartz]

a childOf p

or b childOf p

wait

wrong way i

nvm

oh nvm

a childOf p

[spring hound]

You're saying that a is the child of p or b is the child of p, right?

[spring quartz]

id like to write both but i dont know how

[spring hound]

You can use ^.

That means both have to be true.

[spring quartz]

oh a ^ b childOf p

[spring hound]

v means at least one has to be true.

No, ^ has true or false on both sides.

a is a person.

You can't have "a ^ something" because a isn't true or false and the sides of ^ have to be true or false.

Does that make sense?

[spring quartz]

oh

teag]

yeah

[spring hound]

OK, so how would you write it?

[spring quartz]

a childof p ^ b childOf p

[spring hound]

OK, good.

(\exists p \in \text{Person. } a \text{ childOf } p \land b \text{ childOf } p)

[vital dew]

Chai T. Rex

[spring hound]

That says there's a person where a is the child of that person and b is the child of that person.

[spring quartz]

yea

[spring hound]

So, now you just need to define siblingOf.

(a \text{ siblingOf } b \Leftrightarrow \exists p \in \text{Person. } a \text{ childOf } p \land b \text{ childOf } p)

[vital dew]

Chai T. Rex

[spring quartz]

ohh I thought i wouldve had to use the person variable in the first part of the expression too

like at the start to define

[spring hound]

You mean in the "a siblingOf b" part?

[spring quartz]

yeah

[spring hound]

No, you're checking whether two people are siblings, so you start with those two people.

So, all you need for that are the two people.

Then, on the right, you can introduce the potential parent.

You don't say "a is a sibling of b" with p somewhere in there.

You use the p to figure out if it's true, but it's not part of the statement of what to figure out.

[spring quartz]

oh

[spring hound]

It's like "Are a and b siblings?" is the question, and the answer is yes or no, but to figure that out then you talk about parents.

[spring quartz]

ohh

yeah it makes more sense now

[spring hound]

So, what about cousinOf?

How would you explain to a person how to figure that out?

[spring quartz]

children of siblings are cousins

[spring hound]

OK, so how many people are we talking about there?

[spring quartz]

4 people, 2 siblings and their children

[spring hound]

OK, so "a cousinOf b" has the two children.

We need to introduce the other two people.

So, how would we write that?

[spring quartz]

we use person

so

im thinking of how to write 2 person

[spring hound]

Oh, we need to go back to the previous problem.

(a \text{ siblingOf } b \Leftrightarrow \exists p \in \text{Person. } a \text{ childOf } p \land b \text{ childOf } p)

[vital dew]

Chai T. Rex

[spring hound]

The problem there is that a and b don't have to be separate people.

So, we need:[a \text{ siblingOf } b \Leftrightarrow \exists p \in \text{Person.} a \text{ childOf } p \land b \text{ childOf } p \land a \ne b]

[vital dew]

Chai T. Rex

[spring hound]

Does that make sense?

We use the a not equal to b to show that they're different people.

[spring quartz]

yeah i was about to type that theyre not that but why do we need that

[spring hound]

Because a and b can be the same person, so a has the same parent as b, but they're not siblings.

[spring quartz]

oh

yeah that makes sense

[spring hound]

OK, so how did we introduce a variable last time?

[spring quartz]

we wrote: exists quantifier p is an element of person right

[spring hound]

Right.

So, if the set the two values are in is the same, you do: [\exists p, q \in \text{Person. }]

[vital dew]

Chai T. Rex

[spring hound]

If they're in different sets, you do:[\exists f \in A. \exists g \in B.]

[vital dew]

Chai T. Rex

[spring hound]

Does that make sense?

[spring quartz]

yes but I thought I wouldve had to use the quantifier for q too

[spring hound]

OK, so we have all the variables (a, b, p, and q) introduced.

So, we want their parents to be siblings. How do we write that?

[spring quartz]

we would have to write that theyre both in one set right?

[spring hound]

We already wrote that with:[\exists p, q \in \text{Person.}]

[vital dew]

Chai T. Rex

[spring hound]

How do we do the siblings part?

[spring quartz]

can we re-use the siblingOf definition

so p siblingOf q

[spring hound]

You can use "siblingOf" directly.

OK, so that's good. Now how do we say that a and b have those parents?

[spring quartz]

a childOf p ^ b childOf q

[spring hound]

OK. "siblingOf" already checks whether they're different people.

So p and q are different people.

[spring quartz]

yes

[spring hound]

But we haven't done that with a and b.

[spring quartz]

so would we have to write a not equal to b at the end

[spring hound]

Is there a way for someone to be their own cousin?

[spring quartz]

oh

no