discrete-math

[cerulean radish]

Either way, start by applying de morgan's laws to the negation of (not A) + ((not B) * C)

[stiff slate]

Is discrete math real math?

[brave rock]

Wym “real”

Yes, it is math.

[stiff slate]

Maybe its just my textbook but ive taken foundations of mathematics and they are similar but I feel discrete math just makes up stuff along the way

Ideally they should be the same

Only discrete deals with situations where sets are finite and discrete I'm assuming

[brave rock]

"Discrete math" is not really so much a field of study. It is a name for a course where people learn some basic ideas that come up in many many fields of mathematics. Idk what you mean by making things up, but the fact is that there are a large number of places in math where you use these ideas.

[stiff slate]

Maybe it is the class cause Im taking but I cant think of an example

Whats the point of the class though if you already have courses like intro to proofs or foundation of mathematics?

They cover the same thing minus recursions, exlusive OR, rules of inference, and 0-1 matrix

Only in thise classes you do it for all numbers and even infinite sets

[brave rock]

I can't justify your institution's overlapping classes. I can say that usually these classes, if distinct, will have some overlap at least.

[coral parcel]

A main point of "discrete math" in many places is to be the sole math course that CS majors are required to take. In my time, students who also followed the first year or two of the math undergraduate program were exempt from it.

[clever sail]

damn really

[merry storm]

i need to disagree

if u mean the course - ok its fine

but in general discrete math has some real hard science

not just basic ideas

[brave rock]

That's not what I was saying at all.

[merry storm]

ok sorry then

[coral parcel]

He was talking about the course.

[merry storm]

yeah got it

[coral parcel]

I couldn't say -- in the system I have firsthand knowledge of did not really have a major/minor distinction in undergraduate. Each STEM department put out a course program designed to fill half of a full-time study workload, and then everyone was supposed to choose two of those.

[clever sail]

Ah i see

[merry storm]

so its not about science but about coding?

i feel like its not about really science anymore

i dont think i even need to go to compsci major

[coral parcel]

Back in my time and place, the university's computer science department was completely distinct from the separate and more vocationally oriented institutions that produced programmers and other technicians. What we were supposed to learn was a broad scientifically based overview of computing that was supposed to qualify us as strategizers, decision-makers, and innovators. Of course many of my cohort ended up doing software development in industry, but the nuts and bolts of actual programming were mostly left for us to explore by ourselves. I had exactly one course branded "systems engineering" and that was mostly about academic theories on project management.

[clever sail]

this makes sense and i think its how it should be

[clever sail]

what do you want to do?

[merry storm]

now im just tired a lot of this engineering stuff

i have a feeling that i waste my life doing some dumb coding

so

i want to try to achieve somthing in math

thats also true about bachelor, right? i mean u have comp science bachelor but

[merry storm]

do u really do science there?

oh, i mean that message

u were talking about major

sorry, discord keeps replying on other message

idk how to fix

opportunities for what?

im not even sure u need higher education for such jobs actually

u mean major is useless sometimes?

u mean that its more effective to start working and have more experience by this time?

i dont know about us actually

but

is it considered that if u dont do major ur education is not like

“complete”?

sorry, i was confused with my own lamguage

i was talking about

master degree

is ur education like complete if u are not going for it

yeah i agree that there should be 2 different majors

yes

[merry storm]

because now i face that i need study a lot of engeneering cources

that i dont need

[coral parcel]

Tech hiring has cycles of ups and downs.
In good times, about everyone with a pulse who can convincingly claim they can code will get hired somwhere.
In bad times, having academic qualifications can be your ticket to one of the few interviews,
In the middle periods, degrees can be important if you're fresh out of school, but if you have a handful years of actual development experience on your resume, that counts for more than diplomas.

[merry storm]

i dont want to study assembler actually and how processor works

so u have mostly math sciences in ur program?

what are they for example?

oh, nice

i have those

i dont have diff geometry on the list

and where do u want to work?

i see

here a lot of people have a goal just to be an engineer and thats all

actually i have such thoughts that

that it may be very hard to do science in math

ill try this summer but

we are studying a lot and im not sure that i will able to apply it for my own research

like we have so much time studying that i didnt have time to do it before

do u have time for that?

[merry storm]

(ive just finished my 2nd year)

ah, i see

its cool

and uve done some research?

good for u

thanks

what field of math was ur research about?

[merry storm]

ahh

i studied something similar in diff equations, it was nice

i studied lyapunov stability

xd

like findind equilibrium points and drawing phase graphs

[night fog]

I am studying discrete math, why does it feel like several other fields in a trench coat

[fossil mural]

...might be because it is

"discrete maths" is a pretty general term, a lot of things are discrete

the trenchcoat is probably because of whatever course or book or whatever trying to present all of it as if it's one subject

[shrewd ether]

Please help at #help-7｜zen1thxyz its 2 days before exam and Im crying 🥲😭🤧🤧

[shadow lion]

be patient!

[ashen bane]

Can someone explain for the intuituion how to think of it?

Like where did this build come from

I want to build better intuition in graph theorem

[ashen bane]

can this be proven by induction?

[wary grove]

Guys, how conventional is it to use * or . instead of ∧ operator to represent AND between propositions?

[inland raft]

what do you notice in these bipartite graphs? what is the length of any walk from a blue vertex to a red one? how about length of any walk between two blue vertices?

[ashen bane]

@inland raft so basically its like tici taca

https://tenor.com/view/tikitaka-barcelona-gif-6183953

this is what i see

[inland raft]

nope, the blue vertices cannot be adjacent with each other. any walk from a blue vertex to another blue vertex has to have even length. for example in the first graph above, to go from B to E, you need to go from B to 3, 3 to A, A to 1, and then 1 to E. that's an even length walk

if messi wants to reach neymar then he has to pass the ball to ramos or any other player in madrid but then the ball has to return to barcelona immediately, players from the same team cannot finish a successful pass to each other

[ashen bane]

yes this is a selling tici taca

means ronaldo-messi-ramos-neymar-pepe-suaresz

[inland raft]

okay thats too many footballer names now, i only know messi, ronaldo, neymar and ramos

[white delta]

can someone explain me what is the meaning of these solution?

12. Let 𝑃(𝑥) be the property 𝑥∉𝑥. Prove that {𝑥|𝑃(𝑥)} cannot be a set.
    Solution: Suppose toward contradiction that 𝐴={𝑥 |𝑥∉𝑥} is a set. Then 𝐴∈𝐴 if and only if 𝐴∉𝐴.
    So, 𝑝↔¬𝑝 is true, where 𝑝 is the statement 𝐴∈𝐴. However, 𝑝↔¬𝑝 is always false. This is a
    contradiction. So, 𝐴 is not a set.

[analog tinsel]

Am I missing something with this argument ?
show that a planar graph on n vertices with m = 3n-6 edges is a triangulation:
Let G on n > 3 vertices be a planar graph that is not a plane triangulation (that is, every face has degree 3) => There exists a face with degree > 3 => two vertices can be connected by a non-crossing edge => G had < 3n-6 edges.

I feel like the step where I say that two vertices can be connected by an edge is kind of obvious since you can rearrange the planar graph such that the face is "empty" and then you have a cycle of length > 3 so you can draw the line between them.

[stiff slate]

Can someone explain to me the point of ceiling/floor functions.

Why cant we just use regular rounding

[pale monolith]

you can

but what if you want to round up always

[white delta]

ceilling help

[night fog]

general equation for set union cardinality for n sets, but have no clue how to notate it, can I get some help?
The idea is to sum the cardinality of all the sets, subtract the cardinality of a combinations of two sets, add the cardinality of a combinations of three sets, so on so so forth.

[inland raft]

https://en.m.wikipedia.org/wiki/Inclusion–exclusion_principle look at the formula section

[night fog]

what does this big U mean?

I've looked this up before, but idk this difference between this and union

[inland raft]

That union is just A_1 U A_2 U ... U A_n

[night fog]

oh so it's like capital sigma or capital pi notation but for unions then

[little cloak]

yes, and similar notation also exists for intersection

[night fog]

👍

thank you

[neat oasis]

Can't you just do it via contradiction? (Assume the graph is not connected, then there's at least two connected components, but there cannot be three components as you'd need to have at least one component with less than or equal to n/3 vertices which cannot correspond to the minimum degree of n-1/2, if there is any low vertice counterexample of what I just said just check it, therefore WLOG we can assume there's only two connected components, then, there's at least one component with less than or equal to n/2 vertices, but, if you have n even, you'd need for them both to have a minimum degree of n/2 (as an example (4-1)/2 = 3/2, then you have to have degree 2, but in a connected graph, the maximum degree of a vertice is n'-1, where n' is the number of vertices of this hypothetical graph, therefore if n is even the graph must be connected, and if n is odd, there'll be at least one component with less than or equal to n-1/2 vertices (example: if you have a graph of n=5 vertices, one of the components has to have 2 or 1 vertices), and because of the same lemma used before (the n'-1) that can't happen and therefore for n odd or even the graph must be connected, which is every case)
Probably explained myself horribly because I wrote this while walking but the idea is to:

1. Assume the graph is not connected
2. Show that for a minimum degree of n-1/2 there could be at max 2 connected components
3. Show that for n even it's not possible to have that degree and it be not connected
4. Show that for n odd it's not possible to have that degree and it be not connected

Now by "induction" I think what you can do is the following: Asume you have a graph of n-1 vertices where all the vertices have a minimum degree of n-2/2, add a new "imaginary" vertice and connect it to every previously existing vertice, then you have a degree on all vertices higher than or equal to n/2, therefore there has to be a hamiltonian cycle, if you start from the imaginary vertice you can do a full cycle passing through every vertice exactly once, and finishing in the imaginary vertice, then the initial graph (when removing the imaginary vertice) is connected as you could go through every vertice from the path

(As for actual induction, you can probably do something)

[white delta]

can A = {A}?

[agile magnet]

no

but the reason is hard to grasp and gets right at the roots of the foundations and axioms of modern mathematics

https://math.stackexchange.com/questions/1046863/how-can-a-set-contain-itself

it's a good question though, just I can't give a quick answer (mainly because I've personally never looked into this stuff)

I just know it can't be done according to some axiom

[white delta]

I should skip this one of problem

[agile magnet]

wait someone asked you to prove this or give an example on a HW or something?

[white delta]

2. Let 𝑃(𝑥) be the property 𝑥∉𝑥. Prove that {𝑥|𝑃(𝑥)} cannot be a set.

this one

[agile magnet]

ahhhhh ok this is a much more reasonable question

ok let Y = {𝑥|𝑃(𝑥)}

Assume towards contradiction that Y were a set

either Y is in Y, or Y is not in Y

agreed?

prove that both yield a contradiction

[white delta]

yes it did

[agile magnet]

ok you got it? nice

[white delta]

yeah, it a bit weird

[agile magnet]

it is

this is called Russell's Paradox

very interesting bit of mathematical history surrounding it

because before that paradox (and similar ones) were found

everyone assumed that "if I can define the set, it exists"

[agile magnet]

but clearly this isn't the case

kinda blew open the whole underpinnings of early modern mathematics

[white delta]

Thank you for the answer, man. I stuck with this thing for hours until i get this answer

[night fog]

I wanna do this, but I don't know how to import it to something like overleaf, maybe more of a tech issue then a discrete problem...

[agile magnet]

import what into overleaf?

if you have LaTeX questions, go to #latex-help

[night fog]

true true

[carmine matrix]

Does a loop on a vertex count towards the degree of the vertex once or twice? My textbook defines deg(v) as the number of edges incident to v, but it is provable that an Euler circuit exists iff G is connected and for all v, deg(v)=2n - the singleton graph with one edge clearly contains an Euler circuit, but it seems counter to that theorem if that definition of vertex degree is accurate. What am I missing?

[coral parcel]

I don't think there's a strong convention. You'll need to check in each case what an author means when they speak about degrees in and there may be loops.

In most situations I think it would make most sense to consider the loop to contribute two degrees, but I think there are sometimes exceptions to that (though I can't offhand remember any convincing ones).

[carmine matrix]

Jeez that’s annoying

I’ll just go with the most convenient definition for the sake of the argument then

[exotic heath]

how do I prove that exponentiation to the power n takes asymptotically log n multiplications?

[coral parcel]

A single multiplication can at most double the logarithm of the largest number you've created so far.

[exotic heath]

...and?

[coral parcel]

If you start with only having the base b, then you need to make a number whose logarithm is n×log(b).

If you have fewer than log2(n) multiplications, you cannot get that high.

To prove that O(logn) multiplications is enough, look into exponentiation by squaring.

[exotic heath]

this is not what I wanted
I wanted to logn+o(logn)

[coral parcel]

Do you mean the natural logarithm in particular as a worst-case bound without any possibility of a constant factor?

That seems to be impossible given my lower bound of log2(n) from before.

[weary tiger]

Hey! I just started learning about combinatorial optimization and the first week is some review of basic graph theory that I've unfortunately forgotten. The question is: how would I go about showing that every simple graph has two vertices of the same degree? A simple graph is a graph that is undirected, not a multigraph (i.e. E is not a multiset), and there are no loops. I would appreciate if someone could guide me through the thought process, since discrete maths is kinda a big weakness of mine. Thank you!

I was also thinking of maybe using contradiction?

Connectedness isn't an issue so we can assume that $0 \leq \text{deg}(v) \leq n - 1$, for an $n$-vertex simple graph.

[vital dew]

45

[weary tiger]

Maybe a proof by contradiction would entail the opposite of the implication, i.e. that all vertices of $G$ are pairwise different degrees that belong to this range.

[vital dew]

45

[tight hound]

There are n possible degrees, and if you have a vertex with degree 0 then you can't have one with degree n-1

And vice-versa

Then just use the pigeonhole principle

[weary tiger]

isn't that enough of a contradiction?

do we need to use the pigeonhole principle then?

because if one node has degree 0 then it's true that there can't be one with degree n - 1, since after we've "chosen" a node, we can make at most n - 1 connections (which is impossible if there's one node with no edges)

[weary tiger]

I'm open to the idea though - how would we apply the pigeonhole principle here?

ah I see now

you're taking a step further and saying that if there's $n - 1$ total "possible" degrees (since $0$ and $n - 1$ both can't be possible), then this must mean that given $n$ nodes and $n - 1$ possible degrees, we must have AT LEAST two nodes of the same degree, since it's analogous to putting pigeons in boxes (where the number of pigeons exceeds the number of boxes)

[vital dew]

45

[weary tiger]

right?

[tight hound]

Yes

[weary tiger]

cool, thanks

[haughty ferry]

Hello I asked a graph theory question in #help-42 which might be too hard for what is supposed to go in those channels

Will someone please direct me to the right place to ask it for help? Should I close that thread? Thank you in advance

[fossil mural]

(for the sake of anyone in the future, the question is #help-42 message )

[haughty ferry]

Ooh #combinatorial-structures looks like they talk about graph theory

I’m gonna repost this there

[peak lantern]

Guys I've got a question

I study computer science and I have just completed my first year

Before I study algorithms and data structure is it necessary to study discrete mathematics?

[little prism]

parts of it would certainly help but presumably the course covers the relevant stuff

[oblique pelican]

Graph theory would be good for that

[hoary cloak]

i would say it is assumed that your university course will give you the necessary background on things like enumerative combinatorics, discrete probability and the very basics of graphs early on

[uncut raptor]

Hey anyone here that is a good at discrete math that can give me tips, I feel like discrete math is way harder then normal math courses. So much proof questions, any good advice for that?

[brave rock]

Practice

[uncut raptor]

but even with practice like graph theory for example feels way harder then some linear algebra/calculus etc

[brave rock]

& the tip to get better is practice

[uncut raptor]

but what are like the hidden tips

[brave rock]

There are no hidden tips

[uncut raptor]

did u struggle with discrete math too?

becuase there is no way it can be easy right

like more then half of the quesitons are proof

[brave rock]

It will be easy once you've practiced enough

At least at a certain level

[uncut raptor]

I can't even imagine that but hope it will, some proofs already take atleast full a4 paper tho

[coral parcel]

If it's the first proof-oriented course you're taking, that is a common experience.

[red ocean]

I know the Collatz Conjecture hasn't been disproven, but has it been shown that for every odd integer $m>3$, the sequence defined by $n_i=f(n_{i-1})$ where $f(n_{i-1})=\begin{cases}
mn_{i-1}+1,n_{i-1}: odd\
\frac{n_{i-1}}{2},n_{i-1}: even
\end{cases}$ diverges?

[vital dew]

friendlyneigborhoodtopologydonut

[coral parcel]

I supose you mean "... that for every odd m>3, there's at least one starting point that leads to an unbounded sequence?"

[red ocean]

oh, yes that is what I meant. Thank you.

[coral parcel]

I'm not immediately sure there is even one m this is known to be true of.
There seems to be plenty of numerical evidence that most such sequences seem to grow without bounds, for every m. But from there to an actual proof seems to be a bit of way.

[red ocean]

Okay, thank you.

[fossil blaze]

https://www.ijisrt.com/assets/upload/files/IJISRT22MAR967_(1).pdf

what does this mean? I thought Power Set of Natural Numbers is not Countable
or is this paper just invalid? (not from a math background so i am confused)

[odd heart]

Yeah, that paper is wrong although I don't have the time right now to look where exactly the error is, especially because it's not very well-written.

But I can confirm that the powerset of natural numbers is uncountable.

The erorr is where they take the "even subsets" of natural numbers and enumerate them as E_1,E_2,..., i.e. they act as if there were countably many such "even subsets", which is not the case.

And they don't justify that at all.

https://beallslist.net/standalone-journals/#update

Also the journal is on Beall's list, any journal that's there should be approached with great caution.

[fossil blaze]

thanks a lot

[blazing rose]

I found 2 different ways to factorise this giving me the zerodivisors: 2x and 2x+1, x and x+2

Now I realized there is this polynomial 2x^2 + x which multiplied by 1 also gives 0

But this doesn’t count as zerodivisor as in this field 2x^2 + x would be „reduced“ by the modulo operation mod(x^2 + 2x) which is naturally 0 then?

So if I look for zerodivisors I can’t look for the same degree right

So always lower degree

Because it wouldn’t make sense for degree 0 polynomials to be zerodivisors right? Because they would multiply some polynomial of same degree as the mod operation polynomial in this case x^2 + 2x which would naturally result in 0 by the mod operation?

[hot jolt]

?

[weary tiger]

?

[little prism]

by definition a zero divisor is itself not zero. 2x^2+x=-(x^2+2x) and 0 are the same thing in that ring, so 2x^2+x is zero and hence cant be a zero divisor @blazing rose

anything of degree >=2 can be reduced and it is a zero divisor if and only if the thing you reduce it to is a zero divisor. so it is enough to only look at polynomials of degree <=1

[blazing rose]

Yes that makes sense thanks a lot

[blazing rose]

I guess if I understood correctly, every polynomial of degree 2 here must be equal to m(x) I use for the mod operation or gives me a rest when divided by m(x)

[little prism]

m(x) also gives you a rest when divided by m(x)

so no need to make a distinction there

[blazing rose]

Okay I see

[little prism]

this is just like modulo with numbers

if you are computing stuff mod 7, you dont need to look at number >=7.

[blazing rose]

But I mean the thing at the bottom when I do polynomial division

It is 0 right

For m(x)/m(x)

[little prism]

yes

m(x) = 1*m(x) + 0

[blazing rose]

And m(x)/-(m(x)

[little prism]

so 0 remainder

[blazing rose]

Yes

Okay if I

Don’t immediately see

The other 2 zero divisors

Would it be a good way to take -m(x) and make it positive through mod 3

[little prism]

well that would work but imo is not the best way to think about it

m(x)=x^2+2x=x^2-x = x(x-1), yes?

[blazing rose]

So I get -(x^2 + 2x) = 2x^2 +4 x = 2x^2+x

Then I could see one zero divisor by trying to factor the last thing on the right

Or doesn’t that always work

I.e. I’d get the last zero divisor by using this third one to factor the original m(x) respective to the modulos

[little prism]

and you know that if you have y*z=bla, then also (a*y)*(1/a*z)=bla. so you can just start with the x and x-1 you got and multiply those by other things

yes your method will always work in finding some other zero divisors

[blazing rose]

Ahh right

[blazing rose]

Thanks a lot :)

[little prism]

you know that any zero divisor needs to have a common divisor with x*(x-1). so it needs to have x or x-1 as a divisor

and thinking about it like that also generalizes way easier to bigger examples

[wet glen]

Hello, I wanted to know how to start this problem? It's problem h.

[uncut raptor]

my teacher said if u take the |B| to the left side of the rule of difference u can view it as a different way to write the rule of sum

but I can't see how

nvm I see it

[wraith summit]

i would start by writing out the definition of $\iff$

[vital dew]

esca (@ with reply)

[wet glen]

Thanks I'll try that. There wasn't much info in the book about solving.

[modest light]

for the first
first step
-P -> -Q
P Or -Q

then
P <- Q

Bc -P -> Q === P or Q

-P -> === P or

@wet glen

you should look at these table when you need help

then when you use a law write it next to the expression

[graceful canopy]

hi little question about pumpage lemma

in case, more 1s, than 0s

doing that xy <= p and y>0 and word xyiz should be in langage for every i>=0

then i have
x = 0(Q)

y=0 (R)
z=0(P-Q-R) 1 (P+1)
then for i=0 we have
0(p-R)1(p+1)
but can i say after that, p-R could be in negative because R>0 and p could be =0 so o(negativenumber) and its not in the langage so not regular ?

[coral parcel]

Can you show what the question you're answering is?
Also exactly which pumping lemma are you trying to use? There are several formulations that slice up thing slightly differently.

[uncut raptor]

hey I solved this one with a combinatorial proof bascially
u write the left and right side as the cardinality of the power set(N_n,k)
and then write the definition of that
define a function
show a 1 to 1 corrspondence by showing bijection
show that the inverse existed
and done

but now i had a different question and apprently this is also a combinatorial proof

proving the binomial theorem

but I can't figure out why this is even coonsidered a combinatorial proof like I did with the power set bijective function etc. I can't even see why this is considered a proof as it's mostly words

[uncut raptor]

question2:
I realy don't see how he made the picture out of the equations given

[wet glen]

Thank you. This was my attempt for part h, before seeing your message.

[modest light]

Nice to see that tou achieve the question

[gusty swallow]

The farther you go into math, the more you need words to explain proofs. Most proofs I encounter are largely words with a few equations thrown in.

It proves it by using what nCk is defined to do. It takes the product x^ky^(n-k) and considers it a 'word' of length n using the letters x and y. Since order doesn't matter in the product, the number of ways to obtain this word is by choosing k places for the x and then filling in the rest of the n-k spaces with y. So you have nCk ways to create the product x^ky^(n-k).

Like, the way to get x^2y^2 is one of: xxyy, xyxy, yxxy, yxyx, xyyx, yyxx. So there are 6 ways to do this which is 4C2. This is linked pretty directly to the power set idea of nCk if you consider the positions that x (or y, doesn't matter) can be in {1,2,3,4}. If you just want 2 x's then you're taking subsets of size 2, of which there are 4C2: {1,2}, {1,3}, {2,3}, {2,4}, {1,4}, {3,4}

[gusty swallow]

looks like he's choosing from three groups. So the left is choosing the things in A which is done with nC(r-i), then for B you've already chosen r-i things so there n - (r-i) = n-r+i things to choos s-i things from.
So you get (n-r+i)C(s-i) for B. Then a similar reasonging for C.
He's shoing for the right that this product is effectively doing the same count. for D, E, and F (starting by counting things in F first, maybe?) and if there is an overcount of some kind then they over count in the same way.

Considering that this is labeled 'step 0' i'm gonna guess there's some more reasoning used after this image that's not shown here.

[uncut raptor]

ye indeed there is step 1-3 too, I do have another question where I am quite stuck on. I thought about it a while but I can't find the mistake.

the underlined part why can't I define E as E subset of N_(r+s-1), |E| = s

[uncut raptor]

thank you for reacting btw it enlightend me alot

[gusty swallow]

Suppose D is a subset of N_10 = {1,2,3,4,5,6,7,8,9,10} with |D| = 7, such that D = {3,4,5,6,7,8,9}
Then if E is as subset of N_7 = {1,2,3,4,5,6,7}, E is not necessarily a subset of D.

[uncut raptor]

I see but why does E has to be a subset of D
if I define E as E subset of N_(r+s-1), |E| = s
F wwill be defined as F subset of N_(s), |F| = i
it seems to me cardianlity of Y will stay the same right?

[uncut raptor]

also the picture, do u also make ap icture like that, because I have no clue how to do that. Will it realy help

[gusty swallow]

The idea of this proof is choosing some things for D, then from D choosing some stuff for E, then from E choosing some stuff for F.
If E is not a subset of D, then where are you choosing things from and why is it connected to this set?

[uncut raptor]

well I thought E could be a set just as large as a subsset of D and then the |Y| will stay the same either way right? but I guess it's not the purpose of this excercise. but is it correct if I define my E and F that way |Y| will stay the same?

[ashen bane]

if G is graph k-regular, and k>=2, does it mean every edge is part of a circle?

is it true?

Im trying to prove something and came across this as a lemma

[gusty swallow]

You get a similar conclusion, since D has r+s-i things in it there's a map from D to N_(r+s-i), so you can use the combinations you know in a similar way as if E was a subset of N_(r+s-i). But again, this is trying to talk about counting subset of N_n, so introducing other N_k is over complicating it by having to then argue why this is the same as a subset of D

[ashen bane]

please

[uncut raptor]

oohh I see it's possible but totally not convenient, but I was thinking because this excercise bionomial terms are realy connecting each other, but when I have one which was not as beautiful so say I got instead of r - i I got smth not so beautiful r - i + 1, I have to take that approach that I mentined right?

this excercis I see the way how they are gonna do it I can make subset A B and x and B is subset of A and x is subset of B, is it always the case that I can write it as subsets of the previous ones? Or is it because they want to show me how counting from a set N_n works so they give me these excercises where u can write it as subset from eachother, adding other N_(k) will just make the excercises harder. Btw what part of adding other N_(k) makes the excercise harder actually?

[ashen bane]

בהצלחה ממני מנהל באתר נושמים מזרחית

[ashen bane]

?

[gusty swallow]

this was given as a lemma or you need to prove it as a lemma?

[ashen bane]

I want to prove this as a lemma

part of bigger proof

[ashen bane]

The thing is im not 99% its true

im trying to prove it

[gusty swallow]

seems true

[ashen bane]

Can you give me a lead

on how to maybe look at this

I want build stronger intuition

maybe proof by induction

[gusty swallow]

probably contradiction, if it's not part of a cycle then that implies something about the structure of it's neighbors

[ashen bane]

Yes im exactly tryin it

Ill let you know

[uncut raptor]

in the meantime can u help me with this question

[gusty swallow]

I don't know what this means.

[uncut raptor]

so for the given excercise if I change the excercise to n choose r - i + 1 instead of r - i

wait

I worded it wrong

wait

[uncut raptor]

so for this excercise when I change s - i to s - i + 1 should I then change B is subset of N_(s-i+1) or is there a better way

[gusty swallow]

why are you changing it?

[uncut raptor]

well say the excercise was changed

I am just trying to figure out how I will be able to solve it then

[gusty swallow]

B would still be a subset of n-r+i, you're choosing s-i things form a subset of a certain size.

[uncut raptor]

oh wait

I changed the wrong thing again mb

[uncut raptor]

so say n - r + i was changed to n - r + i + 5

how am I gonna solve it then

because B can't be a subset of N_n \ A now

[gusty swallow]

rewrite m = n+5 and then use the same proof

[uncut raptor]

ah I see

[gusty swallow]

or something along those lines anyway

[uncut raptor]

and if I changed n - r + i to k

so totally different letter

[gusty swallow]

maybe m = r-5

[uncut raptor]

ye I get whatu mean

[gusty swallow]

you'd connect k to the equations you already have and then use the same proof.

[ashen bane]

yes it's hard af

Idk how

[uncut raptor]

so basically u always try to connect ur set to another set either by subset or smth else

[ashen bane]

oh wait wait

i got it i think!

[gusty swallow]

'always' is a pretty strong statement. That's the approach taken here.

[uncut raptor]

also 1 realy last question and I won't bother u said that by adding for example B is subset of N_(k) is getting a similair conclusion but it will be overcomplicated, why is it making the excercise harder actually? at which step

[uncut raptor]

gotcha

[ashen bane]

@gusty swallow.
G is connected graph was missing for me.
Let e = {x,y}, lets remove it from our graph and mark 2 neighbord of x,y as u,v.
since G is connected, also G{e} is.
So there is a simple path from u,v
P = (u...v)
but in original graph x and y were connected to u and v so
(x, u...v, y)
so there is still a path from x,y after removal thus this is a part of circle

do you think its fine?

[uncut raptor]

wait I also dont' see if I got a totally different letter say k, how can I even conect them to r + s - i, I feel like i have to introduce N_(k) then right?

[gusty swallow]

you'd need to connect why they are the same and why they count in the same way.
If you have N_n, N_(n-r+i) and N_(n-r-s+2) and choose elements, Why is that connected to N_n, N_(r+s-i) and N_s? Why do those count or over count in the same way?

You can, and it's not necessarily harder. It just may require a little more justification than the subset approach

[uncut raptor]

so this step will become different I assume?

[uncut raptor]

where exactly do I gotta add the justification, that's basically my question, Because I don't see them adding a justification for the subset approach either

[gusty swallow]

why is G -{e} connected?
And G doesn't have to be connected to be k-regular

[ashen bane]

yes its not true

Since im proving it for a component i can suppose G is connected. but it still doesnt help me

Im not certain, i have e = {x,y}, G is k regular, and connected. how tf i show there is a circle part of x,y

maybe i can prove by induction on the vertex

not sure

[gusty swallow]

Again, why are those counts connected? You're choosing different number of things from different sized sets.
By making everything subsets of N_n you can see (by the picture) that these are the same count of the same subsets written in different ways.

[uncut raptor]

btw do u also often(not always) make a picture because how do u even make one given an excercise?

[ashen bane]

anyone please

if G is graph k-regular, and k>=2, does it mean every edge is part of a circle?

[gusty swallow]

pretty often helps, yeah

[uncut raptor]

wait are these 2 big texts the justification u meant?

[uncut raptor]

is there a wway to learn to make the pictures? would u draw the same because I don't understand these pictures like I thought C should not be in A and B but it is

[gusty swallow]

it takes practice, you're counting 3 things, so you probably need 3 subsets.
C here is not a subset of A. On the left A, B, and C are disjoint sets.
On the right, F is a subset of D and E

[uncut raptor]

so like what is ur thought process when drawing. u know all of the sets are inside N_n. soo the whole square is N_n(which is logical) then u choose A it has r- i elements so a random circle is sufficient. after that u draww B, B can be chosen from everything inside N_n\A so somewhere not in the red circle. C can be chosen from N \B\A but doesn't that mean that C shouldn't be drawn anywhere in the yellow or red circles?

[gusty swallow]

The left, you've got disjoint sets, like you said. But the right has subsets. So how can you show disjoint sets as subsets
Like the above, A\B, B\A and AnB are all disjoint, while D, E, F = DnF
So now you have the same collection of sets so counting them should result in the same number. l

[gusty swallow]

if a vertex v is not part of a cycle, then either v has a degree 1 neighbor and G is not k-regular, with k>=2. Or v is the root of a tree subgraph of G all tree graphs have a vertex of degree 1 which means your graph can't be k-regular with k>=2.
Something along those lines may work? Probably needs to be fleshed out more.

[uncut raptor]

if u were given the excercise would u draw it like this too ?

[gusty swallow]

no idea. depends on what I was given and how i'd previously been shown to work problems like this.

knowing me I'd probably just try to brute force it with computations.

[uncut raptor]

all right I will make some excercises and see how the drawing goes I guess

[uncut raptor]

wait how u brute force it

without drawing?

I wanna learn to brute force it too

[gusty swallow]

write out all the combinations and try to rewrite it

make them match

[uncut raptor]

I assume in a compact way right?

no way u gonan write litteraly all coombinations

[gusty swallow]

i mean all of the nCk in that equality

[uncut raptor]

I see

[uncut raptor]

but given these excercises I feel like it's always possible to match u just gotta figure a way to define the function

like they aren ot goonna give a excercise which is not possible to match

[gusty swallow]

that's the much more useful technique they're trying to show you, yes.

[uncut raptor]

I kinda see the aloghortim they do, but tbh I feel like I am gonna try without drawing first and see how it goes, the matching looks like just match the cardianlity of the sets

for example this one

AUBUC has a cardianlity of r-i + s-i + i

that is equal to D

so just try to match the cardinality oof the sets and u can define the function I think

[orchid igloo]

what subject is this one?

[gusty swallow]

boolean algebra?

[orchid igloo]

oh okay thats correct thank you!

[open wyvern]

how is this derived 💀

it definetely works over Z

but like 😭 where would you even start

oh huh apparently i guess its from here

[shrewd ether]

Please help at #help-22 🥲 I am struggling

[ashen bane]

the statement from yesterday

was not true

counter example

[gusty swallow]

every vertex is part of a cycle...? Am I missing something?

[ashen bane]

what about the middle one?, if you remove it, bye bye its not connected...

i said edge. not vertex

[uncut raptor]

for a combinatooric proof I know how to define a set for the left and right side, but how do I make a function to see the relation between the 2 set

for this particular case the answer is this

but

like it was nto obvious

to osee

I know picture can do the job tho, but left picture is in dimension N_n+1 and right picture is N_n so idk if that will help

[gusty swallow]

left is just N_(n+1) and choose k items.
The right is still N_(n+1). The first terms is fixing an element x, choosing k items without x (meaning you're only choosing from n items), the second term is choosing k items with x in it (meaning you only need to choose k-1 items from the remaining n items)

[uncut raptor]

uhh I don't realy follow the right part

so why is it still N_(n+1) actually

u can only choose from n

[gusty swallow]

suppose you have N_5 = {a,b,c,d,x}, and you want choose k = 3 things.
The first term nCk comes from choosing in a way that excludes the x element. So you have 4 elements to choose 3 from

The second term specifically includes the x element. So there are 4 other elements to choose 2 things from

[uncut raptor]

okay the first term I understand

[uncut raptor]

the second one a bit hard to understand why u do u include the x element, u still only choose from 1 to 4 not 5 included

[gusty swallow]

5 is already there, you can't include it again. So there's only the a,b,c,d to choose from for the remaining 2 spots.
You're building subset of N_5 that looks like {x,_ ,_}

Think of it like this.
(n+1)Ck is choosing subsets of size k. How else can you count those subsets?
Pick an element, x. Every subset you counted either has x in it, or it doesn't.
If x is not in the subset, then there are nCk ways to build that subset because you are ignoring x completely here.
If x is in the subset, then you can't use it again so there's still only n elements to choose from and one element of the subset is already occupied by x, so there are k-1 spots to fill. So you get nC(k-1) subsets that contain x.

[uncut raptor]

oh this is actually making sense

I will reread it a few times

[uncut raptor]

wait so what's like the key to know what the functioon will become between left and right side, logical thinking?

if u are given this, will u see what the function will be?

[gusty swallow]

no clue. I'd have to play around with it for a while.

[uncut raptor]

is that the way to find the relation?

[uncut raptor]

like what strategy will u have to find the relation of this functioon

I realy couldn't find it and when I got the answer I sitll don't understand it

[gusty swallow]

I'd look at a few examples and see if I can connect it to something I already know.

[uncut raptor]

this was the answer if u were curious but how do I connect it

and why is ther even a k+1

[gusty swallow]

this looks like a bit like a donut shop problem to me.

[gusty swallow]

they're defining a maximum element. Every subset you choose has a largest element, they're defining k+1 to be one larger than that maximum

[uncut raptor]

it looks familiair with a excercise u made earlier?

[gusty swallow]

not here no. It looks like it has similar reasoning to stars-and-bars or a donut shop problem.

[uncut raptor]

but why?

[gusty swallow]

Say n=5 and r=3
the left is 3C3 + 4C3 + 5C3
So what's happening? You're always choosing 3 things, but increasing the number you're choosing from. How can we connect that to the subset? Choose the maximum element first (since order doesn't matter, we can do that)

if the largest element is 3, then we're in the 3C3 case. If it's 5 we're in the 5C3 case.

How does this connect to stars-and-bars? We're putting a bar in for the maximum element, but that gives us another 'thing' to place. So the three cases are
_ _ _ | _ _ for 3C3
_ _ _ _ | _ for 4C3
_ _ _ _ _ | for 5C3

But now the bar gives us another element in the set to place, so we have N_5 U { | } == N_6 and we're choosing the 3 things and the bar placement, so we're choosing 3 + 1 = 4 things.

[weary tiger]

Can someone tell me if I did anything wrong here?

,tex \sum_{k=0}^{5} \binom{5}{k} \cdot \binom{5}{k}

[vital dew]

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

[weary tiger]

Here was the problem

There are 25 indistinguishable white chips and 25 indistinguishable black chips, find the number of ways to place some of these chips in a 5 x 5 grid such that:

• each cell contains at most one chip
• all chips in the same row and all chips in the same column have the same colour
• any additional chip placed on the grid would violate one or more of the previous two conditions.

[weary tiger]

1 + 25 + 100 + 100 + 25 + 1 = 252.

,tex \boxed{252}

[vital dew]

Akari

[weary tiger]

Ok, I am lost.

[coral parcel]

I'd think there ought to be 902 ways.

Namely, either you can make everything white or everything black (that's 2).
Or each row and each column have one color assigned to it and there's a chip in every position where the row and the column have the same color. But there must be at least one row of each color, and at least one column of each color.
In the second case where are 2^5-2 = 30 ways to select colors for the rows and 30 ways to select colors for the columns. That gives 30×30=900 solutions where there are both black and white chips. on the board.

[weary tiger]

Yeah you're right

and used the based solution

[orchid igloo]

is my solution correct?

[ember cypress]

anyone can tell me why this is wrong

[coral parcel]

Answer (a) is is correct and the response that claims "incorrect" makes no sense.
In the case it describes, "Bill or Rob is present" would be true, so there's no problem.

[ember cypress]

right

[grizzled flare]

can someone explain the solution of this to me? I dont understand the inductive step, or really what the question is asking me 😭

[autumn bay]

ouch this one look painful to proove with bijection

lol this look even harder than all advanced section for me

[tidal quarry]

https://tenor.com/view/sun-waving-hi-hello-smiles-gif-2600448509154208311

[terse mist]

It's blinding!

[summer niche]

can someone explain planar graph to me

please

[left shadow]

a graph is planar if it can be drawn with no crossing edges

so a graph like k3 is planar

but k5 is not

[unborn atlas]

Hey all, does anyone know if there is a combinatorial proof for the following identity?
$$F_{n+1,,k} = 2^n - \sum\limits_{m_\ell \ge \ell} (-1)^{\ell} 2^{m_\ell - (\ell + 1)}\left[ \binom{m_\ell}{\ell} + \binom{m_\ell + 1}{\ell + 1} \right]$$
where $m_\ell = n - (\ell+1)k$ and $F_{n, k}$ is the generalized Fibonacci number satisfying $F_{n, k} = F_{n-1,, k} + F_{n-2,, k}... + F_{n-k,, k}$ and $F_{0,, k} = 0$ and $F_{r,, k} = 2^{r-1}$ for $0<r\le k$

[vital dew]

nanojumper

[uncut raptor]

this one is realy painful can u help me explain what is happening with this one

[nimble mist]

Where are you struggling?

[uncut raptor]

hey I am struggling in this part

why is AU{k+1} the same cardinality as Y

[nimble mist]

Y is a family of sets

[uncut raptor]

yes

[nimble mist]

And A \cup {k+1} should be a set in this family

not the same as the cardinality of Y

[uncut raptor]

uhhm let me proocess that in my mind for a sec

[nimble mist]

Y contains all the subsets of size r+1

[uncut raptor]

soo A are basically all the subsets of N_k, N_k+1 ... etc with cardinality r

[nimble mist]

So A \cup {k+1} should be of cardinality r+1

[uncut raptor]

not r + 1?

[nimble mist]

oops yes

replace r with r+1

[uncut raptor]

uh okay I think I see in my mind how the sets are defined

but I don't relay see how they match eachother

like foor example

3C3 +4C3+5C3 = 6C4 right?

[nimble mist]

The logic here is simple

[uncut raptor]

oh wait 1 element too short

[uncut raptor]

u are typing the logic now right?

[nimble mist]

yes

Take a subset of size r+1

[uncut raptor]

ye

[nimble mist]

it has a a largest element

[uncut raptor]

yes

[nimble mist]

it must be at least r+1 right?

[uncut raptor]

uhm

ye

definitly

since ui already take r+1

[nimble mist]

So you can partition the subsets by their largest element

[uncut raptor]

uhm

[nimble mist]

That's what you do in X

X_is

[uncut raptor]

is it pssible too have multiple same largest element?

[nimble mist]

What do you mean?

Each subset has one largest element

lets say m so this subset belongs to...? X_{m-1}

because all other elements are a subset of size r within N_{m-1}

Do you see this?

[uncut raptor]

wait I see this

uh

[nimble mist]

in a sense... Becaue X_{m-1} does not contain subsets

it contains pairs

But when you define the function... f

it takes the union

So you get a subset

[uncut raptor]

ye I thoought u define the pairs to make it disjooint

[nimble mist]

So f(X_{m-1}) are the subsets with largest element m

Yes indeed... But you could also define X_{m-1} to simply be the subsets with largest element ,m

you would also get disjointness

But it would be a bit less obvious

[uncut raptor]

ye but there must be a reason it was not doone like that right?

is that the reasoon u are now trying to explain?

[nimble mist]

Just to make 1 obvious

That's just an arbitrary choice

Nothing holy about it

[uncut raptor]

soo if I choose k instead of k+1 it was fien?

[nimble mist]

No

I was referring to the choice to make it pairs

To define the X_j's with pairs

instead of subsets

The indices are important there

[uncut raptor]

uhh I feel like I am missing some steps can we start oover agian

[nimble mist]

Yes, ask your question

[uncut raptor]

okay so let's start wwith defining the set

so Iunderstand why A is defined liek that

but what was the reason for k+1

for disjoint I know

but like

why specifically k+1

[nimble mist]

why not k?

because you start with index r

And if you followed the "maximum element" logic

we wanted subsets of size r+1, so the maximum element must be >= r+1

So k \in {r,...}

and we take k+1...

You could use k \in {r+1,...,} and use k instead of k+1

But then you would have A \subset N_{k-1}

[uncut raptor]

so k could possibly be in the set of A already?

k+1 can't since u are choosing from subset N_k with size r

[nimble mist]

yes

k could be in A

[uncut raptor]

ahhh

ookay wait

uhm

[uncut raptor]

what was this logic again

oh wait that's the next sentence u typed

[nimble mist]

yes

[uncut raptor]

okay so basically when defining set ua re already thinking ahead how to connect them

[nimble mist]

ye

That's reverse engineering this build

These definitions were engineered...

[uncut raptor]

wait what is that?

[nimble mist]

I mean... Someone defined it with something in mind

And that's what I'm trying to shed light on

What's the idea here

[uncut raptor]

ah okay

uhhm

but

I sitll have some questions

[nimble mist]

go ahead

[uncut raptor]

so u want X_k too be disjooint since if u think ahead u are gonna connect them by taking the union right?

[nimble mist]

you want disjoint sets so you can easily compute the size of the union

[uncut raptor]

wait noow I am thinking, isn't it smarter to first think howo to coonnect the 2 sets and then defining the sets

[uncut raptor]

ye

because of the sum rule

u can just add

the cardianlity

[nimble mist]

yep

Look you want to prove this identity

[uncut raptor]

I feel like it's soo hard to cme up this by urself

[nimble mist]

It's not that complicated to be honest

[uncut raptor]

maybe my thought proocess is incorrect

can u help me think the right way

[nimble mist]

You have an identitiy you'd like to prove

[uncut raptor]

yes

[nimble mist]

On the one hand (right hand side) you have something that can be thought of as the size of the subsets of cardinality r+1 (of a set of size n+1)

[uncut raptor]

ye defining that set is realy easyt

it's just B subset of N_n+1 with cardianlity |B| = r+1

[nimble mist]

Ok, now on the other hand you have a sum

[uncut raptor]

liek I know these 2 things

[nimble mist]

Of what? of subsets of cardinality r of the sets of size r,...,n

[uncut raptor]

ye and u add all those subsets

so it's basically

[nimble mist]

You are looking for a way to relate them

[uncut raptor]

thats the realy hardp art

[nimble mist]

Yes

[uncut raptor]

also wait

[nimble mist]

That's the hard part

[uncut raptor]

when u think at this part

u won't know the k+1 yet right?

[nimble mist]

right

[uncut raptor]

u will add the k+1 ad the relation part

all right

[nimble mist]

yes

[uncut raptor]

so like

how

doo I relate them now

if it's a easy identity I can think it in my mind

but

with these my mind gets error

[nimble mist]

It's just the fact that you can partiton the subsets according to their maximum element

That's the whole idea

[uncut raptor]

and how the partitioon of the subsets add to the right side?

can u by any chance give a like concrete example maybe

[nimble mist]

I'm starting with the right side

[uncut raptor]

yes

[nimble mist]

We partition it

Any subset there has a maximum element

So we cover all the sets...

[uncut raptor]

wait partitioon means seperating them right?

[nimble mist]

Partition is a mathmatical term

[uncut raptor]

so like how would u partition it?

[nimble mist]

a partition of X is a family of sets X_1, X_2,...,X_k

such that their union is X

[uncut raptor]

ooh

[nimble mist]

and they are disjoin

t

[uncut raptor]

okay so basically u have Y and u will partition it

to match the X_k?

[nimble mist]

You partition it, into sets that will correspont to the X_k's

And the way you parittion it is by the maximum element

all the sets with the same maximum element m will be in X_{m-1}

ofcourse this is a partition

right?

[uncut raptor]

so u relate the sets with the maximum element of the subsets f Y to X_{m-1}

is there like a small example oof this

[nimble mist]

{1,2,3,4}

subsets of size 2

[uncut raptor]

12 13 14 23 24

34

[nimble mist]

X_{1} = {{1,2}}

X_{2} = {{1,3}, {2,3}}

X_{3} = {{1,4},{2,4},{3,4}}

That's it

[uncut raptor]

wait how is X_{1} not {(1,2)}

[nimble mist]

According to their definition it is

They use pairs

I moved to subsets

it's the same thing

[uncut raptor]

ah okay

uhm

soo we know X_1 2 and 3 hoow we realte this to Y

[nimble mist]

With my definition

The union of X's is just Y

Because we started with Y and partitioned it

you can simply show that any element of Y is in the union of X's

and that the X's are disjoint

So with my definition you don't even need a function

You can simply show that Y = union{ X_k }

[uncut raptor]

wait I am seeing it holds for this concrete example

but now I am trying to think in general

but my mind can't kjeep up foor some reason

[nimble mist]

That's the best I can do...

[uncut raptor]

I really appreciate it tho

let me think for a sec maybe I get it in a minute

[uncut raptor]

I think I see it now,btw the () is from the X definitioon {} is from Y definition but it doesn't matter since u are trying to make a 1 to 1 relation

they are also bascially the smae thing

[uncut raptor]

also how did u get this idea to do this, because for every identity u need t see the idea but how do u find oout the idea

[nimble mist]

That's comes from nowhere

No method

Just creativity and logical thinking

[uncut raptor]

but that is the hardest part

[nimble mist]

indeed

if there was a method

it wasn't hard

[uncut raptor]

oh

wait u right

but can u give me like

like what waws ur thoughr proocess

to develoop the idea

to partition Y and usaw instatntly it will connect to X_k

like if this wwaws given

did u instantly saww

if I partition right side

it should end well

[nimble mist]

it comes with practice when you see a lot of such tricks

it isn't new to me

[uncut raptor]

u did a similair excercise where u had partitioon befoore?

[nimble mist]

Probably many

[uncut raptor]

hey I have a good way to remember this excercise, can I get ur advice to see if I fully comprehend it:

so what u are doing is matching a subset at the left side with a subset on the right side.
right side subset can be intrepeted as:

r+1 elements choosing from r+1 elements
r+1 elements chooosing from r+2 elements
... etc

left side subset can be intrepted as
r elements choosing from r elements
r elements choosing from r+1 elements
... etc

so if u add r + 1 on every set of the left side u get the exact same sets
by viewing n+ 1 Choose r+1 I got noow a new interpatatioon namely: r+1 chooose r+1, r+1 choose r+2 etc...
is this all correct? didn't wanted to ping u since u may be busy

[uncut raptor]

alsoo 1 more question about another excercise, why is this correct, x has m possibilities, y has n possibilities

[autumn bay]

still need help?

[uncut raptor]

ye if u could

[uncut raptor]

this one

[nimble mist]

Hi dude

@uncut raptor how's it going?

[uncut raptor]

hey, nice to see you back can u help me

[nimble mist]

Not sure I follow your logic here

[uncut raptor]

uhm so basically I count the amount of elements in the right side when partiotned and left side separately

[nimble mist]

In any case it wasn't what I was talking about 🙂

Let's deal with your new question

[uncut raptor]

all right

<@&268886789983436800>

[nimble mist]

Do you want me to try to explain their solution?

[uncut raptor]

wait I did think about an idea why it holds tho

[uncut raptor]

so x is element of B and B is iCm right

[nimble mist]

Following their solution or did you come up with a solution on your own?

[uncut raptor]

following their solution

[nimble mist]

I see

[uncut raptor]

soo knowing this hoold

[nimble mist]

Let me read their solution first

OK

[uncut raptor]

is it because x is element of B and B has every subset possible from mCm to nCm therefore n possibilities?

tbh when the summation is introduced sometimes I get a little confused

because then u gotta see a union of sets mapping onto 1 set

[nimble mist]

You have m possibilities to choose x from B

[uncut raptor]

ye

[nimble mist]

because B is of size m

But for B you have iCm

[uncut raptor]

ye

[nimble mist]

and for A you have nCi

So what's the question?

[uncut raptor]

whe n defining the function y can be seen as x

[nimble mist]

|X_i| = nCi * iCm * m

[uncut raptor]

without the same cardianlity I thouight

this part

y has n possibilites

x has m possibilites

right?

but maybe X_i has m possibilities for x but the union has n?

[nimble mist]

Well yeah the union

[uncut raptor]

I think I see the reason but not sure if it's correct

[uncut raptor]

it's because x chooses first from the first m elements choosen from b then m+1 elements chosen froom b etc

eventually B has all the elements from 1 to n?

if u take all the subsets of B

[nimble mist]

yes

[uncut raptor]

but the subsets of B are not disjoint then

oooh wait its' not needed

righ?

[nimble mist]

right

[uncut raptor]

like the subsets of B definitly has some overlapping elements since if u first choose m elements froom m and then m+1 alot of elements are like ooverlapping

but that doesn't matter

because X_i needs to be disjoint

[nimble mist]

yes

Indeed

[uncut raptor]

wait

why is it disjoint?

[nimble mist]

Because they have different A's

of different cardinality

[uncut raptor]

oh wait ye

each triple has to have the exact same element in the triple in order to be like different

like A and B and x has to be the same

in order to be the same right>?

[nimble mist]

true

for an element (A,B,x) to be in X_i and X_j

A,B,x must be the same

You got this...

[uncut raptor]

ye before I only knew the perspective of disjoint of 2 sets whereas the 2 sets has elements in it so every element has to be different, now I gotta go up a scale every set of sets has to have different pair/triple in order too be different right? I can basically see each pair/triple as an element if it's different pair(doesn't matter if some elements inside the pair are the same) it means not in the same set

[nimble mist]

yes

(a,b) and (a,c) are different elements

[uncut raptor]

ye

even though a are the same it's different

[nimble mist]

yes

[uncut raptor]

it's like a dice

[nimble mist]

= means equals in any way 🙂

[uncut raptor]

when u throw 6 and 2 it's different froom 6 and 4

[nimble mist]

(6,2) != (2,6)

[uncut raptor]

ye

[nimble mist]

also

[uncut raptor]

oh

I guess u can say order matters with it then

[nimble mist]

if we are looking on pairs

{1,2} = {2,1}

that's sets

[uncut raptor]

ah

[nimble mist]

() = order matters, {} = order doesn't matter

[uncut raptor]

wait so sets and pairs do differ on this part then right?

[nimble mist]

yes

[uncut raptor]

I see, I will continue with next excercise, will I eventually becoome good at this?

[nimble mist]

Sure

[uncut raptor]

like did u experienced the same back in the days

[nimble mist]

Don't worry! everyone does

[uncut raptor]

will u still be back for today

[nimble mist]

Just try to ask your questions, you can ping me.

[uncut raptor]

all right thanks!

[nimble mist]

yw

[uncut raptor]

hey I am doing this one now, but I am trooubling seeing why the relation is like this. A intersection N_n has a cardianlity of 3 right why is it 0 1 2 3. nvm I see it

[odd sequoia]

hello, need proof check (from Gallian, Contemporary Abstract Algebra, 7 Edition, Part 2: 4, Cyclic Groups). specifically, thinking of being too verbose in k > 0, k < 0 sections.

[rustic hazel]

Hello, I want to further understand the following property and I want to know if I can leverage it to compute computationally infeasible big inputs.

Let A(x) by the g.f. and B(x) = A(x^k), then 0 = B*((1-A)^k - (-A)^k) + (-A)^k

Context: Binary Partition Functions(series with repeated elements where n%2 = 1, a(n) = a(n-1)), https://oeis.org/A018819

To me it looks like we can create a generating function from A(x), that skips k values each term. But my interpretation can be completely wrong. Please tag me if you answer.

[uncut raptor]

I was doing this excercise and I am not understand wwhy x is there. the possibilites of x are n-k, y are k+1 possibilites. nvm I see it again

[uncut raptor]

do u see why this hold?

[wet folio]

Hello, I am trying to calculate this through but Im not sure if I am doing it correctly. Could someone hop in a call with me if possible?

[radiant gale]

What is a variant of horn clauses where multiple negative and positive terms are allowed (a1 & ... & an -> c1 | ... | cn)?

[forest palm]

I'm concerned about my solution . I would be happy for help😄

[cerulean radish]

Show your work

[little prism]

a proof at the very least should contain a conclusion of why whatever you wrote shows what you want

a disproof should give a counterexample

[uncut raptor]

Hello can someone help me at the last sentence of the relation of f, can u write C intersection(N_(n+m) \N_(n))

Nvm i see it

[wet glen]

I have no idea what I'm doing. I still attempted
Any help is appreciated

[agile magnet]

What is the roster method?

[wet glen]

It's where everything is in the curly brackets and separated by commas so like (),(),()....I think

[cerulean radish]

How do you have (1, 0) in a if clearly every string has to start with 0 in that set

[cerulean radish]

In b what do you mean by (0, 1) U (0, 1)?

[wet glen]

the final answer string. and by b.. that one is getting redone at the moment. I didn't understand what the rule meant at the time, when I was doing the homework so I guessed.

[wet glen]

This is the revised work plus I attempted them all

[fossil mural]

well () is normal brackets, not curly brackets

i think what they're asking for is basically just, a list

so for instance "the set of prime numbers less than 10" is {2, 3, 5, 7}

[analog tinsel]

I have a question regarding the chinese remainder theorem:

Given a system of equations $E_i : x \equiv a_i (mod ; m_i)$, where all $m_i$ are pairwise coprime it is always presented that $x = \sum_i (a_i \cdot M_i \cdot y_i) (mod ; M)$ where $M = \prod_i(m_i)$ and $M_i = M/m_i$ and $M_i \cdot y_i \equiv 1 (mod ; m_i)$

My question is , what is an intution for why the formula for x is exactly that ? I know how to calculate it but I have no good way to explain how someone could understand why the formula is what it is

[vital dew]

barış

[past rivet]

I think the idea is that M_i . y_i are like a basis?

They are congruent to 1 for exactly one m_i, and zero otherwise

[analog tinsel]

i had something like this in mind too but couldnt quite work out why it actually works

[past rivet]

well, if x is a solution to a_i, and y a solution to b_i

then x + y is a solution to a_i + b_i

there’s a kind of linearity going on here

which if i knew more algebra i could probably make precise

[analog tinsel]

lol okk

I will think about it a bit more

algebra is not my strongest point as well

[past rivet]

yeah i find it quite difficult

a lot of stuff that feels unmotivated

or sometimes even just intentionally obfuscated

[analog tinsel]

yeah

I think i got it now though

its what you said

we want a term $T_i$ for each $m_i$ such that $T_i \equiv a_i (mod ; m_i)$ and $T_i \equiv 0 (mod ; m_j)$ for $i \neq j$. if we have them then the sum over all T_i modulo M is always congruent to $a_i (mod ; m_i) for all i . Then we only need to figure out that that T_i has to be

[vital dew]

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

[analog tinsel]

thanks for your help

[wet folio]

baris

good job

[past rivet]

maybe there’s a way to express this with, like, Z-modules…

but again i am very much not an algebraist

[analog tinsel]

thanks

[analog tinsel]

i am not familiar with that term "Z-modules"

[past rivet]

i am barely familiar with that term

[analog tinsel]

lol ok

[vale cairn]

It is equivalently just an abelian group

There is a general notion of a "module" over a ring A. If k is a field, then a k-module is a vector space over k, and a Z-module is an abelian group. So modules are some nice generalisation

[vale cairn]

Okay I can explain this. Basically the idea is that you want to show that the map Z -> M/m_1 x ... x M/m_n you get by sending like x -> (x mod m_1,...) is surjective. But then it suffices to show that you can hit e_1 = (1,0,...,0), e_2,..., e_k/(0,...0,1) as then you can add up these guys to get anything

Then you have reduced the amount of work you need to do

[analog tinsel]

I see. thank you very much for your help !

I think I got it now

[weary tiger]

Is it possible to find natural solutions to:

3n²+9n+8 = 2k², k in N

What I thought of was doing the substitution n = p - (3/2), p in (Q^+)-N, to eliminate the 9n term for further simplification

which gives
p² - (2/3)k² = 41/12

But this is equivalent to saying:

12p² - 8k² = 41 which is clearly false so the sub fails

[weary tiger]

The original question though is trying to find three consecutive triangular numbers whose sum is a perfect square.

t_n + t_{n+1} + t_{n+2} = 3t_{n+1} + 1 = k²

And this yields the above quadratic

[twilit pendant]

In how many ways is it possible to distribute , n white balls (similar ) and n colorful balls (different from each other) to 2n cells such that in every cell max 1 ball

The answer is 2n!/n! I don't understand why it's not 2n chose n

Like we chose a place for white balls 2n chose n then left n chose n which is 1

[twilit pendant]

😱😱 wow so many answers I'm going to take hours to finish them

[neon harbor]

There are 2n! ways to place 2n balls, but you have to divide by the number of permutations of white balls, since they are indistinguishable. If the colorful balls are also indistinguishable then the answer would be 2n choose n

[analog tinsel]

hey together!
can somebody please tell me if they think this proof looks fine or is faulty ? I saw a proof for this proposition but it was a bit more complicated therefore I am unsure whether or not I am missing something here , because this seems quite simple and intuitive to me. thanks in advance

[little prism]

if your proof at no point mentions that p and q are prime then something went wrong

[analog tinsel]

I understand your point. But can you point out where exactly it breaks ? Because to me it still looks fine

[fossil mural]

well, substitute in some values with p,q not prime for which the final result fails, and see where the first incorrect step is

[analog tinsel]

I know I know I did that it fails

but I mean , where in my reasoning did I go wrong ?

[fossil mural]

...?

if you did that then you would know which step of your reasoning is wrong

because it's whichever step is the first false one

[analog tinsel]

lol thats true

[fossil mural]

i'm not just saying you can find a counterexample to the theorem statement, i'm saying you can then run the proof with that counterexample

[analog tinsel]

well yes, it seems to break at the third <=>

[fossil mural]

yep, so that's where the problem is

[analog tinsel]

no one moment

sorry

its the last one

the fourth

yep makes sense

now I see it

[fossil mural]

...ok i don't see that actually
what counterexample are you using?

[analog tinsel]

$30 \equiv 6 (mod ; 24) \iff 24 \vert (30-6) \iff 2 \vert (30-6) and 12 \vert (30-6)$

[vital dew]

barış

[fossil mural]

that doesn't seem like a very good example given that it's not a counterexample

[analog tinsel]

wiat

wiat

[fossil mural]

12 is indeed not prime but the conclusion ends up being true anyway

[analog tinsel]

one second

let me organize my mind

I am sorry

I understood it to be a counterexample since $30 \equiv 0 (mod ; 2)$ and we wouldve wanted congruent to 6 instead , no ?

[vital dew]

barış

[fossil mural]

well $30 \equiv 6 \pmod 2$ is also true, given that $6 \equiv 0 \pmod 2$

[vital dew]

bee [it/its]

[analog tinsel]

oh man were is my brain

sorry, give me a moment to think of another one

youre completely right of course

[analog tinsel]

do you have a proper counterexample ?

[fossil mural]

p=2, q=4, x=6, a=2

$6 \equiv 2 \pmod 2$, and $6 \equiv 2 \pmod 4$, but $6 \not\equiv 2 \pmod 8$

[vital dew]

bee [it/its]

[analog tinsel]

thank you

wait but

dumb question incoming

nevermind

but my argument works as an implication doesnt it ? So only from left to right

[fossil mural]

yes, if $x \equiv a \pmod {pq}$ then $x \equiv a \pmod p$ and $x \equiv a \pmod q$, whatever $p$ and $q$ are

[vital dew]

bee [it/its]

[fossil mural]

it's just the other direction that requires pq to be distinct and prime

[analog tinsel]

alright thank you very much !

appreciate it a lot

[pale monolith]

it is also true if p,q are coprime

[raven shard]

is my proof for this good

A intersection B = B. so (A intersection (B intersection C) = (A intersection C) intersection B) is a subset of (A intersection (A intersection C) = A intersection C)

[fossil mural]

well all of that is true but it's not really clear how you derived it and also the conclusion doesn't seem to be the same thing as the thing they asked you to prove

[raven shard]

A intersection B = B since B is a subset of A.
A intersection B intersection C = (A intersection B) intersection C = A intersection (B intersection C) = A intersection (C intersection B) = ((A intersection C) intersection B) which is a subset of A intersection (A intersection C) = A intersection C.

based off what was supposed I continued to add on to the conclusion to transform it into a true statement. The reason "((A intersection C) intersection B) which is a subset of A intersection (A intersection C) = A intersection C." is true is because on the left-hand-side there are more intersections than the right-hand-side

[fossil mural]

...well you're supposed to prove the actual conclusion, not find a different conclusion that's easier and prove that

a proof that $A \cap B \cap C \subseteq A \cap C$ is not a proof that $B \cap C \subseteq A \cap C$

[vital dew]

bee [it/its]

[fossil mural]

(and in fact that first statement doesn't even require the hypothesis that B \subseteq A, it's true for any three sets)

[weary tiger]

Following up to this, I found a nice paper that showed and justified the recurrence relation:

a_(r+1) = 10a_r - a_(r-2)

that generates numbers whose square is a sum of three consecutive triangular numbers.

a_0 = 1, a_1 = 8 would generate one infinite family; and a_0 = 2, a_1 = 19 would generate another disjoint infinite family whose union with the first is the complete solution set.

But hovering over the OEIS database, it seems to give a combined recurrence relation:

a_r = 10a_(r-2) + a_(r-4) with initial conditions a_0 = 1, a_1 = 2, a_3 = 8, a_4 = 19

I'm curious then how I would combine the recurrence relations into the one above

[weary tiger]

Pretty stuck on this one

[snow junco]

Of length 16 reduces many issues with going left and down

[kindred nymph]

@weary tiger have you ever heard of "stars and bars"

It's a technique for counting things like this in combinatorics.

[weary tiger]

Hint: ||Notice that you will have to take 8 rights and 8 ups in whichever order to reach from the lower left corner to the upper right corner.||

[rough herald]

this is stars and bars where each bin must contain at least one element, but remember that you can either start by going up or by going right

[twilit pendant]

i have something i don't understand

the question is
in how many different ways we can write a number from 3 digits and the digits should be different

the answer is 9* 9* 8

but the problem is why it's not 8* 9* 10

like he said from left 9 because 0 can't be so we have 9 second digit we are lift with 9 differant numbers ok cool 9 the last digit 8 ok cool that's correct i have no problem but also if we start from right not left we get the other answer which i wrote 8* 9 * 10 which is wrong but i think it's true

at least it should be the sum of both of them

[pale monolith]

If you start from the right then 021 is a valid number

Even though it has two digits rather than three

[midnight charm]

does someone understand PDA? I can t understand this one it asks "what is the sequence so the word 101100 is accepted in this automata

[twilit pendant]

no i consider the 0 in the first 2 right digits

like the first one from the right when i said 8* 9* (10) u see the 10 the zero is there

[pale monolith]

Right

But imagine I pick 1 for that position

Then I can pick 2 for the next position

And for the last position, you say there are 8 numbers remaining; these must be 0,3,4,5,6,7,8, so I can pick 0

This gives the number 021

[twilit pendant]

oh yeah

i got it now

thx

[uncut raptor]

when doing a combinatorial proof what is it the best way to tackle it. by thinking how to relate the two sets before u define the set? then after thinking of a way u try it and see if the functions defined are correct, if not u try another set?

[light sail]

If G is connected graph that doesn't have an induced sup-graph P3 then the graph is clique ?

[coral parcel]

Yes. You can argue fairly directly that any two nodes must be connected by an edge.

[upbeat fog]

could someone help me please

i have entered a new realm of braindead

3x^2 - x^2 = 2x^2

or am i tweaking

[upbeat fog]

nvm

i was being dumb 😭

[cerulean wind]

i usually try to tell a story first or try to reinterpret some already working interpretation by counting it differently.

this usually leads to a good idea of how to use functions and set theory to write up a more formal argument

[clear parcel]

My major is not related to math and I like math and I had some research on pre calculus my last subject was taylor series and I don't know what should learn after it I will be thankful you guys answer me

[brave rock]

Anything you like

[sick sonnet]

What is a potentially good approach for this one (iii)? I tried using the binomial theorem for (2+2), (1+3), (3+1) which gives the right side but it didn't lead to the left side.

[brave rock]

Hint: $2^{2n+1} = 2\times 4^n$.

[vital dew]

Boytjie

[sick sonnet]

yup I got it now

thx

[wet glen]

I'm not sure if that's what they were asking for part b.

[uncut raptor]

can u give examples?

[brave rock]

You indeed used proof by exhaustion to prove the claim, like the question asked

[wet glen]

Thank you for the clarification

[odd heart]

<@&268886789983436800>

[terse wyvern]

what if it's a marathon runner

[analog tinsel]

Hey everyone , I am trying to find out which bound in the independence number is better. Unfortunately I cant really find a clear argument to say that the first one is better. Does someone know if and why it is ?

1. $\sum_{v \in V} \frac{1}{deg(v)+1} \leq \alpha(G)$
2. $\frac{n^2}{4m} \leq \alpha(G)}$

where n = |V| and m = |E|

[vital dew]

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

[analog tinsel]

wait , this shouldnt work ? The first bound is supposed to be better than the second one. Does anybody see what I did wrong ?

[fiery patio]

Guys what's big O notation?

[pale monolith]

a way of expressing the asymptotic behavior of functions

[clear parcel]

Hey guys

[twilit pendant]

can i pass discrete course if i started studying today i have an exam after 18 days i'm starting from zero

everyday 4 hours

i don't know if u guys learn like my university in our discrete course we learn
Graph theory
combinatorics (everything like Inclusion–exclusion principle , Pigeonhole principle etc.. )
logic
functions
relations
Cardinality
recursion
Generating function
induction

[twilit pendant]

so can i ?

there's also that stupid catalan thing

[pale monolith]

Depends how much depth you go on the topics, how hard the exam is, what score you need to pass etc.

But probably not

That is a lot to cover in two weeks