discrete-math

[urban berry]

in cs in general, in school yeah u might see it again idk about the field

[keen cave]

yikes rip

right here the class is so insane with drop/fail rates C == 60%

80% of the grade is based on 5 exams

20% is homeworks etc

homework, written homework, quizzes, practice exams == 20%

[urban berry]

we have 40 % exam, 40% quizzes and 20 % homework

[keen cave]

ahh I see, kinda similar, unless the quizzes aren't proctored

[urban berry]

university of toronto baby

nah they are

quizzes are just tests

[keen cave]

rip then it's the same lol

[urban berry]

except they only last 1 hour

[keen cave]

ahh I see

[urban berry]

40 % exam is insanity tho

[keen cave]

rip man 🙏

u still going through it rn?

[urban berry]

nah i 4.0ed in summer

u can only take a course twice at my uni

i took it first time barley passed

needed it to get into my program

took it the second time and did evey question in the textbook twice XD

[keen cave]

danggg congrats brooo holy

[keen cave]

oof whyy tho did it interest you?

[urban berry]

u will to surely

[urban berry]

i needed it to get into CS

so to pursue my degree i had to get atleast a 73

98% is insane daym

[keen cave]

ahh I see that's rough man

[keen cave]

bro I tryharded it at the beginning cuz I heard the first two tests are the easiest

[urban berry]

my uni accepts 1200 students for CS but only take 300 forward so this is the course where they cut most ppl lul

[urban berry]

thats good keep at it

[keen cave]

yeah gotta weed out ppl somehw

Physics (mechanics), Calc 2, Calc 3, and discrete math, (maybe linear algebra) are weedouts at my uni

also DSA is a big one

[keen cave]

yessir 🫡

[urban berry]

DSA?

oh

data structures

[keen cave]

Ye lol u know

[urban berry]

and algos

[keen cave]

yeee

[urban berry]

yeah discrete math is what gets alot of ppl

[haughty garden]

The math department at my university really likes 60% weighted exams for some reason 😭

[urban berry]

oof man

[keen cave]

yeah I would like to see the dropout rates

[urban berry]

yeah idk my unis brutal when i took discrete math the second time i went into the exam with a 92%

couldnt finish half the exam

[keen cave]

according to a mechanical engineer who took this class, he said it was harder than Thermo 1 and 2

[urban berry]

i should have endded with a 60%

but still 4.0ed

[keen cave]

holy

[urban berry]

meaning that the curve was 20%+

[keen cave]

ahh I see, my prof doesn't curve but our C == 60% so it balances out

and extra credit built into exams

[urban berry]

i walked out not finishing half the exam bro i was bouta kms

[urban berry]

thts pretty fire

[haughty garden]

This is also pretty normal; if you can get through about 60% of the exam, you’d end up getting around 85+

[keen cave]

damn broo yeah I guess discrete math is hard everywhere

[haughty garden]

💀

[keen cave]

only 8% tho but hey better than nothing xD

[haughty garden]

So 60% weighted exams + barely completing half of the exam 💀

[keen cave]

I just guess on the questions I don't know ofc

[urban berry]

nah but we had this prof

from china

i love this man but bro is textbook perfect

hes not into the yap

[keen cave]

my exams are weighted 80% at my uni 😭

[urban berry]

and for some reason the prof marked all the exams no TA

[keen cave]

20% is hw, quizzes, etc

[haughty garden]

Yeah 80% exams are fucked

I hate doing exams

[keen cave]

TA?

[keen cave]

yup they REALLY wanna weed out people rn

like teacher assistant?

[urban berry]

teaching assistants

[keen cave]

oh

[urban berry]

i got diagnosed with ADHD which lets me write with accesability, id highly recomend looking into it

[keen cave]

I will say this calc 2/3 I thought were hard, I didn't know what hard was until discrete math structures LMAO

[urban berry]

super help ful

[haughty garden]

The discrete math exams have also gotten so ridiculously difficult at my university

[urban berry]

just nice to write in a quiet room with extra time

[haughty garden]

I work at a drop in centre where we provide academic support to first and second year math students, and some of the questions that the students bring to us are actually proper fucked

[keen cave]

I feel like I have adhd but the issue is I just have too much adrenaline to go off the exam, (it is really hard sometimes to focus in exams). When doing homework or watching lectures, every 2 mins I open a game or watch youtube it's baddd...

[urban berry]

bro i know what u mean, when a younger year is bringing u something nd ur liek "uhhh.. "

[keen cave]

I know feeling like it isn't enough, but I feel like those are heavy signs of ADHD

[urban berry]

yeah lol same

[haughty garden]

Oh nah I’m fine, I just don’t like doing exams in general

[urban berry]

go to the accesability department at ur school they can help u

[keen cave]

but somehow during exams I just go into hyperfocus mode

cuz of the adrenaline

[keen cave]

rip I don't wanna take meds tho

that's the only reason I didn't go

to the doc

I guess you don't HAVE to take them though

[keen cave]

but yeah bro sorry about that tangent, just to make sure...

My notes:

for induction we make n the lowest number it applies to

we try to do n+1 to prove the next statements are true (for all n values)

We try to make it into a base case form or a form that alligns with the base case (like if we are trying to prove if something is a multiple of 21 we would want to make something like 21 * (equation)

For n = 5, as n increases we don't use n = 6 because we are using the base case number of n = 5 and n to prove n+1

is sufficent right?

the ones from before

[quick tusk]

i know that if p is a factor of a^2, then p is a factor of a. Is it true to say that for any power of a

[tight hound]

If p is prime, then yes

[quick tusk]

nice ty

how would i explain it in my proof. I have that 3 is a factor of a^5. And i want to now follow up with 3 is a factor of a. Like from that step to the next, what is my reasoning. Something like Euclid Lemma?

[haughty garden]

yes

if 3 | a^5, then either 3 | a or 3 | a^4

if 3 | a, we are done; if 3 | a^4, then repeat the same idea

eventually, you must have that 3 | a

[quick tusk]

ah yeah

damnn i wished i could've seen that immediately, thats genius

[quiet copper]

In an urn are 5 blue, 3 red, and 2 yellow marbles. If you draw 2 marbles one at a
time, what is the probability to get at least one red? If you do not put marbles back. We do not distinguish marbles of the same color.

i am thinking i would do 1-(7/10*6/9)

is that the correct approach ?

[vestal bronze]

yeah

[quiet copper]

thx

[rose widget]

how do I do the last 2 parts

[warm ferry]

Is the bound on xi(I)\leq k/2 referring to cardinality

[warm ferry]

Nvm it was just horrible notation

And errors within the notes

😂

Fun usage of basic combinatorics to prove the semicircle law

Onto its large deviations principle soon 😭

[sweet marten]

Can anyone give any advice on how to approach this problem please? Thanks

[vocal ruin]

i need help with part 2 of this question

i really don't know how to go about it

[vocal ruin]

i have figured out which subject links to what letter in the graph aswell

[nocturne grove]

does this look ok?

i wasn't sure if I needed more base cases or not

i need c-1 base cases but i don't know what c is so idk

well c >= 1

idk

[coral parcel]

{Ø,0,1} doesn't even make much sense. In the most usual axiomatic set formalism, the natural number 0 is represented by the set Ø, and in that case {Ø,0,1} is the same set as {0,1}, so |2^{Ø,0,1}| would be 4. However, the real number 0 is most often either a Dedekind cut or an equivalence class of Cauchy sequences, and neither of those is equal to Ø, so in that case |2^{Ø,0,1}| would be 8. Even asking a question where that difference matters is horribly wrong, and students who write such nonsense would rightly be told it's nonsense ...

[nocturne grove]

i dont think my 2nd base case is right

im confused

[charred harbor]

is my proof correct?

someone pls verify

i think it's correct

[novel ore]

is there any difference between a totally ordered subset and a chain?

[coral parcel]

No. In the context of partially ordered sets, "chain" is a short word for "totally ordered subset".

[novel ore]

i see

thanks

[brave rock]

If perhaps you're thinking of chain in the context of ascending/descending chains of ideals for example, there is a difference, although every ascending/descending chain will in particular be a totally ordered subset of the poset of ideals

[cerulean gust]

hi i just wanna ask a small question which may be a little silly

for 7)a) inductive step, we directly substitute n = k+1 instead of using k + k + 1

and for 7)b) inductive step, its adding an additional k+1 step after (2k-1), why is it not 1 + 3 + 5 + ...+ (2(k+1) - 1)

[cerulean radish]

Just so that what they did there is made clear for the reader

It obviously doesn't change the value of the sum, so hence why not

[gritty tide]

can someone help me?

[severe jackal]

3240 im guessing

just crunched numbers tho

or have u been taught any formulas or alogrithms @ancient ermine

[severe jackal]

💀

[cerulean radish]

I forgot to write the solution for that, my bad; The coefficient is $\binom{n}{k}$ because when we multiply out the parenthesis in $(x + y)(x + y)\cdots(x + y)$, everytime we have to choose either $x$ or $y$ from each parenthesis, this means that to get $x^ky^{n-k}$ we need to choose $x$ out of $k$ terms $(x + y)$ where as there are $n$ of those

[vital dew]

A Lonely Bean

[cerulean radish]

Hence the answer is $\binom nk$

[vital dew]

A Lonely Bean

[cerulean radish]

Alternatively a proof by induction could work, but that will take some extra effort

[gritty tide]

thanks a lot

[cerulean gust]

thanks

[hidden shuttle]

can someone help with part c

not sure if im doing this right or where to go from here

[twilit dragon]

oh ok my bad

[inland apex]

How many ways are there to select 5 students from a class of 30 to hold six different
executive positions on a committee? Can someone help me with this? Is the "six" a typo or there is this type of problem exist

[vestal bronze]

@inland apexit makes sense that you could do this, it would mean one student has two positions

could still be a typo

[inland apex]

so it is a P(30,5)?

[vestal bronze]

it's a thing, it wouldn't have a notation

do you have an answer?

[inland apex]

Sorry I still don't understand, how to solve this problem assuming one can hold two positions

[vestal bronze]

i can't do hints

it would have to be a spoiler

[inland apex]

I can only think of 17100720

which is P(30,5)

[inland apex]

How many ways are there to seat 7 people around a circular table where two
seatings are considered the same when everyone has the same immediate left and
immediate right neighbor? Can anyone confirm my answer? I got 7!/7=720 ways

[coral parcel]

Do you mean "everyone has the same left neighbors and the same right neighbors" or "everyone has the same two neighbors"?
That influences whether mirroring the seating plan should count as a different solution.

[inland apex]

two seatings are considered the same when each person has the same left and right
neighbor

this is the example question

[coral parcel]

Yes, I was asking you to clarify that description. Does it mean "each person has the same left neighbor and the same right neighbor" or "each person has the same two neighbors"?

[inland apex]

I think is it means "each person has the same left neighbor and the same right neighbor"

[coral parcel]

Then I agree with your result.

[inland apex]

thank you so much

[inland apex]

How many ways are there to select 5 students from a class of 30 to hold six different
executive positions on a committee? Can anyone confirm my work on this? I got C(30,5)*5!

In which getting how many ways I can choose 5 people from 30 and ways to assign them is 5!

Is this sound correct

[weary tiger]

You choose five students and assign them six different executive positions? Does one student only hold one executive position at a time?

[inland apex]

That what I was confuse about as well, I do not know if this is meant to be that typoe of question or just a typo

[stoic wasp]

Can anyone lend some help?

[inland apex]

C(30,5)*5! is the most possible answer I can think of

[weary tiger]

If we go by this, then you first choose which executive positions you want to assign, then you choose the people, then you do their arrangements

[weary tiger]

This is valid if there are 5 different executive positions

[weary tiger]

Like say I have the following executive positions:
President, vice President, secretary, manager, captain, vice captain

If I assign the chosen people five different executive positions where one person can hold only one position at a time, I can choose to assign — vice President, secretary, manager, captain, vice captain; or I can also choose the assign — President, vice President, manager, captain, vice captain; and then count their arrangements in the end. So the choice of executive positions being assigned also matters here

If it's a typo and there are 5 executive positions then yeah your answer is correct

[inland apex]

If this is the case

is it like this

[weary tiger]

Yep

[inland apex]

In a certain lottery game you choose a set of six numbers out of 32 numbers. Find the
probability that none of your numbers match the six winning numbers. Can you confirm this for me as well

I got C(26,6)/C(32,6)

[weary tiger]

Yep it's correct

[inland apex]

thank you so much

[opaque escarp]

anyone know why its every option?

[brave rock]

Because every option is true 👍 hope that helps

I joke but if you have a question about what specifically you are struggling to see you might get some more useful help.

[opaque escarp]

hm, what is a equivlence relation

[brave rock]

A relation that is reflexive, symmetric, and transitive.

[opaque escarp]

oooooo, thanks

why would there be 30 parts in this partition?

[brave rock]

You've forgotten about the empty subset, probably.

[opaque escarp]

o that makes sense, is |S| = 29 mean there is 29 parts and including the empty set there is 30?

[gentle kite]

is anyone here good at graph theory?

idk how some of the proofs work

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[gentle kite]

how would u prove diracs theorem

[weary tiger]

I need some ideas how to solve this:

$\frac{\sum_{n=1}^m\sqrt{10+\sqrt{n}}}{\sum_{n=1}^m\sqrt{10-\sqrt{n}}}$

[vital dew]

𝓘 .

[weary tiger]

Is there some relation between $\sum(f(n))$ and $\sum(f(n))^2$ in general?

[vital dew]

𝓘 .

[opaque escarp]

what do i do for this one chat?

[weary tiger]

Find the number of 3 element subsets, then subtract the number of 3 element subsets that contain consecutive integers (i claim that there are easy ways to find both of these numbers)

[opaque escarp]

would (1,4,7) be a set or no

or {1,5,7}

[weary tiger]

{} is a set, () is a tuple

there is a way to do it using partitions instead (hint: start with the lowest element of each set of 3 numbers)

[haughty garden]

Let $A_n = \sqrt{10 + \sqrt n}$ and $B_n = \sqrt{10 - \sqrt n}$. Firstly, convince yourself that [(A_n - B_n)^2 = 2\left(10 - \sqrt{100 - n}\right).]

[haughty garden]

So you can write A_n in terms of B_n

[weary tiger]

Oh yeah it's just (A+B)² = 2B²

Got it, thank you

[sand carbon]

Need someone to check my answer for this:

You have a rectangular piece of graph paper which has n 1 × 1 squares. You decide to
cut the paper into n pieces, each 1 × 1, by making horizontal and vertical cuts. At each
step, you pick up a piece of the paper and cut it, all the way across, along a horizontal or
vertical gridline. (You cannot fold the paper or cut 2 pieces at once.) Use induction to
prove that for any n ≥ 1, no matter the order in which the cuts are made, exactly n − 1
steps are needed.

answer:

Base case:
N = 1. No cuts are needed to get a single square: 1-1=0, this holds. N =2: 1 cut is needed to get 2 squares, 2-1=1, this holds too.
Inductive Hypothesis:
Assume this is true for all 1 <= i <= k which means that it takes i -1 cuts to divide paper in i squares
Inductive step:
Consider a paper with k+1 squares. Let the first piece have m squares and the second piece is k+1-m squares, where 1 <= m <= k and 1 <= k+1-m<= k. By the induction hypothesis, we get m-1 and k-m for the second piece. So, the total number of cuts needed to divide k+1 is 1+(m-1)+(k-m) = k which is (k+1)-1 = k

[gloomy snow]

Guys where do you recommend to study graph theory? im still confused on this topic🥹

[tight hound]

Diestel

[opaque escarp]

how do i do this problem?

[tight hound]

Arrange the families as 5 objects in a line, and then arrange the people within each family

[opaque escarp]

am i using a perm formula or no?

or do i calculte the inner arrangments of the people in the familes by hand like writing out {A,B,C,D,E} {A,B,C,E,D} etc

[tight hound]

You should

[vast basin]

to put what knightwatch said into numbers:
5! * (4!)^5
ways to arrange families * (ways to arrange emembers in a family)^(number of families)

[latent epoch]

Why cant we define Fibonacci sucession without recursion using this ( at least i couldnt) :

u1=0 u2=1 and un= u(n-1) + u(n-2) ?

And then you find the characteristical polynomial s^2 - s - s

[meager prawn]

you do have an explicit formula for the nth fibonacci number

[latent epoch]

And you find the the Roots are the golden ratio and - the golden ratio and then with a system of equations you find C1 and C2?

[meager prawn]

yes

that is a well known formula
It's just much worse as a definition

[latent epoch]

But you can find with this "method"

[meager prawn]

ofc

[latent epoch]

Ok ok ty i couldnt i dont know why when i did the u3 i got some Numbers with decimal points instead of 2

[meager prawn]

that means you made a mistake in the computations. But the correct formula definitely works

[latent epoch]

Ty

[twilit sundial]

pretty hard walled on this rn 😭

all i have so far is $3V=2E$ and $af_a+bf_b=2E?$

[vital dew]

elrichardo1337

[twilit sundial]

nvm i think i figured it out

[blazing dragon]

Is there any generalization of result at least for one task item? It's kind of a lot to check every case for 2<=n<=9 🥺

[vital dew]

Alisia

[finite sonnet]

Can someone explain to me how part 2 of this question makes sense 😭 😂

Like dude, this doesn't seem right at all😂

[steep ether]

Guess who is back, for im confused for part b and c because i have 2 approachesd one, 1 subtracting and one adding all of the combinations but they should be the same answer... but they arent

i did 14 choose 5 times 3 choose 1 + 13 choose 6 times 3 choose 1 for b for example

i think (hope) i got the right answers for a and d

[ornate coral]

Why 14 choose 5? If you already chose one of the rivalry player, then rest should be chosen from 13. Moreover, there are two ways to choose the rivalry player.
This is for part (b), by the way.

[steep ether]

So you mean like 2 times 13 choose 5 times 3 choose 1 + 13 choose 6 times times 3 choose 1?

[ornate coral]

Yes

[coral lantern]

I have no Idea how to find a bijective function in between those 2, I just have the mappings. Would someone help me on how to proceed?

[brave rock]

Tell us what this notation means first, please

The groups that I believe this to represent have different sizes, so a bijection in the first place is impossible. So please explain what this means.

[odd heart]

Probably the positive integers less than n and relatively prime to n

With multiplication mod n

There's 8 of each, so at least bijectivity is there

[meager prawn]

and it is indeed isomorphic, though I don't think the abelian group classification theorem is usable here

[maiden crypt]

Can someone explain to me why this is a tree/forest?

[haughty garden]

it is an acyclic connected graph

so it is a tree

all trees are forests

[maiden crypt]

the answer was that the bottom one was only a forest

cuz trees can't be disconnected or sum

[haughty garden]

oh right yeah there are two connected components

4-3-1-2 is a tree

and it’s disconnected from the other tree

[sick dirge]

supposed to prove that this is a bijection, not gonna lie i have no idea where to even begin for both the 1-1 and onto parts. any ideas are appreciated

oh wait i think i understand the 1-1 part now using a hint the text gave me, still not sure how to do the onto portion, no hint given for that

[ashen token]

I guess a hint could be to compare C(x, y) and C(x-1, y+1)

[sick dirge]

showing C is 1-1: suppose (x, y) =/= (z, w). if x + y = z + w, then since the sigma notation part is the same and y =/= w, C(x, y) =/= C(z, w). if x + y =/= z + w, suppose x + y < z + w. then C(x, y) has at least 1 fewer term in the sigma notation, so the sigma notation is less than that of C(z, w) by at least z + w - 1, and since y < z + w - 1 , it follows that C(x, y) < C(z, w), ie they are not equal. the case for x + y > z + w is analogous

is this part correct?

[sick dirge]

oh thanks i think i understand now. so my working is this: we know C(x - 1, y + 1) = C(x, y) + 1. also, C(x, 1) = x(x - 1)/2. now let n be arbitrary, then let x be the largest x such that C(x, 1) < n. then since C(x + 1, 1) = C(x, 1) + x, it follows that to get to n from C(x, 1) by going to C(x - 1, 2) and so on, we need less than x steps, so we always stay within N × N

[chrome sand]

anyone knows what the inverse element should be

so for 0 its 0
for 1 its 4?
for 2 its 2
for 3 its 1?

[meager prawn]

the inverse of i in Z_n is -i = n-i

[weary tiger]

mod n in general because we have 0

[meager prawn]

any computation in Z_n is always implicitly mod n

[chrome sand]

hi guys

A = {f : X → X}

where f, f ′ ∈ A and∀x ∈ X:

(f ′ ◦ f )(x) = f ′(f (x))

i should check if this is a group?

I mean Associative is easy

finding a neutral element is easy too

idx

but injective

first i thougt i can just fast f^-1

but its not guaranteed that er exists a f^-1 since i dont know if every f in A is bijective?

[little prism]

then can you give a counterexample?

[chrome sand]

hm its not much given tbh

can you give me an hint?

something like this maybe

So basically i take a function which goes from A -> X and a is a subset of X

hmpf

[plucky wedge]

can someone breakdown what question b is asking me?

I used the pigeon hole principle for A

oh I looked up the solution and I was thinking too deep into, thought they wanted us to use some formula to prove that there is that exact combination of students

but they're just asking us to show that it can't be less than 25 students

[weary tiger]

i guess you should suppose otherwise, so you get <= 2 freshmen, <= 18 sophomores and <= 4 juniors which is not more than 24 in sum

[plucky wedge]

ok thanks

[slim ibex]

Why is the side opposite the largest angle in a triangle always the longest, I can't find proof

[gloomy snow]

where do u guys recommend to learn and solve discrete math problems? im afraid my teacher is gonna fail me for low scores

[blazing rose]

why does 1 generate the group of integers

or how do I generate negative numbers with 1^n under addition

is it just 1^x where x is a negative integer?

[haughty garden]

in a group, you require the existence of an inverse

[blazing rose]

yes

[haughty garden]

those generate the negative numbers

[blazing rose]

ah

I see

thank you

[coral parcel]

In an acute triangle the law of sines implies this (since sine is increasing from 0 to 90°).
If one of the angles is >= 90° that angle has to be the largest, and then in the law of cosines c² = a² + b² + (-2a·b·cos(C)) all three terms on the RHS are non-negative, so in particular c² is larger than a² or b² separately.

[coral parcel]

Oops, this is #discrete-math and that wasn't a discrete question. Don't post questions to several different channels, and use #geometry-and-trigonometry for geometry questions next time.

[haughty mango]

hello

i need help in #help-25

with modulo arithmetic

[weary tiger]

Im having real trouble identifying bipartite graphs. Does anyone have a decent eli5 explanation of them or strategies for identifying them?

[brave rock]

Bipartite graphs are precisely the 2-colourable ones, so you can use a greedy colouring technique to identify them

Eli5 version: paint some vertex red, then paint all vertices adjacent to red ones blue, and then all those adjacent to blue ones red, etc. If you have to repaint a vertex, it's not bipartite.

[weary tiger]

got it, i will give it a try, thank you

[plucky wedge]

I'm trying to figure out how to sovle this directly without doing the nunber of passwords with no digits taken away from the possible amount of passwords

I'm doing P6 + P7 + P8 since there are 3 different ways to complete this task

for P6 I then did added the possible ways to create the password (1 digit, 5 letters) + (2, 4) + (3, 3) + (4, 2) + (5, 1) + (6, 0)

and for (1,5) I believe there are 10 * 26^5 ways to create a string with one digit and 5 uppercase characters right

when I do that process for all of them and add them up I don't get the correct answer the book has for P6.

Instead I get 192,447,361

Where am I going wrong

[coral parcel]

You're not showing your calculation, so it's hard to tell you where the mistake is. The general plan looks sound (but needs more calculation than the book's 36^6-26^6).

[coral parcel]

No wait, you forgot to account for the fact that there are 6 possible places in the password to put that one digit.

[plucky wedge]

oh ok I see

[haughty mango]

can any one help

i have no idea what to do next

[haughty garden]

,rotate

[haughty garden]

From 10k_1 = 1 (mod 11), notice that 10 * 10 = 100 = 1 (mod 11) so the inverse of 10 is 10

So if you multiply both sides by 10, you get that k_1 = 10 (mod 11) which is the same as saying k_1 = 11m + 10

So then you have a solution for x by substituting k_1 back into x

[haughty mango]

but does that x satisfy both x’s @haughty garden ?

sorry i’m not home to do the problem immediately and my mental math is bad

[haughty garden]

yes

[haughty mango]

ty ill work out the rest of it soon

[raw cedar]

The question here was specifically whether the LHS was <, >, or = to the RHS; order does not matter.
My question is why does choosing the complementary people for the lefthand side divide it by 2?
Don't we also choose the complementary 4 in the case we choose the 6 on the RHS, or vice versa? What's different about the LHS?

[lean rover]

Let BExpr be the set of all boolean expressions defined by the following grammar:

BExpr::=bool∣(BExpr ∧ BExpr)∣(BExpr ∨ BExpr)∣(¬BExpr)

Define the recursive function countbinexprs, which, given a boolean expression, returns the number of occurrences of binary subexpressions (i.e., subexpressions in the form of BExpr ∧ BExpr or BExpr ∨ BExpr).

Evaluate your function on the expression:

((bool ∧ (bool ∨ bool)) ∧ (¬bool))

and verify that it returns the expected value of 3. Note that expressions are subexpressions of themselves.

[plucky wedge]

Can the division rule also be restated as basically saying that if the set A contains all of the elements(ways) to complete a procedure where the procedure can be done in n task and either of task n can be completed in d ways then there is 1/d ways to complete n. Since there are 1/d ways to complete tasks n then we can say the number of ways to complete the procedure is (1/d)(n(number of tasks) *d(number of ways to complete each task n)) according to the sum rule.

n*d is basicaly |A| or the product rule

so its basically saying 1/d + 1/d +.. 1/d, |A| many times

which in the end result will gives us |A|/d

took me like an hour or two to get to this conclusion 😭

but atleast I think I understand it now

[fossil mural]

for any split of 10 people into 2 teams of 5, there are two possible ways to choose 5 people that gets you that split

if the two teams are {1, 2, 3, 4, 5} and {6, 7, 8, 9, 10}, then choosing {1, 2, 3, 4, 5} gets you the same arrangement as choosing {6, 7, 8, 9, 10}

if the two teams are {1, 2, 3, 4, 5, 6} and {7, 8, 9, 10}, the only way to get that arrangement by choosing a team of 6 people is {1, 2, 3, 4, 5, 6}, you can't end up choosing the team {7, 8, 9, 10} because that's not 6 people

[fringe turret]

Can someone help me download 156th page of this DOI? https://www.pdcnet.org/teachphil/content/teachphil_1993_0016_0002_0155_0156

[raw cedar]

Ah!! Ok, that makes a ton of sense. Thanks so much!

[haughty mango]

hello

[plucky wedge]

Are there any problems with my answer to this problem or does everything seem correct

[coral parcel]

That's a lot of text. It would be quicker to say that if at most 5 students get each grade, then no more than 5×5=25 students can be graded.

[plucky wedge]

Yeah but I wanted to make sure I was understanding everything the problem was asking

I have another question though, what do they mean by n - (r - 1) = n - r + 1

I'm not seeing how they are equivalent

oh

oh

I see

it makes more sense to think of it as n - (r - 1) = (n - r) + 1

wasnt taking into account order of operations at first

[vital dew]

𝓘 , 𝓣𝓵𝓸𝓻𝓽𝓱

[weary tiger]

I simplified this to

[vital dew]

𝓘 , 𝓣𝓵𝓸𝓻𝓽𝓱

[weary tiger]

But I am out of ideas on how to proceed from here

And from the given condition

$0<x_i<1$

[vital dew]

𝓘 , 𝓣𝓵𝓸𝓻𝓽𝓱

[weary tiger]

Well it is also trivial that K>0

[vital dew]

𝓘 , 𝓣𝓵𝓸𝓻𝓽𝓱

[vital dew]

𝓘 , 𝓣𝓵𝓸𝓻𝓽𝓱

[weary tiger]

Is this correct

[weary tiger]

(referencing this inequality in the first part)

[vagrant totem]

Is the correct

[weary tiger]

I didn't get you sorry

[lean rover]

Recursive def:
f(a) = f(a) + 1, if a = ~b
f(a) = f(a1) + f(a2) + 1```  ```
Base case: g(b) = 1, if b = boolean
Recursive def:
g(b) = g(b), if b = ~b
g(b) = g(b1) + g(b2) + 1```   How do I do structural induction with two step recursive function that g(b) <= f(b)?

[opal crescent]

Recursive def:
f(a) = f(a) + 1, if a = ~b
f(a) = f(a1) + f(a2) + 1```
what does b mean in the def of f ?

did you typo ?

[lean rover]

typo

it should be a = ~a

Basically, the first function defines a recursive function to find binary subexpression occurrences. And the second recursive function is trying to find both binary and unary expressions.

Btw I defined it so it could be wrong if it looks wrong

[opal crescent]

ah so a and b are binary strings got it

so you're trying to find the occurrences of what subexpression in f?

like ok you're searching for stuff in a, but what are you searching for ?

@lean rover

[lean rover]

This is one of the questions I solved: ```Let BExpr be the set of all boolean expressions defined by the following grammar:

BExpr::=bool∣(BExpr ∧ BExpr)∣(BExpr ∨ BExpr)∣(¬BExpr)

Define the recursive function countbinexprs, which, given a boolean expression, returns the number of occurrences of binary subexpressions (i.e., subexpressions in the form of BExpr ∧ BExpr or BExpr ∨ BExpr).

And for countexprs, we should count unary cases such as: (¬BExpr)

[opal crescent]

right so we have 4 cases for what a BExpr can be

I don't understand what your recursive cases are in your functions

like just follow how BExpr is defined

either

• a is bool
• a is of the form (b ∧ c)
• a is of the form (b ∨ c)
• a is of the form ¬b

that's all the cases to consider

AH ok now I see what you were trying to say in your f and g

but it's riddled with typos still, you should recheck a bit

@lean rover

[lean rover]

Yes Sorry I also forgot to post what I was trying to proof by induction and it is:

Countbinexprs(b) <= Countexprs(b)

1. Our base case is when b = bool, and we get 0<1 which is correct

2. Now that is where I'm struggling considering everything I've done so far is correct.

@opal crescent

[opal crescent]

well take two expressions b, and c for which you suppose
Countbinexprs(b) <= Countexprs(b) and Countbinexprs(c) <= Countexprs(c),
and you wanna show
Countbinexprs(b and c) <= Countexprs(b and c)

that's your (b and c) case for the induction

[lean rover]

Wait I'm not really following

What is the differenc between: Countbinexprs(b) <= Countexprs(b) and Countbinexprs(b and c) <= Countexprs(b and c)

[opal crescent]

how is (b and c) not different than b ? (b and c) is bigger than b

[lean rover]

you mean the logical "and"?

Sorry lol I'm slow

[opal crescent]

I mean the "and" of your definition of BExpr

/\

[lean rover]

∧

Countbinexprs(b) <= Countexprs(b) but isn't this our base case?

[opal crescent]

for boolean b

[lean rover]

How can I assume something I already prooved

[opal crescent]

you have to be very precise on what objects you're talking about

[lean rover]

here

[opal crescent]

b and c are just two BExpr's (they could be something more than a plain boolean)

[lean rover]

now I am following

[opal crescent]

for which I assume the proposition is true for the purposes of induction

[lean rover]

But the problem is now that I've a two step recursion, how do I even start the induction step?

[opal crescent]

wdym two step

you should really rewrite your functions right now before attempting to prove anything about them

cause I'm not even sure what you're talking about here

there was no mutual recursion in the f and g's you sent here

[lean rover]

is this wrong: Base case: Countbinexprs(b) = 0, if b = boolean Recursive def: Countbinexprs(b) = Countbinexprs(negation_exprs) Countbinexprs(b) = Countbinexprs(b1) + g(b2) + 1

[opal crescent]

"g(b) = g(b), if b = ~b", what does that even mean, don't use the same name twice (b) for different things

[lean rover]

edited that out now, I was trying to simply this huge problem. But now look again

It is edited now

[opal crescent]

also 'Countbinexprs(b) = g(b1) + g(b2) + 1' what's b1 and b2 here ?

I understand what you're trying to say

but it's not clear at all

(and I certainly didn't understand when I first saw the function)

if you write something destined to be read by other ppl, it has to be understandable for those other ppl

otherwise what's the point

[lean rover]

Recursive def:
Countbinexprs(b) = Countbinexprs(negation_exprs)
Countbinexprs(b1, b2) = Countbinexprs(b1) + Countbinexprs(b2) + 1```

this is what I actually answered on this part

[opal crescent]

ok, that still doesn't tell me what b1 and b2 are

[lean rover]

left and right?

[opal crescent]

how do you get them ?

[lean rover]

Tbh I'm a little unsure now that you've said it

I just assumed that if we have b v c, then we put c in one and b in the other

[opal crescent]

yes

how is that apparent in your definition ?

[lean rover]

if we have ~c then the first recusrion

[lean rover]

you have to think like me Ig lol, yeah but not sure

[opal crescent]

if you're going through this with a proof assistant later, be assured it won't think like you

[lean rover]

yes but how can I make this clear, is the logic itself wrong or just the name of the variables?

[opal crescent]

we just don't see how b1 and b2 come from, they're undefined pretty much

[opal crescent]

just follow this pattern if you have problems being clear

[lean rover]

Recursive def:
Countbinexprs(b) = Countbinexprs(b)
Countbinexprs(b1, b2) = Countbinexprs(b1) + Countbinexprs(b2) + 1```

does it solve it?

[opal crescent]

if a is bool, then f(a) = ....
if a = b /\ c, then f(a) = ...
if a = b \/ c, then f(a) = ...
if a = not b, then f(a) = ...

and you're trying to compute f(a) in terms of it's simpler constituents (the bool / b / c)

try and write your functions in this format

[lean rover]

but how can this help me with the last recursion step? As in b1 & b2?

[opal crescent]

If you don't have a clear definition of what your function is, how do you expect to prove anything about it?

[acoustic pond]

Hey can anyone help me to check whether my proof is correct or not?

I have a pdf file and it has 1-2 pages so it's about how I defined my set and my statement and how I proved it, anyone wants to go through it and check if there are any mistakes?

[lean rover]

I thought my first functions were correct, didn't realise I was way off. So I'm restarting it trying to get correct functions.

[opal crescent]

think about that first, then we can talk about induction

[lean rover]

so wait you want me to make different recursion steps for each?

[opal crescent]

yeah

[lean rover]

if a is bool, then Countbinexprs(a) = ....
if a = b /\ c, then Countbinexprs(a) = ...
if a = b / c, then Countbinexprs(a) = ...
if a = not b, then Countbinexprs(a) = ...

[opal crescent]

1 case per way you have of building a BExpr

[lean rover]

So this would be my function, but why can't put cases such as "or" and "and" in the same step, they are both some sort of conjunctions

[opal crescent]

I mean sure you can combine those cases if you want cause I'm not a proof assistant

[lean rover]

Also considering I followed your idea, if a = b /\ c, then Countbinexprs(a) = Countbinexprs(a1) + Countbinexprs(a2)

We will have the same problem, a1 and a2

[opal crescent]

I'm just giving you a completely unambiguous way of specifying your functions

[lean rover]

Yes but how do you suggest I solve this since you told me that it is unclear where a1 and a2 come form

[opal crescent]

just keep the if a =... in your definition

"if a = a1 /\ a2, then Countbinexprs(a) = Countbinexprs(a1) + Countbinexprs(a2)"

etc....

there we clearly see what you're trying to say

[lean rover]

So I don't need to do Countbinexprs(a1,a2)

[opal crescent]

nah

[lean rover]

but in that case, that is more of an clarity problem than logic right

[pallid locust]

hi guys

[opal crescent]

yeah

prolly worse than a logic problem

[lean rover]

So given Base case: Countbinexprs(b) = 0, if b = boolean Recursive def: Countbinexprs(b) = Countbinexprs(b) Countbinexprs(b1, b2) = Countbinexprs(b1) + Countbexprs(b2) + 1 and Base case: Countexprs(b) = 1, if b = boolean Recursive def: Countbexprs(b) = Countbexprs(b) +1 Countexprs(b1, b2) = Countexprs(b1) + Countexprs(b2) + 1

[opal crescent]

it's better having the specs wrong, than not even being able to understand the specs

[lean rover]

yes I will fix that!

My assumption is a two single expressions right

[lean rover]

then I wanna show their conjunctions in the induction step?

[opal crescent]

your assumption is two expressions satisfy the inequality

and you want to show their conjunctions satisfy the inequality

[opal crescent]

that's like saying "my assumption is 3"

[lean rover]

I meant kinda like you said, but worded it wrong

Let me try it, and I'll get back, thanks for the help tho. I appreciate it!

[opal crescent]

aight

[opal crescent]

we're wary of pdf's here, it would be preferable if you send two pics instead

[acoustic pond]

Okay let me write it instead

Is the text I wrote for the proof correct?

To prove: ∀(n, m ∈ N | nm + 1 is divisible by 3 ⇒ n + m is divisible by 3). The negation of this statement is: ∃(n,m ∈ N | nm+1 is divisible by 3, but n+m is not divisible by 3).
Assuming we know that (n * m + 1) gives % 3 = 0, then we also know that (n * m) % 3 = 2. Now we can also say that n % 3 = 2 or m % 3 = 2. So if we have n% 3 = 2, then m% 3 = 1.
An example is n = 2 and m = 4. (2 * 4 + 1) % 3 is 0, then 8% is 3 = 2. Now we can also say that 2% is 3 = 2. So if we have 2% 3 =, then 4% 3 = 1. A contradiction can now follow from this, because if n always has the
remainder 2 and m always has the remainder 1, when added it must have the remainder 0, regardless of the values of m or n. The negation of the original statement is therefore false, which is why one can derive that the
original statement "∀(n, m ∈ N | nm + 1 is divisible by 3 ⇒ n + m is divisible by 3 )" is therefore true.

Also is it correct how I explained that my code is correct

Because I'm not sure how I should explain or argue that it's correct

[opal crescent]

that's too complicated

you introduced a proof by contradiction where it's unnecessary

what you're doing is a direct proof essentially

we also know that (n * m) % 3 = 2. Now we can also say that n % 3 = 2 or m % 3 = 2.
that step is incorrect in general, what were you trying to apply ?

you're lucky that you fell back on your feet again just after

@acoustic pond

[acoustic pond]

Hmm why is it unnecessary, which part, is the whole proof unnecessary?

[opal crescent]

To prove: ∀(n, m ∈ N | nm + 1 is divisible by 3 ⇒ n + m is divisible by 3). ||The negation of this statement is: ∃(n,m ∈ N | nm+1 is divisible by 3, but n+m is not divisible by 3).||
Assuming we know that (n * m + 1) gives % 3 = 0, then we also know that (n * m) % 3 = 2. Now we can also say that n % 3 = 2 or m % 3 = 2. So if we have n% 3 = 2, then m% 3 = 1.
||An example is n = 2 and m = 4. (2 * 4 + 1) % 3 is 0, then 8% is 3 = 2. Now we can also say that 2% is 3 = 2. So if we have 2% 3 =, then 4% 3 = 1. A contradiction can now follow from this, because|| if n always has the
remainder 2 and m always has the remainder 1, when added it must have the remainder 0, regardless of the values of m or n. ||The negation of the original statement is therefore false, which is why one can derive that|| the
original statement "∀(n, m ∈ N | nm + 1 is divisible by 3 ⇒ n + m is divisible by 3 )" is therefore true.

[acoustic pond]

so basically when n = 2 and m = 2, then 2 * 2 is 4 + 1 is 5, 5 % 3 is 2

so n or m, which in this case is both 2 is % 3 = 2

[opal crescent]

no need for a contradiction

[acoustic pond]

Oh okay I see

[opal crescent]

I mean sure that's just an example

how do you justify that step in general

what modulo rule did you attempt to use here ?

[acoustic pond]

is this helpful

[opal crescent]

I mean yeah mn%3 = 2 implies m%3 = 2 or n%3 = 2, I'm not saying it's wrong

just that it falls out of nowhere in your proof

there's no justification for it

[acoustic pond]

Hmm okay, so if I want to use a contradiction, then I can only use it to disprove a statement with any quantifiers

In this case I rather should prove it so that's why the contradiction with negation is wrong in the first place?

Instead I can just write this:

To prove: ∀(n, m ∈ N | nm + 1 is divisible by 3 ⇒ n + m is divisible by 3).
Assuming we know that (n * m + 1) gives % 3 = 0, then we also know that (n * m) % 3 = 2. Now we can also say that n % 3 = 2 or m % 3 = 2. So if we have n% 3 = 2, then m% 3 = 1. If n always has the
remainder 2 and m always has the remainder 1, when added it must have the remainder 0, regardless of the values of m or n.
The original statement "∀(n, m ∈ N | nm + 1 is divisible by 3 ⇒ n + m is divisible by 3 )" is therefore true.

[acoustic pond]

Okay I think my mistake is that I only have shown it with 2 values but the 2 values are not enough to show that it applies for the whole statement

[opal crescent]

adding the contradiction in is not wrong, it's just extra bloat

you'd still end up showing the same thing either way

[acoustic pond]

Can I also say:

nm+1=0%3 implies nm=2%3
In general we can say n=1 and m=2 (mod 3) without loosing meaning
Therefore n+m=0%3

[opal crescent]

you could also have n=2 and m=1 mod 3

but same conclusion yes

[acoustic pond]

okay good good, so because of that conclusion I can say it's a true statement

Also, it's a direct proof now?

[opal crescent]

yes

[acoustic pond]

okay crazy I actually thought I needed way more text 😂

[lean rover]

Now I gave it a little shot but I'm still lost a little. How do I actually compute the proof?

As in I have two recursive steps right

[opal crescent]

do you mind if we do this in DM? I don't want to take this channel for 1 hour straight again

[lean rover]

Absolutely!

[celest oriole]

Hello,
For this contextual free language L={a^n b^n|n belongs to Naturals}
I have trouble seeing if it’s complement is still contextual free (I don’t think so).
I assume it’s complement would be every other words in {a,b}^* except the empty word (a^0 b^0) or any other words of the form a^n b^n right?
This doesn’t seem contextual free, since an automaton using a pile couldn’t memorize all of these possible combinations.

[celest oriole]

I got my answer, no need to answer if someone wanted to help

[grave sail]

Question: Is there a least element in th set of all positive rational numbers ?

[gusty swallow]

no

[lost imp]

Give a left regular grammar for the language of those strings of x’s, y’s or z’s which have no occurence of x, no occurence of y, or no occurence of z. In case it’s not obvious, by this I mean that there is at least one of the letters, x, y, or z which does not appear in the string; I don’t mean that none of them appear.

How many lines should a grammar like this consist of in reality?

[meager prawn]

S -> X | Y | Z
X -> Xy | Xz | e
Y -> Yx | Yz | e
Z -> Zx | Zy | e
Something like 4, or 12 depending on how you count
Or what do you mean by "in reality" ?

[lost imp]

sorry bad wording of my question, that's my question answered

Thank you

[weary tiger]

hi guys

I'm having difficulty in trying to find a way to approach solving this recursive function. I thought of approaching it as a difference equation, but the form does not really fit. or does it? I don't really know.

I'm uhh

stuck

[weary tiger]

by the way, the values for time and Pgas are controlled by a data set I've made.

[solemn zephyr]

How many arrangements of the letters A, B, C, ..., O, P exist such that by omitting some letters, one cannot obtain any of the words PONK, DOBA, or COP?

[novel raptor]

Hi guys

Sports competition is held on a circular system. This means that each pair of sportsmen
meets each other exactly once. Prove that at any given time there will be at least two
sportsmen who have the same number of meetings. how we can prove this using graph theory

[meager prawn]

player <-> vertex
meeting <-> edge
Then each state of the tournament corresponds to a subset of the complete graph, which is to say, just about any graph.

The number of meetings a player has made is the degree of his vertex. There are n players, for which the degree may range from 0 to n-1.

If they all have different degrees, then every degree is achieved by some player. From the player with degree 0, that plays no one, up to the player with degree n-1, that plays everyone, and every degree in between.

Can you find a contradiction ?

[weary tiger]

Does this expansion remind you guys of anything

any patterns?

[blazing rose]

when proving properties of algebras, e.g. a ring, can i just cancel out elements on the left and right in an equation?

like for example its given that my algebra is a group under addition and a monoid under multiplication

and by deriving smth I get smth like a+b+a+b = a+a+b+b using the axioms

in order to prove commutativity of addition

but can i now just say that Im gonna cancel out a on the left and b on the right?

or is there more behind it

like using the inverse function of the group part or smth

[brave rock]

No, you absolutely cannot.

In e.g. the ring Z/4Z, the values of 2*2 and 2*0 are the same, but I cannot cancel to conclude 2 = 0.

If you want to use a cancellation property, you must actually prove it to be true first.

[blazing rose]

I Found this online And this was also my thought process

But I just didn’t know how to continue when I arrived at a+b+a+b = a+a+b+b

Do I use the fact that R under addition is a group?

And use the inverses of a and b?

[blazing rose]

Or how were they able to say we cancel out a on the left and b on the right here

[wet haven]

Exactly. If an operation has inverses, then it is cancellative

[blazing rose]

Ahh I see

But how do I denote that as a derivation step

Before I only used stuff like “using distributive property” “using identity of the monoid” etc

[wet haven]

x + z = y + z => x + z - z = y + z - z => x = y

[blazing rose]

So do i just say -a And -b on both sides?

[wet haven]

Yup

[blazing rose]

Ok ty very much!!!

[keen aspen]

If we have a set A that is partially ordered without reflexivity

So (A,<) is strict partial order

and (a,b) R (c,d) iff a<c or (a=c and b<d) where (a,b) and (c,d) are elements of AxA

then is AxA partially ordered?

[little prism]

well try checking all the axioms

[keen aspen]

i tried and all are correct 😄

i felt like im making mistake somewhere

[little prism]

why do you think so

this ordering is how words are listed in a dictionary. first the first letters are compared. and if they are equal, then second letters are compared. (and so on)

thats why its called the lexicographic ordering

[keen aspen]

ok, so now if B and C are subsets of of AxA such that for all (a,b) from B there is (c,d) from C : (a,b) < (c,d)

is it possible to have for all (c,d) from C there is (a,b) from B : (c,d) < (a,b)

😄

not for all subsets of AxA

just a pair where for every element from one of them there is a greater element in the other

this cant be true as well right 😄

it's actually for all two sets

if we have B and C subsets of AxA and if for every element of B there is a greater element in C

then the reverse isnt true

well maybe not

[wary vortex]

Does anyone know how to do 1b and 1d?

[hushed wagon]

d : as it is 11 vertices graph, it can not exceed 5 edges, and its a solution for 5 edges :
ah , bc , ke, dj , gf

and it is not hamiltonian, you can prove it through vertices h, b, f, d, and j
i mean discussing about the 2 edges that enter and exit vertex j

[weary tiger]

discrete cosine transformations, explained from a applied stand point within machine learning object identification tasks

yeah i think i settle on that maybe

no

[wise halo]

can someone help me!!!!

find the recurrence formula and initial condition to calculate the number of decimal strings of length n that do not contain three consecutive ones?

[wary vortex]

Do you know the theorem for it?

[coral parcel]

Easier just to note that a bipartite graph with an odd number of vertices cannot be Hamiltonian.

[hushed wagon]

exactly!

[hushed wagon]

well only thing that can be said is that a n vertices graph, has at most [n/2] edges in a matching in the graph, the rest I mean finding the matching itself, I think there isn't any theorem for it, In complexity theory we call it NP so you have to try to find the matching by yourself

[hushed wagon]

[] stands for bracket

[coral parcel]

There are polynomial-time algorithms for finding maximal matchings. (But applying one of them to this problem by hand would be clear overkill).

[hushed wagon]

oh that's pretty good, I though the problem was NP

[coral parcel]

It's also in NP, but it is most likely not NP-complete.

Counting how many distinct matchings of maximal size there are in a general graph is #P-complete, though.

[molten stirrup]

Any sensible explanation as to why this happens?

$P(1,n) = 1 \ P(n,m) = P(n-1, P(m, n-1) +1) + 1$ but for any $n, m \geq 2, P(n,m) = 2$

[vital dew]

7aman

[molten stirrup]

And I'm completely lost as to why

Is this the right channel btw?

[fossil mural]

(well this is discrete so i guess it's a reasonable place to put it, and i'm not really sure where else it would fit)

[molten stirrup]

$P(n,m) = P(n-1, P(m, n-1) + 1) + 1\
P(m, n-1) = P(m-1, P(n-1, m-1) + 1) + 1\
P(n,m) = P(n-1, [P(m-1, P(n-1, m-1) + 1) + 1] + 1) + 1$

[vital dew]

7aman

[fossil mural]

well uh, that's not true
P(3, 1) = P(2, P(1, 2) + 1) + 1 = P(2, 2) + 1 = P(1, P(2, 1) + 1) + 1 + 1 = 1 + 1 + 1 = 3

[molten stirrup]

My codes fucked then

Ok $P(n,m) = n$ according to @thorny willow and my fixed code

[vital dew]

7aman

[fossil mural]

yep, it is

you can prove that by induction on n
P(1,m) is 1 by definition, so suppose that P(n,m) = n for all m and consider what P(n+1,m) is

[molten stirrup]

I keep forgetting induction is op

[opaque escarp]

does anyone know how to do part 2, im lowkey lost on what to do

[wary vortex]

sorry for interrupting your question but i do need help with answering this for graph theory. I have been trying to think of how to solve it but honestly the hint threw me off. why does this sum help me prove it?

[chrome osprey]

can i get some help on how i should approach this. i dont want to know what the key step is, but whats the process to show this, or what should i be thinking about when trying to come up with a solution

i dont want to just look at the solutions and try to understand like that, i want to actually come up with something half decent first

[meager prawn]

A usual technique to show an inclusion is to take an arbitrary element of the first set, and show that it's a member of the 2nd set

[chrome osprey]

ah i see

i have a definition

f(A0) = {b | b = f(a), for at least one a in A0}

how do i write this in mathematical notation?

or using quantifiers i mean, would it be: For every b in B, there exists a in A0 such that b = f(a)

[meager prawn]

For every b in f(A0)

[chrome osprey]

ah i see

For every b in A0, there exists a in A0 such that b = f(a)

and for the definition of the pre-image, f^-1(B0) = {a | f(a) in B0}, is this the same as: For every a in f^-1(B0), f(a) is in B0

also, i found this solution for part a)

i had a very similar solution for myself for the first half (i just didnt write out one of the parts explicitly), but i didnt know what to do for the inverse part, and even after looking at the solution, i dont understand why this proves equality

actually, shouldnt it say: then there is an x' in finv(f(A0))

[heavy marsh]

can i get help with my homework here?

im not very good at discrete math

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[radiant gale]

lol (hint: ||notice that the # of parameters in £ equals the # of £ in $. With equiv. substitution, we obtain $ = λr. r ($ r).||)

[brave rock]

Very cool

[vestal bronze]

who;s klop

[chrome osprey]

jurgen klopp

[quiet eagle]

Any literature recommendations for proof collections on graph theory (including algorithms would be ok) ?

[opaque escarp]

does anyone know how to do this?

[coral parcel]

Once you've picked one of each fruit and need to choose the next 8, it's a stars-and-bars problem.

[west wren]

Is my proof valid? In particular, I am worried about some steps which I skipped over.

And here, $S_\mathbb{N}$ denotes the set of all bijections from the natural number set into itself.

[vital dew]

DW0987

[cerulean wind]

i would show that f is injective

[west wren]

What about this? I also proved that f is indeed injective.

[cerulean wind]

nice

[west wren]

And is this rigorous enough to count as a proof of the fact that $|GL_2(\mathbb{F}_2)|=6$?

[vital dew]

DW0987

[west wren]

And here, $\mathbb{F}_2$ is simply integers modulo 2 (as a field under its typical operations), and $GL_2(\mathbb{F}_2)={A\in\mathbb{F}_2^{2\times2} | \mathrm{det}(A)\ne0}$.

[vital dew]

DW0987

[chrome osprey]

is f:Z+ -> Z, g:Z -> Z+, where f(x) = x^2, g(x) = sqrt(x), is this an example of a left inverse but not a right inverse?

[coral parcel]

That g is not Z -> Z+. For example, g(2) is not an integer; neither is g(-1).

[chrome osprey]

dammit

so if instead of Z, i used the set of perfect squares, it just becomes a normal inverse, rather than just left inverse

[coral parcel]

You could say something like g(x) = the smallest positive integer n such that n² >= x.

[chrome osprey]

is that a floor?

isnt that just floor(sqrt(x))

or is it specifically because srt(x) is not allowed

ah the issue would be negatives right?

could i do a piecewise function, where if x < 0, then floor(sqrt(-x)), and if x >= 0, floor(sqrt(x))

[coral parcel]

It's just a way to ensure the non-squares (and 0) map to something.

We could even say g(x) = sqrt(x) if x is a positive perfect square, and 42 otherwise.

[chrome osprey]

so i thought about that, only doing perfect squares, else its some random constant

i just thought itd be a nice thinking exercise to do it without an arbitrary map

lemme try writing in latex

[coral parcel]

Well, it is necessarily "arbitrary" in the sense that there's a creative infinity of different maps that all work (in the sense of being a left inverse of f). No matter how we pick just one of them to point to, that's going to be an arbitrary choice.

[chrome osprey]

Let $f:\mathbb{Z}^{+} \to \mathbb{Z}$ and $g: \mathbb{Z} \to \mathbb{Z}^{+}$, where \$f(x) = x^2$, \$g(x) = \begin{cases} \lfloor \sqrt{-x} \rfloor & \text if x < 0\ \lfloor \sqrt{x} \rfloor & \text if x \geq 0 \end{cases}$\ Then $(g \circ f)(x) = I_A$, and $(f \circ g)(x) \neq I_B$.

[vital dew]

shavet

[chrome osprey]

is that good?

and finding a right inverse is fairly easy with this, you can just make f: Z -Z+, and g = floor(sqrt(x)), i think?

oh wait no, right inverse isnt good there

[coral parcel]

Since f is not surjective, it cannot have a right inverse.

[coral parcel]

It does not make sense to write x = I_A, or x \neq I_B.

[chrome osprey]

whats the better way to write it?

[coral parcel]

Write what?

[chrome osprey]

to show that it equals or doesnt equal the left or right identity

[chrome osprey]

wait this does work actually. f(x) = x^2, where f: Z -> Z+ is surjective i think

[coral parcel]

7 is an element of Z+. Which element of Z does f map to 7?

[chrome osprey]

good point

that was silly of me

[coral parcel]

Ask yourself this: What is the "it" that equals or doesn't equal the identity?

[chrome osprey]

can i make f: R+ -> Z+, g: Z+ -> R+, f(x) = x^2, g(x) = sqrt(x).

[chrome osprey]

the composition of f and g

[coral parcel]

So write that the cpmposition of f and g equals the identity, not that x does.

[chrome osprey]

ah right

[coral parcel]

pi is an element of R+, but f(pi) is not an element of Z+.

[chrome osprey]

sorry, im being really daft and not considering these values

i keep forgetting that the functions individually must make sense

Let $g:\mathbb{Z}^{+} \to \mathbb{R}^{+}$ and $f: \mathbb{R}^{+} \to \mathbb{Z}^{+}$, where \$g(x) = \sqrt{x}$, \$f(x) = \begin{cases} x^2 & $if $x^2 \in \mathbb{Z}\ 22 & $if $x^2 \not\in \mathbb{Z} \end{cases}$

i think thats correct?

[coral parcel]

They are functions that exist, assuming you first decide on a value for n.

[vital dew]

shavet

[chrome osprey]

then f is surjective, since every positive integer can be hit, and f of g is right inverse

[pastel coral]

If you fill on the three dots $\Longleftrightarrow$ or $\equiv$, would the predicate be True, False or Does it depends on the situation?
The answer is it's not logically equivalent and for $\Longleftrightarrow$ it should depend on the situation. But how can I see/prove this?

[vital dew]

cedric_

[fossil mural]

the right-hand side says that for every element of U, either p(x) or q(x) - one "choice" per element
the left-hand side says that either, p(x) is true for all of them, or q(x) is true for all of them

so if you take for instance, U = the integers, p(x) = x is even, q(x) = x is odd

it is true that every integer is either even or odd

it is not true that either every integer is even or every integer is odd

[pastel coral]

ahhhh wow, yes thanks, that's a clear example

[frozen mason]

how is the degree for the region R_4 = 7? shouldn't it be 6? there is a walk where it only traverses 6 edges

[coral parcel]

Both sides of the fg edge are visible from R4, so that edge counts twice.

[eternal thicket]

i understood that the number of perfect matchings in the $K_{n,n}$ is $n!$. but how to count the number of perfect matchings for the graph $K_{n,n}$ in which the edges included in one of the perfect matchings are removed? i think it will be $(n - 1)!$, but idk how to prove that...

[vital dew]

alisas

[coral parcel]

There's n! matchings in the full K_{n,n}, and (n-1)! of them use the edge you're about to remove (why? prove it).
The number of matchings left when you remove those is then n! - (n-1)! = (n-1)·(n-1)! = n!(1-1/n).

[sick dirge]

is anyone able to give me a hint for the <= direction of (b)? im not getting anywhere

[grand totem]

Hint: consider two characteristic functions for h and k.

[sick dirge]

sorry what do you mean by characteristic function?

for (a) i managed to do it by assuming a =/= b, letting Z = {c} and defining h and k such that h(c) = a and k(c) = b, and showing f(a) =/= f(b) but a similar approach for (b) doesnt seem to work

[grand totem]

For sets A ⊆ B there is a unique function χ_A : B → {0,1} such that the preimage of 1 is exactly A (i.e. a ∈ A iff χ_A(a) = 1). Chi is the characteristic function of A.

A further hint may be that for two subsets A, A' ⊆ B. If the characteristic functions of A and A' are equal, then A = A'.
In your case, letting A = B = Y and A' = image of f, you could conclude that the image of f is all of Y (i.e. f is surjective) if their characteristic functions are equal.
And by the hypothesis that f is right-cancellable it would be sufficient to show that χ_Y ∘ f = χ_im(f) ∘ f

[sick dirge]

huh, im not at home atm dont have access to paper to play around, but thanks for the tip, will try it later!

[misty storm]

helloo

can someone help me with this question

let A and B be finite sets and let a = |A|, b= |B| and c = |A∩B|. write and expression in terms of a,b and c that is equal to |P(A)-P(B)| for every choice of A and B.

[vestal compass]

Can someone please explain to me how the hell does a path work in graph theory

Like how can a edges repeat themselves if vertices can't

OK so now I've read that they can't repeat themselves in our textbook but the teacher said they can

So now should I decide which one is true?

[brave rock]

Sometimes we want to consider paths without vertex/edge repeats, sometimes we don't. Often terminology conflicts between authors. That's what seems to be happening here. Fortunately if you pick a single source they will typically be consistent.

If your lecturer says they can, stick with that for the course for now. You should also inform them about this clash with the textbook.

[vestal compass]

I came with an idea that that statement can hold when we consider that we go from point A to B but we don't come out of B and go back to A

But then the thing is that the path would end there since, let's say we have point C and D that connects to A and if we started from C then we can't go from A to D

Or forget this sounds dumb

Cuz I thought it would work when we have some vertex that is incident with only 1 another vertex

[cyan junco]

how should i go about understanding set theory?

ive been self studying discrete math for a while and i got all the laws and baisics down but im having trouble grasping the concept of et theory

[fossil mural]

...is there something in particular you don't understand about it?

like are you confused about the basic idea of what a set is, or do you have intuitive ideas but not know how to make them more precise, or is the problem some specific operator like union, or...

[pure summit]

i'm having a hard time understanding this even w the textbook examples, can someone clarify?

nevermidn i think i got it

[weary tiger]

I've got a homework question in Graph Theory which asks the following:

Prove that every graph G where every two vertices share an odd number of neighbors is eulerian.

I'm quite sure I've got a proof if G is a simple, but I'm not entirely sure whether the professor meant by "graph G" that it is a simple graph.
I've tried tackling the case where G is not simple, but I'm not entirely sure the theorem even works for multigraphs.

So, does anyone have perhaps a counterexample for the case where G is a multigraph? if not, can I perhaps have some guidance in trying to solve the more general case?

[cyan junco]

how should i go about solving something like this

(i jus started so bare with me)

[tight hound]

Choosing U to be some appropriate set of natural numbers will make such examples easier

[cyan junco]

i see

[weary tiger]

We are given a finite set N (|N|=n). We will call a subset X of P(N) a stupid set, if for any A, B in X, A is not a subset of B. Any ideas how can we calculate the number of all stupid sets?

or to better formulate what I mean by a stupid set: X is a stupid set, if it doesn't contain a set and a subset of it simultaneously

for N={1,2} the stupid sets will be:
{∅}, {{1}}, {{2}}, {{1}, {2}}, {{1, 2}}
so the number is 5

for n=3 the number is 17 it seems

[cerulean radish]

Is a stupid set required to be nonempty?

[weary tiger]

let's say yes

[cerulean radish]

I don't have a closed formula but I think I derived this
[ C(n) = \sum_{k=0}^n \binom nk C(2^n - 2^{n-k} - 2^k + 1) ]
Where $C(n)$ denotes the number of stupid sets given $|N| = n$

[vital dew]

A Lonely Bean

[cerulean radish]

Basically when you choose a set, you can no longer pick any of its subsets or its supersets in P(N)

Say the set we chose has k elements

k will go from 0 to n

Its number of subsets is obviously 2^k

And there are 2^{n-k} supersets of it in P(N)

But we counted the set itself twice, so the number of subsets getting "removed" is 2^{n-k} + 2^k - 1

And the rest of the subsets should form a stupid set

Hence C(2^n - 2^{n-k} - 2^k + 1)

I may be wrong though

Yeah I think I'm overcounting

[weary tiger]

also it seems C(3) depends on another C(3) in this formula and in general it can depend on bigger number's C if we count like this

let's say n=4 and k=2

we get C(4) depending on C(9)

[cerulean radish]

Ah yeah the number of remaining subsets shouldn't be inside C

[sonic shadow]

Real quick question, n choose n + k for any positive integer k is always zero, right?

[vestal bronze]

right

[carmine matrix]

Does this question contradict itself? How can there be 6 elements in S and T, but the differences of the two cardinalities be 3 and 1?

[obsidian cradle]

I don't see anything wrong; choose for example U={1,2,3,4,5,6,7}, S={1,2,3,5,6} and T={4,5,6}.

[carmine matrix]

Oh, I see it now

Not sure why but my mind was somehow under the assumption that s and t were disjoint

[carmine matrix]

Hold on, how can the cardinality of T-S be 1 if S is bigger?

Wouldn’t it have to be negative to be true?

[obsidian cradle]

@carmine matrix T-S consists of the elements that are in T, but not in S, so T-S={4}

[carmine matrix]

Oh, I thought it was the same as |T| - |S| lol

Thanks!

[frozen mason]

Does the recursion formula obtained from this word problem not make sense to anyone else also?

Couldn’t he make money from the period of the beginning of year n+1 to the end of the year n+1?

[midnight mesa]

Ndhdbdb

[steep ether]

I think I can do A B C of 1 but im lost for the other d and question 2, any help is appreciated or links to resources to learn it

for A i put not as it wouldnt reach state s3, b I just put {b}, {a} {a,b}

c i wrote {a,a,b}, {b,a,a,b} {a,b,a,a,b}

but im looking through the slides and d and 2 are just very briefly mentioned and im lost

[weary blade]

can adjacency matrices have values other than 1 or 0?

everywhere i look online it says no

but my textbook says yes

[errant bear]

yes, theres weighted adjacency matrices, and theres no reason in general why they cant

[weary blade]

oh okay thank you

[steep ether]

anyone know?

[blazing rose]

hey wanted to ask rq

how is a polynomial mod another polynomial being calculated in general

is it somehow by polynomial division?

[opal crescent]

yea @blazing rose

[unreal dew]

for d, you need to find what strings will be accepted by A. note that the only way to get to s3 is by having an a -> a -> b, then you will get to s3 and it will infinitely loop

so, it would be something along the lines of $s \in {aabw: \text{w is a string made of a,b of any length}}$

[vital dew]

slack

[unreal dew]

idk

i havent done that class in ages

for number 2, you want to create a finite state automaton that will end on an accepted node for any string in the language L.

i think you're using the * notation as a regex, ie any combination of those letters in any length

[steep ether]

yea, i submitted something idk if its right tho 😭

[unreal dew]

so something like ${a,b}^\ast$ would be strings like $a$, $ab$, $ba$, essentially that set would be any string made of the letters a and b. then, part (a) is saying that $L = {wba | w \in {a,b}^\ast}$ is any string made of $a,b$ that ends in $a$ or $b$

[vital dew]

slack

[unreal dew]

or my bad

ends in ba

not a or b

so, you want to create a FSA that will end on acceptance node if the last two characters are $b$ then $a$

[vital dew]

slack

[unreal dew]

you can do this by preserving state so to speak, you want to know what the last two letters were and in what combination for the entirety of the string

[uncut ferry]

Can someone help me w this

[cerulean radish]

Count the elements of A, and exponentiate that with base 2

[uncut ferry]

I got it

It equals to 16 right?

[cerulean radish]

No

32

[uncut ferry]

!!

[cerulean radish]

A has 5 elements

And 2^5 = 32

[uncut ferry]

Damn i already submitted

Cuz i had like timer

[worthy siren]

not for "simple" graphs

[unreal dew]

the set has n= 5 elements, a power set of a set has 2^n elements, so we have 32 total

2^n elements in a power set because for each element, you can either choose to include or disclude it. thus, we have 2^n possibilities to construct a power set

[molten stirrup]

Any thoughts on this?
$u_{n,1}=u_{1,m}=1 \
u_{n,m} = u_{n-1,m} + u_{n,m-1} + u_{n-1,m-1}$

[vital dew]

7aman

[errant bear]

what kind of thoughts are you looking for

this is just dp

[molten stirrup]

I'm not sure if there's an easy explicit form for u_n,m and if anyone knows anything relating to this I'd love to know

[errant bear]

the whole point of dp is that it builds off of prior cells

what you have is what you want

oh, you want a closed form for this case

[molten stirrup]

Yeah

[worn apex]

Hello, I'm studying flow net works, in the following graph, would O,C | A,B,D,T be a valid cut? Follow up: In the context of directed graphs, what constitutes a valid cut?

It is my understanding that a valid cut for a simple or directed graph is the same:

A partition of the graph into disjoint sets A and B

My confusion comes from the fact that in many videos I watch they only consider cut sets that can be performed by drawing a line through the edges of a graph from top to bottom like so:

The creator of the image never specified a reason for why only those cuts are allowed when creating a cut and I want to know why.

[errant bear]

id start by looking at the binomial theorem

[molten stirrup]

$u_{n,2} = 2(n-1)+1, u_{n,3} = 2n(n-1)+1$ according to the chickenscratch from this morning

[vital dew]

7aman

[molten stirrup]

And $u_{n,4} = \frac{4}{3} (n^3 - n) + 1$ iirc

[vital dew]

7aman

[opaque escarp]

how do i do this??

[unreal dew]

rolling two die has 36 possible outcomes, and there are 5 outcomes where the maximum is 3: (3,1), (3,2), (1,3), (2,3), (3,3)

[haughty garden]

This is often the way that people have in visualising what a cut is doing, but this leaves much confusion about cuts that are discontinuous. Indeed, you should go back to the definition of a cut — it is a partition of the vertices such that O and T are on different parts of the partition. So edges which cross a cut correspond to edges that have one endpoint on the O side and the other endpoint on the T side. So, while the visualisation of the cut is good for the purposes of illustration, it has the consequence of misleading students into believing that we don’t count ‘discontinuous cuts’.

[worn apex]

Understood, so discontinuous cuts do count as long as the sets are disjoint. There has to be reason for why only continuous cuts are considered in the problem solving process of determining the minimum s,t cut in many of these videos on YouTube . Could it be that the cuts that are most likely to be minimum cuts are continuous cuts?

[haughty garden]

They're just easier to visualise and the notion of "cut" makes more sense in that setting (you are literally cutting the graph!)

there's nothing inherently different about discontinuous cuts

[sullen skiff]

I don't remember why when we have

  for i = 1 to n
    for j = 1 to i
      // Some O(1) task

the complexity is $\Theta(nlogn)$

[true pelican]

That's wrong

Did you mean j = 1 to n with step size i?

[sullen skiff]

No, step size is 1.

[true pelican]

Then it's n^2

[sullen skiff]

it is $n^2$ when j=i to n for example

[vital dew]

Mr_KEBABOUR

[true pelican]

Yes but also 1 to i

1 + 2 + 3 + ... + n = O(n^2)

[worn apex]

There is a proof that shows that the sum of all numbers from 1 to n is equal to n(n+1) / 2 O(n(n+1) / 2) == O((n^2 + n) / 2) == O(n^2)

[sullen skiff]

sorry but I don't think that is answering my question above

[errant bear]

you dont have a question

you have an assertion that was corrected by 2 people

[worn apex]

You said that "I dont remember why when we have (The above for loops), the time complexity of (The above for loops) is Theta(n log n)"

I just realized you asked why it is Theta(n log n).

The assumption that the time complexity of your snippet is Theta (n log n) is incorrect as DAILI pointed out earlier.

The time complexity is n^2 due to the proof I mentioned earlier.

The amount of times that O(1) task is executed is:

1 (when i = 1 and j =1)

2 (when i = 2 and (j = 1 and j = 2)

3 (when i = 3 and (j = 1 and j = 2 and j = 3)

.
.
.
All the way up to n executions

The growth of these executions is not n log n, it is n^ 2 because the growth is equal to the sum of number from 1 to n.

[unreal dew]

this is O(n^2) since big O is an upper bound, and we can bound $i$ by $n$ => $n * n $ worst case steps (its only an upper bound after all)

[vital dew]

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

[unreal dew]

oh shush

[unborn vapor]

Yeah but it’s not just because it’s an upper bound that it’s true. It’s also Theta(n^2) (because of what TheOwnageGuy explained)

[unreal dew]

indeed

[fallow stratus]

hey

guys need help in graph theory

[weary tiger]

is discrete hard

[fallow stratus]

what do you mean

?

[weary tiger]

is it hard or no

[hard stone]

!da2a

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[unreal dew]

ask away

[fallow stratus]

Well my question is this

Let G be a planar graph for which each facet is bounded by a circuit of length 4.
Prove that each circuit of G has the same length

I thought about using Euler formula

I have the answer but I do not understand it

Hopefully someone van explain

@unreal dew

@hard stone

[unreal dew]

not familiar with the term facet

what does it mean in your context?

[fallow stratus]

Well it means like the face

Of a planar graph

For example cube has 6 faces

[coral parcel]

Then it doesn't even sound true -- the graph of a cube seems to satisfy the condition, but it certainly has circuits of length other than 4 ...

[coral parcel]

By the way, "ask away" doesn't imply "and then I'll answer". It means, "nobody will be able to even tell if they can answer (and have time to explain an answer) until you actually ask your question".
So pinging the people who told you this essentially administrative tip is not appropriate.

[fallow stratus]

Well should I send what the book is saying

[coral parcel]

That might help with figuring out where the disconnect is.

[fallow stratus]

Sure

One second

Take a circuit C' of length n, and say that there are f facets in the area enclosed by
C. In total there are 4f lines enclosing the facets. A number of these lines are now counted twice: the lines that separate two of the f facets. Say there are m such lines. The lines that are not counted twice are the lines that connect to only 1 of the f
facets borders, or exactly the lines in C. Now n + 2m = 4f. Since 2m and
4f are both even, so n must also be even.

This is the answer

I’m not really sure how n+2m=4f

[coral parcel]

That looks like it proves "each circuit of G has even length", not "each circuit of G has the same length".

[fallow stratus]

Well even if it’s has even length

Can you explain

Has even length that is it. I looked and it’s saying that there was a mistake

[coral parcel]

Imagine the edges of the graph are drawn with some finite with, such that an edge has two distinct sides. 4f counts how many sides of edges are within your circuit. They can be divided into sides where the opposite side of the edge is also within the circuit (and there are 2m of those), and the inner sides of the edges that make up the circuit itself (there are n of those).

[fallow stratus]

The 4f and 2m i see that

Well 4f simply because for every face you need minimum 4 edges and and the 2m because it shares like 2m lines in each face

But like the +n I do not really see it

Correct me if I’m wrong

I think about almost like this one second

Something like that

Am i true

[coral parcel]

I can barely read that, and it's not clear to me how to interpret it anyway.

Don't you agree that the sides among the 4f total that are not the ones you counted as 2m must be the ones on the outside of the region?

[sonic blaze]

hi yall. Who has any sample final exams from their university? I want some materials to prep for my upcoming exam

[fallow stratus]

Well the 4m and the 2m I agree on it it

4f

I mean

Agree about

But like how n+4f=2m

I mean like how

I thought first they use Euler formule

[coral parcel]

Here's a concrete example, with the graph of a cube. I've drawn in a circuit in red.
There are f=3 faces inside the circuit, those faces have 4f=12 sides of edges which I've colored green and blue.
There are m=3 edges on the inside of the circuit; I've colored their 2m=6 sides green.
The blue sides are the ones that are left. They are all the 4f green-or-blue sides minus the 2m green sides, that is 4f-2m blue sides.
But there's also one blue side of each red edge, so the number of blue sides is also n, namely the length of the red circuit.

This is perhaps a better example with fewer numerical coincidences. Here we have n=6 (red edges), f=4 (yellow faces), 4f=16 (green+blue sides), m=5 (edges completely within the yellow region), 2m=10 (green sides), 4f-2m=6 (blue sides).

[fallow stratus]

Oh so I see it now thanks a lot

But I need to do it myself but I understand the intuition

I have also one more question

If you do not mind

My teacher though is this inequality as well

Sorry it’s in Dutch

Does it like has to do something with what you have just said

Because he said also something about that this shows double counting or something like that

I think about it this way sort of like a subset but not really sure if I’m right

The thing is I do not really see where is double counting happening

Further for the concrete example you gave it’s really clear thanks a lot 😊

[coral parcel]

I don't feel up to deciphering that right now, sorry. If it's about the same problem, I don't understand how it gets inequalities at all.

[fallow stratus]

No it’s not about the same problem

Do not worry

The thing is I tried searching on google but did not find anything about it

And I’m having exam like in two days but you did your best and really appreciate it

[cerulean gust]

Hi, I was wondering how I could approach 6 c)

[gusty swallow]

P(A given B) = P(A and B) / P(B)

[fallow stratus]

Let G be a connected k-regular graph (k > 0) with n points and assume that n is divisible by 4.
(a) Show that the number of lines of G is kn/2.
(b) Prove that G is line colorable with 2k colors.
(c) Prove that there exists a line coloring of G with 2k colors in which each color appears exactly n/4 times. a and b i do not have problem with. Need help in question c

Only

Can somebody hel

P

[sonic charm]

Guys any idea ???

i am stuck

[unreal dew]

uh

i cant read french

can you translate that

[marble ferry]

Translation: Write S for the set of nxn real matrices whose entries all have absolute value no greater 1, prove a=sup_{A in S} det A finite and an integer divisible by 2^{n-1} for any given positive integer n.

[fallow stratus]

hey

have question regarding graph theory

[regal dune]

Your question is?

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[fallow stratus]

I got a question
Let G be a connected k-regular graph (k > 0) with n points and assume that n is divisible by 4.
(a) Show that the number of lines of G is kn/2.
(b) Prove that G is line colorable with 2k colors.
(c) Prove that there exists a line coloring of G with 2k colors in which each color appears exactly n/4 times. a and b i do not have problem with
stuggling with C only

i do not know how to prove it

[frozen mason]

I row reduced and got 1 0 0 in the first row which would mean un+1 = un im not sure if that’s entirely correct tbh although it technically is

Is it correct?

[cerulean gust]

Thanks

[gusty swallow]

no, because your row reductions would also affect the n+1 column

[cerulean gust]

using this, i got the answer of 0.270 however the correct answer is 0.091 (3 d.p.)

C(15, 4) = 15! / (4! * (15 - 4)!) = 1365
C(11, 3) = 11! / (3! * (11 - 3)!) = 165
C(11, 4) = 11! / (4! * (11 - 4)!) = 330
C(11, 5) = 11! / (5! * (11 - 5)!) = 462
C(15, 3) = 15! / (3! * (15 - 3)!) = 455
C(15, 4) = 15! / (4! * (15 - 4)!) = 1365
C(15, 5) = 15! / (5! * (15 - 5)!) = 3003

P(A given B) = (1365 * (165 + 330 + 462)) / (455 + 1365 + 3003)

P(A given B) = (1365 * 957) / 4823

P(A given B) ≈ 0.270

Not sure where i went wrong :((

[frozen mason]

sorow reducing is not the way i suppose..

[dense copper]

can someone help

[cobalt mason]

If I simplify the formula by using rules of inference, wont I be left with 1? By applying inverse on XY and negate XY, also negate Z to Z? Is that correct?

[coarse token]

each person other than (but including your twin) you took a unique number of selfies between (0-6). You also took a selfie between 0-6 but your number can overlap.