discrete-math

[gleaming dune]

(n

(n _k) k!

not sure how u write combinations on discord lol

[spark gale]

Hmm ya I don't know the LaTeX for it either actually

[gleaming dune]

man this equivalence stuff is kinda confusing for me. So, do u know how elements in a equivalence class are different from the equivalent class itself

i thought equivalence class was the remainder u get from dividing

and u would have n-1 equivalence classes

[spark gale]

I'm kinda out for tonight. But I hope the answer makes sense when you land on it. I get the sense is around 27

Oh right we're counting equivalence classes

Lol totally lost track of the question

Ya the answer is just 7

It's the bottom part of your work there

You separated the classes when you saw what the sums could be

Haha. Damn I'm way too tired

[gleaming dune]

ah the range from 2-8 are the equivalence classes

[spark gale]

You're thinking of equivalence class in terms of the modulo relation

Different relation

[gleaming dune]

ah ok, and i just wanted to show u one last thing before u left haha, i worked up the proof till here but i don't know what the next step is

for the same question

[spark gale]

Ok

[gleaming dune]

so the last part is

and here is my work

so what im trying to understand is

are the elements in [h] going to be numbers that add up to 5 or are there no elements because A only goes from 1-4

[spark gale]

This is part of the last question?

Can you post the whole thing again?

[gleaming dune]

this is the last part of the same question

sure

[spark gale]

Btw start + shift + s

Copies a selection fast fast

Then you just paste it

[gleaming dune]

yh thats what im doing w snip and sketch

[spark gale]

Nah snip is slow

Just paste like you're pasting text

Right into discord

It'll change your life

Lol

[gleaming dune]

i was saving it then sending, i can paste it right away i didnt know that

niceeee

[spark gale]

On any good messaging app normally

[gleaming dune]

so for c, is it going to be there's 0 elements

because the sum of h1 and h2 is 5 and 5 is not an element in A

or is it numbers in A that add up to 5

which will be all of them

[spark gale]

I'll be honest I have no idea wtf they mean in that question. What the hell are the tuples even representing?

Lol I personally would ask for clarification from the prof on that one

[cerulean wind]

h is a function

[gleaming dune]

^

the tuples are the input/output from h

so h(1) is 2 and h(2) is 3

[cerulean wind]

its asking how many functions are equivalent to h

[spark gale]

So h(1)= 2?

[gleaming dune]

yeah

but i dont understand what it means by equivalent.

like does 5 have to be an element in A

[cerulean wind]

equivalent under the equivalence relation from the earlier part

[spark gale]

Ah okay

[cerulean wind]

so how many functions g are there such that h(1) + h(2) = g(1) + g(2) ?

[spark gale]

Ya seems kind of assumed. They really coulda just said on R again or something

[gleaming dune]

so to answer that do we need to know what g(1) +g(2) =?

[cerulean wind]

i thought it was pretty clear, but meh

[spark gale]

Maybe I'm just tired

[gleaming dune]

i just dont understand for this part what im supposed to be looking at

[spark gale]

Well your function h only outputs one value for h(1)+h(2)

[cerulean wind]

you know that if g is going to be equivalent to h, then g(1) + g(2) = h(1) + h(2) = 2 + 3 = 5

[spark gale]

So it's only part of one of your classes from earlier

[gleaming dune]

yes

[gleaming dune]

yes

oh like the equivalence class of 5

[spark gale]

Ya

[cerulean wind]

no, the equivalence class of h

[gleaming dune]

so there's only one equivalence class and that's 5

[cerulean wind]

what does the equivalence class of 5 even mean?

[gleaming dune]

yeah my mistake

it should be the equivalence class of h

that is 5

[spark gale]

All functions f(1)+f(2) that add to 5

[cerulean wind]

you're counting functions

[spark gale]

Is the class

[gleaming dune]

no but the question is asking elements

how many elements in the equivalence class of h

[cerulean wind]

the elements are functions

[gleaming dune]

ok ngl kinda confused now haha

[spark gale]

Ah ya

[gleaming dune]

so is 2 an element

[cerulean wind]

no, h is an element in the equivalence class of h, for example

[gleaming dune]

from f(1)+f(2)

[spark gale]

Okay so you're counting the way we were counting earlier.

All the elements in the class where f(1)+f(2) =5

I think?

K I'm not really helping anymore. Lol I gotta call it a night.

[gleaming dune]

yeah and that's what im saying

[spark gale]

Best of luck though!

[gleaming dune]

f(1)+f(2) = 5 only happens when the sum is 5

[gleaming dune]

thanks for your help man

there

[cerulean wind]

just take a step back and write out what $[h]$ is.
it is the set$$[h]={\text{functions } f:A\to A\text{ such that }f(1) + f(2) = h(1) + h(2)}$$

[vital dew]

c squared

[gleaming dune]

i dont even know what [h] is

thats what im confused on

like i see the definition u give

but f is not given right

[cerulean wind]

abstractly, if $S$ is a set and $\sim$ is an equivalence relation on $S$, then for any element $s\in S$, the equivalence class of $s$ is defined as $[s] = {x\in S:x\sim s}$, or in other words, $[s]$ is the set of all elements $x\in S$ that are related to $s$ through $\sim$.

in this context, your set $S$ is the collection of all functions from $A$ to $A$ and the equivalence relation says that two function $f$ and $g$ are related provided that $f(1) + f(2) = h(1) + h(2)$.

[vital dew]

c squared

[gleaming dune]

is there an example u can give me because i'm not understanding still

[cerulean wind]

so with this in mind, no, you dont necessarily know what f is, but you need to count all of the functions
f : A-->A such that f(1) + f(2) = h(1) + h(2)

[gleaming dune]

yeah so my question how do i begin counting all the functions ^ when i dont know what f is

[cerulean wind]

yes. so an equivalence relation on the integers would be $n\sim m$ if and only if $n\mod 2 = m\mod 2$.

the equivalence class of $[2]$ under $\sim$ would be $$[2] = {z\in\mathbb{Z}:z\mod 2 = 2\mod 2 = 0}$$ which is just the set of even integers.

[vital dew]

c squared

[gleaming dune]

ok so i did a diff example with a sum because it was going to be easier

can u check this and see if i did it correct

because this is easier to understand i think so then u might be able to help me understand the h(1)+h(2) part

i made up a h and defined the relation with the sum

ok so im getting an answer of 4 elements

f(1) = 1, f(2) = 4, that's one function

f(1) = 2, f(2) = 3, that's another

f(1) =4, f(2) = 1

and f(1)=3, f(2)= 2

[cerulean wind]

what about where 3 and 4 get mapped to?

[gleaming dune]

yeah i include that in the other one

[cerulean wind]

but then f(1) + f(2) + f(3) + f(4) > 5

[gleaming dune]

but we don't need to care about f(3) and f(4) right because it's just f(1) + f(2) we're focused on

[cerulean wind]

ohh i thought you meant for this

[gleaming dune]

oh no that was a random example i made to show u and see if i had the idea correct

so is 4 the correct answer for the original question i posted

for this

[cerulean wind]

yea, i dont know in what way you counted them here, but im pretty sure four is right

[gleaming dune]

my counting was that

if u choose f(1) = 1, then there's only one way to get the sum to 5 which is to have f(2) = 4

and the same logic

from f(1) = 2/3/4

is that correct?

[cerulean wind]

no but its on the right track

[gleaming dune]

how would u do it

[cerulean wind]

i would start off the same way you did

so take f(1) = 1.

then it uniquely determines f(2) = 4

but you still have to take in to account f(3) and f(4).

so i will give two examples

1 --> 1
2 --> 4
3 --> 3
4 --> 3

and

1--> 1
2 --> 4
3 --> 4
4 --> 4

[gleaming dune]

ah yes.... because f(1)+f(2) = 5 so just do 5-f(1) and u keep getting the new f2

[cerulean wind]

above are two different functions which satisfy 1 --> 1 and 2 --> 4. so you're answer under counts

[gleaming dune]

ok i see so that means then

the last 2 - f(3) and f(4) can be 2/3/4 which means 1x1x3x2 possible functions when f(1) is 1

so wouldn't you do it that way

then when f(1)= 2, f(2) = 3 unique, then f(3) and f(4) = 1x1x3x2 again because f(3) can be 1/3/4

and f(4) is 1/3/4 - what u chose for f(3)

[cerulean wind]

lets look back at the function
1 --> 1
2 --> 4
3 --> 3
4 --> 3

there are going to be 4 functions satisfying 1 --> 1 and 2 --> 4. those being

3 --> 3
4 --> 3

3 --> 3
4 --> 4

3 --> 4
4 --> 3

3 --> 4
4 --> 4

assuming that 1 --> 1 and 2 --> 4, of course

[gleaming dune]

so there's 4 for each f(1) that's chosen

[cerulean wind]

yea

[gleaming dune]

so that makes it 16 in total then

[cerulean wind]

im pretty sure thats right

[gleaming dune]

alright, but it seems like a very long way to explain it

there's gotta be a faster way doing counting or something

[cerulean wind]

its pretty quick if you summarize it again i guess. i was just drawing it out.

1 has to get mapped some where, and it uniquely determines where 2 gets mapped to.

there are four places where 1 can get mapped to, uniquely determining an initial segment, if you will, for a function.
for each place that one gets mapped to, there are 4^2 = 16 different resulting functions, so 16 * 4 = 48 64 in total

[gleaming dune]

so what i was thinking was

if u make a simple recipe

f(1) - chosen in 4 ways

f(2) - chosen 1 way determined uniquely by f(1)

f(3) chosen in 2 ways because it cannot be f(1) or f(2)

f(4) - chosen in 2 ways because it can't be f(1) or f(2)

4x1x2x2

= 16

[cerulean wind]

oh shit

[gleaming dune]

what happened

[cerulean wind]

i under counted again.

we could have

1 --> 1
2 --> 4
3 --> 1
4 --> 2

that would still work

[gleaming dune]

ok so it would just be

[cerulean wind]

so slight adjustment needed

[gleaming dune]

f(1) - chosen 4 ways

f(2) - chosen 1 way by f(1)

f(3) - chosen 4 ways

f(4) - chosen 4 ways

4x1x4x4

so 64?

its still a function even if multiple domains have the same codomain

[cerulean wind]

there are 4^2 = 16 functions A to A satisfying 1 --> 1 and 2 --> 4

so 4 * 16 = 48 64 in total

wait

[gleaming dune]

4*16 is 64

[cerulean wind]

shit

there are only 64 functions from A to A

waht

no 4^4 total functions

omg i just cant do math

yes were both right now lmao

[gleaming dune]

u sure hahah

[cerulean wind]

yea. sry i forgot how multiplication works

[gleaming dune]

so there's total 256 functions and 64 of em are elements of [h]

[cerulean wind]

ye

[gleaming dune]

alright i just wanna confirm one last time for this question the answers i got

I did a

and part b i got 7 equivalence classes

which was 2,3,4,5,6,7,8 which are the possible sums

and part c is 64.

is that correct

[cerulean wind]

i wasnt here for part b but that sounds right
and for c yes, 64

[gleaming dune]

part b i got the equivalence classes from the possible sums of f(1)+f(2) can be

and it ranges from 2-8, so there's 7 total

[cerulean wind]

yea. makes sense

[gleaming dune]

@cerulean wind i did another practice question, can u check to see if my solution here is correct.

this is the question

this is my solution

[cerulean wind]

everything is good up until checking transitivity

if you think the relation is transitive, then you have to show that for arbitrary X,Y,Z in P(A), that if XRY and YRZ, then XRZ

you cant choose what the sets are

[gleaming dune]

oh yeah, u can only choose if you're proving the negation right?

[cerulean wind]

yea, you want to provide a counter example if you think that the relation isnt transitive

[gleaming dune]

i dont think there is one because it is transitive

or wait

since we can choose the sets, that means i could just make Z big enough to have all the elements in X as well so X-Z = 0

[cerulean wind]

you still need that |Y - Z| = 2 tho

[gleaming dune]

yeah true so its not possible

[cerulean wind]

hmm. i think that it is not transitive

there is a counter example

hint : || |X| is 4, |Y| is 2, and |Z| is 0||

[gleaming dune]

oh yeah lmao why didnt i think of that

and by implying |Z| =0 it means Z is the empty set right

[cerulean wind]

yes

but it wont work for any old sets with |X| = 4, |Y| = 2

[gleaming dune]

sheesh

[gleaming dune]

what do u mean by this

[cerulean wind]

like, it wont work if X = {1,2,3,4} and Y = {5,6}

i only gave you a hint

right

[gleaming dune]

then it'll work right

thanks man i really appreciate the help

basically done just got 1 more part left

[cerulean wind]

sweet

[gleaming dune]

so for this part i did this

@cerulean wind

[cerulean wind]

hmm. @gleaming dune i cant really follow ur work and i dont think thats right.

i think that you should argue like this:

there are four cases.

case i) 1 in S and 2 in S. then S = {1,2,x,y} for two distinct x,y in {3,4,5,6,7,8,9}, so that there are 7C2 different sets S with 1,2 in S and S is related to {1,2}.

case ii) 1 in S and 2 not in S. Then S = {1,x,y} for two distinct x,y in {3,4,5,6,7,8,9} so that there are again 7C2 different sets S with 1 in S and 2 not in S and S is related to {1,2}.

case iii) 1 not in S and 2 in S.

case iv) 1 not in S and 2 not in S

[gleaming dune]

so its 7C2 x2 + 2

[cerulean wind]

no i left the last two cases for u lol

[gleaming dune]

wait so

why wouldn't my method work

because we're just isolating for 1 and 2 right

so 2^9 - 2^7 because we only care about 1 and 2 in S

wait can i just dm u this stuff it'll be much faster because i was following this

[split ginkgo]

Hi, I have a question about diffusion on a graph
If I want to calculate diffusion on a graph
which laplacian should I use?
https://en.wikipedia.org/wiki/Laplacian_matrix#Definition

and to control the "amount" of diffusion per multiplication?

[split ginkgo]

<@&286206848099549185>

[split ginkgo]

sad T_T
Is discrete-math the wrong channel to ask this question?
Are there more appropriate channel where it is more likely for me to get an answer?

[pine star]

Might just be a lull in server activity. Try posting again later

This channel is pretty active from my experience

[split ginkgo]

I see, thanks, finger corssed

[remote cosmos]

I have a question about a Ferrers shape theorem:

The number of partitions of n into distinct odd parts is equal to that of all self-conjugate partitions of n.

I'm assuming this is excluding the partition (n)? ...I'm assuming n is 1 part, which is odd and trivially distinct?
I.e. 6 and (3,2,1) are the two ways to partition 6 into distinct parts. (3,2,1) is self-conjugate and 6 is not. The size of each partition is odd and has distinct parts.

I get the gist of the proof and all. Just maybe unsure about the wording of the theorem.

I've tried drawing a few self-conj partitions at n=3, n=6, etc and it seems to hold to ignore the partition into the single element.

Thanks in advance

[faint narwhal]

The parts of the self conjugate partitions don't necessarily to be distinct. Also, odd parts means that each part is odd, not that the number of parts is odd @remote cosmos

[remote cosmos]

oh oh

but then hm

[remote cosmos]

this makes a whole lot more sense, thank you

[weary tiger]

could anyone give tips for this

[weary tiger]

count them

see how many there are dependent on the value of d

[austere swan]

Notice that if you choose 4 digits at random (not inc. 0), then you can generate a number with that property. Can you get all the numbers with the desired property like this?

(I'm assuming here that no larger means less than or equal)

[split ginkgo]

How to parameterize the "amount" of the smoothing in one operation "step"?

[weary tiger]

So @meager prairie is there anything in particular you don't get

Or are you just at a general loss

[meager prairie]

we were watching a lecture, it seemed to imply that you need to run the algorithm V-1 times before you can detect a negative cycle

this doesnt really make sense to me

also its not really clear how the algorithm knows to take a particular path over another

where is the number V-1 coming from, and why is it the Vth iteration that detects negative cycles instead of any other iteration

[weary tiger]

Ok gimme a sec

[meager prairie]

sure

[weary tiger]

Ok so for the negative cycles thing

You can detect negative cycles at any iteration

It's just that you need V-1 iterations to detect every negative cycle

Since the largest negative cycle will consist of V-1 links

[meager prairie]

Maybe I don't understand the algorithm in general. Would the graph need to be in a certain shape to get to the situation you're talking about, where you need that many iterations?

[weary tiger]

I can draw an example

You need 2 iterations to complete the cycle and find that it’s negative

It’s not hard to see that you need v-1 iterations to find the negative cycle if you have a circular graph like this

But the reason we do V-1 iterations isn’t to find the cycles, necessarily

It’s to consider all paths

Since at iteration n you basically consider the paths of length n

[meager prairie]

oh

that sort of makes sense

i still dont 100% believe that it's necessary to do it V-1 times but at least i sort of understand it now 😄

thanks 🙇‍♂️

[weary tiger]

We still haven’t really gone over how you pick paths, I don’t mind explaining that

    // This implementation takes in a graph, represented as
    // lists of vertices (represented as integers [0..n-1]) and edges,
    // and fills two arrays (distance and predecessor) holding
    // the shortest path from the source to each vertex

    distance := list of size n
    predecessor := list of size n

    // Step 1: initialize graph
    for each vertex v in vertices do

        distance[v] := inf             // Initialize the distance to all vertices to infinity
        predecessor[v] := null         // And having a null predecessor
    
    distance[source] := 0              // The distance from the source to itself is, of course, zero

    // Step 2: relax edges repeatedly
    
    repeat |V|−1 times:
         for each edge (u, v) with weight w in edges do
             if distance[u] + w < distance[v] then
                 distance[v] := distance[u] + w
                 predecessor[v] := u

    // Step 3: check for negative-weight cycles
    for each edge (u, v) with weight w in edges do
        if distance[u] + w < distance[v] then
            error "Graph contains a negative-weight cycle"

    return distance, predecessor```

This is the pseudocode I found on Wikipedia

@meager prairie i can go over how paths are found if you’d like

[meager prairie]

yea i am having a hard time understanding the pseudocode

i dont think i need to know it for this exam its just frustrating

[weary tiger]

It’s nice to actually understand yea

So this is a distributed algorithm which you’re running from some vertex s

And you initialize the distances as infinity to everywhere except yourself, that’s step 1

Then in step 2, we find the distance to every other node by considering paths of length n

[remote cosmos]

there's a good mit lecture on bellman ford

[weary tiger]

For example, in the first iteration you consider single-edge paths

[remote cosmos]

including practice problems etc

[weary tiger]

Yea actually that might be better

[remote cosmos]

https://www.youtube.com/watch?v=ozsuci5pIso

if it's still too dense, just go back a few lectures

[hoary igloo]

A simple graph in which each pair of distinct vertices is joined by an edge is called a complete graph. Up to isomorphism, there is just one complete graph on n vertices

what does up to isomorphism mean?

[faint narwhal]

Do you what isomorphism of graphs is?

[hoary igloo]

I believe so its when every edge/node of a graph can be mapped one to one into a different design of a graph

I know thats not a formal defintion but I didnt just want to copypaste something out of the book

[weary tiger]

So it means that if you produce two graphs complete on n vertices, they will be isomorphic to each other

[hoary igloo]

ah ok thanks

thats what I was going to guess just whenever I first start an entirely new branch of something wanted to make sure I know whats going on in the beginning

really appreciate it

[weary tiger]

[pine star]

Of a deck with 52 cards:
In poker the number of straights that can be created can be expressed as 10*4^5.

I think I understand why 10, but I don't understand why 4^5...

[grave sluice]

for every card there are 4 options (hearts diamonds spades clubs) and there are 5 cards in your hand

[pine star]

intuitively that represents all possible 5 card combinations

[grave sluice]

the 10 because you can start the straight with 10 of the 13 cards

[pine star]

yes

[grave sluice]

so if I give you the starting card you also know the next 4 cards but you dont know which suit they are from

lets say you have A,2,3,4,5
the Ace could be the Ace of spades but also any other suit

the same for every card

so thats 4^5

[pine star]

ah ok yes that makes sense thanks

[grave sluice]

no problem

[pine star]

4^5 is just the starting card

no

yes

[grave sluice]

what do you mean by starting hand?

its just for all possible ways of having a straight

[pine star]

right

nvm i got it thanks

[subtle charm]

~(p^q)
• r

I have the following argument above, but I am confused on how I should go about generating a counter example to prove whether this argument is valid or invalid

I know for a fact that I can just try to prove whether (p V (q ^ r )) ^ ~ (p ^ q) -> r is a tautology or not to prove that the argument is valid or invalid.

However, the questions wants me to generate a counter example to show that it is invalid.

[grave sluice]

you could check the truth table to find a counter example

[bleak void]

Say I have two partial orders p and q on the same set X. I can build a new partial order r so that r(x, y) = if p(x, y) then p(x, y) else q(x, y). Is there a name for this kind of partial order?

[spark gale]

likely in the stats channel

oh I see you were there

[outer hinge]

I’m really confused about “or” when talking about truth statements. I was under the impression that if you had something like p or q that one of these statements could be false but so long as one was true then p or q would be true

But for ~p or ~q both have to be false to be true

Why is this ?

Doesn’t this basically function as ~p and ~q ?

[remote cosmos]

huh

not quite, try drawing out the truth tables. and give p and q some actual statements to better visualize

even if some of the table values are the same, the implication is different

[outer hinge]

Oh

Wait a minute

I realized my problem

[remote cosmos]

so when you manipulate them in a different way it will be different

[outer hinge]

I was thinking of ~(p or q) as being the same as ~p or ~q

[remote cosmos]

either have to be false, not both

yea

but

even then, the negation is not the same

[outer hinge]

So the firs statement would be “Not p or q”, and the second would be “not p or not q”

[remote cosmos]

because of demorgan's

not (A or B) = not A and not B

[outer hinge]

Well I think I was just confused about how I was phrasing it. For some reason I was treating ~ like an operator

[remote cosmos]

it is an operator

(technically)

[outer hinge]

I guess I’m just confused on terminology entirely

[remote cosmos]

no worries

you can keep asking questions

[outer hinge]

What I mean is that I was treating it like there was something within parenthesis that is being multiplied

[remote cosmos]

ah yes, do you know boolean algebra?

i believe it's the same thing

[outer hinge]

I don’t think so, unless I didn’t know what it was called

[remote cosmos]

multiplication is AND and addition is OR

so 1 + 0 is 1

1 + 1 is 1

1 * 1 is 1

0 * 1 is 0

it's the same principles (no need to worry about learning it)

it's useful for logic gates

[outer hinge]

Ah okay, maybe I’ll learn more about it later. I’m really hoping I can get an in-depth understanding of math but I’m kind of afraid that I’m just gonna memorize a whole bunch of things rather than understanding how certain things were derived, the intuition or the proofs

[remote cosmos]

are you still feeling unclear about your original question?

[outer hinge]

I don’t think so. I think I understood my issue, it was just that I said the statement incorrectly. I treated ~(p or q) as ~p or ~q

[remote cosmos]

mit discrete math has a nice problem set for these type of questions

if you do those it can help get more situated with the flow of these things

[outer hinge]

I’ll have to look into that, thank you

[weary tiger]

don't worry, logic makes sense once you start to get into it and you'll begin to think in terms of it

[weary tiger]

@waxen nest #probability-statistics

[waxen nest]

anyone knows how to draw a graph to model this problem and explain it based on handshaking theorem or eulerian path?

[weary tiger]

For the graph model the rooms as nodes and the doorways as edges

Then you should be able to apply Euler's formula I think

[gilded axle]

like already mentioned, you make every room a node and the outside also needs to be a node, the doorways are edges connecting nodes. if you want an eulerian path from A to D you need an odd number of edges connected to A and D and all others vertices need to have even degree, which is a theorem you probably will have looked at in your course . ( the graph also needs to be connected but that is obvious here)

[waxen nest]

i dont quite understand why it says will contain an euler path if it contains at most two vertices of odd degree

[stray reef]

well, that's a result euler himself proved at some point, is it not?

@waxen nest has your class given you any proof of this fact? even a sketch of the proof, perhaps skipping over some boring details?

[waxen nest]

i cant find the definition for this online

if you want an eulerian path from A to D you need an odd number of edges connected to A and D and all others vertices need to have even degree, which is a theorem you probably will have looked at in your course .

[waxen nest]

i dont think so lemme try to search again

this is all the information i have 🤔

[stray reef]

oh so it's outside your scope...

they're withholding the proof from you then

hm

[gilded axle]

so just use the corollary without proof then

that corollary is exactly the theorem I mentioned that is needed to solve this exercise

[waxen nest]

ohh okay got it

does this qn have anything to do with handshaking theorem?

[weary tiger]

Not really, you don't need it for your question

[waxen nest]

okay thanks all

[plush helm]

Hi. I'm self studying basic cominatorics, and I'm sturggling with intuitively differentiating between n and k in written problems.
To illustrate this, I saw this problem - True/False: "the number of ways in which one could distribute 4 distinctive balls into 3 distinctive bags, equals to the number of ways in which one could distribute 2 distinctive balls into 9 distinctive bags".
Now I know the statement is true, because when both the bags and balls are distinctive, the formula is simply k^n. In which case, both cases are equal (k=bags;n=balls. 3^4=9^2).
But I'm struggling to differentiate between n and k. For example, my initial intuition was that the balls were k (since we are distributing the balls in the bags, and not the other way around), but this is obviously false.
Is there a smoother way to intuitively figure out who is n and who is k in those sort of questions? or any guidelines at all on that regard? I've been struggling with this ever since I started studying combinatorics, and I think it's too fundamental of an issue to overlook at this point.

Thank you all kindly.

[remote cosmos]

draw

k is usually used as the smaller entity when paired with n (but it can also take other forms so you always have to be paying attention)

but if you draw these a lot of the properties and identities will become intuitively simpler over time

like for example this identity

[vital dew]

pitabread

[remote cosmos]

sure, it's good to be able to algebraically prove it

but just as important (if not more) is the intuition as why this makes complete sense (without a single calculation)

[plush helm]

Thank you, my mind still immediately jumps to think about it in Algebric terms though

[remote cosmos]

that's ok

[plush helm]

I'm probably fundamentally lacking the combinatoric intuition

[remote cosmos]

once you draw them and try to put them in situations

you will start pushing in that direction

[plush helm]

I will work on that right now

Thank you very much

[remote cosmos]

i dont think many have it from the start

at least from my experience

[plush helm]

Possibly. To me, seeing (n m) just immediately throws me to the algebric form

[remote cosmos]

well you know it's called n choose m

[plush helm]

Yeah

[remote cosmos]

so try thinking there's n things

and you're picking m of them

[plush helm]

Yes, I do that

[remote cosmos]

you'll get it, just keep at it, don't lose hope

🙂

i personally like how blitzstein approaches it: https://projects.iq.harvard.edu/stat110/home

and also miklós bóna in a walk through combinatorics

[plush helm]

Thank you, I will look into them

The book I'm studying with is very old and poorly written

[remote cosmos]

blitzstein has videos too

just hearing him helps a lot

it's more reasoning than calculation from his angle

of course the proofs are important

but i think the reasoning motivates them

[plush helm]

Definitely, I'm fairly sure the proofs very much follow the reasoning in those problems

At least from my limited experience, since when I manage to make sense of the problem, the proof is always very simple

[remote cosmos]

oh some of these can get technical...

haha

[plush helm]

I'm sure they can but, it's probably relevant for more complicated techniques

Not just counting

[remote cosmos]

yes ofc

[plush helm]

Either way, I will definitely check them out and try drawing

I really appreciate it

Thank you for your time !

[remote cosmos]

np!

[vale shell]

https://youtu.be/PWTt2vgwhXM

[weary tiger]

any clean argument for why number of permutations of c is c^c?

[stray reef]

number of permutations of c? what exactly is that supposed to mean?

[lavish hornet]

hi guys, anyone can help me for this question?

Show that out of 9 arbitrary real numbers, there are always two of them, for example a and b, such that:
0 < (a-b)! (1 +ab) <.2 -1.

[weary tiger]

set of cardianlity c

obviouslyt

[lavish hornet]

this is

[weary tiger]

what's (a-b)!

for arbitrary real numbers

[lavish hornet]

i dunno. i confused about dicrete math 😦

[proven silo]

wdym with out of 9 arbitrary real numbers. If that is actually the question then it is false (for instance just take a_1=a_2=...=a_9) (there are other examples too)

[weary tiger]

it would be much easier if you understood the notation and what the problem is asking about... with what you said so far theres no way anyone will be able to help you. Ask your prof or sth if you don't have any notes/context.

[remote cosmos]

i guess it woudn't be too wrong?

[vital dew]

add

[remote cosmos]

maybe try some small examples to get a feel for it to motivate your proof

[weary tiger]

this is my first time posting, but i could use some guidance for this question. “Let G be a planar graph with c(greater than or equal to) 2 and no cycles of length 3. Prove that |E|(less than or equal to) 2|V| - 4”

[faint narwhal]

Have you seen how for any planar graph, you can prove that |E| <= 3|V| - 6?

@weary tiger

[hoary furnace]

Is it possible to map N arbitrary numbers to N consecutive numbers via some function F?

Example [63, 66, 92, 81, 66]:
63 -> 0
66 -> 1
92->2
81->3
66->1

[snow sleet]

yes this is always possible. notice that you may assume that you're given n distinct real numbers, because {63,66,92,81,66} is really just {63,92,81,66} and the same idea follows for arbitrary nonempty subsets of the set of real numbers.

Also note that the rule of a function f from the set of n distinct real numbers to a set of n consecutive integers need not be a nice and clean formula.

[hoary furnace]

Is such a function realizable? I am having trouble explicitly defining such a function mathematically/programmatically

[snow sleet]

yea you can definitely construct such a function.

Consider the given distinct real numbers as $x_1,x_2,x_3,\dots,x_n$ define the function $f:{x_1,x_2,x_3,\dots,x_n}\rightarrow{1,2,3,\dots,n}$ by the following rule. For any $i\in{1,2,3,\dots,n}$, $f(x_i)=i$.

[vital dew]

logician

[snow sleet]

notice that such a function is clearly a bijection

make sense? @hoary furnace

[hoary furnace]

Yes. I consider that as an implicit definition. But I don't think we can explicitly define such a formula, can you define f in a closed-form formula?

[snow sleet]

well we did explicitly define f. It's absolutely clear where each element in the domain maps to. Like I said before, the rule doesn't have to be so nice and neat. In fact, it might not always be possible to define f using a super nice and clean rule. I think my definition of f is prolly as clean as it gets (given general n distinct real numbers).

Depending upon what those n distinct real numbers are, in some cases, I bet there would be a nice and clean rule which you could use to define f...cleaner than the one I already defined.

[hoary furnace]

For example, N arbitrary numbers can map to even numbers via f(x)=2x. I was looking for a similar formula, but I think you are right, the way you have defined it is probably as clean as it gets.

[snow sleet]

yea and the 2x thing has some problems....first off, if x is an arbitrary real number, 2x might not be an integer. Secondly if x is an integer, 2x and 2x+2 are consecutive even integers, but they are not consecutive integers (due to the distance of 2 between them)

[snow sleet]

but that depends on what you meant by "consecutive numbers" here^

[hoary furnace]

Right. For my example, suppose we are dealing with arbitrary integers and the mapping is between arbitrary numbers to even numbers (not necessarily consecutive)

[snow sleet]

okay gotcha

yea 2x and 2x+2 are consecutive even integers but again not consecutive, so that rule doesn't work unless you would count consecutive even integers to be okay

it's really hard to define a nice and clean rule without knowing exactly what you're given

[cerulean wind]

use recursion

every non-empty, finite, totally ordered set has a minimal element

[snow sleet]

yea that's a good approach^

[cerulean wind]

the recursive approach won’t necessarily give you a clean formula, but it will give you a general method to map a set of n elements to another set of n elements, which can be implemented in a programming language, since u mention it

[hoary furnace]

Hmm, that would actually work in the programming sense. Is a mathematical closed-form formula also possible via this approach?

[cerulean wind]

hmm. by closed form formula, do you mean an actual formula like f(x) = x + 1 (probably unlikely unless given more information)?
or a collection of ordered pairs like f = {(1,2),(2,3),(3,4),(4,5)} (do-able)?
or a general recursive formula (do-able)?

like logician said, without knowing more information about the sets your given, there is probably not an explicit formula that u can use

[waxen nest]

hi can someone help me with this qn?

I think im supposed to use euclid algo to solve it

[remote cape]

can we find integers, a,b,c,d,e so that (a - b) (a - c) (a - d) (a - e) (b - c) (b - d) (b - e) (c - d) (c - e) (d - e) is a power of two?

or can we at least find rational numbers a,b,c,d,e so that that formula has a numerator power of two

[faint narwhal]

@remote cape The first one isn't possible, for that product to be a power of 2, each term has to individually be a power of 2 and this isn't possible

Note that finding rational numbers a,b,c,d,e so that the formula has a numerator power of two is the same thing as finding rational a,b,c,d,e so that the formula is a power of two since we can clear denominators

[remote cape]

huh

so

let me just quickly explain what im doing

and maybe you can help me with it ig

so what i want to have is a vandermonde matrix

so that the common denominator of the inverse

is a power of two

$$\left({\begin{matrix}1&0\0&1\end{matrix}}\right)^{{-1}}=\left({\begin{matrix}1&0\0&1\end{matrix}}\right).$$

[vital dew]

Control

[remote cape]

works for 2x2

$$\left({\begin{matrix}1&0&0\1&1&1\0&0&1\end{matrix}}\right)^{{-1}}=\left({\begin{matrix}1&0&0\-1&1&-1\0&0&1\end{matrix}}\right).$$

for 3x3

[vital dew]

Control

[remote cape]

(consider that interpolating a polynomial at infinity gives you 0,0,0,...,1)

$${\displaystyle \left({\begin{matrix}1&0&0&0\1&1&1&1\1&-1&1&-1\0&0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0&0&0\0&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&-1\-1&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0\0&0&0&1\end{matrix}}\right).}$$

[vital dew]

Control

[remote cape]

and it works for 4x4

but i couldnt find one for 5x5

[faint narwhal]

Hm, it's not immediately clear to me how this is related to your previous question. These aren't exactly vandermonde matrices and is it true that the common denominator of the inverse of the matrix is correlated to the determinant?

[remote cape]

so they are almost vandermonde matrices except for the bottom row

which is the evaluation of the polynomial at infinity

and idk about that second one, it just seemed a lot like it is (that the determinant could be the common demominator)

but i didnt have the time (or sanity) to invert a 5x5 vandermonde matrix by hand

[faint narwhal]

I mean, for example, the matrix (2,0) (0,2) has inverse (1/2, 0) (0, 1/2) which aren't the denominators of the determinant which is 4

But maybe your class of matrices satisfies this property

[remote cape]

hmm

btw

can we find a,b,c,d so that (a - b)*(a - c)*(a - d)*(b - c)*(b - d)*(c - d) is a power of 2 or not?

(positive and negative values are allowed)

*edit: power of 2

[faint narwhal]

not integers, I feel like this is possible with rationals but I'm not super sure how to find a solution

The common denominator of the inverse is related to the determinant by the formula A^(-1) = (det A)^(-1) * adj(A) where adj is the adjugate matrix

[remote cape]

yeah, but does the adjugate matrix have a denominator or not?

[faint narwhal]

well in this case, we're wondering if there's a common numerator > 1 that could potentially cancel out with the det A denominator

[remote cape]

hm

yeah

so

want me to explain why i need this?

or are you good?

lol

[faint narwhal]

Oh

okay

It is true that adj(A) has no common numerator and so the common determinant of the inverse is exactly the determinant

oh wait hm

okay my argument only works for the 3x3 case actually

I mean if you think explaining why you need this might make things easier then you can

okay yeah its not true in general, an example I found in the 4x4 case was when a = 2, b = 4, c = 6 which has 1/8 in the denominator but determinant of 16

[amber berry]

does anyone know if theres a pdf textbook for discrete math in this chat ?

[remote cosmos]

We don't do pirated books in this server. Hammack's book of proof is provided for free by the author on his page and that has some intro to discrete topics

(counting, logic, equivalence relations)

Though I wouldn't use that book as my only source for discrete

[amber berry]

Ok

[tardy quarry]

I overheard a conversation once about a website named 'Library Genesis' where you can get PDFs of math textbooks.

[weary tiger]

I’ve heard it is a wretched place where only the impure of heart who don’t care about the profits huge publishing corporations go

[tardy quarry]

Truly a place for the sinners.

[hoary igloo]

so I am feeling a bit overwhelmed on notation here

1. psi(e) = uv? This means that psi connects u and v?

[weary tiger]

That means e connects u to v in G

[hoary igloo]

ok iff psi(phi(e)) = theta(u) theta(v)?

im a bit confused there

[weary tiger]

Ok

Phi maps an edge in G to an edge in H

And theta maps vertices in G to vertices in H

[hoary igloo]

ok hang on

can i try to connect that from here

[weary tiger]

Ofc

[hoary igloo]

so we are saying that then psi maps it back?

[weary tiger]

psi is just a mapping from edges to vertex pairs

In some given graph

[hoary igloo]

so that is saying there must exist a mapping from G->H such that there is a pair theta and phi that maps an edge in G to h?

not sure if that even made sense feel like it didnt

[weary tiger]

Well not quite

The edge is arbitrary

So it's more for all edges in G

[hoary igloo]

so if it maps all edges?

I see

I think

so if I added for every edge in in G is that more accurate?

[weary tiger]

Yeah that's about right

They need to be invertible

Theta and phi need to be isomorphisms

Otherwise you can map every graph to a trivial graph with a single edge

[hoary igloo]

Ah I see

ok cool

so we are saying that there must exist a mapping psi for every edge in G phi that maps every vertex u,v in G to theta(u) theta(v) in H?

I feel like conceptually im getting it strugglign a bit with verbalizing it

[weary tiger]

The mapping psi is not part of the isomorphism definition, it looks like a way to extract vertices from edges

It's part of the graph definition

The graph isomorphism is composed solely of isomorphisms phi for edges and theta for vertices

[hoary igloo]

ok so it just simply must be invertible?

[weary tiger]

Yes, but you also need to make the edges from G connect the same vertices in H

So that's where the condition comes in

[vital dew]

The Library of Babel

[weary tiger]

This is just here to make sure the isomorphism preserves the graph structure

Otherwise all graphs with the same number of edges and vertices are isomorphic

[hoary igloo]

which is true for complete graphs correct?

[weary tiger]

Yeah

[hoary igloo]

when you say the graph structure could you elaborate a bit on that ?

wish I could draw with latex...

[weary tiger]

Its super tedious, I only do it when I'm writing a paper

I'll draw an example real quick

[hoary igloo]

thank you super appreciate it

wait I might get it

[weary tiger]

Here is my example anyway

[hoary igloo]

oh thats a super helpful example

actually and very obvious duh

thank you

ok so the first part here says $\phi(e) = uv$ so Im assuming that means phi here connects u and v in G?

[vital dew]

skischooldropout

[weary tiger]

No, e connects u and w

Phi is just the way of accessing that info

Psi actually

[hoary igloo]

ok so psi simply allows us to get the info ok

yea meant psi... phi and psi kinda seem like an odd choice here by the author cause it makes it a bit confusing to type out constantly lmao

so if psi of e allows us to extract info

what does $\phi(e) = \theta(u) \theta(v)$ mean? I figured it meant we can map any edge in G $\to$ H for any two nodes in G $\to$ H

[weary tiger]

Write \mapsto

Or \to

[hoary igloo]

ah thanks

[vital dew]

skischooldropout

[hoary igloo]

and psi means we keep the structure?

[weary tiger]

This is the statement that keeps the structure

Note that there is always a subscript to psi, which tells you what graph it’s working in

[hoary igloo]

oh I see

[weary tiger]

But it’s always just telling you what nodes belong to what edge, nothing more

It’s part of the graph definition

[hoary igloo]

ok so that just allows us to know for theta and phi which way we are going?

[weary tiger]

Yeah

It says that the mapping of an edge must connect the mapping of its vertices

[hoary igloo]

that makes sense

thank you so much

[weary tiger]

Lmao i was editing a message

Glad I could help

[hoary igloo]

show that there are 11 simple non-isomorphic graphs on 4 vertices

so im not going to lie anyone have a hint

my first thought was to try and find how many simple graphs there can be period on 4 vertices which according to the formula is 64

but I feel like thats wrong

[faint narwhal]

No that's the right number, its just that a lot of them are isomorphic

[hoary igloo]

ok so is that a valid way to approach that problem?

[faint narwhal]

Mmm I don't really see how that number helps

Maybe one way is to realize that isomorphic graphs must have the same number of edges. So you can split it into cases depending on how many edges there are from 0 to 6. For example, there's only one graph on 4 vertices with 0 edges

[hoary igloo]

oh thats smart

cause if there are more than 6 edges it can no longer be simple

[hoary igloo]

I have to say I think I am a bit confused as to what makes a graph non-isomorphic

I go stuck on this problem so I looked up the answer are there is a picture of the two edge 4 nodes that has a graph such that V(G)= (1,2,3,4) and E(G) = (a,b) with x(a) = 1,2 and x(b) = 3,4

however, why is that graph non isomorphic?

if you had a graph V(H)= (1,2,3,4) and E(H) = (c,d) with x(c) = 2,4 and x(d) = 1,3 couldnt you map that to G?

https://math.stackexchange.com/questions/599675/why-there-are-11-non-isomorphic-graphs-of-order-4

[faint narwhal]

I'm not super sure about your notation here

Your first graph has edges between 1 and 2 and another between 3 and 4?

[hoary igloo]

yes

[faint narwhal]

I agree that the second graph you describe is isomorphic to G

Non-isomorphic isn't a property about a single graph G

It's a property about two graphs G and H

[hoary igloo]

im a bit confused as to what you mean by that? so in other words it simply means there exists a graph G and a graph H that are not isomorphic?

[faint narwhal]

I'm saying it doesn't make sense to ask whether a graph is non-isomorphic or not

It only makes sense to ask if two graphs G and H are isomorphic or non-isomorphic

[hoary igloo]

oh I see

so we are showing that between the 11 graphs they are not isomorphic to the 10 other graphs?

[faint narwhal]

Sure you can think of it like that

And you need to show that every graph on 4 vertices is isomorphic to one of those 11 graphs

[hoary igloo]

why would I need the second part?

[faint narwhal]

Maybe thinking of it like this would help. Isomorphism of graphs is an equivalence relation. Thus we look at the set of graphs on 4 vertices under this equivalence relation. We ask how many different sets this equivalence relation partitions the set into

[hoary igloo]

and in this case there are 11 paritions

I think I got it

[weary tiger]

if I want to describe all the even numbers in the set of integers, is the following correct: { x | x / 2 } or { x | x *= 2 }, being x the number?

[faint narwhal]

Yeah, there are 11 different partitions

[hoary igloo]

thanks

so for four there is the one where the cycle is between 3 nodes and one where the cycle is between all 4

I see I see

And clearly those are non-isomorphic to the each other cause of a different structrure and non-isomorphic to thge rest cause a different number of edges

[dense geyser]

Neither, because neither are valid sets. If you use the notation with the bar, you can basically read the bar as "such that". So the first one would be read as "the set of all x such that x / 2", and the second is "the set of all x such that x *= 2", which don't really make sense

You also don't qualify what x is. Is it a natural number? An integer? A real number? A complex number?

[weary tiger]

👍 I'll come up with a solution, thanks for the tip!

[hoary igloo]

the first one is very close

[void lake]

I have this question - "Use logical equivalences to give a logically equivalent expressionto¬p→qthat does not use the conditional. Identify the logical equivalences by name.You will not receive credit for a truth table solution.", maybe it is just worded weird, but I understand from the truth table that the answer is "p v q", however I don't understand what the name of the logical equivalence(s) would be or how I would get this answer, thanks for any help!

[sour arrow]

You may know of this equivalence:
p → q = ~p V q

Just use ~p instead

I think that's called the implication law? I never have memorized any names for these haha @void lake

[void lake]

Ok yeah I saw in the textbook that exact equivalence but there wasn’t a name

Thanks!

[half gyro]

are unions and interesections really necessary? Like couldn't we have used OR and AND respectively they are functionally so similar

[faint narwhal]

Uhh they're kinda different? Like unions and intersections are operations on sets so it doesn't really make sense to say that OR and AND can be used on them

[half gyro]

but AND and OR don't mean anything currently when applied to sets right?

[faint narwhal]

I mean no

and you're right that they are basically the same

[half gyro]

yea so when we apply AND and OR to sets, thats just what they would mean

[faint narwhal]

I mean I guess but I don't really see the point in calling it that

Although sets follow some of the same rules that AND and OR do when applied to truth values, they're also different in a lot of ways

[half gyro]

the point is you don't need to make new symbols and words when we already have symbols and words for those functions

[faint narwhal]

Except they're different functions

AND and OR act on truth values, union and intersection act on sets

I don't see why it makes sense to call them the same thing just because they share a few of the same properties, because they also differ in many ways

[half gyro]

thats arguing we should use different verbs for each noun we can use them on

very strange precedent

[remote cosmos]

Why use true or false when we can just say 1 and 0

[faint narwhal]

But verbs acting on nouns would do the same thing regardless of the verb

[remote cosmos]

And use boolean algebra operations?

[half gyro]

go for it

[remote cosmos]

Context matters

[faint narwhal]

I'm trying to tell you thats not really true in this case because set operations can differ in many ways from AND and OR

And besides, if you want to go full generality, we can talk about meet and joins on lattices

which generalizes both AND and OR and unions and intersections

and you can continue generalizing

[half gyro]

I don't know about lattices yet

[faint narwhal]

My point is that arguing that you should use the same word just because they share a same of the few properties doesn't make a ton of sense

[remote cosmos]

I can say and/or are the same as + * in bool alg

So throw out and or...?

It just comes from a different line, used in diff contexts

It's cool that they share a lot of properties

But yea just rolling things into one isn't going to work across the board

[half gyro]

seems the only advantage is looking at it from a distance you can tell if you should expect the inputs/outputs to be sets or true/false values

[faint narwhal]

I mean you also don't run into confusion when you think AND and OR should satisfy some property that union and intersection do but since they're different it doesn't work out

[half gyro]

could you give an example?

[half gyro]

if A is {1} can I say 1 is contained within A? containment is typically reserved for sets. I'm being asked if this is true or false but I wanna say it just doesn't compute

[remote cosmos]

1 is contained (as in, 1 is an element of A)

{1} is not an element of A

{1} is a subset of A

I might be sleepy but that's how I'm reading it

You can ask, what elements does A contain? Response: A contains 1

(1 here can be any other number)

[half gyro]

is the sideways U used for subset?

[remote cosmos]

Yes, with the open side towards the bigger set

Technically it's a strict or proper subset

So you need to draw the line underneath too

When the subset is the set itself

[half gyro]

from the textbook:
DEFINITION OF A SUBSET. A set A is said to be a subset of a set B, and we Write
A c B,
whenever every element of A also belongs to B. We also say that A is contained in B or that B
contains A. The relation c is referred to as set inclusion.

so the way you used contained is different than how it is used here

[remote cosmos]

Very loose definition

It's like equality, the distinction matters

Whenever you can avoid ambiguity, you avoid it

[half gyro]

what I meant to ask is if A = {1} is 1 c A true or false

I thought that was expressed as is 1 contained in A

[remote cosmos]

Well is 1 a set?

[half gyro]

no thats why I'm leaning towards doesn't compute but it only asked true or false which could be a flase dichotomy

[remote cosmos]

I'm on my phone but you use the element of sign for is contained

Why would it not compute?

It's either true or false

The notation doesn't allow for ambiguity if used correctly

[half gyro]

because c is an operation for sets. Its like asking whats bear * banana

[remote cosmos]

Then it's false

But looks at more examples

Math stack is your friend

Lots of good discussion threads on these topics

[waxen nest]

whats the fastest way to determine the type of such statements?

[half gyro]

contingent was the right answer?

[waxen nest]

yeah

[waxen nest]

why is this tautology?

[upbeat pier]

isnt -q->-p the same as p->q?

And (-P v Q) the same as -(P and -Q) ?

[waxen nest]

?? which qn?

[upbeat pier]

This one

[waxen nest]

🤔

weird

[upbeat pier]

Contrapositive

[upbeat pier]

De morgans law

[waxen nest]

i used logic calculator and it said contingent

[upbeat pier]

<--> is the same as = ??

[waxen nest]

yea

[upbeat pier]

Isnt <--> is iff?

[waxen nest]

this calculator worked for other qns but not this one v weird

[upbeat pier]

Hmm weird

[waxen nest]

it worked for this

it all belongs to same category i think

[upbeat pier]

Well im still a novice so wait for the others to respond😂

[upbeat pier]

Soz

[waxen nest]

this one gave the right answer tho

im guessing is some software bug?

[upbeat pier]

I thk this should be correct?

[upbeat pier]

Idk😂

[waxen nest]

lol

its the brackets...

when i include more brackets it becomes tautology lmao

[weary tiger]

I think it's not hard to tell that the statements are equivalent just by looking and applying de Morgan

[upbeat pier]

LOL

[weary tiger]

And unfolding the implication definition

Yea it looks like iff binds more tightly than and for some reason

[waxen nest]

oh i see

[deft dock]

@cerulean wind @snow sleet thanks for all the help during discrete bros; finished the class with a 95 🙏 🙏

about a month or so ago

[cerulean wind]

that’s awesome! @deft dock glad i could help

[snow sleet]

You’re welcome dude! Great job!

[turbid shoal]

n>7 is an integer that solves the following equation
n^2 + an - b
additionally, 27 (base n) = a
the question is to find b in base n
that is, x (base n) = b

please ping me if you can help 🙂

been on this one for too long at this point

[dense geyser]

Do you mean base n or mod n? As is, it doesn't give you that much information

[split drum]

Hey, can anyone tell me if I'm on the right track with B?

I'm thinking I could say $${x \in S : 0 \ge x \le 3}$$

[vital dew]

Umiguess4000

[split drum]

Is this valid as a description of the set? I only had my first day of class this week.

<@&286206848099549185>

[split drum]

It won't let me edit the tex for some reason, but I realize what I did wrong now. This is valid, I just screwed up the notation.

[dense geyser]

you could even get rid of the $x\leq 3$. Since you quantify that each $x$ comes from $S$, and every element in $S$ is less than 3

[vital dew]

cgodfrey

[split drum]

Oooh, nice 🙂

[weary tiger]

Is cardinality of functions from c to c c^c by definition or sth? C continuum

[grave sluice]

yes cardinalexponentiation is defined by the cardinality of the set of functions

(and for all infinite cardinals k you have k^k=2^k)

[split drum]

Can someone check me on this? P(A) means power set.

Wait, I forgot the empty set itself. So I think it's actually 8.

Oh, by |P(A)|, I'm trying to find cardinality of the power set. I don't know if that was obvious or not.

[pale epoch]

yes, then it's fine

[split drum]

Awesome, thanks.

[turbid shoal]

i mean base n

let me screenshot the hw

and i emailed to clarify, he means that a = 27 (base n)

[stray reef]

$a = 2n+7$ then, isn't it?

[vital dew]

Ann

[turbid shoal]

how?

[stray reef]

recall how the place-value system works

[turbid shoal]

i have no idea what you're talking about

[stray reef]

do you know how non-decimal bases work?

[turbid shoal]

basically

[stray reef]

like base 8, or base 16, or things like that

when writing down a multi-digit number in any base (be it ten or not ten), each place in the number has a certain value associated with it

[turbid shoal]

yes

[stray reef]

in base ten, we have the units place, the tens place, the hundreds place and so on

[turbid shoal]

i understand that, just didn't know it had a name

place value system, got it

so how can you just pop in a 7?

[stray reef]

i was getting to that

the base, which i'll call B here to disambiguate from b, determines the weight of each place in the base-B representation of a number

these weights are powers of the base, starting from the zeroth (B^0 = 1) in the rightmost place

for example, the decimal number \textbf{7231} represents $$7 \times 10^3 + 2 \times 10^2 + 3 \times 10^1 + 1 \times 10^0$$

[vital dew]

Ann

[stray reef]

you understand this, right?

[turbid shoal]

I'll be back in one hour, i have stats

[stray reef]

.-.

ok

ping me when you're ready to come back to this question ig

[turbid shoal]

@stray reef hi

sorry, I'm done with class till tn though

so far i follow

[stray reef]

right

so you know that if the representation 7231 were read in some other base, the tens in that formula would get replaced with powers of that base, yes?

[turbid shoal]

yeah, like with base 2 it would be 2^0 for the first place, 2^1 for the second place, etc. when written in decimal notation

but in base 2 10 represents 2, or the base

this question is "extra credit" but I'd really like to understand it. it's very abstract but I've already invested like 1.5 hours into it and gotten nowhere

[stray reef]

yes

well

here our base is n

[turbid shoal]

(also i absolutely refuse to guess and check. i don't want to know the answer if i don't do it right)

[stray reef]

our number has representation 27 in base n

this means it's 2 * n^1 + 7 * n^0

you understand that, right?

[turbid shoal]

that's literally all i have so far 😅

but yes

[stray reef]

yeah so if you wipe away the fluff it becomes 2n+7

thus we come back to what i started with

a = 2n+7

[turbid shoal]

oh

wow

big brain

i assume sub and simplify?

3n^2 +7n-b =0

oh my god that's the answer

holy shit

370?

@stray reef ❤️❤️❤️

[stray reef]

yup

[weary tiger]

hello everybody

[frosty musk]

why is A x B not equivalent to B x A

Consider: A = {1, 2} and B = {a, b, c}?

A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}.
A x B = {(1, a), (2,a), (1, b), (2, b), (1, c), (2,c)}.
B × A = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}.

isn't it the same thin

[stray reef]

no

(1, a) ≠ (a, 1)

[frosty musk]

why

[stray reef]

because these are ordered pairs

it matters what comes first and what comes second

[frosty musk]

in the first 1 < a, and in the latter, a<1?

[stray reef]

you're overthinking it

[frosty musk]

no, i just don't understand it

[stray reef]

we're not making any statements of comparison

i mean look

here

here are two points on a plane

(1,4) and (4,1)

they are not the same point

[frosty musk]

okay, so depending on the order

thanks

not really a proper math question, but is it actually proper grammar?

[mint bane]

i can prove this identity algebraically fairly easily, but is there a more "combinatorics oriented" way of understanding it

[pale epoch]

yes, a relation is a set, so "in" is the correct term

[frosty musk]

shouldn't it be like to-relation?

oh nvm

i get it

[pale epoch]

suppose you have an n element set and a uniquely labeled element x. to construct a subset with r elements containing x, you include x and choose r-1 further elements from a set with n-1 elements (the original set minus x). to construct a subset with r elements not containing x, you simply choose r elements from a set with n-1 elements (again the original set minus x).

those two ways correspond to the summands and as every subset either contains x or does not, this works

[mint bane]

oh shit

neat

ann im gonna pretend i didnt see anything

[ember solstice]

is there any conventional notation for the union of the sets of integers and half-integers?

[last timber]

half-integers?

[ember solstice]

$\mathbb{Z} + \frac12$

....,-1 -1/2, -1/2, 1/2, 1 + 1/2, 2+ 1/2, ....

[last timber]

well

[vital dew]

271828

Commander Vimes

[ember solstice]

why subset?

[last timber]

because for any integer x there is 2x so x = 2x/2

[pale epoch]

$\frac{1}{2}\bZ$ should work

[vital dew]

Lochverstärker

[pale epoch]

but i wouldnt call it conventional

[ember solstice]

I mean the union of integers and half integers

$\mathbb{Z} \cup \frac12 \mathbb{Z}$

[pale epoch]

there is no reason to union Z

[vital dew]

271828

[pale epoch]

if x is an integer, so is 2x and then 2x/2 = x is in that thing

[ember solstice]

ahhh

got it

silly me

yea ty

[vale cairn]

$\frac{1}{2} \mathbb Z = {0, \frac{1}{2}, -\frac{1}{2}, 1,-1,\dots}$ ye

[vital dew]

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

[pale epoch]

in general $\frac{1}{2}\bZ$ is defined as $\left{\frac{1}{2}\cdot x : x \in \bZ\right}$

[vital dew]

Lochverstärker

[ember solstice]

yeah cool
thats what i need

does $\frac12 \mathbb{Z}^d$ makes sense?

[vital dew]

271828

[ember solstice]

if i need high dimensional space

{0, -1/2, 1, 5, 1/2}

so this vector is in this space

and every coordinate belongs to 1/2 Z

just an example

[pale epoch]

this is not a vector, but sure

[ember solstice]

yeah not a vector

my bad

i am a cs guy i mess up a lot

lol

[pale epoch]

you can define this for any set as long as there is a sensible notion of multiplying elements of that set by 1/2

(this is kind of abuse of notation, more formally you extend multiplication to powersets and then do even more abuse of notation, but usually everyone gets what you mean)

[ember solstice]

this should be ok for cs paper?
i dont pursue for a really detailed math notation

[pale epoch]

i guess, its really obvious what is meant

[ember solstice]

nice thank you again

[ember solstice]

also mind another question?
how to notate the sphere with the centre at $x$?
at my uni, we used to notate it as $O(x)$ iirc

[vital dew]

271828

[ember solstice]

this is probably really dumb question

[pale epoch]

just explain it with words then its fine

[ember solstice]

i have some operations with this set involved

[pale epoch]

i think the most common would be $B_r(x)$ for a sphere of radius r centered at x

[ember solstice]

so i would prefer notated

[vital dew]

Lochverstärker

[ember solstice]

hmm sometimes B is also a ball, right?

[pale epoch]

well, yeah

actually this would be the open ball around x

what do you mean by sphere? just the surface or also the interior?

[ember solstice]

yes just the surface

[pale epoch]

oh ok

[ember solstice]

so i should have exclusion?

of open ball

[stray reef]

youre writing a paper right

[ember solstice]

kinda
i am proposing an idea to my advisor

[stray reef]

you could define your own notation

like idk

S_r(x) maybe?

[pale epoch]

then $\mathbb{S}^2$ i guess for the standard sphere in 3 dimensions

[vital dew]

Lochverstärker

[stray reef]

if it makes the expression of relevant ideas easy, i don't see any reason why not

[pale epoch]

and maybe what ann said to adjust that ye

nvm me

[ember solstice]

also i am kinda bad at english thats why i prefer it notated xD

[pale epoch]

(the sphere of radius r around x_0 is $\left{ x \in \bR^3 : \abs{x-x_0} = r\right}$)

[vital dew]

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

[ember solstice]

nice
anyway i am going to define S_r(x) first

then use S_r(x) everywhere after

[lilac delta]

Ive got 10 numbers. And i need to find how many permutations there are with 3 digits. Repetition is allowed.

Is 1000, correct?

[cerulean wind]

yes, these are typically called ordered tupples and not permuations, but same thing, potato potato. 10 choices for the first slot, 10 choices for the second slot, 10 choices for the third slot, so 1000 in total.

[lilac delta]

👍

Something’s not right tho

It should be more

Shouldn’t it be 3000?

[cerulean wind]

what makes you say that?

[lilac delta]

There is 300 permutations with just the number 0

300x 10

3000

[cerulean wind]

could you explain how you are getting 300?

[lilac delta]

@cerulean wind if you put 0 in the first position, there are 100 permutations for other 2 positions

Im confused 🙄

[rough crater]

if you put 0 in the first position there are 100 permutations for the other 2 positions but if instead of 0 you had all 10 numbers as an option each one of those 100 permutations will have 10 different numbers they could be paired with and then we get 1000

[lethal frost]

hi

for this question