discrete-math

[vital dew]

texaspb

[muted gate]

if I go like this $a_{n + 3} = a_{n + 2} + a_{n + 1} + a_{n}$ is that correct?

[vital dew]

texaspb

[muted gate]

bro this is so hard for me

[olive wren]

Yep that’s true

But

This is simpler

[muted gate]

hm

ok so let me get this straight

when I do operations I'm not actually operating on the sum of a's itself but on the indexes instead

the sum is just denoting a sequence

[olive wren]

Well if you’re manipulating the sum by changing indexes ye

[olive wren]

It’s the sum of a series sure

[muted gate]

I don't entirely get why this makes sense

do you mind elaborating more?

[olive wren]

Sure

$a_{n+1} = \sum_{i=0}^n a_i = \underbrace{\left(\sum_{i=0}^{n-1} a_i\right)}_{=a_n} + a_n = 2a_n$

So you get $a_{n+1} = 2a_n$, so it’s a geometric series

[muted gate]

ok

I literally spent 5 minutes looking at this

but I got the reasoning behind it

ok now one last thing

does this make sense? $a_{n} = a_{n - 1} + a_{n - 2} + a_{n - 3}$
therefore
$a_{n + 3} = a_{n - 2} + a_{n - 1} + a_{n}$

[vital dew]

texaspb

[muted gate]

because if this makes sense I think i got it

[olive wren]

Yeah

That’s right

But how does that help?

[muted gate]

it just helps

HAHAHA

thank you so much

[olive wren]

[muted gate]

I can't explain, but helps in my head

[olive wren]

Ah okie

[muted gate]

ty again!!! really appreaciate it

[olive wren]

Ofc!

[wide vine]

If you have a some recursive relationship, are you always able to express it in a closed form?

Basically if I have some a_n recursive definition, how do I know if it is possible to always convert that into some a(n) function which will give me the answer without the use of recursion

this are notably, but I was curious if anything exist in general or if there is easy cases of knowing when it isn't feasible

[normal hatch]

How is { NOT (x) AND NOT (Z) } OR { X AND NOT (y) AND NOT (z) } == { NOT (x) AND NOT (z) } OR { NOT (y) AND NOT (z) }

[stray reef]

$(\neg x \land \neg z) \lor (x \land \neg y \land \neg z) \overset{?}{=} (\neg x \land \neg z) \lor (\neg y \land \neg z)$

[vital dew]

Ann

[stray reef]

is this what you're asking? @normal hatch

[normal hatch]

yeah..i dont understand how the x disappeared

[stray reef]

3+ hour delay...

i think you can just apply the distributive law here though

$x'z' + xy'z' = (x+x')(x'+y')(x'+z')(z'+x)(z'+y')(z'+z') \ = 1(x'+y')(x'+z')(z'+x)(z'+y')z'$

[vital dew]

Ann

[stray reef]

something like this

i might be veering off into the wrong direction

but whatever

[proven relic]

Pls anyone🙏🙏🙏

[muted gate]

try writing down what S and T are

write their elements down

[vernal cypress]

sos

[hard moth]

use inclusion-exclusion principle

[dark oyster]

Is it 9?

[weary tiger]

how does 2ˆ(k+1) + 2ˆ(k+1) = 2 * 2ˆ(k+1) ?

because there's two of them

let a = 2^(k+1)

then a+a=2*a

2*a=2 *2^(k+1)

[vernal cypress]

yup, correct

thanks

[dark oyster]

Can u solve a and b pls thanks

[weary tiger]

omg

that was embarrassing

ty @weary tiger

[muted gate]

what do you mean solve a and b? lol

please read #❓how-to-get-help, nobody will do your homework for you

[dire obsidian]

Can someone help me understand this?
It's about Finite State Machine Language sets

[dire obsidian]

what would be the expansions of B and C?

[serene walrus]

Clearly it's some form of school or college assignment

So, No.

[fickle turret]

how do you put math into a truth table?
like
1+2=3 is a proposition because this is correct but idk how to show it in truth table

[coral parcel]

That's not something you can use a truth table for.

Truth tables are for propositional logic, which is about how different propositions relate to each other -- and here you have only one of them.

[coral parcel]

Do you know what the set builder notation used to define B and C means?

[fickle turret]

ye thats what im thinking but for some reason part of our instruction is to create a truth table for it and i cant see how to do that

[dire obsidian]

kind of

I'm now more confused about what something like this means

${00}^*$

[vital dew]

Salt

[fickle turret]

only thing i can think of is to treat 1+2=3 as AorB= AorB

[coral parcel]

You have a definition of L^* in your first image -- though it is stated a little strangely, because Sigma is usually used for denoting the alphabet your strings are built from, but here it needs to mean a set of strings (that is, a language).

{00} is a set of strings which has the string 00 as its only element.

[severe swan]

How many subsets of {-6,-5,-4,...7,8,9} contain exactly three negative numbers and four positive numbers?

total numbers wanted: 7

numbers:
6 neg 9 pos
My answer:
P(6,3) x P(9,4)

Is this correct? I believe it is because the order of the numbers does not matter. Otherwise it would be combination and not permutation.

[crude mango]

you forgot 0

[dire obsidian]

wait by definiton lambda should also be included in ${00}^*$

[crude mango]

double whatever answer you got to account for including or excluding 0

[vital dew]

Salt

[crude mango]

also shouldnt that be choose function and not p function? or is that just notation im not familiar with?

$2 * {6\choose{3}} * {9\choose{4}}$

latex hates me

[coral parcel]

The empty string is an element of {00}*, but is not an element of {00}.

[dire obsidian]

is that the only difference between the two sets?

[coral parcel]

No.

[vital dew]

hiiistrex

[crude mango]

there we go

[coral parcel]

The definition of the Kleene star operator was at the bottom of your "red handwriting" image. Unfold it here and see what you get.

[severe swan]

The question on the homework said that 0 is neither positive nor negative so i didn't count it in my calculations

[crude mango]

it's neither positive nor negative, which means you still need to account for it, but differently from positive and negative

the question says nothing about the inclusion of 0

so we need to account for all possibilities it allows for

i.e. every allowable subset without 0 and every allowable subset with 0

which in this case means straight up doubling the answer

[coral parcel]

It's a matter of whether "exactly three negative numbers and four positive numbers" means

• "exactly three negative numbers and exactly four positive numbers and nothing else", or
• "there are exactly three negative numbers and there are exactly four positive numbers and I don't care what else there is"

[crude mango]

true

to me the second is implied

[coral parcel]

Both are reasonable interpretations.

[crude mango]

but ig it could go either way

is the question more specific

[severe swan]

it is not more specific sadly

[paper zinc]

use properties of the summation

[fickle turret]

if its something like hits
~x ^(~y v x) ^ y
can I use associative to
y^(~y v x) ^ ~x
then abrosption law to
~y^~x

[frank silo]

all solved

thanks 👍

[severe swan]

How can I solve this?

How many 5-element subsets of S = {1,2,3,4,5,6,7} have more odd numbers than even numbers?

1,3,5,7 so 4 odd
2,4,6 so 3 even

i know there are 21 subsets with 5 elements

[normal hatch]

'+' and ' * ' ?

[unreal stump]

Pick 3 odd 2 even or 4 odd 1 even

[stray reef]

• stands for or, * stands for and, ' stands for negation

can sometimes help de-clutter long boolean-algebraic expressions

[normal hatch]

oh thanks

[unreal stump]

So ${4\choose 3}
{3\choose 2} + {4\choose 1}
{3 \choose 0}$

[vital dew]

BYE BYE!

[dire obsidian]

that's the part i'm stuck at

[cosmic path]

hey, can someone help me with this, i need to know what is the BIG O Notation of this python code.

[cerulean wind]

in the worst case how many elements can be appended to L in the inner loop?

[weary tiger]

hi

Can anyone here help with induction?

[vital dew]

spatialerror

[weary tiger]

that C is meant to be combinations, I don't know the command

<@&286206848099549185>

that m is also bugging me out, because if m is zero the first case is equal to 1, if m is another natural then 0

With $0\leq m< n$ prove by induction that $\sum_{k=0}^{n} (-1)^k C^{n}_{k} k^{m} =0$ with $n,m \in \mathbb{N}$

[vital dew]

spatialerror

[cerulean wind]

\binom{m}{k}

[spare forge]

Can someone walk me through this section?:

[cerulean wind]

you are right that for m = 0, the sum is 1

[cerulean wind]

do you have to do it by induction?

[weary tiger]

yes induction

[cerulean wind]

what do you have so far?

[weary tiger]

actually I'm the process of proving the base case for m=0

[cerulean wind]

its not true for m = 0.

0C0 = 1, 0Ck for any k > 0 is 0

[spare forge]

A little bump? 😬

[weary tiger]

N must be greater or equal than 1, so the base case is when n = 1 and m =0, which therefore sets the sum from zero to one

f*cking tricky exercise if you ask me lol

[unreal stump]

Why induction tho

[cerulean wind]

(-1)^0 (0C0) 0^0 + (-1)^1 (0C1)1^0 = 1 - 0 = 1

its not true when m = 0

just treat it as a typo and make m > 0

then induct on n

[dire obsidian]

Can someone explain to me how finite state automata works? (I understand the regular kind I have trouble understanding the ones that have "memory/output")

[unreal stump]

You familiar with a stack @dire obsidian?

[dire obsidian]

what?

[unreal stump]

Stack in the programming sense

[dire obsidian]

yeah

[unreal stump]

Pushdown automatas are based on that

[dire obsidian]

I meant stuff like this when I said finite state automatas that have output

[unreal stump]

Like Mealy machines?

[unreal stump]

Yea Mealy

What's your doubt exactly

[dire obsidian]

oh sorry I had to leave for something

But yeah mb I don't really know what Mealy machines are

[unreal stump]

So mealy machines take in an input bit,output a corresponding bit and then move to the corresponding state

input bit here is letters from which the string is made

Output bit is a special set of alphabets reserved for output which could be same as input alphabet

[dire obsidian]

Ok so can you explain to me what the state table is saying?

[unreal stump]

Say you are in state s_0 and you get an input of 0

Then move to state s_0 and output 0

If you are in state s_0 and you get input of 1

Then move to state s_1 and output 0

If you get input 0,check what state you are in currently,then scan the first column of v and get entry corresponding to current state to get the new state

Repeat with w for output

[dire obsidian]

Ah right so for input you can get either 0 or 1

[dire obsidian]

How do you track 'last output'?

or is the output is instantaneous regardless of where you are in in the finite state machine?

[agile magnet]

I don't see a graph theory channel so imma ask here

I want to run a reading group at my university for graph theory

mainly as a way to get me to actually self study it

what are some recommended texts

We were going to use West's but that's what the textbook here is for the graph theory class.

and I don't want to just run a class for the reading group so a different text would be cool

[burnt oxide]

is the gcd of (9k+1,9) where k equals any non negative integer always = 1? and how do you prove this?

[obtuse lance]

Graph Theory by Reinhard Diestel is a popular book, I've read parts of it and it seems good, it's definitely more math based like definition -> theorem rather than application based, which might be worth considering depending on who is in your reading group

[obtuse lance]

You could prove it by induction, I'd recommend just generally proving the euclidean algorithm. For your problem all you really need to show is gcd(a,b) = gcd(a-b, b)

[burnt oxide]

ill give this a try, thank you very much!

[obtuse lance]

good luck 👍

[weary tiger]

how do we get 7

this is a generating function

[obtuse lance]

one way is differentiate it 46 times and then plug in x=0, then divide by 46!

or you can expand the 3 separate geometric series like (1+x^3+x^6+...)(1+x^4+x^8+...)(1+x^20+x^40+...) then look at what terms in the product will contribute to x^47

but if you're going to do it that way you might as well just work out the partitions of 47=3a+4b+20c by hand since that's all encoded in the exponents

that's basically what lets you do the dumb way of taking the derivative I described first, which is arguably one of the reasons you make a generating function in the first place

[weary tiger]

thx

[tidal tulip]

Prove by induction that the number of functions from $A$ to $B$ is $|B|^{|A|}$

Can I get a proof check?

Let $A, B$ be finite nonempty sets. Prove that the number of functions from $A$ to $B$ is $|B|^{|A|}$ (hint: use induction on $|A|$).

\Proof by Induction:

\Base Case:

\Suppose $|A|=1$, then by the definition of a function every element in the domain of A has to map to a single element in the codomain of $B$. The number of ways to map a single element of A to elements in B is $|B|^|A|} = |B|^ {|1|} = |B|$. Thus we see that for the base case if $|A|=1$, the number of mappings from $A$ to $B$ is $|B|^ {|A|}$.

\

\Induction Hypothesis:

\

Assume for an arbitrary $k \in \mathbb{N}$, if $|A|=k$, then $|B|^ {|A|}$ = $|B|^ {|k|}$.

\Induction Step:

\Assuming $|A|=k$, you have $|B|^{|k|}$ functions from $A$ to $B$ (induction hypothesis). If you add one element to $A$ then each of the $|B|^ {|k|}$ functions has an additional $|B|$ choices of how to map that element. Thus you have $|B|^ {|k|}$ * $|B|$ possible functions from $A$ to $B$ when $|A|=k+1$.

Thus we see that if $|A|=k+1$ then the number of functions from $A$ to $B$ is $|B|^{|k|}$ * $|B|$ = $|B|^{|k+1|}$

[vital dew]

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

[tidal tulip]

can i get a proof check

[weary tiger]

how do i get good at generating functions

[obtuse lance]

practice, read generatingfunctionology would hel

[tidal tulip]

can someone check my induction proof

[obtuse lance]

I won't because I don't believe that should be proved with induction, but maybe someone else will

[tidal tulip]

it wasn’t my choice to prove it by induction

it was a problem statement to do so

[obtuse lance]

i empathize

[tidal tulip]

thanks haha

[weary tiger]

c)

trying to solve c?

G(x) = -1 + 0x +1x^2 + 2x^3 + ...

is it just 1/1-x

[obtuse lance]

not quite, look at the derivative of the geometric series

[weary tiger]

idk how to do derivatives

[obtuse lance]

you know what an infinite series is though, which means you must have studied limits, which means you probably learned derivatives at one point though, right?

[weary tiger]

i only have precal knowledge

[obtuse lance]

the alternative is messier, you could try squaring the infinite series for the geometric series

[weary tiger]

can i learn simple derivaties quickly?

[obtuse lance]

for this, yeah probably

idk it will already get harder like part d

I don't see you doing that without knowing about the taylor series of e^x

which is more calculus

[obtuse lance]

are you self teaching or what's the context of this

[weary tiger]

im getting ready for a test

[obtuse lance]

have they taught about the cauchy product?

[weary tiger]

no

[obtuse lance]

to do part c you'll need to learn how to multiply two series or how to take derivatives, not sure what you'd be expected to know for your test if any

[weary tiger]

multiplying two series doesnt sound too hard

alright imma watch a few vids on generating functions

and jump back on trying to solve some questions

[ornate kettle]

can someone tell me if my answers are right or wrong??

[severe swan]

Can someone explain how to solve this?

How many (base 10) integers (leading O's are NOT allowed) between 1 and 9999 are palindromes?

All of the following are examples of such integers: 5, 22, 373, and 8448. The following would not count because they have leading O's: 0,00.000, 0000, 010, 0440.

Answer: 198

[mild temple]

sum of g.s.:

[vital dew]

vin100

vin100

vin100

[weary tiger]

Noice

[fickle turret]

is it possible to use idempotent law on

(~a V b)^(~a V b)

will it just turn into
(~a V b)

[unreal stump]

^ is xor?

[fickle turret]

its and

[unreal stump]

Yea works

[tidal tulip]

Prove by induction that the number of functions from $A$ to $B$ is $|B|^{|A|}$

Can I get a proof check?

Let $A, B$ be finite nonempty sets. Prove that the number of functions from $A$ to $B$ is $|B|^{|A|}$ (hint: use induction on $|A|$).

\Proof by Induction:

\Base Case:

\Suppose $|A|=1$, then by the definition of a function every element in the domain of A has to map to a single element in the codomain of $B$. The number of ways to map a single element of A to elements in B is $|B|^|A|} = |B|^ {|1|} = |B|$. Thus we see that for the base case if $|A|=1$, the number of mappings from $A$ to $B$ is $|B|^ {|A|}$.

\

\Induction Hypothesis:

\

Assume for an arbitrary $k \in \mathbb{N}$, if $|A|=k$, then $|B|^ {|A|}$ = $|B|^ {|k|}$.

\Induction Step:

\Assuming $|A|=k$, you have $|B|^{|k|}$ functions from $A$ to $B$ (induction hypothesis). If you add one element to $A$ then each of the $|B|^ {|k|}$ functions has an additional $|B|$ choices of how to map that element. Thus you have $|B|^ {|k|}$ * $|B|$ possible functions from $A$ to $B$ when $|A|=k+1$.

Thus we see that if $|A|=k+1$ then the number of functions from $A$ to $B$ is $|B|^{|k|}$ * $|B|$ = $|B|^{|k+1|}$

[vital dew]

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

[tidal tulip]

can someone check my proof

[stray reef]

also in the inductive step it is somewhat unclear whether A is supposed to refer to the set with k elements before the addition of a new one or the set with k+1 elements after, and perhaps your teacher might want you to explain why it is always possible to obtain a set of k+1 elements by adding a new element to a set of k elements

but other than that there is nothing to complain about in this proof

[tidal tulip]

excellent feed back, thank you

[wide vine]

is there any real application from the idea of transitive closure

is it just a way to express if 2 nodes/vertex could ever be reached?

such that if you have calculated the transitive closure of a graph then you have all possibly pairings/connections between 2 nodes

actually now that I think about it, it sounds pretty useful to have a matrix/graph that shows all possibly paths between nodes without needing to worry about the exact "walk length"

although I would imagine computationally it could be extensive?

considering you have to multiple the matrix n times for n vertexes?

[wide vine]

what exactly does a partial order or total order mean when it says something is comparable

like if something is "transitive, reflexive, and anti symmetric" it could be a partial order

but even if you can order it, it doesn't exactly mean you can extract anything meaningful from it?

they have an example graph

and while it is a partial order I guess it doesn't really mean much exactly?

I guess it is important when you give context to the stuff in the graph or sets?

[weary tiger]

Why is it

why not 2a_n-2

because it could end with 11?

and 10

do you understand what im getting at

https://www.youtube.com/watch?v=3DIsc2LgU1E

never mind

[weary tiger]

maybe a nonexample would help. If you look at the collection of subsets of the real numbers (or any other set) you can partially order them by set inclusion. But (0,1) is not a subset of (5,6), nor is (0,1) a subset of (5,6). So we'd say (0,1) and (5,6) are not comparable

[wide vine]

yeah I got it but it is just I guess sometimes hard to give meaning to something arbitary

like sure the exam shows how they are comparable and I guess this is how you would define something is maybe "less" then something else

[weary tiger]

what do you mean? 😕

[wide vine]

Like common examples would be numbers and the alphabet, right?

that we say are comparable

[weary tiger]

sure

[wide vine]

but I could have this

and this case it is a total order

but still

in this example square < triangle

like I get it but I think maybe im thinking too deep into any usefulness of when it is said to be "comparable"

but I guess it just gives order to something

maybe im thinking too much about it

but then again it is somewhat by definition that the alphabet and numbers have an order

and I guess I am just so use to comparing them

[severe swan]

How many terms are there in the expansion of (x + y)^98 after like terms are collected? This would be 2 correct? It would be 98x + 98y expanded so 2 terms total.

[viral crown]

what

no

do you know what an exponent is?

[sand smelt]

hello can someone explain me how to solve number 3? it says that the answer is 10 but I get 8 😦

this is how I solved it

can someone point out where I went wrong?

[crude garnet]

how to start with>

[dense glade]

Let A:{x,y,z} and F be commutative. How did they get this graph? I'm so confused, shouldn't f(a,b) =f(b,a)? why are there some blank spaces and some have a value? the question is how many binary operations where f is comutative

[crude garnet]

F be commutative. isn't mean g。f=f。g?

[dense glade]

how did they graph the binary oprtation

[crude garnet]

oh sorry

[gritty crescent]

I'm guessing they want you to count the number of commutative binary operations that meet the constraints of this table (you are free to use any values in the blank spaces so long as f remains commutative). You are correct that you need f(a,b)=f(b,a): does this tell you something about how you can fill up the table?

[fickle turret]

guys can i read
~b ^ (a >b) ^a
as
(~b ^a) > (b ^a)

[muted gate]

never seen this sort of notation before

[rancid fiber]

Can I assumption $\frac{2x}{2^{x}} \leq 1$ automatically for $x > 0$?

[vital dew]

Rezende

[rancid fiber]

Like, that its true for all x > 0

[austere cedar]

no

[rancid fiber]

Oh man, my induction proof in another variable end in this 😂

[austere cedar]

are you talking about every real x or every natural x?

[rancid fiber]

every natural x

[austere cedar]

ah ok, because its false for every real x

[rancid fiber]

I would need another proof?

[austere cedar]

I would write a short proof (by induction on x) just to be safe.

[rancid fiber]

Okay

[austere cedar]

If you think that its pretty trivial, you can also risk it and don't prove it to find out, whether the corrector think the same, such that you know it the next time

[rancid fiber]

I'll ask it today for the corrector

haha

[dense glade]

Why is F: Z+ -> Z+ f(x)=x+1 has no inverse?

[vale cairn]

Is it injective? Is it surjective?

[atomic swan]

Just to be clear, this chat has nothing to do with discrete calculus, right?

I'm just realizing that I already asked that question, I did not get a straight answer but I'll assume nope

[pale epoch]

read the channel topic for what this channel is about

[dire obsidian]

Can someone explain to me what it means by 'recognize all strings in language'?

Is it just related to going to accepting state?

[unreal stump]

Yea

For any string of that form,you go to an accepting state

[dire obsidian]

So recognize == I don't care about output

I only care about going to that accepting state

[unreal stump]

Well,You don't have output here

Yea

[dire obsidian]

So something like this works?

I don't really care about what I set as output?

S_2 is accepting state

[unreal stump]

Are they forcing you to use Finite state automata with output for this?

[dire obsidian]

I think so

[unreal stump]

Ok,Then the definition might be different. For fsa without output,the goal is to get to accepting state

For fsa with output there are no accepting states afaik

[dire obsidian]

That's weird

[unreal stump]

You just output 0 if the new state is supposed to be "non accepting" and 1 if it's "accepting "

[unreal stump]

I think that's 00(0+1)* + 11(0+1)*

Atleast supposed to be

[dire obsidian]

Well the official solution manual i think dictated that there is output and it looks like the state diagram I sent above

[unreal stump]

Show the official solution

[dire obsidian]

From grimaldi textbook

6.3 #3

Since there is no double circle for states I'm pretty sure you assume that S_2 is accepting state

[unreal stump]

Ok,It works ig

[dire obsidian]

So can I change the output to anything I want?

[unreal stump]

No

[dire obsidian]

I know I need to have at least one 0 and 1

[unreal stump]

The output order is important

[dire obsidian]

In what way?

[unreal stump]

If you do the 0 transition on S1 and 1 transition on S2 only in those cases you find the string is in the language

[dire obsidian]

Yeah but what about the loops?

[unreal stump]

You mean the transitions between s1 and S2?

Or the self loops?

[dire obsidian]

Self loops

[unreal stump]

So if you ignore those self loops you get a string like 0101010010

Or 0101011101

Where you have only 1 0 or 1 1 at the end

[dire obsidian]

But only S_2 is accepting state

10 doesnt work?

[unreal stump]

There is no concept of accepting states in fsa with output

That's for fsa without output

[dire obsidian]

Well then what does 'recognize the language' mean in this context?

[unreal stump]

So here's an example of a string being accepted

Say you take 010111

[dire obsidian]

What is the exact goal of 'recognize'?

[unreal stump]

To get an output of 1

[dire obsidian]

Why?

So the prior outputs don't matter?

Very confused

[unreal stump]

Well, That's how fsa with memory are designed. The output bit tells you if the string is accepted or not

If it's 1 the string you have inputed is part of language

If it's 0, it's not in language

[dire obsidian]

So previous outputs literally don't matter?

[unreal stump]

Yea

[dire obsidian]

So self loop with output 1 basically is the same thing as accepting state

[unreal stump]

Well it means accepting on a particular input on that state

[dire obsidian]

Right

[unreal stump]

s_1 doesn't accept on 1

[dire obsidian]

This is kinda scuffed in a sense

[unreal stump]

I know this feels kinda bullshit because for problems on say finding 2's-complement you don't discard the output bits

But here you do

[dire obsidian]

What is 2s complement again?

[unreal stump]

Invert bits add 1

[dire obsidian]

Oh

So binary

[unreal stump]

Actually thinking about it you don't

You print the output bit as soon as it comes and then discard it

[dire obsidian]

Do you have access to grimaldi textbook?

[unreal stump]

No

What's the book called?

[dire obsidian]

What does reflexive and anti-reflexive relations mean?

[dire obsidian]

discrete and combinatorial mathematics 5th edition pdf

[unreal stump]

reflexive is for all a in A aRa is true

[dire obsidian]

What

[unreal stump]

then R is reflexive

So take = for example

[dire obsidian]

Ok

[unreal stump]

2=2 is true

[dire obsidian]

Yes

[unreal stump]

1=1

[dire obsidian]

Yes

[unreal stump]

So for any element a in N , aRa is true where R is =

[dire obsidian]

So reflexive is only =?

[unreal stump]

Well there are other relations which satisfy this

Take aRb iff a=b mod 3

[dire obsidian]

Isnt that also equal sign

[unreal stump]

Not exactly it's equality modulo 3

[dire obsidian]

Hm

So equal sign has to be involved

[unreal stump]

Here's another example

Take aRb iff a<= b

[dire obsidian]

This is kind of weird

[unreal stump]

Well that's the point

aRa is true

[dire obsidian]

aRb

Is weird

[unreal stump]

Oh mb

What's the notation you use

[dire obsidian]

a<=b

[unreal stump]

No for Relations

Do you say aRb or (a,b) \in R

[dire obsidian]

Take aRb iff a<= b

[unreal stump]

Yea?

So if you put b=a you get the condition is still satisfied and you get aRa is true

[dire obsidian]

Yeah it's weird

[dire obsidian]

.

[dire obsidian]

@unreal stump What do
Transistent State
Sink State
Submachines
Strongly Connected Submachines

Mean?

[unreal stump]

Ok,I have no experience with those things sorry

[dire obsidian]

ok thanks anyways

[spring surge]

Number of ways to write n as a sum of k positive integers. What is the short and elegant way?

Just found out there is a whole branch of math talking about this.

[stray reef]

do you consider partitions that differ only by order of terms, such as 2+3 vs. 3+2, to be different or the same?

[spring surge]

same

[stray reef]

then it's going to be painful

[muted gate]

how to prove a set is countable or uncountable? I already know that you can define a one-to-one correspondence between such set and the natural numbers, but is there another way to go about this proof?
also if you could help me with defining a one-to-one correspondence, is there a rule of thumb for that (I'm not that creative lol)?

[pale epoch]

no, there is no other way

countable is defined as bijective with N, so you have to show this some way

how to write down such a map depends a lot on context

might be easy, might be impossible

[burnt oxide]

if xRy iff xy>0 is that relation transitive?

ive trapped myself in a rabbit hole where im conflicted

[pale epoch]

hint: when is xy > 0 based on the sign of x and y?

[loud matrix]

Hi I need help with this

https://discord.com/channels/268882317391429632/423244559682764800

[burnt oxide]

could you elaborate a tiny bit more i'm still a bit lost

[pale epoch]

are you convinced that whether xy > 0 is true only depends on the whether x and y are positive?

[burnt oxide]

also wwhere x and y are negative

[pale epoch]

ye

but the 'magnitude' doesnt matter

(ignoring 0)

anyways

there are 4 possibilities then

x, y both positive
x, y both negative
x positive, y negative
x negative, y positive

when is xy > 0?

[burnt oxide]

only 1st and 2nd case?

[pale epoch]

ye

so they must have same sign

if you now have x, y and z such that xy > 0 and yz > 0, then by the above x and y must have the same sign and y and z must have the same sign

and the question becomes: do x and z also have the same sign?

[burnt oxide]

unless im not accounting for something i beleive yes?

[pale epoch]

i believe so too

[burnt oxide]

therefore on that basis its transitive

?

[pale epoch]

you still have to convince yourself that one of the numbers being 0 doesnt break it

but yes

[burnt oxide]

alright thank you very much

also is there another way to think of fundamental laws of set algebra asides from remembering the laws?

got a test upcoming but its tough remembering all the laws

[pale epoch]

what are fundamental laws of set algebra?

[burnt oxide]

https://www.mathreference.org/index/page/id/313/lg/en

these set of bad boys

[pale epoch]

they follow from the corresponding laws for "and", "or" and "not" in logic

if you think about what the symbols are supposed to mean, most of them are 'obvious'

distributive and de morgan's law need some getting used to

[burnt oxide]

actually yeah you're right its much better looking at it from logic as opposed to just memorising the laws

alright thank you very much for the help

[wicked basin]

idk how to do dis

[stray reef]

Hint: mathematical induction

[wicked basin]

ok

but induction usually has a left hand side and a right hand side

this only gives me half

[true venture]

Just make a left hand side

[wicked basin]

ok

i see that n lines = n(n+1)/2 + 1 regions

but it doesnt look right

[stray reef]

no, that's only when you're proving an identity by induction.

[wicked basin]

ok

i dont see how to apply induction

when n = 0, region = 1

n = 1, region = 2

n = 2, region = 4

n = 3, region = 7

n = 4, region = 11

i dont see a pattern

[stray reef]

when n = 0, region = 1

that's your base case

should be obvious enough

now take an existing arrangement of k lines which divide the plane into k(k+1)/2 + 1 regions and add a new line to them that doesn't pass through any existing intersection points and isn't parallel to any of the existing lines

the new line will intersect each of the k old lines exactly once

continue from there

[cosmic wadi]

What's the contrapositive of p → q ∨ r?

The "V r" is throwing me off. 🤔

I keep wanting to add " ∧ ¬r "

[balmy jay]

You wanna find the contrapositive of p --> (q v r) right

[cosmic wadi]

q v r is in quotations because by default that always comes first, yea?

[balmy jay]

Not sure actually but that's the only way for the contrapositive to make sense in this case

If that's the case, do you know how to do it?

[cosmic wadi]

I'm leaning towards not q or not r then not p

[balmy jay]

Should be not q and not r since the or switches to and when you're negating

[cosmic wadi]

oh, goof

right

thanks

[south yarrow]

I have a question, if numbers in set theory can be expressed as sets can I move from this to prove say addition properties of numbers using just sets ?

I just thought about it and I think its dumb but I just want to ask if it makes sense

[pale epoch]

ye, this is the framework most mathematicians work in

[south yarrow]

well so is there is sth I can read regarding this

I will try to proceed on this on my own too

[pale epoch]

im not 100% sure what you want

you can start with the von neumann construction of the naturals

you define 0 as the the empty set and then $x + 1 \coloneqq x \cup {x}$

[vital dew]

Lochverstärker

[pale epoch]

ye, this is more like it

then addition is defined in terms of this

on the naturals as least

and you can build Z, Q (easy) and R (a bit harder) from this

at the end of the day addition is just a function S^2 -> S for your set S and functions are sets

[south yarrow]

for x ∪ { x } why its not x U { Φ}

I understand 1 = { Φ }

[pale epoch]

technicalities

you can do it differently

[south yarrow]

aight cool thanks ^^

[pale epoch]

well your way doesnt work

you are just adding the empty set

but what you want is x having cardinality x

(in fact you will define cardinality in that way)

and you want $x \leq y \iff x \subseteq y$

[vital dew]

Lochverstärker

[severe swan]

Can someone explain how I can I solve this problem?
If x = log16 y then which of the following is equal to log2 y ?

A) 4x = ln(y) / ln(2)
B) 3x = 3ln(y) / 4ln(2)
C) 1/3x = ln(y) / 12ln(2)
D) 1/4x = ln(y) / 16ln(2)

[weary tiger]

these steps are confusing

Im not sure what is going on

[vale cairn]

Could put it this way.
Define g by g(n) =f(3^n). Since we only care about the calues f(3^n), this reduces to solving g(n) = 2g(n-1) + 4 with g(0)=1

then you just have a more normal recurrence relation

[weary tiger]

thank you

ill solve it

[vale cairn]

I hope that helps?

[weary tiger]

yeah that simplfies it alot

[vale cairn]

Epic

[weary tiger]

❤️

what does a = 2 , b= 3 , c =4 mean

log b^a makes sense

not sure what c =4 means

oh

c^d d = 0

ok makes sense now

😈

is there a easy way to find big-o estimate

for this problem

@vale cairn

[vale cairn]

Well I'd just just use their hint

[weary tiger]

[vale cairn]

Yeah so let g(n)= f(10^n), then g(n) = f(10^n) = 2f(10^(n/2)) +1 = 2g(n/2) + 1

That was my point ig

Then you can get an estimate on g and then f

[weary tiger]

how is 10^m/2

[vale cairn]

Sqrt(10^m) = 10^(m/2)

[weary tiger]

how u get 2g(n/2) +1

@vale cairn

this is too confusing lol

[vale cairn]

Let $g(n) = f(10^n)$. Then if f satisfies the recurrence relation, $g(n) = f(10^n) = 2f(\sqrt{10^n}) + 1 = 2f(10^{n/2}) + 1 = 2g(n/n) + 1$

[vital dew]

potato

[weary tiger]

srry i still just dont generally understand

[weary tiger]

these are the only problems that are tripping me

why

omg

[silver panther]

Change it to $f(3k) = 2f(k)+4$

[vital dew]

Max..

[silver panther]

You might then see this is just $a_{n+1}=2a_n +4$ which we can then solve

[vital dew]

Max..

[sly lava]

hmm if xy>=0 would this relation be transitive? ive seen a question similar to this and want to see how the equality affects said relation.

[hard citrus]

What are your thoughts about it?

[dire obsidian]

Can transitive relations be something like (x,x)

[cerulean wind]

that relation is R = {(x,y) : x = y}

so yes this is transitive

[dire obsidian]

I'm confused because transitive relation definition is
for all real numbers x ,y, and z, if x=y and y=z , then x=z .

idk if I needed that "traversal" part

between different relations

usually transitive relation is something like
{(1,2},(2,3),(1,3)}
idk if
{(1,1)} works as transitive relation

[cerulean wind]

R as above satisfies this condition

[cerulean wind]

{(1,1)} is also transitive

x,y,z are not required to be distinct

[dire obsidian]

Ok then
is this relation transitive, symmetric, but not reflexive?
Set A = {1,2,3,4};
R on $f:A \to A$

$R \in {(1,1)}$

[cerulean wind]

yes

only 1 is related to itself. none of the other elements are related to anything

[dire obsidian]

right so this works

[cerulean wind]

typeset like this: A = \{1,2,3,4\}R = \{(1,1)\}

[vital dew]

Salt

[dire obsidian]

@cerulean wind originally had something like this for transitive, symmetric, not reflexive

so was just wondering

[cerulean wind]

i don’t know why you have f : A —> A

it seems irrelevant

[dire obsidian]

Relation of A to A

[cerulean wind]

then just say R is a relation on A

f is useless here

[dire obsidian]

yeah it jsut makes it more clear for myself

[cerulean wind]

ah

[cerulean wind]

2 is related to 3 and 3 is related to 2 but 2 is not related to 2 so it’s not transitive

[dire obsidian]

oh shoot I need (2,2) for transitive??

[cerulean wind]

yea

[dire obsidian]

I thought it's already on 2?

[cerulean wind]

idk what this means

[cerulean wind]

i just used ur definition of transitive on the relation you gave me and found a counter example

so it’s not a transitive relation

[dire obsidian]

${(1,3), (3,2)} \implies (2,2)$

[vital dew]

Salt

[dire obsidian]

since (3,2) is already on 2

like

"on" 2

[cerulean wind]

(1,3),(3,2) in the relation implies (1,2) is in the relation if the relation is to be transitive

[cerulean wind]

fyi, this notation is extremely vague and non-standard

[dire obsidian]

@cerulean wind also this is the official solution given for this question

[cerulean wind]

this relation is only symmetric

[dire obsidian]

Ok wait I think the online solution thing might be wrong

[cerulean wind]

it is

[dire obsidian]

Actual official textbook solution is
{(1,1),(2,2),(1,2),(2,1)}

[cerulean wind]

or it’s a solution for a different problem

[dire obsidian]

But just {(1,1)} works as well right?

[cerulean wind]

this works if the set has another element other that 1 and 2

[cerulean wind]

if the set has an element other than 1, yes

[dire obsidian]

yeah the set is the same as I defined earlier

[cerulean wind]

okay

then yea

[dire obsidian]

Also are you familiar with finite state automata?

[cerulean wind]

sort of

[dire obsidian]

I'm kind of confused about a few definitions

like
Sink State
Transistent State
Submachines
Strongly Connected Submachines

[cerulean wind]

never heard of these definitions, sry

[dire obsidian]

Dead state?

[sly lava]

im not certain but the relation is not transitive? because factoring in the case where is x>=0 y>=0 and Z>=0 then you would get a case where it just wouldnt relate

Can't exactly picture the case though

[hard citrus]

If you look at it with all 3 of them >=0 you won't find a counterexample. Take one of those to be <0

[cerulean wind]

try combinations on the x-axis and the y-axis.

[sly lava]

not exactly sure how to do that

[cerulean wind]

look at things of the form (x,0) and (0,y)

[sly lava]

sorry a bit lost for that method

[sly lava]

Could i do x=1 y=0 z=-1 where xy and yz =0 but xz !=0 so not trans?

[hard citrus]

Exactly

xy>=0 and yz>=0 but xz<0 --> not transitive

[sly lava]

ahh alright thank you!

[sly lava]

Im still interest how you would prove it like this though?

Interested*

[cerulean wind]

u just did it

[sly lava]

oh

[cerulean wind]

i’m not sure why u had a more positive response to .nai vs me haha. we were saying the same thing lol

[sly lava]

sorry haha i havent gotten up to combinations so i was just focused on that and was lost

[cerulean wind]

i meant combinations in the non-technical sense

just like

try some configurations out

[hard citrus]

trial and error

[sly lava]

OHH i thought you were referring to the other combos mb sorry!

[cerulean wind]

choose a four element subset. how many permutations leave none of the remaining 5 elements fixed?

yes, it’s c

[stray reef]

have you heard of the inclusion-exclusion principle

why time pressure

are you in a test right now

getting help on graded, timed assessments is against the rules here.

[spring surge]

Consider a simple lottery with N tickets and P prizes (of course, P ≤ N). A person buys T tickets (T ≤ N).
How many chances does he have to win exactly K prizes (K ≤ P)?

[unreal stump]

Did you find this from Skiena

[spring surge]

No its from USSR math themed website

unizor.com

[unreal stump]

There is no formula for this

I guess a recurrence might exist

[unreal stump]

mb different question

This one must be easier

[spring surge]

Yeah I just sit and draw little squares and have faith i'll find something

[stray reef]

are you sure theres no formula

cause this looks like hypergeometric distribution to me

you pick K winners out of P prizes and T-K winners out of N-P prizes

so $\frac{\binom{K}{P} \binom{T-K}{N-P}}{\binom{N}{T}}$ is the probability

[vital dew]

Ann

[stray reef]

and it looks like theyre looking for just the numerator

[spring surge]

thanks. hypergeometric distribution - that sounds clever.

[stray reef]

dont pay it much mind

[spring surge]

googling it already ha

[burnt oxide]

how do you prove something is reflexive?

[unreal stump]

Sorry I thought this was a different problem

[coral parcel]

In the vast majority of cases by applying the definition of "reflexive" directly to the definition of "something" and getting a result that is obviously true.

[burnt oxide]

alright that clarifies things tyty

[mint salmon]

T = {E, B, S, δ, s0, F}
E = {a, b}
B = {a, b, *}
S = {s0, s1}
δ = {
  δ: (s0, a) -> (s0, b, R)
  δ: (s0, b) -> (s0, a, R)
  δ: (s0, *) -> (s1, *, N)
}
s0 = s0
F = {s1}

this is intended to be a turing machine and before I start fiddling around with trying to emulate it, I was wondering if I'm even on the right track

it's supposed to move from left to right on the tape and swap a for b and vice versa; the machine stops when it reaches an empty cell, here denoted with *

it seems like it's too straightforward to mess up, but I'm not entirely sure that I haven't misunderstood something

[dense glade]

Hi guys I have been stuck on this question for a bit because I'm getting all the wrong numbers except for a) I get it's 5^24

but for example b) if were to remove the x horizontal and vertical comlumn we would be left with 5^12 but the answer is wrong

c) the answer says a nor bad can have an identity which I'm not sure why

[spring surge]

How many ways are there to divide 2·N different objects into N pairs?

[spring surge]

(2N!)/(2^N)

[narrow trench]

Are the pairs ordered or unordered?

[spring surge]

unordered

[weary tiger]

[weary tiger]

This is also what I did on the side but I am not sure if it’s right or wrong

<@&286206848099549185>

[weary tiger]

Nvm I got it.

[dense glade]

prove that if 6 integers are selected from {3,4,5,...,12} there must be 2 integers whose sum is 15, why is that?

[quiet parcel]

well... you can see it's true if you take the smallest 6, (3,4,5,6,7,8)

or the largest 6, (7,8,9,10,11,12)

because 7+8 = 15

then... something something...

there are only (10 6) = 210 possibilities to enumerate and verify :)

[meager prairie]

write them as pairs which exclude each other

then use pigeonhole

[quiet parcel]

oh that's nice

[violet flower]

I have to find the power set of this and I have no idea how

[stray reef]

"the power set of this"?

what

[violet flower]

maybe i used the wrong word

[stray reef]

can you post the question exactly as stated?

as-is all you're given here is a function

[violet flower]

my bad it says

Determine the powers of f

thats legit the question

[stray reef]

right.

so what you're asked for is to determine f^2, f^3, f^4, etc.

ie what happens when you compose f with itself

[violet flower]

Yes

[stray reef]

and i take it you've made no progress on that front?

[violet flower]

correct

[stray reef]

you know what max and min refer to, yes?

[violet flower]

yes

[stray reef]

okay

so the output of f depends primarily on whether or not x ≥ y

specifically, $f(x,y) = \begin{cases} (x,y) & x \geq y \ (y,x) & \text{otherwise} \end{cases}$

[vital dew]

Ann

[violet flower]

Ok

so like where do I go from here

[stray reef]

think about it

f takes a pair of numbers as input

what does it do?

[violet flower]

it spits back out the x y if x is bigger otherwise it switches the x y numbers

[stray reef]

yes

...you really should not omit the parentheses and comma though

but yes. if the first number is bigger, it returns the same pair as output. otherwise it swaps the numbers.

what happens when you apply this map twice?

[violet flower]

If you would apply this twice you would have 2 sets of points.
Like f^2 would be the equation twice so would we need to narrow that down more or am I heading in the wrong direction

[stray reef]

you are heading in the wrong direction

[violet flower]

freak

[stray reef]

you have this procedure "if the first number is bigger, do nothing; otherwise swap the numbers"

what happens when you do this and then do the same thing again

[violet flower]

you are back at the same numbers

You either remain the same or the numbers switch and then would remain the same

[stray reef]

bad phrasing

doing it twice is the same thing as doing it just once.

[violet flower]

yeah

so the power of f would just be itself

[stray reef]

phrasing...

[violet flower]

so the power of f(x,y) is just f(x,y)

because no matter how many times repeat the steps it will be the same 2 points

[timber python]

I am not sure how to show that the properties are preserved invariants

I assume the first part of a has to do with

[vernal cypress]

This is wrong right? my teacher wrote it but I thought the answer would be it's raining so Iam happy

converse

[hard citrus]

Your proposition is:

If p, then q
The converse is:
If q, then p

Exactly which one are you saying is wrong?

The way the proposition is rewritten using If..., then... or the converse of the proposition

[vernal cypress]

the one in the image of course

is wrong, right?

and the one I sent as a message her is right

no ?

[hard citrus]

The image is right

The converse is: If I'm happy, then it's raining.

[vernal cypress]

how? isn't p the first thing ?

which is I'm happy?

[hard citrus]

The first "thing" after "If" or "whenever"

Not the start of the proposition

So:

p: it's raining

[violet flower]

idk what to do for this quesiton

[coral parcel]

Try to see if there's an easy proof. If there isn't, try to see if it is easy to construct a counterexample. If you fail at constructing a counterexample, see if the way you fail can inspire a proof. Otherwise repeat the whole program with more effort spent at each step until one of the directions yields.

[floral field]

I'm trying to prove that in a simple graph, if there is a walk from vertex u to vertex v, then there is a path from vertex u to vertex v. Intuitively, it makes sense, since there are no repeated edges in a simple graph, but I'm not quite sure how to rigorously state the reasoning in my proof

[coral parcel]

If the walk has no repeated vertices, then you're done. Otherwise, cut away the part of the walk between two repeats of some vertex and proceed by (strong) induction on the length of the walk.

I'm not sure how the graph being simple is relevant for this, though.

[floral field]

Is it possible to argue this without induction?

[floral field]

I'm assuming that having loops and repeated edges pose problems?

[coral parcel]

Since walks and paths are lists of things, almost anything interesting we can say about them will ultimately (but perhaps indirectly) be a matter of induction.

I don't really see any problem from either loops or parallel edges. Unless you're working with a formalism where "path" and/or "walk" are only defined for simple graphs in the first place.

[floral field]

We’re just defining “path” as a walk with no repeated vertices

[stray reef]

i guess like

you could define an algorithm for walk-ifying a path

[floral field]

I think the nature of the proofs I’ve seen in lecture were of this form

[floral field]

But I’m just not sure how to rigorize it for this

[stray reef]

something that, in very loose pseudocode, would look like this:

def pathify(walk w):
    let visited_vertices = []
    let i = 0
    let n = len(w) # n = index of last vertex, so w actually has n+1 vertices but whatever
    visited_vertices.append(w[0]) # 0th vertex of w, a.k.a. beginning; w is considered as an array of vertices
    while w[i] ∉ visited_vertices:
        visited_vertices.append(w[i])
        i += 1
    if i == n+1:
        return w # while-loop found no repetitions => p must not have any to begin with, so is already a walk
    # otherwise vertex w[i] is among the list of visited vertices already. let's find where it is
    let j = find(w[i], visited_vertices) # assume find() does a lazy search, i.e. halts as soon as it finds a match as opposed to finding and returning all matches
    let w1 = w[0:j, i+1:n]
    return pathify(w1)

something along these lines

er

hold on

exit condition

basically the idea is to recursively find the first time a vertex is repeated in your path and cut out the loop between the old and the new occurrence thereof

thereby eliminating one repetition

in doing so the length of the path always goes down by at least 1

[coral parcel]

Surely you mean pathifying a walk.

[stray reef]

do i

surely i am confused as to which of these two incredibly similar terms to the point of near-synonymity in quotidian usage is used for something that allows repetition of vertices and which one does not

...yes

yes i do mean pathifying a walk oops

[coral parcel]

It's a "walk" that can have repeated vertices. (I need to look it up every time).

[floral field]

Wait, a path can’t have repeated vertices right?

[coral parcel]

Correct, that's what distinguishes it from a walk.

[stray reef]

you know there exists a walk and want to show there exists a path, that's what my algorithm does

[coral parcel]

BTW, the induction proof I alluded to is basically this, with just differences of style.

[floral field]

Thank you!

[remote light]

I want to solve for the x_j's.

The question is motivated by looking at the number (y_m) of closed walks in a graph of length m. And relating that to the eigenvalues (x_j) of the adjacency matrix

[unreal stump]

@remote light d has to be atmost n

[coral parcel]

On the other hand d has to be at least n too; otherwise you have more unknowns than equations.

[unreal stump]

With n equations,you can reduce this to finding roots of a polynomial

[remote light]

yes exactly it has to be at least n

[remote light]

I don't think this holds as the equations could be in some way degenerate

[coral parcel]

Well, but only if one of the y_n's is zero.

[remote light]

they are very often zero

[coral parcel]

Ah.

[unreal stump]

Suppose you have

x+y = c
x^2+y^2=z

You can reduce this to a quadratic equation such that x and y are roots

With (x+y)^2-(x^2+y^2)=2xy

[coral parcel]

If any y_{2m} is zero, then all of your x_i need to be zero too.

[unreal stump]

Similarly for 3 equations you get a cubic

[remote light]

y_{2n} is never zero

y_m = number of closed walks of length m

in a given graph

(for intuition)

[remote light]

mh not sure if this helps me

[unreal stump]

If you have a cubic,you can find the roots

[coral parcel]

Hmmm, the thing is symmetric, so you can only get the x_i's up to permutations.

[unreal stump]

And if all roots are real you have a solution

[remote light]

yep

my next thought was that we can bound d by 2n as then we can get a system of equations for x_j^2

and the nice thing for x_j^2 is that they must be positive

so solving that seems way easier

[dire obsidian]

Is there a specific trick to solving pigeonhole problems?

[coral parcel]

Umm, "pigeonhole problem" pretty well means "a problem where the trick is to use the pigeonhole principle".

[vernal cypress]

can someone help me with this one?

I tried but i don't think it's correct

[dire obsidian]

yeah but most of the difficulty of these problems come in terms of recognizing that you need to use pigeonhole and how you apply it
I think I meant like tricks in terms of this ^

[coral parcel]

That assumes that the gold winner can also go on to win silver and/or bronze, which doesn't sound like it's the intention.

[vernal cypress]

so what would be the correct answer?

[coral parcel]

Well, there's 21 people who can win the gold medal all right. Once you know the gold winner, how many ways are there to distribute the silver and three bronze among the remaining 20 contestants?

[dire obsidian]

wait why is this sum rule

[dire obsidian]

Wait you can assume that the order of distribution is gold->silver->bronze right?

If so, why is this permutation and not choose?

[coral parcel]

You can assume any order, and the results had better be the same.

[dire obsidian]

wait so you use choose? It doesn't matter what order for example the bronze medal is awarded in

[coral parcel]

Yeah, the end result is something called a "multinomial coefficient" $\binom{21}{1,1,3,16}$, but if you haven't already learned about that, it's probably not helpful to shoehorn the concept in.

[vital dew]

Troposphere

[dire obsidian]

why not

21C1 * 20C1 * 19C3 ?

[coral parcel]

That's what it is!

[dire obsidian]

dam I need to brush up on multinomial

[dire obsidian]

Will this still work if we do not know the order the medals are distributed in?

I'm worried about something like 18C1
(if bronze gets chosen first)

[coral parcel]

Yes. You can either write $\binom{21}{1}\binom{20}{1}\binom{19}{3}$ or $\binom{21}{3}\binom{18}{1}\binom{17}{1}$. If you then expand each of the binomial coefficients with $\binom{n}{k} = \frac{n!}{k!(n-k)!}$, you'll find that several of the factorials cancel out when you multiply them together and what is left is just $\frac{21!}{1!\cdot 1!\cdot 3!\cdot 16!}$ in both cases.

[vital dew]

Troposphere

[coral parcel]

(and that is neither more not less than what a "multinomial coefficient" is).

[dire obsidian]

I see. Is the multinomial theorem also technically derived in this way?

[coral parcel]

Yes.

[vernal cypress]

So what's the best way to solve it ?

[coral parcel]

Either of them will work.

[dire obsidian]

you first need to recognize whether to use sum rule or product rule tho

you're currently using sum rule (which is incorrect)

[coral parcel]

(Sorry, I hadn't noticed I wasn't talking to the person with the problem 😅)

[dire obsidian]

XD thanks for clearing things up anyways

[coral parcel]

Oh right, I hadn't even noticed that Youz was adding instead of multiplying.

[dire obsidian]

When you think about whether to use sum or product rule,

Think:
If I give someone the gold medal, does that mean I will no longer give anyone bronze and silver?
(If so, sum rule)

If I give someone the gold medal, will I give someone the silver or bronze medal right after?
(If so, product rule)

[vernal cypress]

THANK YOU

[vernal cypress]

should it be like this?

[dire obsidian]

many issues

1. Why permutation
2. Why 21 does not change after every session?
3. Why (a+b)*c?

Does it really matter what order you give the bronze medal in? (Note this is NOT medal TYPE distribution order)

After you give someone a gold medal, can they receive another medal? (Obviously the answer is no)

ex order: gold->silver->bronze
What is supposed to happen is:
After you give someone gold medal, you give someone silver medal, after you give someone silver medal, you give someone bronze medal.

your answer right now says "(I give gold [exclusive or] silver medal), then I give bronze medal"

[severe swan]

I am trying to expand (2x-y)^50 with binomial expanison. I want to find the coefficient of the term x^20y^30. This is what I did. Am I using the correct formula? Is there a different formula I should use to solve this?

https://imgur.com/a/eUtPdq4

[coral parcel]

The binomial formula is right, but something is off in the second line in your image. It has x and y appearing on the left-hand side, but not to the right. That can't be correct.

[dire obsidian]

what is your way of understanding binomial theorem?
I can't seem to wrap my head around it in a discrete math context

[coral parcel]

Hmm, I'm not sure I understand that question.

[dire obsidian]

binomial expansion

^ example

[coral parcel]

The binomial theorem tells us in general what happens when we expand (a+b)^n completely using distributivity until only a sum of products of a and b is left, and then collect like terms.

That's really just a packaging-up of a formal computation using the axioms for a commutative ring; it doesn't inherently depend on whether the ring we then apply it to is continuous or discrete.

[severe swan]

thanks

[dire obsidian]

is there a visual representation of this?

Is there any youtube videos you recommend watching to get a better grasp of binomial theorem/expansion?

[dense glade]

How does that show

that its 1r+

or 1r

[coral parcel]

Hmm, I don't know about any visual representation that I'd feel helpful. And I don't really know about math videos in general.

[coral parcel]

In one sense (b) is true because that is the definition of f^{-1}. I think what the exercise really wants is for you to show that the expression for f^{-1} you will have found in part (a) actually works.

[dense glade]

yeah

i see

[dense glade]

is there a way to figure out if a function

has an identity or not

like a trick or something

[coral parcel]

Do you mean "has an inverse"?

A function has an inverse if and only if it is bijective.

It may or may not be possible to write down the inverse function as an algebraic formula, though.

I don't think there is a foolproof systematic way to determine the latter.

[dense glade]

no no like identity as in f(a,b)=f(b,a)=a

[coral parcel]

Ah, I see.

I can't think of any particularly general way to determine that, either.

[dense glade]

umm I see

[coral parcel]

In other words, what I'd do would depend a lot on which kind of definition and already known properties I had for f.

[dire obsidian]

Do I just expand binomial theorem and multinomial theorem to understand them? Or is there something else involved?

[coral parcel]

Yeah, that would be my suggestion: try the expansion of (a+b)^n on paper (without the binomial theorem, just the distributive law etc) for some small n and observe how what is left after the dust settles is exactly what the binomial theorem promised it would be.

n=3 should be doable; n=4 will start to get tedious.

(whereas n=2 is just the well known (a+b)² = a² + 2ab + b²)

It can help understanding to try to do it while you pretend multiplication is not commutative until you have multiplied out completely and you start collecting like terms.

On the other hand, if you then try to do it another time but attempt to be smarter about expanding out so you compute (a+b)^n by first expanding and simplifying (a+b)^{n-1} and then multiplying the result by (a+b), you will see the recursive formula for the binomial coefficients arise in your computations!

[dense glade]

How is y=x^3 surjective on R -> R

[dire obsidian]

Ill try that

[dense glade]

if the codomain is all real numbers

then for example what is 2 mapped to

there is no value that can be plugged into x^3 to get y=2 right?

[coral parcel]

Sure there is: the cube root of 2!

Which is about 1.259921

[dense glade]

I see

so when I try to prove a function is surjective

i need to solve for x and see if x is defined

for all values?

I guess thats the idea?

[coral parcel]

You don't necessarily need to actually solve for x -- often you can get away with doing just enough work to be sure there's a solution somewhere, without actually finding it.

For x^3, a typical argument would be:

1. Prove the function is continuous.
2. Prove that for every y, the function has a value somewhere that is larger than y.
3. Prove that for every y, the function has a value somewhere that is smaller than y.
4. Apply the intermediate value theorem to conclude that there exists some x with x^3=y.

[dense glade]

alright I will follow that

thanks a lot

[dire obsidian]

Kind of confused why n=1 works for binomial

wouldn't b^0 = 1?

[obtuse lance]

yeah, so what

[dire obsidian]

I thought (a+b)^1 = a+b ?

[obtuse lance]

write out the whole formula for n=1

write out the whole formula for n=1

plug in for each of the terms

show what you get

[coral parcel]

Remember that the sum in the binomial theorem for n=1 has two terms: One with i=0 and another one with i=1.

[dire obsidian]

dam that's wack

[obtuse lance]

nice job

[floral field]

How would I argue that a simple graph, where every vertex has degree k, has a cycle of length at least k+1?

I have no clue where to start.

[dire obsidian]

what's the reasoning behind the "choose" part of binomial theorem?

[obtuse lance]

I see it as coming from when you multiply, if you don't change the order of the terms, for instance

(a+b)(a+b)=aa+ab+ba+bb

before you put exponents on them and join terms by commutativity, you're litterally counting numbers of strings of length 2

[dire obsidian]

can you elaborate?

[obtuse lance]

similarly (a+b)(a+b)(a+b) = aaa+aab+aba+baa+abb+bab+bba+bbb

aab, aba, and baa all are equal to a^2 b, there are 3 choose 1 ways of arranging them

[dire obsidian]

that's kind of interesting

and a bit weird at the same time

[coral parcel]

Start somewhere in the graph, keep following edges at random, except avoid edges that lead to a vertex you haven't already been to.

(Hmm, this might not actually work. But somehing like that probably will).

[dire obsidian]

can I also expand this idea into multinomial theorem?

multinomial is far more confusing for me to understand

[obtuse lance]

yeah it is the same idea just more letters in your strings

(a+b+c+d)^13 the coefficient on a^i b^j c^k d^l will be 13!/(i! j! k! l!) (with i+j+k+l=13 of course)

[dire obsidian]

yeah I'm completely confused about multinomial

[obtuse lance]

you can think of it like each term (a+b+c+d) as giving you one letter to pick from to make the word, and doing this 13 times

[dire obsidian]

This is kind of hard for me to visualize

[obtuse lance]

ah I learned a proof of a similar thing the other day, the main trick for it (in my opinion) is if you start with the longest path, then you know that the end vertex of the path has all its neighbors in the path itself

so to look at any term of say, (a+b+c)^2 I can write it as (a+b+c)(a+b+c) and now I think from the first trinomial (a+b+c) I distribute one of the letters to the right, which will then end up on another choice of letter from (a+b+c)

and all terms are created this way, I'm really trying to think backwards here in terms of

if I wanted to know what the coefficient on ba was I could think of where it came from

(. + b + .)(a + . + .) and (a + . + .)(. + b + .) would be the two terms

[dire obsidian]

can I bother you to draw a diagram/equation?

[obtuse lance]

trying to hide the other terms to highlight what contribute to it

[dire obsidian]

discord text is kind of

[obtuse lance]

maybe later I just woke up and feeling lazy sorry haha

[dire obsidian]

alright I'll wait 👍

[obtuse lance]

the proof actually doesn't require the graph to be regular, you can loosen it to having minimum degree k

just figured I'd say that since I'm guessing your thumbs up and heart meant you proved it haha

[coral parcel]

The graph does need to be finite though -- not everyone considers that implicit in calling it "simple".

[obtuse lance]

true, I only assumed it was finite because if it were infinite the theorem would be false since an infinite tree of degree k contains no cycles

[floral field]

Yeah, so basically take a maximal path of length l. And basically, the fact that it's regular implies the neighbors of each vertex in the path are all in the path?

[coral parcel]

Not necessarily.

But all you need is that for the end of the maximal path in particular, all of its k neighbors are already in the path.

Connect it to the one that is farthest away from the end, and discard the beginning of your maximal path up to that point.

[dry raven]

Suppose a satellite transmission protocol was designed to run at 4 Mbps using 2000 Byte packets size. With the same window size, if we want to transmit at a rate of 40 Mbps and achieve the same utilization (efficiency), what packet size should be used? (Note: be careful with the units.) anyone able to help with this?

[coral parcel]

That doesn't really look like a mathematics problem.

[dry raven]

idk its a problem in my networking algorithm class which is directly after discrete so thought Id ask here

[coral parcel]

It's a question of knowing what "window size", "utilization", "packet size", etc mean in the communication context, and how they interact. The actual computation is likely to be trivial once you use domain knowledge to figure out which computation you need to do.

[vernal cypress]

Hi, can someone suggest me a video explaining the topic surrounding this equation?

I keep not understanding it

[dire obsidian]

Hi do you have time now?