discrete-math

[unborn pasture]

no i didn't know that second part

[coral parcel]

Ah, I thought perhaps the proof you're reading was phrased like that because that's how they worded the definition.

Can you state the exact definition you have of "a = b mod n"?

[unborn pasture]

I think of it as the definition, n | a - b

[coral parcel]

Okay.

[unborn pasture]

Didn't like think of the fact that a = b + kn

[coral parcel]

So "a = b mod mn" means "mn | a - b". And if a-b is some number that is a multiple of mn, then it is also (as Ann said) a multiple of n.

The proof you're reading is likely saying the same just with slightly different choices in how to write the formulas.
"a-b is a multiple of mn" is the same as "there is a k such that a-b = kmn" is the same as "there is a k such that a = b + kmn".

But then there is a different k such that a = b + kn -- namely our new k is just m times the old k.

[unborn pasture]

the solution is a little worse than that, but when you wrote it in words it become a bit more clear 🙂

I appreciate the help

[stoic cedar]

well i didnt make the question

and I dont know the answers

so

[unborn pasture]

Solve the Diophantine equation, 5x + 7y = 1. And check whether there are any solutions where x is a square number? (Examine 5x mod 7)
I solved the equation and found the general solution being 5(3-7n) + 7(-2+5n) = 1.
And for the second part i tried this: x^2 = 5x mod 7 and then i applied the modulus definition to it so: 7 | x^2-5, and found out that x has to be either 0 or 5 but im not sure if its correct or not. Any thoughts?

[coral parcel]

x^2 = 5x mod 7
Um, why? I would expect 5k^2 + 7y == 1 (mod 7).
(The 7y then immediately disappears)

[unborn pasture]

Somebody just try some values that makes 3-7n a square number, so im kinda lost now

I don't see why he would have "examine 5x mod 7" if the answer is as easy as for example 3-7(4) or 3-7(9) etc

[coral parcel]

But there are no integer values of n that make 3-7n a perfect square.

[unborn pasture]

Ill send a email to my profs and ask him

such a (not) odd question

[coral parcel]

Note that 3-7·4 is -25 which is not a square. 7·4-3 would be a square, but that's not what you found in the first part.

[unborn pasture]

perhaps that's the answer? The solution can not be a perfect square since it would result in a negative number

[coral parcel]

Not necessarily -- observe that if you set n=-10 you get x = 3-7·(-10) = 73, which is positive, but still not a square.

Checking mod 7 is really the way to see that there are no solutions with square x.

[unborn pasture]

yes exactly. I tried for some values that are negative and they all result a odd number.

[coral parcel]

Because x = 3-7n, you know that x == 3 (mod 7), but none of the seven possible squares mod 7 are 3.

[unborn pasture]

right, this here might be the solution. Using mod 7 as an argument ?

thank you for the help, once again!

[zenith oyster]

Can I ask help with a dumb math quiz question? I’ve exhausted all my interpretations of it curious if it’s allowed here

[rose wing]

https://www.youtube.com/watch?v=n4KKgKpp--0&list=PLUl4u3cNGP60UlabZBeeqOuoLuj_KNphQ&index=64
Optimal marriage problem (graph theory)
3:40 - 6:00
N and T is rogue, contradicts the fact N is optimal for K? Thank you

[signal goblet]

Thanks for the help man. I ended up coming with this (shortly after) and calling it a day:
S->a
S->aSb
S->abS
S->Sab
S->aS

[elfin marten]

what is persistence of a number ?

[stray reef]

did you see this in some problem you are doing rn? @elfin marten

[elfin marten]

yes

just curious to understand how to find a persistence of number using programmatical approach.

[rose wing]

Hello guys, anyone knows?

[weary tiger]

"Miss Smith, every student registered for this course has taken either a course in linear algebra or a course in analysis."

In this context, "or" is the inclusive or meaning a course in linear algebra or a course in analysis or both

But why? Doesn't the "either" seem to imply an exclusive or?

[final cliff]

You see how baaa ought to be in your language but the cfg you just wrote doesn't generate it?

The bit about S->ab was just a hint for how to approach part of the problem.

[stray reef]

@elfin marten late but you will have to post the problem you saw it in

[unborn oar]

how does that make any sense? how can something be symmetric and antisymmetric at the same time

[stray reef]

work thru the defns

[unborn oar]

?

[stray reef]

write out the definitions of symmetric and antisymmetric

and think about them

[honest holly]

If it’s both symmetric and anti symmetric, then what is the only possible relation?

[stray reef]

there is not just one relation possible under these constraints

[honest holly]

In essence yeah there is just one

But if you are strictly interpreting a relation as a set, then there are multiple, in fact, exactly 8

[signal goblet]

Whoops, good pickup. Perhaps, if I added the following three prod rules?
S->baS
S->Sba
S->bSa

So, the grammar would now be:
S->a
S->aSb
S->abS
S->Sab
S->baS
S->Sba
S->bSa
S->aS

Do you think there are any redundancies in this one, and was your solution any shorter?

[final cliff]

I don't know off the top of my head if that is correct. It seems like it makes sense? I know there are other grammars for this problem that work.

If it is correct you ought to be able to prove for M your given language and G the grammar you just gave that L(G)=M. Induction would probably be a reasonable approach.

If this grammar is not correct you ought to be able to either find a string in L(G) but not M or in M but not L(G).

You can (and probably should) spend time trying to find strings this grammar produces as well as derivations for known strings in M.

[final cliff]

Another approach I like to do is to generate all strings in (a+b)^* lexicographically less than a certain length to check these things on.

[signal goblet]

Appreciate the response. I typically do both of these suggestions (especially writing out the intensional definition of the language), and I did this with this question as well. It seems to satisfy all the test cases I have generated (may have missed some edge cases though, which may render it incorrect). I just assumed you had already worked it out, hence why I asked a question about your solution.

In terms of the formal proof, I probably won't end up doing that, given this is just one of the many practices questions I have had assigned, and would prefer to spend time on other questions that are more relevant to the upcoming assignments. Thanks heaps though :)

[weary tiger]

"Miss Smith, every student registered for this course has taken either a course in linear algebra or a course in analysis."
In this context, "or" is the inclusive or meaning a course in linear algebra or a course in analysis or both
But why? Doesn't the "either" seem to imply an exclusive or?

[little prism]

language is weird and ambiguous

[signal goblet]

^

[signal goblet]

Natural language grammars are very ambiguous (especially English). It really depends on the speaker. You could interpret the above sentence as inclusive or exclusive (1.1: note here how I have not specified the inclusivity or exclusivity of the "or" I just used... in this case, it is easy to infer that it cannot be both, as it is logically implausible to be both inclusive and exclusive -- a contradiction arises -- and so it must be an exclusive or); it really depends on the intended meaning the speaker is trying to convey. In mathematics, I believe the convention is to assume inclusive or unless otherwise specified. For example, if the above sentence was instead written:

"Miss Smith, every student registered for this course has taken either a course in linear algebra or a course in analysis, but not both."

Then, without a reasonable doubt, the intended meaning would be an exclusive or. I guess the takeaway is to not make any assumptions when dealing with natural languages, and always ask for clarification. In the context of set theory or formal logic, then it is reasonable to assume that it is an inclusive or, unless it is clearly specified. Do note that, linguistically, "either" can very easily be a precursor to an "or" - such is the case in the example you provided. So try not to treat "either" as strictly an exclusive or, especially in natural languages, as there is no universality in the usage of "either". It is, like most things in the realm of complexity, situational. Sometimes it is easy to deduce (like 1.1), and other times it is not. Hope this helps or perhaps it confused you even more (or both! 😆 ).

[toxic ermine]

Y'all, is cycles decomposition same as transposition decomposition?????

[ember obsidian]

no, transposition is a special kind of cycle

[toxic ermine]

What makes it special ?

[ember obsidian]

transpositions are 2-cycles. not all cycles are transpositions

[toxic ermine]

Oh, got it

@ember obsidian thanks:)

And is the decomposition same for both?

[restive topaz]

how to calculate
$$\sum_{n=1}^{\infty} {\frac{1}{n^2-1}}$$
known that
$$\sum_{n=1}^{\infty} {\frac{1}{n^2}} =\frac{\pi^2}{6}$$

[vital dew]

Akhil Rao

[stray reef]

those two infinite series have nothing to do with each other

also i think you might want to start the first one at n=2 unless you're adamant that you want to impale yourself

also i would suggest decomposing 1/(n^2 - 1) into partial fractions

[vale cairn]

(As an analogy, the integral from 1 to infty of 1/(1+x^2) is π/2, but the integral of 1/x^2 from 1 to infty is just 1 for example, and one of those is harder to compute than the other for sure - there's no reason they should be related as Ann says)

[restive topaz]

thanks always wanted to know as the sum of the inverse squares is $\pi^2/6$ but if just one is subtracted from the denominator then the result is 3/4

[vital dew]

Akhil Rao

[weary tiger]

\begin{align*}
A - (B - A)
&= {x \mid x \in A ~\text{and}~ x \notin B - A } \
&= {x \mid x \in A ~\text{and}~ (x \notin B ~\text{or}~ x \in A) }
\
&= {x \mid (x \in A ~\text{and}~ x \notin B) ~\text{or}~
x \in A}
\
&= (A - B) \cup A
\
&\supset A - B.
\end{align*}

[vital dew]

n/c

[weary tiger]

I need a sanity check to make sure that this proof of A - (B - A) \supset A - B works

The way I did the intermediate step was B - A = x in b and x not in a, so the negation of this would be x not in b or x in A

Then I distributed the conjunction over the disjunction to get to the third line

[stray reef]

third step is sus

however may i suggest proving that in fact A-(B-A) = A?

[weary tiger]

Why is it sus?

[stray reef]

im not sure and-or-associativity holds

basically, why is this rebracketing valid?

[weary tiger]

x in A = P

x not in B = Q

so we have

P and (Q or P) = (P and Q) or (P and P) = (P and Q) or P

@stray reef

[stray reef]

hm

ok

your argument still kinda smells

but i guess it's valid

[weary tiger]

How would you prove it then?

Without nothing that A - (B - A) = A by some note from God

[stray reef]

it's not a note from god, i can prove it

[weary tiger]

Okay but if you didn't know that...

[stray reef]

i can give an informal but rigorizable argument or i can element-chase in front of you

[weary tiger]

Just... you are asked to prove it, how would you prove it? Without starting your argument by saying note A - (B - A) = A and here's a proof

i.e. you shouldn't know that

[stray reef]

what, to prove that A-B subset A-(B-A)?

[weary tiger]

Yes

[stray reef]

element-chasing

[weary tiger]

But what's wrong with my argument?

[stray reef]

since you forbade me from acknowledging rhs is just A...

[stray reef]

nothing

as i said, its only fault is that it smells

[weary tiger]

What does that mean?

[stray reef]

it means i don't like it, for a reason impossible to put in words

it has a je ne sais quoi but in a bad way

if my dislike for it was stronger i would say it stinks

[weary tiger]

Can you show me your example proof then?

[stray reef]

do you still forbid me from invoking in any way shape or form the fact that A-(B-A) = A?

[weary tiger]

Unless you want to prove it as a lemma...

[stray reef]

is that "Yes, I forbid you from doing that unless you want to prove it as a lemma, in which case I'll allow it" or "No, I do not forbid you from doing that unless you want to prove it as a lemma, in which case it is forbidden"

[weary tiger]

I think the latter would be kinda a pointless thing to say, so the former

[stray reef]

nyeh ok fine element-chasing it is

let x ∈ A - B
from x ∈ A - B and defn of set difference, x ∈ A and x ∉ B
from x ∉ B and B-A ⊆ B, derive x ∉ B-A
from x ∈ A and x ∉ B-A and defn of set difference, derive x ∈ A-(B-A)

[weary tiger]

Okay that works

[native sandal]

hello guys

Would anyone know how to do this question

[pallid lintel]

Start by looking at the definition of "path", "trail", "circuit", "Euler circuit"?

I'm assuming someone has given them to you

[viral nebula]

How come the alternate sum of binomial coefficients multiplied with steadily in/decreasing numbers equal zero? For example: $$6 {4 \choose 0} - 7 {4 \choose 1} + 8 {4 \choose 2} - 9 {4 \choose 3} + 10 {4 \choose 4} = 0$$

It doesn't have to be integers either: $$3.3 {3 \choose 0} - 3.5 {3 \choose 1} + 3.7 {3 \choose 2} - 3.9 {3 \choose 3} = 0$$

[vital dew]

reking

[viral nebula]

Also, we can take powers of the increasing numbers: $$3^3 {5 \choose 0} - 5^3 {5 \choose 1} + 7^3{5 \choose 2} - 9^3 {5 \choose 3} + 11^3 {5 \choose 4} - 13^3 {5 \choose 5}= 0$$

[vital dew]

reking

[viral nebula]

The exponents must be integers though, and they must be less than n in (n choose k) otherwise it wont work

[vale cairn]

Second just looks like a consequence of symmetry of the binomial coefficients

But interesting

[viral nebula]

i dunno, isn't the sequence (1, 1, 1, 1) symmetric? Yet 6+7-8+9 is not equal to 0

[vale cairn]

Ah yes I've done this before actually, 1 sec

[vital dew]

potato

[vale cairn]

@viral nebula

[weary tiger]

do you know the relationship between n choose k vs n choose n-k @viral nebula

[viral nebula]

if n is odd its pretty trivial, and if n is even.. hmm

[vale cairn]

Yeah so I'll give you a hint - what's $\sum_{k=0}^{n} x^k {n \choose k}$?

[vital dew]

potato

[vale cairn]

It turns out considering this function gives a nice solution to your general problem which hopefully you'll enjoy! :)

[viral nebula]

i'm still not sure why this is true for even n

maybe i need to use induction to show it

[vale cairn]

Yeah so consider this

Hint: binomial theorem (in reverse)

Hint: ||Note x^k = x^k 1^(n-k)||

[viral nebula]

oh, yes, i've seen this before i just had forgotten it...

[vale cairn]

Sure nws

But yes, plugging in -1 then gives you that warm up thing I said

Now to generalise it to summing (-1)^k k^m (n choose k) , you'll want to differentiate before plugging in -1.

[viral nebula]

and this is just (1+x)^n

[vale cairn]

Then once you've shown all of those are zero, you've proven that for any polynomial p, the sum of (-1)^k p(k) n choose k is zero. This then proves all the examples you gave

[vale cairn]

Yup

I need to go to sleep but I hope that points you towards the solution and I'll be around tomorrow if you have any more questions

[viral nebula]

sure, thanks!

[serene marlin]

if there is a god how do u do 12 e, I have spend nearly 2 hours in a call with my friend and we cant figure this shit out

[stray reef]

nearly 2 hours? despite there only being 16 possible relations in total on A?

that's a little overkill

in those 2 hours you would've had like 7 full minutes to study every single possible relation

anyway, you can represent relations on A as tables

[serene marlin]

I did and I think I might be retarted

cuz i dont see it

my friend put (1,2)

but isnt that transitive?

[stray reef]

you mean {(1,2)}?

[serene marlin]

ya

[stray reef]

hm

ah wait

something's telling me you need at least 3 elements in the base set to break transitivity

[serene marlin]

thats what I was thinking, but I couldnt crack it

[stray reef]

did y'all manage (a) then

[serene marlin]

ya i did a-d

[stray reef]

what's your thing for a

[serene marlin]

a is {1,2),(2,1)}

[stray reef]

ah.

right.

well we can't have both (1,2) and (2,1) this time because that'd mean our relation is symmetric which we need it NOT to be

[serene marlin]

ya

does it dne

[stray reef]

think it might.

[serene marlin]

Ima jsut write a note saying I tried everything and its not possible, so DNE
c

cuz idk

[weary tiger]

Yeah it's not

To break transitivity you need at least two elements

But any combination would make it reflexive or symmetric

[serene marlin]

That question should not be phrased like that tf

Every time we get a ? Where it’s might not be transitive or something it says prove or disprove

This one just says find it

[stray reef]

theres only a handful of relations possible with the constraints of non-symmetry and non-reflexivity and non-emptiness

all of these are transitive

[serene marlin]

I’ll keep u guys updated with the answers when we get th assignment and AK back

Thanks tho for the help

[halcyon dock]

Hola

{5x−1 : x ∈ Z}
I want to list a few of the elements in this set. How do i find some elements without sitting here and plugging in a bunch of integers?

[serene marlin]

start at -1 and go up by 5 each time

[ember obsidian]

thats p much the only way

[halcyon dock]

{...−11,−6,−1,4,9,14,19,24,29,...}
I guess I could plug in all these numbers and make a rule that if the number divisible by 5 when you add 1 like RickRoss said, it is in the E, but I am looking for some kind of way to solve for all elements in this, is this possible ignoring the fact that is an infinite set?

[ember obsidian]

wdym 'solve for all elements'

it sounds like 'explicitly write each one' which is impossible bc the set is infinite

[halcyon dock]

Gotcha don't judge me senpai

lmao jk thxs guys

[ember obsidian]

yw

[weary tiger]

How to reason through what {x : x in A and (x in B implies x in C)} contains?

The set {x : x in B implies x in C} is the tricky one

The statement is true if x in B and x in C, or if x not in B.

So it is the set of all x that is in B and C union the set of all x not in B???

So something like (B n C) u (B^c)...

[honest holly]

$A\cup (B\cap C) = (A\cup B ) \cap (A\cup C)$

[vital dew]

Andrew071

[weary tiger]

Why did you post that

[honest holly]

that's what your set in question is

[weary tiger]

No it's not

[weary tiger]

How?

[honest holly]

it's clearly A union something

what is x: x\in B implies x\in C?

[weary tiger]

Sorry it should've been an 'and' not an 'or'

[weary tiger]

I don't know that's the tricky part

[honest holly]

it's B intersect C

[weary tiger]

No it's not..

[honest holly]

how is it not?

[weary tiger]

Because the statement will be true even if x is not in B

[honest holly]

yes but you have A intersect some set

[weary tiger]

Yes, A intersect some set is right

But it's not B cap C

Because the statement will be true even if x is not in B

Which doesn't make any sense in that case

It's only B intersect C if x in B.

[honest holly]

oh okay

[weary tiger]

Like you're assuming x in B, but that's not true

It's the statement (x in B IMPLIES x in C)

We care about the truth value of the statement

[honest holly]

yes but when you write ${x: P(x)}$

[vital dew]

Andrew071

[weary tiger]

okay let me try another way...

[honest holly]

i know what u mean

$(B\cap C) \cup B^c$

[vital dew]

Andrew071

[honest holly]

if u want vacuous truth

[weary tiger]

Suppose $B = {1,2,3 },~C = {1,2 }$. Then $B \cap C = {1,2}$, but $x \in B \implies x \in C$ is true for $x = { \dots,-2,-1,0,1,2,4,5,\dots }$

[vital dew]

n/c

[weary tiger]

Which is not B intersect C

Yeah but how do you simplify that further?

I need to use \cap, \cup, \setminus

[honest holly]

$C$

[vital dew]

Andrew071

[weary tiger]

what

I just showed in my example above it is definitely not C

[honest holly]

sorry $B^c \cup C$

[vital dew]

Andrew071

[weary tiger]

I mean how do you simplify B^c

[honest holly]

A - B

[weary tiger]

Why? Who says A is the 'parent' set of B?

[honest holly]

okay because you have $A\cap(B^c \cup C) = (A\cap B^c) \cup (A\cup C)$

[vital dew]

Andrew071

[honest holly]

so it doens't matter what your set universe is

and of course A-B = A intersect B^c

[weary tiger]

It can't be A cup C even if A cap B^c = A - B

Because look

Using propositions:

[honest holly]

yeah it was a typo

it's A cap C

[weary tiger]

Anyway the book answer is A - (B - C)

but I don't know how to get there

[honest holly]

that

is exactly what I wrote

you can check that $A-(B-C) = (A-B)\cup(A\cap C)$

[vital dew]

Andrew071

[weary tiger]

I mean I can prove that relationship yes but I don't know how to "reason" through it

If you didn't know what you had to prove

[honest holly]

i mean because intuitively (A-B) takes away all the B from A

[weary tiger]

So there is some kind of manipulations to do, to get that form without proving they're equivalent

[honest holly]

and then you add to that all the stuff in both A and C

but it's of course possible that some of that stuff contains stuff which was in B previously

so really what did you take away at the end? all the stuff in B-C

[weary tiger]

Alright thanks, yeah I think that works. Just think about removing all elements of B from A, and then adding back all elements in both A and C is the equivalent of removing all elements of B in A except the ones that are in C

[serene marlin]

can someone explain this theroem in english? i have no idea what its saying... From what I understand

there exits a prime number x and if another number is prime y, then there exists a prime number z such that y<z?

[stray reef]

yes, that's the literal translation

a better translation would be, "There exists at least one prime, and for any prime there is a bigger prime"

or, "There are infinitely many primes"

[true bridge]

Would the correct choice for this be nCr(26,9) * (9-1)[!(9-1)+!(9-2)]

I.e. for each permutation of the keyboard, there are 9 different derangements of the swapped keys

[serene marlin]

Ok this makes more sense

Thanks

[unique elm]

how do we write "there are infinitely many primes" using quantifiers

[little prism]

for example like this

[honest holly]

Let P be the set of primes

P is not empty and for all p in P there is a q in P with q>p

[weary tiger]

not to ruin your fun but
isn't the function just n+2?

ah

[unique elm]

tysmm

[lusty fern]

Taking discrete math in the fall, it’s been a while since I had a math class

I heard it’s proofs heavy, any resources to brush up on proofs?

[coral parcel]

It's usually part of discrete math courses to introduce techniques and conventions of proof, not a prerequisite.

They're generally designed for students fresh from high school who have not seen much proof and are not taking any other math

[molten dirge]

When proving a proposition of the form P(n,m) (n&m non-negative integers), is it valid to (strongly) induct over n+m (i.e. base case n+m=0, inductive assumption P(k,l) true for k+l<n+m, prove P(n,m))?

[little prism]

yes

[serene marlin]

whats being said here exactly? im confused on how this proves it is one to one

[weary tiger]

they showed that $f(x)=f(y)\implies x=y$ which is exactly the definition of an injection

[vital dew]

jswatj

[serene marlin]

ok, but can you also explain why exactly this is the definition, how does the definition prove that no image appears twice

aka how does this show that it proves the Horizontal line test

[little prism]

well if it doesn't pass the horizontal line test, then there are two different x,y with f(x)=f(y)

so in that case f(x)=f(y) does not imply x=y

[weary tiger]

^

[serene marlin]

elite definition

thank you

makes sense

[ember obsidian]

@serene marlin the def may be nicer to think about by taking its contrapositive

ie x!=y implies f(x)!=f(y)

in english, distinct inputs have distinct images

[hidden cosmos]

What does the first statement even mean?

Like isnt that just the null set?

Since the condition wont be true for any set

[dreamy lagoon]

That's not true, it'll be true of most sets

W = "all sets that do not contain themselves"

[whole kite]

Can someone help with this graph theory question

A planar embedding P has 102 vertices and 300 edges. Prove that P is connected.

I've already proved as part of previous subquestions that P has 200 faces, each of degree 3, and that P has at least one cycle

[hidden cosmos]

By definition wouldnt a set contain itself

Wait also idk if this is where Im mistaken but "containing" is the same as being a subset of right

Or does it literally mean that the set has to be an element of itself (which seems like it would lead to infinite recursion?)

[whole kite]

no containing refers to it actually being an element of the set

[hidden cosmos]

So that would lead to it being infinitely recursive right

[whole kite]

it is kinda an infinite recursion

[hidden cosmos]

Oh ok

So like

[whole kite]

yea so you could have a set A={1, 2, 3, A}

and it contains itself

[hidden cosmos]

Right, so A = {1, 2, 3, {1, 2, 3, {..}}}

[whole kite]

yea

[hidden cosmos]

That makes sense thx

[whole kite]

but self-containing sets don't show up much to my knowledge outside of Russel's paradox

[hidden cosmos]

Yeah it seems a bit niche lol

[tacit breach]

so, im not fully understanding what my teacher is explaining in class, ill post his own screenshots of his notebook that he posted to google classroom, im in a 12th grade discrete math class
its abt trading places and the jumping frog problem

i understand his mostly

but i dont get the bottom section, where he attempts to answer "What is the minimum number of moves required if there are n frog each"

any help would be much appreciated

idk where else to ask, so if theres a better channel, lmk, new to the server

[austere socket]

Can someone help me

I am solving past papers
And i cant prove why log(135...2n-1) is Θ(nlogn)

[olive wren]

Well, its less than log((2n-1)^(2n-1))=(2n-1) log(2n-1), and it’s greater than like log((n-1)^(n-1))=(n-1)log(n-1) or something (since it’s greater than (n-1) n (n-2) …), and these are both Θ(nlogn)

[austere socket]

Thank youuuuuuuuuuu

[olive wren]

[spark silo]

if i have the letters A P P L L E

how would i go about finding out how many arrangements of this have consecutive P's? thank you 😄

[olive wren]

Think of PP as one letter, so you can think of it as having a 5 letter word, with 1 A, 1 PP, 2 Ls, and 1 E

[spark silo]

ok i see where you're coming from, although im a bit rusty with even this still. is it just 5! then?

[olive wren]

No because there are 2 Ls

5!/2!

[spark silo]

i dont understand, why do the 2 L's change anything? isnt the permutations of A PP L L E just 5!,

ohh do we divide by 2! because the L's can be swapped & arrive at the same arrangement?

so if i was to have the word

A B B C C C D D D D PP
it would be 11!/(4! x 3! x 2!)

[unique abyss]

Yeah 👍

[spark silo]

okay that clears that up thankkks! one more question though 🙂
if i was to have the A P P L L E question but i wanted to find out how many do not have two P's or two L's consecutively, would this working out be correct:

no two P/two L = total - consec P - consec L + consec P&L

total = 6!/(2! * 2!)
cases with consective P's = 5!/(2!)
cases with consecutive L's = 5!/(2!)
then i need to remove the overlap with both of these permutations:
cases with consecutive P & L next to each other: 3! * 2 (could be PPLL or LLPP so i have to multiply by two?)

so it would be: 6!/(2! * 2!) - {[5! x 5!/(2! x 2!)] - (3! * 2) }?

[olive wren]

Your intersection (overlap) is incorrect, think of PP and LL as a single letter, so you have 4 letters (A, PP, LL, E) and you get that it is meant to be 4!

[spark silo]

oh true idk why i thought they had to be next to each other. thanks! 😄

[proper marsh]

Hello! Im trying to solve this Diffie-Hellman protocol problem. Im stuck on the mod chart section. Where i put the question mark, i dont think its correct. I know im supposed to subract by the mod to get a remainder but i think that product is way too large

i also saw this same question posted to chegg however they didnt show all the work involved so it doesnt help me much other than give me the end result

[wooden remnant]

What is descrete maths?

[restive topaz]

I am able to calculate an upper and lower bound for $\sum_{p} \frac{1}{p^s-1}$. From this can I know anything about the sum $\sum_{p} \frac{1}{p^s}$ and deduce the bounds for the sum.

[vital dew]

Akhil Rao

[vale cairn]

p^s > p^s -1 so the second sum is smaller than the first, which gives you an upper bound

[restive topaz]

and anything about the lower bound?

[noble goblet]

in depth math

ig

[weary tiger]

discrete math is about countable sets

countable stuff usually

usually stuff with limits are not considered discrete math

[wooden remnant]

Iam new to this channel.... What kind of math is discussed here

[little prism]

scroll up 5 lines

[vital dew]

n/c

[weary tiger]

Does this work?

[weary tiger]

<@&286206848099549185>

[honest holly]

Yes but can’t you just do

f o g o g^-1 o f^-1 = Id

[vale cairn]

$x \in (g \circ f)^{-1}(C_0)$ iff (g \circ f)(x) \in C_0$ iff $f(x) \in g^{-1}(C_0)$ iff $x \in f^{-1}(g^{-1}(C_0))$

[vital dew]

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

[vale cairn]

that's be what I'd be inclined to do more tersely but yeah it seems yours works

[vale cairn]

This assumes f,g are invertible, which needn't be the case

(since we're talking about preimages of sets, not actual inverses)

[weary tiger]

no because f^-1 is not the inverse of a value, it is a set

[weary tiger]

I understand but I did mine in more detail so as to not fool myself into thinking I understand why those implications happen

(in case I didn't)

[vale cairn]

Hm okay, all of my implications follow immediately from definitions though

[weary tiger]

I agree but also I think most math problems that aren't too advanced are just unfolding definitions 🙂

[west grove]

Tell me if I'm waaaay off course but I'm assuming (approximately 40 pages into a graph theory textbook) that you can prove two graphs are isomorphic because the set of all vertex degrees in one graph is equal to the set of all vertex degrees in another? Am I somewhat correct?

Like one graph has a set {1, 2, 3, 4, 5} and the other has a set {2, 4, 1, 3, 5}, but they're equivalent and thus the graphs are isomorphic

[pallid lintel]

I think you want to preserve adjacency relationship between vertices as well.

If you know what an adjacency matrix is, you'd want their adjacency matrices to be exactly the same (your allowed to relabel vertices and edges to get the same matrix)

two graphs can have same number of vertices and same degree on each vertex and not have the same structure. For example two vertices with 2 parallel edges to each other is not isomorphic to two vertices with a loop on each vertex. Tho, im not sure if your allowed those things in your graphs

[west grove]

ohhh ok

tysm

[patent plaza]

Hello everyone, I wanted to know what are your thoughts for Discrete Mathematics and application by Susanna S. Epp

I'm new to solving proofs and saw a video recommendation on this book

[meager prairie]

you may try #discussion

if u dont get the response you want here

[patent plaza]

thank you

[unique elm]

Hey everyone

quick question

can an implication and its converse be false?

ik that the truth values of an implication and its converse are generally not related

but like is it necessary that one of them is true

[brisk sluice]

no not necessarily, they can both be false

[unique elm]

how tho

yeah

again, how

if you draw the truth tables for p->q and q->p

there isn't a single row where they are both F

[vale cairn]

Sorry ignore me

I meant they can both not be tautologies lol but yes

[unique elm]

visible confusion

sooo.... is it possible orr

[brisk sluice]

do you mean that if you take 2 random statements P and Q, you have either P => Q or Q => P ?

[unique elm]

no i mean

can P=>Q and Q=>P be both false

[brisk sluice]

yeah so if at least one of them is necessarily true

it’s the same thing

[unique elm]

no what

P=>Q is false AND Q=>P is false

[brisk sluice]

yeah i get that

[unique elm]

yeah so can this statement be true

hello?

[weary tiger]

I mean
if one = ~(the other) then sure

[unique elm]

example plz....

like

u mean

nah idk what u mean

[weary tiger]

I mean that p -> ~p is false and ~p -> p is false too

[unique elm]

like

X=4 ---> X=/4

[weary tiger]

mhm

[unique elm]

how would that even make sense

[weary tiger]

yeah that's why it's false

[unique elm]

what abt the truth table tho

if you wrote all the possibilities for P and Q

and found the truth values of P=>Q and Q=>P

there wouldn't be a row where they're both false

[weary tiger]

I mean
for them both to be false one has to imply or be the negation of the other

[unique elm]

yeah i don't get it. ...

[brisk sluice]

take for example P = "x is even" and Q = "the gcd of x and 9 is 1"

P => Q and Q => P are both false

[unique elm]

gcd being?

greatest common what

[brisk sluice]

greatest common divisor

[unique elm]

why would P=>Q be false in that case

[brisk sluice]

if x = 18 the gcd would be 9

and 18 is even

[unique elm]

ohhh

right

[brisk sluice]

so P => Q is false

[unique elm]

and if we take Q=>P

[brisk sluice]

Q => P is false too since you can take x = 5 for example

5 is not even but gcd of 5 and 9 is 1

[unique elm]

yeah yeah i see

but i'm confused as to why this doesn't show using a truth table

[honest holly]

Wdym

[serene marlin]

can someone explain whats going on here as if I was a 12 year old

[honest holly]

Because given the expression (a+b)(c+d)(e+f)(g+h)… how do you expand it

You pick either a or b

Say a

Then you pick either c or d

Say c

Then you pick e or f say f

And finally you pick g or h say g

Then you multiply all of them together and get acfg

that’s one term

We have 2^4 terms in total to sum up

To get the order 2^4-1 terms you just repeat this process

So for (x+y)(x+y)…(x+y) n times, from each (x+y) you pick one term

But you can only either pick x or pick y, and #x you pick + #y you pick must add to n

So for that one term you have x^ky^{n-k}

But there’s n choose k different ways to get x^ky^{n-k}

So you will end up with n choose k multiples of the term x^ky^{n-k}

The only observation here is that to multiply a product of sums, ie (a_1+b_1)…(a_n+b_n), the result is the sum of 2^n terms and each of these terms can be obtained by multiplying X_1X_2…X_n where X_j is either a_j or b_j

[serene marlin]

ahh

that makes sense

ty boss

[opal summit]

can anyone help with this?

[weary tiger]

which part

[opal summit]

all, if possible

🥺

[weary tiger]

Start with a) what do you think?

It should be straightforward

[knotty goblet]

T(n) = T(n-1) + T(n-2) + .... + T(1) + T(0) + n

how do u solve this?

I got T(n) = 2^nT(0) + n * 2^n

T(0) is the base case as it does a constant amount of work, k

but can the time complexity really be O(n * 2^n)?

shouldnt it be O(2^n), lol idfk

[olive wren]

,w T(n) = T(n-1) + T(n-2) + n

Meh n*2^n seems plausible, since T(n)=T(n-1)+T(n-2) has complexity 2^n, so by adding n it makes sense that the complexity would be n2^n

[weary tiger]

I am trying to prove that for a partition $\mathcal{D}$ of $A$, $\mathcal{D}$ is determined by an equivalence relation on $A$.

Define a relation $\sim$ on $A$ by $(x,y) \in \sim$ if $x$ and $y$ belong to the same element of $\mathcal{D}$. Proof: suppose $x \in S \in \mathcal{D}$. Then $\bigcup_{S \in \mathcal{D}} S = A$, so there is a $x \in S$ for each subset $S$ of $A$, so $x \sim x$. Now suppose $x,y \in S$. This means that $y,x \in S$, and so $x \sim y \Rightarrow y \sim x$. Now suppose $x,y \in S_1$ and $y,z \in S_2$. Since the elements of $\mathcal{D}$ are disjoint, $S_1 = S_2$ and so $x,y,z \in S$ and so $x \sim y$ and $y \sim z \Rightarrow x \sim z$

[vital dew]

n/c

[weary tiger]

Any feedback?

[little prism]

you should argue why S1 and S2 can't be disjoint

[weary tiger]

Because y is in both S1 and S2, so y in S1 cap S2, and S1 and S2 two disjoint subsets of A or equal which implies they're equal

[little prism]

yep

[knotty goblet]

sorry, i wrote the recurrence incorrectly

its actually T(n) = T(n-1) + T(n-2) + .... + T(1) + T(0) + n

[signal goblet]

Anyone know a grammar that can produce the language over {a, b, e, f}, where each string is at least four symbols in length and the number of a's and f's is equal [num(a)=num(f)]?

[olive wren]

Well goddamn that’s like some terrible complexity. Something like n^n maybe

Or maybe n^log n

[final cliff]

You could be real shitty and just give the grammar S->aaff. The only string generated by this grammar is aaff, which satisfies all the requirements you gave.

[serene marlin]

how do we find how many tetrahedra triangles are there
is it just c(25,3) + 22
25 choose 3 being the number of triangles there are
and 22 being the number of remaining points to choose from to complete the 4 pointed tetrahedra

[final cliff]

Why + and not times?

[serene marlin]

good catch, it should be times

is that the only error?

[final cliff]

Idk, it just seems like you're picking three from your set of 25 for the base plane then 1 from the remaining set of 22 for each tetrahedra ig.

[serene marlin]

thats what i think too

[final cliff]

Could you maybe also do it as 25 choose 4?

[serene marlin]

but i remember doing this question earlier in the year and it being much more tricky

[serene marlin]

i dont think so

cuz

you can have 2 points on one plane

and 2 on another

so it would just make a rectangle

or something

[final cliff]

No four are coplanar

Three points always lie in some plane

So three of your four points ought to determine a plane containing one face of your tetrahedra

The fourth determines the rest of the tetrahedra ig? Lol

[serene marlin]

why does that take away the possibility of 2 points being on the same plane

[final cliff]

Any two points will be on infinitely many planes

Two pts determine a line right?

Given a line how many planes intersect the line?

[serene marlin]

ahh

ok

that makes sense

thank you

ok so now another question arises

[final cliff]

Maybe I'm mixed up tho

[serene marlin]

no ur right

[final cliff]

Because for what I'm suggesting to be true

[serene marlin]

i remember my ta with this answer

but my question is why doesnt the c(25,3)*22 work

its a differnet number

[final cliff]

We would need (25 C 3)22 = (25 C 4) right?

Which it's not lol

[serene marlin]

wait one sec lol

ohhhh

fuckj

ok ya ur right they dont equal

but why like what is c(25,3) *22 calculate

like how does that not calculate the mount of tetrahedrta

number of triangles times remaining points

[final cliff]

(25 C 3)22 should be the number of ways to pick a set of 3 points from a set of 25 and then to pick a set of one point from the remaining 22.

(Typo)

[serene marlin]

"number of ways to pick 3" is that not the number of possible triangles and then the "pick a set of one from remaining 22" just completing the triangle to make a tetrehedra

fuck discrete math is so fun when u get it

an so anoying when u donty

[final cliff]

That's what I was thinking too

Well wait? No four are coplanar, but could picking three at a time not give us a face?

Ah maybe not.

I was thinking maybe three could be colinear

But then picking a fourth pt would give us four coplanar pts which is contradictory.

[serene marlin]

aghhhhh

idk man maybe its just that time where i just pray something similar isnt on the exam

[final cliff]

It feels like there's gonna be a super obvious reason why one of the two counts doesn't work. It's better to just figure it out.

I'm trash at combinatorics stuff lmao

Actually ya know maybe your first answer over counts

Say you have a tetrahedron given by picking {a,b,c} then by picking {d}.

You can also produce the same shape by picking {a,b,d} then picking {c}.

Yah, I think your original answer just over counts is all. The two examples above get counted as distinct tetrahedra when they aren't.

You don't have this issue when you pick four points at a time all at once I think.

[serene marlin]

i think that makes sense lo

lol

thatnks alot for the hekp

[signal goblet]

That wouldn't be a grammar that produces a language over the entire alphabet though, so wouldn't it be incorrect?

Maybe not incorrect, but probably very strange

I have a grammar that can do equal a's and f's, and I know how to restrict it to min 4 symbols, but I can't fuse these two ideas together

Have tried a lot of different ways

No luck so far .-.

[final cliff]

So, here's how sipser defines these terms: "A string over an alphabet is a finite sequence of symbols from that alphabet." <- this does not require the individual strings use every symbol from the alphabet. "A language is a set of strings."

Idk how ur specific course defines a language over an alphabet fwiw

[final cliff]

The question you asked is just kinda vague ig

When you say "a language"

Satisfying the conditions you gave

There are many languages that satisfy those conditions.

[signal goblet]

Yeah I get what you're saying, but its just redundant to include symbols in the alphabet that cannot be generated. Wouldn't really be "a language over the alphabet", more like "a language over half the alphabet". Irrespective, the question provides examples of valid strings that use all symbols, so I'd need a complete one

And oops my bad

I meant "the". That's my fault for being imprecise. Sorry about that

So a grammar for the language where such and such

[final cliff]

I disagree with this line of thinking, I think it literally just depends on how you define the phrase "a language over an alphabet", speculating about it is kind of a waste of time.

The bit about "the"

Like I said, there are many languages satisfying those conditions.

In fact infinitely many

I think what the q really wants is the set of all strings satisfying those conditions?

[signal goblet]

Yes. Is that not what a language is though?

[final cliff]

I think you're misunderstanding me.

There are MANY distinct sets satisfying each of those conditions you gave.

There is ONLY ONE set containing ALL the strings satisfying your conditions.

Here

https://en.m.wikipedia.org/wiki/Formal_language

[signal goblet]

Let me rephrase the question to eliminate ambiguity.

Language M is the set of all strings over the alphabet {a, b, e, f}, where each string, w, in this language, satisfies the following properties:

• |w| >= 4;
• num(a)=num(f) (i.e., there are an equal number of a's and f's in the string).

Give a grammar whose language is the same as language M.

[final cliff]

"A formal language L over an alphabet Σ is a subset of Σ*, that is, a set of words over that alphabet."

^does not require L contain strings having every letter from sigma

It's kinda like where a function in some cases can have more than one codomain ig.

[signal goblet]

I am aware that is isn't a requirement, but it is pretty odd or at least not very common to not include all members of the alphabet. Regardless, this isn't something worth discussing in my opinion.

[final cliff]

You brought it up because you didn't like my answer, my answer worked because the question was phrased ambiguously due to the issues I pointed out.

It doesn't matter if it is odd?

Sometimes questions just have goofy trivial answers lmao.

Usually it's just poor wording or something ig?

[signal goblet]

It's not that I don't like it, it's that it would be incorrect, given the question provides examples that use all members of the alphabet

[final cliff]

I don't see how specific examples make my answer wrong?

[signal goblet]

And I am certain it is referring to the language that contains all symbols

[final cliff]

It sounds like they asked for one thing when they wanted something else?

Okay, then they should ask for that?...

Either way, for your new question I guess you can at least narrow it down?

Certain things have to happen ya know?

Anytime a rule emits an a it has to emit an f for one.

You can also start from the smallest cases and see how you can extend them to the general case

For ex aaff is one of the smallest possible strings

So _a_a_f_f_ where\ _'s represent strings satisfying ur given reqs will also be a string in ur language I think.

(Oops formatting)

[signal goblet]

Perhaps, but it I know better by now that it is fair enough to assume so (at least in my coursework), and given your answer (as you specified it was a "shitty" way), it seems to me that even you knew it wasn't the typical way of looking at it. Anyway, I get your point :)

Yeah, I'm just having a hard time enforcing the minimum of 4 characters with it

[final cliff]

Imo, you should know the defn of a language over an alphabet for your course and you should point out when a question your being asked is ambiguous enough to provide "shitty" trivial answers.

If you're catching that kind of stuff other people are probably also just as confused as you ya know?

One possible strategy is something like S->RaRaRfRfR|... where R is some other rule to generate strings matching the number of as/fs condition?

[signal goblet]

I've already asked for prior questions and prof said to assume that we will only give you questions where such is the case. The question is publicly available for other students to see as well. But yes, fair enough

[final cliff]

... here as in go thru all other possible base cases.

[final cliff]

I hate when they do that lmao. It's not your fault when they write badly worded questions.

Mmm have you done a cfg for a string that produces the same number of a's as f's?

I know that's a common exercise, it should be in sipser somewhere I'd imagine

You'd have to modify it for ur own alphabet though.

Because usually it's done for alphabets like {a,f} in examples.

[signal goblet]

Yep, was just about to send it:
S->SASFS|SFSAS|e
A->a
F->f

That's the most concise one I've discovered so far

e is empty string btw

Oops

[final cliff]

Oh yeah, then if that alphabet is correct then use it for R

(So replace all R's with S's ofc since my suggestion already used S)

You still need to modify it to include the other symbols of your alphabet I think?

[signal goblet]

Yeah, this is something I've had a hard time with as well

Because your suggestion is good, but it implies you must have 2 a's and 2 f's

Unless I did a bunch of combos possibly?

[final cliff]

Okay so there are two diff problems here ig

[signal goblet]

There are many at this point 😆

[final cliff]

The first one is when do we emit bs and es?

But for this problem I think you can just emit any string of bs and es before/after you emit an a or f.

Unless I'm mixing something silly up.

[signal goblet]

Yes, though, we must also cater for bbbb eeee bbee etc

Since there can be no a's or f's

And still satisfied ig

[final cliff]

Here that all should be satisfied when you brute force out all the strings of len 4 over your alphabet that satisfy your conditions

So for ex since afeb is one such string you would include S->RaRfReRb as one of your productions

[signal goblet]

Ah I see

Brute force allt he possible positions a and f can be

[final cliff]

Well brute force all length 4 strings in {a,f,e,b}^* and then pick out the ones that are in your language then interleave R's and stuff

You'll probably need an S->epsilon rule too

[signal goblet]

Wouldn't that be 256 prod rules if I'm not mistaken

[final cliff]

Could be lmao

[signal goblet]

If you're including all possible permutations of a,f,e,b in a 4-symbol sequence

[final cliff]

Probably not though?

4^4 should be too many

There are 4^4 length 4 strings in {a,f,e,b}^* but we want the subset of those strings that are actually in your language.

[signal goblet]

But having to sift through all of those... 😞

[final cliff]

You can probably use some reasoning to cut it down without literal brute force

[signal goblet]

Hmmmm

Any suggestions?

I think I may have stumbled upon something

[final cliff]

The only way I can think of is to either (a) generate all 256 or so lexicographically and remove the ones not in your language (b) consider ways to arrange no a's and f's one a and one f and two a's with two f's then interleave the remaining chars as necessary.

Both are kinda wonky.

[signal goblet]

S-> afSS | SSaf | aSSf | aSfS | SafS | SaSf | faSS | SSfa | fSSa | fSaS | SfaS | SfSa | SSSS | SS | K
K -> af | fa | b | e

No clue if that holds

Trying to find a counter example

Oh waiut

b e

[final cliff]

I like your thinking on it I'm trying to think up a counterex or if there are excess productions?

[signal goblet]

be

[final cliff]

Ah shit yeah

[signal goblet]

SS -> KK -> bb :(

So close but so far

I mean I could probably do the same thing I did with af/fa with be/eb?

That would be very long

But it might work?

[final cliff]

That's kinda close to what I was going for at the start?

You want your derivations to always end up emitting at least 4 symbols.

I guess you could maybe chunk it up and have a rule that emits b or e to cut down on certain cases too?

[signal goblet]

Ok here we go:

S-> afSS | SSaf | aSSf | aSfS | SafS | SaSf | faSS | SSfa | fSSa | fSaS | SfaS | SfSa | beSS | SSbe | bSSe | bSeS | SbeS | SbSe | ebSS | SSeb | eSSb | eSbS | SebS | SeSb | SSSS | SS | M | K
K -> af | fa | be | eb | ee | bb
M -> aaff | ffaa

[final cliff]

Uh, for ex afee, afeb afbb etc can be generated by a single rule afHH where H->b|e

[signal goblet]

cant do eebb

ffs

now u can

Also cant do aaff, yeah this isn't working

[final cliff]

So, like with the S->RaRaRfRfR|... cases like abHH cut down on a lot of permutations.

Your cases look like HHHH, all ways to interleave a,f with two H's and all ways to arrange two a's an two f's.

[serene marlin]

how does one B

[signal goblet]

Hmmm yeah

[final cliff]

What is that? Like 29-ish such sequences?

[signal goblet]

Your one, or the one above?

[signal goblet]

Also, how does this look

[final cliff]

This one

Then you just interleave Rs and junk ig.

[final cliff]

I'm honestly not sure

[signal goblet]

It cant do aaafff

[final cliff]

It feels like both of our approaches would eventually lead us to a solution

[signal goblet]

This is pure frustration

[final cliff]

But that there is probably a more elegant solution too

[signal goblet]

Yeah I have a feeling there is a really nice concise one

That I'm overlooking

It's probably simple too

[final cliff]

Same

I wouldn't feel to bad about it lol

[signal goblet]

I have a feeling that if you try to do any sort of permutation idea that we tried, it'll give you those ugly long ones

[final cliff]

These problems always sound like they should be easy but they can be really subtle

It's not so bad if they're long but well organized.

[signal goblet]

My intuition tells me that the solution lies somewhere in starting with a single S, and building your way up using something like this

S->SASFS|SFSAS|e
A->a
F->f

[signal goblet]

Yeah, I'm not a huge fan, since it feels like more of an art rather than a science

Just trial and error and see how you go, while gradually building up more and more experience

[final cliff]

There's not much of a point in A->a and F->f here

[signal goblet]

Yeah not in that one

[final cliff]

Well you want to logically build up the solution using stuff like induction and breaking your language up into logical chunks.

For ex if your lang is a union of two easier ones then S->(gen the first lang)|(gen the second lang) works.

[signal goblet]

Yeah that's true, there are a lot of patterns - as in all mathematics ig

[final cliff]

The approach I was going for here was to try and find a way to enumerate the base case in a nice organized way.

Then use that enumeration to build up the rest of the language inductively (which was the point of the R's)

[signal goblet]

Oh, I completely missed that

That's a good idea

[final cliff]

See here

aaff is one specific instance of the base case

[signal goblet]

Yep I saw it, but didn't realise that's what u were doing

[final cliff]

Yeah fafa would be another

So you'd also want a production S->RfRaRfRaR

Once you enumerate all four letter elements of your language you can just interleave R's

Then build R so that it generates all strings containing same num of a's and f's like we discussed.

With the R production, you want to also make sure any time you emit something like a that you emit any number of b's and e's around the a (and so on for f)

But that's just a simple modification of one of your prev grammars you mentioned.

[final cliff]

And you can cut down on the work with this

Because if H->e|b then faHH matches faee and faeb and so on.

So really you just need to enumerate all four letter enumerations of a,f,H and pick only the ones that can lead to strings in your language.

Which cuts down some work.

Like this: HHHH, HHaf,HaHf,HafH,aHHf,aHfH,afHH,ffaa,fafa,faaf,affa,afaf,aaff (I think?)

(Oops missed the fa with two H ones, add those to the list above too.)

Then make S->(each thing in the list above but interleave each symbol by R's)

Then make R->(all strings with same num of A's and F's) using the prev grammar you mentioned. Finally, make A->KaK, F->KfK where K generates (b+e)^*.

I think this would work.

[signal goblet]

I just finished trying another idea and it was swell up until small separated a's and f's .-.

I'm gonna give yours a go

[signal goblet]

Could you summarise all of this with a mini partial grammar (doesn't need to be anything extensive), so that I can ensure I have the right idea?

[signal goblet]

Do u mean something like:
S-> RHRHRHRHR | RHRHaRfR | ....
R-> RARFR | RFRAR | epsilon
A-> KaK
F-> KfK
K-> bK | eK | epsilon

[final cliff]

Yes for S

[signal goblet]

I've missed the usage of A and F

In R

[final cliff]

For R replace a by A and f by F

[signal goblet]

Which grammar were u referring to for R?

Yep updated

[final cliff]

You said you had a grammar that could generate all strings containing the same number of a's as f's

That one but with A and F instead

[signal goblet]

Oh sorry the first one I sent

[signal goblet]

This one

[final cliff]

The purpose of wrapping up a and f in the production A and F is to allow us to add in e's and b's basically.

Your A,F,K productions look correct too.

[signal goblet]

How about now?

I'm missing a prod rule for non-terminal H

[final cliff]

Assuming R is correct that would be what I'm getting at.

Oh yeah H->b|e

In fact you can use H to make your K rule simpler too if you like.

K->HK|epsilon

[signal goblet]

Ah yep

Why not

Ima flesh out S quickly

How does that look

I'm having a hard time trying to generate aaebfbf

[signal goblet]

Perhaps R is incorrect, or S needs some grammar rules that contain any num of a,f and H?

This question is miserable

[final cliff]

S should be fine if you did it right. You would go S->RaRaRfRfR as the first step of your derivation to gen aaebfbf.

You may not have modified your R correctly?

R needs to have a production R->K

I think

[final cliff]

Rather than R->epsilon?

Because the other two R productions always produce at least one a and at least one f.

But for the rhs of the S productions sometimes we want the R's to produce (b+e)^* rather than anything containing an a or an f.

Just a guess

[signal goblet]

Ah yep, this fixed it for that one

[signal goblet]

We needed epsilon so as to produce any combo of a and f, but given the new prod rule R-> K, we don't need it since K already has one. Good pickup dude

I wonder if there are any other redundancies

[final cliff]

Your sure you got all the S production cases?

[signal goblet]

Currently testing string afaaffb

[signal goblet]

I believe so

[final cliff]

You have 18 S productions but here aren't there 19 (including the ones I missed)?

[signal goblet]

Let me double check

[signal goblet]

You're right, I missed one

That should be all of them n ow

[signal goblet]

This holds

@final cliff You are a genius. I have tried about 6 different edge cases, and so far it has worked for all of them

It looks very promising

Can you see any problems with it?

[final cliff]

I didn't really test your R production

[signal goblet]

I don't think it can generate strings that aren't in the language, so the my only point of concern would be if it misses some strings

[final cliff]

I kinda just blackboxed that part away since I know what your R production needs to do

[signal goblet]

It's quite a simple concept, just play around with this and you'll see quite quickly. Shouldn't be too hard to prove via induction either (doubt you want to spend tiem doing that tho)

S->SASFS|SFSAS|e
A->a
F->f

You can mould the first 2 prods to be anything you want

In terms of a and f

I have a feeling some simplifications can be made though

[final cliff]

Pretty sure you can prove our grammar works by induction and some element chasing.

Like if w is in the language we want, by cases we caught all the possible forms w can take in our production for S, so then expanding it out into the respective cases in the inductive step of your proof should show w will be in the language generated by our grammar?

The real proof would be more finicky than that ofc

Actually maybe an inductive proof even would get ugly lol

One way to do it would be to show things like w=R_1 a R_2 a R_3 f R_4 where R_1 thru R_4 have a balanced number of a and f's for example. Since R is correct R should generate R_1 thru R_4 and so S will generate w.

Essentially if you can show w can be written in one of the forms enumerated by our cases for S and you know R is correct (or can prove it) then it should follow w is generated by our grammar, so the given language is a subset of the language generated by our grammar.

Unless I'm making a silly mistake lol.

The reverse inclusion ought to hold by considering cases for S also. If w is generated by our grammar then w ought to have a form corresponding to one of the S cases. For ex if w=R_1 H_1 R_2 H_2 R_3 H_3 R_4 H_4 R_5 with H_i, R_i being strings generated by the obvious productions, then you'd show w satisfies all the conditions of the given language.

[unborn pasture]

How many different strings can you create with "ABCCDEFGH" where the two C's are next to each other?
I don't have the solution but isn't it 9!/2!-8!? We the take the permutation of all the strings where the C's are in different locations. We then treat the double C's as 1 letter and then take the permutation of 8 instead of 9. Then subtract that from 9!/2!. Is that correct?

we subtract "ABCCDEFGH" permutations where c are different places from "AB[CC]DEFGH" where the double C's are one letter.

[unborn pasture]

<@&286206848099549185>

[brisk sluice]

i would say you first place A, B, D, E, F, G, H , so that would make 7! possibilities. then you place CC, you have 8 possible places.

so that would make 7! * 8 which is 8!

you can also think of CC as one letter, so you want to place A, B, CC, D, E, F, G, H

[alpine dune]

ohh smart!

[brisk sluice]

so 8! possibilites

[quaint flower]

Hey guys, what are the ways to define infinity in set theory? And are there instances where we dont have alephs, or omegas but can still define infinity?

And the big question is, is there truly a universal definition of infinity? I personally don't think so but, am I wrong?

[vale cairn]

Perhaps the best reply is that the idea of 'infinity' can crop up in different ways and I wouldn't say there's 'one definition' (in maths)

[quaint flower]

Alright

[next yew]

what do you guys think of trevtutor compared to kimberly brehm for helping with learning discrete math?

[true venture]

How could you find the sum of all numbers from 1 - n who all have a digital sum of k?

[weary tiger]

to understand your problem, can you give an example with a few concrete numbers?

[chilly kayak]

I believe for example

for k=5. valid numbers are 23, 113, 311, 32, 320

but you might pick 320,3200,32000,32000,32000

so your sum is not bounded

you can get as big as you want

he might be missing another restriction

oh you need "n" as well

[little prism]

Given some total orders $\leq_i$ on the set $[N]$ for an integer $N$, we can define a product partial order $\leq$ on $[N]^k$ by $(x_1, \ldots, x_k)\leq (y_1, \ldots, y_k)$ iff $x_i\leq _i y_i$ for all $1\leq i\leq k$.

Given the standard order $1\leq_i 2 \leq_i \ldots \leq_i N$ for all $1\leq i\leq k$, we get that the diagonal $C={(n, \ldots, n): n\in [N]}$ is a chain in $[N]^k$.

On the other hand, if we set $\leq_1$ as the standard order and $\leq_2$ as the opposite order $N\leq_2 N-1\leq_2 \ldots\leq_2 1$ (and then $\leq_i$ for $3\leq i\leq k$ arbitrarily), then $C$ is now an antichain.

Is there some kind of classification for which sets $C$ this can happen? That is, for some product order on $[N]^k$ they are a chain and for a different product order on $[N]^k$ they are an antichain?

[vital dew]

Denascite

[serene perch]

Hey, could anyone help me out with this proof? I'm thinking I should prove this by contraposition but I'm not sure what I should do after to prove this proposition

and I also couldn't find any resources online that can help me with this proof ^

[little prism]

in the middle you used a different S, accident or intended? if accident, use x=b and x=a

[serene perch]

oh I think its the same S as the set provided at the start

pretty sure

[weary tiger]

Let [x] = floor(x);
n is a non-negative integer.
I have [n(n + 1) ÷ 2].
I'm thinking, [n(n + 1) ÷ 2] = [(n ÷ 2)((n + 1) ÷ 2], but I want to split this into integer divisions.
[n ÷ 2][(n + 1) ÷ 2]
The original expression has two factors: n and n + 1. One is odd, and one is even, therefore the above expression with two floors loses a 0.5 from one factor, in particular, the odd factor. To offset this, I'm thinking that I could add half (0.5) of the even factor to the expression?
I end up with this,
[n ÷ 2][(n + 1) ÷ 2] + [((n mod 2) + n) ÷ 2]; I believe that the even factor should be (n mod 2) + n. Yet, somehow I've made an error: after testing with a calculator, [n ÷ 2][(n + 1) ÷ 2] + [((n mod 2) + n) ÷ 2] ≠ [n(n + 1) ÷ 2]? I don't understand where I've gone wrong though

[vital dew]

peaceGiant

[weary tiger]

Welp, that answers

ab ÷ c = (a ÷ c)b = a(b ÷ c), but not (a ÷ c)(b ÷ c), because that's ab ÷ c²

[unique elm]

A and B are logically equivalent?

[unique abyss]

Logically equivalent means that $A \implies B$ is equivalent to $B \implies A$ for all values of The propositions that make up A and B, this is only true if A and B are either always true or always false. I.e. A and B must have the same truth value

[vital dew]

ALPH2H

[unique abyss]

So either A and B must be both tautologies or they must be both contradictions

@unique elm

[unique elm]

That's one complicated way of saying they're logically equivalent 💀

You basically mean that both A and B have the same truth values right?

[ember obsidian]

if u think so maybe it helps to try proving it

[unique abyss]

Yes

Sorry I misunderstood your question, I thought you were confused about what logical equivalence was

Hope my answer could you help you out

[light heath]

Is this a good proof?

Also what about this?

[stray reef]

probably not, given you're most likely expected to actually like, apply definitions which you did not do much. take x in P(A) and argue why x belongs to P(B), not this "although blah blah blah..." weirdness you've got! and the reasoning for the two directions is different enough to warrant its own section in the proof.

[light heath]

Fair enough, It’s so intuitive yet I don’t know how to word it

[weary tiger]

why didn't you show subset inclusion?

take (x,y) in AxB

[stray reef]

well you're learning, so...

[honest holly]

If X subset A, then X subset B since A subset B

[upbeat frigate]

hey there, can someone help me check if my ans is correct? im not sure if this is the right way of doing it

this one as well

[stray reef]

write down the contrapositive and the negation in plain english

[upbeat frigate]

oh alr

can someone help me check for no4

[upbeat frigate]

is it like that?

[spark silo]

how do they get the negativity/positivity of the 1's? thanks

[brave rock]

They will have previously calculated mu(n) for n being each divisor of 30. Your professor has probably preceeded your screenshot with a calculation of these values.

[serene marlin]

are these not all true or am i dumb, for c and d

for c, x can be 1

and for d

ymcan be 0

[weary tiger]

wait

im thinking about it backwards

1 does divide 3

wait

c) your right

yes

ur right for both i believe

[chilly kayak]

does 0 count as integer here?

[devout axle]

Is 0 ever not an integer?

ik there's debates about including it in the naturals, but it seems pretty definitely an integer

[serene marlin]

letsss goo

for this is it 2*9! - 7!

[honest holly]

No

[serene marlin]

fuck

did i have at all the right idea

[honest holly]

Yes you are very close

[serene marlin]

8!?

fuck

my math is dogggy

haha

[honest holly]

lol yeah

[serene marlin]

did 9-2 instead of 10 XD

[serene marlin]

For this can i essetially just right f(x) = 100x iff 0<x<4

[honest holly]

There is no injective mapping of A into B

[final cliff]

In all math or discrete math specifically?

Idk what you mean by this?

There are lots of definitions in a discrete math course and some of them depend on the specific course/book/instructor etc.

If this refers to all math maybe a more general channel is appropriate? It's kind of a vague/broad question.

For lists of discrete math qs I'd probably just flip thru rosen lol

[honest holly]

does anybody actually study discrete math??????

[weary tiger]

no

no one studies this field filled with tiny bits of other fields

[remote island]

Given the assumption, is it fair to do the proof in part a using a proof by cases?

Like this:

Since the root r of an SBTree S has degree two, it is adjacent to two vertices, v1 and v2. There are now two cases:

Case 1: v1 has degree 1 in S. then by forming the induced subgraph resulting from removing r, v1 will have degree 0. Therefore it will be a lone vertex and an SBTree by definition.

Case 2: v1 has degree 3 in S. then by forming the induced subgraph, v1 will have degree 2, therefore it will be the root of an SBTree, since by a routine induction argument, the degree of all the other nodes connected to v1 will remain intact (that is, either 3 or 1, and they all form a connected component by the assumption).

A similar argument applies to v2 and therefore concludes the proof

Are there any flaws in this argument?

[coral parcel]

It looks right, at least at a quick glance.

[remote island]

Nice

Thanks

[remote island]

Proof of (a): The proof is by contradiction. Assume the aforementioned longest walk (denoted by p) contains v as both the starting vertex and the final vertex. That is, p ::= v, a_1, ..., a_m, v. Vertices a_1 and a_m must be different because otherwise, the edge {a_m, v} would just be a repetition of {v, a_1}, which contradicts the assumption that no edge is traversed twice in p. Since p cannot be extended (by the assumption that it's the longest walk starting from v that does not repeat any edges), every edge e such that v is an endpoint of e must have been traversed in p. It is clear that the degree of v is at least 2, since edges {v, a_1} and {a_m, v} are traversed in p. Furthermore, any occurrence of v in the walk a_1, ..., a_m will add 2 to the degree of v, therefore the degree of v will remain even. This contradicts the earlier assumption that the degree of v was odd. (Note: It was assumed that the walk a_1, ..., a_m exists. In case it does not, we arrive at a contradiction, since the longest walk in graph G starting from vertex v and repeating no edge is then just the vertex v, but since it was assumed v is of odd degree, v is adjacent to at least one vertex and therefore the aforementioned longest walk can be extended.)

Is this proof of mine correct? If that's the case, does it need any more detail?

[remote island]

I edited a little bit to be more precise

[chilly kayak]

I couldn't find any solution on internet. any idea how to solve?

this from Kenneth Rosen book 8th edition. section 1.6

[weary tiger]

this is #proofs-and-logic not discrete math

[coral parcel]

Some discrete math courses include basic proof theory. Pretty much all of "discrete math" overlaps with something else.

[light heath]

Here in this example I dont understand why b = -2n

[remote island]

It's chosen for the purpose of showing that A contains every integer

In other words, every integer n can be written in the form 7a + 3b, where a = n and b = -2n

[remote island]

I also just got reminded of the number-theoretic way of thinking about this, that since gcd(7, 3) = 1, then any integer can be written as a linear combination of 7 and 3.

[honest holly]

Exactly. It would have probably been better for the authors to write that 7(1)-3(2)=1. Now multiply by n.

[chilly kayak]

but that problem is in a discrete math book

[honest holly]

Well it's not really math. Your question is more about proof/logic

[onyx pewter]

I feel like discrete math encompasses the last 4 channels in early uni

5

[serene marlin]

I got a question for u guys from my final today

We have a combo lock with 40 numbers and a combo has 3 of the numbers

how many combos are possible if:

no number in the 3 number combo is within less than 4 numbers away

ie:
10,6,11 wont work
10, 13, 14 wont work
10, 14, 18 will work
15, 25, 12 wont work

[weary tiger]

This means that for there to be a lifting the cardinalities of equivalence classes in domain have to match those in the codomain right?

[pale epoch]

do they? cant you always have a lifting

[weary tiger]

it sayd f([x]_E) = [f'(x)]_F so every element y' of [f'(x)]_F has to have y in [x]_E such that f(y)=y' right

[pale epoch]

i dont think i get "has to have y in [x]_E such that f(y)=y' right"

f doesnt take elements of X as arguments

and elements in [x]_E are elements of X are they not

take f: {{1,2}, {3,4}} -> {{1,2,3,4}} then id: {1,2,3,4} -> {1,2,3,4} is a lifting of f is it not

f({1,2}) = f({3,4}) = {1,2,3,4} = [x]_F for every x in {1,2,3,4}

[weary tiger]

Which theorem is better to check for primality of a number a in terms of how quickly we can deduce primality of a?
Wilson's Theorem or Fermat's Little Theorem?

[weary tiger]

I think trial division works out best for numbers < 1000

[unique abyss]

fermat's little theorem + trial division is probably your best bet for smaller numbers

I'd recommend the probabilistic tests

[modest flower]

Somebody know how to get zero order hold (zoh()) of any interval for any mathematical function using floor() ?

https://www.desmos.com/calculator/f44wntgooa

I managed to get zoh(x^2,1)

but I have hard time generalising formula

is there any j(x) -> k(x) ; k(x) = zoh(f(x),3)

the same way this one works: h(x) -> i(x) ; i(x) = zoh(f(x),1)

[weary tiger]

👍

[fresh hollow]

I'm looking for a theorem, if it exists. I was wondering about the following conjecture:
"Given two sets of 5 positive non-zero integers A:{a, b, c, d, e} and Z:{v, w, x, y, z}, A=B iff ∑A=∑B and ∏A=∏B"

Or perhaps, should I go to a help channel and work it out there?

[honest holly]

it's false

oh didn't see non-zero

[fresh hollow]

Yeah I had to edit it 😅

I realized my mistake

They're also unique if that wasn't clear

[honest holly]

hmm

[fresh hollow]

unique in each set anyway

[honest holly]

yeah

[whole jacinth]

this feels false

there’s not enough restrictions

{1,2,3,10,12} and {1,2,4,6,15}

[fresh hollow]

Ah, perfect, a counterexample

[weary tiger]

It's saying set A = set B, not equivalent

Hence elements in both sets must be same too

I believe the statement is true then since it seems well defined to me

You can prove it then
[All elements in set A and B are unique and non-zero]
=>: A = B, hence elements in both sets are same and n(A) = n(B). Hence sum(A) = sum(B), [sorry for bad notation, sum(set A) here means summation of all elements of the set A], since a1 = b1, a2 = b2,..., an = bn by definition (same goes for the product)
<=: If sum(A) = sum(B), then a1+a2+...+an = b1+b2+....+bn
and if prod(A) = prod(B), then
(a1)(a2)....(an) = (b1)(b2)...(bn)
Let c1 = prod(A)
c2 = prod(B)
s1 = sum(A)
s2 = sum(B)

Then you can construct a nth degree polynomial (because by definition n(A) = n(B) = n) x^n + s1.x^(n-1) + ... + c1 whose roots are all elements of set A
You can do the same for set B too, x^n + s2.x^(n-1) + .... + c2
Since s1 = s2 and c1 = c2, the second polynomial is same as the first one. Hence the set of roots {a1,...,an} = set A and {b1,....,bn} = set B are same and equal. Hence set A = set B

[gray oracle]

just wanted to send this

[whole jacinth]

this is wrong, you’re only given 3 of the 6 coefficients are the same

[humble star]

Yo I have a short one about edge point of a set
If we have lim that approaches L from both sides
Is L excluded as edge point?

[fresh hollow]

The counterexample disproves it though. I was suggesting that if[(sum of A = sum of B) and (product of A = product of B)], then A=B.
They have given an example where, although p, !q. Therefore the supposition is false.

[humble star]

For example ((-1)^n) * (1/n), n is Natural

[tacit thistle]

i'm terrible at discrete math

do you guys have any resources?

[tiny helm]

yeah what are good resources to learn discrete math

[fresh hollow]

Our professor taught off of "Discrete Mathematics with Applications 5th Edition" by Epp, but I honestly never looked in the book

I do suggest Numberphile, the YouTube channel. They have quite a lot of fun videos about math in general, and some good ones with proofs. It's not really meant for "learning discrete math" but it's still nice

[weary tiger]

depends on the topics your discrete math course covers

[weary tiger]

True

[weary tiger]

Yeah

[weary tiger]

How would I go about finding solutions to the following equation?
$$ n! + n = n^n, \quad n\in \mathbb{Z} $$

[vital dew]

leadersheir

[pale epoch]

intuitively the right hand side grows faster, so for "large" n there shouldnt be any

so you check when this is the case

and then check the small n by hand

[runic mural]

15x+41y = 1.
1234x + 4321y = 5.

[true venture]

I have a graph question, is there a better definition for a both connected and underected graph. That has nodes of maximum degree 6 and minimum degree 2?