discrete-math

[rugged heath]

like in this random problem, the smallest case to check would be P(8), so that would be your base case

[primal glade]

yep, tysm. and is it possible to have 5edges for a face?

[stray reef]

sure why not

[buoyant sluice]

anyone here done optimization ?

[ivory swift]

What do the evaluations of the sum of consecutive natural numbers n(n+1) / 2 mean when n < 0?

[ivory swift]

I assume the expression is only true for n >= 0

[lone bridge]

for n<0, the formula gives sum of first |n|-1 natural numbers

[eager turtle]

does this make sense? i'm reading it right now as "i pass the exam if and only if i either do not attend class or do not do the homework" which doesnt seem right to me

since that means you cant pass if you show up and do the homework

but if you do neither you do pass

[coral parcel]

It's a correct rendering of the symbolic statement. The exercise doesn't claim that statement is true.

[eager turtle]

hm okay

thanks

[coral parcel]

(However it would be true about, for example, a student who showed up to class and did the homework but eventually failed -- which is definitely a thing that even happens in the real world).

[sudden flicker]

any good source to learn group theory and graph theory?

[lavish valve]

https://tenor.com/view/rio-ngumoha-rio-ngumoha-liverpool-lfc-gif-2402930566872399577

[random sparrow]

help

[cerulean wind]

which ones are you stuck on?

and which parts?

@random sparrow

[random sparrow]

don't know how to start

[cerulean wind]

you need to figure out which functions are injective, surjective, or bijective (both injective and surjective)

do you remember what it means for a function to be injective, surjective, and bijective?

[random sparrow]

no

can i have a quick summary

@cerulean wind

[cerulean wind]

Let f : X -> Y be a function

Injectivity: f is said to be injective if ∀ x,y ∈ X . f(x) = f(y) ⟹ x = y
Surjectivity: f is said to be surjective if ∀ y ∈ Y . ∃ x ∈ X . y = f(x)
Bijectivity: f is said to be bijective if f is both injective and surjective

does this make sense?

[random sparrow]

yes but I can't recall them from the top of my head

[random sparrow]

for example for i) f(-1) and f(1) is an example that it doesnt satisfy injectivity

[neon harbor]

Tbh, if your book doesn't give you the definition of injective, surjective and bijective, you need to find a different book. It seems like every time you ask for help here, the first thing you need help with is just finding the definitions

[random sparrow]

for surjectivity, say for example y = x^2, then it's impossible having y = -1 if y is in R

[random sparrow]

it includes it

what didnt included was quotient set, or was between lines

[neon harbor]

Okay, then why do you need other people to give you the definition?

[random sparrow]

same with representative of a equivalence class, but it gave examples

[neon harbor]

It just seems like you're doing 0 amount of work on your own before coming here

[random sparrow]

if I knew all the definitions from the top of my head I wouldn't even be an undergraduate

[neon harbor]

You don't have to know the definitions by memory, you just have to look them up

[random sparrow]

whats the issue with receiving a bit of guidance?

it's my first week in university

[neon harbor]

There's no issue, but when every single question you ask starts with you not knowing the definitions, you need to ask yourself if what you're doing is actually productive

[coral parcel]

The first "bit of guidance" is to start by looking up the definitions of any concept in the problem you don't remember the definition of. You don't need to wait for someone here to tell you that; it's always the first step.

[random sparrow]

the issue is not about the definition but how to look for counterexamples of subjectivity, like completing the exercise

[fossil mural]

well the first step in looking for counterexamples to surjectivity is to know what surjectivity is, which is why you should check the definition

[coral parcel]

Also note that the very purpose of this exercise is to give you an occasion to think enough about the definitions that you can remember how they work later. To search for a way to solve it without having the definitions at the front of your mind would defeat the entire reason for doing the exercise in the first place.

[random sparrow]

even after csquares gave the definition I was still troubled finding the counterexample of subjectivity, though I agree having the definition at hand is useful if you don't know it from the top of your head

but even after knowing the definition of surjectivity and having at my disposal. i can't figure out counterexample of subjectivity for i)

[coral parcel]

(They seem to have missed a factor of 3 in (iv) )

[coral parcel]

Have you sketched the graph of the function?

[random sparrow]

isnt that kind of cheating

[coral parcel]

Why would it be? Cheating how?

[random sparrow]

well, what is it. a parabola?

[coral parcel]

The reason they harp on about sketching functions in high school is that it's a useful skill to have at higher levels when you see an arithmetic expression like 12x²-5 and need to be able to understand intuitively what it does.

[coral parcel]

Quadratic functions have graphs that are parabolas, yes.

[random sparrow]

how does the 12 affect the x^2, you understand what I mean?

well we don't really care, we just know it's above 5 in y axis

like the vertex

the lowest point is y = 5

[neon harbor]

You can just graph it in desmos, and play around with the coefficient of x^2, so you can see for yourself what effect it has

[coral parcel]

Does that help you find out whether it's surjective?

[random sparrow]

what was surjectivity again, every element in the codomain has a x in the domain that is mapped to

mmmm

[coral parcel]

... and then we're back to step "look up the definitions".

[random sparrow]

there is no y = 4

so its false

it's not surjective

and 4 is in R

now I need to find the image?

the image is a subset of the codomain, right?

[coral parcel]

There ought to be a definition of "image" you can look up too.

[random sparrow]

well, in calculus class you calculate the range finding the horizontal asymptote, oblique and vertical asymptotes and finding first and second derivatives

[random sparrow]

ok one sec

[coral parcel]

It might not differ from what you know as "range".

[random sparrow]

is very similar to the definition of preimage

no?

[neon harbor]

Are you sure? What is f(sqrt(9/12))?

[random sparrow]

well idk what he wants me to find, like all the possible y of f(x) = y

[robust monolith]

Where do you get this text from?

[random sparrow]

,w 12x^2 - 5 , where x = sqrt(9/12)

[vital dew]

Results provided by WolframAlpha

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

Requested by renatoxbz

[random sparrow]

it's from my algebra class

[random sparrow]

my bad, lowest point in y axis is -5

so f(x) = -6 is unreached

[neon harbor]

Yep 👍 can you prove it?

[random sparrow]

yes

f(x) = x^2 - 5
let y = -6
-6 = x^2 - 5
-6 + 5 = x^2
-1 = x^2
which means x is
x = +- sqrt(-1)
and so, x is not in R

guys how to find the image of i)

oh, so in case the function is surjective, then the image is all the codomain or no?

[coral parcel]

... you've just shown that -6 is not in the image.

[random sparrow]

right

if a function is surjective then the image is a proper subset of the codomain

[coral parcel]

No.

[random sparrow]

can you explain

[random sparrow]

I think the image is y >=-5

no?

[coral parcel]

You have the right idea, but that's not the way to write a set.

You can say "the image is { y in R | y >= -5 }".

[random sparrow]

[coral parcel]

Or you can say "the image is [-5,infinity)".

[random sparrow]

this

I appreciate the help fellas

[random sparrow]

can I get some help with ii)

[brave rock]

What have you tried so far?

[random sparrow]

x in R2
x = (1,2)
f(x) = 3
x' in R2
x' = (2,1)
f(x') = 3
f(x) = f(x') but x not x'

[brave rock]

OK... so what does that tell you

[random sparrow]

not injective

[brave rock]

So now you only have to check surjectivity, so you should try doing that now

[random sparrow]

idk if, ii) is surjective or not

I would say yes, because from a sum of x and y where x is in R and y is in R, we can form every element in R

but dunno how would you prove that

[coral parcel]

Explain how, given a real number, you can always find an input to the function that makes it produce the given output.

[random sparrow]

lets say I have an x1,x2,y in R
we have f(x1,x2) = x1 + x2
where y = x1 + x2
we can always get y = y + 0
for x1 = y and x2 = 0

[brave rock]

well then you have your answer

[random sparrow]

guys in iii) how to prove is surjective?

I need to show it works for an arbitrary element in the codomain

f : R3 -> R2
f(x1,x2,x3) = (x1+x2, 2x3)
x1,x2,x3,x,y ∈ R
let (x,y) = f(x1,x2,x3)
then (x,y) = (x1+x2, 2x3)
where x = x1, x2 = 0, y = 2x3
then (x1,x2,x3) = (x,0,y/2)
thus f(x,0,y/2) = (x + 0, 2(y/2))
thus f(x,0,y/2) = (x,y)

dammit

I got confused mid proof

my point is that, if you set x1 = x, x2 = 0 and x3 = y/2 you can get to any (x,y) in R2, where x1,x2,x3,x,y are real numbers

[grand crown]

yes exactly, just show that for any x and y, f(x, 0, y/2) = (x, y)

you basically did that

[scenic mesa]

it should be enough to state that. there's nothing left to show.

well if you want to put more detail, you can add this one intermediate step:
for all (x, y) in R^2, f(x, 0, y/2) = (x+0, 2(y/2)) = (x, y)

[random sparrow]

hardstuck on vi

how to prove its injective

[quick folio]

think about even/odd

[random sparrow]

bottom is odd top is even

whats your point?

[brave rock]

Try out some values and see what you get

[random sparrow]

is injective

i tried a bunch of crap

[brave rock]

OK how do you know?

[random sparrow]

is injective im 99 percent sure

[brave rock]

Why?

[random sparrow]

i need to prove it

[brave rock]

Why are you sure it's injective? What things did you try?

[sudden dawn]

inyectiva

[random sparrow]

because if you plug in a negative number you get that the number is odd

if you plug a positive number you get a even number

[sudden dawn]

ponle valores

[brave rock]

So why does that mean it's injective

[random sparrow]

if the output of one of the cases of the piecewise gives odds and one gives even

then they never overlap, dunno how to explain

[brave rock]

So your proof should probably split across those lines

[random sparrow]

is impossible to find a counterexample is what I am saying

[brave rock]

Yes, that's indeed what it means for something to be true.

Your proof should go something like:
"suppose that one of x_1 and x_2 is even and the other is odd..." see below

And then show that this case is impossible.

Or wait sorry, this is backwards

[sudden dawn]

demuestra si es creciente o decreciente

[brave rock]

"suppose that one of x_1 and x_2 is positive and the other is negative..."

[sudden dawn]

toda inyectiva es monotona

[brave rock]

OK, you go ahead then.

[random sparrow]

fair point, but this is a piecewise I would need to take the derivative using the definition. limits and will get nasty and this exercise is not part of an anal course, is algebra

[brave rock]

The definition of a monotone function does not require calculus, but this is besides the point.

[random sparrow]

i know that you mean f'(x) > 0 or f'(x) <0 , ∀x ∈ Dom(f) implies is monotonically increasing or decreasing and thus is injective

[brave rock]

The actual definition of a monotone function is x < y implies f(x) < f(y).

[neon harbor]

You don't really need to think about monotone functions here, you can just use the definition of injectivity: assume f(x) = f(y) for x, y in Z, then prove that x = y. Just split it into 4 cases, depending on whether x and y are positive or negative, as Boytjie suggested

[random sparrow]

can you give an example shedow?

[scenic mesa]

|| a>0 implies f(a) even () ||
|| a<=0 implies f(a) odd () ||
|| assume f(a) = f(b)||
|| Case 1: If f(a) and f(b) are even, || || then a>0 and b>0 by (), || || so f(a) = 2a and f(b) = 2b. || || Then 2a = 2b, so a = b. ||
|| Case 2: otherwise, f(a) and f(b) are odd, || || so a<=0 and b<=0 by (). || || Then f(a) = 1-2a and f(b) = 1-2b, || || so 1-2a = 1-2b, and so a=b. ||

here's a proof

[random sparrow]

how did you came up with this
?

seems complicated

[random sparrow]

can i get help

[random sparrow]

take a > 0, then f(a) = 2a, take b > 0, then f(b) = 2b, assume f(a) = f(b), then it follows 2a = 2b, we conclude a = b, you can do similarly the other direction

[neon harbor]

Yeah, that works 👍 what happens when you assume f(a) = f(b) and a > 0 but b < 0?

[random sparrow]

we get an absurd

assume f(a)=f(b), a >0, b < 0 then it follows
a > 0 => f(a) = 2a
b < 0 => f(b) = 1 - 2b
assume f(a) = f(b)
2a = 1 - 2b
the lhs is in the form of an even number, rhs is in the form of an odd number, we conclude a > 0, b < 0 such that f(a) = f(b) is absurd

[neon harbor]

Yep, good 👍

[neon harbor]

You can start by looking at just f: for which inputs does f output 13 or 15?

[scenic mesa]

it's the same as what you're doing, except i created cases based on f(a) and f(b) rather than a and b. what you're doing works just as well 👍

the proof i wrote uses contraposition

[granite perch]

Is "the pancake problem" appropriate for this channel?

[brave rock]

I would recommend just asking the question. If people think it's inappropriate they will point you elsewhere, and in any case it gets eyes on your question.

If you post in the wrong channel, nobody's gonna have you assassinated.

[granite perch]

I am designing a problem. The requirements are that it should be based on the concept of The Pancake Problem. It needs to have a definitive, reproducible solution. It should not be NP Hard.
My first thought was "what's the minimum number of flips to sort this given unsorted stack of N pancakes" but I imagine there's a number of different ways to approach it. And better algorithms would give fewer flips and finding the "best" verges on, if not crosses into, NP Hard.
So how could I structure a problem, not necessarily dealing with "minimum" or "best" but still with a specific solution?

[restive iron]

2a=42
2b=43

[restive iron]

f'x+a=1
f'x+b=4
f'x+c=9
f'x+d=16
f'x+f=25
just for reference by the way I think this might help a little bit

[robust monolith]

Ok

<@&268886789983436800>

[granite perch]

Maybe wrong channel 😅

[dusk berry]

maths very discretely

[vital dew]

xDom

[weary tiger]

complex analysis

[cloud holly]

Determine whether the relation R on the set of all Web
pages is reflexive, symmetric, antisymmetric, and/or tran-
sitive, where (a, b) ∈ R if and only if
a) everyone who has visited Web page a has also visited
Web page b.
b) there are no common links found on both Web
page a and Web page b.
I'm analyzing b for irreflexitivity, I think it's irreflexive because there is no way for page a to have a link with itself, which is the condition for irreflexitivty. In the solutions it says however not irreflexive, why?

[haughty pendant]

Hi guys, I have been working on this problem for a day or two. I think I have a solution and would love some feedback.

We first write up the number of combinations for each coin. For pennies $(1+x+x^2+\ldots ) = \frac{1}{1-x}$. For nickels $(1+x^5+x^{10}+\ldots) = \frac{1}{1-x^5}$, and for the dimes $(1+x^{10}+x^{20}+\ldots) = \frac{1}{1-x^{10}}$. We define $A(x)$ to describe the total number of combinations and then find an intermediary generation function $B(x)$

\begin{align*}
A(x) &= \frac{1}{(1-x)(1-x^5)(1-x^{10})}\
A(x) &= (1+x+x^2+x^3+x^4)B(x^5)\
\frac{1-x^5}{1-x}A(x) &= B(x^5)\
\frac{1}{(1-x)^2(1-x^{10})} &= B(x^5)\
\Rightarrow B(x) &= \frac{1}{(1-x)^2(1-x^{2})} \ ((x^{2})^5 = x^{10})
\end{align*}

We want to have the denominator as a single expression. Write $B(x) = \frac{C(x)}{(1-x^2)^3}$.
To find $C(x)$ we need to rewrite $(1-x)^2$ to have $(1-x^2)$ in the denominator.

\begin{align*}
\frac{1}{(1-x)^2} &= \frac{(1+x)^2}{(1-x^2)^2} \quad [(1-x^2) = (1-x)(1+x)]\
\Rightarrow C(x) &= (1+x)^2
\end{align*}

In general we know $\frac{1}{(1-z)^n} = \sum_k\binom{n+k-1}{n-1}z^k$, hence for $z=x^2$, $n=3$ we have

\begin{align*}
B(x) &= C(x) \frac{1}{(1-x^2)^3}\
&= (1+x)^2 \sum_k \binom{3+k-1}{3-1}(x^2)^k\
&= (1+x)^2\sum_k \binom{2+k}{2}x^{2k}\
&= \sum_k \binom{2+k}{2}x^{2k}+2\sum_k \binom{2+k}{2} x^{2k+1} + \sum_k \binom{2+k}{2}x^{2k+2}
\end{align*}

We'll now do a parity and split the coefficients of $b_n$ into odd and even terms.

% Consider $n=2m+1$, i.e., odd terms. Since the first and third term only consists of even powers, only the second sum contributes anything and hence $2m+1 = 2k+1 \Rightarrow m=k$. We find the odd coefficients for $b_{2m+1}$

For odd terms, only the second contributes to the result, because the first and third sum are even numbers. Let $2k+1=2m+1$. Then the odd terms of $b$ are

\begin{align*}
b_{2k+1} &= 2\binom{2+k}{2} \
% &= 2\frac{(2+k)!}{2!(2+k-2)!} \
&= \frac{(2+k)!}{k!} \
&= (2+k)(2+k-1) \
&= (2+m)(2+m-1) \quad [m=k]
\end{align*}

Finding the even coefficients, for the first sum we have $2m = 2k \Rightarrow m=k$. For the second sum we have $2m = 2k+2 \Rightarrow m-1 =k$.

\begin{align*}
b_{2m} &= \binom{2+m}{2}+\binom{2+(m-1)}{2}\
&= \frac{(2+m)!}{2!m!} + \frac{(1+m)!}{2!(m-1)!}\
&= \frac{(m+2)(m+1)(m)(m-1)\ldots}{2m(m-1)\ldots} + \frac{(m+1)(m)(m-1)(m-2)\ldots}{2(m-1)(m-2)\ldots }\
&= \frac{(m+2)(m+1)}{2} + \frac{(m+1)(m)}{2}\
&= [\frac{(m+1)}{2}][(m+2)+m]\
&= \frac{2(m+1)}{2}[(m+1)]\
&= (m+1)^2
\end{align*}

Let $k=2m$ then $a_{10m}=b_{2m}$. Since $a_{10m}$ is the number of combinations we can make for cents using only pennies, nickels and dimes we have $a_{10m} = (m+1)^2$. Which is what we wanted to show.

[vital dew]

fluffy snail

fluffy snail

[grand crown]

were you asked to use a generating function/was the point to practice using them? It seems a little overkill here

if we pick the number of dimes as i, then the number of ways to pick nickels is going to be 2(m-i) + 1,
sum from i = 0 to m of 2(m-i)+1 = 2m(m+1) - 2m(m+1)/2 + (m+1) = m^2 + m + m + 1 = (m+1)^2

if you were supposed to use generating functions / just wanted to practice using them, I think your solution works

[haughty pendant]

Exactly, I wanted to explicity use generating functions because they still seem like a foreign object to me.
The point wasn't the solution it was the journey through generating function world

[primal glade]

How to do this question?

[coral parcel]

A strictly increasing function is completely known once you have decided which numbers are in the image.

For "non-decreasing" you need to decide how many times each of 0,1,2,...,10 is an output of the function. That's a "stars and bars" problem.

[plain prawn]

uhh no that's a strictly increasing function

[random sparrow]

can someone help me

is ambiguous what {1,...,10} means but I think he means natural numbers

[robust monolith]

1 to 10?

[scenic mesa]

i assume it means {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

[robust monolith]

Like: 1,2,3,4,5,6,7,8,9,10

Unless those are real numbers?

[scenic mesa]

i doubt it

[random sparrow]

help with proving reflexivity

like, if f is bijecfive then we know is injective and f(x) = f(y) => x = y

[scenic mesa]

you know it's surjective, so you know 1 has a preimage

[random sparrow]

sujrective is ∀x ∈ Dom(f), ∃y ∈ Im(f) such that y = f(x)

?

no, the other way around

sujrective is ∀y ∈ Codomain(f), ∃x ∈ Domain(f) such that y = f(x)

[scenic mesa]

yes, and in particular, 1 is in the codomain, so there exists n such that f(n)=1

[random sparrow]

wunderbar, but now what?

no wait I think I get it

∀f ∈ F, such that
f R f <=> ∃n ∈ [1,10] : f(n) = 1 and f(n) = 1

[scenic mesa]

yes

[random sparrow]

reflexivity is proved using the fact every f in F is surj

@scenic mesa

what about symmetry?

∀x,y ∈ F,
x R y => y R x

for f,g bijective and n ∈ [1,10]
f(n) = 1 and g(n) = 1 => g(n) = 1 and f(n) = 1?

[scenic mesa]

yeah

[random sparrow]

I mean that is simply true because of the symmetry of the equality relation

[scenic mesa]

you don't even need to use bijectivity

yes

[random sparrow]

x = y => y = x
because = is symmetric

literally f and g being bijective has nothing to do with symmetry

what about transitivity

@scenic mesa

[scenic mesa]

i think you need injectivity here

[random sparrow]

for transitivity or symmetry

?

[scenic mesa]

transitivity

[random sparrow]

can you elaborate

x R y, y R x => x R z

[scenic mesa]

f R g and g R h
f(a)=1 and g(a)=1
g(b)=1 and h(b)=1
a=b by injectivity of g
thus f R h

[random sparrow]

wait a second dude

for symmetry we have

f R g => g R f

f(a) = 1 and g(a) = 1 => f(b) = 1 and g(b) = 1

how to conclude?

[scenic mesa]

you need 3 functions to demonstrate transitivity

[random sparrow]

I want to go back to symmetry dude

[scenic mesa]

oh sorry

[random sparrow]

something is not clear

with my symmetry proof

like

help me prove it

[scenic mesa]

why introduce b?

f(a) = 1 and g(a) = 1 => g(a) = 1 and f(a) = 1

[random sparrow]

dude

f R g and g R f doesn't guarantee same a

[scenic mesa]

f R g is the premise

[random sparrow]

this is where we use the fact it's bij

[scenic mesa]

you shouldn't have f R g => g R f at the beginning of the proof, it should be the conclusion

[random sparrow]

yes

help me prove it

[scenic mesa]

symmetry is f R g <=> g R f, right? it should be <=> rather than => i think

[random sparrow]

yes

one is stronger implication

both are correct

[scenic mesa]

let f, g be in the family F
f R g ⇔ ∃n / f(n) = 1 ∧ g(n) = 1 ⇔ ∃n / g(n) = 1 ∧ f(n) = 1 ⇔ g R f

[random sparrow]

dude

it is not same n

I mean it is same n because is bijective

but you shouldn't jump to conclusions like that

[scenic mesa]

i don't agree but i don't know how to convince you

maybe someone else can jump in and explain

[random sparrow]

like it's same n because they are bijective

but we should use a,b and argue they are bijective

[scenic mesa]

i disagree

[random sparrow]

well doing both f(a) = 1 and f(b) = 1 is only possible when a = b

in case you are in a hurry I guess you can omit that info, but generally speaking i don't see why not

[scenic mesa]

the relation would still be symmetric even if the functions weren't bijective

[random sparrow]

how so?

[scenic mesa]

take f(n) = 1 and g(n) = n
then f R g since f(1) = 1 and g(1) = 1
and g R f since g(1) = 1 and f(1) = 1

[random sparrow]

I see what you mean now

because and is commutative

or why?

[scenic mesa]

oh yeah

it's not because = is symmetric

it's because "and" is commutative

[random sparrow]

ok, that is enough justification for me

[random sparrow]

can I get help

[little prism]

how often are you gonna post a non english picture without translation and any indication of your progress

[cerulean wind]

i ignored your post because of this

[graceful grove]

find the number of 5-combinations and the number of 5-permutations of { 5a, 3b, 2c, 3d, 2e, f, 4g}

i have exam tomorrow, i need help with permutations & combinations

[lone bridge]

You are asked how many 5 element combinations can be made from a list of 7 distinct elements, do you know the formula for finding combinations?

[stray reef]

what does 5a mean?

is this a multiset with five copies of a, three copies of b etc?

[graceful grove]

5 a's

[lone bridge]

oh mb that does look like multiset

[stray reef]

.

[graceful grove]

idk

[stray reef]

if you're thinking of C(n,5) it ain't so simple here

[graceful grove]

yeah

[lone bridge]

-# my dumb brain thought '5a' was representing a single element in the set

[graceful grove]

no vc here 😭

[stray reef]

im not sure a nice formula even exists here

[lone bridge]

have you tried anything

[little prism]

there was a help channel in the mean time. not sure what the result of that was

[random sparrow]

i was trying to prove reflexivity

[lone bridge]

are you stuck at proving gof = gof?

[random sparrow]

so to speak, yes

[little prism]

gof and gof are the same function

there is absolutely nothing to show

[lone bridge]

first of all there is nothing to prove and secondly your screenshot is not complete

[random sparrow]

let me send a better screenshot

[lone bridge]

This can be considered an axiom that any entity is equal to itself.
i.e., if you have an entity E, then E=E is always true so gof = gof is always true. Idk what else to say here

[neon harbor]

wait, why doesn't TeXit say who wrote this? Did TeXit write this herself?

[lone bridge]

this would have been useful if you had to prove two different functions f, g are equal but here you have only 1 function g so ofcourse g is equal to itself

[lone bridge]

there's option to disable that and I did disable that

[neon harbor]

phew, I thought texit had become sentient

[random sparrow]

fair

[haughty pendant]

Let $a_n$ be the number of combinations for an $n$-bit sequence.
Split the problem into two parts, one where the nth digit is 1 and one where the nth digit is 0. Then we can describe the recurrence relation as the number of possible combinations we can make if the nth digit is $0$ or $1$. Because these two sets are disjoint, and fill out all possible combinations for a binary sequence which does not contain two adjacent 1s, then by the addition property of sets we have $a_{n} = |\text{n'th digit is 1}| + |\text{n'th digit is 0}|$. Where $||$ represents the number of combinations in the set.\

If the nth digit is $0$ then we have $a_{n-1}$ number of possible combinations. If the nth digit is 1, then we must choose $0$ on the $n-1$ place, but afterwards one can construct any legal combination of sequences, giving $a_{n-2}$ number of combinations. Combining the two then gives the recurrence

\begin{align*}
a_n = a_{n-1} + a_{n-2}
\end{align*}

We find the base case by counting the number of possible combinations $a_1 = 2, a_2= 3$ and hence $a_2 = a_1+a_0 \Rightarrow a_0 = 1$ which is sensible since $a_0$ is the empty string. We notice that this is a shifted Fibonacci sequence. We can find the closed form by using $(2.41)$ writing $G(x) = \sum_k a_k x^k = \sum_k F_{k+2}x^k$, where $F_k = \frac{\phi^k -\phi^{2k}}{\sqrt{5}}$. Hence the closed form is

\begin{align*}
a_k = \frac{\phi^{k+2}-\hat{\phi^{k+2}}}{\sqrt{5}}
\end{align*}

[vital dew]

fluffy snail

[haughty pendant]

The image shows an exercise and the text shows my hand at a potential solution, any feedback on the above is appreciated!
(if you saw the message earlier I apologize but I found several errors that I needed to correct for.)

[bronze elm]

hey guyz

[random sparrow]

anyone understands what is going on? supposedly intro to graph theory?

somehow related to matroids?

[quick folio]

@fast vale I felt like this ping was obligatory

[clever current]

There are too many questions in rosen, are there a collection of selected questions for that, some of the questions in the book are repetitive should I do all of them.

[cobalt steppe]

does anyone have a good set of videos for discrete math? my prof has cut pasted a video series with no other resources and it just... stinks.

I'm hoping a different explanation might be easier for my brain to wrap around the concepts

[random sparrow]

Given the following logic propositions, alpha and beta, it is said that alpha is stronger than beta if and only iff alpha -> beta is a tautology. In this case, it is also said that beta is weaker than alpha. Determine the relationship of strength of the following pairs of formulas

[winged delta]

Which ones are giving you trouble?

[random sparrow]

everything david

everything

can I get a helping hand? also, please ping me if responding :)

otherwise I might miss the message and reply years after

[winged delta]

Okay, let’s look at the first one

We have two possible tautologies: T -> F and F -> T

Thankfully we can just look up the truth table for implies to see if either holds

[random sparrow]

well

T -> F is false

F -> T is true

but neither of them is a tautology?

[winged delta]

No the latter is

It’s always true

This will make more sense when we look at b

[random sparrow]

ok

so F -> T is a tautology

[winged delta]

Yes

[random sparrow]

correct?

[winged delta]

We need to see if (p and q) -> (p or q), or vice versa

[random sparrow]

so F is stronger than T

[winged delta]

Mmhm!

[winged delta]

Intuitively, which seems stronger, “and” or “or”?

(Also I should head home soon, I may disappear for a bit!)

[random sparrow]

well

(p and q) -> (p or q)

how do I see if this is a tautology?

do I need to write the truth table?

[random sparrow]

wdym stronger?

AND is a stronger requirement, if thats what you are asking

well we can write the truth table and verify if this crap is a tautology or not

[random sparrow]

this crap is definetely a tautology

so (P and Q) is stronger logical proposition than (P or Q)

@winged delta

The other way around is not a tautology

true -> true is another tautology, same with true -> true (swapped)

true is stronger logical proposition than true it seems

@winged delta

this is another tautology

p is stronger logical proposition than (p or q)

the other way around is not a tautology though

this is another tautology

its always true no matter what

so false is stronger logical proposition than false

@winged delta

this is another tautology

so p is a stronger logical proposition than (p or q)

the contrary is not a tautology

@winged delta

this is not a tautology, neither is q -> p

this is not a tautology

@winged delta

the swapped is neither a tautology

[winged delta]

Yes!

I think you’ve pretty much got this

[random sparrow]

what about exercise 5?

[winged delta]

The strongest one will be a statement that implies all the others

The truth table for implies will help here

[winged delta]

Morally, its opposite should be the weakest

[random sparrow]

yeah

[random sparrow]

but

[winged delta]

Have you heard of the principle of explosion?

It not only sounds cool but is useful here

[random sparrow]

wdym?

[winged delta]

“A contradiction” is the same as False

[random sparrow]

yeah

[winged delta]

So in fact, False -> p is a tautology for any p for much the same reason as what you got here

That makes False the strongest!

[random sparrow]

yeah exactly

[winged delta]

Hopefully that’s clear from the truth table - no matter the q, F -> q

[random sparrow]

similarly

p -> true is always true

[winged delta]

Yep!

[random sparrow]

so true is the weakest!

[winged delta]

Mmhm!

“True” doesn’t help you prove any new facts

And “False” proves every new fact - and also their opposites XD

[random sparrow]

is tricky

but I think I kinda get it

[winged delta]

Sweet!

[random sparrow]

I appreciate the help david

sorry for the pinging

[winged delta]

Oh no worries! I don’t mind 🙂

[random sparrow]

:) thanks dude I appreciate it

[runic lava]

,,Q\land\lnot P

[vital dew]

glass

[edgy root]

Does anyone have any good resources for discrete self study? I'm currently reading Introductory Discrete Mathematics by V. K. Balakrishnan and the content is great but it's very terse.

[robust monolith]

Rosen. Also, you can ask in #book-recommendations

[sleek atlas]

Hi so theres like a problem im tryna solve

I need to find a way to find the shortest length arithmetic formula (like using only numbers 1 and -1, with only 3 operators of + * ^) for any number

Any ideas

[weary tiger]

S S Epp, discrete maths and applications

[sullen hill]

This teaches us that we must be false in life!

[lost helm]

hey guys, why do we need these copies?

[sacred fern]

because if S = T

then taking their union would just give you S or T

[lost helm]

two questions: 1. if S=T, then what are their copies such that $S \cap T = \varnothing$, and could the be called copies if they share literally not one common element with their respective ‘precopies’, i.e. S and T. 2. Isn't the whole point of disjoint union that we take sets A and B such that $A \cap B = \varnothing$? So why do we need copies if the sets, to have the operation defined between them, do not supposedly share any elements?

[vital dew]

nezhivoy

[sacred fern]

If S = T the way I have seen it is you consider $S \times {0}$ and $S \times {1}$ theb $S \coprod T = ($S \times {0}$) \cup ($S \times {1}$)$

[vital dew]

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

[sacred fern]

disjoint unions are useful in other places of math, for example in geometry

[sacred fern]

I think this is why he said "copies"

because S and S' are isomorphic

so they are "copies"

[lost helm]

so $S \times {n}$ and S are isomorphic for any fixed n?

[vital dew]

nezhivoy

[quick folio]

they may or may not share any elements

the point of the construction is that it should work regardless of that

so if they dont share anything then sure you can just take S' = S and T' = T

[sacred fern]

yeah because the bijection is simply (s, n) -> s

[lost helm]

yeah understood now

thanks guys

[random sparrow]

does someone understand what I need to do

[robust monolith]

Write a function?

[random sparrow]

not really

[robust monolith]

I think it's about writing the set of inputs, and the set of outputs for this. The requirement is always "True", I assume Z are the integers, and "x: Z", so what's the set of inputs?

[random sparrow]

just one integer that is the double of the other integer

just input is x in Z

output is 2x

[robust monolith]

Any integer as input, yes

[robust monolith]

That's it, and what's the set of the 2x?

[random sparrow]

just like

-6 -4 -2 0 2 4 6

the even integers aswell as 0

dunno if 0 is even or odd

[little prism]

how often are you gonna post a non english image withiut a translation and any indication of your progress

[random sparrow]

I tried to prove it

if someone can check my stuff

[ebon needle]

como zafe de ese tema

lo odie

Los que hablan ingles no te pueden ayudar porque no van a entender las proposiciones

[random sparrow]

de donde sos gordi?

where you from?

[shut egret]

I didn't read it but i would write something like:

Let X = the first line of your image
If X is true then J is true cause if J is false, X is false
So while J is true X is equal to
C interseccion C -> G
It means that if X is true then C is true analogous to the case of J
So if J and C are true, then X=G

And how X is True only if J, C and G then, by definition, X = the last line of your image

[shut egret]

Just read your prove and it looks right

It is actually better than mine

[shut egret]

Qué tema? Lógica proposicional?

[random sparrow]

let a and b be in R, Prove that for all n in N, ... = ... . Deduce the formula of the geometric series forall a not equal to 1. ...

[ebon needle]

Sisi

[ebon needle]

Uruguay

[fading heath]

if a girl's name is Chris
Then a girl's name is Chris
rian do you think this statement is valid according to the law of detachment

[stray reef]

"if A then A" is always valid and in fact true

[willow rose]

hi does anybody here know how to approach combinatorics questions?

[hidden totem]

is there something in particular youre looking for, like a list of topics, how to check answers, or common problem solving tricks, general mentality/mindset, or is this more general? can you be a bit more specific about the context? what grade level is this?

[willow rose]

i mean like in general if i see a sol 90% i understand but how to get to that sol i dont know im cs undergrad student in discrete math

class

[hidden totem]

hmmm thats pretty general, hard to pin down any particular advice

do you have maybe some examples you can show?

[willow rose]

sure

like these @hidden totem

[scenic mesa]

i think for the cube one you need burnside's lemma

oh... it's a bit simpler since the colors are all different

each colored cube can be oriented 6*4 different ways

so it's || 6! / 24 = 30 ||

(i'm assuming there are only six options for colors)

[woven ivy]

Need some push beyond the provided hint to get started with (a)

[scenic mesa]

i think (b) would be || 60! / (10! 24^10) ||
(i'm assuming you have to use all 60 colors)

[scenic mesa]

is this the books one?
|| ((2n)! / 2!^n) ((3n)! / 3!^n) ((5n)! / 5!^n) n!^(n-1) ||

[hidden totem]

I think, if im not mistaken, they are asking for general strategies

not a specific solution to this problem

also Burnside is i think way overkill

[hidden totem]

so a general framework i typically use to think about these problems

[scenic mesa]

you don't need burnside

[hidden totem]

there are two things that are tricky about combinatorics:

• what youre counting
• how youre counting

i think that first one is a little underemphasized

what you want to do is first draw out a couple examples of the thing youre counting

then answer a couple of basic questions to make sure you are not over/undercounting, that youre set up properly to check your answer later

specifically, how are you formally representing the thing you're counting?

is there an alternate way to represent the same object?

are you counting something you shouldn't be or counting it more than once?

have you covered every case?

by "formally representing" the thing you're counting, you can begin to build a picture for how to attack it

for instance, suppose the colors are 1-6, i will list the face coloring in order left, top, bot, right, front, back

123456 is one such coloring

so now you can think about how you can constructively make these representations

are you splitting into cases? are you making independent choices?

now you have a clearer picture for how you want to try attacking the problem of how to count it

and then finally check your answer by checking for both overcounting and undercounting (its possible to do both at the same time)

let me know if that helps or if you would like elaboration on anything

[scenic mesa]

let me revise this...
|| ((2n)! / 2!^n) ((3n)! / 3!^n) ((5n)! / 5!^n) (1/n!) ||

[scenic mesa]

it's really hard

[scenic mesa]

for example if n=6123, notice that 123 < 1000

[nimble hemlock]

is $P \implies Q \lor R$ logically equivalent to $P \land \neg Q \implies R$

[vital dew]

clubsoda14

[fossil mural]

yes

[random sparrow]

what kind of relations are symmetric and antisymmetric?

[grand crown]

if the relation R over the set S is symmetric and antisymmetric, consider 2 arbitrary elements in the set S that relate, aRb

since R is symmetric, bRa

but since R is antisymmetric, and aRb, and bRa, we know a = b

but since a and b were arbitrary elements of S that related, that means that each element in the set can only relate with itself

so relations that are symmetric and antisymmetric are subsets of the "identity relation" where every element of S only relates with itself

(some elements might have no relations at all, we just know that if an element does, it has to just be with itself)

[wind jetty]

hello guys i just got into the computer science college, and i want to learn discrete math deeply bcs i don't understand the logic so i want to practice more this lesson, any recommendation course or book to learn it?

[ancient river]

enderton elements of set theory?

[shy crater]

which kind of textbook r u using I think most of them r comprehensive enough

[hidden totem]

maybe this might be a tad overkill?

its easy for if you're going into like a proof theory/model theory sort of track, and maybe appropriate

but I feel like for comp sci doing discrete math

it might be better to pick something more broad, covering combi and maybe some other topics in a more accessible way

like there is almost no combinatorics in enderton and enderton goes pretty deep into like infinite cartesian products, peano axioms, constructions of the reals, alephs

like surely these are considered niche topics for comp sci, no?

unless you're going into theoretical cs i guess but i lump that in with the proof theory/model theory

[wind jetty]

i don't have any textbook, the teacher just explain in the screen

[ancient river]

what topics do you want to learn

[wind jetty]

i don't know i just wish that my logical.thinking can improve especially about this discrete math

i just have a college in a month ago

[shy crater]

if you want something general and supplements your basic knowledge try this I found this helpful https://discrete.openmathbooks.org/dmoi4.html

[random sparrow]

so subsets of {(a,a) ∈ R | a ∈ A} where A is the set for which the relation is defined in, where R ⊂ AxA

[grand crown]

yup

[random sparrow]

so if I find one a ≠ b, such that a R b, and that b R a then I can intuitively say that R is not antisymmetric

for a,b ∈ A

I'm just asking. because I all the time need to prove or disprove that some relations are symmetric and antisymmetric, so this can save me some time of thinking in which I can continue finding a counterexample

[grand crown]

yup

[warm abyss]

My solution is correct ?

[grand crown]

i would add that this is by definition what not being antisymmetric means

antisymmetric = for all a and b, if aRb and bRa then a = b

not antisymmetric = there exists a and b such that aRb and bRa and a != b

[grand crown]

this looks good

[soft night]

Hello guys I need some help with some discrete problems. I have 0 clue how to do problem 3 and 4, and number 2 I have somewhat of an idea but wouldn’t mind some help either. Thanks!

[topaz blaze]

Are you assuming A is the starting vertex for problem 3

But first, what do you know abt minimum spanning trees (MST)?

@soft night

[wind jetty]

hello guys i need some help with this discrete math problem. I don't have any clue how to do it, can anyone help me for this question. thanks!

[soft night]

I believe so yes, and for I know a little bit but I’m starting to study and remember some of it. I asked my cousin for help and he explained it to me but wanted to make sure it was the correct way. So he said it should look something like this
1. A-B (weight 2)
2. B-F (weight 1)
3. F-J (weight 2)
4. A-E (weight 3)
And so on, so when I add all of them it would give me 24 as MST.

[lone bridge]

For 1st one of the image containing 5 questions, think of it this way:
You have 5 boxes and unlimited Red, Blue, and Green balls. Your task is to place exactly one ball in each box, and the ball in a box can be of any color. In how many ways can this be done?

The first box can be filled with either a Red, Blue, or Green ball → 3 ways.
The second box can be filled by which balls? So how many ways to fill the second box? (remember repetition is allowed)
Same for 3rd, 4th, 5th.

So total number of ways to fill 5 boxes with 3 different balls when repetition is allowed is 3×....

[tepid light]

What is discrete maths?

[marsh onyx]

and I believe what makes it "discrete", is its separation from other subjects of inquiry. It's what truly makes math its own thing and not just a generalization of other studies and their mathematical requirements

[tepid light]

Got it! It's a collection of many maths topic. How many months would a average person took to study discrete maths completely?

[little prism]

you cant study any topic in maths "completely"

[robust monolith]

Discrete as in it uses the set of integers and sets that can be mapped to integers, i.e. it doesn't use the set of reals, right?

[dreamy wave]

just started college math, specifically polynomials need some past papers or a good video that explains it well and also set theory and set notations / set builders its confusing

[random sparrow]

can someone explain cassini identity

[quick folio]

it can use the reals

it just has to be indexed by the integers

[robust monolith]

Yes, I could be more specific.

[primal grove]

So according to my professor these SOP expansions are all incorrect can I get some sanity check on this?

Also its stated to prove these by laws only

[neon harbor]

Not enough context. What is F(x, y), what is SOP and what are you asked to show?

[primal grove]

F(x, y) is defined, SOP is sum of products and im asked to prove that each boolean expression can be expanded to a sum of products strictly by laws, im not allowed truth tables. Im asking for a sanity check, are these all wrong?

they are all expanded into SOP by well defined laws so how can they be wrong?

[neon harbor]

Looks correct to me, except 3b) where you wrote xy + xz instead of xy + zy

but surely your professor has more specific feedback than just saying it's wrong?

[primal grove]

yes that was a typo I understand that, and 3d) I understand is wrong because I forgot to expand the z into the resultant expression, I looked at my professors answers to these expressions and she follows the same steps as I did but she continues to expand past what I did so maybe that is why but I feel as if that is unjust because both my expressions and hers are equivalent by law

and no she didnt specify exactly why I was wrong

[neon harbor]

okay, if you post the professor's answers then we might be able to help you understand why your answers are wrong

[primal grove]

here is 2 a & c )

[primal grove]

and here are 3 b & d)

[neon harbor]

Maybe you need to write it as a sum of products of all 3 terms, not just 2? Do you have a definition of SOP?

[primal grove]

I dont have a specific definition from the professor but just the general definition of sum of products. What do you mean of all 3 terms?

[neon harbor]

If you don't have a precise definition of SOP then you can't determine whether your answers are actually sums of products

I don't think I can help much more, I think you just need to ask your professor why your answers are wrong

[primal grove]

Ok thank you for your time ill see what i can make of this

[primal grove]

So it seems that i have to express the sum of products as the sum of minterms in canonical form rather than standard

[wild condor]

Do you guys know any good resources online to help with proofs and understand discrete better? I'm feeling lost in my discrete math class 😭

[random sparrow]

hey guys, I need some help with combinatorics
The question is
Let f in {h : {1,2,3,4} -> {1,2, . . ., 50} | h is injective} be defined as f(x) = x for 1 <= x <= 4. Find how many functions g in {h : {1,2,3,4} -> {1,2, . . ., 50} | h is injective} satisfy that #(Im(f) \ Im(g)) = 0 or (Im(f) \ Im(g)) = 4

[hidden totem]

any particular topics?

the more specific you can be, the better the resource we can pick out

[hidden totem]

what is this notation? can you describe what the question is asking here?

[grand crown]

Im(f) is just the set {1, 2, 3, 4}

For Im(f) - Im(g) to be empty, we need Im(g) to contain Im(f). Since g is injective, and its domain has 4 elements its image can only have 4 elements, so it must be {1,2,3,4}

you then just need to figure out how many injective maps there are from {1,2,3,4} to {1,2,3,4}

for Im(f) - Im(g) to have a size of 4, Im(g) must not take out any elements from Im(f), meaning the images are disjoint.

This just means you need to find how many injective maps there are from

{1,2,3,4} to {5,6,…50}

Both of these are combinatorial questions

[random sparrow]

dude

there is only one F

[grand crown]

I’m aware

how do you think we know that im(f) was {1,2,3,4}

it tells us what f is

f(x) = x

[random sparrow]

G has two possible events Im(g) = {1,2,3,4} or that Im(g) subseteq {5,..,50}

[grand crown]

yes

[random sparrow]

of course #Im(g) = 4 regardless

but this is where it gets tricky

Im(g) = {1,2,3,4} and Im(g) subseteq {5, .., 50} cant happen simultaneously

they are independet events

4! + (46 pick 4)

[grand crown]

What you’re thinking of is disjoint

disjoint does not mean independent

in fact, generally disjoint implies not independent

let’s be specific

[grand crown]

All this is saying is you have two disjoint events

[random sparrow]

yes

so we need to use addition principle of counting , 4! + 46 pick 4

[grand crown]

exactly

[random sparrow]

and there is only one F

1 + 4! + (46 pick 4) right?

[grand crown]

we don’t care about the one f

based on f, we found all the possible g functions

we don’t need to include f in that

[random sparrow]

ok

[grand crown]

(and actually f does happen to be one of the valid g functions, it was included in our 4!)

[random sparrow]

ok so now what?

[grand crown]

You did it

[random sparrow]

how

what

4! + (46 pick 4)

this?

[grand crown]

yes

that represents the number of possible g functions

That’s exactly what we wanted to find

[random sparrow]

the problem is that I should arrive to 4! x (46 P 4) + 4!

[grand crown]

er that is wrong

hm

I don’t think that’s right either

4! * (46 C 4) + 4! would be right

[random sparrow]

what did you said?

[grand crown]

Wdym

[random sparrow]

,w 4! * (46 pick 4) +4!

[vital dew]

Results provided by WolframAlpha

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

Requested by renatoxbz

[random sparrow]

this you are saying is correct?

@grand crown

[grand crown]

yes

Wait

[random sparrow]

how?

[grand crown]

maybe we’re disagreeing on what pick means

I guess wolfram interprets pick as choose

Just to clarify

When you wrote 46 P 4, was that “permutations” or “combinations”

[random sparrow]

I meant this, srry

[random sparrow]

mb

[grand crown]

Okay got it

[random sparrow]

how are you agreeing with wolfram?

[grand crown]

nws apparently wolfram agrees with your convention

I’ll explain

but that requires going back to the original problem

[random sparrow]

ye

[grand crown]

We agree on counting the functions where the images are equal right

4!

The one we’re disagreeing on is when the images are disjoint

we need an injective image that maps to 5,6….50

here’s a really easy way to count that:

pick an output for g(1). There’s 46 choices for that.

pick an output for g(2). We already used a number so there’s 45 choices here.

g(3) then has 44 choices

g(4) has 43

so there’s 46 * 45 * 44 * 43 total ways to make the function g

This is the same as 46 permute 4

now let’s try getting this via combinations

out of the 46 choices, 4 of them will form our image set

The image set is unordered, so there’s (46 choose 4) ways to do this

But we do care about the order of those 4 elements, bc that decides which output is which for the inputs

Since each output is distinct, there’s 4! ways to order

(Very similar to the 4! argument for when the images of f and g are equal)

so we have (46 choose 4) * 4! total functions

(With disjoint images to f)

[random sparrow]

wait a second dude

there is only one F, agree?

[grand crown]

yes

[random sparrow]

then we have a disjoint event, that either Im(g) = {1,2,3,4} or that Im(g) subseteq {5, ..., 50} with #(Im(g)) = 4

so for arranging F there is only one way

[grand crown]

Pause

We don’t care

We already found our conditions

[random sparrow]

true dat

[grand crown]

so just focus on counting the ways to make those images

[random sparrow]

ok so for the first disjoint event we have 4!

and for the second one we have a Permutation(46, 4)

@grand crown you here?

[grand crown]

Both of those are correct

[random sparrow]

then how do we get to 4! + 4! x C(46,4)?

[grand crown]

algebraically

( n choose k ) * k! = (n permute k)

[random sparrow]

xD

[grand crown]

There’s a combinatorial way to see this too

[grand crown]

46 choose 4 gives us unordered subsets

But to define the function g we have to order them

so that’s why we multiply by 4!, bc there’s 4! orders

that’s why 4! * 46C4 is the answer

[random sparrow]

,w 4! + nPr(46, 4)

[vital dew]

Results provided by WolframAlpha

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

Requested by renatoxbz

[random sparrow]

dude

why does order matters?

[fossil mural]

because, for example, f(1) = 5, f(2) = 6, f(3) = 7, f(4) = 8 is a different function to f(1) = 8, f(2) = 7, f(3) = 6, f(4) = 5

even though they both have the same image, which is {5, 6, 7, 8}

[random sparrow]

in permutations we have more possibilities or in combinations we have more?

[grand crown]

Maybe try to reason it out

what do permutations represent and what do combinations represent

[random sparrow]

algebraically speaking combinations are less

[grand crown]

Yes that’s true

it’s good to remember though, these expressions were defined because of what the terms mean, not vice versa

[random sparrow]

yes so order does matter

two functions can have same image being distinct functions

[random sparrow]

is hard

[grand crown]

it’s hard yeah, but understanding what these words mean and why the formulas look the way they do will make your life a million times easier for combinatorics problems

[grand crown]

That’s a good picture yup

permutations are literally just “combinations except sets are also distinguished by order of the elements”

so that has to just be combinations * number of ordering

[random sparrow]

the problem is

either Im(g) = {1,2,3,4} or Im(g) subset {5,6,...,50}

[grand crown]

yes

[random sparrow]

this are all the possibilities when Im(g) = {1,2,3,4}

its equivalent of sitting 4 people in 4 different chairs

or the number of ways of arranging the letters ABCD

no matter in what chair you sit the first person, for the second person you have 3 chairs

since all of this events are hapenning simultaneously we have 4x3x2xx1

anyways I think I kind of get it dude, is just that is tricky as hell

its just 4! + permutation(46, 4)

[grand crown]

yup

[random sparrow]

I will have a lot of combinatorics question from now on in this channel, I appreciate it both of you guys aswell as the reaper guy, I have been stuck in this one for a while

like, my problem is that I am not familiziared with the basics

this exercise was not hard, but like, you need to udnerstand that if you dont understand the basics everything falls apart

you know what I mean?

[grand crown]

yeah, the problem is easy if you understand permutations and combinations well, but when those concepts are new it's difficult to apply them

in general though, counting principles solve everything

you don't need to know what a combination or permutation is to solve this problem

they exist to make life easier, and make it easier to categorize problems and quantities

they shouldn't be stopping you from solving it

[grand crown]

like this is the exact same thing as 4! * (46 choose 4), and the exact same thing as (46 permute 4)

just 46 * 45 * 44 * 43

that's really what the problem was asking for, and if you can recognize and understand that, then the permutation and combination expressions become synonymous with this, up to scaling factors for order

and then the ease comes from just being able to invoke the permutation expresison instead of manually doing a product count

[true venture]

nice graphic

[buoyant shard]

I am a little stumped with how to answer this.

If A and B equals 4, what is a? I am not sure how to use this infomation. Maybe i could say that, a^2 - 4a + 7 = 4 and then try to solve this because whatever value is in a and b, i know that a and b share 4. This is the only idea that I have but it sounds wrong.

[grand crown]

No that’s exactly correct, there’s no other alternative

If that doesn’t equal 4 then A wouldn’t contain 4, and then the intersection definitely wouldn’t contain 4

[buoyant shard]

wow!

okay, its been long since I have done algebra, let me try to solve it like this. thanks man!

[weary tiger]

Suppose you have natural numbers with the following properties: a > b > c > d.
Does any in/equality exist for the following form $x_1 x_2 + x_3x_4$ ?

[vital dew]

進化

[little prism]

well ab+cd>b^2+d^2 or something? I dont really understand what you want

[weary tiger]

I mean stuff like $ab + cd$ sign $ac + bd$

[vital dew]

進化

[little prism]

sign?

[weary tiger]

I was asking myself if it does make a difference which parts you multiply with which but I failed to prove anything

[weary tiger]

=, < , >, etc

[little prism]

you mean whether ab+cd or ac+bd is bigger?

[weary tiger]

yeah or something simillar

[little prism]

you should be able to come up with examples of either

probably

[wide sail]

Does any one knwo how to solve q4 and explain in q5 that the diam is 4

[weary tiger]

interestingly, I fail to find numbers such that ab + cd < ac + bd.
(for new people: suppose a > b > c > d are natural numbers)

[hidden totem]

yeah, because
ab - bd < ac - cd
b(a-d) < c(a-d)

and since they are all natural numbers, they are positive, so you are allowed to divide both sides by (a-d), so this is proven

there is also a super high powered version of this inequality called the rearrangement inequality

[random sparrow]

I need help with divisibility and modular arithmetic

[cerulean wind]

if we define a(n,n) = 1, a(1,m) = m, a(n,m) = 0 for n > m, and a(n,m) = sum a(n - 1, m - k) for k = 1 to m - n + 1, is a(n,m) = m C n?

this is trying to count the number of order preserving injections from {1,..,n} to {1,...,m}

clearly the n element subsets of m are in bijection with the order preserving injections {1,...,n} to {1,...,m}, but i was wondering if anybody could verify if this recurrence is correct.

[grand crown]

do you have a definition of a(n, m) for negative entries? it seems like the summation always iterates the right argument from m-1 to 1-n

[cerulean wind]

what do you mean negative entries?

like n,m < 0?

[grand crown]

or like do you want a(m,n) to be valid for m, n < 0

[cerulean wind]

i don't care about those

[grand crown]

yeah

why does k iterate to m + n - 1 then

[cerulean wind]

let's say n = 3 and m = 5.

1 _ _ _ _ => a(2,4)
_ 1 _ _ _ => a(2,3)
_ _ 1 _ _ => a(2,2)

these are the possible starting positions for an order preserving injection {1,2,3} -> {1,2,3,4,5}

[grand crown]

right that makes sense

[cerulean wind]

sorry

m - n + 1

[grand crown]

ahh okay

[cerulean wind]

typo

[grand crown]

it looks really similar to the hockey stick identity and i wanna assume the diagonal entries enforce the behavior everywhere from there

i will verify

[cerulean wind]

writing some code to veryify now lol

[grand crown]

okay that def is hockey stick so m C n is at least a solution to the system

[cerulean wind]

yea, code seems to be agreeing too

[grand crown]

i think its fine to let a(0, m) = 1 tbh, empty function vacuously preserves injection or smth lol

hmm is there a similar reasoning for zeroing out the other way

oh yeah its just not a function

so a(m, 0) = 0 is fine

okay and yes the boundary conditions guarantee uniqueness

amazing

[cerulean wind]

yea, that's cool, right?

[cerulean wind]

it should be hockey stick after shifting indicies, right?

[hidden totem]

this is in fact hockey-stick identity

it's a lot easier to see by notationally just first assuming a(n,m) is just mCn and then proving the summation

[grand crown]

yup

in essence this is a combinatorial proof of hockey stick loll

[odd garden]

Can someone explain this to me in a simpler way

[fervent flare]

i can try summarizing!
any DFA accepting L needs to have a cycle of states because the strings in L can get arbitrarily large. you can traverse that cycle again to get some other string that M accepts, but that other string is not of the form 0^n1^n.

this kind of reasoning is called the pumping lemma, and "why exactly that new string isn't in L" is the specific thing you need to prove
e.g here the book breaks it down into those three cases: having both 0s and 1s in the cycle would mean a 0 comes after a 1, and having only 0s or 1s would mean they're not equal in number.

[odd garden]

Can someone explain to me how is this dfa a possible solution ? Because if we take the string 'a' or 'b' then it will accept it altough it did not alternate between them

[cerulean wind]

this comes down to what they mean by ‘alternate between’

the strings “a” and “b” apparently alternate between “a” and “b”

which i suppose makes sense. if alternating between “a” and “b” means that whenever “a” is non-terminal, the character “b” follows, and whenever “b” is non-terminal, the character “a” follows, then “a” and “b” alternate between “a” and “b”.

[odd garden]

Yes true and in the question it states between “a’s” which means many of them

And “b’s”

[cerulean wind]

i don’t think that gives a precise enough definition of alternation (otherwise you wouldn’t have had the question)

but

[cerulean wind]

this one makes sense

[shut ivy]

Is this true?

because when trying to prove using induction I reach to point where I have $\frac{1}{n+1+n+1} = \frac{1}{2n+1} - \frac{1}{2n+2}$

[vital dew]

rabbits_advocate

[little prism]

well then either you fucked up or its not true. have you computed both sides for small n? more than just n=1?

[rugged heath]

pretty sure it's true (tested it to n=3), but the tricky part is the RHS has an n in the actual formula

[lone bridge]

I did get equality by induction. Can you show your steps? @shut ivy

[patent jolt]

I am studying semantic tableaux and using automated theorem proving, in all the references that I find they have 2 set of rules, alpha rules for conjunctives (for prolongation) and beta rules for disjunctives (branching) and the method follows from assuming the formula given is false, and then procceding, if we get a closed path that means we have a contradiction hence the formula is valid.

however in the notes provided to me, they ask us to use alpha rules (conjunctives) as branching rules and bet rules for prolongation and expect us to start by assuming the formula given is valid, and if the paths are closed in this scenario it means the tableaux is indeed valid, I do not understand how or if these two are equivalent, help. I am pretty sure the non standard method I explained second is something I have written exactly what the instructor said (ofc they could be wrong too) but yes, anyone?

@ me when replying

[shut ivy]

Ok for the induction step i assumed it is true for n and then for n+1 here is the left hand side
$\sum_{k=1}^{2(n+1)}\frac{(-1)^{k+1}}{k}=\sum_{k=1}^{2n}\frac{(-1)^{k+1}}{k}+\frac{(-1)^{(2n+1)+1}}{2n+1}+\frac{(-1)^{(2n+2)+1}}{2n+2}=\sum_{k=1}^{n}\frac{1}{n+k}+\frac{1}{2n+1}-\frac{1}{2n+2}$

[vital dew]

rabbits_advocate

[shut ivy]

and the right hand side
$\sum_{k=1}^{n+1}\frac{1}{(n+1)+k}=\sum_{k=1}^{n}\frac{1}{n+k}+\frac{1}{n+n+1}$

[vital dew]

rabbits_advocate

[rugged heath]

thing is that doesn't quite work because n is in the formula itself right?

or am I missing something

[shut ivy]

I can replace n with something like a in my assumption and it's still going to end up with this result

unless I missed a step

[rugged heath]

sorry I'm distracted rn so won't be much help, I'll let Shubh do it

plus I haven't actually solved the problem myself

[lone bridge]

@shut ivy

you have to replace n with n+1 in second summation

[shut ivy]

i don't see how the equality still holds

[lone bridge]

just equate the two and see you get 1=1

[shut ivy]

why did you subtarct with 1/(n+1) on the right hand side

[lone bridge]

try to open summation 1/(n+1+k) and summation 1/(n+k) and I think you will see it

to make both equal, we need to add and subtract some terms on right hand side

If you still don't get it, I can explain it but I think you will get it on your own after writing the summations in expanded form

[shut ivy]

alright I will try to break the summation again

thanks for the help

[shut ivy]

i got it now thanks again

[true venture]

What are semantic tableaux? Sounds interesting, but I don't think I can help

[odd garden]

Is this the correct way to solve the problem?

[winged delta]

In decimal! Huh, tricky.

Should be right, you just check if 1 appears 3k times

Which is what your machine does

[fossil mural]

yeah that looks correct

...well there is the edge case of whether you want to consider "" to be a number that is divisible by 3 (the most obvious choice, and the one your solution appears to be implicitly making, is that this is a representation of the number 0)

but leaving that sort of thing aside, yeah, you got it

[winged delta]

(Are people learning automata in discrete class? Can I change my syllabus to cover automata, I’d like that so much better than the course I inherited 😭)

[odd garden]

The course name is actually Theory of Computation, but it was first named Discrete II

Thanks for the help 🙂

[winged delta]

Sure 🙂

(Damn, probably no changing Discrete I then, I’ll just teach Theory of Computation when I get the chance - I’ve already pitched it a little bit)

[little prism]

<@&268886789983436800>

[timber elm]

This is the graph theory problem, Can anyone tell me how I need to show in part(b). ( if possible, I may need a hint).

[cerulean wind]

i think it is asking you to show that there is a graph G of order n >= 2 satisfying deg v >= (n - 2)/3 for each vertex v of G with exactly 2 components

[timber elm]

I see, really appreciate that

[tired widget]

anyone rn that could help me?

[odd garden]

can someone check if my dfa is correct for the problem?

[hidden totem]

seems right?

[modest bridge]

What the fuck is Discrete Meth?

[torn quarry]

hello, i am struggling to understand the restrictions of universal generalization. i am now wondering if R(x) restricts me from using ug, or it doesnt because it is a different property from P. thank you in advance!

[weary tiger]

do you have the original quesiton

[torn quarry]

it is 2a

[grand crown]

is there an order of operations for the and and the implies

[scenic mesa]

I think it should be "and" first, that's how it is in Lean

[odd garden]

Do I need 5 states for this ?
q0 with two arrows with inputs epsilon
Q1 where number of zeros is even, Q2 where number of zeros is odd, Q3 where number of 1's is even, and Q4 where numbers of 1's is odd?

[lilac solstice]

Hey guys I don't know if I'm in the right channel but is this correct? It seems pretty obvious but I'm not finding the correct result in an exercise where I need that, so I'm not sure

[lilac solstice]

Nevermind, a random calculation error sneaked in and I spent the whole day figuring it out 😅

[wise dawn]

Am I dumb or you guys just too smart

[lilac solstice]

None of these my friend

[wise dawn]

Thank you for making me feel good

[spring hound]

You should indicate which state is the starting state. Also, if the natural numbers don't include 0 in your course, you need to handle that. Other than those, it looks good.

[dawn iron]

i dont want an answer to these questions, but i want to ask how difficult are these questions are from 1-10?

[winged escarp]

2 and 3 are moderate by 1 and 4 are deeply rooted in number theory

[dawn iron]

i passed discrete math in uni last semester but i dont know anything about it

[tired summit]

2,3 are 2. 1 is like 3, and 4 is 4 too I think.

[hidden totem]

3 isnt so much as hard as it is just algebra bashing

you just need to be disciplined and careful

2 is a little tricky, you have to at least be competent with your basic counting principles

1 can be difficult if youre not familiar with induction proofs, but otherwise should be relatively straightforward given a key insight

4 should be very easy if you just apply both the theorem statement as well as the result from problem 1

so the difficulty is very difficult to compare, these questions all test completely different skills

1: proof writing and exposition
2: holistic problem solving and rigor
3: bashing
4: applying known results, synthesizing knowledge

[winged delta]

Question 3.4 also seems incorrectly phrased - shouldn’t it be a limit of f(n+1)/f(n)?

[hidden totem]

nope because there is a closed form for f(n) so there is a closed form for the ratio

its the ratio in terms of n

[little prism]

but its asking for the name of the ratio

instead of the name of the limit

so either they are asking the wrong question or I really dont know what they want to hear

name of the limit would be obvious

[sonic sun]

Hi, in my algebra course a gcd of two integers is defined as an d integer that divides both and such that for any other integer e that does the same, e | d too.
This is a stronger definition than the common sense one of gcd being, namely, the largest integer that divides the two considered integers.
For me grasping the fact that gcd is divided by any other common divisor is trivial in the factorization point of view...
But without that, how could it been derived from the "common sense" definition of gcd? Do these two facts meet at the Bézout lemma, that is showing that gcd(a,b) is a linear combination of a and b?

[cunning plank]

well from the common sense persepctive, if every other integer e that divides both integers satisfies e|d, d must be the largest integer that divides the 2 consdiered integers

[sonic sun]

Yes this implication is the simpler one

But if I were to define gcd not with that "magical" property, rather just being the largest integers that divides both

To derive back that fact should I prove Bezout lemma?

The formal one is a definition that makes the intuitive property (being the largest) a corollary and gives away the non-trivial one for free

[flint lynx]

Anyone who wanna talk or have discussions on set theory algebra including group theory etc, linear algebra, propositional logic or predicate calculus
i just like to discuss and maybe learn alot by exchanging opinions

[random sparrow]

Let $\mathcal{F} = {f : {1,2,3,4,5} \to {1,2,3,4,5,6,7,8,9} }$.

a) Determine how many functions $f \in \mathcal{F}$ satisfy $#{x \in \operatorname{Dom}(f) \mid f(x) = 9 } = 2$.

b) Determine how many functions $f \in \mathcal{F}$ satisfy $# \operatorname{Im}(f) = 4$.

[vital dew]

Renato

[random sparrow]

i need help please

[grand crown]

a is asking for the number of functions that map exactly 2 inputs to 9

in other words, we want the number of ways to pick 2 elements in our domain, which we will map to 9, and then map the remaining 3 elements in our domain to unique numbers from 1 to 8

those are both straightforward counting questions

for b, theres a few ways you can do it

the easiest imo is, we know 2 of the inputs need to map to the same number, and the remaining 3 inputs should map to distinct ones. choose the 2 inputs that should map to the same number, and there's 9 choices for what they map to. the remaining 3 inputs have 8 * 7 * 6 choices for their outputs

[random sparrow]

care to elaborate?

[grand crown]

not really, what part are you confused by

[random sparrow]

how to do A

@grand crown

[grand crown]

I told you how to do A, I don’t want to just restate everything again without you explaining what’s confusing you / attempting to follow the logic

[random sparrow]

two inputs output 9

the rest of the slots have output 1 to 8

[random sparrow]

P(8,3)

[random sparrow]

the issue is that since f is a function it cant map two exact same inputs to different outputs

[grand crown]

yes but we’re mapping 2 different inputs to the same output

8 permute 3 yes

[random sparrow]

or is it combination?

[pure osprey]

How can I get better at proof writing

[random sparrow]

read proofs from other people

and then adapt those ideas into yours

[random sparrow]

permutation or combination

?

[grand crown]

Permute because the order matters

[random sparrow]

how so?

why does the order matter

[grand crown]

mapping 1,2,3 to 7,8,9 is a different function than mapping 1,2,3 to 9,8,7

[random sparrow]

i dont think I follow, care to explain a bit please?

[random sparrow]

isnt it the same?

oh yeah is different function but same image

what is your point? @grand crown

[grand crown]

you want to count the number of functions

That’s basically the point

Order clearly matters then

[random sparrow]

sure

so if order matters is a permutation?

[rare sun]

Are you from Nigeria ?

[timber elm]

Can anyone explain why the differene here is O(nr) and how this equality get. I mean for -o(1) part.

[grand crown]

Yeah essentially, you just don’t divide by the extra factorial in a combination

[eternal shale]

Maybe this is a bit of a stupid question but i started a computer science degree last week and the only subject i just dont understand anything of is discrete maths and i was wonder if somebody knows a great source or whatever where i can kinda learn the basics because i feel like my professor just assumes you already know the basics and its not even in his books anymore

[prisma lily]

I have no way of knowing exactly what your discrete math course covers, but Rosen's Discrete Math was a good resource for me

it covers everything with a reasonable amount of explanation, and you should be able to follow it with no background knowledge

[rare sun]

-(13-77)
(-1)* (13-77)
(-1)*(13)+(-1)*(77)
= 13 + 77
Is this a correct answer?

[prisma lily]

no

the minus sign on the 77 magically disappeared on the third line

also this does not belong in a university math channel

[rare sun]

Which channel then?

[prisma lily]

#prealg-and-algebra

[eternal shale]

hmm thanks i could show you the table of contents of my book but its a bit of a long list. I can get a tutor from my university only for maths tho not computer stuff (which isnt an issue for me) because im doing the computer degree so gonna do that and read some stuff.

[prisma lily]

since you've only just started uni, you may not have read too many textbooks before to learn stuff but it's a really good way (and sometimes the only way) to learn advanced math

and if a textbook is good it will kinda take you through the "story" of the subject and you won't need to watch any lectures at all

[eternal shale]

well i did an engineering degree before but that was in an applied science uni and the math wasnt that difficult so im kinda already in a bit of a panic..

[prisma lily]

don't worry, you can always ask for help here if you get stuck while reading

good luck

[eternal shale]

alright, thanks

[random sparrow]

Prove that for all $n \in \mathbb{N}$, the value of $\gcd(7 \cdot 3^n - 5^{n+1}, 3^{n+1} + 7 \cdot 5^n)$ takes only two values. Find these values and show an example in each case.

[vital dew]

Renato

[random sparrow]

can i get some help!?

[prisma lily]

have you posted the problem somewhere else

if not, what have you tried

[random sparrow]

dunno how to start

[random sparrow]

no

[prisma lily]

well usually if you need to prove something holds for all natural numbers, induction is a good thing to try

have you tried induction

[random sparrow]

we dont need induction i think

like, if the result of this gcd is equal to d, then

d divides 7.3^n-5.5^n
d divides 3.3^n+6.5^n