discrete-math

[deft dock]

i dont want to do that

[snow sleet]

right

exactly

[deft dock]

okay so what im getting at

[snow sleet]

that route would require more NT skills

[deft dock]

2q and 2q + 1 is essentially the same as 3q, 3q + 1, and 3q + 2 in the sense that they represent all integers right?

[snow sleet]

right

[deft dock]

technically any divisor right?

[snow sleet]

yes

this is because you can partition the set of integers in various ways

[deft dock]

okay okay

wait both positive and negative right?

[snow sleet]

this is especially evident in the context of modular arithmetic

[deft dock]

i dont like the sound of that i dont wanna go there

[snow sleet]

divisors are typically positive

[deft dock]

well dont divisors technically have to be positive?

[snow sleet]

no

-1 divides 1

[deft dock]

because 0 < r < d

[snow sleet]

so -1 is a divisor of 1

[deft dock]

oh wait what

is q the divisor?

[snow sleet]

this is for when d is positive

[deft dock]

ohhhhhhhhhhh

okay vnm

nvm

[snow sleet]

there are various versions of the QRT

[deft dock]

i dont wanna go there either

[snow sleet]

if d=0, then that's not very interesting because that doesn't really partition the set of integers

[deft dock]

okay great

but the best thing i can do

is just stick to even divisors right?

at least for a proof like that

[snow sleet]

yes so that you can easily factor out a 4

[deft dock]

ight thanks logician

[snow sleet]

you're welcome! @deft dock

have you ever proved the version of the division algorithm for when you're given two positive integers? @deft dock

That version of the division algorithm is: Let $a,b>0$ be integers. Then there are unique integers $q$ and $r$ such that $a=qb+r$ and $0\leq r<b$.

[vital dew]

logician_pdx

[snow sleet]

This channel is open for questions

[heady ridge]

hey! does anyone know what this means, I been researching all morning but can not put my finger on it, A lot of source say the symbol to the left is delta but edge sub graph k would not have two element to make it a delta

[last timber]

@heady ridge context?

[heady ridge]

http://i.stanford.edu/~julian/pdfs/nips2012.pdf

this is the paper I am reading

https://www.sciencedirect.com/science/article/pii/S0166218X01003419

this paper also has some info

i think

I think I found a answer after the second paper, the symbol I believe means, number of elements and this statement is either 1 or 0

so if element exist in set Ck then it will be a 1

[last timber]

at where delta is met

found it

[heady ridge]

yeah

For a subset S of vertices of a graph G=(V,E), let us denote by δ(S) the number of edges with exactly one endpoint in S

[last timber]

well than i guess you use it

[heady ridge]

awsome, thnx for the support

[barren rose]

can someone help me with this?

[grave sluice]

interesting question just by trying things out I found two graphs each with 6 vertices
(and I am pretty sure its not possible with less)
It helped me starting with a odd-circle

[pallid lintel]

found two with 4 vertices. quite easy if you use loops and parallel pairs

i agree 6 is smallest if no loops/parallel pairs allowed

[abstract iron]

anyone know how to do this?

[weary tiger]

Do you understand what a subset is?

[abstract iron]

vaguely

it's like A & B but like A needs to be a subset of B

[weary tiger]

Explaining subsets in terms of subsets is a bit circular haha

A is a subset of B if all elements of A are in B

[abstract iron]

yeah discrete maths isn't my strong suit. I just started taking this class and all I thought of math is now becoming a lie taking this class lol

[weary tiger]

It’s quite different from the other parts

Does my definition make sense?

[abstract iron]

yes

so{2, 3 ,4 5} is equal to that as b

[weary tiger]

I’m not sure I understand that

If you were saying that 2,3,4,5 are the correct answers that’s quite wrong

[vital dew]

cplaursen

[abstract iron]

no

not at all

was meaning if the value of a was that, it'd be equal to b if those were the same values

[weary tiger]

I'm not sure I follow sorry

Anyway, which ones do you think count as subsets?

[cerulean wind]

0 and 1 are subsets and elements of 2 😎

[tranquil flint]

How does one write the generating function of bn = (-1)^{n} * (3n-3)C(2n-2)

i.e., B(X)

err in a closed form

like B(X) = sum of n = 0 to n = infinity of [(-1)^{n} * (3n-3)C(2n-2) * x^n]

but how do i simplify

is there a trick

[snow sleet]

@tranquil flint . I'm not entirely sure I'm interpreting your question correctly...it's kind of hard to read that math stuff without LaTeX. So let me rewrite your question. Lmk if it's what your asking

You're asking about finding a much simpler formula for $$B(x)=\sum_{n=0}^\infty(-1)^n\binom{3(n-1)}{2(n-1)}x^n,$$ correct?

[vital dew]

logician_pdx

[tranquil flint]

Yess

like for example sum of 0 to inf of x^n is just 1/1-x

[snow sleet]

okay gotcha

right

let's see if mathematica can do this:

give me a minute

[tranquil flint]

Hmm

like i thikn

im supposed to use

newtons binomial theorem

[snow sleet]

hm okay so mathematica "simplifies" this sum down to things involving cosh and sinh functions.

and yeah that $(-1)^n$ is def giving off some binomial theorem vibes. it's just that the $\binom{3(n-1)}{2(n-1)}$ really screws things up

what is this supposed to be the generating function for? what does it count? @tranquil flint

[vital dew]

logician_pdx

[snow sleet]

maybe we can think of a simpler formula if we know what $B(x)$ is the generating function for.

[vital dew]

logician_pdx

[snow sleet]

one way "simplified' version I can come up with is: (and I know this is really trivial lol) but:

$$B(x)=\sum_{n=0}^\infty(-x)^n\binom{3(n-1)}{2(n-1)}$$

[vital dew]

logician_pdx

[tranquil flint]

well

its the generating function of

bn

its an algebra question

[snow sleet]

I know, but what does that count?

oh

[tranquil flint]

its an algebra proof

[snow sleet]

ah

gotcha

[tranquil flint]

for example sum of 2nCn x^n is (1-4x)^(-1/2)

[snow sleet]

,w sum from n=0 to n=inf of (-x)^n times ((3n-3) choose (2n-2))

[vital dew]

Results provided by WolframAlpha

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

Requested by logician_pdx#7452

[tranquil flint]

lmfao

[snow sleet]

yeah see it's not really simplified

LMAO

[surreal sandal]

hi @snow sleet

pls respond to me

plssss

[clever arch]

is this channel free?

[cerulean wind]

yea go ahead and ask

[uncut bear]

I don’t know if this is the right channel. But is there any way to derive the sum of squares formula using the fact that each square is a consecutive odd away from each other? I want to try using some recursive method, but I’m just not sure how to go about it

[modern dew]

G(E,K) Ia a graph and L(G) is edge graph.....if G is eulerian the L is hamoltonian.....gotta prove that..but i also dont know what a kanten graph is

i mean edges graph *

[grave sluice]

thats just the graph you get when changing the vertices into edges and vice versa (obviously not all vertices have to become edges but I think the idea is clear) the formal definition is given

[jagged junco]

How many different graphs with 12 edges that consists of {1,2,..10} vertices have 2 vertices that their degree is 5?

[grave sluice]

what do you mean by {1,2,...10} vertices?

[jagged junco]

I think they meant this is the group of vertices in the graph. So every graph must contain those vertices

[grave sluice]

ah so there are 10 vertices

[jagged junco]

yes

and 12 edges

maybe it's just this:

This is the number of available graphs to have 10 vertices and 12 edges

now we need to subtract from this number all the graphs that don't have exactly 2 vertices that their degree is 5?

[jagged junco]

but it's hard to calculate this idk

[grave sluice]

yeah sorry I dont know either

[jagged junco]

tough

[errant bear]

yes

[civic horizon]

you can do polynomial interpolation

[deft dock]

how is this wrong???

[obtuse lance]

how is it right?

try to explain your thought process/show your work

[deft dock]

well because

for B C A

if we let x = 4n + 1

we can find an integer n to make it equal to 8m - 3

but with A C B

if we let x = 8m - 3

making it 4n + 1 involves a non integer

but m and n are both integers

[obtuse lance]

well we can solve directly by setting them equal to each other

[deft dock]

wdym

[obtuse lance]

8m-3=4n+1

if B is a subset of A, that means any choice of n we want, we can solve for it and find the m that makes it work

so try solving for n

[deft dock]

2m - 1

[obtuse lance]

yeah, so what m do you have to pick to make n=4 let's say

since that's one possibility

[deft dock]

5/2

[obtuse lance]

yeah, and that can't work because that's not an integer

[deft dock]

right thats what im saying

[obtuse lance]

2m-1 is always odd, so we are missing all the even n

that means B is not a subset of A

[deft dock]

wait what

[obtuse lance]

I think you're mixing them up, maybe instead try listing some of the elements of A and B out by plugging in 0, 1, 2, 3, ...

and you can compare those directly

[deft dock]

oh.

sigh

then how come we can do this??

i thought this guaranteed it being a subset?

[obtuse lance]

this is a subset of B

when you only pick odd n

going the reverse way you can do it, m=(n+1)/2

for any integer m, we can pick an integer n that works

[deft dock]

im still confused

i wrote out individual values

and saw how A C B but not B C A

but how come this works?

[obtuse lance]

this is not the same as what they do

if you want to do it this way for your problem you'll have to rearrange what you're given into that

you are plugging in, which is wrong

[deft dock]

ohhhhhhhhhhhhh

damn it

[obtuse lance]

maybe give it a try with the previous problem and I'll check it that way

[deft dock]

when i did it on my own i plugged in 3s-1 instead of rearranging and just assumed thats how you do it

by substituting in terms

[obtuse lance]

yeah, won't work

[deft dock]

i see now

okay so

no subtituting

just rearranging

right?

[obtuse lance]

oh you missed a 2

but yeah that's right

[deft dock]

wait what

[obtuse lance]

4(2m-1)+1

is what it should be after 8m-4+1

[deft dock]

ohhhhhhh yes yes

[obtuse lance]

other than that it's good

[deft dock]

[obtuse lance]

cool, good stuff

[deft dock]

i have one more

im still confused on reflexive, transitive, and sym

like does it have to be true for all values for it to be one of those properties?

[obtuse lance]

yeah

[deft dock]

or can it be true for a value/values and be called that propoert

[obtuse lance]

for all of the elements of the set the relation is defined on

[deft dock]

okay wiat so what about this one?

the relationship isnt transitive for all values

only 1,4,6

so how is it transitive?

same with the value of 3; its reflexive but not symmetric or transitive

this is the picture version

[obtuse lance]

sorry I said that poorly

like think of equality, it's reflexive, symmetric and transitive but that doesn't mean all numbers are equal

[obtuse lance]

we just have to check when it's true, a=b means b=a is symmetry

we can't have a=b with b != a

[next thorn]

Hey csn anyone help me differentiate

[obtuse lance]

@next thorn try #calculus

[deft dock]

my brain hurts man

so if it works once then it works ?

[deft dock]

like for this

if x = 0, then its reflexive

but any other number doesnt work

[obtuse lance]

1=1 is reflexivity with 1

2=2 is reflexivity with 2

etc

with your relation 1R1 we can check 5 | 1^2-1^2

since 5 | 0 is true, 1R1 is true, so it is reflexive for 1

we need to show xRx for all x to show it's reflexive for the whole set

symmetry means proving xRy is true makes yRx true

transitivity means given xRy and yRz as true means that we have xRz true too

[deft dock]

okay i get the reflexive for that one because its always going to make 5 | 0

oh wait

ohhhhhhhhhh

so

argh i think i get it but i dont know how to explain

like for it to be symmetric, we have to prove that xRy is true makes yRx true

but not every single value has to fit this description

like the "xRy is true" has to be there first, and then if yRx its symmetric

so like with 3, xRy isnt true, so it isn't considered

@obtuse lance idk if im understaning it correctly

[obtuse lance]

yeah that sounds perfect

[deft dock]

argh but for some reason it still makes no sense in my head

so for example

assuming xRy is true

if any value makes xRy true, but yRx false, it automatically becomes non symmetric right

[obtuse lance]

x=y means y=x is kind of a simple example

[deft dock]

and if any value makes it false

then its non symmetric

[obtuse lance]

yeah exactly

[deft dock]

but it doesnt have to inclue all values

[obtuse lance]

like < is not symmetric since x<y and y<x shouldn't both be true

[deft dock]

hmm okay

so in that case

im guessing reflexive is the easiest of them all?

to proove

?

like in that example

[deft dock]

this one

had one of these values not been reflexie

the entire relationship would be not reflexive right?

[obtuse lance]

yeah it's easy to prove reflexive here yeah

to prove it all you have to do is say xRx means 5 | x^2-x^2 which means 5|0 and you're done

since it didn't depend on which x we picked

[deft dock]

okay i think i got it thanks

[obtuse lance]

symmetric is also gonna be easy too

yeah you're welcome

[young jolt]

hey i got a question

how do i find the PROBABILITY

[tired jacinth]

<@&286206848099549185> Could someone help me with this question please

[obtuse lance]

use the hint and reduce mod 3

[deft dock]

i am hard stuck on this

[cerulean wind]

@deft dock can you see that the numerator is always one less than the denominator, even for 0 = 0/1

[hearty lagoon]

is this the same as finite math

I have finite in the fall and I wanna prepare for it

[cerulean wind]

yes

[hearty lagoon]

is it harder than calculus? the hardest math class I’ve ever taken was algebra 2 in high school and I’m really bad at math

[deft dock]

right

and ik its at least somthing over n

but that zero at the beginning is tripping me up

wait nvm i got it

[weary tiger]

need help with the manipulation part on (b)

[weary tiger]

<@&286206848099549185>

[deft dock]

i have no clue what this can be

i dont see anything except The commutative law is needed between between steps (3) and (4).

oh just realized now the second one as well (The commutative law is needed between between steps (1) and (2).)

[tired jacinth]

<@&286206848099549185> need help

[cerulean wind]

What have you tried @tired jacinth

[snow sleet]

@tired jacinth the function $f$ is bijective if and only if $\forall t\in\mathbb R,\exists! s\in\mathbb R\setminus{0}:f(s)=t$.

[vital dew]

logician_pdx

[pallid lintel]

anyone here good at drawing matroids?

[weary tiger]

What's an interesting topic to research in Set Theory/Logic on basic level?

[rigid tartan]

ordinals and cardinals? the principle of induction for ordinals

cantor's diagonalization argument proving that the cardinality of the natural numbers is not the same as the cardinality of the real numbers

boolean algebras as semantics for propositional logic

maybe find a good explanation for a popular audience that gives an overview of forcing and the independence of the continuum hypothesis. forcing is not really an introductory topic but it's interesting

[wary scarab]

Can someone help?

[deft dock]

for things like this, we don't have to write a formal proof right? we can just use set identities and rearrange one side to equal the other?

[cerulean wind]

sure, both are valid

[deft dock]

interesting; she told me that for this, i'd have to show both parts??

but i used set identities so like

do i still have to rearrange the LHS and then rearrange the RHS?

[civic horizon]

Pretty vague hint but try to consider both sides as counting the same thing in two different ways

[cerulean wind]

is the note actually related to the image you sent? i dont see A U B anywhere in your work

[wary scarab]

Can't think of a bijection

[civic horizon]

Alternatively you can probably use the closed form of the number of derangements and just bash your way through

Youll get some pretty awful double sum

Hmm its hard to give a hint without spoiling the entire thing

[cerulean wind]

i wanted to say that you have the recurrence relation $p_n(k) = \binom{n}{k}p_{n-k}(0)$ for $1\leq k\leq n$ and you have to use the dearangements for $p_n(0)$ in general

[vital dew]

coycoy

[deft dock]

wait no nvm lol

it was for this

this id have to show both right

A U B C B

and B C A U B

[cerulean wind]

yes in this case you would have to show two way containment

[wary scarab]

Thanks

[cerulean wind]

i would double check that tho

[deft dock]

i have no clue how to do this either

i didnt see any videos on it

[cerulean wind]

step through the algorithm. what is q after the first iteration?

[deft dock]

i have no clue what that means lol

[cerulean wind]

fix the variable i at i = 0. then q = a = 26 is how they got the first box

since i = 0 and q != 0, then you enter the while loop

[deft dock]

mhm

[cerulean wind]

r[0] gets assigned q mod 2 = 26 mod 2 = 0

q gets reassigned to q/2 = 26/2 = 13 (assuming q div 2 means q/2)

i gets reassigned to i + 1 = 0 + 1 = 1

[deft dock]

wait but now i = 1

[cerulean wind]

right, so what is q

[deft dock]

whats the relation between i and q???

[cerulean wind]

q got reassigned to 13 in the first iteration of the while loop, when i = 0

[deft dock]

oh wait

so 13 mod 2

1?

and then 1 div 2?

[cerulean wind]

huh?

[deft dock]

idk man

[cerulean wind]

idk how else to explain this lol

[wary scarab]

Here we're choosing k fixed points out of n and permuting the remaining ones such that there is no fixed point right?

[cerulean wind]

yes, that was the intuition

[wary scarab]

ok

[deft dock]

okay so this worked

so does q go through it twice now?

[cerulean wind]

to clear up, div is integer division, meaning that q div 2 is the integer quotient you get when performing q/2.

[deft dock]

right

wait so r[0] would be 0 right?

because 26 mod 2 is 0?

[cerulean wind]

yes

then i gets incremented to 1

[deft dock]

and then what?

[cerulean wind]

since the statement (i = 0 or q != 0) is true, then you re-enter the while loop with your new reassigned variables
i := 1 and q := 13

[deft dock]

okay so then

under the 2 in the q row

it would be 6?

and r[1] would be 1?

[cerulean wind]

right

[deft dock]

okayyyyyyyyyyyyy that makes sense

so new q on every interation

what ever that means

[cerulean wind]

then you rince and repeat until (i = 0 or q != 0) is false

an iteration is just one time through the loop

so the first iteration was when i = 0, the second iteration was when i = 1, ... and so on

[deft dock]

wait so what would 1 div 2 be?

1/2?

[cerulean wind]

what is the integer quotient that you get when you divide 2 into 1

it should be of the form n (remainder m), where n is the quotient

[deft dock]

itd be .5 but thats not an integer

[cerulean wind]

no, it'd be 0

1 div 2 is 0 (remainder 1)

[deft dock]

ohhhhhhhhhhhh

[cerulean wind]

if you do long division to compute 1 divided by 2, you will see why

[deft dock]

yeah i see

ah okay thanks

[cerulean wind]

yw

[wary scarab]

@cerulean wind I'm not able to calculate the summation after this, are there any identities i should know

[cerulean wind]

not sure. there is a recurrence relation for derangements, but i haven’t worked through the problem all the way

[wary scarab]

nvm i figured it out

[weary tiger]

For all sets A, B and C. If $A\cup B \subseteq A\cup C$ then $B\subseteq C$

[vital dew]

Keanan

[weary tiger]

so since x is in A union B this means that x will be in A union C, which means x in B as well as C thus B sub C?

[red nest]

This statement is false, {x}union {x} is a subset of {x} union the empty set, but {x} is not a subset of the empty set

[weary tiger]

Maybe I have to show some subset {x}?

Oh okay

[red nest]

I think I have a bijective proof of this, just check if this makes sense: Given a permutation and a chosen fixed point of the permutation, t, make a new permutation by erasing t from the permutation and for all numbers greater than t, reducing its value by 1. Then add the number n to make this a permutation on n numbers by mapping n to t and taking the number mapping to t and mapping it to n instead. This is a new permutation on n and this map should be a bijection from the set of permutations with a chosen fixed point to the set of permutations.

[weary tiger]

@red nest wait where do we get the empty set from?

[red nest]

Let A={x}, B={x} and C=empty set

[weary tiger]

Ah you chose it okay

Makes sense now

[red nest]

Yeah

[weary tiger]

For all sets A, B and C, if $A-B=A-C$ then $(A\cap B)-C=\emptyset$

[vital dew]

Keanan

[weary tiger]

Do I prove this by contradiction?

[vale cairn]

The conclusion is equivalent to saying A cap B is a subset of C I suppose, which isn't v hard to show directly

[cerulean wind]

you could do it that way, sure

a hint for a direct proof: $(A\cap B)-C= (A-C)\cap B$…

[vital dew]

coycoy

[snow sleet]

Note that by symmetry, if you prove this statement, you will have also proved: For all sets $A,B,C$ if $A-B=A-C$, then $(A\cap C)-B=\emptyset$.

[vital dew]

logician_pdx

[snow sleet]

That's just a fun fact...I doubt that'll help with the proof

[wary scarab]

I think it works

[red nest]

Nice

[fierce osprey]

is that pseudocode, or a language I don't know :p

[weary tiger]

Thanks!

[weary tiger]

Thank u

[weary tiger]

Thanks as well!

[snow sleet]

You're welcome!

[tranquil flint]

Can anyone help me figure out a EGF for non decreasing sub sequences of sequences of length n strings

comprised of only {1,2}

so like {x1, x2, x3, x4 .... xn} subseqnce of this<<

and at least one of 1,2 used

trying to write it as an EGF

what i have is sum from k = 1 to infinity of 2^k / (something?) x^k/k!

cuz each slot has 2 options, and k = 1 accounts for the "at least 1 of {1,2}" condition"

you can arrange {1,2} in a string of length n

Need to figure out what that something is 😭

[weary tiger]

Hi, what would be a trick to compute this?

[proven silo]

Find prime factorization

(Or euclids algorithm)

[weary tiger]

Sometimes in courses I found that people said that 32 = -1 modulo 11

Because 33-1 = 32

Can you really have negative numbers in modulo calculations?

[maiden notch]

ofc

[weary tiger]

Nice thanks!

So
In the 1st problem can I use that fact?

[weary tiger]

R11(2^1408) = R11((2^5)^281 * 2^3)
= R11(32^281 * 2^3)
= R11(R11(32)^281 * R11(2)^3)
=R11((-1)^281 * 2^3)
=R11(-1 * 8)
=R11(-8) = -8 or 3
Is that correct?

[proven silo]

If R_11 is mod 11 then yes

[weary tiger]

Ok nice, thanks (:

=R11(-8) = -8 or 3
Is that also correct in this context to say 3?

When you find -8

I mean is the notation correct?

[proven silo]

You would always leave the answer as 3

[weary tiger]

I have For all $n \in \mathbb{Z}, n^3+n$ is even. Should I let the entire expression equal 2k?

[vital dew]

Keanan

[zinc marsh]

Which one is bigger asymtotically in big O notation

log(n) and n/log(n)

[remote cosmos]

can you reason about it?

maybe change the variables as well to make it clearer for yourself

try that before using a graphing tool

[zinc marsh]

I think it n / log (n) is bigger now that i think about it

because log(n) is in O(n^epsilon) for every epsilon >0

so 1/log(n) should be bounded below by 1/n^epsilon (in big Omega(1/n^epsilon))

n/log(n) is thus in big Omega(n/n^epsilon))

[remote cosmos]

which is bigger between n and log n?

[zinc marsh]

n

[remote cosmos]

and what happens as n gets large when you have larger growth/smaller growth

[zinc marsh]

not sure what you mean 😄

[remote cosmos]

so as n --> inf

f(n)/g(n) and f is larger growth rate than g

[zinc marsh]

well then lim to infinity

lim f(n)/g(n) i mean

ah

[remote cosmos]

ya

[zinc marsh]

i can consider lim log(n) / (n/log(n))

[remote cosmos]

that's another way yes

[zinc marsh]

yeah lim approach zero

so n/log(n) larger

thanks !

[remote cosmos]

np!

and yea the graph will confirm for you too

but the graph doesn't help on exams or interviews hahahah

[zinc marsh]

unless it's multiple choice question haha

[remote cosmos]

true

[glacial estuary]

In the case of a scrabble question

What is the minimum number of vowel ('A', 'E', 'I', 'O', 'U') tiles you must have to be guaranteed to have at least one of each vowel tile?

anyone knows how to do this

The topic is on Counting

[cerulean wind]

i think you need more constraints, no? can i use each vowel tile more than once? is there a limit to how many times i can use a vowel tile more than once?
is there a set number of vowel tiles that has to be on the board at all times?

as stated, i could take any square board with all vowel tiles and have them all be the vowel ‘A’.

[glacial estuary]

The practice question just says this

the quantity and scoring system is as follows with the one that can be found in the internet

[cerulean wind]

i want to say 39. worst case scenario, you pick all E’s, all A’s all I’s and all O’s, for a total of 38 vowel tiles. the only vowel left at that point is u, so the next choice has to be that vowel, in which case you have at least one A E I O and U vowel tile.

[candid herald]

how so solve this lol

[remote cosmos]

ah classic sock problem

lol

what's your attempt

[candid herald]

well ik the denominator shud be like

(2n!)/2^n?

[remote cosmos]

did you try drawing it out for small values of n?

[candid herald]

lemme try rw

rq*

[remote cosmos]

all these counting problems really helps to do that

as you get used to nCr, nPr, etc.

[candid herald]

yeah i heard from classmates this is p tough tho like we did more basic counting problems last week

[remote cosmos]

like, draw out, notice pattern, take rational guesses as to why that pattern is true, then try to replicate with an adjusted problem to confirm

in an exam this way you can think on your toes and know it better

[candid herald]

they expect like formal work 😔

[remote cosmos]

counting is less memorization and more practice

yes but you need intuition for formal

like if you try to prove the famous identity

sure you could do it arithmetically

but seeing it in pascal's triangle also makes it seem less trivial

[candid herald]

yeah

[remote cosmos]

there's also often 2 or 3 ways to count the same thing

but not for every problem... i feel like drawing it is useful to rationalizing the multiple ways so it's easier to click when you need one over another

[snow sleet]

they never said socks within the same pair are identical. (i.e., consider a certain pair, they never said having the left sock L to the left of the right sock R in that same pair would be different from having the right sock R in that pair to the left of the left sock L in that pair. So LR isn't considered the same as RL)

@candid herald What do you think the denominator should be then?

[candid herald]

yeah i think it should just be

(2n)!

[snow sleet]

yes good

I agree

[candid herald]

ik we apply pie but I am still confused

[snow sleet]

okay yes! that is exactly what we will employ for the numerator

so we will count the complement and subtract from the total

the total is what?

[candid herald]

like the sum of the events that a pair is matched?

[snow sleet]

no

[candid herald]

1??

[snow sleet]

well I'm thinking about it this way:

we need to find $x$ in the probability fraction $\frac{x}{(2n)!}$

[vital dew]

logician_pdx

[snow sleet]

so $x$ must be of the form $(2n)!-y$ for some $y$. We need to find $y$.

[vital dew]

logician_pdx

[snow sleet]

because we're counting the complement

and subtracting it from the total, (2n)!

make sense?

[candid herald]

ohhh

so are we doing complementary counting

[snow sleet]

yes

exactly

this is why I said complement lol

[candid herald]

yeah oops i am dense

[snow sleet]

okay so let's calculate what y should be

we could fix any of the n pairs to have the socks in that pair glued together.

[candid herald]

mk

[snow sleet]

Then we can rearrange the rest in (2n-2)! ways

but we must also multiply by 2

since the socks in the pair can swap and still be next to each other

[candid herald]

why wouldnt it be 2^n

or multiplied by 2^n*

[snow sleet]

so the first thing we will subtract off from (2n)! will be 2n(2n-2)!

[snow sleet]

because we're only swapping the socks in the one pair of socks we selected

[candid herald]

ohhhh

[snow sleet]

okay, so let's keep going

ready to move on?

[candid herald]

yeah

[snow sleet]

currently we have $x=(2n)!-\left(2n(2n-2)!\right)$, but we're not done yet

[vital dew]

logician_pdx

[candid herald]

yeah htis is just a guess but do we keep subtracting like

but increasing

[snow sleet]

so now we must add back when two pairs are glued together

[snow sleet]

no

PIE alternates adding and subtracting

[candid herald]

yeah thats what i kinda meant oops

[snow sleet]

so if two pairs are glued together, how many arrangements are there for that scenario?

[candid herald]

4n^2 * (2n-4)!

[snow sleet]

no

that n^2 should be (n choose 2)

[candid herald]

oh uhh 4 * (2n-4)!

[snow sleet]

and let's write that 4 as 2^2

[snow sleet]

no

[snow sleet]

read this

of the n pairs, we choose 2 of them that'll be glued together

for those two pairs, we have 2^2

[candid herald]

ohhh

wait i get it

i thoguht the 2n

was to account

for hte

switching

[snow sleet]

then the remaining can rearrange in (2n-4)!

[candid herald]

so i squared

ye

[snow sleet]

okay cool

so now you're back on track

so do you see a pattern here?

[candid herald]

so -4 * nc2 * (2n-4)! + 8 nc3 (2n-6)! - so on

yeah

[snow sleet]

where are your factorials?

[candid herald]

gimme a minute lemme generalize it in latex and send a pic

[snow sleet]

so let's write this using sum notation

[candid herald]

all over the denominator

rite

of (2n)!

o wait lemme add parentheses

[snow sleet]

no

[snow sleet]

no

The numerator should be: $\sum_{i=0}^n(-1)^i\cdot2^i\binom{n}{i}(2n-2i)!$

[vital dew]

logician_pdx

[candid herald]

ohh ya oop

wait should it be

[snow sleet]

you shouldn't have 2^n there

[candid herald]

0 through n

or

1 through

n

[candid herald]

yeah got it

wait but should it be

sum of 0 through n or 1 through n

[snow sleet]

where your sum runs from depends on whether you take out (2n)! out already

I generalized so that you see that when i=0, we get (2n)!

[candid herald]

ohhhhh

thx so much u made it very understandable

[snow sleet]

you're welcome!

So to finalize...

the probability is

$\frac{\sum_{i=0}^n(-1)^i\cdot2^i\binom{n}{i}(2n-2i)!}{(2n)!}$

[vital dew]

logician_pdx

[snow sleet]

it looks slightly better tho if you write it like

$\frac{1}{(2n)!}\sum_{i=0}^n(-2)^i\binom{n}{i}(2n-2i)!$

[vital dew]

logician_pdx

[candid herald]

thx so much 🙏

[snow sleet]

You're welcome! Feel free to hmu if you have more questions with these types of problems!

This channel is open for questions.

[candid herald]

wai i thought abt it shouldnt it be 2n - i

@snow sleet

[snow sleet]

hmm let me think

[candid herald]

ohh mk

ooh ok

[snow sleet]

hang on a sec

@candid herald

Ah yes, you're right; good catch!!

So answer should be: $\frac{1}{(2n)!}\sum_{i=0}^n(-2)^i\binom{n}{i}(2n-i)!$

[vital dew]

logician_pdx

[candid herald]

[snow sleet]

because after you've chosen the i pairs, you glue those in the i pairs together and treat each pair as one object then rearrange all of the objects in (2n-i)! ways and then multiply by (-2)^i for those within the i pairs

This channel is open for questions

[candid herald]

hi @snow sleet can u help me with this question

like how would i prove this

rigourously

[snow sleet]

hi @candid herald those problems are too probabilistic for me tbh. I'm more of a combinatorialist. I recommend asking this in a probability/stats channel

[young star]

why is 5^k - 5 = a multiple of 4? this just came up in my proof's answer, idk how I was supposed to just know this fact o.o

[stray reef]

do you have access to modular arithmetic

[solid tree]

Can someone help me with this I need to find the length and the volume is 5 and you can see the length is 2.5 and the 2 is probably the width or the height idk but then I need to circle a,b or c and that's where I'm confused

[stray reef]

you should talk to your teacher and ask them for a worksheet where the formatting isn't screwed to hell

[solid tree]

Lol yeah I'll be asking them

[fierce osprey]

That is messed up lol

Also I didn’t know they teach this in discrete math

[snow sleet]

This is because 5^{k-1} is congruent to 1 modulo 4. Multiplying through by 5 gives the result.

[deft dock]

does this just mean all real numbers except zero?

[unreal stump]

Yes

[deft dock]

so then this proof is correct im guessing?

[cerulean wind]

yes that’s fine

[deft dock]

and this just means all real numbers including 0?

[cerulean wind]

[0,infinity) = {x in R : x >= 0}

[deft dock]

pog

almost got scared for a second because i didnt see this notation in the tutorial videos but then i decided to start using my brain

[cerulean wind]

lol

[deft dock]

wait so whats the difference between 2 and 3?

notation wise

[cerulean wind]

nothing, notation wise

[deft dock]

average discrete math teacher confusing a high schooler

nice

[cerulean wind]

just the codomains are different sets and the functions are different

[deft dock]

wait what

the thing on the other side of the --> is the range right?

[cerulean wind]

it’s the codomain, not necessarily the range

[deft dock]

oh yeah im confusing teh stuff

X --> Y

so number 2 is all the positive real numbers including 0

and number 3 is all real numbers including 0

?

[cerulean wind]

the codomain in two is the set of all non-negative real numbers.

the codomain in three is the set of all real numbers

[deft dock]

ahhhh okay

but proof wise

[cerulean wind]

so yes. you’re right

[deft dock]

its the same thing right?

id write the proof the same for every "proof onto.." just change a few things here and there

[zinc marsh]

What is some counter example to the statement: "Intersection of 2 matroids is a matroid"

Formally: Let (E,M1) and (E,M2) be matroids. Then (E, M1 intersects M2) is a matroid

[deft dock]

for this why cant we just say "Let y be a nonnegative real number..."?

[stray reef]

$\bR^{nonneg}$ is one hell of a notation

[vital dew]

Ann

[stray reef]

even $[0, +\infty)$ is shorter

[vital dew]

Ann

[stray reef]

but you can say "let y be a nonnegative real number"

or just "let y ≥ 0"

[deft dock]

ah so i dont even have to define the domain?

is that assumed?

[stray reef]

wym by 'define the domain'

if anything, y lives in the codomain

[deft dock]

like Z, R, Q, etc

those thigns

things

real numbers, integers, the other stuff

[stray reef]

you can say ``let $y \in [0, +\infty)$'' if you want

[vital dew]

Ann

[deft dock]

ahhhh okay

im gonna stick to words; these symbols are confusing

[stray reef]

symbols are short and to the point

[deft dock]

yeah but i feel like im gonna mess up with the notation on a test or something and then get stupid points deducted

so does this work

actually lemme try symbols

okay does this work

[zinc marsh]

@deft dock it's just notation don't worry about it too much. It's vanity matter. in fact I prefer more verbal proofs

Reading a bunch of symbols give me headache.

[deft dock]

i have found my people

okay this is starting to get dumb

why not just say h(4sqrty) = (4sqrty)^4?

why mention h(x) first?

theres only one function anyways isnt that kinda common sense what function we're talking about?

context

[cerulean wind]

yea but idk. it doesn’t hurt anything

[deft dock]

how do i reason that x is a real number based off of y?

[zinc marsh]

It should be cube root of (y+4)

[deft dock]

yup just realized thanks

i was wondering why she wanted us to do (sqrty + 4)^3

okay same question did i reason x correctly?

[zinc marsh]

yes looks fine for your use case. i don't think you need to show that cube root of a real number always stays in R

[deft dock]

yeah ik i just wanna provide at least a statement beacuse thats what the prof did in her example vid

[zinc marsh]

if you do then well you go into a rabbit hole. I think you have to invoke the least upper bound property of real number

[deft dock]

no clue what that is lol

[zinc marsh]

it means that for every subset of R bounded by above, (means that for every element x in that set, there is a constant C s.t x<C), it has a least upper bound. (means if it has C as an upper bound, then should me a smallest C' s.t C' is an upper bound and every other upper bound is >C')

also called completeness

yeah if you don't know that then i don't think you have to prove it in the proof. just say cube root of real number is indeed a real number as u did

[deft dock]

i just did this but just elaborated a little bit more

[zinc marsh]

anyway i think your questions are more suited to calculus than discrete math

[deft dock]

thats good to know (i take calc next year as a junior )

[snow sleet]

@deft dock That's a good proof for showing f is onto

I'd shorten your proof a bit, and cut out some nitty gritty details about why we know x is a real number, but it really depends on how much detail your prof/teacher wants you to show

My proof would be:

\begin{proof}Let $f$ be as described. Given $y\in\mathbb R$, choose $x=\sqrt[3]{y+4}$. Then $f(x)=\left(\sqrt[3]{y+4}\right)^3-4=y+4-4=y$. Hence we conclude $f$ is surjective.\end{proof}

[vital dew]

logician_pdx

[snow sleet]

but your proof works just fine @deft dock

[deft dock]

niceeeeeeeee

i wanna stay as technical as possible

because like

strange prof

also is this right?

[snow sleet]

ah gotcha

not sure why they didn't stick with g throughout the b and c but lmao kk

[deft dock]

just realized that too lolol

[snow sleet]

yeah i mean you don't wanna be so detailed that the flow of the proof gets lost or stops completely

[deft dock]

yeah i can see that

wait since it says no proof, i dont have to provide a counter example either right

[snow sleet]

correct

in other words, they are saying "No justification is required."

[deft dock]

pog

so those are fine right?

[snow sleet]

4a looks good

[deft dock]

and b and c i just used the logic taht they literally give us the domain and range for sin(x)

so that makes c correct

dont know about b though

well cause i was thinking

for b

[snow sleet]

I'd recommend plotting sinx for the last two

,w Plot sin x

[vital dew]

Results provided by WolframAlpha

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

Requested by logician_pdx#7452

[deft dock]

oh wait.

one to one means its a function

and sin(x) is a function

so it is true...

wait does it not

the line test thing?

[cerulean wind]

one to one means injective

[snow sleet]

you're not asked to determine if those are functions

[deft dock]

but arent functions one to one?

[snow sleet]

not all of em

consider a parabola

[deft dock]

oh yeah.

[cerulean wind]

or maybe… sin

[snow sleet]

yea, so for this one (b), you can think about this without even plotting it too

can you find more than one value of $x\in(-\infty,\infty)$ such that $sin(x)=1$?

[vital dew]

logician_pdx

[snow sleet]

If you can, problem b is not injective

[deft dock]

oh no you cant

because of sin^1(x) domain

[snow sleet]

yes you can

[deft dock]

hmph

wait whattttttt

[snow sleet]

yes consider pi/2 and (pi/2)+2pi

[deft dock]

[snow sleet]

,w sin(pi/2)

[deft dock]

okay yeah

[vital dew]

Results provided by WolframAlpha

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

Requested by logician_pdx#7452

[snow sleet]

,w sin(2pi+(pi/2))

[deft dock]

,w sin(2pi+(pi/2))

[vital dew]

Results provided by WolframAlpha

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

Requested by z|z#0001

[deft dock]

ah oaky

[vital dew]

Results provided by WolframAlpha

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

Requested by logician_pdx#7452

[snow sleet]

yea typo lmao

[deft dock]

but i thought one to one meant like

for every x there is only one y and no more

[snow sleet]

no

that means it's a function

it means that it's well-defined

[deft dock]

they gave this defintion and ihave no clue what it means

[deft dock]

ohhhhhhhhh

[snow sleet]

yes

[snow sleet]

this is correct

[deft dock]

i have no clue what it means

[cerulean wind]

look at some simple functions first

try f(x) = x
or
f(x) = c for some constant c

[snow sleet]

it means that you can give me any two points in X and if they are different, they map to different points

[deft dock]

1-1 if and only if for every x1 and x2 in the set X, if f(x1) = f(x2) then x1 = x2

the bold part

[snow sleet]

look at the contrapositive

[deft dock]

if x1 does not equal to x2, then f(x1) does not equal to f(x2)?

[snow sleet]

yes

[deft dock]

okay okay

so tehn

[snow sleet]

exactly what I'm saying here^

b isn't injective because we found a pair x1 and x2 that were different but got mapped to the same point

[deft dock]

but with the sin question, f(x1) did not equal to f(x2) but it still produced the same y?

[snow sleet]

yes it did

x1 was pi/2

x2 was 2pi +(pi/2)

those are different

and they both get mapped to 1

[deft dock]

i thought they had to be the same?

[deft dock]

from this

[snow sleet]

that's if it is injective.

This function is not injective

we just showed that it's not injective by finding that pair

[deft dock]

so injective = not onto

and not injective = onto

[cerulean wind]

no

[snow sleet]

huh?

[deft dock]

[snow sleet]

those aren't equivalent

think about what it means for a function to not be one-to-one. This means that there exists a pair $x_1,x_2\in X$ such that $f(x_1)=f(x_2)$ and $x_1\neq x_2$

[vital dew]

logician_pdx

[snow sleet]

where X is the domain of f

[deft dock]

okay understood

[snow sleet]

okay dope

so we found such a pair, right?

[deft dock]

yeah pi/2 and pi/2 + 2 pi

[snow sleet]

so the function in 4b isn't one-to-one

[deft dock]

no

wait i had false though

i was saying it wasn't one to one

[snow sleet]

that's right

[deft dock]

wait i thought you said 4b was wrong

[snow sleet]

nope

I deleted that right after I commented that

[deft dock]

ohhhhhhhhhhhhhhhhhhh

[snow sleet]

I was thinking of another function for some reason

lmao

[deft dock]

iz okay at least i truely learned what one to one actually is

[snow sleet]

but maybe it was for the best

[deft dock]

would have been bad if i had thought it was just a regular function

[snow sleet]

yes because at least now you have a better understanding of the definition of injection

[deft dock]

okay well maybe not injection...

injection still no make sense

[snow sleet]

that's one-to-one

[zinc marsh]

https://www.mathsisfun.com/sets/injective-surjective-bijective.html

[deft dock]

so if its one to one, its injective

hold on isnt this linear algebra???

[snow sleet]

the converse is true as well

[deft dock]

i rememebr watching a few khan academy videos

[zinc marsh]

There some graphical illustration

[snow sleet]

a function f is injective if and only if f is one-to-one

[deft dock]

thank god

[zinc marsh]

You seem like a visual learner

[deft dock]

and if it isnt one to one no injective

so

one to one prooves injectivity

or whatever

[snow sleet]

yes

[deft dock]

not the other way around

[snow sleet]

wym?

they are equivalent

[deft dock]

like does it being injective mean its one to one?

ohhhhhhhhhhh

[snow sleet]

yes

[deft dock]

im guessing i confused u guys when i said njective = one to one

i meant = as equivalent

[snow sleet]

this is why I said this^

[deft dock]

high school lets me get away with = and equivalent interchangeably lol

[snow sleet]

lmao

I mean there as logically equivalent (mathematically synonymous)

[deft dock]

wait doesnt the triple line mean equivalent?

[snow sleet]

sometimes

depends on the context

most people use a if and only if arrow to denote logical equivalence

[snow sleet]

this sometimes means something different in modular arithmetic.

[deft dock]

like P --> Q = ~P or Q

[proven silo]

Injective and one-to-one mean the exact same thing - just different words

[deft dock]

ah

ohhhhhhh isee it

[snow sleet]

I'd say (P implies Q) if and only if (~P or Q)

[deft dock]

the double arrow going back and forth

ohhhhhhhhhhhhh that makes a lot more sense

wait can this discrete math course help me with calc?

[snow sleet]

it might help you understand concepts better

but it likely isn't going to help with actual integration

[deft dock]

are there proofs in calc?

[snow sleet]

sometimes, but they usually aren't as technical as proofs in discrete math

[deft dock]

okay good

[snow sleet]

proofs in calc are usually just simple algebraic things

your answer for 4c is correct @deft dock

this is because you can just think of the unit circle

[deft dock]

wait so in regards to this

the opposite works too right?

[snow sleet]

what do you mean by "the opposite"?

[deft dock]

x1 = x2, but f(x1) does not equal f(x2)

actually wait

that doesnt make any sense...

wait actually can that happen?

and if so that would make it not one to one right?

[snow sleet]

well that wouldn't be a function

in the first place

because the same point got mapped to two different points

so that "function" doesn't even pass the vertical line test

hence not a function

[deft dock]

i need a visual lol

so like

[snow sleet]

well you can't have any function mapping the same point to two different points

[deft dock]

wait could you explain this in terms of domain and range?

[snow sleet]

sure

consider plotting the ordered pairs (0,1) and (0,0)

[deft dock]

mhm

[snow sleet]

what do you know about these dots?

[deft dock]

one is right above the other

[snow sleet]

aren't they on the same vertical line?

[deft dock]

yup

y axis

[snow sleet]

right

so does that pass the vertical line test?

[deft dock]

no

[snow sleet]

okay cool

so f took 0 and sent it two different places

so f isn't a function

[deft dock]

so we cant even apply these rules if f(x) isnt even a function deal with

not so much so rules

properties rather

[snow sleet]

correct

f must be a function in the first place.

[deft dock]

okay great

thanks a lot

[snow sleet]

see how they assumed f was a function in this definition?

[deft dock]

ah yes yes

[snow sleet]

okay dope. Good discussion. Now you have a better understanding of that definition!

[deft dock]

okay wait another question...

how can something be bijective???

because bijective is injective and sujrective

[snow sleet]

that's if the function is both injective and surjective

[deft dock]

but if its injective, its not surjective...

[snow sleet]

not necessarily

what is the definition of surjection? Do you know it off hand?

[deft dock]

like for every x in the set X, it maps to a y in the set Y

[snow sleet]

no

wrong

[deft dock]

but every Y in set Y has to have a arrow from X

[snow sleet]

for every y in Y, there's a x in X such that f(x)=y

[deft dock]

ohhhhhhhh yes yes

[deft dock]

yeha i was just going off of this

thats where the question sprouted from

but i can see the surjective not necessarily meaning not injective

[snow sleet]

okay so if the function f satisfies the definition of surjection and the definition of injection, then f is bijective.

[deft dock]

right

[snow sleet]

there's an even simpler definition of bijection

Here it is:

Let $f:A\rightarrow B$ be a function. Then $f$ is bijective if and only if for every $b\in B$, there exists exactly one $a\in A$ such that $f(a)=b$.

[vital dew]

logician_pdx

[narrow trench]

A visual way to see it is that on the diagrams above, if you reverse the arrows you get another function

(in the first case it's not a function because you have one point going nowhere)

(in the second case it's not a function because you have one point going at two places at once)

[snow sleet]

make sense @deft dock ?

[deft dock]

so bijective is just surjective, except every y can only have one x

[snow sleet]

yes

exactly

[deft dock]

okay okay

wait i have this bijective problem its similar to the true and false lemme do it and you can check

[snow sleet]

okay sounds good

[deft dock]

pls let this be right man

[narrow trench]

Correct

If you had included the negatives as input then it wouldn't be injective anymore

(-1)⁶=1⁶

[snow sleet]

This looks right

,w plot x^6

[vital dew]

Results provided by WolframAlpha

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

Requested by logician_pdx#7452

[narrow trench]

If you had incuded the negatives as output it wouldn't be surjective anymore (good luck having x⁶ be negative without complex numbers)

[snow sleet]

There's how you can see it visually

we're focused on the first quadrant

[deft dock]

and i negatives as input were included it wouldnt be injective right

[snow sleet]

as well as the origin

[narrow trench]

i said that before, but listen to the other explanation

[deft dock]

oh sorry lol might have gotten pushed back

but finally it kinda makes sense

wait so can i make the asummption

that

injective is more to do with input and surjective is more to do with output

[snow sleet]

I mean this just seems more like a personal preference than a mathematical fact. Both have much to do with the domain and the co-domain of the given function

[deft dock]

ah okay

[snow sleet]

so it's up to you on that one

[deft dock]

this is just telling me to state whether or not the inverse exists right? not actually find it?

[snow sleet]

it's asking you to find it as well