discrete-math

[limpid fossil]

actually never mind

we can say probability the element is 42 AND the element is at the first index

and the probability of it being in the first index is 1/n?

and probability of 42 is 1/2

so its 1/2*1/n

i feel like im not really understanding probability tat well...

[elder berry]

Yes, but why does that matter?

The value for the probability that 42 is in the first position, and;
the value for the probability that 42 is in the last position, are the same value

The value of the probability being 1/(2n)

So let's say you play a game picking arrays and checking whether 42 is in the first place or not

you start picking arrays, (or linked lists), and you repeat this process 2n times

in those 2n times that you pick linked lists, it is expected that only once will you get a linked list such that 42 is present and 42 is in the first position

it is also expected that you will get 42 in the second position once

and so on and so on for 42 in any k-th position

that means that n of you picks (at least what you would expect, experimentally these values won't be precise), you will once get the linked list that has 42 in the first position

Maybe a good analogy would be to think of the following:

imagine a cube that is painted with 6 different colors, red being one of them

you win the game if once you throw the cube, it lands on red

the chance to win the game is 1/6

this is, indeed, the same probability that the cube would land on blue, green, etc.

None of that is important however, and shouldn't distract you in figuring out the required probability

[dense glade]

does g or f have an idtentity element?

[dark oyster]

thank you

[limpid fossil]

is there a trick to do this without manually counting? they got 10

[onyx hull]

Hi all, to compute the cardinality of a power set is 2^n.. how would I compute the cardinality of P(A) x P(B), where |P(A)| = 8, and |P(B)| = 4, is it simply 8x4?

[coral parcel]

Yes.

[coral parcel]

The tree in this question is very simple -- the 6 at the root must always be first and each of the two subtrees must be inserted from the top down.

[onyx hull]

ty ser

[coral parcel]

The only freedom is in how to interleave the two sequences (3,1) and (8,10,9). This may be done in (5 choose 2) = 10 ways.

[limpid fossil]

i dont think im correctly interpreting the usage of choose in this context: to me 5 choose 2 says how many possible combinations are there of choosing 2 objects from 5 objects, but like shouldnt 3, 8 be selected first in some order

like to me it looks like its counting the selection 3, 10

but you cant insert 10 without inserting 8 first

[coral parcel]

No, the intuition is: You have 5 timeslots to do something in. In two of those timeslots "something" has to be "insert the next element in the left subtree" and in the remaining three the something is "insert the next element in the right subtree".

[limpid fossil]

hm i never thought about it like that

[coral parcel]

That's how to count interleavings of two ordered lists. (You can use it to find a recursive formula for the number of orders to construct a binary search tree in).

[limpid fossil]

thanks!

[weary tiger]

Dave swims three times in the week. How many ways are there to plan his workout schedule (i.e. which days he will swim) for a given week?

I am confused on this one.. On one hand I get it but on another I don't.

Isn't a permutation depending on how you look at the question as the arrangement of what day Dave swim first would matter?

[onyx hull]

Does an empty set only exist when computing the power set? I'm currently working on
"{X |X ⊆(A −B), |X|= 2}" where my difference is {7,8,9}.. which is |3|.. the only way I can see it having the cardinality of 2 would be {{∅},{7,8,9}}

[coral parcel]

Are you saying that A\B = {7,8,9}?

Then you're being asked to find two-element subsets of {7,8,9}.

But {{∅},{7,8,9}} is not even a subset of {7,8,9}.

[onyx hull]

Ah, so more like {(7,8),(8,9)}?

[coral parcel]

Is (7,8) an element of {7,8,9}? Is (8,9) an element of {7,8,9}?

[onyx hull]

no

would be a product right

[coral parcel]

Then {(7,8),(8,9)} is not a subset of {7,8,9}.

[onyx hull]

{7,8} is a subset of {7,8,9}

[coral parcel]

Yes.

[onyx hull]

I see, I am just a little confused on the notation

[coral parcel]

And it has 2 elements, so {7,8} is one of the elements of {X |X ⊆(A −B), |X|= 2}.

[onyx hull]

X could be {7,8} or, {8,9}

[coral parcel]

So {8,9} is another element of your set.

There's one more, though.

[onyx hull]

X = {{7,8}, {8,9}} ?

[coral parcel]

No, {{7,8}, {8,9}} is not a subset of {7,8,9} and therefore does not qualify as the X in your definition.

You have seen that {7,8} is a possible value of X, and that {8,9} is also a possible value of X.

[onyx hull]

there's also {7,9}

[coral parcel]

Yes.

[onyx hull]

Then you're being asked to find two-element subsets of {7,8,9}. Is this kind of like.. list all the possibilities of X where |X| = 2?

[coral parcel]

Yes.

[onyx hull]

Ahhh cool

Thank you!

[coral parcel]

And you have now found all of them.

[onyx hull]

😄 the notation is half the battle some times..

thanks!

[coral parcel]

I'm assuming you're being asked to write the set {X |X ⊆(A −B), |X|= 2} explicitly.

In which case the answer would be {{7,8},{8,9},{8,9}}.

(But note well that this result is not what is called X here).

(And yes, this is very much a "have you understood the notation" check question).

[sturdy walrus]

Hey guys, I am trying to prove this, but I don't understand what I am doing wrong here. Could someone take a look at this?

[craggy juniper]

you already proved the base case

so assume that the equation holds for all $2\leq k\leq n$ maybe

[vital dew]

quantum

[craggy juniper]

i’ll have to check my notes to see if that actually works

but i think it does

[craggy juniper]

then you prove that the equation holds for n+1

actually it might be for all $2\leq k$, then you prove that it holds for $k+1$

[vital dew]

quantum

[craggy juniper]

yes that’s what it is

@sturdy walrus

[onyx hull]

Thank you very much ser

[sturdy walrus]

Gotcha, I fixed that part. Am I doing something wrong for k+1 here? I ended up with 3k^(2) + 5k + 4 when I should be getting 3k^(2) - n + 2.

[craggy juniper]

i don’t know what your fixed work looks like so i can’t answer

oh shoot i’m dumb you just changed a single sentence lol i just realized

well

you have your k’s and n’s mixed up

you should be defining it all in terms of one variable

assume the thing you are trying to prove holds for all $k\geq 2$, then, using $a_n = 2a_{n-1}-a_{n-2}+6$, prove that $a_{k+1} = 3(k+1)^2-(k+1)+2$

[vital dew]

quantum

[dim hemlock]

what does the | symbol mean in this problem?

[balmy jay]

Given

So P(A|B) is the probability A happens, given that B already happened

[dim hemlock]

gotcha, tysm!

[balmy jay]

Np!

[mental pecan]

anyway to guess the solution to this guy? the next two are a_2 = 19, and a_3 = 65

i found the solution on wolfram but its super complicated

[stray reef]

the charpoly is x^2 - 5x + 6, or (x-2)(x-3)

so all solutions will be linear combinations of 2^n and 3^n

[sweet ingot]

For this.

What about a function that takes in a number and randomly adds a number from a list containing 1-5?

is that not a function?

kinda like f(x) = x + random(1-5)

[stray reef]

only if you consider it as a random-variable-valued function

but to do that you need to develop some probability-theoretic machinery

[sweet ingot]

ah ok so its always determined before it goes in?

[stray reef]

so as-is it's not a function in the sense you're used to

functions are deterministic yes

[sweet ingot]

ok thanks

Also we are learning about partial functions, does this go by any other name commonly? I dont see that much info compared to other topics about it online

[stray reef]

no, and there is not much to be said about them anyway

[sweet ingot]

ok thanks

[pale epoch]

you dont really say how you generated the list?

one can verify that those are indeed subgroups but you need some kind of argument why there arent more

also what does mean

[unique canopy]

Could you help me with explaining how to generate the list and I missed the 1 in the definition - it was supposed to be inverse

[pale epoch]

you can argue with orders of the elements

you wrote down all the cyclic subgroups

but adding any other element to any of those will turn into the whole group

either for order reasons or you can just test

actually there is a better argument

if you know that Z_7^x is cyclic and you know how subgroups of cyclic groups look

[unique canopy]

thx u

[muted gate]

guys guys

[weary tiger]

what do I do here? I don't see anything in the notes that lists the different functions that are options for the answers

[proven silo]

Should be fairly straightforward what most of them mean - for example you should be able to figure out what integer and real number functions are

[weary tiger]

Well my notes don't explain it

[proven silo]

What does integer mean?

[weary tiger]

Whole number

As in

[proven silo]

So what do you think the function should do then?

[weary tiger]

One without a decimal

[proven silo]

If it is called integer function

[weary tiger]

Idk, they all have integers here

[proven silo]

f: R to R with f(x)=3x-7

I’m allowed to plug in all real numbers - are all real numbers integers? Do you then think it is an integer function?

[weary tiger]

I don't get it

[proven silo]

Get what? You are given that function

[weary tiger]

If decimals count as real numbers, then I guess not

[proven silo]

You don’t know what $\bN, \bZ, \bQ$ and $\bR$ mean?

[weary tiger]

No

[vital dew]

ScapeProf

[proven silo]

Natural, integers, rational and real numbers

Should for sure be in your book otherwise I would suggest you check wiki or smth

[burnt oxide]

how does

this simplify?

would it just be p->q ?

[weary tiger]

No dice

Man this is frustrating

[dense glade]

How many symmetric binary relations are there?

[rigid heart]

Hi guys. Is there a better way to solve this problem, or is my solution even correct at all? I tried assigning one of the people who are to be kept separate into one of the rooms first and then choosing the rest as normal, and then summed the combinations for each room.

[muted gate]

on what sets and under what conditions

did the problem give you any extra information

[dense glade]

no just in general

how to derive the formula for it

[muted gate]

hm

I don't know

for me it would need to at least define the binary operator

[pale epoch]

say you have a relation on a set with cardinality n
you can think of it as a nxn matrix with entries in {0, 1}
now as the relation is symmetric, this matrix ix uniquely determined by the diagonal as well as (wlog) all entries above the diagonal

[crisp pumice]

Show that any NxM undirected grid where both N and M are odd is not Hamiltonian.

I'm thinking you can find a Hamiltonian cycle for a grid by starting at 0,0; going down to 0,n-1; then to 1,n-1; then to 1,1; then to 2,1, etc.

but if M is odd then you can't get back to the top row and connect back to 0,0

idk how to phrase this formally tho

[rich tiger]

Hey everyone ;-; im struggling so much with discrete math and i have an exam coming up. I dont know what to do im watching lectures and yt vids and not understanding ;-:

[hard citrus]

No, first change the implication to a disjunction, then apply DeMorgan's law with the negation in front of the

[wicked basin]

i know its pigeon hole principle

but how to apply it

[obtuse lance]

I would assume they all have a different number of acquaintances and show this leads to a contradiction

[severe swan]

How can I calculate this?

A fair coin is flipped 8 times.

What is the probability that the first two flips are Heads and the last two flips are Tails?

H H HT HT HT HT T T

2H first two flips
2T last two flips
4 HT middle flips

The total number of flips is 2^8.

x/2^8 How do I solve for what x is?

[unreal stump]

This feels like a graph problem than a pigeonhole one

[proven silo]

The middle flips doesn’t matter so just ignore those

[muted gate]

what is supposed to be the symmetric closure of $R = {(a, b) | , a \mid b }$ I know it's $R \cup R^{-1} = {(a, b) | a \mid b } \cup {(b, a) |, b \mid a }$

but I can't understand what does this union really means

[vital dew]

texaspb

[muted gate]

oh

it's just the same thing but with an or added

-_-

${(a, b)| a \mid b \lor b \mid a }$

[vital dew]

texaspb

[dense glade]

what is the the number of binary operations that have an identity?
I'm so lost with this one

[lucid marsh]

x3+y3+z3=k

How do I do this?

[muted gate]

can you provide us with some more details on what may be your problem

is the exercise asking for the numbers of solutions?

[craggy juniper]

if you mean exponents write them as exponents, also we don’t know what you want

[mental pecan]

Why are there 3 such thats

In this set

[muted gate]

it's supposed to be that symbol

for divisible

lol

[craggy juniper]

: superiority

[mental pecan]

Indeed

[muted gate]

${(a, b)| a:b \lor b: a }$

[vital dew]

texaspb

[muted gate]

yeah

[craggy juniper]

[muted gate]

I guess

it looks better

[craggy juniper]

you changed the wrong thing

the first | is what i meant

[muted gate]

ooh ok

[mental pecan]

I have this super nice set command on my computer

I’ll send it here once I’m home

[muted gate]

ok

[weary tiger]

when you do strong induction

are you trying to show k? or k+1

and I don't understand why you need multiple induction hypotheses

[muted gate]

you're trying to show that $P(k) \rightarrow P(k + 1)$

[vital dew]

texaspb

[muted gate]

P(k) being the statement you're trying to prove

you have to prove this implication, and then your inductive hypothesis is assuming that P(k) is true

[weary tiger]

hm

ok

[muted gate]

what do you mean by multiple induction hypotheses btw?

[craggy juniper]

this is regular induction

[muted gate]

oh

true

I misread it my bad

[weary tiger]

xd

[muted gate]

when it's strong induction you're trying to prove a few cases of your proposition

so like $P(1) \land P(2) \land P(3) \land \cdots \land P(k) \rightarrow P(k + 1)$

[vital dew]

texaspb

[muted gate]

if i'm not mistaken this is what you have to try to prove

[weary tiger]

I don't get why the induction hypos use k-1 k-2 k-3

for the subscripts

[craggy juniper]

you could get this from a google search

[muted gate]

that is because

you are already assuming that P(1), P(2) and P(3) hold their truth

[weary tiger]

so are you proving p(k+1) or p(k) then?

im like 100% comfortable with induction so far

[craggy juniper]

it explicitly says “to prove p(k+1)”

[weary tiger]

but like the hw I just did was showing k

and my prof gave me full credit

for example

[craggy juniper]

if you assume p(1),…,p(k) are true, then p(k) is automatically true by assumption

[muted gate]

P(k - 1), P(k - 2), P(k - 3) are just like previous statements you assumed to be true

[craggy juniper]

are you sure you’re properly putting your thoughts into words?

maybe show us the proof you did

since that’s where your question originated from

[weary tiger]

okay

[mental pecan]

\DeclarePairedDelimiterX\set[1]\lbrace\rbrace{\def\given{\;\delimsize\vert\;}#1}

then you use this like this

[vital dew]

Brontochad (RYC4blushysully)

[old bison]

I need help understanding how to do this problem

[coral parcel]

What I'd do first is notice that p³+3p²-p-3 = (p+3)(p²-1).

Not sure what to make of the first hint, though.

[vale cairn]

Note that that further factorises as (p+3)(p+1)(p-1). Which numbers can we multiply that by to get the product of 5 numbers in a row?

[old bison]

p and p+2?

[vale cairn]

Indeed. So you can consider what we know about p and p+2 and the hint.

[weary tiger]

If a coin is flipped 4 times how would you count the amount of outcomes with atleast 2 consecutive heads ?

[balmy jay]

The number of outcomes with at least 2 consecutive heads is the number of total outcomes - the number of outcomes with no consecutive heads

[old bison]

ok so 2^4 = 16 and for consecutive we do 4 pick two and that gives us 6 outcomes with at least two consecutive heads

not sure how this helps though 🙃

[balmy jay]

To find the number of outcomes without consecutive heads, I think you can split it up into cases based on how many heads you have in your outcome, so 0 heads, 1 head, 2 heads. Can't do 3 heads or 4 heads since those will force you to have 2 heads that are consecutive

[weary tiger]

If you have a case with 2 heads there’s a possibility of it being consecutive tho?

[weary tiger]

That’s not correct

Consecutive of 2 heads is 8

In a flip of 4 coins

My problem is trying to derive 8 without writing out every favorable outcome for that event

I thought it would be the inclusion exclusion principle but that doesn’t help either as I come up with 7

[balmy jay]

You just count the number of outcomes where 2 heads aren't consecutive

[weary tiger]

Alright how would you derive that tho

[balmy jay]

I got 3 for that case and 8 for the total number of outcomes that don't have 2 consecutive heads

For that case, I did the total number of outcomes with 2 heads - number of outcomes with 2 heads being consecutive

The first term is 4 choose 2 = 6 since you pick where your 2 heads will go and the second term is 3 since you can just think of all the cases where you have 2 consecutive heads

[weary tiger]

Right that’s what I’m trying to avoid or atleast find out

[balmy jay]

What do you mean

[weary tiger]

You can just think of all the cases where you have 2 consecutive heads

You’re right you could but if we scale up the number to 4000 flips and 327 consecutive flips of heads

So I am trying to figure out if there’s a technique

[spring zephyr]

Can anyone please verify my solution

[inland rose]

any discreet math textbooks for beginners ?

[young summit]

Discrete Math and its Applications by Rosen is pretty good

[frosty bay]

{X ⊆ P({1,2,3}) | 2 ∈ X}
This is an empty set, right?

[inland rose]

k @young summit

[stray reef]

no

er

wait

yes. it is

assuming it really is as written

[frosty bay]

Yeah, if it was ∈ instead of ⊆ it'd be non-empty

right?

[stray reef]

yes

[muted gate]

what is another name for Turan's Theorem (graph theory)?

[weary tiger]

I have a combinatoric question I can't really understand:
How many different passwords can U have by changing the latter arrangement in the password: "tennessee1224" when U wouldn't have two numbers together

So tenne1s2s2e4e

is fine?

do I understand it correct?

[rough merlin]

Yes that sounds right

[weary tiger]

tnx

I find it hard to read and understand combinatorics question

and I don't know why

So here all I need to do is the complemenry right? to find the ones with two or more digits in a row and subtract from everything

is there an easier way?

[frosty haven]

Can anyone guide me for ans 5

Im not getting the approach

[austere cedar]

yes. Look at it in the following way: First you check for each position in the password, whether there is a letter or a number. So you can calculate the number of options you have for the positions of the four numbers (not caring about the fact that they are different). Now when it is already predetermined what the number positions are, you can calculate the possibilities to write the numbers in these positions and the possibilities to write the letters in the other positions.

[weary tiger]

oh

nice

tnx

[weary tiger]

wait

what about

1te2n2e4ssee

you have 1te2

so in that position

you have 10 possible places

[mild temple]

@sand adder I'm writing in reponse to your message. #help-18 message
you're right that the use of dots lacks formality, and induction is needed at some point (since the Peano arithmetic is built up on induction). with due respect, i share the subjective opion in the linked answer on Math.SE that using well-known properties like $$\sum_{i=1}^{n} x_i = \sum_{i=1}^{n} x_{n+1-i}$$ (that are proved by induction) doesn't provide "a novel argument", so I won't call it an inductive proof.
i believe that math/phy/engineering student shld b able to formalize the idea from the diagram with dots to something less educational to beginners but more formal that encapsulates induction:

[vital dew]

vin100

[mild temple]

,, \begin{aligned}
&\phantom{=} x^n - y^n \
&= x^n - y^n + \sum_{i=1}^{n-1} (x^i y^{n-i} - x^i y^{n-i}) \
&= x^n + \left(\sum_{i=1}^{n-1} x^i y^{n-i}\right) - \left(\sum_{i=1}^{n-1} x^i y^{n-i}\right) - y^n \
&= \left(\sum_{i=1}^{n} x^i y^{n-i}\right) - \left(\sum_{i=0}^{n-1} x^i y^{n-i}\right) \
&= x \left(\sum_{i=0}^{n-1} x^i y^{n-1-i}\right) - y\left(\sum_{i=0}^{n-1} x^i y^{n-1-i}\right) \
&= (x-y) \left(\sum_{i=0}^{n-1} x^i y^{n-1-i}\right)
\end{aligned}

[vital dew]

vin100

[mild temple]

@weary tiger I'm writing in response to your question that I didn't respond to yesterday, because I was thinking about @sterile adderx's remarks. As another user pointed out, you've got the main idea. However, I suggest replacing the ... with a summation sign so as to make things precise and formal. The above is an example. For tests and exams, if you're spoon-fed a closed form of the general formula for n, induction does simplify the calculations, but IMHO, it's more education to observe the first few cases and try to guess and generalize what would happen, as maths is a subject that studies patterns in a generalized way.

[mild temple]

\begin{align}
&\phantom{=} x^{n+1} - y^{n+1} \
&= x (x^n - y^n) + xy^n - y^{n+1} \
&= x (x - y) \left(\sum_{i=0}^{n-1} x^i y^{n-1-i} \right) + y^n (x - y) \tag{induction hypothesis} \
&= (x-y) \left(\sum_{i=0}^{n-1} x^{i+1} y^{n-1-i}\right)+ y^n (x - y) \
&= (x-y) \left(\sum_{i=1}^{n} x^{i} y^{n-i}\right) + (x - y) y^n \
&= (x-y) \left(\sum_{i=0}^{n} x^{i} y^{n-i}\right)
\end{align}

[vital dew]

vin100

[mild temple]

line (3) can be skipped. i included that just for clarity. the advantage of using induction is that you're already "provided" a factor $x-y$, and you only need to add/subtract some term(s) to balance things out.

[vital dew]

vin100

[mild temple]

however, this skill of creating telescoping sums with two columns

$$\begin{array}{rr}
x^n & -x^{n-1}y \
x^{n-1}y & -x^{n-2}y^2 \
\dots & \
x^2 y^{n-2} & -xy^{n-1} \
x y^{n-1} & -y^n
\end{array}$$

[vital dew]

vin100

[mild temple]

is useful for some simple recurrence relations

,tex somethings questions can be ``find the general term of $a_n$''

[vital dew]

vin100

[weary tiger]

@mild temple This is interesting but I haven't learnt about sums (Sigma) yet so I don't really know what's happening. But are you saying my proof was not sufficient? And x^n-y^n has to be solved by induction?

[mild temple]

in terms of $n$ without a function of $n$ given, contrary to usual induction questions.

[vital dew]

vin100

[mild temple]

i think using dots suffices, but i think my teacher would appreciate you using summation sign $\Sigma$, provided that you use that correctly. i say "i think" as you haven't learnt the symbol $\Sigma$ for summation.

[vital dew]

vin100

[mild temple]

and that's my personal opinion. i suggest that you clarify that with your teacher/grader if marks are important for you. they're there to answer your questions.

summation sign is just a symbol

to formalize $a_1 + a_2 + \dots + a_n$

[vital dew]

vin100

[mild temple]

take $n = 2^{10} = 1024$

[vital dew]

vin100

[mild temple]

for me, writing $a_1+a_2+\dots+a_{1024}$ means adding 1024 terms

[vital dew]

vin100

[weary tiger]

Since summation appears later in the book, I am pretty sure I'm allowed to do without it

[weary tiger]

Seems good, no?

[mild temple]

but for some that might be $$a_1+a_2+a_4+a_8+a_{16}+a_{32}+a_{64}+a_{128}+a_{256}+a_{512}+a_{1024}$$

[vital dew]

vin100

[mild temple]

that creates ambiguity

with summation sign things would be clear

[weary tiger]

When you write a_1 ... etc you are saying that you are adding a sum in this. order

$$a_1+a_2+a_4+a8+a{16}+a{32}+a{64}+a{128}+a{256}+a{512}+a{1024}$$

[mild temple]

the former is $$\sum_{i=1}^{2^{10}} a_i;$$

[vital dew]

deg

[weary tiger]

This is not even math

[vital dew]

vin100

[weary tiger]

they have to be indexed in order, and last one, should indicate its the last element and its spot in the index @mild temple

[mild temple]

the later is $$\sum_{i=0}^{10} a_{2^i}.$$

[vital dew]

vin100

[weary tiger]

If it doesn't you can't write a_1 + a_2 + ... +a_1023 + a_1024

Every single a_i must be 2 < i < 1024 in these dots

Otherwise you can't write it

So I don't understand how its a problem

[mild temple]

the problem is that you have so many integer sequences: https://oeis.org/

that simply writing out the first few terms don't suffice, in general. that's why writing summation sign is much clearer

[weary tiger]

Yeah, we have index in both the exponent (n-1) etc and every x can be indexed x_2 for this one

[weary tiger]

It does lol

You think N = {0, 1, 2, ...} is not valid?

You know that it's natural numbers

[unreal stump]

No?

[weary tiger]

IT doesn't go N = {0, 1, 2, 6, 8, 7, 1}

[unreal stump]

It could be anything

[weary tiger]

Are you high?

[mild temple]

just search the OEIS

[weary tiger]

Three dots indicate the sequence continues in the same pattern

[mild temple]

database

to see

the possible sequences

[weary tiger]

What

[unreal stump]

What if it's {0,1,2,3,0,1,2,3} and so on

[mild temple]

https://oeis.org/

[weary tiger]

that's just absolutely wrong in so many ways

[unreal stump]

I can think of a million patterns starting with 0,1,2,3

[unreal stump]

Tell that to a 2 bit counter

[weary tiger]

Then if the pattern breaks at some point you have to clarify it

[unreal stump]

If you are explaining this to someone this is fine

When writing a proper proof this is bad

[weary tiger]

idk what this is

Are you fcking kidding me

Z = {... -4, -3, -2, -1, 0, 1, 2, 3, 4, ...} can be said instead of summation symbol from -inf to pos infinity

If the pattern breaks at some point you don't write " ... "

[unreal stump]

Well,Those are notational things

[weary tiger]

If you are told S = {x^2 : x in N} you can also say S = {0, 1, 4, 9, ...}

And its not wrong

[safe galleon]

what?

deg please behave

also, preferably post in channels where you understand what's going on

[weary tiger]

It's a perfectly valid notation that indicates the pattern continues till infinity

If it doesn't, then you can be more formal

But for x^2 why when would the pattern break?

Is 2^2 going to become 7 all of the sudden?

Like cmon

[unreal stump]

Ok Granted I use that notation at tines

Because I don't like to do the latex

[weary tiger]

I was pinged here 8 times by @mild temple and we're discussing this topic

What is this mod coming with 0 context

[safe galleon]

i received complaints about you in modmail, that's the context

take it easy

[weary tiger]

lmfao

[unreal stump]

Ok, What's the point exactly? I think I am missing it

[weary tiger]

np ill just block and you continue discussing gl

[unreal stump]

The ... terminology is better as an intuitive shorthand

[weary tiger]

wont be able to see your pings vin.

[unreal stump]

But for formal manipulation,other notations are simply superior

Say you want to find intersection of {a^3| a in Z } and {a^2 | a in Z}

[mild temple]

thanks for intervening. i started the discussion in response to a help channel that's covered up with newer questions, and i'm not sure whether i understand "post in channels" correctly. my delayed response to a closed question should go to general discussion channels like #serious-discussion and #math-discussion ?

[unreal stump]

That would be {a^6 | a in Z} by manipulation

[safe galleon]

for now you can just go ahead here, since blue bye is already helping you

[mild temple]

i'm asking for the next time. i would love to add some comments later on, since i often see sth (intuition, inspiration, visualization, etc) beyond logic and rigor (after the question in the math help channel gets closed), and i'd like to put that forward.

to share it somewhere. on which channel would that be appropriate?

[safe galleon]

hmm if you were asking a question, the channel has already closed, and you still need help, you can open a new help channel. if you were helping someone else, you can try using discussion or math discussion, yes.

[mild temple]

i'm using the reply functionality as we have multiple users here

if you search 0,1,2 on OEIS, you'll find lots of integer sequences:
https://oeis.org/search?q=0%2C1%2C2&language=english&go=Search

[weary tiger]

When solving At least problems, and doing so by the complement. The Complement of At least 1 is 0 of what ever element... Would the complement for At least 2 be 0 of the element as well?

Or would the complement be At most 1

[vital dew]

Zara

Zara

[vital dew]

Zara

[onyx hull]

Hi guys, could someone help me break down this notation?.. I'm trying to determine which properties this binary relation has
R1 = { (a, b) ∈Z^2 | a = bn, n ∈Z }
Is this saying aRb if a = bn?

Can R1 have more than one input? or in this case is the 1 next to the R, n?

[pale epoch]

we dont know

its incomplete as you stated it

there is probably some "there exists" missing though

and the n can be any integer

[onyx hull]

Cool 😄 , so.. if (a,b) are Z^2.. are the domain and co-domain all the numbers of Z^2? The same set so to speak?

[pale epoch]

uh, the 'domain' and 'codomain' are both Z

i write '' because this isnt a function and im not sure if you use those terms for relations that arent functions

also you probably know this relation

||a is related to b iff a divides b (which is written a|b usually)||

[onyx hull]

I see, oops. Up until now we have only really used , denote all living people as a set..
But I see the set Z^2 is {0,1,4,16,25..} , I am still confused about n ∈ Z, I assume I try n = 1, 2, 3, 4, ect ?

[weary tiger]

This reads:
If for all x in R, ax <=a
for all x in R, if ax <= a

"There exists" has a symbol of its own ∃

[analog grail]

Oh sorry I miss interpreted the pic

[weary tiger]

But in general you don't have to say for all x in R, x in R is enough

[analog grail]

what i meant to ask if the 2 are same?

[weary tiger]

No

[analog grail]

Can you please explain me how
Cant seem to make a difference between them

[lyric solar]

It's saying if for all $x$ in $\mathbb{R}$, $x \leq a/a \rightarrow x \leq 1.$ The next statement says choose for all $x$ in $\mathbb{R}$ where $x \leq 1.$

[vital dew]

Doveswan

[weary tiger]

One is asking "If x is a real number, ax <= a"
Other is "for all x in R, if ax <=a"

[analog grail]

That makes sense thanks

[lyric solar]

The first one is an incomplete statement, basically.

[weary tiger]

its weird notation

[lyric solar]

If $x$ is a real number, then scaling that real number by another other number is less than that other number. What a strange statement.

[vital dew]

Doveswan

[lyric solar]

The second one is clearer in that for all real numbers, choose those that are less than $1.$

[vital dew]

Doveswan

[weary tiger]

syntax error

not you dove

whoever wrote that thing

[hard citrus]

Assuming a is positive

[lyric solar]

Don't even need to assume that

Unless you assume the first statement is a finished statement

[hard citrus]

I meant for the second one about

[weary tiger]

What is the set that contains every number, infinities, etc

does infinity contain sqrt(-1)?

[unreal stump]

There is no such set

[viral crown]

not in the reals

[unreal stump]

Infinity is usually just a shorthand for "arbitrarily large or small"

[viral crown]

and there's no set that contains "infinities"

[unreal stump]

Although there are things like wheel theory,those are no mainstream

[viral crown]

since infinity isn't a number

[viral crown]

or, well, for a traditional definition of set

im sure there're some axioms that let you

[weary tiger]

so inf only exists on the real number line?

isnt there a complex number infinity that goes up and down the complex plane?

[severe swan]

How can I caclulate this? Can someone explain how to solve this?
There are 45 tickets, each one has a digit between 1 and 9 on it and each has a letter A, B, C, D, or E on it. Here is a table of all the tickets:

 1    2    3    4    5    6    7    8    9

A A1 A2 A3 A4 A5 A6 A7 A8 A9
B B1 B2 B3 B4 B5 B6 B7 B8 B9
C C1 C2 C3 C4 C5 C6 C7 C8 C9
D D1 D2 D3 D4 D5 D6 D7 D8 D9
E E1 E2 E3 E4 E5 E6 E7 E8 E9

You pick three tickets at random. What it the probability that all of them have the number 6? 5 of the 45 tickets have a 6 on them but I don't know how this is information is supposed to help me solve the problem.

A) 9 / 45
B) 3 / C(45,3)
C) 10 / C(45,3)
D) C(9, 3) / C(45,3)
E) None of the above is correct.

[vital spruce]

Any good online resources for learning discrete math?

[onyx hull]

TrevTutor on youtube is quite good

For basic stuff

[vital spruce]

Thanks

[onyx hull]

There's also a book my uni used.. "Garnier_Rowan__Taylor_John_-_Discrete_Mathematics___Proofs_Structures_and_Applications_Third_Edition"

I think there's a free PDF download somewhere

It's quite good, has exercises for every topic and also solutions at the back

[vital spruce]

Thanks alot!

[mental pecan]

There is

Infinity is not a number though, so it’s not included in the set of real numbers

Similar for complex infinity

[floral field]

I am doing a problem that asks me to find all the non-isomorphic trees on 6 vertices. I think I found all 6 of them.

I was wondering how I would argue that I indeed found all of them and that they're all non-isomorphic to eachother

[unreal stump]

The 2nd graph is 5 vertices

@floral field I would do it recursively

Find all non isomorphic graphs on 5 verticrs

Add an extra vertex

[floral field]

Oh oops

[floral field]

For arguing that all 6 are non isomorphic to eachother?

[unreal stump]

Well,For exhausting all cased

[floral field]

Yeah, I think I'm able to find them, but I'm just having trouble rigorously arguing that this is all of them and that they are all non isomorphic to eachother

[unreal stump]

Are you sure this is the exhaustive list?

Check for degrees of each vertex

Related question: Why can't you show 2 graphs are non isomorphic using a variant of DFS or BFS?

[floral field]

whats BFS/DFS

Fixed list

[unreal stump]

Breadth First Search/Depth First search

The algorithm in my mind is you start with 2 vertices(one from graph 1 and one from graph 2) of equal degree

And then match degrees of adjacent vertices

Repeat till a matching is not possible or all vertices are matched

Granted the time complexity is horrible because you have to backtrack and start over if your vertex match fails

[floral field]

Oh yeah, I can do it for 2 graphs. List out the degrees of each vertices for two graphs, and then try to play a matching game

[obtuse lance]

a weird way that might work is to use Cayley's formula, there are n^(n-2) labeled trees on n vertices, then do a counting argument to fill out all these 😬

[oak notch]

Hey guys, what does "belongs to exactly one of A and B" mean?

[obtuse lance]

it means it's only in one and not the other

[unreal stump]

I think BFS/DFS is a useful tactic while counting stuff in graphs

Mostly to ensure you don't accidentally mess up counting

[obtuse lance]

so 3 is in A or it's in B, but not in both

[oak notch]

Got it, thanks!

[obtuse lance]

you're welcome

[ebon atlas]

hey everyone, can i ask a question about finite state automata and minimization of DFA here?

[obtuse lance]

sure

[ebon atlas]

great, one sec, ill get the screenshot

i'm new to Finite state automata and I'm no expert at math, I was doing a DFA minimization and after doing it i checked my answer on a random DFA minimizer website, to see whether i did it correctly or not, my result is right but there is one difference, the result on the web shows only 1 final state on the minimized DFA, and that's my question, why does the web result show 1 final state only when initially it had 2 final states, am i the wrong one or is it the website?

[unreal stump]

You can have 2 final states to be equivalent

[ebon atlas]

so q3 and q4 can still be the final states right?

[unreal stump]

Actually that's a mistake

It should be a final state

[ebon atlas]

i see, thanks man, i was confused by the website, since im not too confident at my FSA knowledge i thought i was the wrong one

[floral field]

There should be n! trees on n vertices, where any vertex has degree at most 2 right?

So then up to isomorphism, there's only 1

I thought it was n^{n-2}

Total trees on n vertices

[unreal stump]

Actually ignore this

[floral field]

So you're saying this is a false claim?

[unreal stump]

All trees of that form will just be a "straight line"

So it's just permuting the set of vertices so n! Is fine

[floral field]

Yeah, I noticed that in examples, but I couldn't thing of a rigorous reason lol

how would one even prove that

[unreal stump]

If you want a rigorous proof consider the construction of such a tree.

Our claim is that permutating the set of vertices and putting them one after the other in the order they appear in the sequence would cover everything

So {1,4,3,2} would correspond to
1-4-3-2

Start 1 end 2

Let's say at some stage of construction you end up with

a_1 - a_2 - a_3...a_k

And you have to add a_{k+1}. Assume till this stage our claim has been correct (i.e.,our current tree corresponds to a permutation on {a_1,a_2...a_k})

a_{k+1} has to be added either at the beginning or the end(because degree of vertex)

Which in both cases is some permutation of {a_1,a_2...a_k , a_{k+1}}

[floral field]

So

Consider a1-a2-...-ak. Permuting the vertices still gives us a tree where each vertex has degree at most 2. What does adding a{k+1} do?

[unreal stump]

Yea

I guess this is what you would call invariant property?

[floral field]

And also, how do we know that the permutations of a1-a2-...ak give us ALL of the trees that satisfy that condition?

[unreal stump]

Well you have to go through a step by step addition

At each step this property holds

For example a_1 is the only tree with 1 vertex

a_1-a_2 or a_2-a_1(which can be renamed as b_1-b-2 or whatever) is forced

So if you were to construct a tree which satisfies that you have to go through these steps of construction in which each and every step has that property holds true

I guess one element is the base case?

[floral field]

So some kind of induction argument

[unreal stump]

Yea

[floral field]

Thank you. I'm going to play around with examples and then come back later today to ask more questions

[unreal stump]

What's the difference between regular induction and "structural" induction

[floral field]

I'm not sure. I've only had encounter with normal induction

[limpid fossil]

is this better done with contradiction or can we do a direct proof too?

[stray reef]

well the contradiction proof is simple

with only one weighing there are only 3 possible results, which is not enough to distinguish between 2n = 6 possibilities (which coin it is, times whether it's heavier or lighter)

[limpid fossil]

yeah that makes sense

they also asked about n = 4, where the scale must be used at least 3 times

[stray reef]

hm

my argument alone won't cut it then

well ok like, for your first weighing you really have two choices: weigh one coin on each cup or two coins on each cup, and before you know anything about the coins it does not really matter which ones go on the scale

maybe some case analysis would do it

[limpid fossil]

if we weigh one coin on eachside of the balance scale, then either the balance scale is balanced or its tipped over to one side

if its balanced its possible one of the coins is the new coin, but it may also not be

if its tipped then one of them has to be the new coin

[stray reef]

wait is it tho

if two coins weigh equal can either of them be fake

[limpid fossil]

if im reading this correctly

and all the n - 1 coins by assumption have the same weight

[stray reef]

the n-1 genuine ones do

the fake has a different weight from them

[limpid fossil]

yeah

in the case that its the same weight though, i think pairwise comparison works?

[floral field]

So I'm trying to prove that in any tree, any two longest paths cross eachother via contradiction.

If I have paths v1-v2-...-vk and u1-u2-...-uk in G of maximal length k that do not cross eachother, how would I get out the contradiction?

[floral field]

maybe something about trees being connected?

[obtuse lance]

hmm, if they don't cross each other then there's a (unique) path between the paths in the tree connecting them, so worst case scenario is it joins them in the middle, and we get a larger path, contradicting maximality

[floral field]

So theres some path connecting some point in the first and second path?

[floral field]

Ahh. I see

[obtuse lance]

nice I didn't know this, thanks

[muted gate]

my brain died with this

can somebody help

is this even possible?

at all

[onyx hull]

Hi guys, given set A = {5,6,7,8,9}, B = {3,4,5,6}, {X | X ⊆ B, X and A are disjoint}
Is X just {3,4} ?

[weary tiger]

No

What about {3}?

[onyx hull]

So all possible sets inside B , ignoring A?

[weary tiger]

Yep

wait

[onyx hull]

Would the empty set be considered? Or only when we look at the Power set?

[weary tiger]

the set u gave is a set of sets

you should write it as {{3},...}

[onyx hull]

When computing sets of sets like that, do we ignore the empty set?

[weary tiger]

No

Consider the set A={1}

then P(A)={{}, {1}}

since the empty set is a subset of every set

[onyx hull]

ah ok 🙂

ty fren

[floral field]

Say we have a tree, where no vertex has degree more than 3. Also, assume that at least one vertext has degree 3. I'm having trouble proving that the number of vertices with degree 1 is two more than the number of vertices with degree 3.

I'm thinking it has something to do with the number of leaves, but I'm not sure how to argue it

[severe swan]

Can someone explain how to get to this answer?

A bit-string (either 1 or 0) of length 5 is generated randomly (each bit-string is equally likely to be generated). What is the probability that the bit-string generated has no 1s next to each other and no 0s next to each other?

For example the bit string "10010" would not be acceptable because it has two 0s next to each other.

Answer: 1/2^4

[balmy jay]

I think it's cause there are a total of 2^5 bit strings and out of these, there are only 2 (10101 and 01010) that satisfy your conditions. So the probability you pick these 2 is just 2/2^5 = 1/2^4

[dense glade]

can someone explain what is (BxB)nR? because my brain is melting

what is the relation here?

[onyx hull]

Hi friends , I'm looking at
{ (X, Y ) ∈P(A)^2 | X ⊂ Y }
when considering the reflexive property, X ⊂ X cannot be true is that right? as ⊂ implies it is a proper subset?

[weary tiger]

Yes that is right

[dire obsidian]

Is there more lemmas for set proofs other than these two?

[limpid fossil]

wheres the 1/10 from: arent there less than 10 nodes

[stray reef]

1/5 each for node 7 and node 15, and the other 3/5 are spread equally over the 6 remaining nodes

[limpid fossil]

oh i was messing it up. i was spreading 4/5 equally over the 6 remaining nodes but didnt realize it should have been 3/5 spreading

thanks!

[sand smelt]

does someone knows how to solve this problem?

[weary tiger]

20 is not in that range fam@sand smelt

[sand smelt]

how do i find it?

[proven silo]

Find prime factorization of 24

Then inclusion exclusion

[tall oxide]

whats the A₁ in here?????

[stray reef]

$A_1$ appears to be the set of all integers less than or equal to 1.

and it appears that your answer to (i) is correct but the answer to (ii) is not

[tall oxide]

how can I know that? it's too confusing for me.

[stray reef]

well the definition of A_i can be rewritten as A_i := {n in Z | n ≤ i}

[tall oxide]

so, ii. is {a in Z | -inf<a ≤1}?

I'm kind of wondering whether A1 is {0} A2 is {-1,0,1}

[stray reef]

no

[stray reef]

you can write -∞ < a but it's redundant

[stray reef]

no, A1 is not {0} and A2 is not {-1, 0, 1}

[languid citrus]

can someone help me with this?

<@&286206848099549185>

[coral parcel]

The definition of "equivalence relation" has several parts. Which of them do you have trouble showing?

[languid citrus]

symmetric and transitivity

in letter b. Am i going to list all the elements of power set P(Z)? and what does / means?

[coral parcel]

When R is an equivalence relation on a set X, the notation X/R means the set of equivalence classes.

[languid citrus]

if |A|= |B| then |B|=|A| is this symetric?

[coral parcel]

That's what it means for your relation to be symmetric, yes.

[languid citrus]

so is this enough proof to show that the relation S is symetric?

complete?

[coral parcel]

That ought to be enough, yes.

[languid citrus]

how about the distinct elements of P(Z)/S?

is this (a,a) (a,b) (a,c) (a,d), (b,b) , and so on.....

[dense glade]

what is the class of [x] under equivalence relation? I really not getting the idea does anyone have an idea how it works?

[unreal stump]

Under what equivalence relation?

[sand smelt]

help

[tall oxide]

My instructor said it is neither of our answers. So I think the A1 is -inf?

[stray reef]

you deleted the original problem statement

did you do that deliberately?

i mean you could probably try to translate that into Coq or something and it'd do it for you

i would try to rewrite the conditions a little

{|A| + x : x ∈ {1,3,5,6,8}, A ⊆ {1,3,8}, x ∈ A, x is odd}

there's some redundancy here

x cannot be 5 if it is to belong to A, and x cannot be 6 or 8 if it is to be odd

so we can write this set as {|A| + x : x ∈ {1,3}, A ⊆ {1,3,8}, x ∈ A}

for x=1, the possible things A could be are {1}, {1,3}, {1,8} and {1,3,8}, so we get elements 2, 3, 3 (again) and 4 in our set
for x=3, A can be {3}, {3,1}, {3,8} and {3,1,8}, so we get elements 4, 5, 5 (again) and 6 in our set

thus {2,3,4,5,6}

is this what you were looking for?

or are you specifically posting about your own frustration about the lack of automation for things like this?

plus if you put more complicated logical formulas in your set you can formulate set descriptions that could not be evaluated without proving an open problem

such as: {Re(s) | zeta(s) = 0}

if a universal set parsing procedure existed we could have it solve the riemann hypothesis by feeding it this input and seeing if the output is {1/2} or something different

[idle hazel]

umm is this subject important? im in 12th grade but my teacher gifted me a discrete math book by susanne s. epp

its not that i dont understand its just stuff ive been using all along

[idle hazel]

and its thicc AF so idk if i should go through all of it

well im just at chapter 1 maybe something super mindblowing will appear later

she told me to make sure i get it done because its an important foundation

[coral parcel]

There are programming languages whose notations come fairly close to this. However the question sounds like you're misunderstanding the purpose of your exercise. It's not like anyone needs a list of those sets, it's just an exercise to make sure you've understood what the notation means. The real purpose of the notation is not to be able to write down tasks to be done, but to give us an abbreviated way to speak about sets without writing down their elements exactly.

[coral parcel]

Is it you alone the teacher gave the book to, or everybody in the class?

[idle hazel]

just me

she asked me to go to the teachers hall or whatever you call it in english

and she gave me it

its a BIIIG book

[coral parcel]

I think my points hold in general.

[coral parcel]

Typically this would be a sign that you're doing so well with the standard curriculum that she's afraid you'll be bored unless you get something more challenging.

[idle hazel]

well she also signed me up for a contest

its next month

[coral parcel]

Sounds good!

[idle hazel]

its not that hard

anyways im gonna try and go through the book

see what i understand

[coral parcel]

As long as you're reasonably sure what the chapter says is old hat to you, you can go through it fairly quickly; you don't have to waste your time on check exercises you don't need.

[idle hazel]

im on ch1: speaking mathematically
i never knew functions were actually relations like this so im just trying making the connection

"trying making"

bruh

i have C2 Proficiency and make mistakes like this

[coral parcel]

Right. That's the sort of thing you wouldn't normally learn in grade 12.

[idle hazel]

ive never actually studied math before so its pretty hard

i basically BTFOd highschool with just what i saw in class

so basically up to calc 1

i did this

https://tenor.com/view/stomp-gif-17874349

[coral parcel]

That's a problem many intelligent kids have, and then they hit a brick wall in university when they need to study. Kudos to your teacher for noticing and giving you a chance to make better habits.

[idle hazel]

she actually told me that

that i need to get used to studying

or i will have a hard time adjusting

i appreciate that she cares tho

[coral parcel]

Anyway, the point of representing functions as sets (in this case, as relations) is to make it explicit in the definitions that the only thing that defines a function is which outputs go with which inputs -- in particular that it's the same function no matter how we describe that connection, as long as the black-box result is the same.

So, for example, it doesn't make sense to ask "is this function defined piecewise?" because that's a property of the definition, not of the function itself.

[idle hazel]

ah i get it

its kinda fun

[coral parcel]

[idle hazel]

its such a transition

from native language to english

when studying math

i adapted but its just so different

[coral parcel]

Good luck!

Unifying functions with relations is really more of a mathematical parlor trick. The formal mechanisms of the two concepts are so close that it would be a waste not to use the same words and definitions for them. But I can't think of any places where we get any deep results out of "functions are a special case of relations".

[unreal stump]

Ok, Here's a simple result based on that. How many equivalence relations are there on a set A that also happen to be functions?

[idle hazel]

so you mean A is the domain and codomain?

[unreal stump]

Yea

[idle hazel]

well then AFAIK every x has to have a value f(x) thats also in A

[coral parcel]

(Have you gotten to the concept of "equivalence relation" at all yet?)

[idle hazel]

ive never heard of it

lol

[unreal stump]

Oh mb

[idle hazel]

sorry to disappoint

[coral parcel]

It ought to come fairly soon in the book, but all in good time.

[idle hazel]

im not rushing better to assimilate as much as possible

[coral parcel]

Anyway, I don't think I'd consider this to be an example of how we get a result out of treating functions and relations together. The answer is "exactly one". So it is more an illustration of how small the practical overlap between those concepts is.

[unreal stump]

Ok,That example was forced

In reality,do you ever care about relations that are not order relations or equivalence relations?

[coral parcel]

At some point you start calling them directed graphs instead. 😛

Also, set theory makes a big deal out of this weird "∈" relation which is neither an order nor an equivalence relation.

[coral parcel]

Less facetiously: "is a normal subgroup of" is an important relation in abstract algebra that is not transitive.

[unreal stump]

But what does thinking of normal subgroups as relations give you

[idle hazel]

welp

[coral parcel]

As a matter of practical usage, it is \emph{spoken of} with the same grammar as other relations. It's sometimes notated symbolically as e.g. $H\triangleleft G$ which matches how other relations are notated. So we need an explicit concept of relations at least such that we can \emph{state} the warning that this one is \emph{not} transitive.
It's true that there are not really any relevant theorem saying "for every relation R it holds that ..." but there's pragmatic value in just \emph{classifying} the things that we use the relation syntax for.

[spring surge]

is there such thing as negative element in a set?

{ !a } & { a } = empty set

[vital dew]

Troposphere

[coral parcel]

No -- if you need that, what you want is a different concept than "set".

[spring surge]

thanks

[coral parcel]

Assuming that your & is supposed to stand for union. It's of course true that the intersection of {-7} and {7} is empty, but that is unlikely to be what you meant.

[idle hazel]

man some of these problems are boring AF

im not gonna write a set with a million elements best you will get is a ... and the last one lol

[unreal stump]

You might want to look at free groups

[spring surge]

Can't I just expand it to all sets, not only numbers, given that I encode my sets as numbers?

[coral parcel]

I don't think I understand enough of your context to give relevant advise here.

[spring surge]

i got enough info for my current understanding at the moment.

[coral parcel]

Gah! You should only enclose the actual formulas of your post in dollar signs, not the text that is not formulas.

[weary tiger]

how many series exists such that for all: $\i\in [2n] , a_{i}\in${1,-1}
and the sum of all is: -4
and for all: $i \in [2n], \sum_{j=1}^{i} a_{j} \ge -4$

[vital dew]

KingKunta

[weary tiger]

this is catalan numbers

do I solve it as a problem of going on a grid of a rectangle

[tall oxide]

Sorry.

A_i = {... - 2,-1,0,1,2...., i}

n
\cap A_i
i=1

[idle hazel]

hey can i ask you something unrelated to discrete math?

[coral parcel]

Perhaps, but no guarantee whether I can or will answer.

[dense glade]

what is residue modulo n of a?

[idle hazel]

how do you know if youre 🧠 enough to study math in university?

in your opinion

[coral parcel]

If you're doing well enough in a standard high-school program that your teacher is assigning special reading to keep you challenged, I don't think you need to worry about that.

More generally, I suspect it might not be raw brains but interest that's the best predictor of success. If mathematics makes you think, "this is so cool, I want to learn everything and understand how it works", then chances are excellent that you'll be able to.

[dense glade]

I mean I have met people that are not crazy at math just decent enough and they have math degrees

depends on program ranking

I guess

[coral parcel]

There'll always be concrete details of things you haven't learned yet that feel like they're completely opaque magic that you'd never be able to internalize -- don't let that discourage you.

[idle hazel]

well here we stopped at area under a curve

calc 1

and riemann sum

[dense glade]

I'm not a math major, just a math minor, but from everything I have seen so far you just need to work hard to learn math more so than having a big brain.

could be wrong though

[idle hazel]

well i wanna go to either the best or second best uni in my country

but im gonna try and make it so that my knowledge doesnt get dictated by university, as in be program dependant

im just gonna use books to get as far as i can

i think that even if your uni kinda sucks if you self study a lot you can still be good enough to be as good as people in top universities

[dense glade]

I think university ranking is probably

relevant in top 20

or something

idk but it seems like after that they are lumped together

[idle hazel]

i see

[dense glade]

like no one cares about the 55th school

its just top 100

so unless u are going to 20 names

[idle hazel]

top 20 in the world?

[dense glade]

yes

[idle hazel]

oh hell no

lol

[dense glade]

yeah thats what I meant

like the 223th school is probably not that different

to trhe 145th haha

[idle hazel]

no university in my country is top 20

Not even top 100

Lol

[hoary cloak]

i think your uni being like top 20 to like 500 is not an indicator of how good of a professional or academic you'll be by the end of your undergrad (besides the name in your diploma). maybe grad school when you're def doing research it makes a difference

if the teaching/infrastructure there is just bad, it does have a negative impact, but there are tons of good unis around the world

[idle hazel]

I see

Thanks

Ive always thought that at the end of the day if youre truly passionate and persistent you can have success

[hoary cloak]

i mean it's certainly not all you need, some people are in serious financial disadvantage etc.. but the point is that just about everything above top 500 is very good, including some names you've maybe never heard of

i'm not stating that these rankings are useless, i just think you prob don't want to discard a name because it's #487

[near void]

A benefit of top ranked schools (in a subject) is the funding they can acquire allows them to support larger faculties (ideally) and more elective courses, otherwise for internationally accredited programs the core curriculum is largely going to be the same with maybe slight varying difficulty of the problems they have students do. Plus you run into other people who chose to attend the those schools for the same reasons.

[hoary cloak]

that is also true when your uni is not #500 but is very good locally tbf

[idle hazel]

Well serious financial disadvantage is the name of the game in my case since no parents.

[hoary cloak]

my uni is like 650-700 and we get a looot of funding because we're the best in large radius

[hoary cloak]

i'd still say you can do your best and not give up, sometimes we pay the price for things that were not our fault, but we can still do the best to follow our dreams

[idle hazel]

#OrphanageMathematician

HAHA

[hoary cloak]

there is no better time to do that than today when we have the internet also

[idle hazel]

Yeah its very useful

No way I can buy so many books

So libgen

[near void]

I would recommend trying to find a tutor locally specifically someone who has and undergraduate degree or higher to help you when you get stuck. If you live near a university or college there is a chance that some professors are willing to help you out even if you don’t attend that institution (more so if the institution is teaching focused rather than research focused). Their willingness to help you can be easily determine by emailing them, typically professors will (ideally) not turn away keen students.

[idle hazel]

Thats actually what I was thinking of doing

Im just gonna shoot an e-mail to a professor

Worst they can do is not answer

What if I just go to the university and ask?

Like straight up

[near void]

That may work, but the profs may prioritize helping students in their classes during office hours. Email is a happy medium because it allows the professor more flexibility to address your questions

[idle hazel]

Oh so you mean emailing the question?

I thought you meant like asking if you could go there for help

[near void]

Sorry I meant both, or all, asking for help, finding tutors or other resources, email is a good starting point

[idle hazel]

Thanks

Ill try

Worst they can say is no

[near void]

Also you could see if you are able to get access to the library at the local college/ university, sometimes the institution may allow the public to checkout books.

[idle hazel]

Famous last words

[near void]

And then my last bit is to address the genius complex that math seems perpetuate. There is an opinion piece that i think highlight this issue well: https://erikhoel.substack.com/p/why-we-stopped-making-einsteins?s=r

[near void]

To answer one of you earlier question, it is likely a matter of practice more than just intelligence, although intelligence most certainly helps. I think the opinion piece supports this assertion

[idle hazel]

so its just like the speed of the process?

or does it dictate how far you can go?

[near void]

Sort of it is hard to define intelligence and how it relates to performance. I like to think of it in terms of the kind of concept a person is trying to learn, are they trying to figure out something new that no one knows or learning something that is already known. Learning things that are already known is easier because that is a matter of engaging with the right resources - like the people that know the concept. However, learning or discovering something new is something that is much more difficult and that is usually where intelligence seems to have a more dramatic effect. Otherwise it might just be the speed as you said.

Specifically in math everyone tends to hit some kind of abstraction ceiling eventually and not every mathematician is good at every topic in math because people have aptitudes, but we also see that people that study math for a while tend to also find ways to learn math better, so it is not clear what kind of limits there are

[idle hazel]

i think that you only find out how good your genetics are when you reach a certain level

i think that at like the intermediate level you cant really tell if you have good genetics

but at the high end its what matters the most

[near void]

I think that is the nature vs nurture debate, which is sort of like 50/50 humans seem to thrive comparably in the right environments as they do with the right genetics, but likely at the extremes genetics might win out. But there is a lot of ground in between where most people will likely fall

[dense glade]

how is this transitive or symmetric?

[coral parcel]

Apply the definitions of these properties, and check.

Transitivity: if you have (x1,y1) and (x2,y2) and (x3,y3) such that x1=x2 and x2=x3, is it then necessarily the case that x1=x3?

[dire obsidian]

I'm pretty sure this is symmetric because for every (m,n) you have (n,m)
I don't think there is even one case where this is not met

[dense glade]

hmm yeah

(1,2), (2,3) and (1,3)

but x2 isn't = x1 or x3

[coral parcel]

For choices where you don't have (x1,y1) R (x2,y2), the definition of "transitive" demands nothing.

[dense glade]

sorry?

[dense glade]

ah I see

so it's transitive

because (x1,y1) R (x2,y2)

[dire obsidian]

an intuitive way to think about transitive is that if everything is connected with one another transitivity must be met

[dense glade]

if x1=x2

I will properly write it

1 sec lol

since (x1,y1) only relates to (x2,y2) when x1=x2 then there will never be case where x1 and x2 are not equal and so

its transitive because it doesn't satisfy the def of transitivity right?

like its trivially transitive i guess?

[coral parcel]

It is transitive, but not "trivially".

The definition of "transitive" doesn't care about cases where x1 != x2, but "trivial" would mean that there is no way to make x1=x2 and x2=x3 -- which is definitely not true.

[dense glade]

ah okay

I see thank you

[dire obsidian]

Transitivity by itself requires if (x,y) (y,z) exists then (x,z) must also exist
but if everything is already connected together you don't even have to worry about that

everything is already connected together for the relation you sent so it's 100% transitive without even having to think too much

[coral parcel]

For the record, I don't think "everything is connected" is a good way to think about transitivity.

And in this case it even seems to be false -- for example, (2,2) and (3,3) are not connected by this relation.

[dense glade]

in this case its transitive because

the (1,2) will never

relate to

(2,3)

so we dont have to worry about (1,3)

[coral parcel]

It is not enough to find two elements that are not related.

[dire obsidian]

ah right I misread the relation I thought that it was full on R^2 x R^2

[coral parcel]

You need to show that for every possible choice of (x1,y1) and(x2,y2) and (x3,y3) such that (x1,y1) R (x2,y2) and (x2,y2) R (x3,y3) you'll also have (x1,y1) R (x3,y3).

An example of a choice of x1,x2,x3,y1,y2,y3 where these conditions are satisfied could be (x1,y1)=(5,13), (x2,y2)=(5,13), and (x3,y3)=(5,29).

So you can't just say "these conditions can never be statisfied".

[dense glade]

but

(x1,y1)=(5,13), (x2,y2)=(5,13), and (x3,y3)=(5,29).

sorry you're saying

these are transitive?

[coral parcel]

"Transitive" is a property of the entire relation as a whole, not of particular elements.

[dense glade]

yeah

[coral parcel]

But these are one of the many combinations of elements that must satisfy something in order for the relation to be transitive.

[dense glade]

I understand but I cannot see how

umm I guess

in the definition

of transitive

x and y need not to be distinct

[coral parcel]

Indeed they don't.

(It's an easy case if they happen to be the same, because if x is the same as y and you know y R z, then automatically you also have x R z).

[dense glade]

ahh

I see Thank you

[coral parcel]

We could also take (x1,y1)=(5,pi) and (x2,y2)=(5,13) and (x3,y3)=(5,29).

So the "easy" case is if (x1,y1) is the same pair as (x2,y2). Here we have x1=x2 but not y1=y2, so it's not automatic in the way noted above.

But that kind of overlap is definitely always included when you see a definition that says "for all x and y and z", unless it explicitly says it's only interested if they're different.

[dense glade]

why is it 29?

shouldn't it be

[coral parcel]

A random number I pulled out of a hat.

[dense glade]

pi or 13?

[coral parcel]

No, the condition is that (5,pi) R (5,13) and (5,13) R (5,29).

[dense glade]

aren't we trying to show that if having the set x1 y1 and x2 y2 imply that x1 and y3

we have the 3 x's equal

[coral parcel]

Yes.

[dense glade]

ah

see was thinking

thatw e needed

the third pair

[coral parcel]

Something that might confuse you is that it sounds like you're looking at a definition of "transitive" that uses the letters "x" and "y" to stand for different kinds of things than the definition of the R relation in your problem uses "x" and "y" for.

[dense glade]

the y value to follow the 2nd pair

that is probably it

so isn't an entire pair

=x

in the transitivty def

[coral parcel]

Yes. So in order to unconfuse yourself, imagine that the definition of "transitive" had been written with different letters:

The relation S is called transitive iff for every p, q, and r such that p S q and q S r it is also true that p S r.

[dense glade]

ok

[coral parcel]

So in the context of our relation here, p, q, and r unambiguously mean pairs of numbers.

With the naming I've been using, p=(x1,y2) and q=(x2,y2) and r=(x3,y3).

[dense glade]

okay

ok let me now

reread what u typed up

because this makes more sense

ok so

ok I actually get it

now

[coral parcel]

Good!

[dense glade]

since p S q and q S r

because

x1 and x2 are the same

in both pairs

then p S r

[coral parcel]

x1 = x2 gives us just p S q. To get q S r you also need x2 = x3.

[dense glade]

exactly

yeah thanks so much

def the way u wrote it at the end

helped me understand it

I was looking athe actual numbers in the each pair

[coral parcel]

Yeah, common mistake to make.
The teaching point of giving homework like this is basically to give you a chance to be confused by these name/pair clashes in a setting where they're basically the only thing going on -- such that when you move on to other relations that are more interesting, you'll already know how to avoid that pitfall.

[severe swan]

How would I calculate this?

A bit string length of 9 (0 or 1) is randomly generated. What is the probability that the bit string had fewer than three 1s?

This means that there would only be 3 but strings with less than three 1s.

Two 1s and the rest 0
One 1s and the rest 0
Zero 1s and all 0

There are 2^9 total strings

A) 2^3/9!
B) 3/2^9
C) 9/2^9
D) 3/9C3
E) 3/9C2 + 9C1 + 1
F) 46/2^9
G) 3/9!
H) 3/9C2
I) 36/2^9

[onyx hull]

Could someone help me understand the notation of N → N × N and R^2 → R ? 😄

is N the domain and N x N the codomain?

[hard citrus]

Yes

[sand smelt]

can someone help me solve this problem?

i also don't understand this problem

what does it means that i have to find the number of how many have 2 elements?

[unreal stump]

So say you have an equivalence relations. That divides the set into equivalence classes

It can be shown these classes partition the set

[sand smelt]

😦

how do i find that number?

if it has only 2 elements shouldn't then it mean all the number of A*A?

im lost

[unreal stump]

Well you need to know that the answer is same as number of ways of partitioning the set into sets of 2

[sand smelt]

how do i get the last problem?

the number 6

??

[stray reef]

think about what it means for a relation to be reflexive, symmetric and antisymmetric

[sand smelt]

then are there 5?

(1,1)(2,2)(3,3),(4,4)(5,5)?

[stray reef]

do not confuse a relation for an ordered pair

[sand smelt]

it says that the answer is 1 but I don't know why

which relations is the one which is reflexive, symmetric and antisymmetric?

[stray reef]

the only such relation is equality

[sand smelt]

what about this problem?

[pallid python]

Hey guys! new here..
could you please help me with these two questions for my assignment:

1. Prove that (6Z, +) is sub group of (3Z,+). (Try to prove it by using any one sub group test and also prove it by using usual group properties)
2. Prove that set of all diagonal matrices forms group w.r.t addition and check the same w.r.t multiplication.

[unreal stump]

What have you tried

[pallid python]

for the second question, i am trying to verify it by every property and then prove it but, not sure if it is right or wrong

[unreal stump]

Should be correct

wrt addition it's a group

wrt multiplication it's not a group

[pallid python]

and how shall i go about with the first question? any idea?

[unreal stump]

(6Z,+) is clearly a subset of (3Z,+)

So you have to show identity lies in (6Z,+) and that inverse exists for all elements in (6Z,+)

[fair jungle]

Can someone explain why the algorithm described in the link runs in O(|V|+|E|) time? https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#Algorithms

I dont understand why its +|E| . I can see why the |V| is there, seeing that there are |V| vertices to be removed.

[weary tiger]

I'm having a hard time trying to prove that for every connected graph its radius must must be less than or equal to half its size. I mostly tried proving it by contradiction, but I just can't find a proper way to lead the proof to conclusion. The thesis itself seems rather obvious to me, so I guess the proof shouldn't be that hard, but I really can't find the missing piece. I'd be very grateful for any help 😅

[coral parcel]

For each neighbor w of v not already in L
This step will eventually iterate over all the edges.

[coral parcel]

Suppose the graph has 2N or 2N+1 nodes. Let v0 be a vertex of minimal eccentricity, and consider a spanning tree consisting of shortest paths towards v0. If this tree has a branch of length >= N+1, then any branch that begins with a different edge out of v0 can have at length at most N-1 (otherwise the two branches together with v0 have more than 2N+1 vertices between them). But this means that moving one step down the long branch leads to a vertex of smaller eccentricity, which is a contradiction.

[ornate forge]

How many permutations of the letters 'solenostemon' contains the string 'on'?

[weary tiger]

Thank you very much, I would have never thought about using spanning tree here. I'm currently working on a similar problem as well, this time the graph is connected bipartite G = (X,Y;E), where |X| < |Y| and I have to show that its radius is smaller than |X|. Do you think that it can be proven in a similar way? I'm thinking that after constructing the spanning tree in the same way as you did, it will include vertices from X and Y alternately, so i it will have to include some minimal number of vertices from X and some from Y and coming from that i can find contradiction in a same way as you did. Do you think that would work or is there a better way?

[coral parcel]

Yeah, some variant of the same argument will probably work.

Thinking further about it, it's not really important for my argument how you construct the spanning tree. You can just pick any spanning tree, argue that its radius is within the claimed bound, and then note that adding the rest of the edges in the graph cannot possibly make the radius increase.

[unreal stump]

Ok nvm

[idle hazel]

Hey sorry to bother, I just wanted to say you were right about the learning thing

Since i basically never studied b4, now, after like 1-2 hours my head feels numb

[muted gate]

How many edges are there in a simple undirected graph with $n$ vertices?

[pale epoch]

what

[muted gate]

a simple graph

I don't know how to start this

like

yeah

hm

is this just n choose 2?

[vital dew]

texaspb

[sick dirge]

Sorry for interrupting. I have a question which asks to write "there exists a unique $x \in D$ such that $P(x)$" in terms of the standard quantifiers. Is $(\exists x \in D, P(x)) \wedge (\forall y \in D, y \neq x \rightarrow \neg P(x))$ correct?

[vital dew]

PhenomPlasma

[sick dirge]

Woops, mean P(y) at the end there.

[unreal stump]

Yea looks correct except for that

[obtuse lance]

since phi is a multiplicative function you can try to work backwards from how it works with primes $\phi(p^k)=p^k-p^{k-1} = p^{k-1}(p-1)$ knowing this we can brute force possibilities through the factorization of 116

[vital dew]

Merosity

[obtuse lance]

for 116? nah

write out all the factors of 116, then one of these will have to be equal to p-1 for some prime p

there are very few factors of 116, so it doesn't take long

[sick dirge]

Thanks.

[coral parcel]

That is normal. Remember to take breaks. And after a couple hours of concentrated studying you ought to sleep on it, to allow the what you've learned to precipitate before you forge on with something that builds on it. In a super crash priority, you might manage two of those sessions per day, but few people can sustain that indefinitely without burning out.