discrete-math

[waxen dune]

Assuming the value 8 ≤ n ≤ k, each of the number 8, so on, k can written as the sum of 3s and 5s.

we have to prove the statement for n = k+1. Since 1 ≤ k-2 ≤ k

k+1 = (k -2) 3, the sum of 3s and 5s.

Thus, every number (n ≥ 8) are true

end

[quick folio]

I mean, the graph isomorphism just tells you that the two graphs are essentially the same

yes

well if the graphs are the same

then everything inside the graphs must also be the same

[quick folio]

try and prove this statement:

If (V,E) is a graph, (V',E') is a subgraph and f is a graph isomorhpism originating from (V,E), then the restriction of f to (V',E') is also a graph isomorphism.

[quick folio]

keep going down that line of thinking

good enough

[thorny crane]

im reading through this old paper on a guys generalization of sudoku, but im confused with the way hes using graph theory throughout the paper, especially whne he proves his first theorem.

when he says " finding a perfect matching on the bipartite subgraph G of B × I that contains only the edges ( p, k), k ∈ C p."

what does the tuple and B × I notation mean?

https://www.math.uci.edu/~brusso/provanAMM2009.pdf

i dont have much knowledge on graph theory, tho i have a friend whos helping me out on some bigger picture stuff. i just need to be able to explain this minimally in ab 2 weeks

[little prism]

its just normal set notation

B x I is the cartesian product of B and I

[trim thicket]

is there a way to figure out how to simplify f(x)?

g(x) is only equal to f(x) when x is odd

[thorny crane]

Oh so the edges are just sets containing two of those tuples?

Didn't know ab the Cartesian product thing thanks

[amber bramble]

is there a nice way to determine hamilton circuit with min weight or do u just have to try all options n see

[odd heart]

If you're referring to the Travelling Salesman problem, then there famously isn't a "nice" way: https://en.wikipedia.org/wiki/Travelling_salesman_problem

There are fairly reasonable ways of getting a solution that isn't very far from the optimal, though

[amber bramble]

https://tenor.com/view/monkey-pissed-mad-angry-furious-gif-4720563

thank u

i will check it out

brute force it is

[thorny crane]

Oh wait does this imply a digraph then?

If so ughhh I just spent way too long reading ab graph theory stuff just for it to be digraph stuff 😭

[quartz blaze]

how to solve this?

<@&286206848099549185>

[quick folio]

find the gcd with the euclidean algorithm, then reverse your steps to find the linear coefficients

[quartz blaze]

didnt get it

[static raven]

You can also just check which one gives you the right value, right?

[quick folio]

As the other guy said, the lazy way is to just check the options one by one

[bright iris]

44=21(2)+2
21=2(10)+1 this is euclidean algorithm now try to express 1= ?

[rough jungle]

Wikipedia says that the smallest possible treewidth is 1 but doesn't a graph with just one node and nothing else have a treewidth of zero?

[limpid coyote]

Nah, it's got a width of one.

Depending on your definition, an empty graph may be a tree in which case, you have a width of 0. But most people don't consider it a tree since it doesn't respect the |E| = |V| - 1 property.

[limpid coyote]

Cos just one vertex is a tree technically speaking. And it obviously has a width of one. Sorry, I probs shoulda explained that.

[lusty loom]

,,f(x) = \begin{cases}
0 &\text{ when $x=0$ }\
x! \sum_{n=1}^{\floor{\frac{x}{2}}} \frac{1}{(2n-1)!} & \text{ when $x$ is even, >0} \
x! \sum_{n=0}^{\floor{\frac{x}{2}}}\frac{1}{(2n)!} & \text{ when $x$ is odd}
\end{cases}

[trim thicket]

damn what a piece wise this did not occur to me

[vital dew]

Asteroid

[trim thicket]

tysm

[lusty loom]

You can replace the limits of the sums with x/2 when x is even and (x-1)/2 when x is odd instead of floor(x/2)

[primal glade]

Anyone online

[twilit sundial]

!da2a

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[twilit sundial]

this is a server of hundreds of thousands of people from around the world, surely someone is online

[last flicker]

sorry, just checked. Noone is online (except me) and I'm about to go offline.

[indigo cedar]

Hi all, I am confused by this exercise in this set theory book “The Joy of Sets”, and I’m starting to suspect it might have an error. I wonder if instead of “v_i is an element of y”, it should say “v_i is a subset of y”. One reason is that just above, the book defined the preimage of a function as taking a subset of the codomain as its input, not an element of the codomain (though, maybe here they implicitly mean the singleton set {v_i}). Another reason I am confused is that the union of all the v_i’s is a set of elements of the v_i’s, not elements of y! So how can the preimage of f take that set as input?

Even if I change to “v_i is a subset of y”, I’m still confused. Does the indexing set range across the full power set of y? If so then isn’t the union of all the v_i’s just equal to y? I don’t recall that indexing notation being established for subsets of a set yet.

[west hedge]

yes the v_i should be subsets of y

you're right that it is common to also use the notation f^{-1}(v) for v an element of y to actually mean f^{-1}({v}), the preimage of the singleton, exactly as you said. but this is not what's happening here

for the indexing set I, it can be any set. this is just a way to indicate a family of subsets of y. in particular, no, the family of subsets under consideration does not have to be the entire power set

[indigo cedar]

Okay thank you so much, that makes a lot more sense.

I did find an errata for this book online, but it didn’t mention this. Maybe I should keep a record of any other oddities I find in this book

[neat matrix]

Let X_n be the set of strings of length 2n in Dyck's language. Is there any efficient algorithm to sample X_n uniformly? Or, since computing Catalan numbers isn't too difficult, is there an efficiently computable bijection between {1,...,C_n} and X_n?

[rough jungle]

Why is this the case? If a graph has only one node, then the tree for it is just going to be the same thing, so the largest bag has size 1 which means the width is 0 right?

[hidden totem]

i have a naive solution, probably this could be improved slightly but not sure how quite yet

first notice that there is a bijection between the strings and a class of grid walks. if you treat each open bracket as moving down, and each closed bracket as moving right, this directly forms a bijection between the string and a grid walk from one corner of an n x n grid to the opposite corner, without ever touching the top-right half of the grid

now you just label each point with a number that represents the number of ways to get to that point, noticing a simple recursive relationship. a particular node is just the sum of the node to the left and top

(might be a few addition errors, i did this super fast mentally)

so to construct a string at random, uniformly, start from the end, and work your way towards the beginning

so let's say I start at the 429 in the corner, I can only move left, so I start by writing an open parentheses (i know this step is supposed to be a closed parentheses at the END of a string instead of an open parentheses at the BEGINNING of the string, but it's easy to see you can just take the reflection of all of the strings and it's the same thing)

now from here, I can either step left again, or step up, which would be writing an open bracket and closed bracket respectively

but the probabilistic weight of each of these is dependent on the node values

there are 247 paths coming from the left and 132 coming from the top, so the probability of an open bracket appearing next is 247/429, the probability of a closed bracket appearing next is the complement, 132/429

continue this way all the way up to the top to get your final string, uniformly chosen at random

this is equivalent to sorting all of the strings in lexicographical order and then bijecting them to a list, except we go one character at a time as we need, using casework, rather than write to memory the full list

this algorithm should be O(n^2) in time and space complexity, i think

[neat matrix]

Ah, thanks!

[neat matrix]

So, basically, we're walking over the recurrence that generates the Catalan numbers.

[hidden totem]

yeah

[primal glade]

Anyone online?

<@&286206848099549185>

[quick folio]

if you have a question just ask it

[primal glade]

How u prove it

[zenith monolith]

Odd degree, what does that mean?

[primal glade]

Like edges

D(v)=1 (degree)

[zenith monolith]

Huh??

[zenith monolith]

Use a help channel, i have no clue

[quick folio]

start with a graph with only even degree vertices. if you try to add one vertex with odd degree, what happens?

[quick folio]

1- you don't need that lemma,
2- using ai here is very frowned upon. i suggest you delete that post before anyone else notices

[twilit sundial]

!nogpt

[lofty cloud]

Please do not trust ChatGPT or similar AI tools for mathematical tasks, as they often generate output which "sounds correct" but has numerous factual or logical errors. Use of these AI tools to answer other people's help questions is strictly against server rules (see #rules).

[twilit sundial]

too late

😁

[zenith monolith]

I’m just trying to help out in something i’ve never studied

[quick folio]

doesn't change what i said, unfortunately

[twilit sundial]

scroll down literally 2 inches from the ai slop

[zenith monolith]

Ok, sorry, i was just trying to help

[quick folio]

you don't always have to help, it's okay to wait for someone that can answer better

[primal glade]

I was a bit confused about that part

Can u like demonstrate it?

[quick folio]

so right now we have a graph with only even degree vertices.

[primal glade]

I was confused with v and d

[zenith monolith]

If i can find a way to help i will do my best, and try to learn from it, its why i help

[quick folio]

I want to add one extra vertex to that graph, and I add the requirement that I also want the new vertex to have odd degree

what happens to the total number of odd degree vertexes in the graph

[primal glade]

Became odd?

[quick folio]

why?

[primal glade]

Bec even plus odd=odd

[zenith monolith]

But for an edge to form you need 2 connections, so 2 new odd vertexes are formed, right?

[quick folio]

no, there are more odd vertexes

[\begin{tikzcd}
\bullet & \bullet && \bullet & {\color{red}{\bullet}} \
\bullet &&& \bullet & {\color{red}{\bullet}}
\arrow[no head, from=1-1, to=2-1]
\arrow[no head, from=1-2, to=1-1]
\arrow[no head, from=1-2, to=2-1]
\arrow[no head, from=1-5, to=1-4]
\arrow[no head, from=1-5, to=2-4]
\arrow[no head, from=2-4, to=1-4]
\arrow[no head, from=2-5, to=1-5]
\end{tikzcd}]

[vital dew]

HChan

[quick folio]

notice that when the new point is added, you are also changing the degrees of the original vertexes

[zenith monolith]

So this is right?

[quick folio]

it can be more than 2

you don't know how many more edges I am adding

[zenith monolith]

Yeah, but either way it’s groupings of 2 right?

[quick folio]

good enough, now let the other person figure it out

[zenith monolith]

Wait what if you add another onto the right of the one just added?

Ohh wait nvm

[edgy canyon]

induction

take f(x_1) and prove f(x_a) for any a subsequent to 1

then expand f(x_a) to fit f(x1) and it's proven

[primal glade]

Wth

[edgy canyon]

hchan put you on the right track

you start with a line between two points

each odd degree

even number

add a line

[primal glade]

Means edges r?

[edgy canyon]

1 with two connections

two with one

so even number of odd degree

[edgy canyon]

jesse what the fuck are you talking about

odd degree here we'll take to mean the amount of connections using the point

if 1, odd, if 2, even

[primal glade]

Connection to edges

Ok

[edgy canyon]

now imagine the original dot had not existed

you're back to the original case

now go back to your case of 3 points 2 connections

if i add a connection between the 2 unconnected points

you will find they are all even degree

you've hit a dead end, ignore this path

now go to the other case

[edgy canyon]

if i add a 4th point

i can disregard the first point i started with

[primal glade]

Bro don’t swear pls

[edgy canyon]

and i end up with 3 points 2 connections, look at that

[primal glade]

Yeah

[edgy canyon]

so what we've just proven

is you can turn any case where you add points

and simplify it to the base cases

all of which have an even number of odd degree points

ta-da

[primal glade]

Can u demonstrate on a graph?

[edgy canyon]

it's midnight where i am, too tired to make a graph

you should be able to draw what i'm saying

[primal glade]

Ok

[primal glade]

Can I use contradiction to prove that too?

[edgy canyon]

probably not

[silent hazel]

proof. suppose evil man isn’t too tired to make a graph, this must mean that it isn’t late at night. however, it’s midnight, therefore it is late at night. this is a contradiction, hence evil man must be too tired to make a graph. $\square$

[vital dew]

Gyro

[rugged dock]

!yesgpt

!trustgpt

!lovegpt

!nogpt

[lofty cloud]

Please do not trust ChatGPT or similar AI tools for mathematical tasks, as they often generate output which "sounds correct" but has numerous factual or logical errors. Use of these AI tools to answer other people's help questions is strictly against server rules (see #rules).

[rugged dock]

Bruh

[edgy canyon]

✍️ 🔥

[stray reef]

and what were you trying to do exactly

[rugged dock]

#chill ?

[clear trout]

In b, why are {f} and {g} considered strongly connected?

To my knowledge, a strongly connected component is a path that leads back to itself so if f and g are strongly connected by themselves then wouldn’t every vertice be strongly connected?

<@&286206848099549185>

I’ll give 3 robuxs to anyone that helps me plsssss

[quick folio]

well yes, there's the empty path

[clear trout]

Wdym

How would I be able to tell if something has an empty path

[quick folio]

a path is a sequence of edges, so you just take the empty sequence

[clear trout]

So I kinda get how g would be one but how would f be one?

Since there’s a path from f to g

[quick folio]

yes but we don't care

because there isn't a way to get back to f from g

so they're not strongly connected

[clear trout]

Hm

That definitely helps thanks

Also I lied about the robux

[quick folio]

so you just start at a vertex v, do nothing... and you're back at v

so you just got from v back to v, so every vertex is strongly connected to itself at least

[clear trout]

Got it

[magic bronze]

Anyone familiar with drawing logical circuits

[stray reef]

!da2a

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[magic bronze]

I dont have a question I just need help understanding circuits

[silent hazel]

how so?

[royal arrow]

Is there a name for a 3d polyomino? Not, like, a polyomino made of cubes, but a polyomino made of squares which are the 2d faces of the 3d cubic lattice

(let me know if there's a more appropriate channel than this one)

[oblique pelican]

https://en.wikipedia.org/wiki/Polyominoid something like this?

[royal arrow]

aha

exactly

thank you

[random sparrow]

how does the cartesian product between sets work

how do I plot the cartesian product of two different interval

[oblique pelican]

The Cartesian product between sets A and B is just the set of all ordered pairs where the first element is from A and the second element is from B. So it's the set of all pairs (a,b) where a is in A and b is in B. The pairs are called "ordered" because the order matters: (a,b) != (b,a) (when a != b).

[twilit sundial]

its just ordered pairs?

really all it is is a fancy sounding name for smth you’ve been using since middle school

[oblique pelican]

It'll look like a square basically. Every point where the first number is from the first interval and the second number is from the second interval.

[random sparrow]

a rectangle

not necessarily a square

[oblique pelican]

Yeah sorry

[indigo forge]

@everyone

[silver jay]

i am taking discrete maths as a highschool senior next semester and ts is what i see 💔

what is ts

ts is not algebra 💔

[still vortex]

did you....think it was going to be algebra? 😐

[random sparrow]

two questions is AnC a proper subset of B
and is AnC a subset of B
A ∩ B = {(x,y) € R^2 | (-2 <= x <= 3 and 1 <= y <= 4) and (0 <= x + y <= 5)}
A U B = {(x,y) € R^2 | (-2 <= x <= 3 and 1 <= y <= 4) or (0 <= x + y <= 5)}
A = {(x,y) € R^2 | -2 <= x <= 3 and 1 <= y <= 4}
B = {(x,y) € R^2 | 0 <= x + y <= 5}
C = {(x,y) € R^2 | y = 2x}
A ∩ C = {(x,y) € R^2 | -2 <= x <= 3 and 1 <= y <= 4 and y = 2x}

yeah i think i got it now what you mean
proper subset means is a subset but is strictly not equal
and subset means every element in the first set is contained in the other
there are some points in AnC not contained in B
so it's not a subset
AnC is not entirely contained in B
so AnC is not a subset of B
and since AnC is not a subset for B then it's not either a proper subset
since to be a proper subset we also need that is a subset aswell

[silver jay]

yes

[humble swan]

I am

[true venture]

Is there a way to keep track of pairs of equal adjacent parts in multiset permutations?
For example the multiset {1,1,2} there are 3!/(2! 1!) = 3 Permutations. but if you keep track of equal pairs with say a variable y, you get the refinement of three permutations 1 + 2y.

[limpid coyote]

Idk if this is too late of a reply. But can you clarify what you mean please? It could just be my caveman brain, but I can't figure out what your actual question is.

[true venture]

So given some multiset or colection of numbers how can you find the number of permutations with k pairs of equal adjacent parts.

[true venture]

This is would be similar to some q-multinomial thing.

[limpid coyote]

I mean would you not just permute the pairs as one element?

[true venture]

yes, given some set you can find them like that.

but what I was hoping was there was some general way becuse If you have a set with many differenent repeated elements like {1,1,1,2,2,3,4,5,5,6,6,6} there are many pairs

[limpid coyote]

Are you considering each element of a pair as distinct elements?

If so, you'd just multiply the number of permutation by the number of ways to permute the elements in the pair.

[true venture]

No repeated elements are not distinct

The idea is to take some multiset S and find the number permutations of S with k pairs of equal adjacent parts for all possible k.

[limpid coyote]

Yeah, okay. Then that's easy. It's just basic counting, just permute all the elements while keeping equal pairs together 😍

[true venture]

I guess that's what I was thinking, But how to figure out all the different arrangements of pairs?

[limpid coyote]

Yeah, it's just (n-k)! Where n is the number of letter, and k is the number of dupes.

[true venture]

I don't get it lol.. Say the multiset is S ={1,2,2,3,3} how would I find the expansion I'm after?

[limpid coyote]

What do you mean the expansion you're after? Aren't you trying to find the number of permutations?

[true venture]

Yes, while also tracking the number of pairs equal adjacent parts in each permutation not the original multiset

So say use y^k for a permutation with k pairs of equal parts. The expansion for S= {1,2,2} would be

y^0 + 2y^1 for the 1 permutation 212 with no equal pairs, and 2 (122, 221) with a single pair

The sum of the coefficients will be 3!/(2!)

[limpid coyote]

Look, maybe I'm misunderstanding what you're saying, but to me it just seems like a counting problem. Try writing it in cycle notation, what you're trying to do now seems unnecessarily complicated and using more obvious notation should help. That's my last piece of info, sorry. I don't have anything else for you.

[true venture]

Lol yes it is a counting problem

[true venture]

Ok no worries, thanks for chatting about this.

[hidden totem]

oh i see, you want the generating function for a multiset with k pairs of adjacent elements that are equal

lemme check if im understanding it:

{1,1,1,2,2}
should give you 10 permutations:
1 of which gives no pairs (12121),
4 of which give 1 pair (11212, 21211, 21121, 12112),
3 of which give 2 pairs (11221, 12211, 21112)
2 of which give 3 pairs (11122, 22111)

so you should get

1 + 4x + 3x^2 + 2x^3

is that right?

[true venture]

Yes

[rocky karma]

hey

i would need some help if its possible

with linear recurssive homogeneous equations

[true venture]

ask away

[muted pumice]

how do you know the area is σ * √2 from the graph?

[hidden totem]

man this is actually weirdly hard

hmmmmmmmmm

[true venture]

I was more wondering if it was some known thing. But I have no reason to beleive there would be an easy way to do this. Looking at other things there are several q series q-multinomal things similar to the q-binomial theorem I found.

Which is the most relevant direction I see

[hidden totem]

fair, but im also not convinced there isnt an easy way to do this

[true venture]

I mean that would sweet

[hidden totem]

yeh

[true venture]

Also I forgot why i thought of this, I had something I wanted to do with such a expansion

[gentle sandal]

I did with double counting but i am sure about results what do you think is the best idea?

[cunning elbow]

Hi

[ornate timber]

Hi guys. I'm new to discord.

[true venture]

Welcome to the discrete math page

[true parcel]

Is your name german

[oblique pelican]

German doesn't use ï

[true parcel]

But Godel tho

He has those 2 dots on top of o

[oblique pelican]

Ye they use ä, ö, and ü

[true parcel]

Ah

Did not know that, thanks

[silent hazel]

french uses ï occasionally

ex. maïs

[chrome sand]

Hello

Let f : A → B and g : B → C be functions.
Show or disprove:

• If g is injective, then g ◦ f is also injective

I want to find a counterexample:

I took g: Z -> Z : x -> x (which is injective)
f: Z -> N : x -> x²

g(f(2)) = 4
g(f(-2)) = 4

therefore its not injective since x_1= 2 /= -2 = x_2 , but g(f(x_1)) =g(f(x_2))

Is this correct?

[woeful pulsar]

Chat is the answer 21? I used stars and bars

999999 satisfies this condition, and the smallest number satisfying this condition is 999988, and from there it's just a matter of counting how many ways to arrange 2 objects (the 8's) in 6 places (the rest of the places can be filled with 9's

[hidden totem]

you can rigorously check your answer to counting problems by showing both that you have not overcounted and have not undercounted

if you can justify both of those you can be confident your answer is correct

[cunning elbow]

No

[woeful pulsar]

what is the answer?

[woeful pulsar]

I see

how would I do that

[cunning elbow]

28

[woeful pulsar]

how?

[hidden totem]

the numbers you counted, realize that you definitely have everything that is at least 52, so this shows that you didnt undercount

[woeful pulsar]

hm alright

[hidden totem]

overcounting could be due to duplicated counts (this can be shown to be impossible because the way you distribute the balls in boxes gives you a unique number and can be reversed) or counting something you should not have counted (all of the numbers you counted can be shown to be valid)

[cunning elbow]

First number is 999999, six numbers with one 8, six with one 7 and 15 with two 8s

[hidden totem]

ohhhhhh

yeah hes right

[hidden totem]

so this was wrong because you didnt count things like 999999

you counted where the sum of digits is exactly 52 not at least 52

my b

[woeful pulsar]

Oh that's true!

[woeful pulsar]

oh right I undercounted

by a lot

[woeful pulsar]

yea RIP

[hidden totem]

yeah so do the thing i said about checking in the abstract but actually go through the steps without making mistakes

[woeful pulsar]

[woeful pulsar]

well I did count 999999, since that's included in stars and bars

I just left out the ones with the 7s

since my "objects" were only 8s

[hidden totem]

ooooh might want to check that reasoning

[woeful pulsar]

[cunning elbow]

What does your bio mean

[woeful pulsar]

which part?

[hidden totem]

so which ball distribution corresponds to 999999

[woeful pulsar]

| | | | | * *, here the stars are the 8's and the bars are the possible places for the 8's to go into

so none of the places recieve an 8

it's all 9's

[hidden totem]

i think thats 999997

[woeful pulsar]

There is no 7 in consideration though

[hidden totem]

the ball is a -1 to the digit, not an 8

[woeful pulsar]

huh?

[hidden totem]

counter question, what is * * | | | | |

[woeful pulsar]

889999

I'm talking about this one btw

https://discrete.openmathbooks.org/dmoi2/sec_stars-and-bars.html

[hidden totem]

then what is * | * | | | |

[woeful pulsar]

oh wait no

* * | | | | | should be 899999

[woeful pulsar]

this is 889999

[hidden totem]

ok then what is 999997?

[woeful pulsar]

There is 7 under consideration

that was the mistake

I only considered 8

[hidden totem]

oh right sorry my question should be what is 999998

[woeful pulsar]

| | | | * | *

[hidden totem]

you said that was 999999

[hidden totem]

then what is 999988

[woeful pulsar]

| | | * | * |

[hidden totem]

keep going, match 999889

all the way to 889999

you will notice they dont line up

[woeful pulsar]

I see

[hidden totem]

you should rigorous describe your matching rule

syou have a messy concept of what the two balls in a bucket covers

[woeful pulsar]

I just learned the matching rule 20 minutes ago

[hidden totem]

yeh

let me put it this way

[woeful pulsar]

But yea I'll try to do that

[hidden totem]

it is way easier to just say

the ball represents -1 to the bucket

so putting both balls in the first bucket is therefore 799999

the reason why this method is so nice is because

if you do it this way, you still need to count cases for digit sum of 53 and 54

however, now there is a trick so that you dont have to split into annoying cases

you have 6 buckets, one for each digit

include one more "trash bucket"

all cases covered, done

[woeful pulsar]

I see

[woeful pulsar]

what I did was, the balls represented the two 8's, and putting both balls in the first bucket, * * | | | | | would be 899999

[hidden totem]

its not wrong to do it this way, it just doesn't generalize nicely

[woeful pulsar]

But yours seem to include all of it

yeah

I just saw 999988 satisfied the condition and ran with it

without considering 999997

I'll try your ball represents -1 to the bucket

[hidden totem]

yeah, this is the counting equivalent of geometry's "it looks right so it's right"

[woeful pulsar]

me proving the Jordan Curve Theorem be like

[woeful pulsar]

@cunning elbow @hidden totem thanks btw

[livid gust]

looking for a tutor for discrete math

5-6 hours a week helping me go through my lessons

paid^, dm if interested

[muted basin]

i dont understand the proof for this

why does x + y + 1 = n + 1

maybe i am misunderstanding what it means to be an internal vertice

the x+1 and y+1 sort of makes sense to me, bc if G has n+1 leaves then any other tree should have that but with a diff variable

[oblique pelican]

It's saying that the tree with n+1 internal vertices has 1 root (which is an internal vertex), a subtree to the left with x internal vertices, and a subtree to the right with y internal vertices. So in total there are n + 1 = x + y + (root) = x + y + 1 internal vertices.

[hearty belfry]

do you guys any recommed book discrete mathematics book?

im finding topic like propositional , first order logic and sets, relation and partial orders, lattices, monoids,groups, graphhs ,combinatorics, recurring relations and generating functions

[viral hound]

Discrete Mathematics and its Applications by Kenneth Rosen. I haven’t used it personally, but I was looking through the table of contents and some of the chapters yesterday and it looks pretty good, and it’s the textbook my university uses for discrete. It has most of what you’re looking for and a lot of other really interesting topics like algorithms and formal grammars

[oblique pelican]

Yeah Rosen is a very popular discrete math textbook

[dire pendant]

Hey there any good resources for sets operations and direct proof on sets?

[dire pendant]

Do you have it as a pdf?

[viral hound]

If you look it up you can easily find one

[dire pendant]

Thx

[viral hound]

My uni uses Book of Proof by Richard Hammack and again a PDF is available online, it has what you’re looking for

[dire pendant]

Gonna go for it
Thx again

[plucky wedge]

trying to understand why the two formulations for the axiom of pairing in set theory is equivalent

I see why strong implies weak

and does weak imply strong becase we can use the axiom of specification on weak pairing to get strong pairing?

is that how that works?

[plucky wedge]

I just started that book like just now lol, do you enjoy it?

[viral hound]

I thought it was good. I didn’t physically read it but the class lectures heavily followed the book

[plucky wedge]

oh ok thats good

Also why do they say (*) is a psuedo-special case of (**), why is it not the other way around?

[coral parcel]

Yes. They are equivalent in the presence of Specification, but not necessarily without it.

[coral parcel]

It is not terribly well written -- for example I think it's doing the reader a disservice by omitting the "for all x" that MUST come in front of (*) and (**) in order for them to make the correct sense.
I would advise not getting too hung up on what that book calls a "pseudo-special case" of what -- that is not standard terminology anyway. The key principle here is that ZFC has many axioms of the general shape
$$ \exists B : \forall x : x\in B \iff \cdots $$
where the $\cdots$ is some formula that may mention $x$ and possibly other parameters but does not mention $B$.
In the case of Pairing the $\cdots$ must have the shape "$x=a \lor x=b$"; in the case of Specification it can be anything that starts with "$x\in a \land \cdots"$ and doesn't mention $B$.

[vital dew]

Troposphere

[coral parcel]

Intuitively we might want to declare anything of the form above to be an axiom no matter what the "..." is (that is called "unrestricted comprehension"), but unfortunately some of those turn out to lead to contradiction such as Russell's paradox. So the main job of ZFC is to single out a repertoire of "safe" forms of "..." that we believe won't lead to contradictions.

[plucky wedge]

Thank you for the information, that made sense, ill add it to my notes

[crimson hemlock]

can somone maybe give a hand with (b). i dont have any direction in mind. thanks!

[agile magnet]

does the proof for A \cap [1, 2] change if you want to show that A \cap [2, 3] is countable?

what about A \cap [3, 4]?

use this to partition A among a countable cover of R^+

[plucky wedge]

continuation of this part, I don't see what they are trying to get at from the first sentence of the second paragraph

I dont think they ever mentioned anything about an element appearing in a set twice before this. I might just be overcomplicatnig things and confusing myself but isnt there only one set a from the axiom of extension, if so what does {a, a} mean?

They are saying this set with two elements only has one element?

[coral parcel]

By the preceding discussion, what the notation {a,a} means is nothing more or less than
the set B such that x is in B if and only if x=a or x=a.

That is, by pure logic, the same as
the set B such that x is in B if and only if x=a.

[plucky wedge]

ohhh

that makes a sense thank you

[coral parcel]

So the underlying point here is something like "we don't need a separate axiom to tell us that {a} exists, because Pairing will do the job for us if we turn it the right way".

[plucky wedge]

ahh I see

I need to get better at extracting information like you from these text

I think I'm gonna stop reading after this section and read the second chapter in book of proof on logic since it seems it might be useful to know when reading this

[coral parcel]

My secret here is that I know the stuff already, I don't need to extract the information from that text ...
The author here seems to make a very brave choice to start discussing axioms at so early a time that he/she still needs to explain to the reader that Ø and {Ø} are different sets ...

[plucky wedge]

oh ok, hopefully after gathering enough information I can pick up the pace on the reading this book

thank you for the help

[sacred lotus]

order of coloring is giving me different chromatic polynomials

e, f , c ,a, b , d gives n(n-1)³(n-2)²

e,d , a , b, f , c gives n(n-1)(n-2)⁴

at each point of coloring I am writing how many colors are available

[coral parcel]

So your two polynomials claim there should be either 24 or 6 ways to 3-color the graph. Perhaps try working out some colorings explicitly to see if there are really 24 possibilities ...

Your basic mistake, I think, is that you're assuming "how many colors are available for this new node" depends only on which nodes you have colored so far, and not on how you've colored them.

Take for example your "e, f, c, a, b, d" ordering. By the time we get to a, we'll have n-1 choices if you chose the same color for e and c, but n-2 choices if e and c have different colors.

Your choices for finding the chromatic polynomial here are either to use something systematic like the deletion-contraction recurrence (which will probably take up a fair amount of paper even for a graph as small as this), or to find a clever ad-hoc way to count colorings specific to this graph.

My approach would be to split into cases according to whether a and f have the same or different colors. In each case, once you've colored a and f, what remains to color the path graph d-e-b-c with either n-1 or n-2 colors -- and the chromatic polyomial for a path graph is easy to write down. This works because each of a and f happens to be neighbor to all the four other nodes.

[flat lintel]

I can't believe there's a discrete math channel! Discrete math gets so few love because it doesn't appear either in math because it's more of a computer science thing or in computer science because they care more about programming😅

[sacred lotus]

thanks I now understand

[plucky wedge]

I think the wording is tripping me up a bit here, is the second part saying that for any two sets there exist three sets, one containing element 1, another containing element 2, and the last containing element 1 and 2?

no its not saying that

I understand the first part but the second part is confusing me

"any two sets are simultaneously elements of some one and the same set"

what is "some one"

[quick folio]

"any two sets are simultaneously elements of some one (set) and (that set is) the same set (for both of them)"

[plucky wedge]

what does simultaneously mean here

[quick folio]

given any two sets A and B, there exists a set S that contains both A and B as elements

or in other words, if A and B are sets then {A,B} is a set

[plucky wedge]

I think the wording is just tripping me up, I thought that at first but arent they saing the same thing twice then or am I misunderstanding

couldnt it be said like any two sets are both elements of some one set, why do they specify that it is the same sset

maybe my english is bad

[quick folio]

lol no, the wording is confusing here

it's saying that two sets A,B are simultaneously:

• elements of some one set S, and
• S is the same set for A and B

[plucky wedge]

ohh I see

though I still dont see why the second part is there because wouldnt saying they are elements of some one set S already imply that S is the same for both of them

[quick folio]

so the first point says that {A,B} is a set, and the second point says that {A,B} = {B,A}

[plucky wedge]

oh is that what its saying

[quick folio]

it's true, but not immediately true

it's saying that, from the perspective of A, looking at B, A knows that there is a set S that has both itself and B.
Equally, from the perspective of B, looking at A, B knows that there is a set T that has both itself and A.
but, a priori, there is no reason for us to know that S and T are the same set - after all, one is from the pov of A and one is from the pov of B

but it essentially boils down to saying that the universal quantifier commutes with itself

[plucky wedge]

oh wow I didnt think that deep into it, it makes sense why its specified now

[quick folio]

here's an example of how this symmetry can fail:
given two sets A,B, let's call S_A the smallest set that contains all of A, and some of B.
now let's suppose that A = {1}, and B = {1,2}.
Then the smallest set S_A that contains all of A and some of B is {1}; but
the smallest set S_B that contains all of B and some of A is {1,2}

[quick folio]

yes, foundational ZFC set theory is extremely specific in its statements and logic

[quick folio]

but fundamentally all that is just a roundabout way of saying {A,B} = {B,A}

[plucky wedge]

ah I see, thank you for helping me understand the meaning

[plucky wedge]

im so confused on what this exercise is asking

what I think its asking just doesnt make sense to be a question

distinct here means for any two sets they are distinct if atleast one element is not in the other?

ohhh

just looked up distinct

ok I had the wrong assumption of distinct let me retry

is this the right definition of distinct here?

waitttt nvm

is says distinct from one another

[plucky wedge]

so does that go back to this defintion?

[quick folio]

just... no two sets are equal

thats it

[plucky wedge]

oh ok ill try thinking up of a way to show why its yes or no

[plucky wedge]

ok I think im confused on what they mean by "this way"

[quick folio]

I thought about it a little and it seems to be pretty hard actually

[plucky wedge]

are they restricting us to start from singletons and build up from there?

maybe im just confused as a whole, what are the sets we are considering at the start?

because if I take sets a, b, {a,b} I can show its no

but I dont think thats what they are asking

[quick folio]

first we construct the collection of sets C0 {∅, {∅}, {{∅}}, {{{∅}}}, ...}.
from that, we construct the next collection C1 by pairing elemets of C0 together, so {{∅, {∅}}, {∅, {{∅}}}, {{∅}, {{∅}}}, ...}
next you construct C2 by either

• choosing from C1 twice; or
• choosing from C0 and C1
  we're specifically disallowing C2 to choose from C0 twice because that would be an obvious repeat
  so you iteratively construct C4, C5, C6, ec cetera, where you allow all pairings except for the ones that you already did in the previous ones

[plucky wedge]

ok so were using whatever combination of sets in that set to build up from

[quick folio]

not whatever combination, there's a little bit of nuance

see above ^

so the question is, is there any repeat at all among C0, C1, C2, C3, C4, ....?

and that does sound pretty hard actually

[plucky wedge]

hmmm ok Ill give it a shot

[plucky wedge]

by this are you saying if there is any element in for example C2 that is in C1?

[quick folio]

pick any random nonnegative integer i and j.
next pick any random element of Ci and Cj.
prove that those two elemets are always different

[odd heart]

If that's the Google AI overview, then I'd treat those with great caution.

They very often confidently provide incorrect information.

[coral parcel]

Just the beginning "a distinct set is ..." pretty much guarantees that whatever follows will be nonsense.

That's on the level of "G is isomorphic but H isn't".

[odd heart]

<@&268886789983436800>

(also spamming this in other channels)

[dire pendant]

Can someone help me finding the preorder search for this tree?

[stray reef]

!status

[lofty cloud]

What step are you on?
1. I don't know where to begin.
2. I have begun but got stuck midway.
3. I got an answer but I was told that it's wrong.
4. I got an answer and would like my work checked.
5. I have a question about someone else's work/solution.
6. I have completed the problem and don't need help anymore. Thank you.
7. None of the above

[dire pendant]

3

[dire pendant]

💀

[stray reef]

ok, show your answer and how you got it

why the skull react

also what's the letter on the bottom-most node that got cut off?

[waxen dune]

First thing, do you know what is preorder of the binary tree?

[agile magnet]

probably an a

[waxen dune]

I think I am agreeing with you

[dire pendant]

how can I find binary operations features on finite sets using the table only without taking all posible outcomes, such as inverse, identity element and commutitive

[scenic mesa]

if there's an identity element you will see 12345 in some row and column

if it's commutative it will be symmetrical about a diagonal line going down and to the right

[stray reef]

commutativity can be tested by looking at if the table is symmetric across the diagonal

[little prism]

if only someone had written that already

fwiw, associativity is very hard to tell from a table. so if you have to check that, good luck

[royal roost]

Can someone pls explain why the Axiom of Choice exists? I mean to me it seems like a very obvious thing. If I'm not wrong it just says that from a set of non-empty sets, it is possible to pick one element from each set.
But doesn't this literally just follow from the definition of non-empty set?

[odd heart]

Axioms are supposed to be obvious, that's their purpose.

You can't prove an axiom, it's your starting point to prove other things, so it should assert something that ought to be self-evident

And no, it doesn't follow from the definition of a non-empty set

Nor indeed from any other ZF axiom, which is why it's included as an additional thing, because it's indeed an obvious thing you want to be able to do

[grand totem]

Picking an element from a single non-empty set is unproblematic, the underlying logic and the fact that this set is non-empty allows us to do that. By induction one may prove that picking elements out of any finite family of non-empty sets is doable without choice as well.
Where choice becomes necessary is when you have to pick out of an arbitrary (possibly infinite) family.

[odd heart]

But to be able to do something in an axiomatic theory, it must either be an axiom or follow from the axioms.

[odd heart]

Also this; you don't need the axiom of choice to pick an element from one set.

[royal roost]

Oh I see this makes sense

Thanks

[little prism]

and also, initially it was very obvious. it took some time until people realised that it was even a thing they have to spell out. mostly cause it has some weird consequences

[royal roost]

can u give an example of such consequences?

[little prism]

banach tarski

[royal roost]

will look into it

[dire pendant]

can you modify more please still didn't get ite

[stray reef]

hmmm have you worked with matrices at all

[plucky wedge]

from what I learned I was under the interpretation that the union of a collectiong of sets is the set that contains all elements from each set, but that doesn't seem to be the case?

or maybe im misunderstanding

because they then say by the axiom of extension the union of a cet is unique but that couldnt be if the union isnt defined as containing all the elements belonging to each set

maybe I just have to read some more and itll make sense

[final cliff]

I think you are misunderstanding the wording of the axiom but you get the idea of what the axiom is for. There are several ways to word this axiom. The way they've chosen to do it doesn't immediately give you the existence of the union. It gives you the existence of a set that will end up containing the union however. This allows you to uniquely define the union with a little effort using the specification axiom.

I guess one way to think of it is that this axiom gives you a set bigger than the union and specification lets you whittle it down to exactly the union.

[clever wolf]

is it just

[final cliff]

Btw notice how the union axiom tells you SOME set exists. Possibly more than one. You can show logically that this is no problem to the uniqueness of the union with a bit of unwinding of the definitions and logic

[final cliff]

I'd say so yeah

Unless your tree/subtree definition has some weird caveats that explicitly forbid this.

[plucky wedge]

I think im still a bit confused, so by collection of sets lets say they mean A = {a, b}, B = {c, d}, C = {e, f}, by the axiom of union there exist a set F such that F = {a,b,...} or {c,d,...} or {e,f,..}?

[plucky wedge]

ohhh

hmm

ok so by the specification they added does that mean F can now be F = {A,B,C} or F = {A,B} or any other combination of A, B, C

since it doesnt specify F needs to contain every set in the collection

so wouldnt that make all of those sets a union

wait

I dont think what I said intially is right

I wasnt thinking of the elements

[final cliff]

The union axiom is being used to construct unary unions. So for ex U{A,B}={a,b,c,d} is what we want. But the way the axiom is stated it tells you that a set containing a,b,c,d exists AND ALSO possibly more stuff.

So for ex the set containing {a,b,c,d} given by the axiom could be {a,b,c,d,empty set} rather than the exact union of A and B.

[plucky wedge]

oh ok so saying "set that contains atleast one of the sets" doesnt exlcude the set that contains both but includes it, so by the axiom of extension it says there exist {a,b,c,d}, {a,b}, {a,b,c}, {c, d}... ?

[final cliff]

I think you are misquoting the axiom.

[plucky wedge]

maybe I am 😭

Im not seeing why the axiom doesnt say {a,b,c} exists but it says {a,b,c,d} exist

[final cliff]

"For every collection of sets, there exists a set that contains all the elements that belong to at least one set of the given collection"

Sorry just copying it here for reg

[final cliff]

It can give you both of these

[plucky wedge]

oh ok

yeah thats what I thought so how come when adding the axiom of specification they give we only get {a,b,c,d}?

I might be misunderstanding something still

[final cliff]

The set from the union gives you a set containing {a,b,c,d} it doesn't have to give you the exact set {a,b,c,d} itself. It can give you a bigger set.

[plucky wedge]

hm yeah I understand that part

and also a smaller one right

[final cliff]

No

Well sorta

[plucky wedge]

smaller than {a,b,c,d} like {a,b,c}

[final cliff]

You can build up smaller sets

[plucky wedge]

oh you said union here not axiom of union mb

[final cliff]

But if you're applying the axiom to A and B from here you won't get a smaller set.

[final cliff]

I meant from the axiom

[plucky wedge]

hm ok ill let you finish and then ask any questions

[final cliff]

Say I'm the axiom and you give me A and B. I have to give you a set that contains {a,b,c,d}. I can give you {a,b,c,d,10000000,fish,bob} according to how the axiom is written. But I can't give you something like {a,b}.

[plucky wedge]

wait why

a,b is all the elements in A

[final cliff]

Okay, but we are applying the axiom to A and B

I.e. to {A,B}

If we just apply it to {A} then sure

[plucky wedge]

so C = {A, B} if were using the C in the axiom in the image

[final cliff]

Yep

[plucky wedge]

and X can be A or B

from the axiom

[final cliff]

Yep

[dry moon]

Daily reminder axiom of abstraction is dumb but lowkey helpful for learning n using set theory

[plucky wedge]

can you try explaining to me why the axiom says {a,b} doesnt exist?

what condition does it not satisfy

A is in C

[final cliff]

It does say it exists.

You have to apply it/other axioms correctly to get that though.

[plucky wedge]

but the axiom of union alone doesnt say it exist?

[final cliff]

Yeah I would say it doesn't give you it by one application of this form of the axiom.

[plucky wedge]

I dont really see how thats possible, {a,b} to me seems like it meets all the requirements stated in the axiom

A is in C, {a,b} contains all the elements in A, and by the axiom alone it should exist?

[final cliff]

Okay, so you take the sets A={a,b}, C={A} and you apply the axiom to C, suppose the axiom gives you the set {a,b,c}. This is not the set you want. Now what?

[plucky wedge]

you apply specification to say that x should come from one of the element in C to get {a,b}

[final cliff]

Okay, but now you've had to do something else besides just using the axiom.

The axiom of union in this form doesn't tell you {a,b} exists in one step. It kinda forces you to take a second step in this case.

Which is nbd

It's still pretty immediate.

[plucky wedge]

oh maybe I was confusing you with my questions earlier, I get that it can give us a set containing elements not belonging to either and we need to use specification in that case, but I dont understand why if C={A,B} the axiom alone doesnt say {a,b} exists

[final cliff]

This is a different case still.

The axiom tells you a set containing the elements of A={a,b},B={c,d} exists. So for ex the axiom can give you {a,b,c,d,e,10000000000000000,13}. Now what?

Well you'd have to use specification again.

Like before.

It's not that you can't get {a,b}. It's that you have to take more steps after axiom of union to do it.

You might say, well what if I use C={A}, but that was the case we just talked about and we still needed to use specification rather than just union alone.

[plucky wedge]

it says a set containing the elements of atleast one of those sets exist right

[final cliff]

It depends on what C is.

[plucky wedge]

say we use C={A,B} like here, then all elements in at least one of the sets means only A elements, only B elements, A or B elements, A elements + extra, B elements + extra, A or B + extra elements right?

[final cliff]

Idk what you mean by that

[plucky wedge]

all elements in atleast one of the sets in the collection, wouldnt either of those sets above satisfy that

{a,b}, {c,d}

{a,b,c,d}

[final cliff]

I think you are misreading the axiom.

One sec

"For every collection of sets, there exists a set that contains all the elements that belong to at least one set of the given collection"

The collection of sets in this case you mentioned is now C={A,B}

The axiom says there is a set D, so that if x is in A, then x is in D and if x is in B, then x is also in D

That is what they mean by "contains all the elements that belong to at least one of ..."

[final cliff]

Neither of these sets satisfy the axiom for our choice of C

"Contains all the elements that belong to at least one of A or C"

[plucky wedge]

why do they say atleast one of the sets in the collection and not all sets in the collection

[final cliff]

Because if we used all we would not get a union.

Try this:

For C={{a,b},{a,c},{a,d}} what is the set of elements contained in every element of C?

[plucky wedge]

{a,a,a,b,c,d}

[final cliff]

a certainly is in {a,b},{a,c} and {a,d}. How about b?

[final cliff]

Nah

b is not in {a,c}

[plucky wedge]

ohhh

[final cliff]

You see?

[plucky wedge]

yeah that makes sense

[final cliff]

Unions are sort of inherently to do with existential quantifiers.

There are ways to phrase the axiom of union that immediately give you the union set exactly and they use existential quantifier. It looks like this $\forall C \exists U (x \in U \iff (\exists B \in C)x\in B)$

[vital dew]

DootDooter

[final cliff]

The set U ends up being the (unique) union of the collection C.

The way yours is phrased is just a different way to get to the same thing.

[plucky wedge]

Ok I believe I understand now, I never seen existential used like this before, so saying there exist a B in C s.t x is in B gives us {a,a,a,b,c,d}

I didnt realize existential can sort of iterate through all of C and apply the statement that follows, if that make sense?

[final cliff]

Yeah for C={A,B}

I guess both existential and universal quantifiers can be thought of in terms of iteration

[final cliff]

Worth mentioning that the way this is phrased is essentially just saying "there is a set that satisfies the definition of a unary union on the set C"

[plucky wedge]

oh ok that makes sense, thank you for your help, I can now continue through this chapter lol

[final cliff]

No problem

[grand wolf]

why is the highlighted bit true

[coral parcel]

How do we know T_r has no cycles? Are there hidden assumptions that we can't see here? Can you show all of them?

[grand wolf]

Oops, this is the full question

[coral parcel]

v1 cannot be adjacent to more than one blue edge, or to more than one red edge.

[wheat plinth]

<@&286206848099549185> can anyone assist me a bit here

[fast vale]

$A \vee\neg B$ is something special, do you know what it is?

[vital dew]

Super Matroid

[wheat plinth]

Means A is true or B is not true?

[coral parcel]

Perhaps it rings more of a bell if you write it as "not-B or A".

[wheat plinth]

I know all those basic interpretations but I just kinda need some help in the work, I’m used to using a truth table to prove everything

[coral parcel]

Do you know how to express "->" as a combination of {and,or,not}?

[wheat plinth]

I don’t need it to be solved at all I just need to understand where to begin

[wheat plinth]

Ohhh I get it

They’re the same thing

Damnit I forgot

Thanks I guess I’ll see where I can go

[coral parcel]

I suppose you could also just wing it:

Let's assume the long statement is true and that we also know that, for example, p is true. Now since (r or ¬p) must be true, we can conclude that r must have been true too, because ¬p definitely isn't [... etc etc etc ...]

[tall trail]

Hey guys, I have a final exam tomorrow and need some help if anyone knows any tricks tounderstanding the topic of Estimation I have my professor's notes on it but she kinda dumped it on us on the last lecture and went really fast

So I understand that
Big O is <
Big Omega is >
and Thetha from my understanding is. approaching each question by finding the highest growth rate

[dull halo]

Rewriting the statement to p -> r and r->q and q->p
Each variable will appear in the conclusion once.
If its value is true then the premise must be true so the third variable has to be true by the same argument.
By the same argument, without loss of generality consider two variables true and one false.

[wheat plinth]

If you assume the whole expression is true and start with one variable (like P = True), the others are forced to match it to keep the entire conjunction true. The same logic works in reverse if you assume one is false the rest have to be false too. So either they’re all true or all false any difference breaks the chain.

[wheat plinth]

If two are True and one is false then all becomes false right? So they all have to be true?

[wheat plinth]

Ahh I see

They’re all logically equivalent

[dull halo]

I dont mind showing you in vc

Writing

[wheat plinth]

Yeah sounds good

[dull halo]

Is there vc in this channel? lol

I can not see it

[wheat plinth]

I don’t think so

Should I call vc you?

[coral parcel]

There are no public voice channels in the server; they became impossible to moderate meaningfully.

[dull halo]

Wow. Haha

How so?

[coral parcel]

Unless there's a moderator actually listening in at all times, claims that "so-and-so was being rude / racist / making weird annoying noises in the VC" becomes impossible to react to.
In a server of this size there will be someone who goes to the voice chat to spew racist tripe, but we wouldn't want to hand everyone a carte blanche to get their enemies banned just by claiming they misbehaved. So it's a lose-lose for the moderation team.

[wet sedge]

Can someone help me prove this identity?
[\sum_{i = 0}^{m}\binom{m}{i}\binom{x}{i}t^i = \sum_{i = 0}^{m}\binom{m}{i}\binom{x+i}{m}(t-1)^{m-i}]

[vital dew]

questions

[wet sedge]

by $x\choose i$ I mean the polynomial in x

[vital dew]

questions

[wet sedge]

with some computation I've reduced it to showing
[\sum_{i =m-j}^{m} \frac{j!}{(m-i)!}\binom{x}{i} = \binom{x+j}{m}]

[vital dew]

questions

[glossy roost]

Isn't this supposed to be a combinatorial proof?

[wet sedge]

wdym? like if we assume x is an integer we can prove it by some counting argument?

[glossy roost]

I think so. I'm not sure, but when I see, a proof problem that looks like this, I assume it's a combinatorial proof i.e try to figure out what counting problem is answered by one side of the equation, and try to show that the other side answers the same question.

[wet sedge]

ah no I need to use it when x is not an integer too

[fossil mural]

if two polynomials are equal at infinitely many values then they're equal

so restricting to the case where x is an integer isn't a problem

[wet sedge]

oh oops

[glossy roost]

oh my bad!

[wet sedge]

nvm you just had foresight

[hidden totem]

pretty sure this isnt even true?

[wet sedge]

yeah i mightve made some calculation mistake was pretty sleepy when I wrote that

the above identity is true though

[hidden totem]

the right side is a monic polynomial but the left side is not

[wet sedge]

it's from a table of combinatorial identities

[hidden totem]

yeah it looks like you matched exponents of t and then expanded with binomial theorem, then compared coefficients

[wet sedge]

yep

[hidden totem]

i would check those steps again

[wet sedge]

cool

[plucky wedge]

how would you exactly prove something like this, the third statement

its easy to see that it has to be the case that the right equals the left

would you just state the definitions if you were to prove it?

he says it easy to prove but I'm just wondering about the appropiate way you would prove it

[rain moth]

usually the way to prove this is to show that each set is a subset of the other
(A subset B and B subset A) <=> A = B
so you need to show that "any element on the left is also in the element on the right"
and also that "any element on the right is also in the element on the left"

[plucky wedge]

ah ok that makes sense

What is the difference between commutative and symmetric?

[hidden totem]

my understanding is that commutative is a property of binary operations, where symmetric is a property of binary relations

like equality is symmetric because if x=y, then y=x. we have to treat the relation statement x=y as a binary, true/false or in/not in a set

addition is commutative because a+b = b+a, they have the same value, but not as a binary. you cant say for instance, if a+b, then b+a. that doesn't make sense

but this does seem like a semantics thing so there might be some higher level stuff where the line is blurred and convention dictates usage more than a formal definition

[odd heart]

Pretty much, I'm not sure if there's some hard and rigorous distinctions, but I'd say "commutative" of an operation, and "symmetric" of a property/definition/relation

So in this case the definition of intersection is symmetric, which leads to intersection being commutative

[ashen surge]

hello добрый день

i have asnwer

discrete mathematics is the foundaments of programation, and all of computer science ?

what is computer science, it can help me to advance in this area ?

i have a question ****

[plucky wedge]

Thank you for the help that makes sense

[cerulean radish]

If you want to look into foundations of computer science, look up stuff like theoretical cs, theory of computation/complexity, automata theory, formal language theory

Discrete mathematics is a different thing

[coral parcel]

"Discrete mathematics" is a lot of different things at different institutions. Sometimes it does include a bit of formal language theory.

[little prism]

discrete math is basically a catch-all term for everything concerning finite or countable things

[coral parcel]

In practice it often means "whatever math we feel CS majors ought to learn".

[dry moon]

How’d you guys formalize this?

[cerulean wind]

i think the phrasing could be improved:

let a and b be odd integers. Then there are integers c and d such that a = 2c + 1 and b = 2d + 1.

The key point here is that c and d depend on a and b, respectively; c and d can’t just be arbitrary

everything else looks good

[agile magnet]

Write actual sentences that'll get you most of the way there

Also yea like what was said above, c and d are not any integers

They are integers such that a = 2c + 1 and b = 2d + 1

There's only one such c and d that work for a and b, so saying any is really quite wrong

That's really the only logical hole I can see

[agile magnet]

like here's how I'd write it.

Let a and b be odd integers. Then there exist integers c and d such that a = 2c + 1 and b = 2d + 1. Then we have that

a + b = 2c + 1 + 2d + 1 = 2(c + d + 1).

Thus, a + b is even.

much easier to read and parse than the free floating stuff you have on the board

scratch work vs a complete solution

I mean whatever textbook you're using, there are proofs in that that are written in actual sentences and paragraphs.

That should be your model

[south marten]

I don't understand the line in the proof displayed in the image below.

[little prism]

n has no prime divisors but n is a divisor of n

so n cant be prime, as otherwise it would be a prime divisor of itself

[south marten]

Ahh that makes sense

[little prism]

therefore n is composite which means n=ab and that product is not of the form 1*n

so a,b are both between 1 and n

but now a < n but n was the smallest number without a prime divisor

so a has a prime divisor

which is therefore also a prime divisor of n

[south marten]

The way I understood is when you write n equals ab with the given bounds due to the well ordering principle (i.e) a < n we have a such that it's a prime divisor . Since a is a prime divisor, n consequently must have a prime divisor and by applying theorem (1.8) you get a divisor where no remainders exist hence contradicting our original premise we can conclude every positive integer greater than 1 there exists at least one prime divisor

[little prism]

a isnt necessarily a prime divisor but it has a prime divisor

but yes

[nocturne dew]

there's any book of discrete math for beginners? i need a good introduction to propositional logic

[tulip loom]

this is the textbook my class uses if it helps:

also i had this question for this problem:
wasn't rly sure how to show the proof, (i tried using the contraposition method of proving) would my steps be correct?
btw for the question, i think we're assuming a,b,c are all an integer (so you would use numbers like 3,4,5 or 5,12,13, etc)

[cerulean radish]

The example you are giving is a counterexample

Neither would a single example be enough to prove an implication in this case

[delicate frost]

i cant see there any congruences, do you recomend any other book?
i have hard time with those and i have it in my discrete maths lectures

this is set of my exercises (those are probably easy but im stupid probably)

im on my B.Eng. course in Computer Science so i dont have too much of maths but i need to learn some

[hardy zinc]

You have only proved the contrapositive for a=4 and b=5, not for all integer values of a and b

[nocturne yew]

If 3 | ab, then necessarily at least of a and b has a factor of 3, right?

Then if we assume (for our contrapositive/contradiction) that 3 does not divide ab, what can we say about each of a and b?

Then what about a^2 and b^2?
Then about c^2? [From here you should find a contradictory statement about c^2 being a square number]

[untold kite]

I'd like some more eyes on a question I posted a while back, I also wrote a partial proof that needs more attention, hope this is the right place
https://math.stackexchange.com/q/5036847

it is about proving the shortest possible path's length that touches every square in an n by n grid

[true venture]

This is cool, I've seen similar paths called a "kings tour" where a king chess piece moves through all squares visiting each exactly once. This could be viewed as a variation of that moving alone the edges. The tiling interpretation given in the mse post seems like the best way to prove this to me. I think it's likely that there would be similar proofs about tilings, which could give you the tools to prove this.

Though, idk how easy proving the bijection to tillings will be

[untold kite]

I've heard of "knight's tour", though that doesn't help much as that only touches one square at a time, did you look at my proof at the very bottom?

I also haven't thought much about the tiling approach as it is too heavily restricted for me to comprehend it as any arbitrary tiling

it's there as a maybe useful idea

[true venture]

Yes they are different, but I meant there are many resources that use that name and since they are very similar those might be helpful. I looked at the mse page briefly

[true venture]

Yea, for me I am more familiar with tilings.

One bijection between one of your paths and a tiling with maybe only dominoes and L pieces is: if you start at one end of the path each grid point in the path maps to the tile of the squares touched by that point minus the squares touched by the next path point and previous path point if there is one.

I think this gives a bijection between such a path and a tiling using only dominoes and L tiles. No 2x2 squares are needed.
But then yes not all tilings using those 2 kinds of tiles map back to a valid path

[true venture]

Then this also ties back to n being a multiple of 3, since a nxn square can be tiled using only L tiles iff n is a multiple of 3

[true venture]

Also for n>3 similar to your proof.

[true venture]

After drawing a few out, you do need nxn squares as well

[true venture]

yea I see how the restriction on such tilings is complicated

[untold kite]

do you have an example without the 2x2 square at the start, I can't think of how you'd void it or the directional-ness of it

[true venture]

The 3x3 path didn't need a square

That might be the only one, think if the start of the path is adjacent to the end you don't need a square

[untold kite]

https://virtual-graph-paper.com/

[true venture]

Excuse my handwriting

[untold kite]

this is how I understand the n=3 case

the L shape corresponds to a diagonal in the bijection I used to get to a tiling problem

and you are forced to use a 2x2 because you start on a vertex, which by definition touches 4 squares

[true venture]

Oh I see, slightly different tiling method than I was using.

I'll look at this way, but I'm losing hope that looking at this as a tiling problem will help. I'm not seeing a good way to tell which tillings have a corresponding path

[untold kite]

it's going from point to point for each new move like you described, I don't see how you get to your tiling though

[true venture]

So in yours you look at each point and make a tile for all cells the point touches. I was looking at a point and subtracting the cells the next point touches from the first.

Then for the last point there is no next point so it's often a 2x2 sqaure

[untold kite]

for evey case other than 0,1,3 it will be

also is it not just the opposite of what I do

[true venture]

Yea

I have no reason for my method it was just what I thought of first

[untold kite]

the results should be the same

anyways, spread the word, there is a proof somewhere

[true venture]

Are you using code to find the optimal paths? You could make an oeis sequence of the counts of optimal paths for an nxn grid.

Or a sequence of the length of the shortest path for an nxn grid

[untold kite]

https://github.com/tomka700/Minimal-path

it's hit an exponential wall of O(c^n^2)

[untold kite]

not sure how you'd put infinity into oeis lol

n=1 has infinite distinct solutions

the rest are all countable

[true venture]

How are their infinite solutions for a single square?

[untold kite]

here's 2 different solutions

now overlap the two, make a line between them and count all the different points

the problem itself isn't restricted to the grid

[true venture]

I'm not following, why is the answer not a single point on a corner which are all reflection/rotations?

[untold kite]

it is forced there for larger n by the vertices touching a lot of squares at once

[true venture]

Oh well if your trying to make it a finite sequence you would restrict to an nxn grid

[untold kite]

see here: https://math.stackexchange.com/q/5036912

[untold kite]

the original idea for this was to take the original hamiltonian path problem and generalize it to any curve you wish

[true venture]

Oh ok, interesting

[untold kite]

this one, who's to say that the path must go from middle to middle

[true venture]

Similar though I had, for a nxn grid what is the min number of just points you need to place so that all squares are touched, that seems like an easy lower bound, idk if it would be better than what you linked

[untold kite]

ceil(n^2/4)

if you could do it with just diagonals it'd be ceil((n^2-4)/3) (you can't)

[true venture]

Ah ok

[untold kite]

look at the original post it has formulas

[true venture]

The length of the shortest path covering for an nXn grid would be a good oeis sequence. Also some ppl there may be able to provide insight or crunch more terms.

[untold kite]

I'll look into that someday, gn for now

[true venture]

Let me know if you do, I know the formatting they want pretty well

[gusty dome]

is there any motivation, how people come to know $(m,n) \mapsto 2^{m-1}(2n-1)$ is a bijection between $\mathbb N \times \mathbb N$ and $\mathbb N$

[vital dew]

Abstract Afzal

[gusty dome]

i mean how they got idea to go for this map

[odd heart]

Try to explicitly work out what the images are for m=1,m=2, m=3 and so on.

[cerulean wind]

every natural number can be written a product of a power of 2 and an odd number

[gusty dome]

Ah yes. This makes sense.

Thank you c squared and Outsider

[inland raft]

lump all the even primes that appear in the prime factorization together and do the same for odd ones (how many even primes even are there anyway)

[primal quail]

someone with knowledge in graph theory ?

[coral parcel]

!da2a

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[coral raven]

how the fuck do you do this

i'm struggling to even do it for r = 3

i mean i know for sure i could just look it up but

[tired summit]

For even r I think it's easy, for odd r I don't really know of a nice way to do it

[coral raven]

for even r i vaguely remember it's something about complete graphs

need to work out how to prove that as well

[tired summit]

Yeah, for even r it's ||K_{r+1}||

[coral raven]

wait, i might be smart

ah ok i found a good way to do it for even r

[coral parcel]

Is chi' the chromatic number?

[coral raven]

edge-chromatic number

[coral parcel]

Ah.

[tired summit]

For odd r I think the family of graphs like this are called snarks

[coral raven]

urgh i don't think i ever learned about those

i feel like there should be a way to do it just with what was taught but maybe it's just fucked

[coral parcel]

Looks like "snark" are specifically examples of r=3.

And ||the Petersen graph|| is the smallest r=3 example -- not even particularly obvious that it works.

[coral raven]

if i assume that there exists an example for r = 3 maybe i can find a general way to get r = 5, r = 7, etc.

hmmm

[coral parcel]

[response to someone who pushed back on !da2a and then deleted their posts] your choice; feel free not to get your question answered because you never ask it until someone commits to answering it without even yet knowing what it is. ¯_(ツ)_/¯

[coral raven]

yeah no if they ask me this in the exam i'm just fucked

next question

[tired summit]

If you discover a nice construction of them, please let me know too

[coral raven]

ok so. let r be odd. now start with a vertex u.

connect u to r other vertices, call them v_1, ..., v_r. (red)

now take any of the v's. they already have 1 edge, so we need r-1 more. so connect v to x_1, ..., x_{r-1}. (orange)

now we are going to make the x's into a bipartite graph. the x's already have 1 edge, so they need r-1 more. so add vertices y_1, ..., y_{r-1}, and connect each of them to all the r-1 x's. (yellow)

this satisfies the x's. but now the y's each need just 1 more edge. r is odd, so we can hopefully just pair off the r-1 y's to get an r-regular graph. (green)

the result is hopefully not r-edge-colourable

[untold kite]

https://oeis.org/draft/A383980 it's gonna take a bit to get it approved it seems

[tropic moth]

did i get r=3?

i started with the 5 top dots, then drew in the / \ reds, and the -- blue and forced to criss cross purples

then the lower edge blue and i got stuck and was forced to use a 4th color

but it wasnt 3 regular, so i threw in like a central connector

and x3 symmetry

[graceful shell]

hellou guyssssss

if i see something like this

i should expect that it has 2 or 4 answer?

[spare slate]

Non-real complex numbers have two square roots

Which follows directly from the fact that second degree polynomial equations have at most 2 distinct roots

[graceful shell]

ah

i see

then not 4

ohk

thats x^4 then

[stray reef]

two.

[graceful shell]

thx

[untold kite]

https://oeis.org/A383980 YOOO

[true venture]

Ha nice, it's already up.

[untold kite]

it's so cool that the guy that founded it is still approving stuff to this day

[true venture]

Oh nice Neil himself approved it. Even if it is not approved quickly, recently you will only have to wait a week or so. It used to be like a month

[reef frigate]

someone online?

[coral parcel]

!da2a

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[tropic moth]

it gets even better

$\sqrt{5+12\sqrt{-1}}$

how many solutions there?

[vital dew]

rochambo

[untold kite]

sure it was quick but then immediately someone else is complaining that it should be renamed without making the change themselves 🤷‍♂️

[true venture]

Yea there are normally some suggestions given.

[true venture]

I was the user who added a period to the crossrefs. I think it makes sense to add more description to the name.

[coral raven]

yes, this is exactly my construction

i'm pretty sure it works

[tropic moth]

i didnt finish here but the construction i think works for a consistent +1 colors

er like r+1 colors, here i need 6 to do the 5 regular

im trying to generalize like a complete graph remove the neighbours of one vertex and only add 2 total

2 neighbours i mean so its like a V attached to some surgeried complete graph

i tried it a few times with different arrangements and its consistent

and then i think the V will have r-1 degree, but then you create r copies of it like my r=3 version

same idea as yours kaisheng, like the red into orange into yellow
but the orange-yellow graph is a r-complete with a couple edges removed, and then make a red star to copy paste it

[prisma patrol]

"every subgraph of a k-partite graph is k-partite"
is a notion of a proof that if we color the original graph with k colors, then eliminate all vertices but the ones in the subgraph, the ones remaining must be colored with k colors?

[tired summit]

Yeah, by removing the vertices, it'd still be colorable with k colors or less

[prisma patrol]

thank you

[tropic pumice]

I'm not sure if it appropriate to ask this question here.
Could anyone help me construct a block design that satisfies the requirements here?
I can't imagine a reason why each element must be contained in exactly k blocks.

[somber vapor]

are you available right now?

[sleek elbow]

Hey guys, I'm currently reaching the end of my least enjoyable semester so far and I have learned that I'm definetly not a Real Analysis person.

I really really enjoyed Abstract Linear Algebra I and II and I feel like Graph theory might be something I'd enjoy.

Can someone recommend a book on graph theory to read on the side to keep my love for mathematics alive while I suffer through this semester?

I'd love something with a lot of exercises, I'm planning on taking a rigorous course on Graph theory next semester so there is no need for too much rigour but it should also be suitable for a math major.

Hope that is not too much to ask 🙂

[untold kite]

that is approved too now, I made a third now (https://oeis.org/draft/A384083) and I have an idea for a 4th which would count the number of symmetric solutions but that sounds kinda lame

1, oo, 1, 1, 1, 1, 2, 0, 0, 2, 0, 0?, 8?

[true venture]

It's is kind of sparse, could also do numbers k for which a symettric solution exists
0 2 3 4 5 6 9 12

I now see why for n=1 there are infinite solutions. This may cause confusion and can be avoided by only considering lattice paths with kings moves

But idk don't think it's that big of a deal

[untold kite]

I'd only want to make it so that I could replace k with it, also after a while it seems only 0 mod 3 will have any but the number of them stays interesting

except there is nothing interesting in the currently proven list that only goes up to 10

[untold kite]

I rather keep the original problem and add an overexplaining comment to the n=1 case if requested, it makes the problem cooler in my eyes that it isn't restricted at all

idk if you've looked at it but 12 is where the problem gets fun

also is it a symmetric path if the path doesn't exist

it feels like it would be

[coral raven]

#book-recommendations

[tropic pumice]

Well, I wasn’t. However, I noticed when lambda=1, k=3, v=6, there might be a solution. And this question might only be solved by analyzing the determinant of matrix.

[tropic pumice]

Though it's not necessary to find an explicit example, I think it's unsatisfying to solve a combinatorial question with analysis only.

[tropic moth]

wtf is this? can you post the whole page? would love to see the rest of the questions of whatever the heck is going on there

[runic yarrow]

can someone tell me about the difference between big o and big theta?

[tropic pumice]

Well, that's my combinatorial homework, and that is the whole question, it won't to be helpful to see the rest of the page .

[tropic moth]

this doesnt strike me as an "intro" to combinatorics

what level or year course is this?

can i see the course webpage if its public?

or do you guys have an assignment textbook i can look up?

[tropic pumice]

This is graduated level, but I don't know where I can ask in this server.

[tropic moth]

but still where can i look into for this kind of stuff? like what textbook or what course webpage or somethign

[runic yarrow]

can anyone help? struggling primarily with understanding the concepts for this question

[runic yarrow]

not necessarily answer the question, rather provide insight into the relation of big o/theta towards this question

[true venture]

You can ask in #combinatorial-structures that is the graduate combo page

[tropic pumice]

Here is the webpage, but I didn't read any textbook here, though

[tropic moth]

coo coo thanks

but id say its considered advanced level being graduate, on the server list theres probably #combinatorial-structures under advanced

[runic yarrow]

lol

[loud galleon]

Hi..i got a few questions about induction...logic...can anybody help me?

[coral parcel]

!da2a

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[primal glade]

help

[runic yarrow]

use a truth table

if they hold the same truth values then yes its logically equiv

[primal glade]

IK

But can we prove it algebraically?

[runic yarrow]

you can prove it w demorgans laws

not w algebra

[primal glade]

Could u show me?

[runic yarrow]

your prof shouldve given you a sheet

or it should b in your book

[primal glade]

I just don’t know how to do it with demorgens law

My book is the one without answer sheet

[runic yarrow]

you should have a sheet of logical equivalencies, you need to use those to solve the question. for this particular question I would use a truth table unless specified otherwise

[primal glade]

Okay thx

[runic yarrow]

no problem I posted a few discrete math questions above, I am re-taking discrete rn and my 2nd midterm is on wed so I am studying up. if your familiar with big o and big theta lmk

[tropic pumice]

Hmmm, I think it's possible to find the definitions of Big O and Big theta on Wikipedia, and I don't think they should be included in discrete math.
Anyway, for the case big O, you can only know that limsup f/g is finite, but it might go to zero, for the theta case, we can be sure that limsup f/g>0.
And that's great, because that means the growth rates of f and g are the same.

[coral parcel]

The hint you got when you asked the same question in #proofs-and-logic points toward an argument by algebraic manipulation.

[tropic pumice]

Oh wow, this question is surprisingly easy. I couldn't solve it at first because I misunderstood the first sentence of the question, so I missed one of restrictions about B.
(I'm pretty bad at English)
Anyway, thanks for everyone's help.

[tropic moth]

can you write it out?

just curious about this stuff

[gritty dome]

I'm having a bit of a hard time understanding the requirements of a minimum bag. Do I understand it correctly that a bag is simply a set of vertices that are connected?

So a possible bag would be (B,C) or (B,C,A)

If so - what are the requirements for a bag to be considered "minimal"? My friend explained it to me that a minimal bag is such that every node in the bag has precisely one edge between them

But, would that not mean that all minimal bags are of size 2 or less?

[agile magnet]

what is the definition of a bag

I'm not familiar with it so if you can give an actual definition from your textbook or notes or something that would be a good first step

[gritty dome]

I've been trying to find one. https://www.youtube.com/watch?v=kEnDGTwSDXY&t=21s seems to simply a set of connected vertices?

[agile magnet]

and probably answer your first question "do I understand it correctly..."

[gritty dome]

My friend just talked to me about it over the phone, I have almost no knowledge about graph theory besides some very, very basic understanding (cs major)

[agile magnet]

So "bags" isn't really a technical definition like "graph" or "tree", he just seems to be using it as a word to symbolize that each vertex in T is a collection of vertices of G

but like all the definitions you need are here

it may help, and this is a good thing to do in general for math and TCS stuff, to work out a couple examples of tree decompositions for graphs G you come up with

start with perhaps a smaller graph, like 3-5 vertices

and then also maybe do a different tree decomposition for the G in the picture there

as well as understanding why the tree decomposition T drawn there is also a tree decomposition according to the definition (this would be the first thing I do before working out other examples)

[gritty dome]

From the first rule, if (u,v) have an edge then they must be in a bag, but this does not mean that if (u,v) dont have an edge, they cant be in the same bag, right?

that's why one bag contains (b,d)

[agile magnet]

yup!

exactly correct

[gritty dome]

hmm okay, so maybe, when he said "minimal tree decomposition consists of minimal bags", he meant that the tree would consist of bags, with as few nodes as possible, such that rule 1 and 2 still hold?

What I am confused is, rule 1 and 2 could always be fulfilled by creating pairs

say top is A, bottom left is B and bottom right is C

b_1 = {A,B}, b_2 = {B, C}, b_3 = {A,C}

or hmm, I'll probably get some sleep and try again tomorrow

ahh noo ok yeah no im too tired

a tree per definition can not have cycles

so for rule 2 to apply and T to be a tree, the above would not work

I think the only solution for the triangle is one big bag {A,B,C}

[fallen dome]

hi could someone help me understand how I solve these kinds of problems? I know what dynamic programming is, but not sure how to do it in this context

[vestal bronze]

@fallen dome you find the cost for each node in order, that's all it means

those two nodes are obviously 4 and 5, which lets you mark the next one with 5

5 comes from 4+1

you have two possible paths, choose the shorter (cheaper)

there will always be some node where you have the information to decide this, until they are all done

i don't know what the backwards part means on the other hand ok i get it

[vestal bronze]

i mean yeah, that sounds so dumb, "ignore the prompt, there is no such thing, don't use the algorithm, it doesn;t exist"

while True: find a cost that's easy to compute and compute

[fallen dome]

wdym?