what is this formula meant to be for?
#discrete-math
stray reef
is there a problem you're doing right now?
the expression C(n+r-1, r) has no meaning until you say what problem you're trying to solve.
bold relic
number of ways of selecting r object from n obj, allowing repeated selections
here is a problem
A box contains 20 balls. In how many ways can 8 balls be selected if each ball can be repeated any number of times?
stray reef
so the balls are all distinct from each other, right?
bold relic
not really
stray reef
bold relic
can be can be not
stray reef
now that's weird
cause right now, the problem sounds like the answer would be 20^8
because as far as i can understand, you have 20 balls (labeled with the numbers 1 through 20 or something)
and you're pulling out 8 balls one at a time, recording which ball you got and putting it back in before pulling out the next
and you want to know how many possible records there may be
and that is 20^8
is that not what's happening?
bold relic
yes it is wrong
stray reef
"it" meaning my interpretation of the problem?
bold relic
yes
stray reef
okay, so what should it be instead?
i have arrived at another possibility, but only by considering what it might've been based on the expression you opened with
stray reef
...how much later
bold relic
cause right now, the problem sounds like the answer would be 20^8
I dont think this is correct
because
a wait hold on
I thought it is 20! at the begining
because when you choose 1 ball
the options that you can choose for the second one decrease to 19
and so on
20^8 is still an incorrect
stray reef
"if each ball can be repeated multiple times" seems to contradict "the options that you can choose for the second one decrease to 19"
bold relic
yea I can imagine it now
bold relic
20^8 is still an incorrect
the answer is 27C8
idk how to derive that
there is a dude
who explained it this way
This formula can be reached quite easily. Think of this problem as n choices of ice cream and r scoops. Put the ice cream choices in a row. If you start from one end and move across, you will have a total of n-1 moves and r scoops, which gets the n+r-1 part of the formula. Then, from these, you have to choose r scoops, which gets you the formula, C(n+r−1,r).
Idk the r scoops part
stray reef
there can be no talk of a derivation until we are all clear on what the problem is.
which right now, i at least am not.
stray reef
A box contains 20 balls. In how many ways can 8 balls be selected if each ball can be repeated any number of times?
i guess im not clear too
stray reef
is this the verbatim statement of the problem?
bold relic
yes
stray reef
huh.
stray reef
okay so presumably we do not count "1, 1, 1, 2, 2, 2, 3, 3" and "3, 2, 3, 1, 1, 2, 2, 1" as different outcomes for example
okay, then it becomes clear to me why it's meant to be 27C8. but the problem could be worded better.
bold relic
okay so presumably we do not count "1, 1, 1, 2, 2, 2, 3, 3" and "3, 2, 3, 1, 1, ...
ohhh
but i still dont understand C(n+r-1,r)
stray reef
A box contains 20 balls. You pull out eight balls one at a time, replacing each one before pulling out the next, and record how many balls of each type you got. How many outcomes at possible?
this is how i would amend the wording of the problem
bold relic
this problem is like 8 yrs ago
stray reef
so an outcome is essentially characterized by a list of 20 nonnegative integers adding up to 8.
an example outcome would be:
Ball #1 - 3
Ball #2 - 0
Ball #3 - 0
Ball #4 - 1
Ball #5 - 1
Ball #6 - 0
Ball #7 - 2
Ball #8 - 0
Ball #9 - 1
Ball #10 - 0
...
Ball #20 - 0
have you heard of stars and bars?
bold relic
no i havent
stray reef
okay great
that means i get to explain this my own way
each record from your experiment can be represented with an arrangement of 8 white stones and 19 red stones in a row.
it is a bit unwieldy with the numbers you have here, but the precise description of the translation between the two is as follows
to go from a record to an arrangement of stones, arrange the stones in the following order:
- as many white stones as the number of times ball #1 was pulled out
- 1 red stone
- as many white stones as the number of times ball #2 was pulled out
- 1 red stone
- as many white stones as the number of times ball #3 was pulled out
- 1 red stone
... - after the last red stone, as many white stones as the number of times ball #20 was pulled out
to go from an arrangement of stones to a record, read it off as follows:
the red stones separate the row into 20 runs of white stones (and if there are two or more red stones adjacent to each other, we consider them to be separated by a run of 0 white stones)
the length of each run of white stones is the number of times the corresponding ball type has been pulled out
bold relic
im trying to understand
stray reef
i would present an example here, but there are too many ball types and too few draws to make it illustrative
are you ok with me demonstrating an example with different numbers?
bold relic
yes
stray reef
okay
say there were only 4 types of balls, and you made 16 draws
with my "row of stones" method, you would have 16 white and 3 red stones
a record like this:
Ball #1 - 4
Ball #2 - 9
Ball #3 - 0
Ball #4 - 3
would translate into the following arrangement of stones:
⚪⚪⚪⚪🔴⚪⚪⚪⚪⚪⚪⚪⚪⚪🔴🔴⚪⚪⚪
bold relic
thats 16 balls
stray reef
16 stones
this is how you read that arrangement of stones
oh oops!
yes, sorry
i typo'd
bold relic
i'll need a sec to run through all of these explanation
stray reef
of course, take your time
bold relic
maybe 2 secs
stray reef
i've corrected my typo in the meantime
bold relic
how can I derive C(n+r-1,r) from this arrangement of stones?
stray reef
well counting the arrangement of stones
you will find that there are 19 stones, of which 3 are red and the rest white
bold relic
16* u mean?
stray reef
no, i mean 19
there are 16 white stones and 3 red stones
each white stone represents a ball drawn from the box, and its position relative to the red stones is what identifies which ball type it was
you will have C(19,3) as the answer to this problem (16 draws, 4 ball types)
bold relic
C(19,4)?
stray reef
no, C(19,3).
the number of red stones is 1 less than the number of ball types.
in general, when you have n types of balls and r draws, translating the problem into arrangement-counting as i demonstrated will require r white stones and n-1 red stones.
thus the number of arrangements is C(r+n-1, n-1)
or C(r+n-1, r), which is the same
bold relic
no, i mean 19
so this problem require to form a row of 3 balls?
stray reef
please reread what ive said
there are two parts to my explanation
er, not two.
- translating from "counting ball-drawing outcomes" to "counting arrangements of white & red stones"
- understanding how the number of draws and the number of ball types translate to the numbers of white and red stones to be arranged
- counting the arrangements of white and red stones.
which one of these requires clarification?
bold relic
1
bold relic
an example outcome would be:
```
Ball #1 - 3
Ball #2 - 0
Ball #3 - 0
Ball #4 - 1...
is this 1?
i understand this
bold relic
it is a bit unwieldy with the numbers you have here, but the precise description...
i dont understand this
god im so confused rn
bold relic
a record like this:
```
Ball #1 - 4
Ball #2 - 9
Ball #3 - 0
Ball #4 - 3
```
woul...
ok this is 1
i dont understand that
no
i understand that
stray reef
no, the things we're putting in a row are STONES, not balls.
bold relic
itscoming together now
ohhhhhhhhhhhhhhhhhhh
okok
i understand all now
thank you very much
can you give me an e.g. to see if I can do this in row of stones way?
stray reef
another problem like this but with different numbers?
ok
let's say you make 8 draws with 3 different ball types
stray reef
no.
again, the things we're arranging in a row are called stones, specifically to distinguish them from balls.
i do not exactly appreciate this distinction getting conflated.
bold relic
i mean
how many are going to be selected?
to form a row
i terms of balls
not stones
stray reef
8 draws => 8 white stones
3 types => 3-1 = 2 red stones
bold relic
it is a bit unwieldy with the numbers you have here, but the precise description...
what is the purpose of pairing 1 red to n number of white stone resemble the draws?
bold relic
what does red stones do?
stray reef
each white stone represents a ball drawn from the box, and its position relative...
.
put another way, red stones act purely as separators between white stones.
bold relic
10C2 for the problem
ball#1: 4; ball#2: 4; ball#3: 0
⚪ ⚪ ⚪ ⚪ red⚪ ⚪ ⚪ ⚪ red
although
this method works
but the red stones still kinda random idea to come up with
I am rereading everything
loud copper
what font is this
stray reef
fantasque sans mono
loud copper
nice font. thnx 
pale sorrel
hello, i was wondering why this combinatorial proof was not finished after the highlighted statement
dense geyser
It is. But sometimes it's nice to go into a little more detail just to help explain it a different way
dense geyser
do you know bayes rule?
deep portal
For something like Proof that 1/a + 1/b ≥ 4/a+b
Do a and b have to be different numbers
faint narwhal
no
snow sleet
hello, i was wondering why this combinatorial proof was not finished after the h...
as someone else said, the proof is already finished. We know this because they showed $\sum_{k=0}^n\binom{n}{k}(-1)^k=0$. This means the number of even sized subsets of an $n$-set minus the number of odd-sized subsets of an $n$-set is $0$. i.e., the number of even sized subsets of an $n$-set \textit{equals} the number of odd-sized subsets of an $n$-set.
vital dewBOT
logician
little oyster
Hey, I'm wondering, if I have a p3 graph, with the first end already coloured how would the chromatic polynomial be for the rest? It cannot be (x-1)^2 right? It would've been x(x-1)^2 if all three vertices were uncoloured to begin with.
young monolith
W O L L O N G N O G
waxen nest
ohh okay what about this one?
is the tree correct based on inorder and preorder traversal?
waxen nest
hmm do you know what will be the post traversal output?
young monolith
W O L O G N N O L G
waxen nest
ok thanks
remote cosmos
is that an australian tree? 
dense geyser
is the tree correct based on inorder and preorder traversal?
The way i remember, pre/in/post refers to where the parent node goes relative to its children. So in preorder, the root node is the very first element in the traversal, but is very last in post order
proper bronze
How would I express this in set builder notation?
${(1,1), (2,1), (2,2),(3,1), (3,2), (3,3), (4,1),(4,2),(4,3),(4,4)}$
Thank you!
vital dewBOT
allucinator
weary tiger
Looks like ${(x,y) | y \leq x \land x \leq 5 \land x \in \mathbb{N} \setminus 0}$
also x,y in N \ {0}
Ah yes
proper bronze
Both x and y are natural nums.
vital dewBOT
cpl
weary tiger
y also in N though
Both are assumed natural
Looks like ${(x,y) | y \leq x \land x < 5 \land x > 0 \land y > 0}$
proper bronze
Thank you! I was thinking about indexing the cells of a square grid.
vital dewBOT
cpl
proper bronze
That's why my sequence looks like that.
weary tiger
Starting from 0 makes it easier
Because you skip the constraints that x and y be greater than 0
But it depends on the application
proper bronze
I am making something like this. But those indices I have shared earlier are for rows and columns.
weary tiger
ok
warped pecan
I was wondering if someone could please give some pointers for this
If I have n vertices and n +1 edges
What is the expected value of the number triangles?
I know my number of trials is n choose 3
But not sure how to go about computing the probability
With the n+1 edges selected uniformly at random
thorn copper
do you have like a screenshot of the question or something
not sure if its just me but i feel like i cant comprehend the question much like this
weary tiger
what is the expectetd value of number of triangles in a graph with n vertices and n+1 edges.
civic dagger
Non-Negative Integral Solutions:
If I have an equation like x1 + x2 + x3 + x4 + x5 = 12 with constrains like x1 ≤ 7 and x2 ≤ 5, would I calculate the total number of non-negative integral solutions with no constraints and then subtract the number of solutions with each constraint one by one? (If I substitute in y1 = x1 - 8 and y2 = x2 - 6 [where I assumed the constraints x1 ≥ 8 and x2 ≥ 6] I end up having to subtract 14 because 8+6=14 which would then mean that there are no non-negative solutions)
If someone ends up answering this pls @ me, thanks :D
snow sleet
I'd do this using generating functions @civic dagger
if you can also assume each x_i satisfies x_i>=0 as well
weary tiger
For 3a showing R is transitive, do i use another ordered pair (e, f)? idk how this one works
cerulean wind
For 3a showing R is transitive, do i use another ordered pair (e, f)? idk how th...
take ordered pairs (a,b), (c,d) and (e,f) with (a,b) R (c,d) and (c,d) R (e,f). then show that (a,b) R (e,f)
cerulean wind
yea
weary tiger
okay thank you!
snow sleet
look at the coefficient of x^12 @civic dagger
civic dagger
yah, just so when i come to other questions i can be like hey this is a multiset
snow sleet
yah, just so when i come to other questions i can be like hey this is a multiset
multiset problem*
civic dagger
granted this technique definitely seems like something you'd only want to do for assignments
doing this in an exam
snow sleet
yeah you're not gonna wanna expand this all out on an exam
it's a great way for checking your answer though if you have a calculator that can do this polynomial expansion
but for exams, you're gonna wanna stick to stars and bars (aka identical balls into distinct boxes)
civic dagger
how would i go about doing stars and bars for c?
would i calculate it without restraints subtract the restraints 1 by 1? (feels wrong since im potentially over counting)
snow sleet
yea so for 1c, I don't think counting the complement would be easy
I think the restraints imply you must choose some amount from the other groups of flowers
for instance
civic dagger
hm i was just trying to do the complement so i keep it as a non-negative integral
snow sleet
okay, you could do that, but it's tricky because you'd have to cover the case when you choose at least 8 red or at least 6 yellow (inclusive)
it can be done forsure tho
civic dagger
hm it just occurred to me maybe they're trying to change the question to only 4 variables (7 red + 5 yellow = 12 roses total)
snow sleet
that's why i said the answer could be 1 (I dm'ed you this a while ago lol)
civic dagger
ohhhh
to be honest i didn't quite get what you meant
i still was thinking in my head there was 12 roses of the others left
snow sleet
however, if we're allowed to assumed we have at least 12 of each of the other kinds, then we need to do this
civic dagger
but now i see that you're saying there's ONLY red and yellow left
snow sleet
to be honest i didn't quite get what you meant
shoulda asked then and there lol
civic dagger
might just assume there's only red and yellow left lmao
snow sleet
might just assume there's only red and yellow left lmao
I'd ask your teacher fosure
civic dagger
i thought i understood but you were just 200iq
snow sleet
lmao
okay how about this
how about we solve the problem twice
so to speak
so if they were only talking about having only 7 red and 5 yellow left, then the answer is 1 there
we just solved the problem once lol
now if they assumed that we have at least 12 of each of the other kinds, then we need to do some more work
civic dagger
yeah, tbh that's the solution im intrigued about
especially if it can be done using stars and bars method (which i feel like it could?)
snow sleet
yeah, tbh that's the solution im intrigued about
okay let's do it
yea we can do it with stars and bars
civic dagger
because im sure in the exam theyll give us a question where there's a less than or equal to restraint
snow sleet
using the complement
civic dagger
yah
snow sleet
okay ready?
civic dagger
bet
snow sleet
So part a was the total
civic dagger
correct
snow sleet
that we'll be subtracting from
aight
now for the complement
we have
to count when we have at least 8 red or at least 6 yellow (inclusive)
civic dagger
understood
snow sleet
okay clearly we can't have both 8 red and 6 yellow
as that would be greater than 12
so if there must be at least 8 red, what's the count there?
snow sleet
what? I'm just talking about the case where we have at least 8 red flowers in our bouqette
snow sleet
right we don't care about yellow rn
civic dagger
kk
vital dewBOT
logician
civic dagger
yup right
snow sleet
okay now what happens when we have more than 5 yellows? this means we have chosen at least 6 yellows
civic dagger
wait, for the count above, is the formula we're using this?
but instead of taking n we're doing n-8?
should it be 12-8+4-1?
vital dewBOT
logician
civic dagger
oh mb
snow sleet
should it be 12-8+4-1?
no
snow sleet
okay so now we add up these two cases and subtract the sum of the cases from the total found in part a
so the answer is $\binom{12+4}{4}-\left(\binom{12-8+4}{4}+\binom{12-6+4}{4}\right)$
vital dewBOT
logician
civic dagger
okay yeah i might have done a shit job at explaining it but that was the method i was originally going to use
but the explanation helps
snow sleet
,w \binom{12+4}{4}-\left(\binom{12-8+4}{4}+\binom{12-6+4}{4}\right)
vital dewBOT
civic dagger
ty for the help
civic dagger
true
snow sleet
,w Expand[((Sum[x^i,{i,0,12}])^3)*(Sum[x^i,{i,0,7}])(Sum[x^i,{i,0,5}])]
vital dewBOT
snow sleet
yup
civic dagger
nice
snow sleet
look at the coefficient of x^(12)
civic dagger
can this generating function technique be used for anything else
snow sleet
yes
civic dagger
related to counting
snow sleet
yes
you can use them for many things in counting
you can use them for things related to partitions
multisets (like we've been doing)
you can use em for finding how many ways you can be n cents given some number of nickels, some number of quarters, some number of dimes, etc. to use
you can use them for figuring out how many ways the letters in a word can be arranged (in a row)
you've prolly heard of the Binomial Theorem?
civic dagger
yah
snow sleet
lo and behold, that has to do with the binomial coefficient!
yeah you can do cool stuff with GF's (Generating Functions)
civic dagger
yh ive touched it a few times but always forget its use cases right after i finish the exams rofl
honestly being able to characterise a question has been your biggest help, and obviously having ways to solve said question
i think that's where the course is lacking rn
snow sleet
awesome!
civic dagger
like now that i can look for questions that have multisets etc
i know how to approach them
snow sleet
yea GF's are a great way for giving yourself a surefire way of checking your answer to many combinatorial problems
snow sleet
like now that i can look for questions that have multisets etc
yes identical balls into distinct boxes, stars and bars, multisets, unordered selection with replacement, nonnegative integer solutions to a linear diophantine equation are all really the same concept...different names for the same thing tbh
snow sleet
you're welcome!
snow sleet
This channel is open for questions
bold relic
hello
where can I find math problems that are properly worded and suitable for freshman college
I was grinding on problems on careerbless but their wording of the problems sucks
and they might have wrong knowledge
khanacademy is just fundamental
pale epoch
this is a very open question
both "math problems" and "suitable for freshman college" are very open to interpretation
bold relic
i am studying combination and permutation
pale epoch
just pick any book on the topic, it should have plenty of exercises
bold relic
ok
weary tiger
I need help calculating how much I make an hour. I make 100,000 game coins every 15 seconds, can someone calculate how much that is per hour?
candid gulch
I need help calculating how much I make an hour. I make 100,000 game coins every...
jesus christ your question was answered in at least 2 channels
snow sleet
I need help calculating how much I make an hour. I make 100,000 game coins every...
please don't repost your question in other channels if you've already posted it in one channel.
candid gulch
Is anyone aware of any results on the rule 30 cellular automata that go along the lines of partially discovering the formula for the middle column?
pine star
if a relation R is symmetric, then the relation R^2 is also symmetric
I need to prove this but not really sure how to start
Let R be symmetric and let aRb and bRa.
Then xRa and bRx for some x. Since R is symmetric, it follows that aRx and xRb, then aR^2b and bR^2a. Therefore, if R is symmetric, R^2 is symmetric.
unreal stump
How is this equivalent to distributing 20 identical objects into 3 distinct boxes
faint narwhal
It's kind of like stars and bars. You put objects i + 1 through 20 into one box, objects j + 1 through i into another box and objects 1 through j into a third box
unreal stump
Is this generalisable? Like instead of j=1 to i,if I change it to j=1 to 2i,can I still use stars and bars
faint narwhal
Mm no I don't think that would translate to putting balls into boxes nicely anymore
gloomy beacon
Anybody get this one?
vital dewBOT
The Library of Babel
gloomy beacon
Ohh my bad yeah thanks
pine star
aRb iff either a mod 4 = b mod 4 or a mod 6 = b mod 6
This is not an equivalence relation, but I can't understand why.
it seems reflexive and symmetric
so it must not be transitive, but I can't think of a justification
dense geyser
so it must not be transitive, but I can't think of a justification
If a and b are equal mod 4 and b and c are equal mod 6, then a and c aren't necessarily equal mod 4 or mod 6. Haven't thought of an example, but I imagine that's why
faint narwhal
0 is equivalent to 4 and 4 is equivalent to 10, but 0 and 10 are not equivalent
vale cairn
faint narwhal
What do you mean?
Do you see why 0 is equivalent to 4?
And why 4 is equivalent to 10?
faint narwhal
0R4 if that makes more sense to you
pine star
Thinking about building a set based on the relation
pine star
xRy iff ax+by=0 for some a,b!=0, over the set of real numbers.
my intuition says that ax=-by which means the relation isn't reflexive
cerulean wind
x is related to x. take a = 1 and b = -1
cerulean wind
?
pine star
nvm I was just confused
cerulean wind
lol ok
hoary igloo
so just to make sure im reading this correctly
this means that phi(e1) is the edge that connects vertices v1,v2 and phi(e2) is the edge that connects v2 v3
last timber
yes
hoary igloo
V(G) is the set of the verticies and E(G) is the set of edgtes
thanks
sorry
wanted to double check
last timber
hmm
well
it is also possible to define graph to be tuple tho
like G = (V,E) where
E is subset of V^2
cerulean wind
same thing tho
hoary igloo
gracuas
pine star
xRy iff ax+by=0 for some a,b!=0, over the set of real numbers.
my intuition says...
but if I choose a=1,b=2, I can say that it's not reflexive unless x=0, right?
so it's only reflexive when a=-b
I'm trying to verify that the relation is an equivalence relation
grave sluice
why do you get to choose a and b?
as I read it there should exist a and b not for all a and b
pine star
1f is the question in... question
grave sluice
yes you dont get to choose a and b
lets say x=0 and y=1 here you cannot find a and b such that ax+by=0
but if x=2 and y=1 you can find a=1 and b=-2 for example
this means that 2 ~ 1 but not 0 ~ 1
pine star
and to check reflexivity, I would check if there is some a,b such that 2 ~ 2 ?
grave sluice
yes not only for 2 but for every real number
pine star
ok that makes a bit more sense
grave sluice
notice that if x and y are both not 0 you can always put a=y and b=-x
weary tiger
do cycles in graphs only exist when its a directed graph ?
faint narwhal
No
hoary igloo
Show that if G is simple, then e < v choose 2 where G is a graph e is an edge and v is a vertices
Im not going to lie its been over a year since I last did anything proof based and im struggling with this relatively simple problem
a graph is simple if there are no loops or multiple edges so it seems like then the number of edges would be equal to v - 1 otherwise youd get a loop? and the number of choices is obviously v!/ 2(v-2)!
but idk what to do from here
faint narwhal
If I give you 4 vertices labeled A,B,C,D what are the possible edges you can have?
hoary igloo
in a simple graph?
faint narwhal
Yeah
hoary igloo
{(A-B, B-C, C-D), (A-B, A-C, A-D)} my notation might be rough there because if you had a any other edge in the first tuple you would form a loop right
sorry super new to graph theory was doing some connectomics and realized I might have a bit of a deeper understanding if I was better at graph theory like as in new anything
oh shit
my definition of a loop is off
faint narwhal
Ah I think you've misunderstood the definition of a loop
hoary igloo
yea
faint narwhal
In this case, a loop means there's an edge from a vertex to itself
hoary igloo
ok yea so if we had 4 verticies we could have four edges
faint narwhal
Simple graphs still allow paths from a vertex to itself, called cycles
hoary igloo
A-B, B-C,C-D, A-D
"a graph is simple if there are no loops or multiple edges so it seems like then the number of edges would be at most to v"
hoary igloo
yep that would work shoot
faint narwhal
And there's one more as well
hoary igloo
is that ok for the proof? I feel like its sort of apparent right? that if you arent allowed to have multiple edges and loops(a edge to it self) the maximum number of edges you can have will be the number of pairs in the graph
i feel like thats just not idk? formal/rigorous?
faint narwhal
Yeah that's the right idea
pine star
this seems like an appropriate answer for 3b, not for 3a
seems like 3a should be [7]=7
stray reef
the kernel relation of f is the relation defined by xRy iff f(x)=f(y), yes? @pine star
gusty gale
stray reef
so if f is a constant then the kernel relation of f is the 'everything is related to everything' relation
hence there is only one equivalence class
pine star
hmm
weary tiger
which question??
cerulean wind
theyre getting help in another channel
weary tiger
oh ok
weary tiger
look at the second 'x'
it has no quantifier
theres an extra bracket in there
$\forall{y}(\exists{x}R(x,y)\land{S(x,y)})$
vital dewBOT
jswatj
pine star
so if f is a constant then the kernel relation of f is the 'everything is relate...
so is this because every combination of x and y makes the statement true?
stray reef
...that certainly is one way to word it i guess...
pine star
sorry this is brand new to me
edgy vine
I have a question about the complexity of sieve of eratosthenes.
weary tiger
Shoot
edgy vine
I thought I describe the complexity by the sum from prim to sqrn(n) multiplied by the sum from 2 to floor n/i. But I am not sure.
There is this proof that you can just check the sqrt(n) first numbers to find all primes from 2 to n. Thats the outter main loop.
The inner for loop just flags the multiples of primes from 2*i, ..., n/i * i to 0. They are marked as composite.
Also I do not know why one can just floor down there.
this would be my estimation for the complexity. by prim I mean all primes all the way to sqrt(n).
;_; now the hard part would be to describe the sums differently. All I know is the complexity is O(N log log N)
dense geyser
Also I do not know why one can just floor down there.
You can do the floor because (n/i)*i = n, so floor(n/i)*i < n, and the next integer multiple of i would be greater than n
The second loop at the end where you collect the primes is O(n), so I think we can agree that we can ignore that part, leaving the nested loop
Additionally, finding the next prime in the list is amortized O(n), e.g. you have to step forward n times in total, so on average we can consider that to be a constant
Thus, the complexity is basically the number of times that b_j <- 0 is run
So the first time the loop runs, with i=2, b_j <- 0 is done n/2 times; then n/3 times, then n/5, etc., where we sum over the inverses of the prime numbers
It's hard to show, but this sum (the inverse primes) converges to log log n
and since we have an n in the numerator, we end up with n log log n
@edgy vine
edgy vine
Ok, I will check the proof on that. But yes I thought I have to estimate the complexity to find the next prime by O(n). But that would be too harsh, also I dont know why we can assume it to be a constant here. If we take super large n (for what this algorith is not intended for), we would take bigger and bigger steps.
dense geyser
it takes bigger and bigger steps, yes, but it takes no more than N steps over the course of the entire algorithm
it's amortized constant time
austere swan
That's true for 3a, but not for 3b
pine star
hmmm
would it be infinitely many equivalence classes with a single natural number in each?
does that even make sense
edgy vine
@dense geyser thx. Where did you deal with this algorithm.
I do internship at my professor. He allowed me to choose a topic. I took primes and cryptography as topic 🦢so I firstly write about how primes are constructed, useful algebraic properties, and primtests like PRIME. And maybe discrete log stuff.. But I had neither discrete math nor number theory yet. I will have it next semester.
fierce osprey
I need a bit of help with this proof in problem 5…
Here’s what I’ve tried already, but the numbers aren’t working out
I’m getting fractions with primes on top instead of 1 
(As coefficients of 3^(n+1) - 2^(n+1))
dense geyser
Here’s what I’ve tried already, but the numbers aren’t working out
You have your terms flipped
You have 5G_{n-1} - 6G_n
fierce osprey
Ah charming
dense geyser
Took me 5 minutes to spot it, it happens lol
austere swan
would it be infinitely many equivalence classes with a single natural number in ...
Exactly
hazy bay
Proof by recursion.
You done the base case. Here is the continuation !
sharp turtle
can you use graph theory and MST algorithms in GPS?
MST=Minimum Spanning Tree; GPS=Global Positioning System
edgy vine
So the first time the loop runs, with `i=2`, b_j <- 0 is done n/2 times; then n/...
Isnt it n/i - 1 time, because we start with 2i, 3i, ...?
pine star
7b
No tree has fewer than zero leaves. Therefore, every descending chain of trees is finite if the order is by the number of leaves.
Does this sufficiently answer the question?
dense geyser
Isnt it n/i - 1 time, because we start with 2i, 3i, ...?
Maybe, but in big O notation it doesn't really make a difference
edgy vine
kk
lilac kestrel
<@&286206848099549185>
lilac kestrel
and yes, Player 2 only has the moves F,G,H,I, and K
and does not know the possible payoffs for Player 1
distant glade
i'm assuming the values at the bottom are (points for player 1, points for player 2)
wherethe more points the better
if so this looks like a mini-max problem
lilac kestrel
i'm assuming the values at the bottom are (points for player 1, points for playe...
yeah they are the payoff
s
then C is the best move, yes?
distant glade
it depends, do we want to minimize the payoff for player 2?
lilac kestrel
it depends, do we want to minimize the payoff for player 2?
does it matter?
either way doesn't C have the more beneficial expected payoff for Player 1?
and for worse gets only 1
had they chosen either C or D
distant glade
if we want to maximize both payoffs there’s better moves
it depends on what player 1 wants to do and what player 2 wants to do
lilac kestrel
well the question is for Player 1
best move for Player 1
and Player 2 is assumed to choose the move with maximum payoff for them
distant glade
alright so under the assumptions that we want to minimize the payoffs for player 2 and maximize those of player 1, C would be the best move
and there's also the assumption that player 2 will minimize the payoffs for player 1 and maximize his own payoffs
outer hinge
Can someone write “A = the set of all X values such that the square root of X is in the set of all integers” in latex ? I’m starting off with set builder notation and want to see if I’m reading it correctly
I don’t know how to use latex
vital dewBOT
Ann
main marlin
struggling with a pretty basic combinatorics problem and hoping someone can push me in the right direction. i'm working with a tiled $1\times n$ strips covered in either squares or $1\times2$ dominoes. I'm trying to show that the number of tilings with $k$ dominoes is equal to $\begin{pmatrix}n-k\k\end{pmatrix}$ but i'm a bit stuck on how to do that. you could construct dominoes with by picking $n-2k$ squares, but i can't think about how those could be selected in such a way that you still get blocks of 2 tiles adjacent for the dominoes
vital dewBOT
panoramatopia
red nest
struggling with a pretty basic combinatorics problem and hoping someone can push...
Here is one way to think about this: So we need to choose k positions for the dominoes such that none of the dominoes over lap, once we’ve done that filling in the square can be done and can be done in only one possible way. Now think about selecting the k positions for the left tile of the domino. To ensure no overlaps, they have to be selected such that there is atleast one tile in between two selections and the rightmost selected tile can’t be the last tile. So to the right of every selected tile there is an unselected tile, if we delete that tile we are left with a selection of k tiles out of a total of n-k tiles. And for every selection of k tiles from n-k tiles, by adding a tile to the right of a selected tile we get a selection of k tiles from n tiles that satisfy the conditions we want. That’s why you get the answer as n-k choose k
main marlin
ohhhh i see
thank you! i was kind of thinking about how you could construct a tiling from a k choosing of n-k tiles but i wasn't going about it the right way
pine star
$5+9+11+...+(2n+3)=n^2+4n$
vital dewBOT
CreamyBoy
pine star
to prove the base case I do P(1), and it's true, but P(x), x>1, and it's a false statement
does that matter?
sour arrow
You're saying that P(2) is false
Yeah, that matters. That's a counter-example. The statement isn't true.
pine star
Gotcha, seems obvious just wanted to be sure
I think it's a typo
should be a 7 in the series between 5 and 9
storm pollen
Hey guys I have a math question I just finished from an exam and I want to see if it’s right
pine star
having trouble reading this
lilac kestrel
and there's also the assumption that player 2 will minimize the payoffs for play...
no, like i said at the start, Player 2 does not know the possible payoffs for Player 1. lol.
cerulean wind
u have to make sure y is not zero
coral raven
'for all x there exists y such that: for all z, x - y = y + z'
distant glade
no, like i said at the start, Player 2 does not know the possible payoffs for Pl...
then what does he know?
is his move random?
there's basically no information to go off of
distant glade
E, D, and C are all equivalent from what you've told me
they all result in player 1 geting a payoff of 1
in fact option D is the best in this case
since there's a 50% chance we get 2 instead of 1
lilac kestrel
3,0 means Player 1 gets a payoff of 3 and Player 2 gets a payoff of 0?
distant glade
yeah they are the payoff
i thought so
lilac kestrel
Player 1 always gets a payoff of 1? why is that
the lower payoff for both C and D is 1
and C has a higher more beneficial payoff for Player 1 than D has
distant glade
ah but player 2 doesn't know, so C is best assuming the choice is random after C
lilac kestrel
but why D
distant glade
wdym
lilac kestrel
in fact option D is the best in this case
why D
distant glade
nono it's C like you said
lilac kestrel
ah ok
ty
i learned this just yesterday to help my friend lol
we all arrived at the same answer
kindred portal
can anybody help with this question?
faint narwhal
what have you tried? @kindred portal
faint narwhal
Maybe computing the first few terms would help in seeing how the pattern works
waxen nest
can i check if its correct for (a) use combination and for (b) can use either permutation or combination?
last timber
@waxen nest for first one yes it is combination
for second one
is 1asd the same as asd1?
waxen nest
ohh
snow sleet
so second one must be permutation?
Yes. Also, do you need help finding the answers to those problems? or do you got it?
waxen nest
so.. even if the qn is changed to with repetition allowed, it will still be permutation right?
waxen nest
Yes. Also, do you need help finding the answers to those problems? or do you got...
yes i need help
snow sleet
okay i can help
snow sleet
so.. even if the qn is changed to with repetition allowed, it will still be perm...
yes, but it would be permutation with repeats allowed
so let's do part a first @waxen nest
What answer do you have for part a?
waxen nest
What answer do you have for part a?
idk but im guess its 4C11?
snow sleet
yes
waxen nest
ohh the first number always have to be bigger?
snow sleet
not necessarily bigger, should be at least the second number...otherwise nCk is 0
so nCk is for when k is an integer 0<=k<=n.
if k<0 or k>n, then nCk=0
make sense?
are you ready for part b @waxen nest ?
waxen nest
alright'
snow sleet
okay cool so notice that we need cases for part b right?
cuz the number of letters and numbers can vary in the 4-character sequence
we could have all numbers
all letters
or some numbers and some letters
waxen nest
oh yes
snow sleet
we could have all numbers
^
waxen nest
yea 3 cases
snow sleet
well the last case entails some subcases....but for now, let's calculate them all at once
are you familiar with summation notation?
and then I'll show you a much faster way that doesn't involve any casework
you there? @waxen nest
waxen nest
are you familiar with summation notation?
okay
snow sleet
is that a yes or no?
waxen nest
yes
waxen nest
is this under discrete math or probability statistic?
snow sleet
this counts as discrete math too as well as stats
waxen nest
ohh
snow sleet
so what can you tell me about that sum
waxen nest
yes
snow sleet
I'm choosing i distinct numbers to be in my sequence and 4-i distinct letters to fill the remaining spots in the sequence
waxen nest
yes
vital dewBOT
logician
snow sleet
once made my selections, I must arrange those things I've selected in 4! ways
since the sequence is of length 4 and all of the entries in the sequence are distinct. Then I sum over all relevant i values. So from i=0 to 4
does that make sense?
snow sleet
uh what?
this is the answer to part b
there's more to my answer than just permutations, I've also used combinations too
would you like to see a much shorter route to the answer to this problem? @waxen nest
waxen nest
yes
snow sleet
okay
so let's notice that we have 26+10=36 objects to choose 4 from. These 4 that we've chosen will be in our sequence. Then we arrange those 4 things in 4! ways
so the answer is $\binom{36}{4}4!=36\cdot35\cdot34\cdot33=^{36}P_4$.
vital dewBOT
logician
snow sleet
**logician**
this is the final answer^
snow sleet
,w 36\cdot35\cdot34\cdot33
vital dewBOT
snow sleet
,w Sum[4!Binomial[26,i]Binomial[10,4-i], {i,0,4}]
vital dewBOT
snow sleet
notice that those are equal^
that is no coincidence that they are equal
@waxen nest do I have to keep pinging you? because you kinda just disappear without saying anything beforehand about your disappearance lol
snow sleet
okay
snow sleet
this one^ is better for that
waxen nest
**logician**
so i show it like this?
snow sleet
well you show it like $^{36}P_4=36\cdot35\cdot34\cdot33$
vital dewBOT
logician
snow sleet
the other thing I had in that equation originally was just to show you what that also equals
waxen nest
ok got it thanks
subtle charm
hi, im trying to prove that ((p Vq) ^ ~p ) -> q is a tautology.
I tried applying implication laws followed by De morgan's law, then double negation law and De Morgan's law again
I ended up with ~p ^ ~q V p V q so am kinda stuck.
cerulean wind
do you mean (~p ^ ~q) v (p v q)?
sour arrow
I ended up with ~p ^ ~q V p V q so am kinda stuck.
You need brackets somewhere to make sense of this line
subtle charm
hold on let me type out my approach.
sour arrow
You do indeed mean
(~p ^ ~q) v p v q
Consider the distributive property to move forward
subtle charm
2. ~((pVq) ^ ~p ) V q # Implication Laws
3. ~(p V q) V ~(~p) V q # DeMorgan Law
4. ~(p Vq) V p V q # Double Negative Law
5. ~p ^ ~q V p V q # De Morgan's law```You could do this by making use of the fact that a->b is equivalent to ~a v b. Of course, De Morgan's law will also be required for this approach
subtle charm
Do I have to keep a bracket after performing De Morgan law?
sour arrow
So when using Demorgan, don't drop the brackets, unless you can without losing the meaning
Dropping them in 3 is okay, because V is associative there's no mistaking that line
But when you put V and ^ beside eachother it isn't clear which to do first
subtle charm
uhm could you explain a little more on when I can drop the brackets?
sour arrow
For example
a ^ b v c makes no sense
subtle charm
yeah its ambiguous
waxen nest
why not draw a truth table to prove
sour arrow
But a v b v c makes perfect sense
subtle charm
why not draw a truth table to prove
I am not allowed to use a truth table
subtle charm
But a v b v c makes perfect sense
so if the resulting proposition that I am writing is ambiguous, then it would be more meaningful to keep the brackets?
sour arrow
Basically you can't drop the brackets if you'll be mixing v and ^
sour arrow
so if the resulting proposition that I am writing is ambiguous, then it would be...
Yeah this exactly
subtle charm
Ok, thanks a lot!
sudden bridge
Can someone help me with these 3 pls, I have vague answers for the first 2 but I need help on all 3
sour arrow
Let x be an element in A' \ B'
Show that it is also in A \ B
Then,
Let x be an element in A \ B
Show that it is also in A' \ B'
subtle charm
@sour arrow Would it be more proper for me keep the brackets regardless since im new to this? (sorry for the intrusion)
snow sleet
For problem 1, if you know $A\setminus B=A\cap B^c$ for sets $A$ and $B$, then you can give a super quick proof for problem 1.
snow sleet
Can someone help me with these 3 pls, I have vague answers for the first 2 but I...
see below
vital dewBOT
logician
snow sleet
of course, I'm talking about A and B as subsets of U a universal set
sudden bridge
For problem 1, if you know $A\setminus B=A\cap B^c$ for sets $A$ and $B$, then y...
Yea the formula makes sense but I don’t know how to give a proof
sudden bridge
Let x be an element in A' \ B'
Show that it is also in A \ B
Then,
Let x be an ...
I’m not sure how to go about doing it this way
sour arrow
Let x be an element in A' \ B'
That means it is in A' but not in B'
That means it is not in A, but must be in B
Whoa, it's in B \ A
snow sleet
Yea the formula makes sense but I don’t know how to give a proof
to prove the equation I mentioned, (it's pretty much straight forward use of the definition of setminus and intersection), but proofwise, you'd have to show that $x\in A\setminus B$ if and only if $x\in A\cap B^c$
vital dewBOT
logician
snow sleet
anyway, I'm off to bed lmao...it's only 1:28am here lol. It sounds like @sour arrow has got ya covered on this.
sudden bridge
@snow sleet lmao ty
sour arrow
I like logician's more haha. I'm going with the noob proof
sudden bridge
Let x be an element in A' \ B'
That means it is in A' but not in B'
That means i...
Ok yea it makes sense, I’ll try doing it this way and let you know
@sour arrow omg ty that worked that easily in my head and makes way more sense now
But I’m still stuck on 2 and 3, I am soo lost
subtle charm
4. (~p ^ ~q) V p V q
5. [ (~p ^ ~q) V p] V q
6. [ (p V ~p) ^ (p V ~q)] V q # Distributive Law
7. True ^ p V ~q V q # Negation law
8. True ^ p V True # Negation law
9. True ^ True # p V True equivalant (3 lines) to True ```does this makes sense lol
sour arrow
It's easy to get counter examples. Mess with really simple examples to get an idea.
For example, what if X is a subset of Y, and f is the identity function?
cerulean wind
```
4. (~p ^ ~q) V p V q
5. [ (~p ^ ~q) V p] V q
6. [ (p V ~p) ^ (p V ~q)] V q ...
just do (~p ^ ~ q) = ~ (p v q)
sour arrow
just do (~p ^ ~ q) = ~ (p v q)
Oh LOL I didn't see that
cerulean wind
lol
sour arrow
``` 1. ((pVq) ^ ~p ) -> q
2. ~((pVq) ^ ~p ) V q # Implication Laws
3. ~(...
You even have it in your proof:
~(p v q) v (p v q)
Which looks a lot like:
~x v x
sour arrow
Note 7 needs brackets to make sense
subtle charm
oh yeah so I have to do the distributive law again right
just realize that I am wrong for point 7 onwards
sour arrow
You could let True get eaten:
True ^ q = q
Then you don't have the bracket problem anymore
Then you have p V ~q V q which is True
But yeah go with c squared's, much faster
cerulean wind
just realize that I am wrong for point 7 onwards
from ~x v x u can infer true 
cerulean wind
Can someone help me with these 3 pls, I have vague answers for the first 2 but I...
2 is kinda fun to try and cook up examples for
sudden bridge
2 is kinda fun to try and cook up examples for
Wdym fun I’m soo confused
cerulean wind
lol. super simple one. take X = {1} and Y = {1,2}
just mess around for a bit with that
sudden bridge
Ok I’ll do that and let u know how it works
sudden bridge
lol. super simple one. take X = {1} and Y = {1,2}
G wouldn’t be a function then so I’m not sure I understand
cerulean wind
you have to make the functions
sudden bridge
you have to make the functions
No what I mean is in your example, say f(1) mapped to 1 then G(Y) wouldn’t be a function right?
Since 2 isn’t mapped to anything
subtle charm
2. ~((p->q) ^ p) V q # Implication law
3. ~(p -> q) V ~p V q) # De Morgan Law
4. ~(~p V q) V ~p V q # Implication Law
4.1 ~(~p V q) V (~pVq)
5. True # Negation Law ```Can someone help me check if this is right?
Not sure if I am allowed to perform implication law on step 4 given that there is a negation sign outside..
I assume I can do so since the -> is within the brackets?
cerulean wind
No what I mean is in your example, say f(1) mapped to 1 then G(Y) wouldn’t be a ...
what about g(1) = g(2) = 1
sudden bridge
Oh, yea ok
weary tiger
I assume I can do so since the -> is within the brackets?
You can do that
That looks right to me
The last line has the form of a tautology
pine star
can someone point me to a good explanation of what's going on here? my book does not explain this well
weary tiger
Yeah
weary tiger
Assuming of course n is non-negative
pine star
n is of N
weary tiger
Yea im dumb
pine star
lol nah
gleaming dune
do i need 3 base cases for part b and then start to do the proof by supposing there's an integer k that's >=4?
spark gale
if you consider how many numbers you need to "solve" the first unknown number, this should give you an intuition of how many base cases you need
given you only go so far back as a_{k-2} to solve a_k you only need two other numbers from the sequence
gleaming dune
so since the next unknown number is 4, i would need a2 and a3 to solve it
which means the base cases would be k = 2 and k = 3?
spark gale
for an induction proof you need to seperate pieces
I know they always teach it as dominos but I think it gives the wrong image
you need the piece to knock down the dominos
and you need the base of dominos to start on
so here you really only need a_1 and a_2
gleaming dune
ok so if i understand this correctly
if we can prove for n=3 using base case of n=1 and n=2 then it should domino to n+1
is that what you're saying?
spark gale
This is the tutorial materials I made for the discrete math class I was a TA for last year
not sure it'll help or not.
base case is seperate
it stands on it's own
you can prove the inductive step first and give the basis step afterwards
and your proof still holds
gleaming dune
the inductive step here would be to let k be an integer > 3 and suppose that a_n holds and to try and prove a_k holds as well?
spark gale
prove that a_{k+1} holds yes
k would be an integer >= 3
just careful to include the equals there
otherwise your induction won't actually "latch onto" the basis
spark gale
well you could do that. But then you need to include k=3 as a part of your basis
it's obviously cleaner to only have the minimal base cases, and then go from exactly the next case up
gleaming dune
ok so if i understood correctly, if i use base case of n = 1 and n= 2, then k should be >=3
but if i used n =1, n=2, and n=3, then k > 3
spark gale
we just use k as the constant taking place of n
gleaming dune
yeah
spark gale
which is just mathematicians being sticklers, not always easy to appreciate till more complex problems 😛
gleaming dune
alright im going to attempt 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?
gleaming dune
wait, in the question they already give a_1 and a_2
spark gale
yes, they need to
gleaming dune
so my base case is a_3 and a_4 then?
spark gale
for this particular type of question
uhhmmm
having a blank, lol one sec
okay ya you're proving for k>= 3
so your base is k=3 k=4
ya
sorry my bad
the proof is for the first line of your question
gleaming dune
ok so now my base case will be using n (or k whatever u call it) = 3 and = 4, then my Inductive step will STILL BE K >= 3?
spark gale
before a)
I believe you could still stick with that yes
though I'm thinking it might be better to start with k>=5
sorry I've been doing calculus all day and I'm foggy on my discrete stuff now
gleaming dune
haha no worries
spark gale
uh ya I'd stick with k>= 3
both are rigorous I believe. so it likely shouldn't matter
I'm realizing there's a link and my e-mail on the resource I sent you. If you share it I'd ask that you just block those out for me 😛
gleaming dune
absolutely, no worries
Is what I have so far correct?
sorry for the bad writing lol
Z is supposed to be the set of integers
spark gale
the bound on m is a bit off
it could be from 3 <= m <= k
because you aren't asked to prove for k=1
or k =2
gleaming dune
oh yeah it should be 3 thats my bad
gleaming dune
oh niceee
for a question like this do u need to choose and make up a function f and g to show its an equivalence relation?
just assigning what f(1) and f(2) etc.. would be
weary tiger
I dont think you would need to
spark gale
no making up a function will limit you to one example
weary tiger
^
spark gale
which is only good for a counterexample
weary tiger
The 3 parts should be pretty straightforward to prove
gleaming dune
yeah that's true i dont think u could come up with an example to show all 3 at once
spark gale
go through all the properties of an equivalence relation and try to prove them one by one
weary tiger
^
spark gale
keep f and g general throughout
gleaming dune
the thing is im not even sure how to start on this, like how do i show fRf if i dont know what f is
spark gale
and you'll need an h(1) + h(2) at some point too 😉
gleaming dune
yeah for transitivity
spark gale
the thing is im not even sure how to start on this, like how do i show fRf if i ...
this is the easiest one and I'll give it to you
$$f(1) + f(2) = f(1) + f(2)$$
done
vital dewBOT
Dawson
spark gale
yup
gleaming dune
LOOOOL
spark gale
that's equality through and through
weary tiger
similarly $f(1)+f(2)=g(1)+g(2) \implies g(1)+g(2)=f(1)+f(2)$
vital dewBOT
jswatj
weary tiger
obviously
spark gale
this question is more asking if you know the properties of equivalence
so just review those and this question basically will answer itself
cerulean wind
so then symmetry would be f(1)+f(2) = g(1)+g(2) = g(1)+g(2) = f(1)+f(2)
it should be if fRg, then gRf
gleaming dune
f(1)+f(2)= g(1)+g(2) then g(1)+g(2) = h(1)+h(2) implies f(1)+f(2)=h(1)+h(2)
for transitivity
weary tiger
yes
gleaming dune
ah ok
spark gale
it should be if fRg, then gRf
and conversely
honestly these questions annoy me because you aren't really doing anything
cerulean wind
and conversely
it suffices to only show one way
spark gale
I wish they'd find other ways to test you on those kinds of things
spark gale
it suffices to only show one way
right I guess if you're considering they're general functions already
spark gale
yep I think you're right
just had to look up the definition again 😛
damn I'm definitely rusty
can't believe I was teaching this stuff last year
cerulean wind
lol
gleaming dune
now
cerulean wind
weary tiger
😳
spark gale
👀
gleaming dune
if i want to show how many equivalence classes there are for the relation R on f, how would you calculate that because you don't know what the values are supposed to be
would i take the approach and assume f(1)+f(2) is odd or even
cerulean wind
the values of the functions are irrelevant
gleaming dune
and go from there
gleaming dune
the values of the functions are irrelevant
oh sheeesh
so then what am i supposed to use to find how many classes there would be haha
would it just be 2^3?
because n-1
spark gale
Think a little bigger
gleaming dune
i wish my brain was a bit bigger hahaha
let me think for a sec
i want to say 2 but that's not based on anything except there being two functions
is that correct?
spark gale
well you have your set A
and ANY function from A to A
start making some functions
it's a bit of a combinatorial problem
for example f(1)=1, f(1)=2, f(1)=3 ...
gleaming dune
if there's no restriction on one-to-one then it should just be 4x4x4x4 right
4 slots and 4 choices (1,2,3,4) for each
spark gale
but you're only considering the classes for f(1) + f(2)
gleaming dune
@spark gale am i on the right path
spark gale
<@!407546452315996160> am i on the right path
oh sorry I went to eat. Did you settle on 4^4/2?
I actually don't know the answer exactly but I wouldn't just guess at something unless you knew where each count was coming from
for the left side I get f(1) has 4 choices and f(2) has 4 choices
so 4*4 seems about right there. once the left side is chosen, how many ways can you choose the right side so that f(1) + f(2) = g(1) + g(2)?
spark gale
what have you tried?
pine star
I'm trying to understand counting certain operations in a for/while loop. I just can't wrap my head around it and my textbook isn't helping me
if somebody could point me toward a good resource for understanding this, I'd be super appreciative
first how to construct a summation expression and then how to interpret that into a formula as the problem poses
gleaming dune
so 4*4 seems about right there. once the left side is chosen, how many ways can ...
is this correct?
spark gale
Check your 6,7,8
gleaming dune
oh i just noticed lol
spark gale
:P
spark gale
Ye
spark gale
Good. It should seem weird
Lol you're missing the permutations from the left side
the ones that are of the form (a,a) shouldn't be counted twice
But those of the form (a,b) can be counted with (b,a)
My combinatorics knowledge isn't super strong. Sorry I cant guide better than this.
I'm sure there's a counting pattern at work here I just can't seem to find it properly