I listed it
#discrete-math
high ermine
weary tiger
i meant ann
sorry
idk
i'm just confused as to how the summation formula (i don't need it) is related to the problem, how i need to set the proof up for submission, and what i need to find the sum of (other than just the divisors, broadly speaking)
high ermine
We are using this formula while summing part of divisors
$1+2+4+ \dots +2^{s-1}=2^{s}-1$
vital dewBOT
LearTsura
high ermine
not yet, we need to sum all the divisors and get 2* 2^{s-1}*(2^{s}-1)
and that means 2^{s-1}*(2^{s}-1) is a perfect number
and from here we are very close
weary tiger
i lost my 4.0 GPA to discrete math. fuck discrete math worst class ive ever taken in my life
weary tiger
i lost my 4.0 GPA to discrete math. fuck discrete math worst class ive ever take...
i lost my 4.0 to calc 2 bc i decided to do everything but listen to the lectures for my second exam
ended with an 87 and got a 76 on the second exam 
would’ve gotten at least a 91 otherwise
idle cave
weary tiger
why is this statement true? Z^2 ∩ Z^3 = ∅
i dont understand why both these cartesian products contain an empty set
obtuse lance
they don't contain an empty set, that would be {{}}
weary tiger
they don't contain an empty set, that would be {{}}
in order for this to be true, doesnt it mean the intersection is an empty set?
haughty garden
No it just means they don’t have any elements in common
weary tiger
No it just means they don’t have any elements in common
ok that means sense
cuz one has (, ,) and the other is (,)
haughty garden
$\emptyset \neq {\emptyset}$
vital dewBOT
opengangs
weary tiger
thanks!
mint bane
can you have a graph with all even degrees but no euler circuit?
olive hamlet
nope, graphs with all even degrees always have an eulerian circuit(and vice versa, its an iff)
mint bane
lol my textbook gave it to us as an if but negations didnt add up
merci
in a similar vein: can you have an euler trail that doesnt have every vertex
pale epoch
isolated vertices
weary tiger
can you have a graph with all even degrees but no euler circuit?
if the graph isn't connected then yes
simply look at how the proof of euler's theorem goes: using the fact that all vertices have even degree allows to partition the graph into edge disjoint tours. Using connectedness, we can combine these tours to get an euler tour
For example every 2k-regular graph is a collection of edge (in fact vertex) disjoint cycles. Take k=1 and n=6, there are 2 2-regular graphs on 6 vertices up to isomorphism one of them is just the cycle of length 6 and the other is composed of 2 cycles of length 3. The latter doesn't form an Euler circuit since you can't join the two tours.
mint bane
i shouldve come up with that lmao, still, ty guys
mint bane
can someone help me break down combinatorics please
like when to use products, choose, permutations, and so on
weary tiger
If a relation R is defined on Z by R(a,b) if a^2 = b^2 (mod 5), then what are the distinct equivalence classes?
For example, a^2 - 0^2 = a^2 = 5k
So what is the equivalence class of [0]?
Is it just 5k, k in Z?
unreal stump
If a^2-b^2=0 mod 5 then either a+b=5k or a-b=5k
unreal stump
Is it just 5k, k in Z?
Yes
weary tiger
Is that an inclusive or?
unreal stump
Yes
weary tiger
Okay, and for example for 2, we would have a^2 - 2^2 = a^2 - 4 = 5k, so (a - 2)(a + 2) = 5k, which means a - 2 = 5k or a + 2 = 5k
unreal stump
Yes
weary tiger
So 5k ± 2
unreal stump
You have 3 equivalence classes
weary tiger
[0], [1], and [2]?
unreal stump
Yes
weary tiger
How do we prove there aren't any others?
unreal stump
A number is of form 5k,5k+1,5k-1,5k+2 or 5k-2
Numbers of form 5k will be in [0]
Numbers of form 5k+1,5k-1 will be in [1]
unreal stump
np
native sandal
Could someone help me with this pelase?
errant bear
no
mental wigeon
Hello intelligent people! Could I get some assistance with this problem? My group partner and I are just kind of banging our heads against it and we don't know what to do.
errant bear
do you think it is valid or not, for starters
mental wigeon
We are assuming it is not valid.
mental wigeon
That is kind of why we came here. Because we don't know 😅 We are assuming that S is not prime, but we're not sure where that error is.
errant bear
do you have any issues with the first two lines
mental wigeon
Should we? tbh we honestly have no idea. Do you see any issues with it that we should take issue with?
stoic mountain
Hello intelligent people! Could I get some assistance with this problem? My grou...
Do you assume it is invalid or do you think it's invalid
Just to be sure where exactly the problem lies
mental wigeon
Could you differenciate assume and think? I'm fairly certain they are synonyms
stoic mountain
The difference I'm thinking of is if you assume that it is wrong, you're saying, before understanding the proof, that it is false.
If you think it's wrong, then you have tried to understand the proof and from your own logical conclusions it has to be wrong.
Anyways, what I really want to know is why you assume it is wrong
there is certainly a step you're not sure of
mental wigeon
Ah. let me clarify. We think that It is wrong, because this is a math project and We highly doubt that we would only have to circle "No". So that is why we think that it has errors
stoic mountain
Alright, the only thing I can think of that seems to be problematic is that in the first sentence there is no clarification why p is element in {p1,...,pn}. It may very well be that p1*p2....pn + 1 has no divisor in {p1,...,pn}
per construction it doesn't, actually
The rest is sound and makes sense, but this one is fishy
Did that help @mental wigeon
mental wigeon
Okay thanks
meager prairie
this is more a probability question i think
mint bane
this is more a probability question i think
combinatorics ¯_(ツ)_/¯
weary tiger
combinatorics is taught in discrete as well
meager prairie
fair
meager prairie
idk combinatorics so im trying to figure it out from scratch
mint bane
a is P(26,8) that's easy
weary tiger
can someone help me with finding an average?
The average height of the eight shorts was 150 centimeters. The average height of the twelve mediums was 170 centimeters, and the average height of the five talls was 200 centimeters. What was the overall average of all 25?
mint bane
link pls?
meager prairie
mint bane
unrelated but can you have a graph whose vertex connectivity is 1 and edge connectivity is 2?
i feel like no but idk reasoning
wait yes u can oopsie
meager prairie
combination i think but youre talking to probably the least knowledgeable person here about combinatorics
oh im just dumb
yea dont mind me at all
combination since order doesnt matter on C
can you just find like
how many ways are there to place 2 a's and 2 b's in 8 spots
mint bane
8^2 right
meager prairie
meager prairie
im so scared i have a 300 level course on this next semester
meager prairie
idk youre asking me like i know the answer 
meager prairie
yea
so should be 28 ways
just for the a's
so could you do like
8C2*6C2
honestly just brainstorming since idk shit
thatd give 420
do you have the answer?
guess what 😄
420 is right
8 choose 2 times 6 choose 2
mint bane
for only a's and b's right
meager prairie
well theres 8 choose 2 ways to arrange the a's
then since 2 spots are taken
6 choose 2 ways to arrange b's
then theres only one way to arrange the c's
since you have 4 c's and 8 spots
but 4 spots are taken up
by two a's and two b's
and its a combination so order of the c's doesnt matter
theres only 4 positions for 4 c's to go in at that point
or at each point i guess
mint bane
like
meager prairie
one to one has a pretty straightforward process to it
mint bane
i know the process but can and asymptotic function be 1-1
meager prairie
mint bane
no wait im p sure it is 1-1
mint bane
ok then e is the last thing fucking me
meager prairie
since that element is also missing from the codomain i guess is my smol brain way of justifying it
you can just google this
transitivity of a union of transitive relations
weary tiger
anyone here good at discrete math
errant bear
no :(
meager prairie
no one is good at discrete math in da whole world
weary tiger
well does anyone know discrete math
meager prairie
whole crane
<:JustAsk:371662163489718273>
Man I'm stealing this emote
safe canopy
Maybe its still lacking?
pale epoch
this is fine
safe canopy
Is it only injective tho? Is it not surjective aswell?
pale epoch
ok, why?
safe canopy
we solve for y=f(x)
and can then show that x is in Z
pale epoch
what is x?
safe canopy
x = y+7
pale epoch
yes, that works
alternatively notice that g(x) = x+7 is the inverse of that function and hence it is bijective
pale epoch
yw
weary tiger
Result: Every symmetric and transitive relation on a nonempty set is an equivalence relation.
Proof: Let R be a symmetric and transitive relation defined on a nonempty set A. We need only to show that R is reflexive. Let x in A. We show that R(x,x). Let y in A such that R(x,y). Since R is symmetric, R(y,x). Now R(x,y) and R(y,x). Since R is transitive, R(x,x). Thus, R is reflexive.
Each step in this proof makes sense to me. Why is it wrong?
unreal stump
You are assuming there is a y such that R(x,y) is true
unreal stump
<@!734020733595942952> How can it not?
Consider A={1,2,3}
R={(1,2),(2,1),(1,1)}
last timber
and as Ann pointed out assumption that A is nonempty is not sufficient
empty relation is vacuously transitive and reflexive
@weary tiger what you want to add to your statement is:
R is nonempty and for each x its image under R is nonempty
then it becomes true
stray reef
so what?
so what if A's nonempty? you're trying to pick an element from {y ∈ A | R(x,y)}
which, yeah, might be empty
weary tiger
@stray reef Then my proof would work?
last timber
as it is your proof fails
stray reef
if you added vimes' somewhat technically heavy condition then yes that'd plug up the hole in your proof
where'd you get that result from anyway
last timber
that makes sense
so @weary tiger the error was that
the conditions for transitivity/symmetry can be satisfied vacuously
but for reflexivity - no
(except prolly case with empty set)
weary tiger
I see alright
stray reef
I was supposed to find the mistake
make this clear next time you post such a problem
mint shore
does anyone know how to use wolfram or other software to get the sequence out of a generating function?
just the solution
no answers at the end of the book moment
unreal stump
What kind of gen function
As in is it an ordinary gen function or an exponential gen function or smt else
mint shore
sec
stray reef
you probably want the Taylor series
mint shore
you probably want the Taylor series
i'll try that ty
unreal stump
Do a partial fraction decomposition
And then expand 1/x-alpha
There's actually an algorithm for this
Let's F=a_0+a_1x+a_2x^2...
Then a_n=(D^nF)(0)/n!
Where D^nF is nth derivative of F
You could write a python program to do this(calling wolfram to compute the derivative)
unreal stump
You could say gcd(n,(5n^2+8))=gcd(n,8)
weary tiger
how would that be written to solve for the gcd?
n = 8(??) + ??
n > 8 and 4 does not divide n
somber anvil
weary tiger
Why do you think its 11
lol
why does everyone respond with non-answers 
Are you asking why people don't solve shit for you?
Are you asking why people don't solve shit for you?
no, it’s just that he explicitly asked whether it was correct or not
he didn’t ask for an answer lol
i don’t expect anyone to solve anything for me
i just find “why do you think ___?” is redundant and unhelpful
Why?
Lmao
Youre so wrong
stfu
blocked idc
<@&268886789983436800>
^ toxic
ember obsidian
👢
quaint star
Lol what
mint bane
quaint star
Did you kick Ledog?
mint bane
it seems so
ember obsidian
banned
quaint star
But why?😂
stray reef
are you forced to indicate edges as {A,B} as opposed to AB?
mint bane
yeah just silly in-class notation stuff
stray reef
a and b look correct
idr prim's algorithm so can't say anything about c
is prim's the one that attempts to add arcs to a forest starting with the smallest weight arcs until everything joins up into a tree?
mint bane
idk exactly what you mean by adding arcs but sounds like the gist of it
stray reef
marking them as being part of the tree
mint bane
oh then yeah
mint bane
i understand it as finding a MST by always picking the edge with smallest weight as long as it doesnt lead to a visited vertex
quaint star
The only named algorithm i remember is dijkstra
mint bane
okok looking gucci
oh ew
i know d is right
confident in f
and e
c and a are what im unsure about
stray reef
c isnt a simple graph
weary tiger
Let S be a nonempty collection of nonempty sets. A relation R is defined on S by R(A,B) if there exists a bijective function from A to B. Then R is an equivalence relation.
What are the equivalence classes of [A]?
Or of R?
gritty crescent
R is the relation itself, it would not have an equivalence class here.
As far as [A] goes
It's a matter of definition itself-all sets which are in the collection and in bijection with A
(these are exactly the sets which have same cardinality as A)
weary tiger
I see
gritty crescent
Have you verified/proved that R is an equivalence relation, though?
weary tiger
That's given
gritty crescent
Ah, okay.
errant bear
it cant br R->Z
errant bear
fundamental thm of arithmetic
idk what you are asking
oh, well 1^x=1^y
so its not unique
the 3 naturals that you pick must be coprime
like, 2^2 * 3^3 * 6^1 = 2^1 * 3^2 * 6^2
order doesnt matter
i could pick like
49, 8, 81
as my 3 numbers
they are coprime
mm
i mean it makes sense after you understand whats going on
like, its an extension of how, say 2^n will never equal 3^m
and fta guarantees uniqueness
well, when you are dealing with composite numbers, say in our example of Z^3 -> Z
lets say we pick 2 primes and a composite, x, with 2 prime factors u and v (6 for example)
we have p^a * q^b * x^c
= p^a * q^b * u^d * v^e
and since p,q,u,v are prime
this is really just solving the Z^4 -> Z case
yea, but that doesn't rly matter for my demonstration
so it turns out we dont care about composites as long as they are coprime
weary tiger
Does a code being optimal mean that it minimises expected codeword length across all decipherable codes for some probability distribution?
errant bear
i wouldnt think so. ~~also my book doesnt mention it so 
~~
weary tiger
I'm a bit confused though because I don't think we ever got told the definition of an optimal code
but we got told that the Huffman code is optimal
but in this question it asks to define optimal
errant bear
optimal code is one such that the size is maximized
(without breaking the given dimensions of n, d)
one sec
it could be defined slightly diff for your book/class idk
but yeah im p sure it doesnt minimize
it could, but not always
weary tiger
im kinda confused though
don't you need all codewords to be the same length
to define it like this
weary tiger
but it says in the Q
and also in my notes it says huffman is optimal but huffman isnt a block code
but it doesnt define optimal lmao
weird
oh nvm i found the definition
im blind
errant bear
do they just mean like, most efficient
weary tiger
it says 'A code $f:\Sigma_1 \to \Sigma_2^*$ is optimal if it has the shortest possible expected word length among decipherable codes.'
vital dewBOT
same
errant bear
mm ok
yea this just wants u to do huffman
idk, we just used "most efficient" in place of your "optimal"
weary tiger
Let S be a collection of n ≥ 2 numerically equivalent sets. Prove that these sets can be shown to be numerically equivalent by means of n − 1 bijective functions between pairs of sets in S.
I do not understand what this question is asking. Are we allowed to assume that they're numerically equivalent, but we also have to show that they are?
west hedge
Let's say n=4 and S = {A,B,C,D}.
Then it's just asking you to verify that in order to show that all sets in S have the same size (which means that A~B, A~C, A~D, B~C, B~D, C~D) you can instead just check A~B, B~C, C~D.
weary tiger
I see.
Thanks.
@west hedge Actually, why is the first one so "long"?
I don't see why we have to do A ~ B, A ~ C, A ~ D and then B ~ C
We can just do it like you wrote in the latter example: A ~ B, B ~ C, C ~ D
west hedge
Yeah it seems obvious, but the point is that when people say that a collection of sets all have the same size, what they really mean is that any two of them have the same size, since bijections only go between two sets at a time
So it's technically a statement involving n^2 bijections (I already cut out some of the obvious ones when I wrote those six in the example)
The problem just wants you to show why it's so obvious that you only need to check A~B~C~D
For example, to show that B~D you can combine B~C and C~D (using the fact that ~ is transitive)
Another example, to show that B~A you can use A~B and the fact that ~ is symmetric
weary tiger
Right, but if A and B have the same size, then so does A and C if B and C have the same size
So why are you checking A and C anyway?
west hedge
That's exactly what the problem is saying
gritty crescent
They suggested checking A~B, B~C, C~D. The remainder cases are taken care of by the fact that bijections here form an equivalence relation on this collection of sets(throwback to your problem from yesterday).
gritty crescent
A~C is guaranteed when you check A~B and B~C by transitivity. A~D by transitivity on A~C and C~D, etc.
weary tiger
@gritty crescent But why do we have to check every possibility?
As you said, we get A ~ C when we check A ~ B and B ~ C
weary tiger
No?
weary tiger
Let's say `n=4` and `S = {A,B,C,D}`.
Then it's just asking you to verify that in...
I don't understand this part
(which means that A~B, A~C, A~D, B~C, B~D, C~D)
We don't need to do all of that
west hedge
We don't need to do all of that
Like I said, this is what the problem wants you to show
west hedge
This is the problem:
Let S = {A,B,C,D}. Assume A~B, B~C, C~D. Prove that for any X and Y in S we have X~Y.
You keep asking "why do we need to check all the possibilities?". The answer is because the problem told you to.
weary tiger
@west hedge I don't see how that's the case.
When two sets are numerically equivalent, then |A| = |B| = n for positive integer n (assuming nonempty)
We get that X ~ Y automatically.
west hedge
X~Y means that there is a bijection f : X -> Y
west hedge
When two sets are numerically equivalent, then |A| = |B| = n for positive intege...
This is not true since the sets may not be finite
weary tiger
No
Numerically equivalent means they are finite
Not that they have the same cardinality
west hedge
It doesn't really make a difference, the proof will have the same structure
You just have to use the properties of an equivalence relation (either bijection or equality)
weary tiger
But you argued against that |A| = |B| = n in case they are infinite
But that's not the case here
They are not denumerable sets
That have the same cardinality
west hedge
In one case you use the existence of a bijection f : X -> Y and in the other you use equality |X| = |Y|
Both of these relations have the same properties reflexivity, symmetry, transitivity
So the proof is the same either way
weary tiger
Let A and B be denumerable subsets of R^+. Define C = {x in R | -x in B}. Show that A U C is denumerable.
As A, B are denumerable, we can suppose that A = {a1,a2,...} and B = {b1,b2,...}. It is therefore that C = {-b1, -b2, ...}
So A U C = {a1,-b1,a2,-b2,...}
We can define f(x) = a_i if i is even, and f(x) = -b_i if i is odd
Do I need to worry about ai = -bi?
west hedge
Your problem makes it so that you don't have to worry about that by saying that A and B are subsets of R^+ (I'm assuming this means positive real numbers)
So everything in A is positive and everything in C is negative, you never double count
Not that double counting would matter anyway
west hedge
Yeah that's good
Oh actually I guess the indices are a bit off
Or well actually the whole f(x) = a_i thing itself
Without looking too closely I assumed you wrote f(i) = a_i but what you really wrote doesn't quite make sense, what is x?
west hedge
Yeah so if you do that then you still need to adjust it a bit
Since f(i) = a_i for i even and f(i) = -b_i for i odd skips over half of A and half of C
west hedge
Oh actually I guess the indices are a bit off
This is what I was originally going to point out when I said this
weary tiger
Oh wait you are right
We can define A = {a1,a3,a5,...} and B = {b2,b4,b6,...} to get rid of that problem
west hedge
Yeah that's fine
weary tiger
Instead of using N to list them
west hedge
You could also define f(2i) = a_i and f(2i+1) = -b_i but what you did works too
weary tiger
Yeah
I want to show that |Z| = |Z - {2}|
Can I define f : Z -> Z - {2} such that f(i) = i if i ≤ 1
Otherwise, f(i) = i + 1?
west hedge
Yeah that's good
weary tiger
Do I need to show that f(i) = i + 1 is bijective, for i ≥ 2?
(Because f(i) = i is the identity function and is clearly bijective)
weary tiger
Yeah, f^(-1)(i) = i - 1
For i ≥ 3
Anyway, assume f(a) = f(b), so a - 1 = b - 1, and so a = b, which means it is one to one
Then clearly i - 1 reaches all integers from 2 onward, when i ≥ 3
weary tiger
There are N black and white checkers in a circle boundary... A move consists of placing a white checker in between every pair of checker of the same colour and a black checkers between every pair of checker of opposite colour and then the original(previously placed) checkers are removed..
This is done repeatedly..
How do we prove if N=2^n the. All the checkers will be eventually white
.......
Any ideas on how to approach this would be much appreciated.
pale epoch
i cba to think about this in depth but have you tried induction
weary tiger
Hmm yes...
But is there something I might have missed
So can u just outline what the process would be...
I tried taking 2 and it's true
Then assumed for 2^k
Tried proving 2^k+1
This is what u mean right..?
pale epoch
yes
you can also think of it another way
try to reduce the case of 2^(k+1) to the case 2^k
weary tiger
try to reduce the case of 2^(k+1) to the case 2^k
Hmmm 🤔
pale epoch
maybe there are some simple moves that you can perform to make the case smaller
or somehow consider one half different than the other
since obviously the case 2^(k+1) has twice as many checkers as the case 2^k
marble pivot
if I have a function $$f:\bN \hookrightarrow \bN \to X$$ could it look like this
vital dewBOT
abs_0
vital dewBOT
Lagrange the Multifarious
deft current
yes
marble pivot
Yes
Can an injection just like, skip terms in the codomain
Even if the domain and the codomain are the same set
pale epoch
are you asking if f: A -> A injective implies f surjective?
if A is finite, then yes
otherwise no
so in your case, the answer is yes it could look "like this"
marble pivot
are you asking if f: A -> A injective implies f surjective?
Yeah that’s a better way of saying it
marble pivot
if A is finite, then yes
otherwise no
Ok that’s interesting
Why is that?
Does it follow directly from the definition of injective
signal meadow
Can someone help with with my hw assignment?
pale epoch
Does it follow directly from the definition of injective
more or less, i think it's worthwhile to think about this
minor lake
so I'm currently messing with some combinatorics
none of you is probably going to understand what I'm trying to say because I'm very unclear
but does anyone have a trick for distinguishing counting in the two following fashion
1) _ x _ x _ x _ x
2) _ X _ X _ X _ X _
i know that it might not make sense but please lmk if you have an idea about what I'm talking about for those who can relate
oh yea also each underscore obviously represent some sort of possibility
stray reef
makes no sense at all
minor lake
I knew it
I need to find a concrete example
dang I just don't know how to say it even doe those are two completely different examples
stray reef
still no clue what you're talking about
minor lake
😂
i'll probably just right away ask a direct question regarding a problem in this case to see what's wrong instead, might be clearer
(nevermind just got it, big dumb am I)
marble pivot
more or less, i think it's worthwhile to think about this
I tried proving it
Feel like I screwed something up tho cause that’s really simple
minor lake
uh
isn't it
because the image = codomain
perhaps typo
oh nevermind misread, a -> a
so a would be both codomain/domain/image
pale epoch
you should probably use the fact that f is injective
stray reef
what's "it"
are you asking for example of a function from A to A which is inj but not surj (or vice versa)?
marble pivot
what's "it"
f
marble pivot
are you asking for example of a function from A to A which is inj but not surj (...
Yeah, cause my intuition is sort of failing for how that proof doesn’t extend to an infinite set A
marble pivot
Gimme a sec lol
Ok no proof
Just this question
Why doesn’t that proof work for an infinite set A?
stray reef
i don't get what you are even trying to prove
rn it reads as "Every function from A to itself is surjective" which is clearly false
marble pivot
I tried proving it
Ok is this proof correct
stray reef
rn it reads as "Every function from A to itself is surjective" which is clearly ...
refer to this again
stray reef
so you are trying to prove
marble pivot
Is that wrong
coral raven
yes
marble pivot
No
stray reef
then WHAT are you trying to prove
marble pivot
At this point I’m not trying to prove anything
stray reef
AAAAAA
marble pivot
I’m just trying to understand why that above proof doesn’t work for infinite set A
stray reef
what's it a proof of??????
coral raven
consider the set A = {0, 1}
consider the function f: A -> A such that f(x) = 0 for all x in A
then f is clearly not surjective
so not all functions from a set to itself are surjective
stray reef
ok yknow what im gonna go to sleep
marble pivot
Ok I’m stupid
stray reef
bc im clearly not going to get anything out of yelling
marble pivot
Nvm nvm
OH man I am
That
I’m actually stupid
Is it true that for a finite set A, if f:A to A is injective then it must be surjective as well?
coral raven
yes
marble pivot
it's not true for an infinite set because (+1): N -> N exists
Ahhh
minor lake
nvm it's good I was just typing the wrong shit on my calculator
actually I'm not even sure about my own reasoning so I'll repost it
how many anagrams can be made up with the word "CHATONS" if there are no repetitions, starts by a consonant and ends by a vowel
at first I got $\binom{5}{1} \cdot (1 \cdot 4 \cdot 5!) \cdot \binom{1}{1}$
vital dewBOT
Chad
minor lake
the result was off by an half so I guess I just need to divide by 2 but I'm not sure to understand
in fact I get 2400 instead of 1200
$\binom{5}{1}$ for the consonant at the start, 1 for a vowel, 4 for the remaining consonants, 5 for the order of that group (basically 1 + 4) and $\binom{1}{1}$ for the remaining vowel at the end
vital dewBOT
Chad
keen girder
Isn't this just 5 * 5! * 2?
keen girder
you have two vowels, which means you have two ways to place vowel in the last position, then you have all 5 distinct consonants, so you have 5 ways to place them in the start, and you have remaining (7-1-1)! choices to place in the middle
minor lake
geez 🤯
that looks so much simpler
i always get dumb stuff when i deal with that kind of stuff
ty
keen girder
you're welcome.
minor lake
geez, there's really something with my way of thinking about problems involving combinatorics
I had another issue but I solved this one as you did
same problem, anagram of the word "CHATONS", still no repetitions, except that this time vowels have to be consecutive
this time, I first did, $\binom{6}{1} \times 2 \times \binom{5}{1} \times 5!$ instead of $\binom{6}{1} \times 2 \times 5!$
vital dewBOT
Chad
marble pivot
Vowels are consecutive? That’s interesting
minor lake
I often tend to think about positions then available (actually remaining) choices and multiply them together
marble pivot
Just think of the vowels together as one unit
And then you’ve got 6 objects to arrange
And then multiply by 2 at the end for switching the vowels (we need to count AB and BA)
minor lake
And then you’ve got 6 objects to arrange
5 if I were to consider the two vowels as one unit actually
marble pivot
Oh
minor lake
my issue wasn't really the vowels, but the remaining part
marble pivot
Isn’t it (C)(H)(AO)(T)(N)(S)?
minor lake
yes
marble pivot
That’s 6 objects
minor lake
oh ok, I thought you meant objects to arrange after I place the vowel
my issue is not the vowel
minor lake
in both attempts I got the part regarding the vowel well
marble pivot
Are you doing like
Fix a vowel somewhere, then see the number of arrangements for the rest?
minor lake
yeah that's what I did
marble pivot
Yeah that works
minor lake
but for some reason in my brain
I thought this way
(there are 5 remaining positions, and I have 5 consonants, so for whatever reason multiply them together)
instead of just doing 5! for the remaining spots I did 5! x 5
marble pivot
Why 5!*5?
minor lake
that's the thing I have no idea
marble pivot
Because for each letter there’s 5! ways so multiply by 5?
minor lake
maybe that's due to the fact that I tend to separate "position" and "available objects"
and for some reason I just do a product of these, I have no idea
marble pivot
Do you know why we use factorial
marble pivot
Nah nah
minor lake
after 4, 3, 2 and it goes on
marble pivot
I’m talking just in general
Do you know why there are 5! ways to arrange 5 objects?
minor lake
P(n,n) ?...
minor lake
?
it's only meant to work in a context
I don't see the general meaning of it working
marble pivot
Yeah, there are n! ways to arrange n things
Do you know where that formula comes from
minor lake
pi?....
minor lake
recurrences?
marble pivot
What
minor lake
with an initial condition that 0! = 1
marble pivot
No
minor lake
which implies it to have a degree of 1
then I don't know what you're talking about
also unfortunately my exam is tomorrow and I have 5 other chapters to review
minor lake
I recommend you get a foundational understanding of counting
to be frank, not the best time to read about that
marble pivot
I know it sounds like a lot
But if you don’t do it
You’ll never really understand what you’re doing
minor lake
are you referring to generating functions
minor lake
then what's your understanding of factorial in simple elementary terms in about a few sentences/word
minor lake
I don't really see how that really helps at all unfortunately I'm sorry
quaint star
I believe all abs is trying to say is that. If you are sorting 5 things, there are 5 positions you will place the things in. There are 5 things to go in the first position, then 4 things left to go in the second, ..., then 1 thing left to go in the last spot. So there are 5*4*3*2*1 ways to arrange 5 things. And that's just 5!. In general, there are n! ways to arrange n things.
pale epoch
how does it guarantee that?
rain stone
Any graph with no edges is trivially bipartite no?
Yeah, I think they are just repeating for emphasis?
weary tiger
|A| = 3 so P(A) has 2^3 = 8 elements
There are 3C1 subsets of size 1, 3C2 subsets of size 2 and 3C3 subsets of size 3
Now figure them out
burnt frost
wait so i write whats in each subset?
upbeat olive
I need help with these 3 questions if anyone was willing to lend me a hand 😅
keen girder
exam
upbeat olive
past paper im tryna finish for my exam tomoroow but cant for the life of me to finish them
keen girder
do you have link?
upbeat olive
link to the paper?
keen girder
yes
upbeat olive
its on my uni server so snipping tooled xD
keen girder
I don't know what that is but I don't feel comfortable helping on exam papers, unless I know for sure it is from the past...
keen girder
most likely an ongoing exam since they haven't provided any proof of it being a past exam....
graceful elm
can anyone help me translate this into english? ∀x∀y [(P (x) ^ ~P (y))→ (~P(x+y))]. where P(x) = x is even, P(y)= y is odd
unreal stump
You can't make one predicate mean 2 things at the same time
unreal stump
What does p(x+y) mean
unreal stump
P means one thing and one thing only
graceful elm
yeah thats what i was confused by
wait doesnt it mean P(even+odd)
so like
odd
P(odd)
idk
im speaking out of my arse here but adding an even number with an odd number makes an odd number
i think
halcyon kraken
stray reef
careful with your choice of variables.
as is you are only considering an even and odd number which are adjacent to one another
mint shore
fair point
stray reef
you will want another letter
mint shore
even + odd = 2n + 2m + 1
= 2(n + m) + 1
well this isn't really going anywhere
or actually
would 2(n+m) + 1 count as an odd number?
thorn flicker
yes
that is basically an integer times two plus 1
which is odd
because n +m is an integer if n and m are integers
mint shore
im speaking out of my arse here but adding an even number with an odd number mak...
just proved it
in case you're curious
thorn flicker
can someone explain the answers for these 3 questions
actually i understand 6B, not 6a or 6c tho
quaint star
Yeah, it's the positive rational numbers
So you are taking the integers and removing the positive rational numbers
All positive integers are also positive rational numbers, so you have to remove them
Then you are just left with 0 and the negative integers
mint shore
I forgot what Q is
then why not look it up
thorn flicker
sorry didnt feel like it lol
thorn flicker
are you offended i didnt search it up lol
quaint star
They didn't ask what the size of A is, but the size of the power set of A
@thorn flicker we are not here to act as google
Make sure you understand all the terms in your question and if you still can't do it, then ask. We don't want to waste time helping you if you could have done it youtself.
thorn flicker
okie dokie
errant bear
artichokie
stray reef
would `2(n+m) + 1` count as an odd number?
why on earth would 2*(an integer) + 1 ever not be odd
mint shore
dunno
anyways, small thing
i'm working on some solved examples of generating functions and i just want to make sure i'm reading this right
find sequence with generating function A(X) = that
shouldn't a_1 be 9?
and not 7
stray reef
tfw no gf 
errant bear
just consider the prime factorization of some arbitrary natural
obtuse minnow
what class is this for?
"Show that 2n + 1 covers every odd number possible."
This question asks a similar question about functions.
In the given function ... f: N x N -> N
The question about onto is the same as saying:
"Show that f(m, n) can cover every possible N."
tardy mica
What's the answer for - if i have n types of car and we have k money
I car cost 1 money. And we want k cars how many different combination will be made assuming we have infinite car of every type
stray reef
f: N x N -> N
i'm assuming 0 ∉ N in your class?
anyway, what sideurk said. prove that every natural number can be factored into the product of a power of 2 and a number not divisible by 2 (ie odd)
(hint: it amounts to 'divide your number by 2 as many times as possible')
stray reef
ok
weary tiger
Okay
So let 2^k be largest power of 2 that divides into a natural number l
Then the other number is in the set 1,3,5,... which can be written as 2o-1 for some o in N
So we get 2^k * (2o - 1)
This is not f(m,n)
weary tiger
Oh right
Because k can be 0, we need 2^(k-1)
I see thanks
Is standard the way you prove (0,1) is uncountable using decimal expansion?
stray reef
yes, cantor's diagonal argument
weary tiger
I have a theorem that states if A is uncountable and B subset A, then B is uncountable
And we've proven that (0,1) is uncountable
But I can't use this to say that R is uncountable, right?
past gate
Guys,I have this weird combinatorics problem wich I am stuck on.
Can anyone help me?
6 people need to be picked up by three uber drivers,at the same time,from one place to another,and thereby every uber car needs to have at least one person.How many different ways are there for the transport to be implemented?
haughty garden
If we place one person in every car, then I think we can reduce this problem into an easier problem without the restriction of having at least one person in each car
past gate
I don't even know how to approach this,lol.
haughty garden
My thought process is this: start by fixing one person in each car. We can do this in P(6, 3) ways. Then, because each car has at least one person in the car, we have already satisfied the required condition. So the other three people can freely choose among the three cars. This gives us P(6, 3) * C(3, 1)^3
Numerically that gets us 3240 ways
past gate
By P and C you assume Permutations and Combinations,right?
past gate
Cuz we use a little different terminology at my uni.
Can anyone confirm @haughty garden solution?
haughty garden
Do you have answers for it or nah
past gate
No,sadly 😦
haughty garden
ah rip
I’ll probably get better at combinatorics after I take a combinatorics class next year
But yeah your best bet is to try and draw up a picture and play around with it until you can find a pattern
past gate
I suppose.
Can you tell me why did you raise the whole equation to the power of 3?
P(6, 3) * C(3, 1)^3
haughty garden
Each person that’s free to choose a car has 3 or C(3, 1) options
past gate
Ah right so if we take 3 from the group of 6
We are left with 3,each individually free to choose from C(3,1) options right?
haughty garden
Yep
We pick 3 out of 6 as fixed people inside a specific car
The remaining people are free to do what they want
We ensure that each car must contain at least 1 person
weary tiger
```6 people need to be picked up by three uber drivers,at the same time,from one...
What's the answer btw?
haughty garden
Oh jks I think my solution might overcount some cases
3^6 < 3240 which is already sus to me
So instead, you might want to compute 3^6 - 3(#ways to get 0 people in one car) + C(3, 2) * (#ways to get 0 people in two cars)
past gate
Damn that escalated quickly lol
haughty garden
#ways to get 0 people in one car reduces down to just 6 people choosing from 2 cars which is 2^6, #ways to get 0 people in two cars reduces down to just 6 people choosing from 1 car which is 1.
So we have 3^6 - C(3, 1) * 2^6 + C(3, 2) * 1 = 3^6 - 3 * 2^6 + 3 = 540
I think this makes more sense actually
past gate
I think it would not matter if 3^6 < 3240
haughty garden
hm what makes you say that
3^6 is the total number of arrangements without any restrictions
past gate
Yeah
haughty garden
There are some fairly strict restrictions here so you would need to omit some of the cases from the total
so you should (theoretically) have less arrangements than if there were no restrictions
haughty garden
I think 540 is right
ok yep, I just googled a similar problem and it seems like 540 is right
past gate
The thing is that I don't get it lol,it seems way too overcomplicated..
Why would they throw in something like this..
haughty garden
it's a fairly tricky problem when you haven't seen the trick yet
but it's just an application of the inclusion-exclusion principle
halcyon kraken
yea its kinda hard to account for at least 1 person in each car but once you figure out that you can fix 1 person in each car it becoems way eaier
then u have 3 ppl left
and they can go to whatever car
so its like 3^3
haughty garden
alternatively, a tweak to my original solution works because I realised it should be C(6, 3) and not P(6, 3)
the reason why P(6, 3) didn't work was because I assumed that picking people had a fixed ordering when in reality, it doesn't matter where each of the original three people went
so these three people could have swapped among themselves and we still would have had the same arrangement
Once you fix these three people in each of the cars, then everyone else is free to move around as they please
So we have C(6, 3) * 3^3 = 540
^We assume the cars are indistinguishable and that we only care about how the people are arranged, not people AND cars
weary tiger
hello everyone, is there anyone able to help me in a discrete math 1 final? i could really use some help
weary tiger
i just need help in Sets and Functions
weary tiger
you could just say what u need help on
i meant like helping me during the exam n stuff
urban saddle
I dont think thats allowed here bro
halcyon kraken
i meant like helping me during the exam n stuff
bro wtf
dont cheat
!!
holy shit this isnt a math cheating server
weary tiger
no no no i didn't mean by cheating
weary tiger
it's just like i got screwed up by my doctor
and didn't understand the material
which i already told him
haughty garden
if there are general concept questions you want to ask (not related to the exam), I'm sure there are people who will be happy to assist
past gate
@haughty garden thanks a lot man! appreciate it! 🙂
Thank you all that helped me as well! 🙂
haughty garden
no worries! I'm glad my 1:30am brain could be of use 😄
urban saddle
how can you compute the number of Hamiltonian cycles in a Kn graph?
wikipedia says its (1-n)!/2 but i have no clue how to get there
urban saddle
yep
past gate
(1-n)! ? <:thonk:406575732563902485>
he probably means that,else for every n>1,we'd get a factoriel of a negative number.
stray reef
okay
urban saddle
What I get is that for every cycle generated by a vertex, you can get a reverse one, but it doesnt count, so thats the reason you divide by 2?
stray reef
well a hamiltonian cycle in K_n is just a permutation of the numbers from 1 to n
except they're equivalent under cyclic shift and reversal
the division by 2 accounts for the equivalence under reversal
urban saddle
well a hamiltonian cycle in K_n is just a permutation of the numbers from 1 to n
and isnt that just n!?
stray reef
yes
urban saddle
where does the -1 comes from then
stray reef
except they're equivalent under cyclic shift and reversal
but you need to account for this
any cycle generates n cyclic shifts including itself
hence you divide by n
n!/n = (n-1)!
urban saddle
any cycle generates n cyclic shifts including itself
with that you mean that each cycle generates the same cycle but in reverse order? eg 123 and 321?
stray reef
no, that's not what i'm talking about
i'm talking about cyclic shifts
like 12345 -> 23451, 34512, 45123, 51234
urban saddle
so each cycle starting in each vertex would generate those cycles, and since they are the same for each vertex thats why you divide by n right?
okay no, this have no sense
urban saddle
like 12345 -> 23451, 34512, 45123, 51234
all of these are unique right? why would they be equivalent
if any of those are generated by starting in a fixed vertex
rancid rune
vital dewBOT
Ann
past gate
I don't think you can conclude that,as much as I've learned about graphs: A complete bipartite graph Kmn is defined with two subsets V1 and V2 of the set of vertices V that don't have an intercept: V1 with size m and V2 with size n.
Although you can conclude the total amount of edges wich is:
m * n
Am i right @stray reef ?
quaint star
I don't understand your explanation of K_(mn). It is the graph with two groups of vertices, one with m and one with n vertices. Each vertex in the one group has an edge to all the vertices in the other group.
So yeah, there are m*n edges
past gate
That's what I am saying,but @rancid rune here is asking if m*n is always an even number, wich I cannot conclude.Also I don't know what he means by "circuit",theres a term called "cycle" but haven't heard of circuit.
quaint star
No, it's not always even
If m and n are both odd, then it's odd
Oh
Nvm
A circuit is a closed trail. So a cycle that can repeat vertices.
past gate
Ah,yeah that's a matter of terminlogy I guess.
At my uni we basically say "a path"
Not sure if I should say at my uni or in my uni lol 🙂
quaint star
Anyway, yeah, since it's closed the number of edges must be even since you must always go the other group and then back.
past gate
This bothers me a little.
Let's assume we have K2,1
It's supposed to look something like this,right?
Then what about K3,1
3 edges, odd number.
Am I wrong?
quaint star
They didn't say the number of edges in the graph but the number of edges in each circuit
So every circuit has an even number of edges
past gate
Ah I get it now.
I remember the formula was something like:
n(n-1)
Wich is always even.
quaint star
The formula for what?
past gate
The graph Kn,assuming n vertices.
n vertices,and each one is connected to the others (n-1) vertices.
And the total degree(edges) of all the vertices is equal to n(n-1)=2e.
Or
.```Sure, yeah, but that's not the same as their question
quaint star
Take an arbitrary circuit in a complete bipartite graph, then the circuit must consist of an even number of edges.
past gate
Oh right,I think I get it now.
Something like this,right?
That +1 step for coming to the first position always makes it an even number.
exotic ivy
So Im taking this discrete math and probability course as a pre-college summer program... but lately my parents and the internet are saying discrete math is really hard. But all I just see is boolean algebra and induction, which I feel like if you just study them and practice should do fine. And I also do know that this is one of the first major "real" math where you solve proofs and theorem. So is it really hard? Is calculus required? (the course listed did not say calculus is required or even mentioned anywhere in its short decription) What specific topics you guys find relatively hard to learn?
haughty garden
imo, discrete math is a different type of math from what you may have experienced in high school. While high school focuses on algebra and calculus (maybe even stats), discrete math focuses more on logic, proofs, sets, elementary number theory, basic combinatorics/enumeration, and graph theory. So it may just take a bit longer to wrap your head around these fairly new concepts
But with anything, if you put in the work, you'll generally be okay
calculus and algebra ideas may be used in a few questions but you generally won't be needing fully developed calculus concepts to do well in the course
exotic ivy
I see thanks for the insight!
haughty garden
no worries! 😄
urban saddle
is it possible to draw a 4 vertex graph that is eulerian but not hamiltonian? been at it for a while and can't find one
nvm just found one
past gate
Guys I need help again
I need to check wich of the following graphs are isomorphic.
Can anyone tell me how do I do it?
gritty crescent
Recall what it means for two graphs to be isomorphic.
gritty crescent
Sure. What do you understand from this definition?
past gate
Well first we have to ask ourselves if the number of vertices are the same I guess.
gritty crescent
Correct.