but did you have an explanation for why R^4 cant be embedded into R3 with coordinate wise <=
#discrete-math
hybrid crown
hybrid crown
okay thanks anyways
cyan talon
Thank you @lyric pumice
stark creek
How many ways can n elements be chosen from a collection of 2n elements where n are different and n are identical
i have no clue how to even start with this
i mean, i know its 2^n
i just dont know why
lyric pumice
Since you are choosing n elements, each element is either from the set of distinct elements or from the set of identical elements.
This implies that you are choosing whether or not an element is from the distinct set.
stark creek
but if theyre from the "distinct elements set" its not irrelevant which element i choose, right?
lyric pumice
In other words, for each element of the distinct set, you are deciding whether or not it is chosen.
stark creek
and if its not chosen, it gets replaced with one from the identical set
lyric pumice
That is correct.
stark creek
HOLY SHIT
thats so smart
oh my god
i would not have thought of that
thats clever
lyric pumice
So, since you must make a decision for each of n elements and only for those n elements, there must be 2^n possibilities for choosing n elements.
The simplicity of 2^n comes from the convenient fact that the number of distinct elements is the same as the number of elements that you must choose from.
stark creek
theres one thing that doesnt make sense to me about that
if im going element by element and deciding wether it is chosen or not
isnt that for one order of those n pairs of elements?
wouldnt i have to to n*2^n?
lyric pumice
Order doesn't matter in this problem because an element from the set of those that are distinct is is either part of those that you choose or not.
lyric pumice
Moreover, the problem implicitly asks about choosing to make a set of elements.
And in a set, by definition, the order of the elements given does not matter.
stark creek
thank you so much
copper ore
so if i have an integer written as the product of prime factors I can use the (exponent + 1) in the prime factors to find the number of divisors of the integer
is there a proof for this?
i don't understand why it works otherwise
weary tiger
it is easy to "prove" with counting principles
the divisors of an integer are built out of the primes
so given a prime factorization
for each unique prime p, we could choose p^0 or p^1 or ... p^n (whatever the order is)
this gives n+1 options
by the multiplication principle
similarly, by the MP, multiply together all the options for the other primes
example
for 18=2⋅3^2
we could choose 2^0 and 3^0, this gives the divisor 1
2^1 and 3^0 gives 2
2^0 and 3^2 gives 9
each different choice of exponents gives a unique divisor
copper ore
for each unique prime p, we could choose p^0 or p^1 or ... p^n (whatever the order is)
@weary tiger what is this mean?
weary tiger
to be a little more clear on the example
the choices are
2^0 and 3^0
2^0 and 3^1
2^0 and 3^2
2^1 and 3^0
2^1 and 3^1
2^1 and 3^2
does that help?
it will help to have a good familiarity with the multiplication principle, if you don't already
copper ore
yes that makes sense!
yeah i gotta learn it properly
thanks so much for the help
great explanation
weary tiger
no problem
copper ore
it's very hard to figure this out own my own
but when someone explains i get it
its insane how can you figure this out on your own lol
weary tiger
lol, I tried to figure it out on my own once and ended up having to look it up
weary tiger
yea
weary tiger
I never forget it, if that gives you any hope
weary tiger
but I've worked with it a few times so that helps
copper ore
when it says n is a positive integer
does that include 0 ?
is there like universal acceptance on 0 being a positive integer?
weary tiger
Positive integer means integer 1 or greater
Natural numbers may include 0, or they may not
copper ore
ok thank you
delicate ridge
fucking excuse me
this is quite possibly the most clapped notation i have ever seen
errant bear
wdym
naive saffron
Clapped?
ember obsidian
obtuse lance
0 because students shouldn't be drinking beer
oak plaza
Combinatorics is so hard 😩
I need to practice.
I can figure out some of this problem but not all.
copper ore
Yeah practice is best for this type of stuff
obtuse lance
have you learned stars and bars?
copper ore
Me? No
obtuse lance
imagine the k beers as stars in a row
then put dividing bars in the row
so between bars is how many beers a student gets
there are n-1 bars you have to place, like for instnace
let's say there are 5 beers and 3 students
oak plaza
oh yea I've seen this before.
obtuse lance
xx | |xxx
this means the first student gets 2 beers, the second gets 0 beers, and the last gets 3
so now it's a matter of asking how many ways are there of arranging just these two kinds of symbols in a row
copper ore
Ohh yeah ive seen this with binary numbers
oak plaza
same
copper ore
6 ways?
obtuse lance
nope
here's an easier problem that's not fundamentally different
how many ways are there of rearranging the letters of this word: AAB
there's ABA and BAA
but you should know of a way to count this combinatorically
maybe do AABB or ABBB
copper ore
4!
Hm actually nvm
Cause AABB is same as AABB
6 ways
4 choose 2 multiply by 2 choose 2
@obtuse lance
sick swallow
No it is just 4C2
Picking 2 determines where the others go
Also another way, which is basically equivalent, is doing 4! Divided by 2!2!
As out of the 4! permutations, 2! where the red are swapped are the same and also for 2! Of blue; so you are overcointing by a factor of 4
lyric pumice
The problem does not require stars-and-bars techniques.
copper ore
Picking 2 determines where the others go
@sick swallow true
obtuse lance
do you see how to solve the original problem now @copper ore ?
obtuse lance
a proof of what
copper ore
Of why this works
obtuse lance
the dividers represent separations and you're always guaranteed the correct number of people and beers
lyric pumice
What are you counting?
obtuse lance
scroll up
lyric pumice
It looks like you've done this all wrong.
copper ore
lyric pumice
The answer should be n^k.
obtuse lance
I did the problem assuming the beer bottles were indistinguishable
copper ore
Can you explain why its n^k
lyric pumice
Since there is no restriction on how many bottles a student may get, the bottles can be assigned to students freely.
Each bottle must be given to some student.
So, for each bottle, there are n students to choose from.
Thus you are making k choices.
So, the combination of choices is given by multiplications of n.
There are k of these multiplications.
crystal forge
Hi, I got competitive programming excercise about graphs/trees. I got weighted vertices and undirected edges. I have to find minimal cost of takeover entire graph.
With every chosen vertex you add its weight to the sum and you got it and every neighbour considered as "marked". You have to mark all vertices with minimal cost.
Maybe you know how to name this problem
It's not a Minimum Spanning Tree. It's similar, but not MST
lyric pumice
It looks like it involves independent sets.
crystal forge
I found only this
it's really similar, excluding that I got constant weight of nodes (and there are increased by 1 with every neighboring or semi-neighboring)
and I need to know which vertices to get, not only the " minimum strenght"
lyric pumice
It looks like you are trying to solve a weighted set cover problem.
copper ore
Let f ≥ 2, m ≥ 2, and k ≥ 2 be integers such that k ≤ f and k ≤ m.
The Computer Science program has f female students and m male
students. The Computer Science Society has a Board of Directors
consisting of k students. At least one of the board members is female and at
least one of the board members is male. Determine the number of ways in
which a Board of Directors can be chosen.
${k \choose 1} * {k-1 \choose 1} * {(m+f)-2 \choose k-2}$
vital dewBOT
The-Elite:
copper ore
i was thinking the answer is this
lyric pumice
That appears to be incorrect.
copper ore
aw damn
obtuse minnow
yeah ... you can ... "ignore" ... some info there or manipulate it a bit.
Simplify with what you know. (a common math trick). What do you know for sure?
lyric pumice
Moreover, start simply. How many ways can you choose a Board of Directors if you disregard the condition of choosing at least one male and at least one female?
stark creek
How many 4 letter words can be made with the letters of TOPOLOGIA, where all words must contain at least one vowel?
The correct answer is ||1020||
I did the total amount on possible 4 letter words minus the amount that dont have any vowels
and that amount is 4! = 24
Now, I know that for the amount of words that can be made with the letters of TOPOLOGIA is 9!/3!
i dont know how to restrict that to 4 letter words, though
Could anyone point me in the right direction
lyric pumice
The number of 4-letter words depends on the number of times a letter appears in a word.
weary tiger
try counting the number of words with 0,1,2, and 3 o's separately
for 0 o's we would have P(5,4)
for 1 o... P(5,3)⋅4?
for 3 o's, 5⋅4 I think
I will need to work out 2
lyric pumice
I have the solution.
weary tiger
oh I thought the word had 8 letters, not 9
I need to redo this
ok my solution is complete
||the total number of words we can make is
N = [6P4] + [6P3 ⋅ 4] + [6P2 ⋅ 6] + [6⋅4]
this is given by cases of 0, 1, 2, and 3 o's
final answer is N-4! = 1020||
lyric pumice
Or,
weary tiger
explain
lyric pumice
There are 6 choose i ways to choose i letters that are not O.
Then there are 4 choose i ways to choose the positions for those i letters in a 4-letter word.
Then there are i! ways to permute those i letters in the word.
weary tiger
ahhh
lyric pumice
4! 4-letter words do not contain a vowel.
The number of letters that are not O is at least 1 and at most 4.
naive mural
How many contain no even numbers
copper ore
n/2
naive mural
How many k-element sunsets contain no even numbers though
copper ore
n/2 choose k
naive mural
Okay, how many contain 1 even integer
And you can put this together to work out your answer
copper ore
n/2 choose 1
okay i think i see where this is going
is it just
(n choose k) - (n/2 choose k) - (n/2 choose 1)
quaint star
Why n/2 choose 1?
quaint star
n/2 choose 1 is choosing 1 even number, sure, but you aren't considering the different combinations of odd numbers than can go with it
quaint star
First choose the odd numbers, then multiply by how many even numbers can go with it
copper ore
so the odd numbers are n/2 choose k
quaint star
But if your set has one even number in it, why are you choosing k odd numbers?
copper ore
no the set has n/2 even numbers
quaint star
Wut
copper ore
quaint star
Okay, how many contain 1 even integer
I'm talking about the subsets
You are trying to find the subsets with 1 even integer
So then they only have k-1 odd integers in them
copper ore
So then they only have k-1 odd integers in them
@quaint star sorry dont get what that means
quaint star
If you are trying to take a subset with k elements, with exactly one of the k elements even, then the other k-1 elements must be odd
copper ore
yeah
quaint star
So if you are choosing the odd numbers for these subsets, it would be n/2 choose (k-1)
copper ore
yeah true
quaint star
And then with each of these combinations, you can add any of the even numbers
copper ore
So if you are choosing the odd numbers for these subsets, it would be n/2 choose (k-1)
@quaint star so this finds all sub sets that have all odd except for 1 even?
quaint star
Well, you still have to multiply by something
Because for each of those, you can choose any of the even numbers to go with it
quaint star
Yes, which is just n/2
quaint star
Practice
copper ore
could never figure this out on my own
quaint star
You'll get better at it
copper ore
thanks man i hope so
my school starts in september but i am just practicing right now cause i know this stuff is hard
quaint star
The more problems you do, you learn what to focus on and how to think about different kinds of problems
That's really good of you to work ahead. I'm sure you will be fine.
vital dewBOT
Manan:
gritty crescent
My question: Is a recursive definition simply a function which depends on the value assigned to the base number, i.e., 0(or 1, based on definition of N)?
pale epoch
a recursive definition always defines a function
gritty crescent
Is the converse true- can every function on N be defined as a recursive definition?
stray reef
sure
gritty crescent
How??
stray reef
let $F:\bN \to \bN$ be an arbitrary function and define $c = F(0)$ and $f_n(m) = m + F(n+1) - F(n)$, in keeping with the notation from your excerpt
vital dewBOT
Ann:
vital dewBOT
Manan:
vital dewBOT
gritty crescent
Ah, I see
stray reef
f(0) = 0, f(n+1) = f(n) + 4n^3 + 9n^2 + 7n + 4
gritty crescent
This is enlightening, thank you!
unreal stump
I don't think it's true for an arbitrarily defined function
gritty crescent
That's the same doubt I had, but elementary functions on N are rather well behaved
unreal stump
Like,f(0)=3,f(1)=2,.. and so on, without a pattern
gritty crescent
What would happen in case of piecewise functions @stray reef ?
pale epoch
in general f(n) does not need to depend on f(m) for m != n, so you can't just use a recursive definition for that
gritty crescent
So recursive definitions are only a subset of functions on N?
pale epoch
unless you do something stupid like define the recursion as a_n = f(n) + f(0) - f(0)
gritty crescent
Lmao
pale epoch
tbf i don't have a clear definition of what a recursive definition is
gritty crescent
From what I've read so far, I guess recursion means backtracking to a base value which is explicitly highlighted. So given how the recursive definitions behaves and its base value, one can, in principle, deduce all subsequent values
pale epoch
i mean, then a_0 = f(0) and a_n = f(n) + f(0) - f(0) works for any function f: N -> N
gritty crescent
This only seems more perplexing than the good ol' function, which simply assigns a value to every element in domain 
i mean, then a_0 = f(0) and a_n = f(n) + f(0) - f(0) works for any function f: N -> N
Given this definition, I cannot deduce a_(n+1)
gritty crescent
The point of recursion is to establish some relation between successors in N
pale epoch
ok, then there must not exist such a relation for arbitrary functions
gritty crescent
That's what I think too.
For example, a function dependent on parity of input may not behave well in a recursion
pale epoch
at least not one you can write down in finitely many symbols
gritty crescent
I guess I could try framing a simple piecewise function of the sort
pale epoch
anything you can reasonably write down you can probably define recursively in some way
gritty crescent
At the very least, I can safely assume there are some functions which can't be listed as recursions, right?
stray reef
for some it'd be impractical to do so
pale epoch
the thing is
unreal stump
After decimal
gritty crescent
Seems credible enough to me
pale epoch
if you want f(n) to somehow depend on f(m) for all m < n, then you cannot do it
gritty crescent
That's it, that's what I wanted to know :p
pale epoch
like, if that is your definition of recursion
you would have to further formalize what "depends on" means though
unreal stump
if you want f(n) to somehow depend on f(m) for all m < n, then you cannot do it
@pale epoch yea,Define "depends on" that way
gritty crescent
Well as long as I'm assured there exists a function f(k) such that f(k+1) can't be deduced in terms of either k or f(k), I'm good
Ah
I can say a function which doesn't depend on induction fits this
Every recursive definition is simply a consequence of induction; functions which don't depend on induction should be independent of recursion too.
pale epoch
what does "depend on induction" mean
gritty crescent
f(k+1) follows from f(k)
pale epoch
what does follow mean
gritty crescent
I don't think I can explain it very well, I just started with Peano Axioms :3
Hmmm but you're right, 'follow' is rather a hand-waving term
pale epoch
like if you want f(k+1) = p(f(k)) for some polynomial p and all k in N, its easy to see that this is wrong
unreal stump
f(n)=f(n/2)+1 is also a recursion
pale epoch
if you replace p by any function, it's true, you can do it
but i am not sure if that is "depends on"
gritty crescent
Hmmmm, makes sense. I need more clarification on the definition itself it seems.
crystal forge
It looks like you are trying to solve a weighted set cover problem.
@lyric pumice Thank you. It seems that my problem is called: "Minimum Weighted Vertex Cover problem"
distant bobcat
Was wondering if I got this proof correct? I.e is it valid, anything I could clarify...
errant bloom
is it sqrt(a)b or sqrt(ab) ?
distant bobcat
sqrt(ab). Thanks)
errant bloom
doesn't look like it, otherwise it looks good 🙂
errant bloom
those are just possible examples that satisfy the statement from above
a = -14, b = 3, q = -3, r = -5 and it holds that -5 < 3
but this is garbage, right? Which is the reason why it's not enough to only require r < b but we actually want 0 <= r < b
noble wasp
where it says r < b then that means r can be any negative numbers up to 2?
hm i guess we are testing numbers to see which of them satisfy?
errant bloom
It tries to show you why the rule 0 <= r < b is needed, because if you don't have lower bound of 0 then your solution is not unique
but you want to have a unique solution
noble wasp
okay, how would you read that " o </ r <b"
can that be broken up into two inequalities?
errant bloom
this means that 0 <= r AND r < b AND 0 <= b
stray reef
the third bit there is redundant
errant bloom
but the last isn't necessary because of the second. If 0 <= r and r < b then by definition 0 <= b
stark creek
@weary tiger @lyric pumice sorry, i fell asleep last night and didnt get to thank you two. Thanks a lot! I eventually figured it out near 3 am and fell asleep on my notebook haha
weary tiger
lol np
lyric pumice
Certainly.
subtle galleon
can someone help me with this problem?
lyric pumice
That answer appears to be correct.
copper ore
so like that answer is equivalent to
but i'm not sure how
hmm seems like (n choose k) - (n-1 choose k) = (n-1 choose k-1) ?
didn't see it anywhere just assuming
wow looks like it is an actual identity lol
weary tiger
wait actually i'm not sure if it is an identity
is it true that ${n \choose k} - {n-1 \choose k} = {n-1 \choose k-1}$
vital dewBOT
The-Elite:
obtuse lance
this is basically how you construct Pascal's triangle
you look in the n-1 row and add the k and k-1 entries to get the entry in the kth number in the nth row below those two
weary tiger
ah yes ! ^^ thank you
obtuse lance
you're welcome
stray reef
may i suggest first obtaining the generating function for the sequence (0, a_1, a_2, a_3, ...)?
i.e. the original sequence {a_n} but where the 0'th term has been zeroed out
@small kayak
small kayak
Oh i get it 😢 , tks a lot
But the requirement is expressing in terms of A so i wonder what is the relation between the generating function for the sequence (0, a_1, a_2, a_3, ... ) and A(x) ?
stray reef
the generating function for $(0, a_1, a_2, ...)$ is just... $A(x) - a_0$
vital dewBOT
Ann:
small kayak
Oh okay tks a lot
oblique oracle
I"m taking this class and I"m trying to understand this could someone point me in the right direction for a simple example https://www.coursera.org/lecture/what-is-a-proof/n-queens-brute-force-search-OPyaT?utm_source=link&utm_medium=in_course_lecture&utm_content=page_share&utm_campaign=overlay_button
errant bloom
did you understand the problem? @oblique oracle
oblique oracle
not exactly
Not how we go through permutations to check
I tried to code and and print the code but I'm not sure what to print
errant bloom
okay, you understand what we want to find? And how the queens can move?
oblique oracle
I understand the concept of the queen but not how we find the solution
errant bloom
okay, so the queen can move in 3 different directions: horizontal, vertical, and diagonal
oblique oracle
they give you a link to a site to try it out http://dm.compsciclub.ru/app/quiz-n-queens
but I don't understand mathematically how to think about the problem
errant bloom
oh wow, it's super hard to find the solution for 8 manually haha
oblique oracle
would this be considered combinatorics?
errant bloom
so the queen can move in those 3 directions. This means that you can never have two queens on a vertical or on a horizontal line
not really
so instead of all the possible (i,j) permutations, you now only consider a subset of them
where you already exclude the possibilities that two or more queens are on the same horizontal/vertical line
to do this you start by placing a queen on each column, now you only have one dimension, the vertical one, where you can move them around
oblique oracle
Is there a simpler idea that builds to this?
errant bloom
and you have $n$ vertical positions for each. To guarantee that no two queens are on the same horizontal position, you just take the permutation of this, which guarantees that no two cross
vital dewBOT
lyinch:
errant bloom
euhm I don't now
use a chess board or a piece of paper and try it yourself
for n=4 or something small
so that it "makes sense". There's really not much theory behind it
oblique oracle
the concept makes sense the best way to find a solution doesn't and I don't understand itertools and how that work
oblique oracle
if they gave me a for while loop I could probably understand it
errant bloom
this just gives you all the possible permutations
a permutation is a shuffling of your data
oblique oracle
meaning try every possible data combination?
errant bloom
yes
but it's a bit smarter
instead of trying all the permutations of the possible board combinations
which would also mean that you could place two queens in the same row, you make some restrictions
and already fix one of the two coordinates for each queen
that reduces your search space
it's still brute force, but a smarter solution than randomly placing your queens, or trying every single field
oblique oracle
The first i1, i2, perm[i1], perm[i2] is 0101 I don't know that that mean
is it the position of two queenfs?
errant bloom
are you familiar with python?
oblique oracle
yes
errant bloom
okay, yes this particular example is for 2 queens
check what combinations does in the docs https://docs.python.org/3/library/itertools.html#itertools.combinations
oblique oracle
i understand what it gives but not what it represents
errant bloom
it gives you the y coordinate of your queens
you know the x coordinates of your queens, right?
oblique oracle
i1, i2 = x1, x2? perm[i1], perm[i2] = y1, y2?
oblique oracle
I feel like I'm detecting a collision here?
errant bloom
what do you mean?
oblique oracle
like if two things occupy the same space like in hashing
errant bloom
but that doesn't happen
oblique oracle
like if I put a queen here she occupies this space and i put the next queen down and if
errant bloom
by construction, you don't place two queens at the same spot
oblique oracle
meaning she occupies 22 spaces
errant bloom
for a board of size nxn, each queen can only go on n different places
and even less, because once you have the positions of n-1 queens, the last one is already determined by the fact that you're using a permutation
try to do the example by hand on paper, before you use the code maybe
oblique oracle
Okay thank you.
errant bloom
try it out a bit and you can ping me if you're stuck again or still need help
I'll try to explain it differently then 😄
@oblique oracle https://repl.it/repls/SereneWastefulCleantech I commented the code, maybe that helps
oblique oracle
WOW thank you soooo much!!!!
I was trying this https://repl.it/@Michaelmikey/KnobbyUltimateAmpersand#main.py
so when we check for vertical we are by default checking for horizontal because the abs will still be the same?
errant bloom
we don't check for vertical
there is exactly one queen on each column
so all we do is check for horizontal, which are the permutations
but to see if they diagonally collide, we need to also get the vertical coordinate somehow, which is what the it.combinations does
oblique oracle
Do you think a statistics course would be a prerequisite for this really its my first time working with "combinations" and "permutations"
at the start of the class they stated you need no background
errant bloom
no
this has absolutely nothing to do with statistics
don't worry mate, there were times where I spent 2 weeks trying to solve an algorithm problem
and looking back, it's not like those were difficult problems. You'll get better at this the more you do it
oblique oracle
Thank you. I'll google permutations more all I find is in statistics
errant bloom
You don't need to know much about permutations
Just that you rearrange, and try all the shuffles
He couod have explained the algorithm without ever using the word permutation
oblique oracle
Im thinking the ugly way is a nested for loop 3 times?
errant bloom
For what?
Use python itertools to create the permutations, it's not trivial to do it efficient yourself and will be a new algorithm to learn. It really doesn t matter for this problem how you get the permutations
errant bloom
what does that mean?
that's not a permutation, in a permutation you don't duplicate
because if you have 0111 then this means that you have queens at (0,0), (1,1), (2,1), (3,1) which is wrong because they are all horizontally aligned
oblique oracle
okay I think thats the idea I'm missing thank you
errant bloom
good 🙂
weary tiger
sick swallow
2^(n-(n/2)Ck)
obtuse lance
try to explain what you think it's saying, that might help, just do your best even if you know what you're saying is wrong
south marten
Can someone look at my attempted proof: http://mathb.in/44609
lyric pumice
@weary tiger Start by disregarding conditions like "minimum" and think about what n could be.
What does it mean for students to receive the same grade?
@south marten it's-->its
The set X has at most n elements.
south marten
ahhh okay thank you I struggled with that proof 🙂
@lyric pumice other than that the argument is okay right ?
lyric pumice
That statement changes the entire proof.
You cannot color 1 element red and n other elements blue because that would imply that X has n+1 elements, which contradicts the assumption that X has n-r elements.
south marten
ahhh okay that makes sense 😦
short hamlet
Can someone help me with a pigeonhole principle problem?
This is the problem
this was my solution but i dont think it is corrent
*correct
south marten
@lyric pumice how bad was my attempt because I spent hours racking over it
lyric pumice
Either come up with a counterexample or prove that there is such an isomorphism.
@worthy palm
weary tiger
What does it mean for students to receive the same grade?
@lyric pumice students grade map to the same grade value?
i kind of think of it as a function
weary tiger
I mean how come you can't just take 4 students and let them all get the same grade lol
lyric pumice
4 students don't all have to have the same grade.
Having 4 students does not require that all 4 of them must have the same grade.
weary tiger
true
but what's stopping all n amount of students from having the same grades
i dont see that restriction in the question
so it's kinda confusing
lyric pumice
Nothing is stopping all n of the students from having the same grades.
weary tiger
hm okay i think i get it now maybee
im thinking of something
i think minimum is 16
n = 16
but i just used a book shelf analogy from another similar question, I want to maybe find formula for this
if thats possible
lyric pumice
@worthy palm I presume that the size of the cycle space of a graph is preserved under subdivision.
lyric pumice
Well, the cycles are not technically the same, but the vertices of the old Eulerian trails appear in the new ones.
@weary tiger Good.
weary tiger
is there a way to do it with a formulA?
lyric pumice
Almost certainly.
weary tiger
i just drew this:
A | | |
B | | |
C | | |
D | | |
F | | |
and like the next one has to be the 16th |
so that's how i got my answer
but not sure how to do the formula way
weary tiger
Hey I have this question I am stuck on which goes as follow
"How many words, of length 10, can we form if we are to use exactly one 'a', two 'b',
three 'c' and four 'd'? "
I am unsure how to start of doing this so any help would be appreciated 😄
stray reef
there's a way to do it by deliberate overcounting
if you pretend all the b's, c's and d's are distinct from each other then you get 10! words
but then to factor in the fact that the d's are distinct you need to divide by 4!
then by 3! for the c's and 2! for the b's
vital dewBOT
Ann:
weary tiger
probably because language but delibirate overcounting is a word I am not familiar to what is the idea of that ?
stray reef
makes sense cause it's a term i just made up
weary tiger
hahah
stray reef
basically it's overcounting but in a controlled manner
one that can be accounted for
like counting everything exactly twice
or exactly three times
stray reef
,calc 10!/(4! * 3! * 2!)
vital dewBOT
Result:
12600
weary tiger
Another question anyone familiar with Dijkstra's Algorithm? I am suppose to find the shortest path from the corner "d" to all other corner in the graf G below with help of Dijkstras algorithm.
last timber
@weary tiger what exactly you need
i mean have you read pseudocode of dijkstra's algo?
weary tiger
Sorry should of explained better I am not super familiar with dijkstras Algorithm just started learning about it and wonderd if I can get some help understanding
last timber
alright, but have you at least read pseudocde for it?
weary tiger
Yes I have
last timber
so you have to find shortest path from d to which vertices?
weary tiger
to all other corners in the Graf
last timber
wdym by corner
weary tiger
Like shortest path to a,f,i,u etc
last timber
do you need to find paths or only their cost?
weary tiger
Path and cost I think i looked at an exampel and he started from "e" and went to "u".
Wrote it like this
last timber
why
look
initially all your vertices are labeled with infinity
except for starting one d
then look what you do
you will have two sets
(or label on vertices)
what you do is i will write down pseudocode
or no
alright i will just copy pseudocode here
and we will do it step by step together
weary tiger
you can pm if you want to leave chat open for other questions
last timber
ok
vital dewBOT
Your roles have been updated!
steady axle
Say I am looking for a combination of 3 numbers, from the possible values of 5 numbers (0,1,2,3,4), that would equal 4. Is there a formula to find this, or what would I need to do?
weary tiger
i think this is what you need?
@steady axle
actually yours seems a bit different
soz
steady axle
Would you like me to share the actual problem?
weary tiger
sure
steady axle
Something like this word problem
I say 5 numbers (0,1,2,3,4), because I would like to account for empty throws (0) when a value of 4 is hit
vital dewBOT
Zophike1:
cerulean ore
Is it possible to improve the worst-case performance of bucket sort algorithm?
vital wyvern
hello everyone can I ask a question?
what does it mean when the elements of a set is meaningful and unambiguous
south marten
@vital wyvern essentially it means for elements of a set to be unambigious is if that element is define clearly
vital wyvern
what would be an example of an unclear definition?
sour arrow
There should be no confusion on whether or not a given element is in a set
sour arrow
It either is, or is not
vital wyvern
thanks!
sour arrow
Np. Feel free to ask if you have anything else
vital wyvern
will do! :p
fallen tinsel
could i prove this by showing that the cardinality of A is less than P(a) using the proof that that elements of set A is n and P(a) is 2^n so n < 2^n for all natural numbers. and since the cardinality is less is it not surjective ?
fallen tinsel
i need to make my own proof for it so cant use that
i was wondering if it was possible to show through proving the cardinality is less
last timber
that |A| = n and P(A) = 2^n wont work if set is infinite
fallen tinsel
even if the set is infinite wouldnt 2^n be larger and still a smaller cardinality
last timber
rationals intuitively are larger then naturals but there is bijection between them
obtuse lance
more than intuitively, the naturals are a proper subset of the rationals
serene basalt
|N| = |Q|
fallen tinsel
so my proof would only work if the set A is finite?
last timber
yes, when A is finite you just say that |P(A)| > |A| and that's all
fallen tinsel
gotcha.. im doing a presentation to my professor tomorrow on this theorem and i cant use the proof from the book and have to present my own so i was trying to figure out a different approach to it
serene basalt
this also works with A infinite
fallen tinsel
maybe i could do the proof my way then do a separate proof given A is infinite ?
last timber
rn i just skimmed through google and all proofs base on russel paradox mhm
fallen tinsel
this is the proof that my textbook used
fallen tinsel
ah gotcha, so yeah i was told i could use the idea of the textbook but needed to be phrased different and i was struggling to do that so i decided to try and take a completely different approach and try to go through cardinality
but if that doesnt work than maybe i can reevaluate
last timber
1010 and five elements remain
in fact you have just to find number of bitstrings of 5 symbols for second prop
weary tiger
what
last timber
if bitstring starts with 1010 you already know first 4 bits
now you have to find remaining 5
last timber
how would you find amount of bitstring of length n?
without any additional constraints?
weary tiger
2^n
last timber
so plugging n = 5?
weary tiger
32
so there are 32 bit strings?
with that property
how come the answers im getting isn't one of the options
for the first property, i got 16
so i did 16+32
but there's no option for that answer
last timber
@weary tiger because look
101010101
satisfies both properties
you need to trace that satisfy both
weary tiger
but it says or
last timber
yes, but look
suppose i have 101010000
which is in first set
1010111111
which in second
and 101010101
by simple + you will get that you have 4 strings
whereas in fact you have 3
and are u sure that for first property there is 16?
weary tiger
and 101010101
@last timber this would be in both sets yeah?
last timber
ye
weary tiger
truee
last timber
so u have 64 but you have to trace string in intersection
weary tiger
so in terms of sets whats the goal? take out the duplicates?
last timber
yes
weary tiger
ok i see
@last timber this would be in both sets yeah?
@weary tiger wait i thought it starts at position 0
@last timber
last timber
?
last timber
what
weary tiger
last timber
bits are numbered 1, 2,3
weary tiger
why did you say "ye" to this
oh okay in computer science it starts at 0 so i thought it started at 0 here too
last timber
because 101010101 has both first property (0's at even bits) and second one
well, if it start from 0 it is equivalent to 0's at odd bits
answer should not change
weary tiger
hmm ok
this is not intuitive at alll for me lol
wait i dont get this... If the bits are numbered 1,2,3 then wouldn't there be 4 even positions and 5 odd positions @last timber
weary tiger
but if started at 0 itd be 5 ,4 respective
last timber
look
if you number from 0
you have 0's at odd positions
-0-0-0-0- where - for unknown bit
if you number from 1 you have 0's at even position
but nevertheless, the amount of -'s, that is, the amount of unknowns bits is still the same
weary tiger
oh i thought ur example was saying someting else
i dont get it
if your start position is different, the number of odd,even positions will be different too
weary tiger
lol
last timber
if your start position is different you would have to restate the whole task
weary tiger
like if n = odd number
last timber
what is n?
last timber
yes
stray reef
what problem are y'all doing again
weary tiger
i dont really care
last timber
@weary tiger if you would start enumeration from 0, you should restate first property as "the bit at each odd position is 0"
but in both statements the amount of unknown bits is the same
stray reef
i mean like ok let $A$ be the set of bitstrings with 0's at all even positions and let $B$ be the set of bitstings beginning with 1010
vital dewBOT
Ann:
weary tiger
@weary tiger if you would start enumeration from 0, you should restate first property as "the bit at each odd position is 0"
@last timber okay that makes sense then
stray reef
we're looking for $|A \cup B|$, and for this we need $|A|$, $|B|$ and $|A \cap B|$
vital dewBOT
Ann:
stray reef
none of which is particularly hard to calculate imo
weary tiger
yeah im working on (A n B) now
last timber
the problem as far as i see was even not in method of calculation
but the-elite was confused by enumeration
stray reef
$A \cap B = { 1010x0y0z \mid x,y,z \in {0,1} }$
vital dewBOT
Ann:
weary tiger
wow writing it out like that makes it so much easier
thank you all @stray reef @last timber
fallen tinsel
is the reverse of cantors theorem true? is P(A) onto A? i can see that it is for finite sets but wanted to be sure it was the case with infinite as well
stray reef
are you asking whether or not there always exists a surjection of P(A) onto A?
stray reef
i believe you might need choice to prove it for sets any larger than N
fallen tinsel
before i spend a very long time working on writing this out i was wondering if someone could look over my idea and see if it makes sense to
this is what i have to prove. I was planning on breaking it into two cases, If A is finite or infinite. If finite I plan on writing that A has n elements and P(A) has 2^n so by cardinality it wouldnt be onto.
then if A was infinite, I was going to use this argument
stray reef
that argument applies regardless of the finitude of A
fallen tinsel
so would it be wasteful to include the finite part? this is for a presentation so i want to make sure that its clear to my professor that i understand and am not just copying a proof online
stray reef
yes it'd be a waste of time
you can mention that the argument applies regardless of whether or not A is finite
fallen tinsel
ok sounds good thank you
vapid light
Wow, pretty slick
oblique oracle
I have a challenge if you can do the last one without cheating http://dm.compsciclub.ru/app/quiz-clock-game
unreal stump
||Isn't it just binary search?||
last timber
it is
unreal stump
It is not truly random
oblique oracle
I don't know I can't get it and the instructor insists its solvable
warped mica
It's easy to do, but the number they give you is not random at all
I think it is programmed explicitly so that you can only solve it if you do binary search
last timber
?
stray reef
you should start by comparing to 1,048,576
and go up/down in descending powers of two
that's how you avoid falling one question short
last timber
,w log_2 (2097151)
vital dewBOT
last timber
ye 21 question is enough
warped mica
2^20 = 1048576
2^20 + 2^19 = 1572864
2^20 + 2^29 + 2^18 = 1835008
...
Carry on with this pattern and I assure you that at the end the number will be 2097151
oblique oracle
so we can't split it 21 times and guess it in one try?
warped mica
You can split it in half 21 times and get the answer for sure
oblique oracle
see my answer wasn't even close to the split though
warped mica
That's the theory
oblique oracle
the number changes as you guess
warped mica
The thing is that this website is not picking a random number, it is cheating and you can only beat it by binary search, which is what you said
last timber
oh finally they didn't give me maximal possible range value
warped mica
@last timber but that only happened because you went above the half point in that third guess, so now the range of possibilities is too large and you cannot win (because the game cheats)
Try it, any third guess below 1835008 will tell you that x is larger, and any third guess above said number will tell you that x is smaller
oblique oracle
right I can beat it by binary search but rounding it killing me to get the actual values
1 number off and you don't get it
warped mica
You can even do this on your first guess: anything below 1048576 will tell you x is larger, and anything above it will tell you x is smaller
last timber
i did nt manage to catch them on explicit cheating tho
oblique oracle
did you solve it?
oblique oracle
how?
warped mica
Did you read my previous message?
last timber
write my own binary search lol
warped mica
Input the values 2^20, 2^20+2^19, 2^20+2^19+2^18...
oblique oracle
2^20 = 1048576
2^20 + 2^19 = 1572864
2^20 + 2^29 + 2^18 = 1835008
...Carry on with this pattern and I assure you that at the end the number will be 2097151
@warped mica this?
warped mica
And I guarantee you will win and the final answer will be 2097151 = 2^22-1
Yes, that one
warped mica
Is that the source?
oblique oracle
the final answer should be 1618235
last timber
oblique oracle
yes the javascript is cheating
warped mica
Yeah, that's the explicit cheating l
oblique oracle
I set an alert to tell me what the answer was
void valve
Could anyone confirm whether this takes the order into account?
Because the first part is getting all the permutations of the drawn objects but removing the permutations of each kind of object
quaint star
It does not take order into account.
It gives the probility of obtaining k1 objects of the first kind, in whatever order you got them
What would it even mean for it to take order into account?
void valve
Ok but is my interpretation of the first part correct? Like we have n! which is the permutations of the n drawn. Then we are removing the permutations for each object as they are the same
why are we doing that?
Yeah I guess youre right that it does not make sense to take the orderings into account hahah
but what should I make of the first part before the second product sign?
Like for two objects of amount a and b we have that
quaint star
Combinatorics is not my strong suit lol
void valve
Ok but I will try to make sense of it and you tell me where I go wrong
we have 'n' spots to fill, we want 'k' of them to be the desired outcome. That is, all the k-subsets of n (nCk) give the possible orderings in which we can have our desired outcome. We multiply it (why???) with having the desired a/(a+b) in k spots and the undesired in the rest (n-k) spots
I got even more confused after writing that, it isnt my strong suit either haha lol
quaint star
Oh it's right
void valve
Hahahah
quaint star
Let's find the probability of drawing k objects of type a
Each draw has a probability of (a/(a+b)) of being of type a
So if you want k draws in a row to be of type a, it is (a/(a+b))^k
Do you agree?
void valve
Yep so far im with you
quaint star
Then if you want the next n-k draws to all be of type b, you have to multiply by (b/(a+b))^(n-k)
quaint star
Shhh
void valve
heheh
quaint star
So (a/(a+b))^k (b/(a+b))^(n-k) is the probability of a specific draw happening with k items of type a and n-k items of type b
void valve
Yes sir
quaint star
By a specific draw, I mean the order matters: did you draw aabb or abab
So now to find the probability of any such draw, you have to multiply by how much such draws there are
And there are nCk many of them
void valve
nah here I dont understand why tbh
like first of all wouldnt the number of all such draws be nPk instead?
quaint star
Wait
Let's take a small example
5 objects. 3 of type a, 2 of type b
Let's say we draw 3 objects and want 2 of type a and one of type b
The probability of getting aab is $(3/5)^2 \times (2/5)$.
vital dewBOT
Lunasong:
void valve
yes with that I would agree
quaint star
But you could also draw aba or baa
And those have the same probability of occurring
So the probability of getting any of these is $3 \times (3/5)^2 \times (2/5)$
vital dewBOT
Lunasong:
quaint star
Where the 3 is there because that's in how many ways you can draw it
Does that make sense?
void valve
Yeah ok that does actually make a lot of sense
void valve
Ok oceans of thanks man
so we are multiplying the probability of both events happening with the number of times it happens
kind of
i.e. addition principle?
quaint star
Yeah exactly
void valve
thanks I really needed your help to see it
quaint star
If you want to understand why it's nCk. Think of there being n possible positions for the k objects of type a and you have to choose k of them. There are nCk ways to make that choice.
void valve
Would it make sense to see it as all the "subsets" of the positions?
ok but if I can bother you just a second more, for the general case I posted first
We aren't really doing nCk
but does this:
Because the first part is getting all the permutations of the drawn objects but removing the permutations of each kind of object
@void valve
make sense?
quaint star
The last part is the product of the probabilities
void valve
Yep that one I get
but like the first part is like the ways you can rewrite "hello" (5!/2!) right?
quaint star
The $\frac{n ! } {\prod_1^r k_i!} $ is the number of ways you can draw it
vital dewBOT
Lunasong:
quaint star
It's the equivalent of nCk in the general case
void valve
but like the first part is like the ways you can rewrite "hello" (5!/2!) right?
@void valve
is it the same as this?
because then I think I understand it fully
if not Im not sure
rewrite as in jumble the letters up uniquely
void valve
Thank you alot, seriously I really couldnt grasp it 🙂
quaint star
Np
waxen bear
lyric pumice
The question can be either.
sick swallow
it is combinations
pale surge
If you don't treat switches as distinct, then it would be combinations.
sick swallow
but they are all the same thing
and it just wants total postitions which satisfy the condition, and two positiions are equivalent through permutations
weary tiger
I don't get how to find strings with at least 1 lowercase letter
so far i have 52^15 - 26^15
pale surge
I think you should calculate how many have exactly 0 or 1 and remove that from the total
weary tiger
yes
I don't get how to find strings with at least 1 lowercase letter
so far i have 52^15 - 26^15
note that KD said "exactly 0 or 1", not at least 1 lowercase letter
?
velvet junco
I was wondering if anyone had a clue with this one
The property he's hinting at would be demorgan's theorem
but ive got not clue how that could be used for simplification here
weary tiger
rip Reckful 😦
velvet junco
yes
hollow bloom
Are plane graph planar?
weary tiger
plane graphs?
weary tiger
yeah that's a planar graph
hollow bloom
Gotcha
I was confused because
The definition for planar graph is like it’s a graph that can be redrawn with no edge crossed
But if plane graph is already redrawn
I thought it didn’t make sense to call it planar
Or I’m just being dumb, but either way thank you for your confirmation!
hollow bloom
Then it is still planar right?
distant bobcat
I did this proof, but was wondering if this is directly related to the Cauchy-Schwartz inequality?
weary tiger
this looks written backwards
honest barn
I agree
last sigil
stray reef
yeah it is written backwards and also the assumption of a, b, c ∈ Z is frankly unnecessary
hell you don't even need them to be positive.
and also the "for all positive integers a, b, c" should have been formatted as a line of plaintext rather than as a formula
distant bobcat
Thanks, Ill remember to write the text as a plaintext next time.) Ironically the problem has this form and its from the book " How to think like a Mathematician" which is supposed to illustrate good proper form one would think haha. Anyway couldnt one see this as some sort of variance of the Cauchy inequality? It looks at least pretty similar, no?
stray reef
yeah it's cauchy with the vectors (a,b,c) and (b,c,a) basically
distant bobcat
thanks
delicate ridge
Also it should be spelt "practice"
void valve
Could somebody help me "see" that formula or explain in words?
For probabilities of the events A and B
Like it makes total sense if we divide both sides with P(A), P(A) becomes the new sample space and B happening given A has happened leaves their intersection as favourable outcomes
but I can't see why it makes sense when we rearrange it like this, help would be appreciated 🙂
unreal stump
P(B|A) is probability of B occuring,if A occurs. P(A) is Probability of A occuring.
So,We see if A occurs and in that case,we see if B occurs
Which is same as seeing A and B occuring at same time
void valve
Ah yeah ok I think I get it actually, A occurs, given that A has occured we see if B occurs we multiply them and that gives the intersection
unreal stump
Yea
void valve
What would the formula become if they are disjoint? Like P(B|A) has to be zero as B can't happen i A has happened?
void valve
Like if they are disjoint we dont have P(A intersection B)
what on the right hand side makes it zero?
Is it that B can't happen given that A has happened in P(B|A)
I mean I guess
last timber
may i suggest first think about equivalent
P(B|A) = P(A n B)/P(A)
void valve
Yeah vimes, that one I can visualize perfectly
P(A) becomes the sample space as A has already happened
And what remains would be their intersection if B also has to happen
It is just that I cant visualize it when we multiply both sides with P(A)
last timber
but then if we know result of multiplication of probabilities of events including A and of events where B happens in sample space of A we are able to find P(A n B)
void valve
Sorry what do you mean exactly?
Multiplication is intersection more or less, right?
Of two probabilities
I mean algebraically I get it, it isn't that
last timber
i mean that P(A n B) is like product of probability that event A happens and event B happens when A does so
void valve
But would it be possible to draw a venn diagram or something? It being normal multiplication trips me up I guess
Is multiplication of probabilities always them both happening at the same time?
void valve
Hahah nice, I mean P(B|A) being the ratio is the formula but why is it + green also?
void valve
But P(B|A) = P(AnB)/P(A) where is the plus green?
Shit I think I just became more confused now
perhaps Im overthinking it
last timber
yes
void valve
P(B|A) = green / (red + green)
Therefore P(A n B) = green / sample space (???)
Ah ok yes that makes sense hahah 😄
Yeah ok it feels like multiplying the formula still but I have a much better picture of it now, thanks 🙂
Just another perhaps somewhat embarrasing question, is P(A) * P(B) (as in normal multiplication) always P(A n B) ?
last timber
only if A and B are independent
last timber
i mean that is definition of independept events P(A n B) = P(A)P(B)
void valve
They are dependent if there is a conditional probability P(B|A)?
last timber
like consider when P(B|A) = P(B) or in words probability of B = probability of B given A
void valve
That only happens if they are independent?
Otherwise we have P(B|A) = P(A n B)/P(A)?
Like is independent = disjoint sets in this case?
void valve
Ok thanks that is a great example describing it, so when they have no connection their probability can easily just be multiplied
frank zinc
What is relevant to determining whether there is an euler path that is not a circuit on a graph?
This is for discrete structures, but I am not sure if it falls under this
last timber
@frank zinc if all vertices are of even degree graph contains circuit
if exactly two vertices are of odd degree it contains path but not circuit
frank zinc
So basically a circuit is not a subset of a path