discrete-math

[mighty dust]

do that in the help channels

not here

[weary tiger]

oh sorry, what is this channel for? it says discrete math

and i am working with discrete math

[mighty dust]

ye this is discussion channel

if u want some1 to help u, ask in the help channels

[weary tiger]

okay

[rare barn]

there's nothing strictly speaking wrong with asking an objective question when the channel is inactive @mighty dust

[mighty dust]

true

[mighty dust]

sorry lol im just having a bad day @weary tiger

[coral parcel]

It is not true.

A counterexample could be f(n)=2log_3(n) and g(n)=log_3(n).

[coral parcel]

(poof!)

[weary tiger]

can anyone explain why $P \implies Q$ is true if P is false but Q is true?

[vital dew]

Renegade

Renegade

Renegade

[weary tiger]

so we know x^2 >=0 for all x in R, and the Riemann hypothesis is either true or false hence there are two possibilities

FT and TT

which both imply that the proposition is true?

[olive wren]

Let’s say I have a coin and I say “if my coin is a penny, then it is worth one cent”
But then I show you my coin, and it’s a dime, does that mean my statement is false?

P=>Q just means “P implies Q”, ie. when P is true, Q must also be true.
It places no restrictions on when P is false

Otherwise if “False implies X” were false, implies would be equivalent to and

[idle hazel]

so if A ⊆ B then A is a subset of B but also the subset A=B?

and A ⊂ B is the subset A thats not equal to B?

[stray reef]

bad wording

[idle hazel]

[stray reef]

A ⊆ B includes the possibility that A = B, while A ⊂ B excludes it -- however, some authors use ⊂ in the inclusive sense, so you should be careful using it that way

[idle hazel]

ah ok

[stray reef]

to write that $A$ is a proper subset of $B$ and be unambiguous about it, you can do $A \subsetneq B$.

[vital dew]

Ann

[idle hazel]

that looks more proper i think ill go with that

[dark oyster]

How can ı solve this

I tried Catalan numbers but ın lesson we always solved with (0,0) to (x,y) problems, I didn't solve that because of

[stray reef]

you don't need catalan numbers here

any path from (3,3,3) to (12,12,12) can be encoded as a string consisting of 9 each of the letters R, L and U

[vital dew]

Results provided by WolframAlpha

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

Requested by Anton.#8858

[dark oyster]

How can we solve this with pie

[stray reef]

with what?

[coral parcel]

One approach is to split according to how many nodes have degree 3 in the spanning tree.
0: The spanning tree is a line graph, and for each color we need to decide which sequence the nodes of that color appear in when we move down the line starting from the leaf of that color.
1: A central node is connected to all three nodes of the opposite color. Each of the two remaining nodes of the center color must hang off different nodes of the opposite color.
2: The two degree-3 nodes must be from different sides; otherwise they create a cycle. Once we choose which nodes they are, everything will be connected.
In each of these three cases it is fairly easy to count the ways to assign nodes to roles in the tree; they then sum to 81.

[stray reef]

i think you mean path graph and not line graph, at least if Wikipedia is to be believed with terminology

[stuck compass]

use kirchoff's matrix tree theorem :P

(replied to the wrong person, mbmb) @tardy comet if you're interested in a more linear algebra approach. trop's is way more direct

[pastel hollow]

What’s S4

[stuck compass]

also, by PIE, I'm assuming you meant https://en.wikipedia.org/wiki/Inclusion–exclusion_principle

ie, principle of inclusion/exclusion?

[weary tiger]

for a)

so e.g

but this seems wrong

update: oh wait I got it nvm

[hoary cloak]

yea line graphs are roughly when you turn the edges into vertices and vertices into edges, it's a completely different thing from path graphs

but it's understandable regardless

[whole field]

Literally there are no solutions bc max(x1+...+x8) = 120

[versed void]

how do we determine which columns represent what

nvm figured out the above!

[weary tiger]

can someone help em

me

[coral parcel]

No, because you don't seem to have asked any question.

[hoary cloak]

does the fact that any graph with chromatic number >= k is k-constructible imply that any k-critical graph is constructible (by hajos construction)?

https://en.wikipedia.org/wiki/Hajós_construction

both things seem to be true, but i'm having a hard time figuring out how does one follow from the other

nvm it doesn't follow

wait no

[hoary cloak]

this is wrong, it needs to have a k-constructible subgraph

yeah it all makes sense now

[spring surge]

Is there any geometrical interpretation to combinatorics concepts?
Or the discrete nature of the latter permits any 1 to 1 correspondence in between ?

[hoary cloak]

i think it depends. for graph theory for example the closest you might get are planar graphs. and i'd still argue it's more related to topology than geometry

actually i remember there was a field of research called discrete differential geometry which might be a nice blend of the two

but i can't think of geometrical interpretations to most concepts rn

[pastel hollow]

Where does this equality come from?

[hard bone]

Could you help me out for this two questions? Or at least could you recommend a channel for this questions

[weary tiger]

$[(1+x+\cdots +x^5)(1-x)]^3=(1-x^6)^3$

[vital dew]

jswatj

[sacred dune]

could someone clarify, here when they say every edge at every stage has the same probability of being chosen as the next, im not sure what they mean. If the probability of picking an edge not chosen yet is p, and this is uniform through every stage, then we dont have a probability measure do we?

[final cliff]

Do you know about cyclic subgroups?

[whole field]

is this a group under multiplication?

[unique canopy]

yes I do

[unique canopy]

I believe so

[whole field]

normally it's written as GL(2, R)

[final cliff]

I thought that superscript x referred to the group of units of M_2(R)? My algebra is pretty rusty though.

[whole field]

that would be the same as GL(2, R) right?

[final cliff]

Pretty sure? I honestly don't remember.

[final cliff]

But if it is a group then there's a way to look at the question in terms of cyclic subgroups. Have you characterized cyclic subgroups in terms of smallest subgroups containing certain elements?

[unique canopy]

nope

[final cliff]

Hmm. They might have taught you it, but if G is a group and a is an element of G then <a> is the smallest subgroup of G containing a iirc.

Idk if you should use that if they haven't taught it though

[unique canopy]

I got the answer could I ask another q

[final cliff]

You can keep posting questions here so long as they are appropriate for the channel.

I don't mind looking but I might not know the answer.

Have you tried looking at/for any examples/counterexamples?

Rings from modular arithmetic are a nice place to start.

[unique canopy]

Would this be one example

[final cliff]

Yeah in Z_10 right?

In general any time you have a ring like Z_(mn) for m,n two nonzero integers then you will have mn=0

Rings where any product of two nonzero integers is a nonzero integer are called integral domains iirc.

Sorry not integers specifically

Rings might contain items besides integers lol

[final cliff]

It's basically just rings where you habe the zero product property by contrapositive of this condition.

[untold ravine]

ah

[jolly saffron]

I've got a following sequence of numbers: 2, 7, 18, 41, 88, 183, 374. How can I generalize this sequence, so to be able to retrieve any nth term?
Initially I thought that this sequence is quadratic, but quadratic sequence requires a constant second difference.
The first difference of this sequence is:
5, 11, 23, 47, 95, 191
Here's the second one:
6, 12, 24, 48, 96, ....
And then I figured out that am able to generalize the latter:
6 * (2^(n-1)) where n is a term's number.

Still struggling with generalizing initial sequence, though

[coral parcel]

Let (a1,a2,...) be the original sequence, (b1,b2,...) be the first differences and (c1,c2,...) be the second differences.

By your observation, we have that bn-b1 is always 6 times a sum of consecutive powers of 2. Such sums behave nicely; they're always one less than the next power of 2.

So let's try to add 1 to each of the bn's which will let us divide by 6 and look for a nice relation there.

The sequence of (bn+1)/6 turns out to be: 1, 2, 4, 8, 16, 32, ...

So we have bn = 6·2^n-1.

Now $$a_k = 2+\sum_{n=1}^{k-1} (6\cdot2^n - 1) = 2 + 6\sum_{n=1}^{k-1} 2^n - \sum_{n=1}^{k-1} 1 = 2 + 6(2^k-2) - (k-1)$$

[tidal tulip]

why is m^2 even in this proof is it because m^2 can be written as m^2 = 2k where k=n^2 ?

[vital dew]

Troposphere

[coral parcel]

Try rewriting the proof so it doesn't mention m². If you succeed, we can look at whether the result as convincing as what we started with.

It's true that m²=2n² by assumption, but I'm not sure how you propose to speak about the relation between 2n² and m without saying "m²" or something equivalent to that.

[tidal tulip]

ok im just trying to understand their justification of m^2 being positive, i suspected it’s because m^2=2n^2 could be rewritten as m^2 = 2k where k=n^2

or how about breaking m^2 up into cases where case n is odd or n is even

if n is odd then n^2 is odd and it’s even (2) times n^2 (odd) and even * odd = even

if n is even then n^2 is even and it’s 2*even = even

so in either case 2*n^2 is even whether n is even or odd

is that a proper justification why m^2 is even

@coral parcel

[median forum]

does anyone know why this is not 2?

[coral parcel]

Sorry, I think I spectacularly misunderstood your question. When you wrote

why is m^2 even in this proof
my brain somehow converted that to "why is m^2 mentioned in this proof at all". 🤦 I should go get some sleep.

[tidal tulip]

haha

[coral parcel]

But yes, the reason m² is known to be an even number is that it is assumed to be 2 times n².

[tidal tulip]

so both of my justifications are correct?

m^2 is of the form 2k

[coral parcel]

Yeah, but perhaps the latter is more verbose than it needs to be. By definition a number is even if it is twice some integer; you don't need to split it up according to whether the "some integer" is odd or even.

[tidal tulip]

so i can just simply say

m^2 is of the form 2k where k=n^2 in this case

hence even

[coral parcel]

Yes.

[tidal tulip]

k ty!

[coral parcel]

Because f^-1(4) is only defined if there is a unique input that the function f maps to 4. There isn't here -- both f(2) and f(-2) are 4.

[median forum]

assuming f: A -> B, where A, B are elements of R, then (-2) shouldn't exist in the set A,B regardless

so 2 would be a unique input

also, where do you get that it's defined by having to be a unique input?

[coral parcel]

R stands for the set of real numbers, and -2 is certainly one of those.

[median forum]

oh

you're right, im thinking of natural numbers

regardless

it doesn't specify the function is injective right?

[coral parcel]

Usually the notation f^-1 is only defined if f is injective.

[median forum]

ah i see

ok thanks

[coral parcel]

(I briefly thought your problem looked like it considers f^-1(x) to be defined for a non-injective function f just as long as x is hit by exactly one element of the domain -- but this would be a rather nonstandard usage, and is not really necessary to make sense of the exercise, so let's forget about that).

[coral parcel]

Does "stars and bars problem" ring any bell? Otherwise look that up.

[weary tiger]

can someone tell me the (c) part ?

[unreal stump]

You need to choose 18 people out of 118 total students

After that it's identical to (b)

[weary tiger]

This is how i did (b)

i think i messed up in (b) too

Lol

[unreal stump]

Well in (b) you choose 19 out of 119 students

That is the only difference

Shouldn't (b) be just
$\ 3 \binom{119}{19} (19!)$

[vital dew]

Drake

[unreal stump]

If Toni is first in line,you can ignore her and think of the problem as arranging the remaining 19 people in 19 slots

Same for 2nd and same for 3rd

[weary tiger]

ah you are right

thanks man

i was just thinking too deep into it

[weary tiger]

so the only difference in (c) is that we are going to
$\3\binom{118}{18} (19!)$\

[unreal stump]

Yes

Well it's ```
\

Discord renders it as \

[weary tiger]

oh yeah i forgot it treats it as an escape sequence

thanks lol

[vital dew]

Anti_spiral69420

[weary tiger]

can someone tell me this question ?

[unreal stump]

This is just (19C3)

19*18*17 may not preserve the alphabetic order

For example you could get
BACT

[weary tiger]

i need to think lol, my little brain isnt able to wrap around lol

AH

i get it

thanks

this is the last question i wnna ask

i couldnt figure it out to be honest

[weary tiger]

i mean i am sure there is 10C3 but what else after that

what am i supposed to do to avoid the common sides

[stray reef]

perhaps you could count how many triangles do share a side

and how many triangles share two sides

[weary tiger]

i was planning on overcounting and subtracting

[weary tiger]

this

but how am i supposed to count the common sided triangles

[civic nova]

Couldn’t you count permutations on one side?

[stray reef]

well the decagon has ten sides

fix one side in particular. how many triangles include that side?

[civic nova]

Yes

But it would be more like picture 1

[weary tiger]

i was thinking abut that, like a typical circular table question but

i dont know how to approach it

[civic nova]

I mean you could break it down, and use a smaller shape (less sides) and see if a pattern arrises also

[weary tiger]

i think i will fix one point and then draw manually to see if some pattern arises

[weary tiger]

yeah that

thanks talking to you guys set things straight

[quaint notch]

Hey guys, can anyone help with the following:

Prove that There’s a subset of R^2 that intersect exactly every line exactly twice

[signal goblet]

Q: Does anyone know of an algorithm that can find the graceful vertex labellings of complete binary trees?

I have spent the past week searching and creating my own, and it is driving me insane. I don't want a brute force approach that involves just finding the permutations for a given n, because it is far too inefficient and its practical value is next to nothing (just try solving this problem using the brute force paradigm for any n greater than 11...).

This is the closest I have found (as far as papers go), but the authors have erred in saying that their algorithm constructs one for a complete binary tree (its just a binary tree).
https://www.researchgate.net/profile/Dipta-Gomes/publication/346604572_Graceful_Cascading_Labelling_Algorithm_Construction_of_Graceful_Labelling_of_Trees/links/60277c18299bf1cc26c0ecff/Graceful-Cascading-Labelling-Algorithm-Construction-of-Graceful-Labelling-of-Trees.pdf?origin=publication_detail

[coral parcel]

Can you do transfinite induction?

[quaint notch]

We learned that, still confused when working with ordered groups that are not numbers for some reasons but yeah, that's an option

[quaint notch]

forgot to reply

[coral parcel]

There are |R| distinct lines in the plane. Well-order them so their order type is the initial ordinal of cardinality |R|. Go through the lines one by one, choosing up to two points on each if it doesn't have two points yet, while being careful not to add any point that is collinear with two points you have already chosen. At each step you will have chosen strictly fewer than |R| points yet, so there are also fewer than |R| points on the line you have to avoid (this requires a bit of additional argument which I'll leave to you), meaning there will always be points left over that you can choose.

[quaint notch]

I'll give that a shot, the idea is clear now even if I won't succeed doing it, thanks a lot!

[coral parcel]

This seems to depend on the exact details of what "the transfinite reduction theorem" and "the preliminary form of transfinite recursion" mean. Even though transfinite induction/recursion are a common concepts, there is no standard for exactly how to express it with which variable names and assumptions, nor for which special case to single out as "the preliminary form".

[coral parcel]

Okay, so to prove "(i) holds for every t in A" by transfinite induction, you need to prove an induction step:
Let t in A be arbitrary and assume that (i) holds for every u < t. Then we have to prove that (i) holds for t too.

The induction hypothesis tells us that for every u < t we have F(u) = G(f restrict seg u). But since G is a function that maps into B this means in particular that F(u) is in B.

This means that $F \upharpoonright \operatorname{seg}t$ is a function whose domain is $\operatorname{seg}t$, and whose values lie in $B$. But that's just what it means to be an element of $^{<A}B$. So $t$ is not in case (ii); therefore it must be in case (i), as required.

[vital dew]

Troposphere

[weary tiger]

What's a good syllabus/ gradual book that's freely available for an utter beginner to learn discrete math?

[sour arrow]

Very beginner friendly
http://discrete.openmathbooks.org/dmoi3.html

[hollow isle]

Do you guys find Discrete Math harder or easier to understand than Statistics and Probability?

[tired bluff]

I would like some help understanding this paragraph.

I have almost no formal training in structures like rings and fields, though I do know my vector spaces.

A simple explanation would be nice.

(I've put this here because the context is a problem in combinatorics; if this is relevant to another channel, feel free to direct me there.)

[stray reef]

the space of homogeneous polynomials has a 'natural' basis consisting of unitary monomials

to give a more concrete and less symbol-heavy example, the space of homogeneous polynomials of degree 2 in 4 variables $x, y, z, w$ is spanned by ${x^2, y^2, z^2, w^2, xy, xz, xw, yz, yw, zw}$

[vital dew]

Ann

[tired bluff]

Makes sense to me.

Ahhhhh, I think I get it now.

Basically, we want the degree of our monomial in x+1 variables to be equal to y.

That's it, right?

[stray reef]

yes

[tired bluff]

Makes sense. It reminds me of a generating polynomial.

All the same, it's a pretty funny way of understanding this combinatorial idea.

Thank you!

[tired bluff]

I'm having trouble understanding this argument.

An even number of persons are seated around a able. After a break, they are again seated around the same table, not necessarily in the same places. Prove that at least two persons have the same number of persons between them as before the break.

[stray reef]

which part of the argument is tripping you up?

[tired bluff]

I have a lot of issues with this, really.

First: I don't agree with the very first assertion. Isn't it only true for a row of chairs, rather than a round table which wraps around?

For instance, given 10 chairs, if 1 and 3 get permuted to 1 and 9, then....

They still have one guy between them, but 2 is not equal to 8. Or am I misreading something here?

[stray reef]

well

hm

actually they might be proving a stronger statement here

that there exists a pair that ends up in the same relative position (mod 2n) after the permutation

[tired bluff]

I'm struggling with the second part, too. It's a little hard for me to get an intuition for the mathematical statement they have provided.

I'm imagining a polygon with P0 at the top and moving clockwise through P1, P2... to P_{2n-1}.

[stray reef]

yeah that will work

[tired bluff]

In that sense, $a-\sigma(a)$ denotes how far anticlockwise $a$ gets permuted.

[vital dew]

Wishes

[tired bluff]

And ditto for $b-\sigma(b)$.

[vital dew]

Wishes

[tired bluff]

Again, I'm bothered by the fact that the congruence statement doesn't really match the simple example I gave earlier, in which 1 goes to 1 and 3 goes to 9. If they're actually proving a stronger statement than asked for, then saying that the problems are "equivalent" seems a bit rude to me!

The frustrating part of this explanation is really that I have no idea why the writer has written what they've written, haha.

[proven relic]

Hello

My problem is in how many ways there is to set 3 numbers >=0 thats the sum of them is 300

D(3,300) ?

[livid drum]

Maybe as a clue suppose you've solved D(2,N).
Then you can set the first number to 0 and you'll have D(2,300) ways to set the other two numbers.
Or you can set the first to 1 and have D(2,299) for the rest. etc.
If the order isn't important, you can minus away the overcounting

[coral parcel]

Otherwise google stars and bars (combinatorics).

[proven relic]

What about this

?😅

also what the equation of 1+2+3……n

Not related to this

(1+n)n /2 ?

💀

https://tenor.com/view/time-timecard-spongebob-later-gif-3570175

[signal goblet]

Yes

[weary tiger]

Kinda bad with terms so I wanted to ask

The infimum of a set is the element with the lowest value?

And supremum respectively vice versa

[unreal stump]

Not always,The infimum need need not be in the set

Consider $\left{\frac{1}{n} \middle | n \in \bN-{0}\right}$

[vital dew]

Drake

[unreal stump]

Infimum of this set is 0 which is not in this set

@weary tiger

[weary tiger]

ah

wait but in this case there isn't an infimum is there? @unreal stump

how is it 0? if you don't mind explaining

[unreal stump]

Suppose inf is not 0

Then let x=inf(A)>0

Now 1/x is a positive real number and hence lies between floor(1/x) and floor(1/x)+1

[weary tiger]

ah

[unreal stump]

Which means x lies between 1/n and 1/(n+1) n=floor(x)

Ergo not infimum

[weary tiger]

I see

thank you

[weary tiger]

Hi so, in an undirected graph G and a matching M is every node that's contained in an edge of M, M-saturated?

By definition a node is "M-saturated" if it's an endpoint of some edge in M

[ember obsidian]

u can also directly show inf=0

[pastel hollow]

My book says that to solve the recurrence
$$C_N = C_{\lfloor N/2\rfloor} + C_{\lceil N/2\rceil} + N, \qquad N \geq 2$$
with $C_1 = 1$ when $N = 2^n$ is a power of two, we can rewrite the recurrence by letting $a_n = C_{2^n}$ and then $a_n$ satisfies the recurrence
$$a_n = 2a_{n-1} + 2^n, \qquad n \geq 1$$
with $a_0 = 0$. Why isn't $a_0 = 1$?

[viral crown]

ooooh lemme see

[vital dew]

EdgarAlnGrow

[viral crown]

i think this is false too btw

.>

consider the set of all real numbers between 0 and 1

sup is one

and inf is 0

neither of which are in set

[ember obsidian]

its clear 0 is a lower bound. in fact its the greatest one since, for any x>0, the archimedean property says some 1/n falls under x, so x is not a lower bound

[weary tiger]

for predicate calculus, anyone know how to LaTeX the logical conjunction symbol?

∧ this shit

$\wedge$

[vital dew]

Renegade

[weary tiger]

okay just answered my own question

[coral parcel]

Either \wedge and \vee, or \land and \lor will work.

[novel ore]

Is this a mistake? The two boxes clearly contradict each other

[karmic prairie]

The negation of ∃x, P(x) is not ∃x, ¬P(x)

(It's ∀x, ¬P(x) )

The first box is clear because there are no elements in the empty set

The second box says the exact same thing: the first box holds for all statements, but ¬P(x) is also a statement

[strange peak]

73^1567 = x mod 11

73 mod 11 is 7

I then try to use the Chinese remainder theroem but can't get it to work

Unable to get -1 or 1 without getting an extremely big number

[stray reef]

why CRT tho

you want fermat's little theorem here

@strange peak

[strange peak]

The exponent and the mod p isn't the same though

How should I use it on my equation? Really lost here

@stray reef

[stray reef]

a^(p-1) = 1 mod p

therefore 7^1567 = 7^(1567 mod 10) mod 11

[strange peak]

Thanks a lot but how do you get 1567 mod 10 in the exponent?

Probably need to check some videos on Fermats to really get it

Got it now, thanks a lot for your help 🙂

[stray reef]

7^10 = 1 mod 11 so the exponent can be reduced by 10 without affecting the value

[zenith oyster]

Hey, I’m trying to think of a way to algorithmically solve this problem but I’ve been stuck on it for these past 3 days. The problem is as follows:

You have a directed graph with weights (distance) where some vertices S you must avoid as much as possible. You have to go from vertex A to B. Essentially you need to find the path that maximizes its vertices distance to S (as in one of the vertices in ur path is the bottleneck). So what I did first was to compute how far every vertice is from S. I thought that was a good starting point, but then now I’m really confused about finding the path with the maximum distance from S.

I can see a way to do it in O(v^2*log(v) + e) but I’m required to do it in O((e+v)^1.4) and I can’t figure out how!! I feel like I’ve tried everything. Any help would be appreciated

[coral parcel]

Sort the vertices in order of decreasing distance to S; add them to a new graph in that order while keeping track of connected components with a union-find structure. By the time you have added both A and B and they're in the same component you have how far your can stay away.

[stray reef]

so hang on. what are we minimizing?

are you sure you didn't mean max[v in path] min[s in S] dist(v,s)?

avoiding things as much as possible seems to mean maximizing distance to me

[coral parcel]

That's how I read it too.

[stray reef]

and we have a directed graph, so are we talking about dist(v,s) or dist(s,v)? because one of these may well be +∞ sometimes

[coral parcel]

I overlooked that it was directed. Then my suggestion won't work, or at least not right out of the box.

You can still do a binary search for the threshold distance in O((v+e)log v) time, though, checking reachability from A to B from scratch for each guess.

[zenith oyster]

Sure one vertice might be unreachable by S. Yeah it’s important that it’s the distance from S to V (part of the path) that is maximized

Oh yeah sorry I mean maximize

[zenith oyster]

wym with connected components?

[coral parcel]

I thought at that point the graph was undirected, so disregard that proposal.

[zenith oyster]

ok

[zenith oyster]

this too disregard?

[coral parcel]

No, that should still work.

[zenith oyster]

What do you mean with threshold distance?

[coral parcel]

How far you can stay away from S and still get from A to B.

[zenith oyster]

Sorry I don't get it, do you mean I use my computed values of distances from S or do I not need that?

[coral parcel]

Yes, you use your precomputed distances from S.

[zenith oyster]

So do I start from a specific point like A and do some kind of graph traversal or is the idea to do some completely different?

Because I've legit spent days on trying different ways to traverse the graph and do some smart things to find the solution. I just don't see it.

[coral parcel]

You make a guess at what the threshold is, and do a bog-standard reachability problem to see if you can get from A to B through only the nodes whose distance from S is >= your threshold.

[zenith oyster]

yeah but wouldn't that exceed the required time complexity?

[coral parcel]

Reachability can be checked in time O(e).

[zenith oyster]

you're doing something v * (v + e) (at least no?)

still that makes it v*e no?

[coral parcel]

Where does the v factor come from?

[zenith oyster]

well there can be v unique distances from S what was I was thinking, worst case scenario

so if ur doing test from A to B for each those unique ones u get v*e, no?

[coral parcel]

I'm not testing for every possible distance -- that's where the binary search comes in.

It means you only have to do log(v) tests to know where the boundary between "possible" and "not possible" is.

[zenith oyster]

oh my god obviously

yeah thinking not my greatest suit always

Thx I will see if this suits my needs

[zenith oyster]

I had a discussion about this with my friend, quite recently, I mean my go-to strategy would be BFS or DFS but those are often described as O(e+v) which isn't an issue here. However, I've seen this claim you make elsewhere, I'm a bit confused to as to how? Is it that we can only take e edges anyway and thus we can stop looking after e edges as we would have found what we were looking for by then?

[coral parcel]

The difference between O(e+v) and O(e) is only relevant if e<v -- that is, when most of the nodes in the graph aren't even connected to anything.
If you want to compute a BFS/DFS ordering of all the nods you need to restart the search if it runs dry before it has seen all the nodes -- but here you're not interested in ordering the nodes, just to get a yes/no answer to "is node B reachable from A". For that, you don't need to restart the search.

It still becomes O(v+e) if you need to reset a "seen yet?" flag for all of the nodes each time you start a new search.

But you can avoid that by being clever, e.g., by just maintaining a "which instance of the reachability search was this node last seen in?" field instead, and comparing it to a sequence-number for the current instance.

[zenith oyster]

Thx

[pastel hollow]

They’re called “nodes”, not “nods”. Please try to refrain from attempting to answer questions pertaining to topics about which you’re uneducated👍

[zenith oyster]

real men call them vertices but ok

[pastel hollow]

nods in agreement

[earnest mountain]

Let V be the set of all strings of length 2 in the alphabet {A,B,C,D}. Define a graph G with vertices V by putting an edge between the string s and the string t in V if s and t differ at exactly 1 entry.
How do I find the number of vertices in G and the degree of AB? I initially thought it would be 16 (4 choices for the first)x(4choices for the next), and the degree of AB would be 9 (3 choices to differ)x(3choices to differ)
Finally how many edges there are? I choose 72 (degree)x(vertices)/2 but idrk if that's correct

[loud ember]

the degree of each of your vertices is 6. by multiplying 3 and 3 you count how many differ in both letters, not one

[vagrant crow]

Bit confused about notation here, what is e?

[willow fog]

identity

just like 0 is for addition and 1 is for multiplication

since 5+0=5 and 5*1=5

e is kinda the generalized version of that

[tired bluff]

I would like a check on my mathematics here.

We are concerned with how many numbers in the domain are mapped to odd numbers. If an odd number of them are mapped to odd numbers, then the sum is odd, and it is even otherwise.

So the number of functions are $\sum_{n=0}^{999}{1999 \choose 2n+1} 2^{2n+1}. 2^{1999-(2n+1)}$

(2^{2n+1} represents that for all the 2n+1 numbers mapped to odd numbers, we have 2 choices for where they go. Ditto for the other power of 2.)

[vital dew]

Wishes

[tired bluff]

And so, simplifying, we have $2^{1999} \sum_{n=0}^{999}{1999 \choose 2n+1}$

[vital dew]

Wishes

[tired bluff]

We know that the sum of odd coefficients of a binomial is equal to the sum of even coefficients.

So this is $2^{1999}.2^{1999}/2$

[vital dew]

Wishes

[tired bluff]

Or 2^3997.

This also has something of an intuitive appeal: There are 4^1999 = 2^1999.2^1999 total functions, and it makes sense that half of them have sum odd and half even.

Is this correct?

[dense obsidian]

From where can i add this bot to my server ??

[cerulean wind]

seems correct. alternative approach:

we intuit that about half of the functions from {1,…,1999} —> {2000,…,2003} have even sum and half have odd sum.

take f such that the sum of the outputs is odd. set g(x) = f(x) for all 1<= x < 1999 and set g(1999) = f(1999) + 1 if f(1999) != 2003, g(1999) = 2002 if f(1999) = 2003. then g has even sum.

this gives a bijective correspondence from the set of functions with odd sum to the set of functions with even sum.

[tired bluff]

Thank you!

[coral parcel]

A reasonable strategy would be to start by googling texit -- and when that only gives you results about Texan secessionists, refine the search to texit discord bot.

[pastel hollow]

Im trying to find the number of binary sequences with n 1s and m > n 0s s.t. if you scan the sequence from left to right, you will always have encountered more 0s than 1s

if m = n + 1, then the number of these sequences is the nth catalan number

is there any way to extend this to arbitrary m by counting the number of ways to insert the remaining m - (n + 1) 0s after you form a sequence with n + 1 0s and n 1s?

[dense glade]

what is x^2 mod 5 for the first 100 positive ints mean?

[tired bluff]

What remainder do the squares of the first 100 natural numbers leave when divided by 5?

There's a pattern to it.

[amber hill]

every number can be expressed in terms of 5x+1,2,3,4

so the remainders repeat

[stray reef]

bad wording

[formal flicker]

Can someone explain to me why are (a) and (b) false ?

[amber hill]

sorry

[amber hill]

A,B are sets

consider like x=1, A={1,2,3}, B = {{1,2,3},a,b,c}

here, x belongs to A, and A belongs to B but x doesn't belong to B

and almost same with b). too

C={{a,b,c},d,e}, B={a,b,c}, A={b,c}

here $A \subseteq B$ and $B \in C$ but $A \notin C$

[vital dew]

usernamephobic

[stray reef]

you know $\notin$ exists, right

[vital dew]

Ann

[amber hill]

I didn't know but thank you

[formal flicker]

Can somebody tell me what does “A:B “ mean?

[stray reef]

not standard notation; should be defined in your textbook somewhere nearby

[proven relic]

How many possibilities to put integers number inside this block thats the sum of them is 300

Or like how many posiblities for x + y + z = 300

x,y,z >=0

[stray reef]

C(302, 2)

it's possible to make a bijection between triples of nonneg integers (x,y,z) st x+y+z=300, and arrangements of 300 white stones and 2 red stones in a row

[proven relic]

Why

I did this why its wrong

@stray reef

[stray reef]

if you notice the message immediately below the one you replied to, i explained exactly why

i don't know what the notation D(n,k) = (3,300) is supposed to mean

[amber patio]

any one know, how it's done ?

[stray reef]

.... how what's done?

you're asked to make a graph based on a poorly typeset definition and then you're shown a completely wrong solution...

@amber patio

[amber patio]

yep, i am learning the concept & trying some problems
then i saw this in book

[stray reef]

then your book is shit.

[karmic prairie]

^ i can confirm, the definition of G has 2 "(" and 3 ")"

[stray reef]

not only that but their picture doesn't even correspond to their defn

you would have one loop at 4 and one edge from 3 to 4 and that's it

[amber patio]

[stray reef]

notation on the right is bad but you drew what i described accurately

[amber patio]

alright, i will try to learn better.

[unborn widget]

Can someone explain to me why am I wrong or right? I'm lost

i answered:

1. (a,b) =/ (b,a) not equals
   Hence, aR/b not related

2. R: A implies B = {(a,b)|a is element of A, b is element of , (a,b) element of A x B
   Then the relation of A to B is a subset of AxB
   honestly I just copied this in my textbook thinking that this answer makes sense

[cerulean wind]

1. R is a subset of B x A so it is not a relation from A to B.

2. Q is a relation from A to B because it is a subset of A x B

[unborn widget]

is my proof at no. 1 wrong?

[cerulean wind]

i didn’t fully understand what you meant

in 1

[unborn widget]

I see, thank you for answering tho.
but if you have time, would you enlighten me on why no. 1 is not a relation?

[cerulean wind]

it is a relation, just not a relation from A to B

[unborn widget]

OOOOOOOOOOOOOOOOOOOOOOOOOOOOH

thank youuuuuuuuuuu

[proven relic]

How many possibilities to set on 12 chair , 6 boys and 4 girls

Without any restrictions

Thats my answer

Or just( 12 10)^t

[remote anvil]

image is correct

also correct C(12,10) *C(10,4)

also correct C(12,10) * C(10,6)

[karmic prairie]

what if you can seat multiple people on top of each other

("Without any restrictions" 🤡)

[cinder stag]

Does anybody know how to prove that its surjective?

[coral parcel]

The expression has no value for x=-sqrt(2), despite the question claiming the function is defined on all of R-{sqrt(2)}.

Other than that, this is a follow-your-nose exercise: Let a be an arbitrary element of R, and show that f(x)=a always has a real solution (by expanding the definition of the function and going where the algebra takes you).

[north bay]

heey
do you guys know during the tableau method (for linear optimization)
you have these coefficient for your artificial variables however at the best solution those variables are equal to 0. So I was wondering what these values represent

is there any way for me to recover these values if I only have the best solution ? ( suppose I used an online solver to get it )

[blissful latch]

Hey guys, do you know how to solve this?

[plucky escarp]

can someone help me out with this

answer is : x^2, y < x (theorem: if a < b and c > 0, ac < bc)

i dont understand why so

[stray reef]

you want to contradict minimality

to do this you want to find an element in S that is smaller than x

[plucky escarp]

how would i know to square x?

is it becuz x is known to be >0 and <1

what if i do something like, x - k where k is a number smaller than x

[stray reef]

where are you going to get a number smaller than x?

[plucky escarp]

oh wait

ohhhh

okay i see it now

[plucky escarp]

how about 1.7 thou?

i dont see where that theorem is used

[stray reef]

the theorem guarantees you that since x < 1 you have x*x < x*1

[plucky escarp]

ah

[plucky escarp]

i see it now, tysm!

[spice basin]

Can you explain to me why c is the correct answer in this problem ?

the more i analyze what the worksheet given, the more I find myself stuck

[cerulean wind]

convert the first condition into
“if Binh is not the tallest, then An is the tallest”
so that you can check which make sense between Binh being the tallest, in the middle, or shortest.

if Binh is the tallest, then Tam is the tallest, and we can’t have two tallest people in a group (assuming that nobody is the same height)

if Binh is in the middle then An and Tam are both the tallest, which again doesn’t work

[spice basin]

i tried your way a few times but i didn't get it until now

I think we just need to test each answer one by one to check whether each of them fit the given condition

[dawn forum]

1.if an not tallest -> bin tallest
2.if binh not shortest -> tam tallest

a) an is tallest -> 1 and 2 applies -> possible
b) bin is tallest -> an isnt the tallest (undecided position), tam is also tallest -> not possible
c) tam is tallest -> 1 doesnt apply (either an or binh are tallest), 2 applies -> not possible

@spice basin

idk if this explains anything new

a is the only possible way

[orchid hull]

Anyone familiar with ceiling/floor equations and discrete?

[coral parcel]

https://dontasktoask.com/

[willow fog]

> Discrete math channel
> "Anyone know discrete math?"

[pastel hollow]

Any Java experts around?

[inland rose]

try the java discord server

or stackoverflow

[final cliff]

So, the truth table they've given you directly gives you the SOP expressions for the function X and minterms. I haven't done much with POS and maxterms but they should just be based on duals so it should be super similar.

Let me give a simpler example. Consider the truth table of A+B (go look one up or write one down to see what I mean), each row containing a 1 for the A+B column corresponds to a minterm in the SOP expression for A+B. They are AB,(-A)B and A(-B), so A+B=AB+(-A)B+A(-B).

These minterms are derived by looking at the 1's and 0's of each row containing a 1 in the A+B column basically. For example (-A)B is the row with A+B=1,A=0,B=1.

You might wanna be a little careful and make sure this all matches your books/notes because I haven't done this kinda thing in a while btw.

For simplifying an expression via kmaps I'd recommend looking up examples done in youtube vids. It's easy enough, but it's pretty graphical and I don't know of an easy way to explain it.

[orchid hull]

What’s the best method here?

I know the answer, but got it by guessing kind of.
Removed the ceiling and just solved x = 5 and continued with range =>
5-n <= x <= 5+n
Correct answer:
4.25 <= x <= 5.25
So n= 0.25
Not sure how to get n other than guessing though

[coral parcel]

4.25 <= x <= 5.25 doesn't sound right. The value of ceil(4x-7) increases by one at x=4.75, but the value of ceil(2x+3) doesn't -- the the equation cannot be true at both 4.7 and 4.8.

Ah, perhaps that was a typo and you meant 4.75 rather than 4.25. But it should still be 4.74 < x <= 5.25 with a strict inequality at the lower end.

This suggests a way to think of the equation, though. The function f(x) = ceil(4x-7)-ceil(2x+3) increases by one at every odd multiple of ¼, but at even multiples of ¼ the two ceilings both jump in opposite directions, so f(x) don't change. So therefore the solution to f(x)=0 must have the form of the interval between one odd multiple of ¼ and the next odd multiple of ¼.

Locating that particular interval by removing the ceilings sounds like as good a method as any.

[orchid hull]

Meant .75 yes*

[orchid hull]

But 4.75 works no? 13 = ceiling 12.5 => 13

[coral parcel]

No at x=4.75 the equation ends up claiming ceil(12) = ceil(12.5).

[orchid hull]

Oh u right, it’s getting late 👴🏻

[orchid hull]

But i guess you meant

4.75 < x <= 5.25 then

[coral parcel]

Argh, yes. The .74 was definitely a typo.

[orchid hull]

Or how does it become .74

Ye

Thanks!

[coral parcel]

Muphry's law strikes again.

[orchid hull]

I’ll read it tomorrow and see if i can understand the method, but yea, think i got it decently:)

[fallow zodiac]

Can I get a little help with this? I keep coming up with the wrong answer

[coral parcel]

Which wrong answer do you keep getting, and what do you do to get it?

[fallow zodiac]

I followed these steps from my professors notes

[coral parcel]

That seems to be complete different numbers than the question you first posted.

[fallow zodiac]

yeah it is, I plugged in my numbers into my teacher's notes

in this case the 23=54939 and the 61=91608

[coral parcel]

Based on the available information I have no idea what you're doing wrong. ¯_(ツ)_/¯

[fallow zodiac]

Ok I actually got it, I found an algebra error in it that I solved and now I got it right

[plucky escarp]

can someone tell me the idea of how to prove this?

[cerulean wind]

what can you say about X if X is in P(A intersect B), i.e., what is X a subset of, what is A intersect B a subset of?

[stray reef]

@plucky escarp a proof by element-chasing ought to work

i.e. to prove two sets are equal prove they are subsets of each other

[proven relic]

Combinatoric proof

[unreal stump]

You want a combinatorial proof?

@proven relic

So what have you tried

[proven relic]

right hand: choose 2 animals from n dogs and 1 cat 😆

[unreal stump]

So Let's say you have {1,2,3,4...n+1} and you have to pick 2 numbers. Let the numbers be x and y with x>y WLOG

So let's say x is k

For y you have (k-1) options

if x were 1 ,you can't choose a y
So (1-1)=0 options
If x were 2 ,y={1}
x=3 ,y={1,2}
...
x=n+1,y={1,2,3,...n}

So this corresponds to
0+1+2...+n

[proven relic]

Why make it hard

Cant with animals?

[unreal stump]

Animals don't have an ordering

[cerulean wind]

there’s no ordering here

[unreal stump]

I wonder if this generalises to
\sum_{i=1}^{n} i^k

[unreal stump]

Well if x were k,there being (k-1) options for y requires order

Because I ordered the set as
1<2<3...k-1<k

[proven relic]

How you know there is no ordering

For the animals

I know thats C

[weary tiger]

what r u studying

[vagrant prairie]

pretty sure he's trolling 😂

[proven relic]

do you even know the answer

No

.

[ember obsidian]

@proven relic can u stop being an asshat

[proven relic]

https://tenor.com/view/cristiano-ronaldo-soccer-footy-football-futbol-gif-22763381

[ember obsidian]

i take that as no

come back in 24h

[vagrant prairie]

bahahahhaha

[cerulean wind]

consider n coins each having a value k for k between 1 and n. i want to find out how much money i have, so i have to add the value all the n coins, which is 1 + … + n. this is fine and dandy, but takes a long time.

a friend notices that if we group the kth and (n-k)th coins together, then each group of two coins has the same sum. if n is even, then there are n/2 pairs of coins each having value n+1. if n is odd, then there are (n-1)/2 objects with value n+1 and 1 coin with value (n+1)/2.

adding the values of the groups coins in either case results in n+1 C 2

friend has solved the problem and it no longer takes me forever to find out how much money i have

@proven relic this work for you?

[stray reef]

they are muted

[cerulean wind]

oof

[vagrant prairie]

really nice word description tho, nice to conceptualise

[cerulean wind]

thanks

[desert edge]

When I have to prove 1^3+2^3+3^3…n^3 =(n^2(n+1)^2)/4
What does the left hand side imply

That every n will be some cube?

it works for my base case but when I plug in n>1 I get results such as 9 for n=2, 36 for n = 3 etc

[austere cedar]

you have to show that the sum of the first n cubes is n^2(n+1)^2/4

[spice basin]

firstly, I solve this problem by f(x) = f(y) => x = y

by doing that way, i have proof that both of them are 1-1 func

but when i used a graph calculator

i see that the f(x) is 1-1 as it only intersects with the y-axis whereas g(x) is not 1-1 because it crossed two points

so are both of them 1-1 funcs ?

maybe i misunderstand the way we proof by using graph

[whole agate]

Hi everyone. So, l have this problem that l can't solve about combinatorics.
How many ways can 40 books be arranged on a shelf, if among them there are 10 books that are 10 volumes of a novel and are marked with the numbers 1,2,3,4,5,6,7,8,9,10, so that these 10 volumes are in ascending order (they do not have to be next to each other on the shelf).

My first approach was by using combinations. So, l have to place 30 books that are not marked between those who are marked, for example, l can have between novel 1 - 2 about 5 books, about 2 - 3 none, about 4 - 5 let's say 10, etc.., so l used this formula for Combinations,
C( 30 + 10 - 1, 30) = 39! / (39-30)! * 30! and l got 211 915 132.

My friend decided first to use combinations to place those 10 books on the 40 places that are available,
C(40, 10) = 40! / (40-10)! * 10!, and when calculated, he can do that in around 800m ways, l don't remember the exact number, doesn't matter, but after he calculates that number, using combinations, he then multiplies it with 30!, that's the number of ways that those 30 books can be placed, and in the end, the number of ways for the whole problem is just too big, like it goes to infinity.

Sorry for my poor english, l tried my best to explain the way l approached the problem and my friend, l want your opinions on this and how would you solve it.

[final cliff]

I think you made a mistake in your proof that f(x)=f(y) implies x=y.

Notice f(1)=2,f(-1)=2, but 1 is not -1.

Oh wait.

This never happens from N to N.

Actually yeah. They are both 1-1 on the domain N.

When you graph them you have to be careful to graph them on the correct domain.

[karmic prairie]

your friend is right: first choose where the 10 books will go, place them there, then fill the last 30 slots with the rest of the books
in the end you get C(40, 10) * 30! = 40!/10! = 224844379201911853600532206127677440000000
it's big, because the 10 volumes constraint is really not that big compared to 40!

[whole agate]

yeah I realised the mistake, thanks though 😄

[whole agate]

Here's another one l have doubts with

39 students from the first, second and third year should be selected for one survey, so that at least 8 students are from the first and at least 3 are from the second year. In how many ways can this be done?

[fallow salmon]

About arguments / validity
I know if all hypothesis / the argument is true, and the conclusion is false, then the argument is invalid

but what about the opposite (not all hypothesis are true, but conclusion is true) / if there is no situation where all arguments can be true at the same time

At least I think this is the correct channel to be asking about this

[weary tiger]

is x == 1?

can somebody confirm pls?

[amber hill]

Nope

X is not that

Hint use binomial theorem

[weary tiger]

Guys how to solve this in python.. I tried somehow.. is my approach anywhere near solution

Its given in 1st text

Dm if you can explain a solution

Plz

[cerulean wind]

for future reference, x = ||3||

[formal flicker]

Guys does anybody know a book with the same chapter covered in it? Cause I am find it hard to understand this book.

[fickle plume]

A first course in discrete mathematics, John C. Molluzo and Fred Buckely

[north bay]

hii
I am asked to prove this partition identity by using durfee squares but tbh I don't even know what the left hand side represents. Does anyone know what the left side represents geometrically / ferrers diagram

because of the n^2 in the exponent I assume its related to building the ferrers diagram by using lots of durfree squares

but it just doesnt make sense yet

[formal flicker]

Thx

[true venture]

How is the left hand side evaluated at n=0?

[north bay]

hmm 1 I guess ?

[true venture]

How would you relate this to partitions , like the coefficients are the partitions?

[north bay]

This 1 means that the partition of 0 can only be written in 1 form which is 0

hmm not sure if thats what you meant

[true venture]

Oh so n is the number being partitioned, yea that helps

[worldly knot]

where did the values come from? what does it mean "by algebra"

like where did the 7 come from

[meager sparrow]

you just multiply out the parenthesis: $(15-13)\cdot 6=6\cdot 15 - 6\cdot 13$ and thus $13 - 6\cdot 15+ 6\cdot 13=7\cdot 13-6\cdot 15$

[vital dew]

Ursus1234

[worldly knot]

gotcha thank u!

[worldly knot]

why is 7 paired with 13 tho

shouldnt it be 15?

[true venture]

Maybe it's related to the number of partitions you can make with a durfree square length n, that are not larger than n+n^2

[true venture]

Did you figure this out?

[north bay]

hii
I decided to take a nap because this week has been cruel with me
Ill get back on it a little later

[north bay]

I shall test this

it sounds very close to some other proof I saw on the internet

[true venture]

Oh gotcha, sry your week has been tough. Rest up!

[north bay]

oh no its fine !! I appreciate you trying to help me !!

[meager sparrow]

no, why would it be paired with 15?

or paired with is a weird frasing. you have 13 and then you have 6 times 13, which makes it 7 times 13

[pastel hollow]

I found that the generating function for a sequence $f(m, n)$ is
$$F(x, y) = \sum_{m, n}f(m, n)x^my^n = \frac{xy}{1-(x + y)}$$
I tried expanding it as a geometric series and i got
$$F(x, y) = \sum_{r \geq 0}\sum_{k = 0}^r\binom{r}{k}x^{r - k + 1}y^{k + 1}$$
Is there any way I can use this to find a closed form expression for the coefficient of $x^my^n$?

[vital dew]

EdgarAlnGrow

[pastel hollow]

never mind, i got it

[craggy knoll]

f : [1..n] →[1..2n] such that for all x in the domain, either
f (x) < x or f (x) ≥2x. How many distinct functions are there of this form?

where n is a positive int

anyone have any advice on how to do these types of problems?

[coral parcel]

Given an x, how many valid possibilities are there for what f(x) can be?

Multiply all those counts.

[light heath]

Am I allowed to use simplification on this conditional on the conclusion of it?

[elder fern]

[light heath]

does that mean no?

[north bay]

Ok so this is what I got:
(the z^n controls how many parts)
(so in the denominator the (q;q) will vary only the size of the parts while te (zq;q) will change the number of parts therefore the left side says something like this:
build a durfee square with sides n then the (q;q) will be responsible for adding more parts to the ferrers graph while the (zq;q) will be responsible for increasing the size of the parts (adding dots to the right of the durfee suare )

the right side of the identity is basically every partition possible

so on the leftside we will be adding every partition that has a durfee square of sides n (with as many dots we want to the right of the durfee square) and (with as many dots we want below the durfee square)

hmm that text is very confusing

thats more like an argument than a proof

but I think it is something along these lines

ok in other words

build a durfee square with sides n

now the denominator will be responsible for adding dots below and to the right of that durfee square

[true venture]

Oh I sort of get that, you should draw some examples

[north bay]

yeah! and I forgot to mention but the reason why the (q;q)_n goes up to n is so that we don't draw dots to the diagonal of the square (therefore making a new square which we don't want)

in this class

proofs that are more of drawing and giving arguments

sounds more powerful than any proof using only math

which is cool

[true venture]

What class is this for?

[north bay]

I don't really know how to translate it to english

one sec let me see if I can find on the internet

its called enumerative combinatorics

[true venture]

Cool, I'm just interested in this things. I need to take some actual classes tho

[north bay]

yeah !!

discrete maths is amazing

[true venture]

I'm still not sure how the denominator gives every partition with a n durfree square. Could you draw out an example for n =2?

[north bay]

I think its something like this:
take the (q;q)_2 = (1-q) (1-q^2)

so like 1/{1-q} = (1+q+q^2 ... )
and 1/{1-q^2} = (1+q^2 + q^4 .... )

so like you will be able to draw

lines of size 2 or 1

represented by green and blue dots

in this case q^4 from 1{1-q^2}
is the same as drawing 2 columns of green dots

and the same idea for the (q;zq) but instead we would draw those green and blue lines below the durfee square

because adding +1 to the exponent of z means adding one more part

[true venture]

Hmm thanks, I get it a bit more. I will have to try to draw the 3 square myself.

[cursive aurora]

If a, b and c are the roots of the polynomial 3x^3+11x-14 and sum of the roots is 0, then find the value of a^3+b^3+c^3.
how to do this

[naive saffron]

First write $3x^3+11x-14=3(x-a)(x-b)(x-c)=3x^3+(...)x^2+(...)x+(...)$, where each $(...)$ is some expression of $a,b,c$. These expressions should be fairly nice. Then by compare coefficients you know what those expressions equal to, and now try to write $a^3+b^3+c^3$ in terms of those expressions

[vital dew]

Whoever

[naive saffron]

This might be a bit difficult so you want to know what newton's identities are

@cursive aurora

[formal flicker]

Does anybody know how is the circled part justified ? Cause it does not make sense based upon the definition of Cartesian product.

[spice basin]

Hey guys, can you explain why the answer is 917

By doing traditional method, i get approximately 600

[stray reef]

traditional method?

wait, do you get a decimal? @spice basin

[spice basin]

i just plug in i from 1 to 5 into the inside-parenthesis equation

[spice basin]

yeah

it is 600.71445

[stray reef]

i think maybe whoever wrote this intended to have $2 \times 3^i$ and not $(23/10)^i$

[vital dew]

Ann

[stray reef]

also i goes from 0 to 5 anyway, not from 1 to 5

[spice basin]

oh yeah me too

i went from 0 -5

the above text is typo

[spice basin]

let me try that again

[formal flicker]

Does the book have answer sheet ?

[fickle plume]

yes but only for odd numbered problems, the answers is in the end of book

[formal flicker]

With explanation?

[fickle plume]

no

if you want help in any problem you can send here

[coral parcel]

Yeah, that's not valid at all. The two lines are globally equivalent, but the circled parts of them are not themselves equivalent. I'd call that a bug in the proof.

[winged kelp]

hey guys, i was wondering on the solution for the first function with n^0.99999 log n , how can i make sense of the solution ?

how is n^0.999999 log n = O(n^0.999999 * n^0.000001) ?

[stray reef]

log(n) grows slower than any power function

recall that for any c > 0, log(n) is O(n^c)
they take c = 0.000001 here

[winged kelp]

ooo

[winged kelp]

thank you. lol its been awhile i worked with any math - is it basically this? how is it we can accept the conversion to be base n , wouldnt base become 10 by default? like O(n^0.999999 * 10^0.000001) ?

[stray reef]

what are you talking about base n here?

no, this is not about the definition of logarithm at all...

[winged kelp]

oh

[stray reef]

also tbh that looks like a terrible explanation you posted

[winged kelp]

tbh, im lost as well LOL.

[frank latch]

@tribal bolt hey

[formal flicker]

Is the set of all equivalence classes equal to the partial ?

Is A/R equal to the Partition of A?

[molten birch]

yea, the set of all equivalence classes is a partition of A

if im not wrong

[formal flicker]

What is the meaning of highlighted parts?

[proven relic]

Wanna make a group of 4 people:
We have 5engineers, 12 worker, 8cleaner’s.
How many possibilities to make this group thats in this group have 1 from every type of work

[coral parcel]

It's pretty bad typesetting, but: The first highlighted part tells you the symbol for the new relation it's about to define. The second is the actual definition, using the common infix notation for relations: x R y stands for "(x,y) element of R", but here instead of R we have the new symbol shown previously. (Plus some parentheses with absolutely horrible spacing).

The thing that looks like a miniature integral with a dot to the left of it is probably supposed to be a script capital S.

[coral parcel]

You can either use inclusion-inclusion, or divide into three cases depending of which of the three professions you have two of.

[proven relic]

I did this

[coral parcel]

Yeah, but that counts each solution twice, because if the last person is, say, an engineer, you could also have chosen him first, and then chose the other engineer in the group as the fourth group member.

So you can do that, but you need to divide by 2 afterwards to correct for the overcounting.

[formal flicker]

The book is shitty and confusing af. Do you know a better book that covers the topics below? ( it would be amazing if the book has answer sheet for at least some of its practice questions.

[coral parcel]

Sorry, no.

[formal flicker]

Still no?

[formal flicker]

Topics in the pics

[coral parcel]

Yeah -- I'm very bad at recommending books.

[formal flicker]

Ok, thank you so much for the explanation:) it was very helpful

[whole mist]

I'm a bit confused for 9g as to why the universal quantification for w is utilized

[weary tiger]

how did u calculate it ?

[cerulean wind]

(x + y)^n = sum (n C k) x^k y^n-k from k = 0 to n

choose appropriate values of n, x, and y

[serene marlin]

how does one do C

the answer for a and b are

29 choose 9

and

19 choose 9

I am flabbergasted on C and completely delusional on what direction to approach this question

[cerulean wind]

every child has to get at least one chocolate, so there are 10 chocolates left after giving each child one choco. now its the same as asking how many ways i can put k balls (give away k chocolates) into 10 boxes (to 10 kids), then summing the result from k = 0 to 9, since you dont want to get rid of all 10 chocolates

@serene marlin

[serene marlin]

Would this work?

by no chocolate i am no chocolate left to givce out

[cerulean wind]

you are missing all the cases where we give out, say, only 8 of the 10 remaining chocolates by choosing 9 every time

also, where is 19 coming from? what items are you referring to?

[serene marlin]

what Im doing is there are initially 9 dividers + 10 chocoaltes --- hence the 19 ( 10 comes from inital 20 chocolates - 10 given out to 10 kids since each has to have one

then

for the choose 9

I am choosing 9 dividers to seperate the remaining candies into 10 baskets

[cerulean wind]

ah okay i was misinterpreting then

[serene marlin]

According to my logic would the answer be appropriate then?

[cerulean wind]

this method will work but you are calculating it incorrectly

of the 19 items, choosing 9 arbitrarily doesnt guarantee that you have chosen 9 dividers

you could have chosen 3 chocolates and 6 dividers

which messes up how you are giving away your chocolates

[serene marlin]

See what ur saying makes sense but our prof went over something like this in class (not C but B) and he did it exactly the same way

[cerulean wind]

this assumes that all of the bananas need to be distributed

we dont want to get rid of all ten chocolates here

[serene marlin]

then what could I do to resolve this?

[cerulean wind]

this is the method of stars and bars (distribute n objects into k distinct bins such that each bin has at least one object). it should be (n - 1) C (k - 1), so in the banana example, 9 C 4

[serene marlin]

ahh ok, ill give that a shot, thansk sm man

[cerulean wind]

im not sure why i just didnt do this first

[serene marlin]

lmaoo

allg

Before i let u go I jsut wanna make sure I did D correctly

i just took 19c9 - the number of bad options

is it that simple or am i missing a step

[cerulean wind]

let me think on it

[cerulean wind]

@serene marlin just to clarify, the number of ways to put n balls into k boxes with each box non-empty is (n - 1) C (k - 1). to see why, there are n objects lined up. there are n - 1 gaps between all of the objects. i need to choose k - 1 of these gaps to fill with a divider to determine a pairing of n objects into k boxes. the number of ways to do this is (n - 1) C (k - 1). in your case, it would be 19 C 9, i apologize all the confusion i caused earlier.

then yes for part d), just calculate the number of bad options and subtract it from 19 C 9

im quite tired atm haha

[serene marlin]

ur crazy for being tired and wanting to help ppl for math for fun

[cerulean wind]

yea im just procrastinating all the work i actually need to be doing rn

[serene marlin]

lmaoo

well thanks for ur procrastination

[cerulean wind]

np 🥲

[winged kelp]

just going through the first page of discrete mathematics textbook, the first questions asks:
'Use variables to rewrite the following sentences more formally.

• Are there numbers with the property that the sum of their squares equals the square of their sum?'

the solution goes,

but im wondering how how did we arrive that there is only variables of a + b

and wouldnt be a^2 + b^2 + c^2 = (a + b + c)^2 as well ?

or infintely more..

[obtuse lance]

yeah I agree, the way it's phrased it's vague, what you said sounds good

[winged kelp]

thanks for clarifyin 👍

[obtuse lance]

you're welcome

[amber patio]

Any Idea to check isomorphism
Or
Sol.

[coral parcel]

The vertex you marked "a" definitely can't be it, since it has only two neighbors in the drawing, but three neighbors according to the list.

[stray reef]

where's the closing brace in "{a, b, c, d, e"?

and also yeah that

[amber patio]

oh, sry i forgot to mention.
{a, b, c, d, e }

[stray reef]

i think you may want to draw graph 1

[amber patio]

Here is Proper Question

[stray reef]

okay well now looking at the drawings are you able to tell if they are isomorphic?

[amber patio]

Nope, edges are different

[stray reef]

i asked about isomorphism, not literal equality.

[amber patio]

I am not clear with the concept of isomorphism

I know it's one cond.

[stray reef]

do you want the formal version or the informal version

[amber patio]

Vertices-edges same ?

[amber patio]

Just informal
I want to solve this just

[stray reef]

two graphs are isomorphic if they are the same when stripped of all vertex and edge names

[amber patio]

Okay

[stray reef]

in your case they are both this

[amber patio]

With different edges?.

[stray reef]

what do you mean by "different edges"?

[amber patio]

C has 2 edges a&d in graph one
But in graph 2 c has 3 edges a,d& b

[stray reef]

these graphs are not equal, yes.

even though their vertex sets are the same, the edges are different.

but (and i am speaking informally here as you asked) ignoring all names produces the same picture for both graphs.

[amber patio]

okay ! got it👍

you have any source, to Learn Graph better.

[stray reef]

no

[formal flicker]

Can somebody please explain the first part of the proof( the part placed into parenthesis)? Because I literally don’t get it

[lone raft]

This is not discrete math but you have a right triangle.

Next time try #precalculus

[tidal sage]

oh ok

[worldly knot]

could someone clarify to me what "lists of branded items can he come up with" mean?

does it mean how many branded items in total is available in the supermarket that he can get?

or does it mean how many variations of different brands can he get

[north bay]

he was asked to buy 2 detergent
and there are 5 brands of detergent there so I believe it asks how many ways he can buy 2 detergents

same for the others

[worldly knot]

5^2?

[north bay]

uuh no but idk

[worldly knot]

yeah i get what u mean

[north bay]

wait

[north bay]

yes

i think yes idk am confused

[worldly knot]

to my understanding u just add all those

[north bay]

you should multiply them

[worldly knot]

5^2, 10^3 ewtc

idk if its right tho

[north bay]

because for every list of detergent he will also have a list of floor wax and also have a list of soda

[worldly knot]

hmm

[pastel hollow]

can the generating function for $a_n^2$ be expressed in terms of the gf for $a_n$?

[vital dew]

EdgarAlnGrow

[weary tiger]

@hollow mantle

sorry for the ping

have u been in touch with l'arithmétique recently?

nyways

so for part 2 1c

ive used the fact that x n y are a solution

so gcd(17x^(p-1);y^(p-1))=gcd(2021;y^(p-1))

then gcd(17x^(p-1);y^(p-1);p)=gcd(2021;y^(p-1);p)

and since gcd(2021;p)=1

then gcd(17x^(p-1);y^(p-1);p)=1

[hollow mantle]

off, i remember that in terminal... I suffered

[weary tiger]

LMAO

I am suffering

[hollow mantle]

I don't remember the ^ notation tho

[weary tiger]

wait thats power

oh wait mb

gimme a sec

[weary tiger]

it's le plus grand diviseur commun

idk if u'll be able to help

[hollow mantle]

Oh, so they are coprime

[weary tiger]

should I keep going?

[weary tiger]

no but wait

[weary tiger]

yes

mb i was thinking abt something else

anyways heres where i end up

wtf

i can eliminate the first case by setting p=17

the second one will give me the reslut i want

but idk how to discuss the third one

[hollow mantle]

Honestly, it was a too long time ago, i'm sorry....

[weary tiger]

all good 😭

this means i have to translate

then im not going to translate it

[obtuse lance]

yeah it's kind of gross tho https://en.wikipedia.org/wiki/Generating_function_transformation#Hadamard_products_and_diagonal_generating_functions

[subtle ermine]

Assuming I have

[vital dew]

ShadowIo

ShadowIo

[subtle ermine]

I think it doesn't

Because under mod 12

a is in a specific congruence set, and it's equivalent to all numbers in that congruence set

To change the modulo adds/decreases the number of congruence sets, and thus changes the meaning of what a repsresents

But I'm not sure if there's any relationship whatsover

?

[unreal stump]

It doesn't tell you anything

Wait it does mod 4

[subtle ermine]

Hmm that's what I was wondering

mod 4

Is 1/3 of 12

[unreal stump]

a=12k+3=4(3k)+3=3 mod 4

It doesn't tell you anything mod 5

[subtle ermine]

And if I do
a = 3 + 12k
a * 3^- 1= 3^-1 * 3 + 4k
a ^+* 3^-1 = 1 + 4k

so

$$a * 3^{-1} \equiv 1 mod (4)$$?

[vital dew]

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

[subtle ermine]

Is this true then?

[unreal stump]

Yes

[subtle ermine]

But what if I wanan look at mod 24

$$a = 3 + 12k$$
$$2a = 6 + 24k$$

$$2a \equiv 6 \pmod{24}$$

[vital dew]

ShadowIo

[subtle ermine]

Doesn't this add issues

The inverse of 2 doesn't even exist

So does this only hold when you simplify or smth?

Because by multiplying I added solutions

Well not add solutions

like....made them all have a gcd > 1 :/

[unreal stump]

There's an idea called zero divisors

2 is a zero divisor of 24 and {2*12,2*0} are the only things that reduce to 0

So a-3 has to be 12 or 0 mod 24

Both cases reduce to your original solution

Actually you can never add solutions by multiplying with a constant that's not (new mod) or 0

[subtle ermine]

Hmm I see

[subtle ermine]

So like here, even though a = 15 would technically work, we can't consider it a solution

Because we have to take into account that a equiv 3 mod 12?

[unreal stump]

Yea

So here I wanted to find x such that 2x=24 ,2x=48 etc

You get x=12,x=24 etc which are 0 mod 12

[subtle ermine]

Ah gotcha

@unreal stump Just wondering then...is they any approach I can take specifically that I can take with this.

I'm thinking that with any given modulo, you can learn more about modulo where it is a multiple of that modulo or a factor of that modulo

And that each time you have to make sure the number of solutions/the type of solution remains consistent?

[unreal stump]

Say you have a solution x=a mod m
And you consider solutions for kx=ka mod km
Then
k(x-a)=0 mod km
Which implies km divides k(x-a) which implies m divides (x-a)

Because k(x-a)=p km implies
k(x-a-pm)=0

[subtle ermine]

Hmm, I see, that makes sense

But while doing this, you have to ensure your m remains an integer

And you have to remember not to lose or add any solutions?

Aka keep it consistent?

[unreal stump]

We started with m as an integer

I guess you meant p

We can take k as a common factor so that works out find

[weary tiger]

Hello , I just want to ask how is the answer, 6 in the second box

[weary tiger]

Let $a_n = 106$ and $a_{n-1} = 100$, do you see now?

[vital dew]

Renegade

[weary tiger]

ohhh yes, thank you

to find the 10th term do i just have to substitute the n's by 10?

[vernal cypress]

Hi, does anyone know what subject this is?

[weary tiger]

combinatorics

[vernal cypress]

does this video explain it?

[weary tiger]

how can I tell you if I haven't watched the video

[sick bramble]

you have to watch it

[weary tiger]

im good

if i have the option not to do combs i'll take it

[sick bramble]

are you perelman ?

[empty spire]

hello

solve this

[subtle ermine]

What have you tried?

[empty spire]

I just want to know what are the hypotheses and conclusions in these two proposition, could you help me?

[subtle ermine]

I mean like

What do you think?

I could give you the answer sure

But that defeats the point of the question

[empty spire]

I donno, I tried for 3 days, I'm stuck in implication, what's the answer? and why tell me pls

[coral parcel]

What did you do for those 3 days?

This is not a "figure out some complex trick to solve a puzzle" exercise. It's a "verify that you've understood what these words mean" check question. If you don't know that, you should have used your 3 days to look up the explanations of the words in the question in your textbook or whichever other source you're using.

[karmic prairie]

Does your book/class/material/etc define "hypothesis" and "conclusion"?

[empty spire]

tell me the answer just -_-

[coral parcel]

No.

[karmic prairie]

I don't think that's productive at all, you might just have similar questions in a test and fail it if you just copy answers from a discord server

[subtle ermine]

It's fine if you are unsure and even if your approach is completely off :p
But providing a starting point ensures ppl can help you master the concept...not the question, which will help you on ur exam

[coral parcel]

Your time will be spent much more usefully by actually trying to learn the material, than by begging for random people on the internet to tell you an answer so you can fake having understood something you feel is beneath you to even attempt.

[empty spire]

you actually dunno the answer

😒

[coral parcel]

Good try. Nope.

[empty spire]

I know the definition of hypotheses and conclusion

look at the picture

these two proposition are different

[coral parcel]

Then what prevents you from answering the question yourself?

[empty spire]

if you know, then why can't you give the answer simply?

[coral parcel]

Because that would just be enabling your habit of thinking you don't need to learn anything yourself.

[empty spire]

seriously?

[coral parcel]

Yes.

[empty spire]

is this a puzzle that I've to think here?

this isn't any puzzle or problem

[coral parcel]

As I said, this is not a puzzle.

[empty spire]

Then why do I need think here?

[coral parcel]

It is a simple check question that verifies you have understoo what the words mean

[empty spire]

I just have a confusion

Man

[subtle ermine]

Everything demands you think.

What do you think of the phrases? You know what a hypothesis and a conclusion is, what connection can you make to each word in the sentence?

[coral parcel]

If you had spend the same amount of effort on actually looking up what those words mean that you have now used on whining here because we won't help you cheat, you could already have answered the question.

[subtle ermine]

I mean sure the question is simple... but just because something is simple doesn't mean the answer is given to you on your exam

[empty spire]

okay tell me the definition of hypotheses and conclusion

I made this question by my own

[coral parcel]

I'm sure you have a textbook that will tell you that.

No you didn't.

[empty spire]

lol

wait

wordpad that I've used

I made this to simplify what I want to ask

[subtle ermine]

That's cool and all xD

But.........let's start at the basics. What is a hypothesis? What is a conclusion?
What is the basic meaning of any conditional statement p -> q?

[empty spire]

as my pdf says, p is hypotheses and q is conclusion