discrete-math

[vital dew]

clementine

[snow cedar]

And R^(3)(a, b - 1) + 1 <= n so K^(3)(n) contains a red K^(3)(a)

[lethal linden]

You don't need to extend anything in the red case. You have R^3(a, b-1) vertexes.

If you have a red 3-hyperclique with a vertexes then you're done, whether you extend to include v again or not.

[snow cedar]

Oh so I'm doing extra work

[restive raptor]

I have a question regarding Adjacency Matrixes in Graph Theory. Is it safe to assume that there exists an isomorphism between 2 graphs if the row echelon form of their 2 corresponding adjacency matrixes are the same? And what if they correspond to the identity matrix, is there any theorem that proves/ supports any conclusions regarding that aswell?

[lethal linden]

No.

[restive raptor]

So let's assume i have two graphs , each one with 10000 vertices. To prove there's an isomorphism I have to map each indivual vertex from Graph 1 into Graph 2, thus taking 10000 mapping operations?

[opal crescent]

the question is how do you map them ? you can't just take any old bijective function from the vertices of graph 1 to the vertices of graph 2 and hope it's an isomorphism, there's just too many of them

factorial of 10000 is a stupidly huge number

[restive raptor]

I was looking for an easy way to prove theres an isomorphism between 2 graphs without having to individually map a pair of vertices 10000 times, is there anything that can help me with that?

[inland hare]

Is there some online tool where I can input a truth table and it spits out a simple logical formula?

[opal crescent]

you're looking for software ?

[remote jay]

can any one recommend any yt channel to learn full DM?

[mental plaza]

trevtutor, dr.Trefor, and kimberly brehm have pretty good videos for DM

i recommend going through a textbook though because you wanna practice proofs and exercises

[cursive nymph]

very very stupid question ahead warning

could there be a 'universe' in which the cardinality of an infinite set could be smaller than countable?

[brave rock]

If a weaker version of AoC holds (namely, unsurprisingly, the axiom of countable choice) then the countable cardinality is the smallest cardinality.

[restive raptor]

No not really, I was just wondering how it was done computationally when dealing with very big graphs

[haughty garden]

the computational complexity of graph isomorphism is still an open problem, so we don’t know whether deciding if two graphs are isomorphic is a computationally easy problem or not. You might want to look at some invariants under isomorphisms and see if they hold for your two graphs

The best we can do is a quasipolynomial-time algorithm due to Babai (https://arxiv.org/abs/1512.03547)

[polar crag]

Not sure if the right channel, but quite confused by this part in Halmos' Naive set theory. Why are we assuming B equivalent A and why B E B or B E' B , not and please

[fossil mural]

i don't see where it "assumes B equivalent A"?

[polar crag]

Also confused as to why B E B is so unlikely, so far seen the 'hat in a box is not a hat argument', but confused as to why that means it is possible

[polar crag]

Pardon me, is contained in

[fossil mural]

the reason to assume that either B e B or B e' B is that every statement is either true or false

if we assumed that B e B and B e' B then that would be a contradiction immediately

(if i'm guessing correctly that x e' y means x isn't an element of y)

[polar crag]

This is correct

Oh ok, so they're saying if it is contained in A then by definition it is contained in A? e.g. we are ignoring the second part for the time being?

[restive raptor]

Oh i see, thank you so much

[opal crescent]

to complete a bit on opengang's answer https://arxiv.org/pdf/1301.1493, here's a paper by the maintainers of one of the fastest packages for graph isomorphism there is (nauty/Traces), where they explain their global approach + some specific techniques they used [this paper is cited in the Babai paper also]

[restive raptor]

thank you again

[obtuse spear]

yo can someone pls help with prop logic man

[north urchin]

send ill have a look and see if i can solve it

[obtuse spear]

It’s not a question

[north urchin]

ohh

whats up

[obtuse spear]

I have an exam on Friday I just need sum guidance on how to study

[north urchin]

just prop logic?

[obtuse spear]

Prop logic, Boolean algebra and first order logic

[north urchin]

i remember i kept asking chatgpt for short quizzes and was able ace it

also yt helped

alot

[obtuse spear]

What did you major in?

[north urchin]

im in cs

[obtuse spear]

same

[north urchin]

my discrete math final is coming i think im doomed 😭

[obtuse spear]

but the thing is my uni has its own book for prop logic

[north urchin]

oh

does it use diff notation?

[obtuse spear]

So finding vids is kinda hard

[obtuse spear]

What year are you in

[north urchin]

im still in first year

[obtuse spear]

I’m sorry but what are notations

[obtuse spear]

damn same

[north urchin]

basically symbols for operations

[obtuse spear]

nah the symbols r same

[north urchin]

whats diff abt the book then

[obtuse spear]

Holon I’ll send you the contents

[north urchin]

okayy

[obtuse spear]

Am I allowed to send pictures here?

[north urchin]

our book is weird asf too

[north urchin]

i think so

send in dm just to be safe ig

[obtuse spear]

ye here

[north urchin]

P=NP is crazy

we didnt cover that

[obtuse spear]

that’s not coming

[north urchin]

yea i agree the book isnt like ours

but i dont think ours is any better

[obtuse spear]

yea

[north urchin]

wait let me get my book

[obtuse spear]

i have last year's paper and the prof said the format would be pretty much the same so that would help a lot understanding it

ill send that holon

[polar crag]

Thanks, this helped me get it 🙂

[obtuse spear]

@north urchin heres the paper

its out of 80 so each question is worth 20

[north urchin]

i cant take a ss of the contents the quality sucks

[obtuse spear]

😭

Can I send a pdf here?

[north urchin]

i got a 0 on sets

[tall comet]

do you know how to construct truth tables?

[obtuse spear]

yea so

the first question i can solve except e

[north urchin]

idk abt e

[obtuse spear]

and i can do 2nd question a

[north urchin]

we didnt take that

we stopped before that

and started taking random stuff

i hate the way my instructor is handling the course

[obtuse spear]

i se e

[north urchin]

its all over the place

[obtuse spear]

saem

[tall comet]

you can do it simply by taking the conjunction of a proposition that is true only in every row

it is called disjunctive normal form

[obtuse spear]

so pAqAr?

[tall comet]

what is A?

[obtuse spear]

in my topic the topic is named as truth function

[obtuse spear]

conjunction sign

and

or wait p and q and negation r ?

i tried studying but idek man

[tall comet]

basically you want a formula that is only true in two cases; p F, q F, r T and when all false

[obtuse spear]

so 2nd and last row

[tall comet]

only the last two rows

[obtuse spear]

yea i dont get it man

so i have an exam on friday and the whole book is coming

nd i need help regarding how to finish the book

[tall comet]

in the truth table can you see that it is only true for the last two rows?

[obtuse spear]

yea

[tall comet]

so can you also see that if you make some formula that is true for one of them and another that is only true for the other then take their disjunctionit will be what you want?

disjunction i mean

disjunction means OR

[obtuse spear]

ive no clue bro i havent gotten to that topic yet

yea ik that much

should i send u the pdf of the book in ur dms man if u can help

[tall comet]

you should read the book

[obtuse spear]

the exam has 80% weigthage of my grdae

[tall comet]

if you have questions send them

[obtuse spear]

i tried its too confusin g

[tall comet]

but read the book first

[obtuse spear]

i did read the book

[tall comet]

you can send what you find confusing

[obtuse spear]

ill send in dms

alr?

[tall comet]

sure

[obtuse spear]

alr

[obtuse spear]

this is the book btw

[polar crag]

This

Basically for each of the three variables think about how you would chain them together

Don't forget the use of brackets either

[obtuse spear]

yea so (~p and ~q and r) V (~p and ~q and ~r)

~ is negation

[sharp rose]

[ \lnot ]

[vital dew]

qiuzlm

[sharp rose]

😎

[obtuse spear]

yea i dont have that sign on my keyboard so used the other

[oblique pelican]

$\neg$

[vital dew]

Dilly

[torn magnet]

guys discrete math or calculus for my second semester of freshman year

[still vortex]

calculus is solid, can't talk about discrete

[covert flare]

you need both

[oblique pelican]

I'd say calc since you'll probably need it more for upcoming classes. But yeah discrete math is also important. Both have some big foundational topics

[sharp rose]

What major

[wicked vapor]

hi, ive just had a lecture with induction hypothesis strengthening, my question might be irrelevant to the whole concept because i understand it, but what i do no understand is how 2-(1/2^k+1) becomes 2-(2/2^k+1) for context the question asked to prove the formula in the image using these steps

[oblique pelican]

$\frac{1}{2^k}=\frac{2}{2\cdot2^{k}}=\frac{2}{2^{k+1}}$

[vital dew]

Dilly

[wicked vapor]

yeah i figured its maybe * it by 2 but why exactly?

[lethal linden]

Because $$\frac{a}{a^n} = \frac{1}{a^{n-1}}$$ for any positive real number $a$ and any natural number $n$.

[vital dew]

Cufflink

[wicked vapor]

i dont get that, so we are trying to make the fraction a natural number?

[lethal linden]

Either you're confused about the basic rules for exponents or you're not recogizing those rules as being applicable here. There's nothing tricky going on. You have $$\frac{2^i}{2^j} = 2^i \cdot 2^{-j} = 2^{i-j} = \frac{1}{2^{j-i}}$$ Here you have $i=1$ and $j=k+1$.

[vital dew]

Cufflink

[lethal linden]

You can replace 2 with any positive real number a.

[wicked vapor]

maybe i am confused about that rule, where could i read up on this

i got into a bachelors cs degree at uni level with no previous math knowledge than highschool so theres my problem with these ideas

[lethal linden]

If you write out what $2^i$ means it will make sense. Do it first with specific numbers, like $$\frac{2^5}{2^3} = \frac{2 \cdot 2 \cdot 2 \cdot 2 \cdot 2}{2 \cdot 2 \cdot 2} = \frac{2 \cdot 2 \cdot 2}{2 \cdot 2 \cdot 2} \cdot 2 \cdot 2 = 2 \cdot 2 = 2^{2}$$

[vital dew]

Cufflink

[lethal linden]

There's nothing special about 2 there. It could be any real number.

And there's no problem if the power in the denominator is larger, either: $$\frac{2^3}{2^5} = \frac{2 \cdot 2 \cdot 2}{2 \cdot 2 \cdot 2 \cdot 2 \cdot 2} = \frac{1}{2^2}$$

[vital dew]

Cufflink

[wicked vapor]

That makes more sense ig thx

[lethal linden]

🤨

https://tenor.com/view/chuckles-im-in-danger-ralph-wiggum-the-simpsons-gif-14149962

[wicked vapor]

Yeah I don't understand nun

[clever sail]

[coral island]

Could someone explain the difference between if then, and if and only if

[sharp rose]

The first goes one way and the other goes both ways

[clever sail]

Let P and Q be statements.
P ==> Q is “if P then Q”
Q ==> P is “if Q then P”
P <==> Q is “P if and only if Q”
, i.e. (P ==> Q) ∧ (Q ==> P)

[coral island]

Maybe I’m not understanding this correctly, but isn’t P ==> Q only true if P and Q are both true or both false

So if they’re both true or both false, won’t they be the same backwards

[inland raft]

if P is false then the implication is always true

[wicked vapor]

Just have a look at truth tables

[weary tiger]

i have a trick to remember it which my professor taught me

umm...
Assume that
P = You study
Q = You Graduate

NOTE THE LOGIC:
UNDERSTAND THAT IF YOU STUDY THEN YOU'LL SURELY GRADUATE, IF YOU DON'T STUDY THEN YOU MAY OR MAY NOT GRADUATE.

Case 1:
if you study then you graduate
P is True, Q is True
cuz u study the u will surely graduate so True

Case 2:
If you don't study, you don't graduate
P is False, Q is False
cuz you don't study you'll not graduate => true hence P -> Q is true

Case 3:
If you don't study, you graduate
P is False, Q us True.
cuz you don't study still you may graduate somehow
so P-> Q is True

Case 4:
If you study, you don't graduate.
P is True, Q is False
this would never happen that your hard work would never pay off
So, P -> Q is False

✨️P <-> Q
take it as
( P -> Q ) And ( Q -> P )

Apply above logic, apply and operation and you are there.
Hope it helped

[wicked vapor]

guys 😭

[desert coyote]

Wtf lol

Lmao

[desert coyote]

You should identify the assumptions and conclusions in the proof and how they connect them together

[wicked vapor]

Yh ik but tf is this question 😂

[desert coyote]

I'm sure they had fun making it

[wicked vapor]

It's from an episode of rick and Morty where they show how this dildo looking thing is made too

That's why it's so out of place lmao

[weary tiger]

Mah Gawddd

So i hade my exam yesterday that of Dicrete Strcutures and syllabus was fineee

[coral island]

Thanks for this

[cerulean plover]

depends on what you're going into tbh. they're both very essential for a lot of fields

i'd say both

[oak drift]

(Regarding recursive functions) Is there a mistake in the powerpoint? It doesn't make sense to me

Why, if teacher says we start with 1 pair, then at zero months we have no rabbits?

I thought maybe she meant zero "older than 2 months" pair, but then why is there a pair at f(1) if they become mature after 2 months??

[cerulean plover]

maybe the problem is supposed to say "at 1 month, you will have a newborn pair of rabbits"?

so starting at 1 instead of starting at 0, kind of

[oak drift]

maybe yeah

but it makes it more confusing since, in most other examples I saw on the internet, the "base condition" is always f(0)

[amber arch]

Could anyone give me a hint for approaching this problem?

[cerulean plover]

a and d are obviously not vector subspaces, since they're not sets of vectors, right?

[little prism]

vectors are elements of a vector space

it doesnt have to mean column/row vector

[weary tiger]

I have my EggJam

After That I'll surely reply

I just love Graphs and Trees!
Dicrete Structures Yaaayy

[tight hound]

Both of them can be interpreted as sets of vectors

[obtuse spear]

my test is tommorow

and I am pretty fked

[weary tiger]

aigh this seems easy enough

can somone send a vid or explain the basics of this?

[novel ore]

by unique do they mean that if f and g are both isomorphisms then f(a) = g(a) for all a in A?

[novel ore]

if f(a) =/= g(a), then f(a) < g(a) WLOG, but I can't seem to derive a contradiction (tried applying inverses, etc.)

[lethal linden]

This isn't true for total orders in general. For example, the integers are totally ordered and x ↦ x + 1 is an order-preserving isomorphism. Indeed, x ↦ x + a is a distinct isomorphism for any integer a.

So will have to use the fact that they're well-orders.

[novel ore]

We defined well ordered to be every nonempty subset has a minimum

[lethal linden]

Indeed it does

[novel ore]

So we can consider the set f(a) g(a)

Which is non empty

If they’re distinct one is the min and hence one is less than the other

[lethal linden]

Yep. More generally, if a statement about well-orders has a counter example then it has a least counter example. That's often the crux of proving things about well-orders.

It can help to think of a concrete example and see what goes wrong there then try to generalize that to the abstract setting.

You don't need to do a proof by contradiction. Show the contrapositive: if f and g differ anywhere then at least one isn't an order-preserving isomorphism.

[novel ore]

oh wait my bad I thought you were saying that this didn't hold for well orders

I see

[lethal linden]

It does hold for well-orders, but not all total orders.

That tells you that if it's true then the well-ordered property will feature prominently in the proof.

[green hare]

Does anyone have some good resources for learning bigO. I have the idea but struggle with questions on how to prove it like the attached problem. like I just dont know where to start and seemingly everything I find online is just talking about applications of bigO

[lethal linden]

What definition are you using for O(h)?

[green hare]

Sorry, what do you mean

are you talking about the definiton of bigO?

[lethal linden]

What's your definition of Big-O? Here's one: We say that $f \in O(g)$ if $$\limsup_{x \to \infty} \frac{|f(x)|}{|g(x)|} < \infty$$

[green hare]

ohhhh

[vital dew]

Cufflink

[green hare]

both of these are in my course notes

[lethal linden]

The latter isn't a definition. It's technically stronger than the former. The latter is "Big Theta" or Big-Θ.

The definition of f ∈ Θ(g) is that f ∈ O(g) and g ∈ O(f)

Actually, never mind. I got my letters mixed up. Anyhow, it's still stronger.

[green hare]

So the limit one I attached isn't bigO?

[lethal linden]

Consider the function isPrime(n) which checks every number k from 2 up to n to see whether k divides n. (Yes, this could be improved.)

If n is even then it has to check one number, i.e.,2. And if n is prime then has to check n numbers.

[green hare]

okay, I'm still just alittle confused on the original question you had about my definiton of O(h)

[lethal linden]

It's ok. You answered it. You can use the latter definition. It makes it easier, even if it's technically stonger.

If f(x)/h(x) goes to L and g(x)/k(x) goes to R as x goes to infinity

[green hare]

but could I still use it in the problem/proof if I have no way to tell what the limit would be. or does somehow knowing that since O(h) exists that is enough

[lethal linden]

The definition says it's some finite number.

The basic fact is that: $$\left|f(x) + g(x)\right| \le \left|\max{f(x), g(x)} + \max{f(x), g(x)}\right| \le 2 \cdot \left|\max{f(x), g(x)}\right|$$

[vital dew]

Cufflink

[green hare]

okay thank you

I think I see now

do you happen to know any good videos or resources for this kind of stuff, I'm trying to prep for my final on tuesday

[lethal linden]

TBH the Wikipedia page has a very nice table: https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann–Landau_notations

Proving things about Big-O, generically, boils down to calculus.

[green hare]

what does the sup in lim(sup) mean? sorry this is the first time ive seen it

[lethal linden]

Think of something like $1 + \sin(x)$, which oscillates between $0$ and $2$. The limit $$\lim_{x \to \infty} \frac{\sin(x)}{1}$$ doesn't exist, right?

[vital dew]

Cufflink

[lethal linden]

But it's certainly true that sin(x) is eventually bounded above by some constant multiple of 1.

The limsup is whatever it's eventually bounded above by and it always exists.

The liminf is whatever it's eventually bounded below by and it always exists.

The lim might not exist at all.

The limit exists if and only if the limsup and liminf are equal (allowing $\infty$ to be a possible value for the limit).

\\

So your first definition, quite literally, is saying $f \in O(g)$ if $$\limsup_{x \to \infty} \frac{|f(x)|}{|g(x)|} < \infty$$ Your second definition is saying something stronger.

[vital dew]

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

[green hare]

ohhhhh okay that makes sense

[lethal linden]

Some images:

[green hare]

yeah I've just never seen that before

thanks

[lethal linden]

So the time complexity of an algorithm like isPrime(n) like I described is eventually bounded above by some constant multiple of n, but it's eventually bounded below by some constant multiple of 1.

Why? Because I can always find a still-larger input that checks n numbers (the next prime) and a still-larger number that checks exactly 1 number (the next even number).

[fossil venture]

What is the recurrence relation for the number of n-digit ternary sequences with no consecutive 1 or 2? https://math.stackexchange.com/questions/338417/recurrence-relation-for-the-number-of-n-digit-ternary-sequences-with-no-consec
Why does a_n = a_n-1 + 4a_n-2 not work?
my logic is:
with 0, any number can go before so a_n-1
with 1, you can only have 0 and 2 that leaves you with (n-2) digits so 2a_n-2
same with 2 as with 1.

[mental plaza]

probability kicking my ass

[vestal bronze]

not every sequence from a(n−2) would allow adding 21

[vestal bronze]

i just found a short proof, i think it's not anywhere in the answers

[fossil venture]

So how would I not count those? Subtract a_n-3?

[vestal bronze]

i don't know

you just add a digit that's 1 more than the last or a digit that's one less, wrapping around

and then only 00 is missing

[fossil venture]

wdym by wrapping around?

[vestal bronze]

i mean 2 is one less than 0

or in other words the last two digit are always consecutive

nvm that's not clear at all

[fossil venture]

So how would you count it?
if 0 then you would add 2 or 1 infront
if 1 then you would add 0 or 2
if 2 then you would add 1 or 0
then I'm confused on how you write out the recurrence relation? would it be a_n-1 or a_n-2 because you need to know what the previous digit is?

[vestal bronze]

it's this one

i'm adding digits on the right side

[fossil venture]

i'm still confused on how you would do it.

[vestal bronze]

like you just said

[fossil venture]

for 0 it is 3a_n-1?

[vestal bronze]

i can add the +1 digit, and i can add the −1

they don't intersect

and it covers everything, except 00

00 is a_n−2

that could be what that answer actually meant

it just says "Add up" i have no idea what it means

[fossil venture]

why is 00 a_n-2? Is it because you are forcing 2 numbers to be 0 and the rest n-2 of them can be anything that is valid?

[vestal bronze]

yes

if you try to fix your idea, you end up with the "infinite" version probably

[fresh hull]

1. Eulerian cycle in Km,n
   Both m and n must be even

2. Hamiltonian cycle in Km,n
   Both m >= 2 and n >= 2

are these the correct conditions for a eulerian and hamiltonian cycle in Km,n?

[weary tiger]

for Eulerian Cycle it's correct!

Well true for Hamiltonian Cycle as well

[fresh hull]

Okay cool thanks

[fossil venture]

This is where I am confused. For problems that are have a forbidden subsequence like sequence that doesn't contain "013" you have to subtract? a_n = a_n-1 - a_n-3(fixing 013 and the other n-3-digits that allow this? But if it's consecutive like consecutive 4s then you can't subtract?

[fossil venture]

I thought you also need m = n

[weary tiger]

umm it is Complete Bipartite graph so no need to check whether m = n 🙂

[fossil venture]

i think the problem comes from alternating between each side.

[weary tiger]

lemme visulaize 🥹

[weary tiger]

thats true it will be Hamiltonian Path and Not Cycle

[weary tiger]

Please correct it that for Hamiltonian Cycle M = N >=2

[fresh hull]

so both equal and >= 2? cool

thanks

[weary tiger]

Assume that universe of discourse consists of all the adults 18 or above living in Patiala, India.

All credit union employees must know C++. All credit union employees who write loan applications must know Excel. Aman works for credit union but he doesn't know Excel. Akshay knows Excel but doesn't know C++. Therefore, Aman doesn't write loan applications and Akshay doesn't work for credit union.

Write arguments in symbolic form and tell if the conclusions given are true or false!

[lethal linden]

Start giving names to sets, like:

D = {adults 18 or above living in Patiala, India}
U = {p ∈ D : p works at a credit union}
C = {p ∈ D : p knows C++}
E = {p ∈ D : p knows Excel}
L = {p ∈ D : p writes loan applications}

[dire schooner]

guys im final tomorrow 8:30 am

kill me

[signal sphinx]

If I have a bipartite graph with two parts A and B, the degree sum of verticies in A is x, and the degree sum of verticies in B is y, how do I tell if this is a valid graph or not?

[weary tiger]

ummm see;

let us say sum of the degrees in part A is X the sum of the degrees in part B will also be X
and number of edges will be X+X = 2*E (E-> number of edges)
=> X

so we can put the condition there that it necessary to that the sum of degree of vertices in part A must be Equal to Part B

Also this is not a sufficient condition but necessary !

[burnt nebula]

any discrete mathers available to help me

[last flicker]

don't ask to ask, just ask

[left shadow]

what are the odds of drawing a royal flush in poker? I see conflicting answers about this online

[burnt nebula]

Is this 120?

[tight hound]

Yes (if they mean induced subgraphs). You just need to count the number of ways to choose 3 vertices.

[vestal bronze]

it's probably 5-card vs. holdem

what this says

0.00308% that only you get royal flush and 0.00015% that everyone gets it

[arctic valve]

Hello I am learning the multiplication principle along with permutations and combinations, how would I know what the questions means if they ask “with replacement" and "without replacement" ?

[marble flint]

I think "without replacement" means that, once a permutation is used/account for, it is no longer possible to use or choose that permutation again. When it is "with replacement," none of the permutations are removed as possibilities once found or chosen.

Hope that was an intelligible explanation.

[lethal linden]

You have a box full of balls. You pick them at random.

With replacement means after you randomly pick you out that ball back in the box before you pick again, i.e., you replace the ball.

Without replacement means you toss the ball away before you pick again, i.e., you don't replace the ball.

[arctic valve]

So without replacement would be more associated with the multiplication principle and with replacement would be permutations and combinations?

[marble flint]

With and without replacement both have to do with permutations. There are different formulas for finding the number of permutations with and without replacement.

[arctic valve]

Like if I had to choose 4 letters at random with replacement, it would be 26^4, while without replacement is 26•25•24•23

[north urchin]

anyone know where i can learn discrete math topics related to algorithms (both iterative and recursive), counting and induction?

both mathematical and strong induction

im screwed

also proving correctness for algorithms and finding their time complexity and running time

and using a recursive tree

[marble flint]

Correct.

[marble flint]

https://www.khanacademy.org/computing/computer-science/algorithms#recursive-algorithms

[marble flint]

https://www.mathsisfun.com/algebra/mathematical-induction.html

[north urchin]

tysm youre a lifesaver

[marble flint]

No problem. I’ll circle back and share more later.

[north urchin]

deal

that would help alot

[rugged dock]

yes

a similar problem is the number of rearrangements of a given string, ignoring spaces

since we might introduce repeated chars, we have to divide by the num ways we can arrange those

[noble inlet]

could anybody solve this pigeonhole problem "show that if any 30 people are selected, then we may choose a subset of 5 so that all 5 were born"

[oblique pelican]

I feel like theres more to the problem than that

"all 5 were born"

[noble inlet]

i felt that too

[noble inlet]

yea doesnt make sense

[oblique pelican]

I mean... all 30 of them were born so proof complete

choose 5 of them

[neat oasis]

Is there any graph where if you remove an edge it removes two or more cycles? Or is the max always one

Well I think I formulated my question wrongly

What I mean is

if you have a graph which is basically two or more cycles, if by removing an edge you can make it acyclic

[sharp rose]

Maybe this?

[neat oasis]

which single edge can you remove that makes it acyclic?

[sharp rose]

Remove diagonal edge

[neat oasis]

the entire exterior is still a cycle

and the interior rectangle is also a cycle

[sharp rose]

Oh I was thinking about Hamiltonian

my bad

[neat oasis]

Dw

[sharp rose]

I dont think you can destroy two cycles by removing one edge

In that case

[neat oasis]

you can definitely destroy two cycles by removing an edge but I don't think you can make it acyclic

it should be like

Btw the graph is undirected and simple

Two cycles that depend on one same edge

but then I'm pretty sure this would form an external third cycle

and if you try to break that one, one of the two cycles is still intact

Already solved

[odd heart]

Yeah, it's this. If two cycles share an edge, then there exists a third cycle which does not include that edge (so removing the edge won't affect that cycle)

[grand marten]

test question i just had: prove that if a graph at most 34 odd cycles, it is 6-colorable.

what results can i use to approach this? the only upper bound on chromatic number i know of is brookes

[sharp rose]

just say all graphs are five colorable then add one extra color 😎

nvm that's for planar

sorry guys I should stop yapping about graph theory 😔

[novel ore]

If I'm assuming that A > B and I deduce that A >= B, is that a contradiction

[lethal linden]

Interesting. My first thoughts were Brooks theorem and the theorem about colorings and a cyclic orientations. Gallai’s theorem? I forget.

One thing to think about is removing all the odd cycles, which leaves you with a bipartite and therefore a 2-colorable graph. So if you can prove that the subgraph consisting of just the odd cycles is 4-colorable then you’re done.

[lethal linden]

No, because A>B already implies A>=B

[tight hound]

No

[novel ore]

oh right lol

[lethal linden]

Like, P implies P or Q for any Q

[novel ore]

roight htanks

[grand marten]

how do you remove all odd cycles? consider k5. removing all odd cycles would remove the entire k5, but that includes even cycles, no?

maybe there's a planarity argument to be made? G = B U P where B is bipartite and P is planar

[lethal linden]

Oh, yes. Well...let's think about what's going on there.

No two odd cycles are disjoint. That means if you remove any odd cycle, you remove all odd cycles and what remains is bipartite.

Any graph with that property is therefore 5-colorable.

[grand marten]

No two odd cycles are disjoint
how so? consider two triangles joined by one vertex

[lethal linden]

Sorry, I mean any two have a vertex in common, not that they share an edge.

[grand marten]

why is that a condition? there's no limit on even cycles, so odd cycles may share arbitary edges, so long the total is less than 34

i'm trying to figure out why 34 is important here. i assume something to do with cliques. k5 has 22 odd cycles, k6 has more than 34

[true venture]

Say I start with an unlabeled k-regular graph. Then how many non isomorphic graphs can I reach by removing vertices from that graph? What is this problem called?

[waxen mist]

I need some parameter for amplitude of b(x) regardless of b(0) and c(0).

(using only basic operators)

[true venture]

The amplitude seems to be b(0), not sure how you would define it without b(0)?

[waxen mist]

I can change the amplitude if I add +a.

But b(0) still affects the amplitude. I want to get rid of that effect somehow.

[true venture]

Idk, about adding more parameters, but in your first plot. b(0) is your amplitude.

So do you want the slider a to directly set the amplitude?

[waxen mist]

yes

i want b(0) to NOT affect amplitude if possible

[true venture]

I think it would be helpful to first get rid of c(x) and just have b(x).

But from the definition of b(x) you have b(0) is the amplitude.

[waxen mist]

how to just get b(x)

[true venture]

You can write b(x) as b(x) = b(x-1) - floor(C + Sum_{i=1..x-1} b(i)/100)

Where C is c(0) a constant, this makes it easier to see what is happening as you iterate through x

[waxen mist]

I can't get it to graph

[true venture]

The /100 is outside the sum

Floor {(C + Sum)/100}

[true venture]

I've not used desmose

The i=1 is off maybe

But this should just be equal to what you had, you start with b(0) and begin subtracting terms until the running sum also becomes negative then you are adding to the next b term.

[waxen mist]

oh wait i think i need a list to graph it one sec

👍

[true venture]

Can you make the slider b(0) that should adjust the amplitude

[waxen mist]

it does

[true venture]

And it can help to work out some terms by hand to get a feel of how each initial condition effects the function

[waxen mist]

is it possible to change the amplitude not based on the inital condition?

like an increasing amplitude over time

[true venture]

Probably I'm not sure how

Are there non recursive ways to give a sine function ?

This being a recursive function makes it confusing

[waxen mist]

has to be discrete, and only use basic operators, but can have multiple variables

[true venture]

So as n grows you want the amplitude to grow....

[waxen mist]

i want a parameter that can adjust amplitude regardless of b(0)

[true venture]

Is this an assignment, I don't get what you mean by that?

[waxen mist]

like if b(0) was randomized

[true venture]

Why

[waxen mist]

i want amp despite previous points

[true venture]

Yea idk, my thought would be to look up other discrete approximations of sine waves that are not recursive. Those will probably be easier to work with

[waxen mist]

i was hoping something like this.
where the amplitude would tend towards a parameter. despite the inital value big

[true venture]

Oh and you want the parameter to be the amplitude it tends to

[waxen mist]

yes

[true venture]

Dang Idk

[waxen mist]

i legit dont know what to google to find info

[true venture]

Try to find out what the above curve is called

Maybe someone else knows

Damped sine wave

Try that

[noble inlet]

could someone share their notes for Chinese remainder theorem having a hard time understanding it

[brave rock]

Maybe instead you could talk about what is confusing you about it and someone could explain that specifically. That way, people can adapt their explanations to what you already know.

[coral island]

Could someone explain the difference between weak and strong mathematical induction

They kinda look the same to me

[waxen mist]

More base cases I think.

[inland zenith]

Not necessarily, nothing about the structure of the proof has to change necessarily, strong induction just means that you have a stronger induction hypothesis. Normally if you want to prove some property of natural numbers for example you prove that it holds for 0 or 1 or whatever, then assuming it holds for k you show it holds for k+1. Using strong induction, the induction hypothesis says that it holds for all natural numbers less than or equal to k instead. Imagine if you could show that some property holds of k+1 assuming that it holds of k but simultaneously assuming that it doesn't hold of k-1, have you then shown that it holds of all natural numbers? If it didn't hold for all previous values less than k too then being able to prove the statement by induction would be a serious problem. You only need more than one base case if you are inducting over a structure that has more than one "lowest level" or in the case of natural numbers if you are proving a statement that is recursive and depends on more than one previous term (e.g. a recurrence relation where the k'th term is defined in terms of k-1 previous terms). only proving that it holds of the first term would either give you an induction hypothesis that's too weak or else you might be able to prove something that's false

[brave rock]

They are logically equivalent and the equivalence is relatively clear, yes.

[true venture]

Say I start with an unlabeled k-regular graph. Then how many non isomorphic graphs can I reach by removing vertices from that graph? What is this problem called?

[true venture]

Is this just the number of subgraphs?

[agile magnet]

No, you should be able to easily think of example graphs where removing different vertices and edges can yield isomorphic subgraphs

[true venture]

Ok, I see that

[agile magnet]

I don't know if this number has a name but upon some quick research it seems like this number (unsurprisingly) is quite hard to compute in general

[true venture]

Nooo

[agile magnet]

For special classes of graphs it would be simple

But in general, very hard

[true venture]

I wanted to know this number for the graphs with vertices being subsets of size 2 of [n] with edges if two subsets have non empty intersection.

Not sure if these graphs have a name

Looking at all subgraphs may still be useful, but I'm also interested in how many elements of [n] are covered by the vertices of each subgraph

[true venture]

For graphs with vertices being all subsets of [n] of size k <=n, and edges if two subsets have non empty intersection, do these graphs have a name. They are regular

[agile magnet]

I'm not familiar with any name

But graph theory is not my strong suit

[true venture]

For [4] and k =2

[agile magnet]

Actually it's strongly regular I bet

If that's of any interest

[true venture]

Me neither, I'll look into the strongly regular property

[raven python]

@true venture https://link.springer.com/article/10.1007/BF02773686

[cursive nymph]

we can't just define it like this, right? (this is baby Jeck)

under the hood it takes intersection of all inductive sets

but that might not be a set, right?

seems like constructing N := {S' ⊆ S | S' is inductive}, where S is some inductive set, guaranteed to exist by the Axiom of Infinity, is the way to go, right?

oh, we can consider that as x in S AND x in every other inductive set

so that it uses axiom of separation

[random sparrow]

Can I get some help

[haughty garden]

Try thinking about what it would look like when they do attack each other. You’ll basically either form a 2 x 3 board or a 3 x 2 board

So now you basically want to count the number of ways you can form either a 2 x 3 board or a 3 x 2 board from a k x k board

[fossil venture]

How do I find the recurrence relation?

[true venture]

You can think of all ternary words with length n and first part 0,1, or 2. Starting with w(0) = 1 and w(1) = 3. How can you make the words of length 2 in terms of the words of length 1?

Assume what you want is (0,1,2), (00, 01, 02, 10, 11,...), ...

[fossil venture]

You can put 0, 1, or 2 in front of those numbers

but you can't have 21 or 012 so I would consider the complement

[grand marten]

@lethal linden a friend figured out solution to the 34 odd cycle problem if you are curious.
suppose, for contradiction, G has chromatic color at least 7. consider color classes 3 at a time. there are 7 choose 3 = 35 ways to choose a set to consider. each subgraph induced from 3 color classes must have an odd cycle since it is not bipartite. therefore, a chromatic color at least 7 implies at least 35 odd cycles. this is the contrapositive to the original statement.

i believe there's a bit of nuance in that odd cycles between induced subgraphs are currently assumed to be unique, but that should be pretty easy to prove.

[fossil venture]

To get a length of n from n-1, I can put a 0, 1, or 2.
If I put 0, I can't have 012, so I consider the previous possible ways to get n-1 character subtracted from n-3 assuming that I have 12 before putting the 0?

[true venture]

Yea, except like you said ones that will create a forbidden pattern

[lethal linden]

Neat! I had realized the contrapositive was more suggestive and asked another server about it, but never dug into it more (or got an answer there).

It was definitely trickier than I thought at first glance haha.

[true venture]

What inwas thinking is let w(n) be the number of ternary words of length n avoiding the given patterns. Then w(n) = w_0(n) + w_1(n) + w_2(n), where w_0(n) is the number of words of length n with first letter 0 ect.

[fossil venture]

I tried doing but I think the answer involves using a subtraction somewhere.

[true venture]

Find w_i(n) interms of the others, will give you a system of equations for the a recurrence

Yea maybe there is a better way

[grand marten]

for sure. it's a pretty clever solution.

[true venture]

For that way first find a recurrence for all ternary words then find a recurrence for words matching at least one of those patterns and subtract

[lethal linden]

But in my initial digging I learned a new set of theorems which are pretty cool, owing to Gyarfas: https://users.renyi.hu/~gyarfas/Cikkek/57_Gyarfas_GraphsWithKOddCycleLengths.pdf

The theorems in there revolve around the number of distinct lengths of odd cycles. In particular, if a graph has k different odd cycle lengths then the chromatic number is less than or equal to 2k+2

[fossil venture]

for this, is it:
w0(n) = w0(n-1) + w1(n-1) + w2(n-1) - w2(n-2)
w1(n) = w0(n-1) + w1(n-1) + w2(n-1)
w2(n) = w0(n-1) + w2(n-1)?

[fossil venture]

I'm not sure how to use subtraction here.
if it's 0 then I have (an-1 - an-3) since 012 is forbidden
if it's 1 then I have (an-1)
if it's 2 then I have (an-1 - an-2) since I subtract the fordden 21...(n-2) characters?

[true venture]

For w_0(n) you can add zero to words unless they have prefix 12.

[fossil venture]

How do I check for that?

[true venture]

I'm assuming I'm adding letter to the left of a word

You only need to think which words when you add a 0 to the front will match one of the forbidden patterns

[fossil venture]

that's why i'm subtracting by w2(n-2)

or is that wrong

[true venture]

Idk I'm trying to think it through

We want to subtract words that have first letters 12

Those letters are fixed, what's left is a valid word either with first part 0 or 2 since we also avoid 21

Or the empty word for just 12 itself

w_0(n) = w_0(n-1) + w_2(n-1) + w_1(n-1) - w_0(n-3) - w_2(n-3)

w_1(n) is easy since adding 1 doesn't create any patterns. And w_2(n) you cannot have words with first letter 1

Think that is correct

[fossil venture]

Why are you subtracting by w0(n-3) and w2(n-3)?

[true venture]

Those represent words with first two letters 12

[fossil venture]

I'm confused how does that represent first two letter 12?

[true venture]

You fix the first two letters, then what can come after?

Or rather what kind of word can come after the 12: (12)(word)

[fossil venture]

why is 12(0...) a problem?

[fossil venture]

so if I fix 12 then I have n-3 words left right?

[true venture]

Yes

[true venture]

Because this is within w_0(n) and adding 0 to 120 gives 0120

[true venture]

Yes

[fossil venture]

What about if you have 1 before 12, like 0121

or is that not counted by w2(n-1) already excluded that option?

[true venture]

21 is a forbidden pattern

So it's assumed that w1(n-1) does not include any words with 21 so we don't need to subtract them

[fossil venture]

why w1(n-1)? 1 is fine with anything number

[true venture]

That what we are subtracting from

w1(n-1) can only add a 0 if the word does not start with 12

w1(n-1) includes words that do start with 12, so those are what we are subtracting

Like the word 1201 is fine by itself but adding 0 gives 01201 which is a pattern to avoid

[fossil venture]

since w2(n-2) doesn't allow to number that start with 1 before

so what if I also included the sequence "0121" then it wouldn't change anything because we are already accounting for this case.

[true venture]

Because we technically haven't added the 0 yet we don't want to count it

[fossil venture]

but if we also included the sequence "011", then we would to fix 11 and consider all valid ways that form 11?
so the new w0(n) = w0(n-1) + w2(n-1) + w1(n-1) - w1(n-3) - 2w0(n-3) - 2w2(n-3)
since 111, 110, 112 are valid?

[true venture]

011 doesn't match any of the patterns we're trying to avoid

Idk why would you include 011

[fossil venture]

I'm just trying to understand your approach. Am I right or wrong?

[true venture]

What does include 011 mean? 011 is counted under w1(n-1)

[fossil venture]

oh I meant as a forbidden sequence

so "011" is also forbidden

[true venture]

Oh that may change many things ...

[true venture]

Yea, I think that's right. You would subtract all words with first letters 11

[fossil venture]

but what if no "22" also.

[fossil venture]

so the recurrences for my original problem are:
w0(n) = w0(n-1) + w2(n-1) + w1(n-2) - w2(n-3) - w0(n-3)
w1(n) = w0(n-1) + w1(n-1) + w2(n-1)
w2(n) = w0(n-1) + w2(n-1)?

[random sparrow]

there is only 4 squares that they can sit on

[haughty garden]

i'm assuming that you're only placing knights

and this makes sense for the outputs given

[fossil venture]

Oh damn I can't seem to get a way to simplify the recurrences. I know an = w0(n) + w1(n) + w2(n). Do I just keep going until I reach the base?

[haughty garden]

yeah so given a 2x3 board, there are two combinations for which a pair of knights attack each other

you place them at (1, 4) or (2, 3)

[true venture]

Idk how much it can be simplified. Just add the three cases

[haughty garden]

and by symmetry, there are two combinations for which a pair of knights attack each other given a 3x2 board

[true venture]

Is what I was thinking and combine like terms

[random sparrow]

I dont want to clutter the chat, but let say we have two knights, lets call them k1, k2,

if k1 sits on 1 then k2 sits on 4

if k2 sits on 1 then k1 sits on 4

if k1 sits on 2 then k2 sits on 3

if k2 sits on 2 then k1 sits on 3

[random sparrow]

how to extrapolate to a nxn board btw

[haughty garden]

the assumption here is that two knights are identical so you just obtain two unique combinations

but it's not hard to extend it so that you lift the assumption

[haughty garden]

so the idea is that you basically want to find the number of ways for which you can fit a 2x3 board inside of an nxn board

and this can be done purely combinatorially

there are n rows, so there are (n - 1) ways of selecting two consecutive rows. Once you choose the two rows, you choose the columns; there are n columns so there are (n - 2) ways of selecting three consecutive columns

this gives you (n - 1)(n - 2) total 2x3 boards that you can fit inside of an nxn board. Each such board gives you two ways of placing knights such that they attack each other

a similar argument can be made for the 3x2 board case; the question now is to determine whether we've overcounted by counting these boards separately (convince yourself that we don't)

[fossil venture]

I checked my professor's answers but I can't seem to get any -an terms the w0, w1, w2 equations, it's always just been addition.

[true venture]

That's much simpler lel

[haughty garden]

it's basically inclusion-exclusion principle

you naively extend any (n - 1) valid string by some character to form a string of length n

[true venture]

Even with w1(1) = 1? I'd hope what ever I was doing would still give the same terms

[haughty garden]

the only way you can get invalid strings is if you get something like

__________012
___________21

so each valid string of length (n - 3) can be "invalidated" by naively appending the string 012; similarly, each valid string of length (n - 2) can be "invalidated" by naively appending the string 21

[random sparrow]

there are n rows so there are n-1 ways of selecting two consecutive rows? why?

[haughty garden]

you mean n rows right

[random sparrow]

yeah

[haughty garden]

you can think of it as you’re keeping track of where the bottom row is

you can’t have the bottom row as the first row

so your set of potential bottom rows are rows 2, …, n

[random sparrow]

yeah

[haughty garden]

once you pick the bottom row, the top row is automatically picked

so there are (n - 1) total ways

[random sparrow]

how do we count the number of squares

on a nxn

[haughty garden]

Choose a row, choose a column

[random sparrow]

hmm wdym for example 100x100

[haughty garden]

there are 100 rows and you choose 1 of them

there are 100 columns and you choose 1 of them

each selection of (row, column) gives you a unique square

so there are, in general, n^2 many possible squares on an nxn board

[random sparrow]

n^2 - (n-1)(n-2)

something like that? sorry I dont get the combinatoric aspect, is hard

[haughty garden]

not quite

so (n - 1)(n - 2) is the number of 2x3 (or 3x2) boards you can fit on an nxn board

[random sparrow]

right

[haughty garden]

what you want to think about is the number of ways for which two knights can attack each other

this is not quite (n - 1)(n - 2)

remember that each 2x3 board gives you two unique ways of placing a pair of knights so that they do attack each other

and similarly, each 3x2 board gives you two unique ways of placing a pair of knights so that they do attack each other

so how many different ways can you place a pair of knights so that they attack each other

[random sparrow]

like for example for a 2x2 chess boards, there are multiple ways to place two knights but they never attack each other

[haughty garden]

yah

in fact, any combination of pair will give you a valid pair

[random sparrow]

wait but why are we only considering 3x2 and 2x3 situations

what if the board is squared I dont get it

[haughty garden]

the only situation where you can get two knights attacking each other is on opposite corners of a 2x3 or 3x2 board

[random sparrow]

like in the case of 2x3 and 3x2 boards, is only two ways

we need to count the number of 2x3 boards in a nxn and multiply that by 2?

[haughty garden]

yup!

[random sparrow]

I dont get it tbh

[haughty garden]

the reason we do this is because we know that when two knights attack each other, they can only do so in an L shape

and this L shape is 2 units in one direction and 3 units in another direction

this gives you that 2x3 or 3x2 subboard

so we want to figure out how many ways we can get a 2x3 subboard inside of an nxn board

[random sparrow]

how do I do I figure the number of 2x3 sub boards in a nxn

[haughty garden]

^

[north pilot]

and an ordering. a photograph of C is a graph

yeah, I don't know

[solemn badge]

i just found this discord and my discrete exam is at 8:30 am i'm so cooked

is there like tutoring in here

[true venture]

The C graph?

[north pilot]

i'm stuck on this problem i know to use burnside's lemma but it feels so daunting here

Exercise 12. Consider the colorings of vertices of a regular dodecahedron with 8 colors such that a face cannot have more than 3 vertices of the same color.

(a) How many such colorings exist?

(b) Consider two colorings equivalent if one can be obtained from the other through an action of an element of the group of symmetries of a regular dodecahedron. How many unique colorings exist?

(Hint: This group is isomorphic to the alternating group on 5 elements)

(also posted to #groups-rings-fields , wasnt sure if here is also okay)

[timber leaf]

Can I receive some help for this. I began it but I am unsure how to calculate the cost of an edge, would it be multiplication of d x p(v_i) ?

[fossil venture]

are you refilling at every gas station?

[timber leaf]

I am not sure, I believe so because in the dijkstra's algorithm all nodes have to be visited

so since nodes represent gas stations I think it would be yes

[fossil venture]

you should ask your instructor. And how much are you refilling at each gas station?

[timber leaf]

I think they will likely say that that is for me to figure out

I think perhaps it is until V_n has been reached

[fossil venture]

Then I don't why you won't just make the price the edge weight.

[timber leaf]

This is what I ended up doing. I am not sure about it though.

The edge has to be related to the distance I think. since that is defined in the question

I set the edge weight to the distance x price

to find out the cost for that distance but idk

[solemn badge]

ok i am a bit confused on this question. i know how to show that it is an equivalence relation (i need to show it is reflexive, symmetric, and transitive, right?) but i don't know how to complete the second part of the question referring to prime factorization.

[bleak vigil]

i need to show it is reflexive, symmetric, and transitive, right?
yes, that's correct

i don't know how to complete the second part of the question referring to prime factorizatio
the equivalence class [n] consists of all positive integers m such that nm is a perfect square.
so, if n = p_1^{e_1} \cdots p_n^{e_n}, what do you know about m? ||Hint: what does the prime factorization of m need to be like in order for nm to be a perfect square?||

[solemn badge]

the exponents of m need to balance out the exponents of n in order to be a perf sq? idk

[bleak vigil]

yeah exactly, namely, the exponents need to be... ?

[solemn badge]

uhh...

e1 + 1 or...uhhh

[bleak vigil]

does m in [n] have the same prime factors as n?

[solemn badge]

no i think

it's like q_1^something

[bleak vigil]

yeah exactly it need not have the same prime factors

but you do know

[solemn badge]

ok why

[bleak vigil]

if p_1^{e_1} is a prime factor of n and e_1 is odd, then m needs to have at least one factor of p_1

[solemn badge]

ah ok

so what would m look like then

[bleak vigil]

take for example:
n = 2^2 * 5^2
m = 9^2
we know m is in [n] because mn=2^2*5^2*9^2 = (2*5*9)^2

maybe try an example where n has a prime factor with an odd exponent

[solemn badge]

ok

does the exp for n need to be greater than 1 or can i use 1

just as an easier example

[bleak vigil]

however you want

[solemn badge]

ok

so n = 2^1 * 5^1

do n and m's exponents always need to have the same parity ig is what i am asking

[bleak vigil]

well

the goal is that when you multiply them

the exponents of the prime factors of nm have odd or even parity?

[solemn badge]

even

right...?

[bleak vigil]

yeah exactly

[solemn badge]

ok

[bleak vigil]

so if n = p_1^{e_1} \cdots p_n^{e_n}, you can desrcibe exactly which integers multiply with n to beocme a square

[solemn badge]

i can? Ok I think I'm just over complicating the answer then

[north pilot]

i'm stuck on this counting problem on my discrete math hw, i need to find the number of ways to color the interior edges (none on the boundary) such that around each interior vertex there's either 2 blue and 4 red edges or 2 red and 4 blue edges

[north pilot]

i did it for a few smaller cases ill send that

i can find my work if needed

the 30 case it's just 6 choose 2

*2

for 450 it's 5 choose 1 * 5 choose 1 if both vertices are majority blue and the center edge is red, 5 choose 2 * 5 choose 2 if the center edge isn't red (still both majority blue), then if one vertex is majority blue and 1 is majority red its 5 choose 2 * 5 choose 1 if the center edge is red, and 5 choose 1 5 choose 2 if the center edge isn't red, for 225 total, but we multiply by 2 for the symmetries so it's 450

for the 3374 case consider ordered 6-tuples $(K_1,K_2,K_3,c_1,c_2,c_3)$ where $K_n$ is 0 when the vertex labeled $K_n$ has majority blue edges around it and 1 for majority red and $c_n$ is 0 when the edge opposite the vertex labeled $K_n$ is blue and 1 when it's red

[vital dew]

Emma

[north pilot]

(sending diagram 1 sec)

Consider actions of the group $\mathbb{Z}_2\times D_3$ on the set of these 64 6-tuples where $(0,x\in D_3)$ just moves the graph around like it would and $(1,e)\cdot(K_1,K_2,K_3,c_1,c_2,c_3)=(1-K_1,1-K_2,1-K_3,1-c_1,1-c_2,1-c_3)$

[vital dew]

Emma

[north pilot]

then we have 10 orbits and for each we can pick a representative 6-tuple and count the number of colorings that it would result in, then multiply by the size of the orbit, and sum all of these

and that gives us 3374

im not sure what to do in the next higher case with 4 vertices though

i meant H not K

@low hare do you know what i should do

sorry that took so long

some of these orbits give the same count so i think there might be a different group i can use thatd make it less orbits but this was the intuitive one

[fierce venture]

Emma can u do with 1 point and red and blue pencil cuz i confused what was u asking

[north pilot]

what

oh

i dont have red or blue pencil

i'll do solid/dashed line

[fierce venture]

Ok

[north pilot]

examples of valid vs invalid colorings of the edges around a vertex

[fierce venture]

Thx

[north pilot]

also turquoise if you say use a generating function i have not learned that so i probably wont be able to because i dont really know what they are

but i can try to learn

[north pilot]

that is not a valid one

because they're all red

you can only have 4 red and 2 blue or 4 blue and 2 red around a vertex

[fierce venture]

I want ti say its ur shape u need to think of

[north pilot]

but those are the edges we're considering

yeah

thats the shape im thinking of

[fierce venture]

Hmmm

[low hare]

Yeah I'm not sure. I can see how complex this gets after you solve the permutation for one hexagon

[north pilot]

yeah i had to move away from trying to just do one hexagon at a time and use the symmetries thing instead

considering assignments of the central triangle and what the majority around each vertex is

the 64 cases of that have 10 orbits under the group action (maybe can optimize this to 6 if i find a better group but i cant quite express one of the symmetries as an element of some other group in a nice way)

and you can count for each orbit instead of each of the 64 cases

theres no book just the professor's lectures

she said we dont need generating functions for this class though

and we learn that in the graduate combinatorics

[fierce venture]

That was kinda brilliant q of discrete math

[low hare]

Emma I'm afraid I won't be able to help you. But one thing I would suggest is for you to repost your question in a better prepared manner, because it was too long after reading the prompt you gave that I finally understood. Also yes a little diagram with true-false cases. (so that others who read this won't have to scroll and lose the train of thought!)

[north pilot]

i would go to office hours but they're different depending on your grade in the class so the ones for my grade are during my other class that i cant skip

[fierce venture]

Yellow one is ez but red one need to think

[north pilot]

this isnt valid

on the top left vertex you have 3 yellow and 3 red

[low hare]

Not only ^, but the question asks for EVERY POSSIBLE way

[north pilot]

are any of you good at logic? im stuck on a problem about translating into predicate logic w/ identity

in #proofs-and-logic

[north pilot]

the really interesting thing to me is 3374 is exactly (450*(6 choose 2))/2 - 1

and 450 is the previous case

and 6 choose 2 is what you would do for one vertex

i dont know if there's anything meaningful there or if its just a coincidence

[fierce venture]

I cant find any solution but i will ask my teacher

[north pilot]

can you give me their email after you ask too

[low hare]

What if you don't have all 6 hexagons and consider a case with only two? The more hexagons you add I suspect the amount of viable permutations decrease

Or well you looked at that yes

[fierce venture]

I will ask him if he accept i will glad to

[still grove]

Can someone let me know what this colon means in this context?

[little prism]

"such that"

maybe you have also seen ${x\in S \mid x\in A....}$ before

[vital dew]

Denascite

[little prism]

thats the same meaning

[still grove]

Yes I've seen that version but not this one

thank you

[fierce venture]

Check dm

[hard citrus]

trying my luck here, i want to know if im doing the convelution operation correctly in this exercsise:
here are my functions: $$\begin{cases}
x\left(t\right)=u\left(t\right)-2u\left(t-2\right)+u\left(t-5\right)\
h\left(t\right)=e^{-2t}\cdot u\left(1-t\right)
\end{cases}$$
where the convolution is defined as following:
$$x\left(t\right)*h\left(t\right)=\intop_{-\infty}^{\infty}x\left(\tau\right)h\left(t-\tau\right)d\tau$$

[vital dew]

horizon2.0

[hard citrus]

this is what i've done

[random sparrow]

@fossil mural

can I ask the difference between $\not\subseteq$ and $\subset$

[vital dew]

938c2cc0dcc05f2b68c4287040cfcf71

[random sparrow]

I saw you were about to type something but the conversation was way out of topic for calculus

or if anyone can help me understand what the heck does the symbol $\not\subseteq$ tranalates in venn diagrams

[vital dew]

938c2cc0dcc05f2b68c4287040cfcf71

[random sparrow]

because I was told in calculus it does not mean the two sets are disjoint

they can have intersection but is not entirely contained I pressume

so $\not\subseteq$ means $\subsetneq$?

[vital dew]

938c2cc0dcc05f2b68c4287040cfcf71

[random sparrow]

or am I tripping here?

sir, what were you about to write? @tight hound

[tight hound]

It is very odd to ping someone just because they were typing in a channel.

[random sparrow]

desperation

because I see conflicting venn diagrams online

some people mean something and others mean other things with the same symbol?

[tight hound]

I hope you get the answers you need

[raven python]

Not a subset vs. proper subset

[neon harbor]

$A \subsetneq B$ means that A is a subset of B, but A is not equal to B, usually we say A is a strict/proper subset of B. $A \not\subseteq B$ just means that A is not a subset of B, ie. there is an element of A that is not in B

[vital dew]

sheddow

[random sparrow]

ohh ok, so $A \subsetneq B$ can be used to refer to a $A$ being a proper subset of $B$

but in the case $A \not\subseteq B$ means A is not a subset of B, meaning than all of it its not included (disjoint) or that some of A is included in B but not in its entirety

[vital dew]

938c2cc0dcc05f2b68c4287040cfcf71

[random sparrow]

hopefully I understood what you guys mean, now

[odd heart]

Sheddow phrased it best; $A \not\subseteq B$ is equivalent to "there exists an $x\in A$ such that $x\notin B$"

[vital dew]

Outsider

[odd heart]

I.e. "A is not a subset of B, proper or otherwise"

[random sparrow]

I see, thank you for the clarification, sorry for bothering with the pinging

[elder quest]

when showing surjectivity of an algebraic function that is already shown to be injective, i get that we can solve for the input in terms of the output and show that f(input) = f(input), correct?

if the function is not injective, is this method inconclusive?

[elder quest]

if anyone decides to reply to my question, ping me as well

[little prism]

I am not quite sure what you mean by that. f(input)=f(input) is always true. can you give an example of what you mean?

for any given output y you can try to compute some input x and then show that indeed f(x)=y. thats how you usually show surjective

and it has nothing to do with injective

[elder quest]

oh

[elder quest]

sorry i meant this

[elder quest]

i was confused because i thought that f(x)=y where we found x in terms of y would only be valid if the function itself is invertible; so surjectivity can be inferred if we know that the function is injective and invertible

[hexed arch]

I'm poor at combinatorics and probability related to it.

Any way to improve it?

[oblique pelican]

You can't infer surjectivity from injectivity. Take f(x) = e^x. It is injective, but you can't find an x where e^x = 0, so its not surjective. You can also have a surjective function where you can find multiple x values where f(x) = y for some y, this type of function is surjective but not injective. Take f(x) = tan(x). Notice that f(pi) = 0 and f(2pi) = 0 (and in general, tan(x) = 0 for x = pi*n where n is in a integer).

[elder quest]

I edited my last phrase sorry

[oblique pelican]

Oh I see

in that case you're right

invertible functions are injective and surjective

and vise versa

injective + surjective <-> invertible

[pearl lark]

Is it fine to ask questions about set theory on here?

[brave rock]

It's better sometimes to ask forgiveness rather than permission

Just ask, and if it's not appropriate, people will direct you elsewhere

[neon wagon]

Could anyone help me draw this graph?

I know the steps to it but I have no idea how to draw it

My finals are soon and i've been studying

[pearl lark]

#help-31 it is on here but I still didn't get any help..

[brave rock]

Draw vertices labelled 1 to 5. If (a, b) is in R, there is an arrow from a to b.

[solemn badge]

for all the points like (1,1), (2,2), (3,3) and (4,4) this means you'll have a loop in the digraph

and (5,5) sorry oml

[polar grove]

Does anyone here understand the binomial theorem?

[pale epoch]

plenty of people do, it would be easier if you just ask your question

[polar grove]

It’s kinda broad but when I took discrete math, I didn’t understand it at all but it seems to have a lot of implications not just with polynomial expansion but also derivatives, integrals, etc. How does that work?

[brave rock]

Please be more specific

[little prism]

situations where you add two things and then take a power just occur quite frequently. so its no surprise that you encountered the binomial theorem in different contexts

[autumn hearth]

hello, can i ask about

why does strong induction work

like i get how to do a proof by strong induction

its more of

i dont get why we're allowed to assume the inductive hypothesis

or that it's true for all numbers less than the one we're doing induction on

[left ridge]

Strong induction consist of 2 steps.

1. Prove that base case is true. (I use P(1) for base case in this message)
2. If P(1), P(2), ..., P(k) are true, then P(k + 1) also true.

By step 1, P(1) is true
Then we are using step 2 over and over again.
P(1) true ⇒ P(2) true
P(1) and P(2) true ⇒ P(3) true
P(1), P(2), and P(3) true ⇒ P(4) true
P(1), P(2), P(3), and P(4) true ⇒ P(5) true
P(1), P(2), P(3), P(4), and P(5) true ⇒ P(6) true
and so on

And ultimately, P(n) is true for all positive integer n

[gusty swallow]

By your base case, you show P(1) is true (or some other initial value). So you have shown that P(k) is true for some k, specifically k=1.
Then assuming P(k) is true works, because you showed it works, and this lets you show P(k+1) in generality, instead of case by case.

[cursive nymph]

this is correct, right?

asking because our lecturer used a too complicated proof, that uses the smallest elements etc

so wondering if this is as simple as that, or if there are some subtleties I didn't notice

[polar grove]

So one of my classmates was solving this basic triple integral and he was too busy to actually do it himself and one of my coworkers rewrite it as a the series on the right (I could be mistaken on the exact series that he wrote though) and I’m trying to understand how he rewrote it

Just looking at it, it seems to make sense to me except for why he multiples the series by 4

[polar grove]

This is a generalized form that he wrote it in

[prime topaz]

can anyone look at help 13 to help me with this problem

[runic hedge]

help yall

would the denominator be 40

bc its not conditional

[molten hearth]

does conditional mean something like “student plays trumpet given that they also play clarinet”?

[molten hearth]

either way yes

[left ridge]

yes it's 6/40

[oak drift]

Hello I have a question regarding modulo

This is a true or false

but invertibility of a modulo is not part of my notes so idk I just wasn't listening during that time or whatever but can someone explain?

[left ridge]

true, f(0) = 3 and f(2) = 3 so the function is not invertible

[oak drift]

isn't f(0) = 1 ? or maybe I didn't understand the question

[left ridge]

f(0)= (5(0) + 3) mod 10 = 3 mod 10 = 3

[oak drift]

oh yeah mb

[oak drift]

thank you

[left ridge]

you're welcome

[cursive nymph]

guys?

[neon harbor]

I don't really understand it, is n an integer? But you write n U {n}, and m ∈ n

[cursive nymph]

that's how integers are defined in ZFC

[vital dew]

Sweet Tea 🧋🥥🍍🥭

[neon harbor]

Ah, I see 👍 I don't quite see how you get the last two lines, could you elaborate on what assumptions you are referring to?

Nvm, it's just the inductive hypothesis. Looks correct

[north pilot]

i need to determine the number of ways to color the cayley graph of $A_6$ with 8 colors such that each vertex is adjacent to exactly 4 vertices of the same colors

[vital dew]

Emma

[north pilot]

vertices of it

[light sinew]

If C is a partition of X then how can we use X/C? Doesn’t the second term after the / have to be a relation, and C can’t be one because it’s not made up with ordered pairs? What am I missing?

[pale epoch]

its defined right after what X/C is supposed to mean in this context

its a relation

[light sinew]

Oops yeah you're right, so would this be correct: Given a relation, we can define a partition such that: Each partition contains elements that are related to each other under the relation. Elements in different subsets are not related to each other.
Given a partition, we can define a relation such that: Two elements are related if and only if they belong to the same subset of the partition.

[pale epoch]

yes, exactly

[light sinew]

Thanks alot

[arctic hill]

Hey guys

I need someone to help me

Quickly

In discrete math

Please tell me so I can dm.

[solar marsh]

I can

[coral island]

For part a, S means student ID, N means name, C means course
Why is it that for SC circle (SN)^-1, it is a direct relation from N to C?
Won’t it evaluate to SC circle NS. Is SC circle NS equivalent to NS circle SC?

[arctic hill]

Anyone?

[lethal linden]

!justask

[arctic hill]

@lethal linden how to approach 1.3?

Take part a for example

Should I substitute value of x first?

Or y?

How should I approach this?

[lethal linden]

Somewhere that syntax is defined in your textbook. What is the definition?

[arctic hill]

@lethal linden is this it?

[lethal linden]

Seems like the syntax takes an expression and a substitution rule and gives a new expression, so the only way for expression[rule][rule] to make sense is interpret it as

(expression[rule])[rule]

[arctic hill]

So first I gotta put x = y + 2 and then put y = y.x ?

Ok that makes sense.

Chatgpt and copilot suggest the opposite lol.

[lethal linden]

The power of reading the definitions

[arctic hill]

So in short, first I'll evaluate or solve the innermost rule and then the outter rule?

[arctic hill]

True.

[lethal linden]

Seems like it. I don't even know what it would mean to do it right-to-left.

Do you replace it everywhere, including in other rules? Or just the expression?

If just the expression, you may as well commit to doing it left-to-right and reordering the rules.

[arctic hill]

This is basically textual substitution. Let me clarify it further

This should help

Click on the image to view it in full size.

[lethal linden]

I understand what is happening. I'm saying if you were deciding how your syntax was supposed to work, you'd have no good reason to make it work like expression([rule1][rule2]).

[arctic hill]

Oh. Yea you are right.

[lethal linden]

It's what I said originally.

It's E[rule] gives you a new expression E'

So the syntax is only defined when it's an expression and a rule.

So E[R1][R2] has to be

E[R1][R2] = (E[R1])[R2]
          = E'[R2]
          = E''

Where ' just means an expression after some rule has been applied.

(I think the textbook would've done well to spell this out.)

[arctic hill]

I see. It's very clear now. Thank you sooo much.

[lethal linden]

Cheers

[arctic hill]

Well either I am too stupid or the book is kind of vague.

[lethal linden]

There's a certain style of mathematical writing that assumes the reader is always taking everything very literally and never over-interprets. Of course that is never the case, at which point a successful interpretation depends on a reader's ability to self-correct.

Because here the very literal statement is you're given expressions E and R and told what E[x := R] means.

So if you took the minimal possible grammar consistent with that then the alternative would look unintelligible to you.

But we're humans and that's not how humans work, so a silly thing for the textbook author not to mention, or at least give an example of.

[hexed arch]

Any nice discrete math book for non-math students?

[arctic hill]

Hmm

[arctic hill]

True.

I'd like to thank you once again for taking out your time to help.

[final cliff]

Kenneth Rosen has a pretty common one for CS

[coarse token]

Will this be 0.6 or 0.0?
Given the following Markov Chain. What is P(A|E)?

[grand rivet]

are you starting at A or E?

[random sparrow]

can someone explain handshake lemma

Twenty switches in an office computer network are to be connected so that each switch has a direct connection to exactly three other switches. How many connections will be necessary?

[buoyant raven]

handshake lemma is most easily explained through a graph theory representation but the gist is like

Say you have a switch A with three connections c_1 with switch X, c_2 with switch Y, and c_3 with switch Z

If you count up all of switch A's connections, you get 3 connections

But those 3 connections will also be counted in X Y and Z's connections to

That is to say when you count X's connections, it will also count c_1

when you count Y's connections, it will also count c_2

when you count Z's connections, it will also count c_3

So essentially when you add up the number of connections for each switch

You would be counting each connection exactly twice (for all connections)

[random sparrow]

I guess I get it

is just hard to think of

maybe more practice is needed from my part

[buoyant raven]

here we have a graph with vertices and edges (in your case these are switches and connections)

the degree of each vertex is the number of edges on each vertex

deg(a) = 2, deg(b) = 2, ...., deg(f) = 1

when we add up all the degrees we get 2+2+3+5+2+1+1 = 16

But notice each edge has two vertices that are counting it

the edge shared by a and b is counted in both deg(a) and deg(b)

[random sparrow]

yeah

[buoyant raven]

similarly, the edge shared by a and c is counted in both deg(a) and deg(c)

so each edge is counted twice (once for each vertex) in the sum of degrees

count the number of edges and tell me what you get

[random sparrow]

well

16

[buoyant raven]

not the orange tick marks

just the white lines

those are the edges

[random sparrow]

8

[buoyant raven]

8 edges

[random sparrow]

yeah

[buoyant raven]

and each edge has how many tick marks on it

[random sparrow]

2

[azure smelt]

Can someone pls tell me how to solve c part

[buoyant raven]

so basically when you add up all the number of edges incident for each vertex (tick marks around each vertex)

you count each edge twice (2 tick marks on each edge)

in your case

[azure smelt]

I know the duality principle

[buoyant raven]

for each switch there is 3 connections, 20 switches for a sum of 20*3 = 60

In this sum, you count every actual physical connection twice

so how many actual connections do you have

[random sparrow]

well

(20x3)/2

[buoyant raven]

which is what

[random sparrow]

30

yeah, ty for the help i think i got it

[buoyant raven]

is that still iffy or do you get it conceptually

[random sparrow]

I get it fr, ty

[buoyant raven]

ofc, good luck with what you are doing!

[buoyant raven]

what have you tried?

for c

[azure smelt]

Nothin much tbh. I know + becomes * but I cant seem to do anything with this question

How do I convert the whole thing?

[azure smelt]

Will it be

a.(b.ā) + b (complement) <-> 0

[buoyant raven]

work outward to inward

the biconditional is the most outward boolean operation

what is the dual of the biconditional

you get that by finding the and/or representation of the biconditional and flipping them

[azure smelt]

Nothing

Oh wait

Wow this is very confusing

I thought it would be something simple for 2 marks

@buoyant raven

Can you solve this

[light sinew]

Is my definition correct: The canonical map maps each element to its own equivalence class which is the set that contains all the elements the element is related to in an equivalence relation. Thanks

[buoyant raven]

find the primitive and/or representation of the biconditional

then flip it all

there are two equivalent such representations

conjunction of conditionals along with material implication

And you can easily make the other one by looking at the truth table of the bicondiitonal

[west scarab]

guys................. i made a problem someone pls try solving it

You have n identical objects arranged in a straight line. First, you choose a positive integer k (where 1 ≤ k ≤ n). Then, you can repeatedly perform the following operation:

Select k consecutive objects that have not been chosen before and add k to a total sum S.
What is the maximum possible value of S?

Example
Suppose n = 4 and you choose k = 2.

The line of objects looks like:
1, 1, 1, 1

You can select the following consecutive groups of size k = 2:

The first 2 objects → Add 2 to the sum (S = 2).
The next 2 objects starting from position 2 → Add 2 to the sum (S = 4).
The next 2 objects starting from position 3 → Add 2 to the sum (S = 6).
After this, you cannot choose any more groups of 2 that have not already been chosen.

Maximum possible sum S = 6.

[azure smelt]

Im still confused

Can you guide me about part c?

I know negation of For all turns into there exists at least one and vice versa

[arctic hill]

How to solve 1.9?

[opal crescent]

@solemn mortar

[solemn mortar]

je suis la

[opal crescent]

donc 2Z\X U X\2Z = 6Z

ok

bon ok on va essayer d'en dire un peu plus sur X

[solemn mortar]

j'ai eu cet conclusion

ah si je peux je veux additionner qlq chose que je crois peu nous aider

[opal crescent]

t'as l'union de deux gars qui vaut 6Z, a minima faut que les deux gars en question soient inclus dans 6Z

i.e. t'as $2 \mathbb Z \setminus X \subseteq 6 \mathbb Z$ et $X \setminus 2\mathbb Z \subseteq 6 \mathbb Z$

[vital dew]

aPlatypus

[solemn mortar]

oui..

je ne sais pas beaucoup les loi ou application des ensemble mais est ce qu'on peut prendre 6Z = 2Z * 3Z ?

[opal crescent]

ok mais tu veux faire quoi avec ça ?

la question c'est jamais est-ce que je peux, c'est est-ce que c'est utile pour moi maintenant

[solemn mortar]

n'auras pas une route pour savoir X comme ca non?

[opal crescent]

faudra m'expliquer dans ce cas, là je vois pas où tu veux en venir

[solemn mortar]

2Z sont les entier pair

on le prend 2k

et 6z est 6k

[opal crescent]

faut que j'y aille qq minutes, tu peux prendre ton temps

[solemn mortar]

et X dois avoir les elemnt de 2Z qui ne sont pas dans 6Z