discrete-math

[wild merlin]

thanks so much i get it

i had the exact diagram i needed i was just looking for a bijection now

i was considering partitions of n-2 and adding to them but i should've considered n of course

[amber prism]

Not sure how to start this w/ combinatorics

[meager prairie]

do you know the numerical answer

is it 8!9!3

[amber prism]

nope no answer key

[meager prairie]

well im dumb with stuff

but my thought was 8! reduces it to the combination / accounts for all orderings of the 8 gifts

9! is the bars counting

then 3 choose whichever youd like for the final factor

[amber prism]

I know from partitions it's like 3(# of partitions of 8)

[meager prairie]

stars and bars

but i never really learned it

[amber prism]

Same

[meager prairie]

i feel like my answer should be close

bummer i cancelled chegg

[amber prism]

so it's apparently 66 I think, but idk what combination of factorials/combinations/permutations would get me there

[meager prairie]

that sounds so low

hmm

[amber prism]

<@&286206848099549185> if anyone has an idea

[amber prism]

I got $\frac{10!}{2!}$ since 10! ways to arrange the 8 gifts and 2 bars for stars and bars, and then corrected for double counting the bars

[vital dew]

Mosh

[elder berry]

The problem is confusing in the sense that, do we care if person A has 8 of the same unique gifts means it is a separate case to consider then when person B has 8 unique gifts. I assume yes

Anyway, my guess would be 3^8

Yeah, the more I think about it the more I like the answer.
We set up a bijection with counting base-3 numbers (however, I'll use A, B, C and not 0, 1, 2)
All possible strings after shifting the bits give a unique number
AAAAAAAA would be the first such one, AAAAAAAB the second and etc.

The different gifts are analogous to the digits power or whatever it is called

we also know how to count these problems, for each place in the number (bit) we can put either A, B, C meaning 3*3*3*... = 3^8

Yeah, I over-complicated it when I shouldn't have but I think it's correct @amber prism

Instead of looking at the above argument, just consider giving the first gift to either A, B, C. There are three cases. For the second one, you can do that again, but you had three previous cases, so 3*3

[north dust]

I am getting killed by my Combinatorics homework, ahhhh

https://tenor.com/view/lucifer-pretended-lucifernetflix-get-shot-gif-20063910

[elder steppe]

How do I prove this if I'm not given any terms

[minor zephyr]

sure you are. The terms are a_1 = 2(-4)^1 + 3, a_2 = 2(-4)^2 + 3, etc...

[elder steppe]

oh I didn't even think about that haha

I'm also a little confused on where to start with this, I get that I should just find the summation but wouldn't that be a_n - a_n-1

[proven silo]

why? Try and write it out for n=5 for example, everything execept a_5 and a_0 gets cancelled

[elder steppe]

ahh I see, ok that makes sense

[elder steppe]

how would I go about solving this

[weary tiger]

Use the identity:)

[elder steppe]

like should I follow the same method of writing out a bunch of terms and trying to find a pattern?

[proven silo]

it looks an awful lot like this after using the identity does it not?

[elder steppe]

oh haha I see it now, yup it's exactly like that

[elder steppe]

so when I did that I got 1 - 1/n, does that look right? I'm trying to plug in numbers and I don't think they match up

[proven silo]

almost

you sure its -1/n?

its not

[weary tiger]

oop wrong index haha

[elder steppe]

i mean +1/n

[weary tiger]

Nope, what would be the last term of that sum?

[elder steppe]

Oh wait

It would be 1/n+1 right?

So then 1 - 1/n+1?

[weary tiger]

Yep

[elder steppe]

Ok ty!

Any advice on this? I just can't think of any example for a function with this case

[weary tiger]

Well, can you find a function that is not one-to-one?

[elder steppe]

Wait I just read that wrong it's actually super easy, thanks lol

[last timber]

no

this is -1/n

use parentheses properly

[exotic fog]

https://i.imgur.com/HmiVRmX.png

I wanna check my answer.

(yz'+y'z)(yz'+y'z)' = 0, I expanded the XOR

im left with

x+x'y(wz+w'z') = x+x'y, paranthesis goes to 1 cuz x + x' = 1
x+x'y = x + y using simplify theorem

[raven kite]

Hello everyone. New to the channel.
I am interested in studying formal methods, so I would appreciate it if someone had a book or course in mind, to get me started

[pale epoch]

there need to be any definable "rules"

formally a function is just some relation (with a specified domain and codomain)

when we write something like $f\colon\bR\to\bR$, $x \mapsto x^2$, that means that $\bR$ is the domain and the codomain of the function $f$ and the relation in the definition is given by
$$ {(x, x^2) \in \bR^2 \mid x \in R} \subseteq \bR\times\bR$$

[vital dew]

Lochverstärker

[pale epoch]

so yeah, most functions you encounter will be defined by some kind of rule $x \mapsto f(x)$ that tells you that $(x, y)$ is in the relation if and only if $y = f(x)$ for some element $x$ of the domain

[vital dew]

Lochverstärker

[pale epoch]

oh, typo

should be $\bR$ as well

[vital dew]

Lochverstärker

[pale epoch]

ye, it's common to define the image of x under f, so f(x) by some kind of rule/expression

this has to be functional and serial, but it usually is for obvious reasons

it doesnt really matter

either $f(x) = ...$ or $x \mapsto ...$ are both common

[vital dew]

Lochverstärker

[pale epoch]

yes, (x, y) is in the relation (that appears in the definition of function)

[tidal tulip]

for the proof below they don’t mention what n should be in either case

so could i augment their proof by saying something like:

“..if both m and n are positive, then m is positive integer divisor of 1. by theorem 4.4.1, m<=1, and since the only positive integer that is less than of equal to 1 is 1 itself, it follows that m =1 and n=1.”

as opposed to just ending it with "and follows that m=1"

and state something similar about how n=-1 in the other case?

[pine lotus]

@tidal tulip yeah I'd agree

if you were gonna recreate the proof just use the same reasoning for why n = 1, or n = -1

you wouldn't need to add a tonne extra

to be honest even, their proof is very wordy because it's meant to give a full understanding to someone

about how they could go about proving what the divisors of 1 are

it doesn't really need to be this long in my opinion, but ye

I think also they may have just skipped n, because it's just obvious what n is if you've already selected a value for m

and finding out all the different possible values of m, gives you all the divisors, regardless of what n is

[tidal tulip]

@pine lotus yeah that makes sense. what further justification would you need to justify n=1 or n=-1 once you established what m is? i think you could just say something like “since we know m=1 then we have 1 = (1)n and we can see by division in Z that n must equal 1” and something similar for n=-1 case. would that work?

[pine lotus]

yeah tbh I'd say that explanation is fine

in my discrete mathematics paper they would accept that

like, the only way it could be wrong is if you can't assume division is possible in Z or something lol

which is just not gonna happen

[tidal tulip]

great, ty

[pine lotus]

algs g

goodluck

[stone lantern]

hi, just started learning discrete 1, can anyone explain how they got example 3?

[elder berry]

That is one of the rules of replacement of implication. p => q is the same as not p or q

[tidal tulip]

p->q is ~p or q

[stone lantern]

tyty

[crystal scarab]

Am I doing this right so far? Bit confused

[meager prairie]

looks right to me i think only i wonder if youre missing some

i might be wrong but i feel like you might be undercounting

since if you have one pair, you have 3c1 places to put that pair

same with 2 pair

except with 3c2

[crystal scarab]

hmm i see yea that would make sense

do u have any tips on how to do b?i know it starts with 5x4x3 but im not sure about the rest

[meager prairie]

hmmmm

im in a similar class so grain of salt 😄

5 times 4 times 3 is easy for 0 case

1 case is gonna be uh

$5 \cdot 4 \cdot \binom{3}{2} + 5 \cdot \binom{4}{2} \cdot 2 + \binom{5}{2} \cdot 3 \cdot 2$

I think?

[vital dew]

jan Niku

[meager prairie]

similarly for 2

[crystal scarab]

i see so you just straight up add for each case in case 2

[meager prairie]

yea

well maybe theres some nice form

[crystal scarab]

i was trying to figure out how to do it without straight up adding it

[meager prairie]

i wonder if you expanded this out in factorial notation and did some factoring

something nice might fall out

but i dont know off the top of my head what youd even look for

like the first term is probably represented in the second

[crystal scarab]

yea this answer prolly works even if it doesnt look the nicest

[meager prairie]

same with the 2nd to the third

since itd be subsets (the tree of the third term should be most expansive i think?)

[crystal scarab]

honestly not sure lol

[meager prairie]

so probably something nice to factor

but i have no idea without doing it

probably not worth the effort 😄 unless you have a bunch of similar problems

3 is not so bad

should be 3 terms for the last part also

[crystal scarab]

got it ty!

[meager prairie]

[weary tiger]

$5 \cdot 4 \cdot \binom{3}{2} + 5 \cdot \binom{4}{2} \cdot 2 + \binom{5}{2} \cdot 3 \cdot 2$

[vital dew]

olymath

[weary tiger]

that's the correct answer

$$\text{that's the correct answer}$$

[vital dew]

olymath

[indigo tinsel]

Does anyone know if this is correct?

Boolean algebra

Just need to simplify so that I can make a gate

[sharp ledge]

Could someone explains this ?

[vital dew]

Ganymede

[hybrid ether]

If the sky is clear then sun is not visible.
I think the above word can also be written as (P) and (~Q) right?

[vital dew]

_______________

_______________

[pale epoch]

yes, although the "and x^2 in Y" is unnecessary

the second thing is not a function

if it's not a function, you should not use the notation we use for functions

well, if you just say that $f\colon X\to Y$ is a function it just means that: X is the domain, Y the codomain and f itself is some kind of relation or a subset of $X\times Y$

[vital dew]

Lochverstärker

[pale epoch]

no, it would be ill defined

huh? if you talk about a general function it can be any relation (that has the required properties)

if you write $\pm x^2$ you usually mean something like ${+x^2, -x^2}$

[vital dew]

Lochverstärker

[pale epoch]

x can only map to one value

you can define a function $\bR \to \bR^2$ that maps $x$ to $(x^2, -x^2)$ or something like that

[vital dew]

Lochverstärker

[pale epoch]

but mapping $x$ to $\pm x^2$ is not a function into $\bR$ (or any subset of it), as $\pm$ denotes two different values (in most cases)

[vital dew]

Lochverstärker

[hoary cloak]

hey, what does the notation n_0 (as a funcion of 2 integers) means in graph theory? is it a common notation?

this is from diestel's graph theory chapter 1

i wish i could give more context but apparently they just threw in this notation here and idk what that means?

ok apparently this is it 😩

i answered myself it seems 😅

this is for a graph with maximum degree d and girth g

and this is a hard limit to the number of vertices

[sharp isle]

anyone studying MIT 6.042?

[scarlet current]

yo is 7x^2 = O(x^2) ?

it is right becoz 7x^2 <= 8x^2 when x>0

[hybrid ether]

2.28

My answers are

A=F, B=T, C=F, D=T, E=F, F=T, G=T

Please correct me

[cerulean wind]

yes. you could even reason because 7x^2 <= 7x^2 for all x

[gleaming notch]

hi, could someone help me with this question please?

[cerulean wind]

what have you tried

[gleaming notch]

nvm i confused algebraic proof with combinatorial proof

i got that

could you help me with this one?

it's the second part

[stray reef]

okay so this is going to sound weird

but i'm having my doubts over something that happened earlier

oh nvm i'll go elsewhere

[vapid torrent]

Consider this setup: I have a people and want to form the club with b members. Out of the club of b members, I want to form an executive board of c people.

How many ways could you form the club and board?

I think this works

[gleaming notch]

Yup ok

[gleaming notch]

Is my reasoning fine?

@vapid torrent ?

[vapid torrent]

that looks right

[gleaming notch]

Great

Could you help me with this too?

[vapid torrent]

How would you set this up?

Like, do you know how to start this problem (in particular the inclusion-exclusion principle)

[coral raven]

are you sure it's true lol

ok so you should try a few examples

[slate burrow]

my brain is shutting down rn

ok so I agree is does not hold

But I'm not sure how else i can prove it

Maybe congruence could help here?

[narrow valve]

So what are you thinking about doing?
Are you going to prove it or contradict it?

So you suppose that it is true then?

I suggest you try some examples as the other guy said. Take the numbers from 1 to 15 or something. Maybe you'll understand why it is true or why it is not.

[distant glade]

the statement says that it’s true for all numbers, so all that’s needed to disprove it is a single counterexample

take the number 35 for example. the number is not divisible by 2 or 3, yet it is a composite: 7*5, and therefore not prime

actually they want you to use contradiction so it’s a little more elaborate than a single counterexample, but the idea is:
you start assuming the proof is true and show how it leads to a contradiction

[gleaming notch]

Yeah that's what I am having trouble with. I can understand that c must have a common factor of p or q to have a gcd greater than 1

[sharp ledge]

Hey, how do we construct a bijection functions to show two objects are the same ? lets say set a = {1,1,2,3,4,5} and B = {1,1,2,3,4,5}

[stray reef]

are you sure you didn't typo anything there?

{1, 2, 3, 4, 5, 11} and {1, 2, 3, 4, 5} are not the same cardinality, so no bijections exist between them.

[sharp ledge]

Just changed it , yes, it is typo

[stray reef]

so you want to show that there is a bijection from {1, 2, 3, 4, 5} to itself?

[exotic fog]

how can i prove this?
https://i.imgur.com/5kgs4qN.png

I tried picking random numbers but they are all false

also how do I know for certain there isnt a solution? How do I justify in my answer that there is no answer?

[stray reef]

i mean, you could solve the system as you normally would, and show that all the solutions are non-integer

or you could just argue that these equations imply 2x = 5, which already is impossible for x ∈ Z

[exotic fog]

Im not sure if im following. Does this mean that two values when added/subtracted can not be both even and odd?

[stray reef]

no, you're overthinking it.

i omitted the actual argument

i was suggesting that you show $x+y=2 \land x-y = 3 \to 2x = 5$

[vital dew]

Ann

[stray reef]

and this can be done by adding the two equations together

since (x+y) + (x-y) = 2x, to which i'm sure you have no objections

[exotic fog]

Oh I think i get it now, thanks for clearing my confusion 👍

[tidal ibex]

any ideas how to prove this ? I have no idea how to deal with subtraction of power sets

[weary tiger]

Let x in LHS of a). Then x is a subset of A and B and is not a subset of A and C. Therefore it is a subset of A nad not a subset of C.

[stray reef]

do not overthink it.

[heavy stirrup]

e

[stray reef]

let $S \in \mathcal P(A \cap B) - \mathcal P(A \cap C)$. this means that $S \in \mathcal P(A \cap B)$ and $S \notin \mathcal P(A \cap C)$. and this in turn means that $S$ is a subset of $A \cap B$ but \textbf{not} a subset of $A \cap C$.

[vital dew]

Ann

[stray reef]

@tidal ibex do you understand what i said here? (y/n)

[weary tiger]

That's what I said -.-

[stray reef]

i put it in more detail in case michal was confused about the definition of powerset or set difference.

[tidal ibex]

I achieved exactly this but I don't know how to move further

[weary tiger]

Well, if it is a subset of AnB, then in particular it is a subset of A. And if it is not a subset of AnC then it is not a subset of C.

[stray reef]

you need to show S is a subset of A and S is not a subset of C.

that's what'll show S ∈ P(A) - P(C)

[tidal ibex]

Hmm

Are these steps correct ?

Maybe this is better ?

@stray reef
@weary tiger

[stray reef]

seems ok

[tidal ibex]

Thanks 🙏

Now I'm going to try RHS

But where can I get set B ?

[stray reef]

might it be that there are some instructions you have in your problem that you haven't shown us?

perhaps some relationship between A, B and C that has not been brought to light until now?

i'll need you to post the whole problem exactly as it is stated.

[tidal ibex]

I do not have any other instructions. Only sets A, B C exist

[stray reef]

what does it say in the line immediately above part a?

[tidal ibex]

It's not in English but I will translate it

[stray reef]

what language is it in?

send it anyway, even if it isn't in english

[tidal ibex]

Find out if for the sets A,B,C following holds:

a)...
b)...

Prove your claims.

[stray reef]

so it's not "prove these", it's "find out whether these are true"

and you've misled us all into thinking you were actually asked to prove that these are true

[tidal ibex]

Oh yes, sorry, my bad

So the possible solution is that a) is true and b) false ?

[stray reef]

(a) has been proven true already

(b) is false because you can take, say, A = {1}, B = empty and C = {2}

[sharp ledge]

Yeah, so its like both a and b even though that i knew they have same elements in it, but there are from different situation where one is derived through equation and I wanted to prove that it is same as the {1,1,2,3,4,5}

[tidal ibex]

Thanks a lot

[stray reef]

sorry, i don't understand you at all

it sounds as if you want to prove the obvious

or maybe you are leaving something out here and making me confused as a result

[exotic fog]

Im solving previous tests but not sure if my work is right

https://i.imgur.com/qUi5CTW.png

,tex $ X + (YZ'+Y'Z)(Y \oplus Z)' + X'Y(WZ+W'Z')\newline X + 0 + X'Y(1) \newline X + X'Y \newline X + Y $

would appreciate feedback

[vital dew]

penguin

[sharp ledge]

So it like i have a sequence which from the base case , i know it is a fibonacci sequence , but to prove it , it asked to construct a bijective functions , so its like mapping the sequence i have to a set of fibonacci sequence to prove that sequence is fibonacci

[stray reef]

that is word salad.

it's getting harder to understand you with every message you send.

[hoary cloak]

hi i'm trying to solve this exercise from diestel's graph theory. i tried some things, like an induction proof (starting with a minimal graph, two connected vertices, but the inductive step has a lot of different cases i have to consider and overall solving this problem like this seems like it's particularly unpractical)

i also attempted to assume there are two vertices u, v whose distance is equal to the diameter of the graph, but i haven't reached any valuable conclusions

i'm not looking for a complete answer but does anyone have an intuition of how would i prove something like this?

if anyone has a response, by all means, ping me. i'll be trying some other exercises

btw, if someone has more experience with graph theory, could they clarify if attempting an inductive step by adding vertices to the graph is useful at all? it hasn't worked for a single case i tried to do this

[hoary cloak]

welp i just proved a theorem doing this exactly. so yes it's useful apparently

[peak cedar]

Hello 🙋🏻‍♂️, I am a freshman in college and need some assistance. How do I prove this? A ∪ B = B ⇒ A ⊂ B

[fallow lagoon]

Maybe say A U B = A + B + A int B

Since A U B = B

A = A int B

So A is included in B

[stray reef]

what do you mean by +

[hoary cloak]

i'll give a hint: instead of trying to prove that if X, Y, try to prove that if not Y, not X. they're equivalent.

that's how i did it at least

(if you want i have a screenshot of the full proof but idk if it's good practice to disclose full answers in this server, nor i want to just throw a full proof at you without much explanation)

[wooden spear]

The power of definitions

What’s the definition of A being a subset of B!

You don’t need to use contradiction or intersections

[peak cedar]

(if you want i have a screenshot of the full proof but idk if it's good practice to disclose full answers in this server, nor i want to just throw a full proof at you without much explanation)

[hoary cloak]

wut

[peak cedar]

Sry 😅 a full proof would be very helpful. I have now spent half the day on this exercise and can't get any further. It's not the only exercise that still needs to be done, but then at least I know how to proceed.

[hoary cloak]

gimme a moment. icy sounds like theyre onto something more than i am, but anyway i'll send it

im not a math major so this might not be the fastest or most rigorous proof, but yea

[peak cedar]

Ok, this is very helpful! Thx so much

[hoary cloak]

np! good studies

[weary tiger]

how could you prove an algorithm by induction?

[hoary cloak]

you can use loop invariants (a property of the algorithm that is true before each iteration). given an invariant, you prove the properties of initialization (analogous to the base step in induction), maintenance (inductive step) and termination (the invariant at the end is useful at proving that the algorithm is correct).

Cormen's book explains this at chapter 2 iirc

they show a pretty simple example using insertion sort

[weary tiger]

well im trying to prove an algorithm but ive asked some ppl and they think its not optimal

[hoary cloak]

by not optimal do you mean it doesn't find the best output?

necessarily

[hidden crystal]

GUYS, WHAT IS THIS? I'M GETTING ANGRY.

that aint no fraction where the line at

<@&286206848099549185>

[weary tiger]

yeah ;/

[weary tiger]

its combinatorics

6 C 4

[weary tiger]

what is number set where grouping depends on whether they're increasing or decreasing?

like the number of groups

[short steeple]

i've got a problem regarding unsigned stirling numbers of the first kind (in my class it's denoted $c(n,k)$, but i know other places use bracket notation):

Assume $n=tk$. Show $$c(n,t)\geq\frac{n!}{k^t, t!}.$$

[vital dew]

Snodlop

[short steeple]

i know that c(n,t) is the number of permutations in S_n with t cycles, but i'm not sure how to compare it to the fraction on the right

n! is all possible permutations of S_n, and i suppose t! is the number of permutations of the t cycles in c(n,t)? but i'm not sure where the connection is

if this is the wrong channel for this problem, please let me know and i'll move it to the appropriate place :)

[short steeple]

update: figured it out :)

[kind hollow]

how many edges are in a circuit?

5?

[weary tiger]

anyone here can help me w an inductive proof?

[pearl fern]

[west bane]

Hey, can someone help me understand how to approach this question?

I looked through the rules but I didn't find a combination of rules that would imply the conclusion

[elder berry]

Show they are equivalent, start working from the right side, change the equivalence and then and use De Morgan's laws

[past nova]

hello! can someone explain how these two are equivalent? thank you very much!

[elder berry]

Hockey Stick identity

[past nova]

why is it n+2 and not n+1?

[elder berry]

On the left we have r+1, on the right it is going to evaluate as (r+1)+1 where r=n, or (n+1)+1

maybe put in some substitutions to see how they both match up

[past nova]

okay! thank you very much for the help!!

[mystic elbow]

Hi can anyone please help with q8

[onyx zephyr]

What techniques are there for proving strong induction? As in leading up your equation into getting to your k+1 at the end. Haven't learned any real tools or rules yet just to try with simplifications and hope to get to the answer.

[torn tendon]

this might be helpful
after that , ask any questions concerning what exactly you didnt understand

[weary tiger]

can someone pls help w an inductive proof

its a proof in cs

[torn tendon]

[wild merlin]

for (c) i think i've convinced myself you need the diagonal of the chessboard covered in grass initially and then it covers the board

but i don't know how to prove that's the minimum number of tiles

should i consider smaller tiled boards inside it? (since for example a 2x2 only has the diagonal work)

[severe oak]

what does order mean in line 4

[pale epoch]

O(n^(1/2))

[waxen sequoia]

Can anyone help me

[digital quail]

Which is a permutation, combination, or combination of both?

[worn wolf]

In the first case it's how many ways can be the pianists ordered multiplied by how many ways the guitarists can be ordered

[hybrid ether]

Hi

Have a doubt

[worn wolf]

In the 2nd case you pick 1 pianist from 6 for the first performance and 1 guitarist out of 4 for the last performance, the remaining performers are 6-1 + 4-1 and you can arrange them however, so 6 * 4 * how many ways can you arrange 8 people in

The third one you have to pick 3 pianists out of 6, then you can order those pianists in whatever order, then you can order the guitartists in whatever order, then the remaining 3 pianists in whatever order

[past burrow]

im unsure of what reflexive reallly means in terms of this set

i understand it with numbers since it should be divisible

[pale epoch]

huh?

[past burrow]

like

[pale epoch]

what should be divisible

[past burrow]

like when the set was (1,2,3,4) wouldnt it just be like (1, 1), (1,2)...

and for 2 it would only be paired with (2,2) and (2,4)

since 2 is only divisble into 2 and 4

and 3 would only be (3,3)

[pale epoch]

eh, so

[past burrow]

and 4 would be (4,4)

[pale epoch]

divisibility is just an example of a relation

[past burrow]

oh

[pale epoch]

which you correctly described on the set {1, 2, 3, 4}

relations are much more general

a relation on A is just a subset of A x A

so just a set of tuples

and the tuple (x, y) being present signifies that x is related to y (where x, y could be any element of any set)

e.g. reflexive just means that every element is related to itself, or that (x, x) is in the relation for every element x of the set

you can see that R_1 is not reflexive because (b, b) is not an element

[past burrow]

or cc or dd

[pale epoch]

ye

[past burrow]

so is reflexive just the element REFLECTED for each pair

oh

[pale epoch]

oh wait, i cant read

not sure what reflected is supposed to mean in this context, but if it helps you remember it

(also both divisibility and equality is reflexive, as every number divides itself and is ofc equal to itself)

(< would not be reflexive, as no number is smaller than itself)

[agile magnet]

What about -∞???

[past burrow]

uhhh

wait isnt it just symmetric for R1

[pale epoch]

ye, R1 is symmetric

[zinc karma]

Can someone please help me with this problem? I know that the probability of drawing a black card remains 1/2

But I'm unsure how to prove by induction that the chance is always 1/2

[weary tiger]

Hi, a little group theory problem i got stuck all day and cant seem to be able to solve it. I have a group and i'm supposing that it is left orderable. If I know that $yhy^{-1}=h^{-1}$ and that $h^{-k}<y^{2}<h^k$ and $h^{-k}<y^{-2}<h^{k}$ with $h>1, k>0$ how can I show that $yhy^{-1}>1$? I've tried for a while to work it out with "bare hands calculation" but I think I'm missing something

[vital dew]

Stephen

[silver knoll]

Is 3!x2! wrong?

[lime plinth]

let $x_n$ be the number of ways to tile a 2-by-n grid.

for $n = 0$ there is only 1 way to tile (no dominoes), so $x_0 = g_1$

for $n = 1$ there is only 1 way to tile (one 1-by-2 domino), so $x_1 = g_2$

if we know that $x_{n-1} = g_n$ and $x_{n-2} = g_{n-1}$, then there for 2-by-n grid we can do one of the following:
\begin{enumerate}
\item add one 1-by-2 domino to a 2-by-(n-1) grid
\item add one 2-by-2 domino to a 2-by-(n-2) grid
\item add two 1-by-2 dominoes to a 2-by-(n-2) grid
\end{enumerate}
which gives us 2 ways for each 2-by-(n-2) grid and 1 way for each 2-by-(n-1) grid

therefore $x_n = x_{n-1} + 2x_{n-2} = g_n + 2g_{n-1} = g_{n+1}$

[vital dew]

rept1d

[lime plinth]

which of the steps are you having difficulties with?

we are trying to show that $\forall n \ge 0,, x_n = g_{n+1}$

[vital dew]

rept1d

[lime plinth]

if it is true for >=0, it is obviously true for >=1 as well

it is just a bit easier to begin with 0 in this case

we have two base cases here: n = 0 and n = 1

you can have as many as you like

P(n)

we need P to be true for two consecutive numbers

for example, for k and k + 1

then we can show that it is also true for k + 2

or in my proof, i assumed it is true for k - 2 and k - 1 and showed for k

no, why?

for example, you can assume that for some k >= 0 both P(k) and P(k + 1) are true

and then show that it is also true for P(k + 2)

these are steps 3 and 4

and step 5 is the second part of my solution, just replace n with k + 2 everywhere

[pale valve]

From a past exam: Pls help!

[lime plinth]

you can't solve it with only one base case

you need at least 2

if for some reason you want n >= 1, not n >= 0, then you will need a separate proof for base case of n = 2

i would recommend against it

if you are dealing with n >= 1, then you need to explain that x_2 = g_3

so your base case would be k = 1 or 2

[pale valve]

Is anyone free to help me?

[flat goblet]

would someone be able to help me understand this question

[sharp ledge]

How do i get transitive closure for : {(x,y)∈R2|xy = 0}

[pale epoch]

well, what have you tried?

a good first step would be describing the given relation

[oak notch]

Theorem: Let G be a graph with n vertices. If deg(u) + deg(v) >= n - 1, for every two nonadjacent vertices u and v in G, then G is connected and diam(G) <= 2.
Can someone help me visualize the "every two nonadjacent vertices u and v"? Why is that the diam(G) <=2? Aren't some connected graphs have a diameter greater than 2?

[stray reef]

you are told that your graph has the following property: pick any two vertices that aren't adjacent to each other, then the sum of their degrees is at least n-1

you need to show that this forces G to be connected and have diameter at most two.

[oak notch]

Oh, so I just have to stick to one pair of nonadjacent vertices?

[sharp ledge]

Yeah, i mean do i just aimed to make that when xy = 0 , and yz= 0 , then xz = 0 ?

[pale epoch]

the first step is to figure out when xy = 0 even happens

[sharp ledge]

when ether x or y is zero

[pale epoch]

so take a handful of those objects and compute the transitive closure of that

you will quickly see how it behaves in general

[topaz jacinth]

is this correct

[sharp ledge]

How do i do that exactly ?

I did try to put xy >= 0 but it seems that is it wrong

[pale epoch]

what are some related numbers?

or just write down the relation restricted to something like {0, 1, 2, 3, 4, 5}

[sharp ledge]

Yeah, i used 1 to 4 , but after drawing them , i still cant identify it

[pale epoch]

without 0 you just get the empty relation

[sharp ledge]

So i would have 0 connceted to 1-6 in opposite direction ?

[pale epoch]

huh?

[sharp ledge]

Could you explain it more detailed ?

[pale epoch]

you said that two numbers are related if and only if one of them is 0

[sharp ledge]

Yup, that part i understand

[pale epoch]

so in the set {1, 2, 3, 4} no number will be related to any other number

taking transitive closure won't change anything

[sharp ledge]

Ok, yes, so i should add in 0

[pale epoch]

so you should look at what numbers are related in something like {0, 1, 2, 3, 4}

and then compute the transitive closure by hand to see what is going on

[sharp ledge]

0-1 , 0-2, 0-3 , 0-4 ?

[pale epoch]

what does "-" mean?

[sharp ledge]

like 0 R 1

[pale epoch]

then you are missing a few

just go through all the pairs: (0, 0), (0, 1), ..., (1, 0), (1, 1), ...

[sharp ledge]

is there (1,1) is it not equal 0 then ?

[pale epoch]

yes

so its not in the relation

[sharp ledge]

Since it is not in relation, why do we have (1,1) then ?

[pale epoch]

i was just saying that your list is incomplete

so you either have to think more about it

or just mechanically go through all the pairs and check if they are in the relation

[sharp ledge]

I mean now i want to find for transitive closure

[pale epoch]

you should first be able to compute the actual relation on a small example before you can compute the transitive closure...

[stray reef]

a single example never proves a forall statement.

and there exists a counterexample to yours:

d = 4, a = 2, b = 2.

[pale valve]

Is anyone free to help me btw?

[stray reef]

have you made any progress?

[pale valve]

Tbh, no.

I've tried direct proof and proof by contrapositive.

But I always end up at a dead-end.

[stray reef]

"if p is an odd prime not dividing a, then either p doesn't divide 3a^3 - a or p doesn't divide 7a^3 + 3a"

[pale valve]

Yeah, but how do I go from the if to the "then" statement?

[stray reef]

perhaps try the contrapositive?

"if p is an odd prime which divides both 3a^3 - a and 7a^3 + 3a, then p divides a"

sounds easier to prove if you ask me

[pale valve]

But how would I use the hint?

ohhh, nvm, you already implied it

[stray reef]

consider: the sum of multiples of p is itself a multiple of p

[pale valve]

But when I multiply (3a^3-a)*(7a^3+3a)*d = p

I get stuck

I get da(21a^4 + 2a^2 - 3) = p

How does that show a = c*p?

d,c are integers.

[stray reef]

uh

why did you multiply?

please don't tell me it's because i told you to.

[pale valve]

Like why did I FOIL?

[stray reef]

no

[pale valve]

Ohh, p|a => a = c*p

[stray reef]

why did you multiply (3a^3 - a) by (7a^3 + 3a) in the first place

[pale valve]

Using the hint?

[stray reef]

no you didn't use the hint at all

you went somewhere weird

[pale valve]

Yeah...

[stray reef]

let x = 3a^3 - a and y = 7a^3 + 3a for brevity

may i suggest that you consider that, since p|x and p|y, you also have p | (7x - 3y)?

and that 7x - 3y simplifies to something nice

[pale valve]

Yeah

Gcd(7,3) = 1

Is that of importance?

[stray reef]

no this has nothing to do with that.

[pale valve]

Ok

How do I simplify 7x-3y

[stray reef]

recall these definitions of x and y

use them

do algebra

don't overthink it

[pale valve]

do I do 7(3a^3-a) - 3(7a^3+3a)?

and play around with that?

p|-11a*

That's what I get.

[stray reef]

are you sure about that coefficient?

i think you screwed up your algebra.

you should get -16a, not -11a.

[pale valve]

Oh woops lol, thanks.

Ohhhh, I get it now.

p|a and p|-16

p|-16 = p|-1 and p|16, right?

Thanks!!

Another Q:

Here's my work for ptb

[stray reef]

p|a and p|-16
no

[pale valve]

or*

[stray reef]

to confuse "and" with "or" is to spit on the graves of all who devoted their lives to logic

[pale valve]

I am sorry to the graves 😦

I shall sleep before I do anymore damage.

[stray reef]

confusing "and" with "or" is how unscrupulous politicians twist logic to get their way

confusing "and" with "or" is how false charges are filed and false verdicts given

[pale valve]

Wow...

I really did fuck up

Is this logic correct for 5b?

[hybrid ether]

Didn't understand question 2.58 and 2.59

[meager prairie]

2.59 is pigeon hole

how high can you count in binary with 2 bits?

[pale valve]

What about 2.58 tho

That one is tough lol

[meager prairie]

yea im not sure that one looks more interesting

[pale valve]

jan Niku, can you look over my work as well?

[meager prairie]

im about to be in class for like 3 hours

[pale valve]

.

[meager prairie]

just killing time till teacher shows up

[pale valve]

my work for 5b

Me too lol

[meager prairie]

so al these statements in 2.58 are like what $\neg P \lor Q \lor R$ or $P \to Q \lor R$ or smth

[vital dew]

jan Niku

[meager prairie]

i cant think this one through

[pale valve]

I thought the same too.

[hybrid ether]

I'm hitting my head

[pale valve]

Some sort of weird implication.

[hybrid ether]

Yes those both are same

[pale valve]

There can be many answers

no?

[hybrid ether]

Yess

Many answers

[sand cipher]

How would i prove this? by PMI??
if so what should i do for basis and IHOP,
Basis : n=1 i=1? 1/3=1/3?
IHOP:

[weary tiger]

You can also notice that $\frac1{(2i-1)(2i+1)} = \frac1{2(2i-1)} - \frac1{2(2i+1)}$ and write out the sum to see what happens.

[vital dew]

catfan1337

[weary tiger]

what does it mean when it says to find the width of the confidence interval?

[sand cipher]

what does it mean to write out the sum?
1/4i-2 - 1/4i+2
like that?

[vocal quartz]

Hi, is it possible to solve this recurrence relation?

a(n)=a(n-1) + k*(a(n-1))^0.21 (n starts at 0)

[tender kestrel]

hey

can someone help me with an exam review paper?

@autumn oyster

[sharp ledge]

How do i get transitive closure for : {(x,y)∈R2|xy = 0}

[frank wing]

Could someone help me with Equivalence relations with reflexive, symmetric and transitive

[stray reef]

this sounds like a question best suited for #prealg-and-algebra @covert elm

[sand cipher]

do i prove this using contradiction?

[stray reef]

if you think you can do it with contradiction then why not

[sand cipher]

so then if i do with contradiction do i use like if x is > 0

[stray reef]

"x is is greater than zero"

if you want to do some pointless case analysis then who are we to stop you

but you don't need that

[alpine agate]

I got a question involving Pigeonhole Principle; maybe my understanding in it is bad but the question is: "Given any n+2 integers, show that there exist two of them whose sum or difference is divisible by 2n."

[meager prairie]

n being a natural number?

[alpine agate]

Yeah

[meager prairie]

okay

whats the least amount of numbers you can have

"given any n+2 integers"

this must be true also for the smallest case, right?

and a smallest case is easiest to work with

how many do we have in that easy case

[alpine agate]

I guess 2 would be the smallest?

[meager prairie]

well 0 isnt natural

[alpine agate]

Oh then 3

[meager prairie]

debatable but its important to be 3 in this case

youll see why

okay

3 numbers

they are integers

in the metaphor, the numbers are our pigeons

and parity is the boxes

every integer is either even or odd

3 pigeons, and they all go into a pigeonhole

but we only have 2 holes, so one hole must have 2 pigeons

then i can pose to you the question

[alpine agate]

Right

[meager prairie]

what happens if we have 2 odd numbers and one even number

and what happens if we have 2 evens and one odd

how can we pair these to ensure we have an even number in the sum of some 2 we select and how can you be sure those are the only two possibilities?

(since "can be written as 2n" is equivalent to saying "sum to an even number")

[stray reef]

but it's not "can be written as 2n" in the problem is it

[meager prairie]

oh is it

[stray reef]

it's "divisible by 2n"

[meager prairie]

oh

[stray reef]

parity alone will not cut it

[meager prairie]

im very tired sorry

well wait

is that not just mod 2

[stray reef]

you might want to group by residue modulo 2n instead

or to be more exact

our boxes contain the following residues mod n:
0
1, 2n-1
2, 2n-2
...
n-1, n+1
n

n+1 boxes in total

[meager prairie]

damn i was really far off

[alpine agate]

And so these pairings are all remainders?

[stray reef]

for any box with two numbers in it the desired "sum or difference divisible by 2n" conclusion will follow

[meager prairie]

my bad skyhawk i shoulda been paying more attn sorry

[stray reef]

yes you put your integers in boxes according to what remainder they have when divided by 2n

[alpine agate]

And this is assuming you add the pairings together; like 1+(2n-1) gives you 2n which is divisible by 2n?

and n is divisible by 2n and of course 0 is too?

[stray reef]

no

n is in fact never divisible by 2n (unless n=0)

[alpine agate]

oh right im reversing

[stray reef]

let me explain this in another way since i clearly failed to communicate it properly

we have n+1 boxes, into which we put our integers based on the remainders of these integers upon division by 2n

the first box contains all those integers whose remainder is 0

the last box contains all those integers whose remainder is n

for all the boxes in between, the k'th box contains all those integers whose remainder is either k or 2n-k

[alpine agate]

Oh I think I get that, I was most confused on the pairing part

[stray reef]

and now that we have that

by the pigeonhole principle there exists a box which contains two or more integers

if it's the 0 box or the n box you can take either the sum or the difference as you please, since they both are divisible by 2n no matter what

if it's any other box, take two numbers from it and check their remainders. if the remainders are the same, subtract them; if the remainders are different, add them. this way you will get a multiple of 2n.

[alpine agate]

So there's kinda two cases we have to work with here

one being that you choose two of the numbers that are different, and the other case where they're the same

[stray reef]

if you insist on calling it that then yes

i have laid out my reasoning in its entirety.

[alpine agate]

well thank you very much! i'll have to re-read this since this stuff hasn't fully sank in but this'll be very helpful!

[sharp ledge]

For part u , how should i show that the number of sequence for each n is catalan number ?

I tried using the staircase path to show but it dont works, there seems to be some relationship between height of column and the diagonals, but i dont seems to igure how

[thorn bobcat]

Determine the number of ways to pick 8 sets Xᵢ where each set is a subset of {1,2} and Xᵢ contains Xⱼ if i|j

[sly agate]

do i use rules of inference on this question?

or both logic equi and rules of infere

[weary tiger]

I wasn't sure whether I should put this here or in analysis but can someone give me a hint on how to do this one?

[stray reef]

here's a hint: try to biject N with N^2

[weary tiger]

what does that mean? should I make a bijective function from N to N^2?

[stray reef]

yes

[weary tiger]

I don't get how that can be used to produce those sets

[stray reef]

do you know how to visualize N and N^2?

[weary tiger]

I can visualize N as a line and N^2 as a plane

[stray reef]

N as a line of points extending only in one direction

[weary tiger]

ah right

[stray reef]

and N^2 should be visualized as a square lattice of points extending infinitely in two directions

N^2 has a very easy to name infinite collection of infinite subsets

just take the rows of that lattice

(or the columns instead if you want)

[weary tiger]

oh so something like {(1, 1), (2, 1), (3, 1)....}?

[stray reef]

sure

[tidal mica]

Hey!

As you see, in the definition it says k must be even but there's no k in the examples that's even 😖 how does this work, is it a mistake

[last timber]

@tidal mica wym

[tidal mica]

Sorry just saw-
On the second line it says "for an even number k" a tmod k (it says the same in the book)
But for example on the 4th line, we have 204 tmod 5 and 5 is odd

[weary tiger]

$A = {n^2 \ | \ n\in\mathbb{N}}
\
\
A = {n^2 \ | \ \forall n\in\mathbb{N}}$

[vital dew]

neamesis

[weary tiger]

which one is the correct one if I wanna have a set which contains the square of all natural numbers?

[stray reef]

the first

[coral raven]

the first

[weary tiger]

you don't need to mention "for all"? is it just implied when working with sets?

[coral raven]

it's just incorrect

[weary tiger]

oh right yeah it makes sense

[coral raven]

the set is inherently 'all of the elements such that:'

[weary tiger]

right got it

thanks @stray reef @coral raven

[weary tiger]

I've got some graph theory question

Given a graph on n nodes where each node has either an in degree of at least 1 or an out degree of at least 1 (so basically, no isolated nodes)

How can I count the number of such directed graphs for which there is some subset of nodes pointing to the same set of some other subset of nodes

Eg. i have a subset of nodes {1,2,3} where each nodes points to {6,7,8}

I would like to know the case where n=10

[coral raven]

consider the set of all possible directed graphs and then narrow it down

[weary tiger]

2^n(n-1)

is the number of possible directed graphs

but then I'll have to subtract from that the number of specific cases

[coral raven]

you can divide instead

[weary tiger]

oh

[weary tiger]

mind explaining a bit?

[coral raven]

let A be all the possible ways for each of {1, 2, 3} to be connected or not connected to {4, 5, 6}
let B be all the possible ways for everything else to be connected to everything else
then the total number of graphs is equal to AB

[weary tiger]

Well for A each of {1,2,3} is connected to each of {4,5,6} so the total number of ways is 2. Either we have (1,4), (1,5) etc.. or the other way around so (4,1),(5,1) etc

[coral raven]

no

what about (1, 4), (5, 1), (1, 6)

[weary tiger]

The requirement is that all of {1,2,3} point to the same nodes in {4,5,6}

sorry if I have been unclear about it

[coral raven]

argh

anyway that's how i'd approach it

[weary tiger]

I'll try, thanks 🙂

[weary tiger]

How can I go about proving the minimum length of a walk for n vertices that visits each vertex at least once

[weary tiger]

Can I ask if someone will be willing to help/teach me for 1 time if i pay them?

[weary tiger]

minimum length -> shortest walk -> visits each vertex exactly once

[weary tiger]

I'm afraid I'm not understanding

[floral field]

The vertices of that are just the different permutations of 1,2,3

[coral raven]

nah you totally can

[pearl fern]

That’s the definition of projection

[shadow grove]

Say I have two die, one red and one blue. They go from 1-6 both of them. Getting (1,2) is not the same as getting (2,1).

Is it correct, that there are 26 ways of getting at least 6 as the sum of the two?

• this is not a homework question. I misunderstood the original question (how many ways to get at least 6, as in one of the dies showing 6.)

Please tag me.

• Also, what would be the most efficient way of calculating this?

I did the stupid of saying

A_1 = {(1,x) | 1<_x<_6 and x+1 _>6}
.
.
.
A_6 = {(6,x) | 1<_x<_6 and x+6 _>6}

And then I just counted

[meager prairie]

i mean counting is okay

you could probably do it in your head with enough practice

should be clear what the choices are

is it just a factorial

[willow fog]

so using the fact that the log of products equals the sum of logs, we can easily write this as $\log \prod f = \sum \log f$. however if I want to specify the indices, can I use the same index for the product and sum? namely, $\log \prod_i f_i = \sum_i \log f_i$. is this allowed? I want to specify that the numbers for the index will be the same but idk if I can use the same index for both operators

[vital dew]

gmod

[willow fog]

ping me if u have answers

[stray reef]

you can and should use the same index @willow fog

in fact, not using an index at all is not very good practice

[weary tiger]

Before drawing the karnaugh map, do I first have to get it to CSoP form?

[stray reef]

no, you can draw the kmap as-is.

[weary tiger]

Wait how would I do that

one is xzt and other one is xyzt

[weary tiger]

@stray reef

[stray reef]

xzt' will jut give you two 1 cells in the diagram rather than one

[weary tiger]

I dont get it, do you have any examples... please 😿

[stray reef]

do you know how to construct a K-map?

[weary tiger]

Yes

but when all summons have same amount of variables

[stray reef]

so if i asked you to construct a K-map for the single term xzt' would you be able to do it?

if you really insist, you can reintroduce the "missing" variable y by writing it as x(y+y')zt' but this is not really necessary

[weary tiger]

you mean like this?

[stray reef]

no

[weary tiger]

Oh we havent covered these kind of k-maps in class (with 0 and 1)

But yeah I still got it

thanks a lot

you are the best

[stray reef]

what other kind of kmap is there

[weary tiger]

No I meant like this

[gleaming notch]

hey guys, just to cross check. I got the answer for 3b as 6

[weary tiger]

Just the writing is different

[gleaming notch]

is that correct?

[stray reef]

tick marks are basically 1s lol

[weary tiger]

yeah yeah

I got it sorry

I might have autism

Thanks a lot of your help

[weary tiger]

@stray reef btw you were wrong

I think it should be like this

[blissful fox]

ah yes karnaugh maps

takes me back to my digital logic days

[stray reef]

what you ticked here is x'z't

[weary tiger]

thats not true lol

this is what I ticked

[stray reef]

your table is arranged differently than mine

if i were to arrange my table in the same way as you did, the row and column labels would go 11 10 00 01

[weary tiger]

Oh you just said that tick marks are 1s

[stray reef]

you ticked the cells corresponding to 0001 and 0101

which has x = 0, z = 0 and t = 1

x' z' t

[weary tiger]

if ticks correspond to 1

it means that 0 means no ticks

x = 0 would be x not x'

[stray reef]

ticks != primes

when i say tick i mean this: ☑️

not the symbol above x in x'

[weary tiger]

Ahhhh

[stray reef]

would you still wish to argue that i'm wrong

[weary tiger]

Then what you wrote here is non-sense

When I meant that the graphs are different

[stray reef]

what you write as ☑️ i write as 1

[weary tiger]

I wasnt talking about check marks being replaced with 1s

I was talking about 00 01 11 and stuff

[stray reef]

and also the rows and columns are arranged differently between mine and your tables

[weary tiger]

Yes thats what I meant when I said the graphs are different

I obviously dont care about check marks being 1

[stray reef]

if i were to level my table in your fashion then the columns would be labeled z't', z't, zt and zt' in that order

[weary tiger]

right

[stray reef]

yes i know this is a crime punishable by death

daring to be in noncompliance with the format

[weary tiger]

Nah you just confused me

You are just a confusing person, if you catch my drift 😉

[willow fog]

thank you so much!

[hollow garnet]

Guys

how we can it "Prove that n*3 − n is divisible by 3 for any integer n ≥ 0."

[fluid zealot]

Did you mean n³?

[hollow garnet]

yeah

[fluid zealot]

Then you may wanna factorize n³-n

[hollow garnet]

so we should to solve it by transform it into factors ?

[fluid zealot]

Then it will become 3 consecutive integers multiplying

[hollow garnet]

👍

[past burrow]

is b.) transitive and anti-symmetric?

[vapid cove]

Hi, im looking to simplfy this expression:

not sure how they did this

[shadow grove]

If I have a set |A| = n.

How many subsets can I get?

I have gotten the formula in the picture.

Please don't tell me the correct answer, if this is not it. Just in which way/an example, of how mine is wrong.

I used the product rule in the following way.

If |A| = n <-> A = {x1,x2,...,xn}.

We can define a set A1 as a set with one element from A.

A1 = {x_i | x_i in A}

This gives us |A1| = n.

A2 = {x_i,x_j | x_i, x_j in A}

This gives us |A1| = n*n = n^2

And so on and so forth until

A_n ={xi,xj,...,xn | where all x in A}

This gives us |A_n| = nn....*n = n^n

For the empty set

{ø} it is dealt with in my formula as

k =0 -> n^0 = 1.

[pale epoch]

this does not work because (sub)sets do not care about order of the elements in them, i.e. {1, 2, 3} has 3 subsets of size 2 (namely {1, 2}, {1, 3} and {2, 3}) and not 3^2 = 9

@shadow grove

[shadow grove]

oh...

[pale epoch]

or even better counterexample: there is one subset with n elements, not n^n many

if you want a hint: ||when building a subset you have a choice to make for every element: either include it or not||

[shadow grove]

I will save this for later. I will give it another go, but thank you for your answer :9

Okay

Just checked your hint before I answered, and it seems this one is correct:

2^n - because as you said, it becomes a "binary" choice, not a n-ary choice.

[pale epoch]

the LHS and the RHS do not agree, it's just 2^n

[shadow grove]

Okay, understood, thanks for the help.

[weary tiger]

nice

[shadow grove]

What is this formula called in English, can't find it?

P(n,k) = n!/(n-k)!

Where k are the amount of elements picked out of the n (different?) elements.

Where the order of picking matters.

[meager prairie]

@shadow grove "Permutation"

"n Permute k"

[shadow grove]

Thanks 🙂

A cat for the cat.

[meager prairie]

lol

[shadow grove]

Do you know a good online source for the different mathematical objects in combinatorics?

I feel like our course defines it very neglibly.

[meager prairie]

not really, lol

the wikipedia sidebar has nice summaries

i use that all the time

[deep tapir]

Can someone teach me how to count the number of r-permutations of a multiset that has size bigger than r? For example How many 5-permutations are there of the set {x,x,y,z,z,z} ? I can do the problem when the permutation size is the same size as the set, but not this case.

[past burrow]

what makes d.) anti symmetric

[cerulean wind]

nothing. it is symmetric

[lime plinth]

being symmetric doesn't imply not being anti symmetric

[lime plinth]

By definition, $R$ is anti-symmetric if [\forall x, y \enspace x R y \land y R x \implies x = y]
That clearly holds for d.

[vital dew]

rept1d

[lime plinth]

Let me know if you need are more detailed explanation

[weary tiger]

Hey can someone explain to me why the ones in red cancelled out?

they are not the same

[muted socket]

Is this a valid way to prove commutativity of union, making use of commutativity of "or"? Or am I missing details?

[pale epoch]

works

[muted socket]

Many thanks

[stray reef]

@weary tiger they didn't cancel out, rather they got absorbed into y'z and x'yz' respectively

p + pq = p in Boolean algebra

if you wish to be more explicit: x'y'z + y'z = (x'+1)y'z = 1y'z = y'z

in terms of kmaps this means that the tick marks for y'z already include those from x'y'z so adding x'y'z makes no difference

[weary tiger]

hold on let me look

ohh i see

thanks

is this called the absorption law?

[stray reef]

i think so? it might be that absorption is specifically for 1+p = 1

[weary tiger]

oh okay thanks a lot

[stray reef]

ah no you're right p+pq= p is indeed called absorption

so is p(p+q) = p

[weary tiger]

ah alright thanks for clarifying

you are the best

[muted socket]

These two also work just fine?

[pale epoch]

yes, all the properties you want are (more or less) directly inherited from the logical operators

(you can even prove them with truth tables)

[narrow trench]

the parallels between set operations and logic operators are as direct as possible

they might as well be two ways of looking at the same thing

[muted socket]

Understood, thank you! Is there anywhere I can look up properties of logical operators? Will Google do? Cause' right now, I'm just guessing what I can and can't do with them based on what just makes sense

[muted socket]

Ahhh, I see

Very convenient

[pale epoch]

i have a list of them somewhere

like this?

[muted socket]

Yup, exactly what I needed. Thanks a bunch!

[pale epoch]

same for sets

#proofs-and-logic message for source

[muted socket]

Oh dang, they are basically identical, yeah

Much appreciated

[high ruin]

Hello I want to ask this:

To describe the various restaurants in the city, we let P denote the statement \The food
is good," Q denote the statement \The service is good," and R denote the statement \The
rating is three-star." Write the following statements in symbolic form.

(a) Either the food is good, or the service is good, or both.
(b) Either the food is good, or the service is good, but not both.
(c) If both the food and services are good, then the rating will be three-star.
(d) It is not true that a three-star rating always means good food and good service.

I have the following answers:

1. P OR Q
2. (P' AND Q) OR (P AND Q')
3. (P OR Q) -> R
4. R` -> (P AND Q)

Can someone help check whether my answers is correct or not?

[proven silo]

Might want to recheck 2,3 and 4

For example 3. it says if BOTH food and service are good then 3-star rating

[high ruin]

that what i was thinking too as well but not sure

[high ruin]

i basically make the equivalent of XOR for number 2

[proven silo]

2 is correct now, 3 and 4 are still wrong

[short steeple]

is there a channel i can go to for help regarding abstract algebra/group theory? i think this channel might be the place for it but i want to get the channel right before i ask my question

[cerulean wind]

there is a channel called #groups-rings-fields

[short steeple]

thank you! don't know how i missed it lol

[weary tiger]

I was reading this proof and I don't rally understand this point; my professor defined limit points as given $x\in S, \exists \epsilon > 0 \forall y: |x - y| < \epsilon \implies y \in S$

[vital dew]

justini

[pale epoch]

are you sure your given definition is that of limit point? it should be the definition of interior point

like, take [0, 1] in R, then 0 is not a limit point according to your definition, because for every epsilon, you will have -eps/2 at a distance less than eps from 0, but that is not in [0, 1]

[weary tiger]

My mistake

$\forall \delta > 0 \exists y \in S: 0 < |y - x| < \delta$

[pale epoch]

ok, yes that is better

have you heard the term epsilon/delta ball before?

(you can just say no btw...)

[weary tiger]

Yes but we haven't covered it in class

[pale epoch]

well ok, to reiterate i define a $\delta$ ball around $x \in X$ to be the set $B_\delta(x) = {y \in X \mid \lvert y-x\rvert < \delta}$

[vital dew]

Lochverstärker

[weary tiger]

So in 1-dimension, this is just an interval (if the topological space is the set of reals)

[pale epoch]

yes

in 2 dimensions its an open disk

in 3 dimensions an open ball

you can rephrase what it means to be a limit point in terms of those balls

so x is a limit point of some set S if every delta ball around x contains an element in S that is not x

or yet in other words: every delta ball around x intersects S\{x} non trivially

this will remain true if you replace the word "delta ball" by "open set" as in metric spaces the open sets are just sets that contain delta balls around each point

and this now gives you are more general definition of limit point that is applicable to all topological spaces and not just metric spaces

that is used in your picture

[weary tiger]

"If x is in U, a limit point of S, and U is a subset of s, then the intersection of U and S not containing the limit point x is non-empty"
So basically this statement?

[pale epoch]

yes

an open set U containing x is often called an open neighbourhood

and those play the role of open epsilon balls in general topological spaces

[weary tiger]

So how do I actually formulate the proof?

[pale epoch]

well, generally its a definition

you can prove this for metric spaces from your given definition

but then you first need to look up your exact definition of open set

you probably use "in metric spaces the open sets are just sets that contain delta balls around each point"

so in each open set you will find a delta ball around x and then you just use your definition of limit point

[wary scarab]

is G' the notation for the complement graph of G?

[outer hinge]

I feel weird about this

Does anyone have any comments ?

Also

I forgot to put brackets around my negation and the not symbol

[languid moss]

isthiscorrect?

[cerulean wind]

no way to know without know the formulas from class

[cerulean wind]

i think typing out the question would be helpful. i can’t really read what’s going on here, or rather, can’t find what your concern is

[outer hinge]

So, it gives us a set D and E, and then asks us to give a negation to the statement in which all elements x within D and an element y within E, XY is greater than it equal to Y

Then it asks which is true, the negation or original statement

[cerulean wind]

okay

so the original statement was just, for each x in D there is a y in E such that xy >= y

[outer hinge]

I know which is true however I want to ensure I’m arguing for it properly

And that my negation is a proper negation

[outer hinge]

Yes

[cerulean wind]

your argument outline looks fine.
to clean it up, i would just write for all x in D, x•0 = 0 >= 0 since 0 in E

cuts down on all the extraneous symbols

[languid moss]

thats my formula sheet @cerulean wind

[cerulean wind]

then no i would say this is incorrect

[languid moss]

thank you

so they want an equation not what it equals?

[cerulean wind]

ye

[languid moss]

better?

[cerulean wind]

yes

[languid moss]

❤️

ur a beast i always see you helping us plebs i appreciate it

[quaint star]

The last one is wrong though

In the second one, you removed the first term which is 1, so -1

But in the third one...

You are not removing 1

@languid moss

[languid moss]

in my notes it says that formula is n*c-1

if it starts at two

[quaint star]

No

Does it maybe say (n-1)c?

[quaint star]

That's wrong

The first term is c (or 5), so if you remove the first term, it will be c (or 5) less

So it should be nc - c

Or 5n - 5

[languid moss]

hmm okay thanks

[quaint star]

👍

[languid moss]

ahh ur right

she just fixed it in lecture

xD

n*c-c

[quaint star]

Do you understand why it's that?

[languid moss]

is it because your multiplying every term by c?

so i at 2 will be 10 but you need to start from 1 so you would need to subtract 5 to start at 1

[quaint star]

Every term is c

So when it's from 1 to 10

Then you are adding c to itself 10 times

c+c+c+c+c+c+c+c+c+c = 10c

But if you remove the first term

Then you only added up 9 cs

[cerulean wind]

i too am just a pleb. glad i could help tho

[languid moss]

i see thank you guys

for the first one am i only subtracting 1

[cerulean wind]

yea that one is right

[languid moss]

thanks 😄

[coarse cave]

is this correct?

for the question:

[vital dew]

abs_0

[marble pivot]

^ can I make this even simpler (no modular arithmetic)?

[meager prairie]

idk 🤔

for any 2 consecutive numbers, 2 divides one of them?

wlog a=2n b=2n+1 then 2|a

show b|c -> ab|ac here

if you dont have that already