discrete-math

[elder berry]

but yeah

[regal gate]

what is the intuition of the magnification ratio

the im(X,Y) thing seems a natural thing to look at, but the magnification ratio idk

then the main theorem is

which sounds plausible at least, but Im more interested in the definitions

[meager prawn]

can't help motivate a definition I've never seen, sorry

[abstract valve]

wassup yall....im new to the server but discrete math is very cool !!!!!!!!!

[quick tusk]

Does the toient function always produce an even number

[obtuse lance]

almost

1 and 2

[quick tusk]

NO

Dammit

[obtuse lance]

lol

[quick tusk]

I got that wrong in the exam lol

[obtuse lance]

rip

[quick tusk]

I didnt think of those cases

I just did a bunch of trial and error and notice it was all even

[obtuse lance]

do you have any formulas for it that you learned or

for instance $$\varphi(n)=n\prod_p 1-\frac 1 p$$ is one way, that product goes over each distinct prime factor p of n

[vital dew]

Merosity

[obtuse lance]

from that you can work out exactly when it'll be odd

[quick tusk]

I argued that every number has a prime factorisation like n = p1 * p2 * … * pn. So phi(n) = (p1-1)*(p2-1)…. And that had to be even

Ok i will take note of this

[obtuse lance]

ah, that formula is not quite right, yeah I guess the main thing is forgetting not all prime numbers are odd though... 😛

[quick tusk]

Yeah i just gave a very rough argument because it wasnt a proof kind of question but brief explanation

[obtuse lance]

to write it how you did you could do something like $$\varphi(n)=\prod_p p^{e_p}-p^{e_p-1}$$ which will look like what you put when the powers are all $e_p=1$

[vital dew]

Merosity

[quick tusk]

Ty for clarifying and although i got it wrong, i understand it now

[obtuse lance]

you're welcome

[stoic wing]

how beginner to learn discrete-math?

[brave rock]

read book 👍

[weary tiger]

I have read but I don't understand the hint to the (creative) problem 33 "design an algorithm to determine whether a digraph has a unique topological ordering" on this page: https://algs4.cs.princeton.edu/42digraph/ Please help me.

"Hint: a digraph has a unique topological ordering if and only if there is a directed edge between each pair of consecutive vertices in the topological order (i.e., the digraph has a Hamiltonian path). If the digraph has multiple topological orderings, then a second topological order can be obtained by swapping a pair of consecutive vertices."

Question: What's the implication relation between (A) "the digraph has a unique topological ordering" and (B) "the digraph has a Hamiltonian path"? => or <= or <=> ?

[rugged valley]

is there a proper mathematical name for this type of 1xn tabular shape?
like in general

[river imp]

hey

for a relation

thats trans and symm but not reflexive does this work

xRy iff xy>0

[faint sphinx]

Sure, so long as you take it on some subset of real numbers that includes 0 🙃

[west night]

Hello, could you please help me with the following demonstration?

[little prism]

p is not an element of (Z/pZ)*

[deft vigil]

I spent about half a day thinking what this "following Corollary 4.3.2 means" part from my textbook to no real progress, but I have no idea why the number of edges in K_n being equal to (n choose 2) is related to the fact that "the number of vertices of odd degree in a graph is even".

I initially thought they meant that the number of edges of complete graphs with vertices having odd degree must be even, but this is clearly false since (6 choose 2) = 15 (deg(v) = 15 for each vertex, but |E(K_n)| is odd).

The only other possible thing I could think of is that they're saying in a complete graph such as K_4 or K_6, there are an even number of vertices with odd degree, and zero vertices of even degree, but I can't think of what this has to do with the number of edges

(Maybe it's a mistake in the book and I probably should not have obsessed over this, haha)

[faint sphinx]

in K6, deg(v) = 5 for each vertex, not 15 (not sure if that was a typo or not)

i don't immediately see how it relates to 4.3.2, but I imagine they meant the handshaking lemma instead

since sum(degrees) = n(n-1) clearly, so number of edges must be that divided by 2, which is exactly n choose 2

[stray aurora]

I don't understand anything

But it looks damn cool

[deft vigil]

Thanks ryx they must have meant handshaking lemma instead

[deft vigil]

BTW how did you know n(n-1)/2 is n choose 2 exactly? I know this is correct since I just worked out the formula, but it seemed obvious to you in a way it wasn't obvious to me... maybe it's just my lack of experience 🥲

[faint sphinx]

Oh that one shows up frequently

Like if course there's a formula that is helpful to know generally

But n choose 2 is pretty common, you memorize it quickly enough 🙃

(and ofc I've taken a class on intro graph theory before)

[somber heath]

how do I show that $$\sum_{n = \on{max}\set{ a,b}}^{a+b} \frac{(-1)^{n+1}}n {n \choose b}{b \choose n - a}$$ is zero for non-zero a, b

[faint sphinx]

I'd rather not

[somber heath]

for context

it's for this #real-complex-analysis message

[elder berry]

So this is probably not the type of sol. you are looking for, but I assume one could prove that with a bijection. Firstly rewrite as
[\sum_{k=\max {0, b-a}}^{b} \frac{(-1)^k}{b} \binom{a+k-1}{b-1} \binom{b}{k} = 0]
which removes the $n$ from the denominator, so you may as well multiply the above equation by $b$. It is enough to show that
[\sum_{k=\max {0, b-a}, k \text{ is odd}}^{b}\binom{a+k-1}{b-1} \binom{b}{k} = \sum_{k=\max {0, b-a}, k \text{ is even}}^{b} \binom{a+k-1}{b-1} \binom{b}{k}]
Interpret it as follows: Suppose there are two groups of people of size $a-1$ and $b$. You invite all the people from group $a-1$ to your show, and decide to invite only $k$ people from $b$ to the show in $\binom{b}{k}$ ways, enough so you can give $b-1$ awards to those invited. The number of ways to give out the awards is $\binom{a-1+k}{b-1}$. Now for any particular arrangement of these awards to the groups, one is primarily interested in how the awards are distributed to the group of people originating from the groups of size $b$. Fix an award arrangement where the group $b$ recieves $0 \leqslant m \leqslant b-1$ awards, and look at how many times that arrangements is counted in each case in the beginning summation. It ends up utilizing the well-known formula that
[(1-1)^n = \sum_{m=0}^n (-1)^n \binom{n}{m} = 0]

I think this works but am a bit tired to recheck, though if you want a better write-up of this I can write it more thoroughly upon request

[vital dew]

pseudo deus ex machina

[jolly ledge]

where's this cursed qn even from 😭

[faint sphinx]

p-adic logarithm properties

to show log(ab) = log(a) + log(b)

[jolly ledge]

😭 tf 😭

[chilly dew]

Bruh lmao you kept going

[chilly dew]

Nice to see there is a resolution

[deft vigil]

Trying to prove no pair of these 3 graphs is isomorphic. I spent a few hours today coming up with a proof but unexpectedly, it's not as easy as proving that there is an isomomorphism (where we can just find a bijection...)

Here is my proof so far, but really I'm pretty sure it's not rigorous enough. Is there some standard technique that I don't know in order to prove this? Actually, in the textbook, cycles are not introduced yet so I think I wasn't supposed to use them LOL

Proof:
For all of G1, G2, G3, we label the outer pentagon vertices from 1 to 5 in clockwise order, starting from the uppermost vertex. For the inner shape of all of G1, G2, G3, disregarding edges, we label them from a to e, also in clockwise order. Note that each inner shape of G1, G2 and G3 forms a cycle of 5 vertices when we disregard all edges connecting inner shape to the outer pentagon.

G1 and G2 are not isomorphic: Note that if we traverse the inner cycle of G1 from the uppermost inner vertex clockwise, we get the sequence a,b,c,d,e. Doing the same for G2 yields a,c,e,b,d. Observe that for G1, each of a,b,c,d,e is adjacent, in order, to 1,2,3,4,5 of the outer cycle. However, for G2, each of a,c,e,b,d is adjacent, in order, to 1,3,5,2,4. Since the two cycles correspond to different inner-outer pairs, no isomorphism exists between G1 and G2.

G1 and G3 are not isomorphic: Similar to above case...

G2 and G3 are not isomorphic: Similar to above two cases...

(and my labelling of the inner vertices also I've never seen in any kind of textbook where we just remove the edges, maybe also I'm missing a standard technique...?)

Maybe it's not clear but I meant to label them all in this fashion:

[light raven]

One standard approach to showing non-isomorphism between discrete structures is to compute invariants. For graphs you have things like the number of vertices, number of cycles of a certain size, etc. are all preserved under isomorphism, so finding any difference indicates that isomorphism is impossible. Finding the right invariant is generally an art form but there's always going to be something. Even for graphs it can be way more abstract like which spaces they can be embedded into isometrically if the edges are given length. I think you have a generally correct approach.

For example G1 has five different cycles of length 4 it seems, while G2 has none. G3 has two. So the invariant "number of 4-cycles" distinguishes all three graphs even though there may be other graphs with the same number of 4-cycles.

[deft vigil]

Oh I totally didn't see this. I was only focused on the outer and inner 5-cycles

Hmm, thanks I see so that's how you prove non-isomorphism!

I don't even know what spaces are though haha! 🙃

[light raven]

Looking for subgraphs is a good way to find invariants. Maybe something more abstract but intuitive not using "spaces" would be symmetry. G1 has some rotational and reflective symmetry that the others don't have. Computing graph symmetries can be difficult, but it is essentially looking for permutations of the vertices which are self-isomorphisms. Group theory can be used to actually do these kinds of computations. I am positive G1 has 20 symmetries and G3 has only 2, and G2 I'm having trouble counting but I think at least 30.

[deft vigil]

Maybe its still a bit too advanced for me, what comes to mind when I think reflective symmetry for example might be putting the X axis underneath all 3 graphs and reflecting horizontally to the negative X axis, but they're all equally symmetric in that case...?

Maybe putting different axes of reflection near each of them in different positions (top, bottom left, etc) and seeing where the symmetry breaks would be good... hmmm

Thanks anyway!

[plucky wedge]

is anyone able to explain this to me

It's not making any sense to me, I don't understand what they are trying to say

[brave rock]

Point out the specific part that you don't understand

[plucky wedge]

the first paragraph, I don't get what they are trying to teach me, are they trying to tell me how I can figure out bitwise OR, bitwise And etc. by myself?

[brave rock]

They are describing exactly what those operations are in the first paragraph

[teal sparrow]

I need help with 4.

I don't understand what B2 means

[rigid oriole]

the subsets of A of size 2

[nova wing]

knights and knaves problem. i know the answer is A is a knave and B is a knight, but don’t know how to set up the truth tables to show why that is the case.

[ivory badge]

no context given

but presumably, the knave lies?

[jolly ledge]

yeah

[hollow token]

What does this mean

[little prism]

it means what it says. it would be more helpful if you say what exactly you dont understand

[alpine hull]

What is a good way to visualise mobius inversion of functions on partially ordered sets?

[brave rock]

Man I wish I knew. But I do have a couple of related things that might help

1. The inclusion-exclusion principle is a specific case of Moebius inversion (I forget the derivation) on the inclusion ordering of sets. Since every poset can be seen as a poset of sets, you could think of this as the generic case.

2. If we choose a refinement of the partial order to a total order, the formula for the Moebius function is the same as the formula for the inverse of an upper triangular matrix with indices given by that total order.

I'm not aware of any good visualisations. I know there are some related things to do with order complexes but I'm afraid I don't know the details.

[proud needle]

hey everyone, does anyone know what exactly “splitting” a digraph is?

so if we have a digraph we split it into two groups

[peak jay]

anyone got a good soruce to learn combinatorics?

[magic parcel]

This might sound really dumb, i feel like i have a good grasp on basic set theory, but this one i just cant wrap my head around, why is it that the intersection betwerrn the set of A and powerset of A is an empty set? Say if A={1,2,3}, then the powerset P(A) = {{}, 1, 2, 3, 12, 23, 13, 123}, wouldent the intersection then be both {1,2,3} and {}?

[proud needle]

no because the power set is the set of all subsets

like P(A) ={{},{1}, etc…

{1} ≠ 1

[magic parcel]

so even though the subset of {1,2,3} in P(A) is the same as A, because it is a subset its not equal?

[brave rock]

{1,2,3} is not a subset of P(A)

it is an element of P(A) though

[vestal bronze]

{1} is not an element of {1,2}, 1 is element of {1,2}

1 is not a subset of {1,2}, {1} is a subset of {1,2}

[magic parcel]

Ok so it's the notation that's got me thinking wrong then, it does make sense

[quiet tendon]

A and B play a “match” consisting of a series of “games”. Every game simply exists
from tossing a coin with a chance of 2/3 heads (A wins) and 1/3 tails (B wins). The
match continues until A or B has won a total of 3 games. Calculate the probability that A is the
match wins.
Hint: The total number of games is between 3 and 5.

answer: 64/81

but for some reason i am not getting the answer

[quiet tendon]

how I thought it was let's say ur example P(A) should be {{}, {1},{2}, {3}, ... } so when u talk about P(A) u get an extra {} and that's why the intersection between these 2 is empty or not possible I am not sure either so don't take my word for it

[faint sphinx]

Doesn't need to be empty. Consider A = {0, {0}}. Then A \cap PA = {{0}}

But in this case it is

[quiet tendon]

so the intersection between A and P(A) is non empty here right? it's {0}

[faint sphinx]

It's {{0}}, since {0} is in both A and PA

[quiet tendon]

ooh wait ye

[quiet tendon]

do u by any chance understand this one

[faint sphinx]

What's the chance that A wins within the first 3 matches (i.e., three times in a row)?
Then, what's the chance that B wins one of the first 3 matches, but A wins the rest?
Then, what's the chance that B wins 2 of the first 4 matches, but A wins the rest?
Something along those lines is what I would try, I don't do much probability tho

[quiet tendon]

ye I had the same idea so basically what I did is

the chance that A wins
in 3 matches is 2/3 * 2/3 * 2/3
in 4 matches I thought it was 4 * 1/3 * 2/3 * 2/3 * 2/3
in 5 matches it was 10 * 1/3 * 1/3 * 2/3 * 2/3 * 2/3
but I made an error somewhere

because this is even greater then 1

[faint sphinx]

Note what I said tho. B has to win one of the first 3 matches, otherwise A won the first 3 and so the game is over

Same with the next one: 2 of the first 4, not 5

[quiet tendon]

ooohhh

[quiet tendon]

this helped me alot thx

[plain spindle]

take bits A = 1000 1011 and B = 1101 0010
A or B = 1101 1011
A and B = 1000 0010
A xor B = 0101 1001

The bitwise operation is performed bit by bit on the string, and they should be of equal sizes. There is nothing more to it, explained in that paragraph.

[peak jay]

anyone got a good soruce to learn combinatorics?

[worldly beacon]

hi can someone help me with this ?
ive rearranged it to 2x^2 = 2floor(x) + 1
which tells me that LHS is a odd integer but unsure where to go from there

[tight hound]

Write floor(x) as x - frac(x) in the given equation, this will immediately give you bounds on x.

[worldly beacon]

sorry can u explain the bounds on x abit further ? cant rlly see it

[tight hound]

Maybe the way you did makes it easier to see. We have floor(x) = x²-0.5, and since floor(x) ≤ x, we get x ≥ x²-0.5. This gives us x²-x+(1/4) ≤ 3/4

Hence (x-(1/2))² ≤ 3/4

The bounds on x then give us the set of possible values of floor(x), which can then be used to find x² from the relation given to us, and the values of x that satisfy the given bounds are the required solutions

[worldly beacon]

i got it now thanks alot :))

[halcyon swallow]

Hi, I've trying to solve 8x ≡ 10 (mod 14) for 1 hour I'm going insane can someone please help meeee

This is all I’ve done and idk how to solve this shit

[worthy siren]

you want to find all natural X ?

or just one X is enough ?

x=3 is one of the solutions

[halcyon swallow]

Yeah I know the answer is 3 and 10 but idk how to do the solution

[halcyon swallow]

Yes 😭

[fossil mural]

if two things are equal mod 14 then they're equal mod 7

so 8x = 10 mod 7

which simplifies to x = 3 mod 7 because 8 = 1 and 10 = 3

and then anything that's 3 mod 7 is either 3 or 10 mod 14

[halcyon swallow]

I don’t understand 💀

[fossil mural]

which part do you not understand?

[halcyon swallow]

I don’t understand where you’re getting 3 from

[fossil mural]

10 mod 7

10 = 7 + 3

[halcyon swallow]

Oh

[worthy siren]

well you can use this as long solution.

[halcyon swallow]

omg surely there's gotta be a easier solution I don't understand

[worthy siren]

the easier solutin expressed by "bee [it/its]" ( didn't want to tag )

[vital dew]

cedric_

[pastel coral]

Given the set $V ={1,2,3,4,5,6}$, give a permutation group consisting of the elements of V with order of the group equal to 12.
So, I've found a permutation group, but it was through trial and error. Are there any tips/ideas to use when dealing with such like questions? Or is there an explicit way to obtain these?

[vital dew]

cedric_

[fossil mural]

my first thought looking at this is that the prime factorisation of 12 is relevant
so 2x2x3

3 means a 3-cycle and 2 means a transposition, the easiest way to get those without anything extra messing it up would be to do it all separately (so the group generated by (123), (45), (67)) but we don't quite have enough numbers for that so we need to overlap them somehow

[pastel coral]

but like, i know for disjoint cycles, the order is lcm(lengths of each cycle), but in this question in particular, you can't get cycles of lentgh 2,4,3 with the cycles being disjoint, that's what makes it hard imo

[pastel coral]

(123), (45), (67))
7 isn't in the set V

[fossil mural]

yeah i know, that's the problem

we need to handle multiple of the prime factors in the same set of numbers

but if you just include all the permutations of {1,2,3}, there are 6 of those

then add a transposition like (45) and now there are 12

[tepid oak]

this would have order 6 however

surely it must be a 3 cycle and 4 cycle

[pastel coral]

but like, i know for disjoint cycles, the order is lcm(lengths of each cycle), but in this question in particular, you can't get cycles of lentgh 2,4,3 with the cycles being disjoint, that's what makes it hard imo

[fossil mural]

...how is that 6

[pastel coral]

but with 6 elements you cant get disjoint cycles of 2,3 and 4

[tepid oak]

oh

[fossil mural]

identity, (45), (67), (45)(67)
(123), (123)(45), (123)(67), (123)(45)(67)
(123)^2, (123)^2(45), (123)^2(67), (123)^2(45)(67)
there are 12

[pastel coral]

ye that's 12 indeed

but we can't have the 7 in there 🥲

[fossil mural]

yeah

so we have to find two factors that we can "overlap"

getting 4 using only 3 numbers doesn't work

but you can get 6 (2x3) using just 3 numbers

[pastel coral]

yeah so back to my point, is there a systematical way, or is it just trial and error?

because i got one, but just by trial and error

[fossil mural]

well you can probably extrapolate this into a systematic method
find collections of prime factors and try to overlap them

still involves brute force but a lot less than if you tried something like producing random subgroups

[pastel coral]

yeah alright, i think that kinda answers my question

thanks for your time!

[tepid oak]

what was the group you found I haven’t found one yet

[fossil mural]

the group generated by S_3 (all the permutations of 1,2,3) and (45)

[pastel coral]

but like, would this even be considered a good answer since we have just (6), a cycle of length 1?

[fossil mural]

...huh, it is very interesting that that works

[fossil mural]

well you could just remove that

(6) is just the identity so it's going to be in the group either way

[pastel coral]

yeah right

[pastel coral]

why?

[fossil mural]

i just would not have expected that you could do it using only the first 4 numbers

[pastel coral]

i can't clarify why that'd work 😂 , my discrete math professor just explains everything so badly lol

[fossil mural]

...oh i get it now
this is A_4

it's the group of even permutations of 4 things

which is exactly half of all the permutations and therefore you get 4!/2 = 24/2 = 12 of them

[hardy needle]

how to write mathematically logical statements

[hardy needle]

@here

[frigid surge]

#proofs-and-logic ?

That’s a pretty vague request

[gritty garnet]

any ideas?

#help-15 im here btw

[outer bridge]

is every bipartite graph tripartite if yes then how can a simple connected graph of order 2 can be tripartite ?

[faint sphinx]

If you have sufficiently many vertices, then yes, every bipartite graph is tripartite. If you allow empty vertex sets (not sure if it's standard to allow them or not), then this includes simple graphs of order 2

(in fact: if you allow empty vertex sets I guess it's trivial lmao. Just take the 3rd set to be empty)

[outer bridge]

how will a set with not vertex be connected to other vertices?

[faint sphinx]

There doesn't need to be any connections between the vertex sets, at least not in the definition of bipartite I remember

If you allow edge cases like I mentioned above, then any bipartite graph is tripartite. If you don't, i.e., if you want all of the vertex sets to be nonempty, then any bipartite graph with at least three vertices works

[ivory badge]

Is a discrete graph bipartite

[sage gale]

whats the best way to studt discrete math?

any good resources?

[quiet tendon]

hey I asked a question about the coin tossing yesterday and I got another question but the probability are the same on both, I was wondering why

A and B play a “match” consisting of a series of “games”. In each game, A rolls a coin with probability 2/3 heads and 1/3 tails and B tosses another coin with equal probability 1/2
on heads and tails. If the outcomes of the two coins are different, the player wins
heads, and if the two outcomes are the same then it is a draw (no winner).
(ii) If the match continues until A or B has won a total of 3 games, calculate the
probability that A wins the match.

[faint sphinx]

Sorry, I'm not sure I understand how A or B wins the match. So they both toss 1 coin with differing odds? Could you clarify how the "winning" works for the game?

[quiet tendon]

ye so what u are saying is correct they both toss with different coins and when the coins are different then the one with heads wins

if they are the same it's a draw

I asked yesterday about another quite similair problem with coin tossing and it has the same probability but I guess actually that it won't matter too much

answer was 64/81 now too

[faint sphinx]

Oh I see, if A rolls heads, B rolls tails, then A wins

makes sens

lemma think on this

[quiet tendon]

ye

[quiet tendon]

so this question was yesterday

[faint sphinx]

well, we can try to calculate the chances for each game that A wins, B wins, or it's a draw. that would be a good first step I guess

[quiet tendon]

that is easy

1/3 1/6 3/6

[faint sphinx]

cool

[quiet tendon]

so I was thinking same approach as yesterday then chance that A wins 3-0 is like 1/3 * 1/3 * 1/3

and then 3-1 and 3-2

but I was not sure

[faint sphinx]

so you could probably handle this with an infinite series of some sort (since, ya know, there is always the possibility that they just keep drawing over and over again)

but that sounds awfu;

[quiet tendon]

ye

[faint sphinx]

Effectively, I think we can just "ignore" the chance for a draw, and only look at the case where someone (either A or B) wins

[quiet tendon]

ye I thought that too

since the tosses are independent and it doesn't afect the result smth like this was my reasoning

[faint sphinx]

so that chance that someone wins at all is 1/2. Of that 1/2, there's a 2/6 chance A wins and 1/6 chance B wins

but ofc that doesn't sum up to 1, that sums up to 1/2. So if we normalize these chances since we are ignoring draws (i.e. divide them by 1/2), we get that, for each game that has a winner, there is a 2/3 chance it's A, and a 1/3 chance it's B

Does this now look similar to the previous exercise you did?

[quiet tendon]

ye then it works

[quiet tendon]

I didn't saw this step

thank you

[faint sphinx]

now there is the possibility that they draw forever

[quiet tendon]

oh

[faint sphinx]

But that ofc has probability 0

[quiet tendon]

ye

because that is 1/2 * 1/2.....

that is 0

[faint sphinx]

(since 1/2^n converges to 0 as n --> infinity). So I think (? I don't do a huge amount of probability tbh) we can effectively ignore that

[quiet tendon]

ye this is correct I think too

[faint sphinx]

Not sure if there's a more formal justification, but the chances of nobody winning is 0, so I think that works?

[quiet tendon]

ye thanks alot agian

[faint sphinx]

[quiet tendon]

if u have time can I ask 1 last question,

(iii) If the match continues until a total of 5 games are won (by A and B together),
then calculate the probability that A wins the match, i.e. that A has won more games than B.

the chance is again the same

so I thought like I calculate the chance A wins by 3-2 4-1 and 5-0 and sums it up

[faint sphinx]

well by the point 5 games are won, someone must have at least 3. So you could directly calculate it like you mentioned with 3-2 4-1 and 5-0, or recognize that this is the same as A winning with the previous criterion (since there's no possibility for B to win 3 games, and then A ends up with more wins in the end)

Again, any weirdo edge cases with draws have probability 0, so we ignore them

[quiet tendon]

oh wait u are right the previous case was the cahnce of A winning 3 games and this question basically ask the cases were A wins atleast 3

[faint sphinx]

yeah. If we were going to, say, 7 games it would be a different story. Since then you could have B win 3 times, then A win 4 times (so B wins by the previous condition, but A wins with the new condition). But since it's only 5 this can't happen

[quiet tendon]

wait ye so it's basically the same question but I just didn't recognized it I guess

[faint sphinx]

yup

[quiet tendon]

wait but isn't the second case asking a scenario where A wins by 3-0 3-1 or 3-2 and case three asks for a scenario with 3-2 4-1 5-0?

[faint sphinx]

right, but as the number of total wins goes from 3 to 5, the first two cases will become one of 3-2, 4-1, and 5-0. Like if A won by the first condition 3-1, then then next win would either make it 4-1 or 3-2. So in essence, the total probability of A winning should stay the same, although the specific probability for each case will change

(btw, I'm not sure whether this justification is appropriate in an exam setting or not. Might be better sometimes to just do the boring calculation just to be safe!)

[quiet tendon]

ye basically what I am doing is I know the probability is the same so I find a clarification for it but it actualy has to happen the other way around

first finding the clarification and then seeing that they are the same

[quiet tendon]

the boring safe calculation should be looking like
for 3-2 and 4-1
2/3 * 2/3 * 2/3 * 1/2 * 1/2 +
2/3 * 2/3 * 2/3 * 2/3 * 1/2 +
...

and then also 5-0

is that correct

[faint sphinx]

uhh times any reordering of those

[quiet tendon]

oh wait ye

ye I can figure that part on my own

[faint sphinx]

but yeah once you add that it looks good

[quiet tendon]

but for this part so 3-2 is in both cases

so the chance of 3-0 and 3-1 is the same as 4-1 and 5-0?

[faint sphinx]

nope. Like I said, the probability of each specific case will change. So the chance of A winning 3 times in a row is (2/3)^3 = 8/27, but 5 times in a row is ofc much smaller at (2/3)^5 = 32/243 (I think that's 3^5 anyways lol)

but in total, chance of A winning stays the same

[quiet tendon]

ye I thought so

[quiet tendon]

but uhm I don't realy see why actually

is it because of the reordering?

or the way the question is asked?

[faint sphinx]

well there's this answer

But in terms of the calculation

[quiet tendon]

wait I found a reasoning

idk if it's correct

[faint sphinx]

okay

[quiet tendon]

so basically in the second question

I was thinking like this

64/81 is the chance A is winning a total of 3 games

so the leftover 17/81 is the chance that B is winning a total of 3 games

so in question 3 u know it's not possible that B wins a total of 3 games

it can only be that B wins 0 1 or 2 so that is 64/81

idk if u can follow me but I think u wnated to try to explain smth like this

[faint sphinx]

uhh yeah I think I get the idea. Seems similar to what I had in mind, except you're viewing it from the case of B winning (whereas I was looking at A winning)

But yeah (a variation of) that should work

[quiet tendon]

ye for some reason my mind couldn't grasp the idea of A winning idk why

[faint sphinx]

lol

[faint sphinx]

but yeah does that reasoning make sense to you now?

[quiet tendon]

this one?

[faint sphinx]

any of them

or the one you sent ig

[quiet tendon]

ye I understand the one I sent

[faint sphinx]

:swag:

[quiet tendon]

but ur answers still helped me alot thx

[faint sphinx]

of course

[still isle]

Is every Cartesian product an equivalence relation? Since the equivalence relation is the subset of the Cartesian product?

[meager prawn]

Technically yes

[brave rock]

Technically no.

{1} x {2} is not an equivalence relation.

And the justification is spurious.

[still isle]

Oh ye that's right, thanks mate.

[meager prawn]

oh duh

right, it's A x B union B x A

[rigid oriole]

is equiv rel => is subset of cart product

i dont understand how u conclude
is cart product => is equiv rel

[rigid oriole]

i dont feel like this gives one either

suppose A n B = phi

then reflexive fails

[faint sphinx]

A x A is an equivalence relation for any A, which is perhaps what they were thinking

And yeah A x B U B x A fails reflectivity and transitivity even I think

[little prism]

even if it worked, relating all elements makes for a very boring equivalence relation

[faint sphinx]

Relating all elements of the same set works, but yeah it's not particularly interesting

[eternal grove]

Hello, can anyone help explain to me how this problem works? I'm super lost

[zenith sage]

guys i need help: see first of all its a combinatorics problem,,...Suppose you have 6 men and 4 women and u want to form a committee of 5 such that a commitee has atleast one woman

the way a normal person does it is by making cases

[dire walrus]

so, do you want to solve it without cases?

[zenith sage]

i.e. 1 woman 4 men, 2 woman

[zenith sage]

bro i thought of another method

[dire walrus]

okay, say

[zenith sage]

lemme say

first u eliminate the restriction by choosing 1 woman out of 4 women i.e. 4C1 ways and then u have total 9 people left now u need 4 more people so 9C4 then by fpc total ways = 4C1x9C4

but bro the answers are different and i think something is wrong with my method

[dire walrus]

you want at least 1 woman

not exactly 1 woman

so your committee can have 2 woman as well

[zenith sage]

but bro all i am doing is removing the restriction

[zenith sage]

bro see my logic

i thought what u r thinking

my comitee can choose 2,3,4 women now

bcz of no restriction

9c4 can have anyone

btw the guy who did these types of problem first in history thought about these i think,,.. bcz why make cases when u do it easily using fmc

[dire walrus]

the easiest way is to count the number of committees without any women and subtract that from the toal number of committees

but let's see what's wrong with your approach

[zenith sage]

yup bro

btw if it was alike objects then we use beggars method(idk what u guys call it but in my country they call this beggars method)

but people are different objects and not alike

[dire walrus]

there's things that get overcounted by your method

say your women are w1, w2, w3, w4

you fix one women, say w1, and then choose 4 more people, say w2 is in them

so it's like (w1,w2, sth, sth, sth)

now when you fix w2, and choose w1 from the remaining, you have (w2,w1,sth,sth,sth)

which is the same if the sths are the same

so you are overcounting a lot

[If you want to explicitly see the overcounting, try with a smaller number of peoplr. 3 men, 2 women and a committee of size 2 should help you]

[zenith sage]

hmmn

yup bro i got it i think

thanks

according to my method w1,w2 and w2,w1 are different

whereas they should be the same

[dire walrus]

yeah

so you need some kind of inclusion-exclusion

better to just do it via the compliment

[still isle]

Yes, this is what I was thinking.

[still isle]

I was just wondering the maximum size of an equivalence relation on a set.

[gusty nacelle]

i’m trying to rewrite a sentence in “If/then” form but i’m confused on how “p unless q” works

if the sentence is “you do x unless you are not y” then would q be “you are y” or “you are not y”?

[blissful crescent]

Hello, I apologize if this is an inconvenience but I would like some help understanding why it is that the codomain of G is neither c, d, or cd. I'm just not sure what I'm missing.

[blissful crescent]

nevermind..

I misunderstood it as range

I'm dumb LOL

[rugged valley]

tips?

[zinc kettle]

can any modular equation pro help me in #help-2

[unique dove]

Is this work accurate? Primarily the part of me trying to find the negation of the original statement S

For N I'm using all integers 1 and up

[worthy siren]

sry for mention. but what is this website name ?

[worthy siren]

the answer is 24 ?

i think you should just choose k1, k2, k3, k4 in the formula to be power of which xi

it would be 4! = 24

[near moth]

Hello there,

I am a college student and I recently just started Foundations of Discrete Mathematics, I am having a hard time trying to get started since I am all new to this stuff and I have been recently stuck on Propositions and Truth Values, If anyone is knowledgeable with Discrete Math, Can we please video call each other and you can show me how the Proposition/Truth Value formulas and equations work and stuff?

[rugged valley]

correct answer is 12 apparently

[tidal socket]

Two dice are rolled. What is the probability that (a) the two numbers will
differ by 1 or less and (b) the maximum of the two numbers will be 5 or larger?

[weary tiger]

Why not draw a 6x6 table and tick the squares that satisfy the criteria, then / 36?

[tidal socket]

yes, but i cant understand , please give me solution of this problem

ans of a is 16 /36 and b is 20/36. what is the procedure

[weary tiger]

like i said, if you draw a 6x6 table, you will have 36 squares, one for each possibility. Check how many possibilities satisfy the question they asked

[tidal socket]

is the 2nd answer is right?

[weary tiger]

Yes

The solution is:

• A is 1, 2, 3, 4: B must therefore be 5 or 6, giving 4 x 2 = 8 possibilities
• A is 5, 6: B can be anything, giving 2 x 6 = 12 possibilities

Add together, you get 20 (out of 36)

You can work out the first subquestion yourself using the prior method

[near verge]

I need help with a concept about graph theory, how do I prove that the number of possible trees with n vertices is n^(n-2)?

[brave rock]

The formula is false. For example there is only a single tree with 3 vertices up to isomorphism, yet the formula you write predicts that there are three.

I happen to know that the formula you have written counts the number of labelled trees with n vertices. The reasons for this are actually quite complex.

I imagine you've seen this as part of a course or book, and I would also imagine the course or book has discussed the relevant concepts, for example Pruefer sequences. You should look at those to understand how to prove that.

[near verge]

yes, thank you. I forgot that it was about labelled trees and I would like help with that, because the teacher read it from a book and told us to read it, but I can't find that book, so I'd appreciate proving it for labelled trees or the recommendation of a book where I could find it.

[arctic nest]

is {1} a subset of {1,{2}}?

I would think so because both share the element of 1

[faint sphinx]

Yes

{1} is a subset, but not an element

[arctic nest]

yeah thats what I thought

but based off the solution I was given it isnt?

said something about no because {1} is a set and there is no sets used as elements in {1,{2}}

I feel like thats wrong doe

[faint sphinx]

None of that makes sense

[arctic nest]

lol yeah

[unborn vapor]

can you send the solution you were given? Because yeah none of that makes any sense

[arctic nest]

then again theres also a handful of incorrect solutions in my exercise sheet lol

this is probably another one of them

[faint sphinx]

[unborn vapor]

I guess lol. I’m amazed they managed to mess it up that badly though, like it’s not just wrong it’s completely nonsensical - there is a set as an element, and it doesn’t even matter whether there are since this is asking about subsets

[arctic nest]

an underlined c just means "is a subset of" right

where as proper subset is just a regular c

so im correct in thinking {1} is a subset of {1,{2}}

another questionable solution

question is if {1} is a subset of {1}

I thought every set is a subset of itself?

[unborn vapor]

yeah

[unborn vapor]

yeah but that symbol isn’t as common and I think it can ocasionally also be used just for regular subsets? Don’t quite me on this though

[unborn vapor]

no this one’s true because it says not a proper subset

[faint sphinx]

Cringe

[unborn vapor]

Yes subset but not proper subset

[arctic nest]

Yeah it didn’t specify that in the question lol

It just had the underlined c

[unborn vapor]

yeah so that’s a mistake in the question/solution then

[arctic nest]

Yep

[arctic nest]

Ye?

[fossil mural]

{1} is a subset of {1} and of {1,{2}}

[arctic nest]

Cool I got it correct then

[fossil mural]

they're correct that {1} isn't a proper subset of {1}, but if the question was just "is {1} a subset of {1}" then that's not relevant

[arctic nest]

Yeah which it did not specify

I’ll just write it to be safe lmao

I appreciate the advise 👍

My professor is basically learning this at the same pace as us lmao

[arctic nest]

what do N and Q mean when referring to sets

like ik R means all real numbers and Z means all integers

[brave rock]

Here's a list of all the ones that are helpful to know https://www.mathsisfun.com/sets/number-types.html

[arctic nest]

thank you

pi and e would be subsets of real numbers and rational numbers right

cause you can rewrite pi and e as fractions

[brave rock]

pi and e would not be subsets of the real numbers nor rational numbers, you mean to say that they are elements.

However, no.

pi and e are real numbers, but they are not rational numbers. They are irrational numbers.

[arctic nest]

ah ok

cause they're too specific to be written as fractions?

[brave rock]

It is a bit more complicated than that

[arctic nest]

basically they're special numbers

[brave rock]

1 is also a special number, but it is rational

[arctic nest]

idk you get what im trying to say

[brave rock]

Not really

[arctic nest]

why are they irrational?

pi and e

[brave rock]

It is quite difficult to prove they are irrational and I don't think I have any sort of satisfactory informal reason for their being irrational.

[arctic nest]

I just gotta know they're irrational lol

[brave rock]

Yes.

[arctic nest]

gotcha

thanks 👍

[keen flare]

Can someone figure out what im talking about?

My memory is hazy

[snow sleet]

Looks like ur counting the ways to distribute 3 types of donuts (one with 10, 4, 8) amongst 14 people. Counting distributions

(10,4,0) would be one such distribution meaning 10 donuts of one kind and 4 of another were chosen

[snow sleet]

See above

[keen flare]

Tysm

This is definitely it

[keen flare]

Is there a wiki page on this

Because I used this to compute a boundary map for cohomology before but I don’t remember exactly what I did

[snow sleet]

Prolly lol. Balls into boxes . Identical balls into distinct boxes more precisely

Stars and bars method is related as well

[keen flare]

Stars and bars is related?

Oh but if you have three things it’s probably stars bars and something else

Or maybe stars and bars is case when you are distributing one item?

Nah no way let me think about this

[snow sleet]

consider the 14 people as the 14 identical stars. Use 2 dividers and then everything to the left one the leftmost would be the donuts of one type. Everything in between the two dividers would be another type and everything to the right of the rightmost bar would be the last type

(16 choose 2) is the number of distributions in other words

[snow sleet]

Stars (identical balls) the bars represent the distinct boxes (things to the left of one bar mean that one box, things to the right of a bar mean another box)

[keen flare]

Do these have any relationship to the linear diophantine i gave?

The 10x+4y+8z=14

Or is that unrelated

[snow sleet]

Ur looking for integer solutions to that equation (I.e., lattice points) (x,y,z) kind of similar thought not obviously similar

If I asked u to find the number of nonnegative integer solutions to x+y=14, then (1+x+…+x^(14))^2 would be another route u could take.

[keen flare]

And then summing degree 14 coefficients ?

And this would work with a_1x_1+…+a_nx_n=a where a>sum a_i?

[snow sleet]

in my example, the x^14 after expansion is the thing u wanna see the coefficient of

[keen flare]

Wouldnt it be 1?

Oh no you squared

Wait

Wouldnt this be the same?

[snow sleet]

I squared it because y can go from anywhere from 0 to 14 and x can too

NOTE: this is only for counting nonnegative integer solutions

[keen flare]

Yeah

[snow sleet]

Let me give u yet another example. Suppose I distribute 13 cards among the 4 suits. How many possible distributions are there?

I could expand (1+t+...+t^(13))^4 and look at t^(13)'s coefficient

or I could use my reasoning from before about stars and bars (i.e., identical balls into distinct boxes) and say the answer should be 16 choose 3

[keen flare]

17?

Wait

13 cards and 3 bars

[snow sleet]

yes

,w Expand[(Sum[t^i,{i,0,13}])^4]

[vital dew]

Results provided by WolframAlpha

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

Requested by logician#7452

[snow sleet]

,w 16 choose 3

[vital dew]

Results provided by WolframAlpha

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

Requested by logician#7452

[snow sleet]

this is the same as asking what the number of nonnegative integer solutions to x+y+z+a=13

[keen flare]

Ok i see

[snow sleet]

back to this problem...were u asked to find the number of nonnegative integer solutions here?

[keen flare]

No I don’t remember exactly

But there was a connection between this and multiplying out the polynomial earlier

Or maybe it was slightly different

The donut thing sounds familiar

[snow sleet]

if so, I would expand (1+x^(10)+x^(20))(1+x^4+x^8+x^12+x^16)(1+x^8+x^16) and look at x^14's coefficient

[keen flare]

Oh yeah

This might be closer to what it was

[snow sleet]

yeah based on the context of the convo surrounding that equation, I think that's it

[keen flare]

I think it was something like this but every polynomial was in terms of x y and z instead

And we looked st degree 14 term

I didnt give the exact problem

Just how I remember this thing from a yesr ago

It might have been something like x+2y+5z=10

[snow sleet]

,w Expand[(1+x^(10)+x^(20))(1+x^4+x^8+x^12+x^16)(1+x^8+x^16)]

[vital dew]

Results provided by WolframAlpha

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

Requested by logician#7452

[snow sleet]

gotcha

[keen flare]

And then I think it was some formula similar to (1+x+…+x^10)(1+y^2+…+y^10)(1+y^5+y^10)

[snow sleet]

yeah so these are called GF's generating functions not girlfriends lol

[keen flare]

That should be the same if you count degree 10 terms

Yes

I remember this

Thanks so fucking much

Im pretty sure thats it

[snow sleet]

no problem

[keen flare]

So yeah

I have used generating functions before

But in context of recurrence relations

Idk how this was the same thing

Ik generally the idea is you have some equations and then you make a power series on both sides and do manipulations

[snow sleet]

oof recurrence relations is not one of my strong suits lol. I imagine those manipulations ur talking about are just simple alegbraic manipulations. I'm kind of surprised actually that GF's are talked in a discrete course. They def weren't brought up in my discrete course. I found out about em from a probability and stats course and a combinatorics course

[keen flare]

I am not learning discrete

I never did

I graduated school this May

[snow sleet]

lol what??

oh

wait

what grade are u in lol?

[keen flare]

Idk im not in school

I finished undergrad

[snow sleet]

ohh that explains it

[snow sleet]

this sent me ahahaha

"what grade are u in" "idk I'm not in school"

[keen flare]

Lol

[keen flare]

Oh yeah

To clarify

These generating functions in probability are different

You mean moment generating functions?

Or are you talking about using generating functions for branching processes?

Because you did mention combinatorics

[snow sleet]

I was talking about EGF's not MGF's

[keen flare]

Exponential generating functions?

[snow sleet]

yes (1+x+...

[keen flare]

Yeah i never learned then

Oh wat

They are the same thing?

I thought egfs were like something with e^x

[snow sleet]

They are similar, but forget about the factorial denominators and then yea they're the same.

egfs are the taylor expansion yea but don't look at the denominators

[keen flare]

O i see

I wonder how they differ

[snow sleet]

me personally, I'm more of a number theory proof kinda person

well they differ by that k! denominator in the sum

[keen flare]

Yeah but how that changes their usages

I never knew use of egf

But ive seen similar things when talking about formal power series

[snow sleet]

absolutely, it's been a hot minute since I've used and sort of GF before, so I'm not quite sure when I used an EGF but it was definitely when stars and bars didn't quite cut it

[keen flare]

Lol

[upbeat mango]

guys how do i go about this question

[worthy cobalt]

this too

[gusty grove]

im just confused on how to do this:
Let R be an equivalence relation on A = {a, b, c, d, e, f, g} such that aRc
would the elements of R be R={(a,a),(a,c),(c,a)}?

[faint sphinx]

those are necessarily all elements of R, but there must be more as well. Remember that an equivalence relation needs to be reflexive, so you need at least (x, x) in R for all x in A

[gusty grove]

understood, thanks🫡

[tulip nymph]

what do I do about bounds in a quantifier??

do they invalidate an equation?

[dense pelican]

Our framwork will be N^2. Let A=(x_1,x_2) , B=(y_1,y_2) in N^2 , instead of measuring in the usual way we will consider the distance d(A,B)=gcd(x_1-y_1, x_2-y_2).

Q1: Let ABC be the triangle of sides a=d(AB) , b=d(BC) and c=d(AC) , then gcd(a,b)|c , gcd(a,c)|b and gcd(b,c)|a.

Q2: Given a,b,c in N such that gcd(a,b)|c , gcd(a,c)|b and gcd(b,c)|a , then there exists a triangle with those sides.

[faint sphinx]

please don't crosspost

[tulip nymph]

can u help me out rq?

[faint sphinx]

i don't know the answer to your question, and please don't ping me randomly

[tulip nymph]

bros not a helper 😢

[gusty grove]

does anybody know how to find [-82] in Z11?
i find it easier for a positive number, like for example [207] in Z11 is [9] because 207 is congruent to 9 mod 11, ie the remainder when 207 is divded by 11 is 9. But how does it work for negitive numbers? Am i correct to say that when -82 is divided by 11 the remainder is 5 so [-82] in Z11 is [5].
But i know the answer to be [6], i just dont know how that was obtained. Any clues?

[ivory badge]

Can you find [82]

[gusty grove]

yes, is it not [5]? ie when 82 is divided by 11 the remainder is 5 so 82 congruent 5 mod 11?

[ivory badge]

[82] + [-82] = [0]

gg

[gusty grove]

lol wdym by this?🥲

[ivory badge]

I’m saying that’s how you find it

[faint sphinx]

-82 = -7 * 11 - 5 = -8 * 11 + 6.

The remainder is not 5, but -5

[distant grove]

I'm currently working on a problem involving path counting in the x-y plane, and I could use some guidance on how to approach it. The problem is as follows:

My approach to solving (a) was that we start at the point $(0,3)$ and need to reach the point $(7,2). In each step, we can either move up one unit and to the right one unit (denoted as U), or move up one unit and to the left one unit (denoted as L). To reach our destination, we must take 3 "U" steps and 4 "L" steps. This is because we need to go from a starting y-coordinate of 3 to a final y-coordinate of 2 (a difference of 1), and move 7 units in the x-direction. Now, the question is how many different combinations of 3 "U" steps and 4 "L" steps we can take, where the order of the steps doesn't matter. To count these combinations, we can use combinatorics. One way to do this is by calculating the binomial coefficient "7 choose 3," which is also denoted as "$C(7,3)$." This can be computed as: $C(7,3) = 7! / (3!(7-3)!) = 35$.

But I am not sure if this correct?

As for (b) to (d), I am not really sure how to solve the questions and would like some help.

[safe steppe]

Hi guys, do you need 2 defined operations for the associative property to be able to apply in a mathematical structure

[unborn vapor]

No, because associativity is a property of an individual operation. Do you know what associativity is? Where does the second operation come into your question?

[safe steppe]

My bad 🤦‍♂️ I was confused, I thought the associative property was A^(B U C) = (A U B) ^ C ( ^ being an operation)

I see now that there is only one operation lol, thanks

[empty escarp]

What is the number of edges in complete r-partite graph where each part has size n

[safe steppe]

Hi guys, how exactly would I do A, Im not sure how these predicates work, because every integet is obviously not an odd integer, but what do they mean by this in context of the question?

[abstract whale]

Hey guys. I have a question regarding both answers of these proofs. So I am following everything until "red highlighted" step. I feel like I am missing some algebraic steps there, that I am not sure how they came to that conclusion.

For example, proof(a) how did 7 * 7^n - 5 * 5^n turn into 2 * 7^n + 5 * (7^n - 5^n).

Another example, proof(b) how did 14 * 7^n - 15 * 5^n + 1, turn into (2 * 7^n - 3 * 5^n + 1) + 12(7^n - 5^n)

[faint sphinx]

7 * 7^n = 2 * 7^n + 5 * 7^n
So then they factored the 5 * 7^n and 5 * 5^n
The other one is similar, just by splitting up the 14 and 15

[abstract whale]

Wait, by 7 * 7^n = 2 * 7^n + 5 * 7^2 do you mean 7 * 7^n = 2 * 7^n + 5 * 7^n?

[faint sphinx]

Yes my bad, that was a typo

[abstract whale]

So, let me see if I understand:

7^n+1 - 5^n+1 
= 7 * 7^n - 5 * 5^n 
= 2 * 7^n + 5 * 7^n - 5 * 5^n
= 2 * 7^n + 5 * (7^n - 5^n)
= 2 * 7^n + 5 * (2k)
= 2 * (7^n + 5k)

[abstract whale]

I see! It makes a lot more sense now, thank you so much, friend.

[radiant mantle]

Okay so bassicly i need help to clarify which positions i can say are legal and which are ,,crushed walls", what i mean? bassicly we are given a board of NxN (also let's say N needs to be at least 3 and needs to be odd)
there's example of 5x5 board:

on the board you're allowed to place walls in such a way so you cut 2 connections

in a way like this for example:

(red line for easier imagination)

,,crushed walls" positions are for example where 2 walls are overlapping with each other you can get it in 2 ways (i call those criss cross and cross cross)

that's a example of cross cross situation (second wall is blue to see the difference)

that's example of ,,criss cross"

and about cross cross example i can say that on each step of placing a wall i just can calc how many connections are there and check if the amount of them is even, if yes then it's good but if it's odd then it's ,,crushing walls" positions

but what if there's ,,criss cross" situation?

i have no idea how to calc those

and idk if i should even try to do that in some graph way, because i guess there's other ways to answer my question, i by myself tried to count ,,crushed walls" position by calcing how many there is and going out with formulas (i got half of the formula and only for criss cross situation, no idea how to do that with cross cross situation, (with 3 walls also btw)) for 2 walls only on board that's not too hard to calculate

my friend was able to find formulas for 2 walls and 3 walls to count legal positions but they look very random and he gonna explain them a bit later so i tries to do that by graph method somehow

any idea?

also if i know that cross cross situation needs odd number of connections anyone have any idea on how to generalise how many there is for any NxN board (for N being bigger than 3 and always ODD)

[radiant mantle]

also for more data:

((4(n-1))(2(n-1)^2-3)+(2(n-1)^2-4(n-1))(2(n-1)^2-4))/2

2((n-1)^3 ((n-1) C 3) + (n-1)((n-2) C 2)(n-1)(n-2) + ((n-3) C 3)(n-1)) + (2(n-1)((n-1)^2-2)+(n-1)(n-3)((n-1)^2-3))((n-1)^2-2)

for n x n board
C it's Choose

first formula is for any board with 2 walls
second for any board with 3 walls
(both says how much legal positions is there)

3x3 board (up to 2 walls)

5x5 board (up to 6 walls)

7x7 board (up to 6 walls because calcing 7 walls would take 1-2 days)

[arctic nest]

For a relation between sets to be a function all elements in the domain must be connected to the co domain right

That and no repeating x values

[safe steppe]

Hey guys, any advice on how I could show this. Ive been trying for an hour but I keep on getting stuck. I tried starting at the Modus Ponens, but I'm not sure where I should do what to get it to the resolution rule. So far I figured I can change the ϕ ⇒ ψ to ¬(ϕ∨ψ) and then use demorgans law but Im not sure what to do after

[radiant mantle]

i have no idea what that means but i'm sure there needs to be some formula which goes like
0,1136,6552
or just
1136,6552 (and something further but i didn't finished the code for 9x9 to know what's the value for 3 walls 9x9 quoridor)

or with legal things

for 1136,6552 i checked oeis

no results

for 8,40,96 there seems to be resonable formula on oeis but i can't be sure, having 9x9 results should make it more obvious

this one to be more clear

[arctic nest]

You replying to the right person?

I just means in terms of like arrow diagrams lol

Like this

[radiant mantle]

i mean your message was to mine things or

or to somebody else

[arctic nest]

This is wouldn’t be a function because 5 isn’t connected to anything right

[radiant mantle]

okay i know what you means but how that would help me?

[faint sphinx]

there are multiple people using this channel

they were asking their own question, not related to yours

[faint sphinx]

correct

[arctic nest]

That and no repeating x values is allowed

[radiant mantle]

oh i was thinking he's answering mine

i didn't thinked that this is a question

my bad then

sorry for that

[faint sphinx]

"connected" is perhaps in imprecise term, but I think you have the right idea. A function must map everything in the domain to something in the codomain. That is, if f: X --> Y is a function, then f(x) exists for every x in X. And correct, we cannot have f(x) take two different values. (in terms of the relation, this means that "for each x in X, there is exactly one y in Y with (x, y) in the relation")

[arctic nest]

You get what I’m saying lmao

Me bad with words

[faint sphinx]

yes, but you should try to be precise in math (as best as you can 🙃)

[arctic nest]

Apologies

[spiral aspen]

• Every coffee drink contains coffee
• There is a coffee drink which contains coffee and milk
• A cappuccino contains coffee and milk
• If cappuccino is a coffee drink then latte is a coffee drink
• Latte is a coffee drink
from the above premises can u derive Cappuccino is a type of coffee drink

?

i think no right?

[rigid oriole]

you should suppose if it isnt and check if any inconsistensies arise

[gusty grove]

1 ≡ 7 ≡ 13 ≡ 19 · · · (mod 6)
is a statement like this saying that 1≡ 7mod 6 and 1≡ 19mod6 and 7 ≡ 13 mod6 and so on?

[jolly ledge]

a ≡ b mod n means
n | (a-b)

so

this very much says what you're trying to?

[gusty grove]

im trying to understand that if p is prime and not 2 or 3 then the residue class of p is equal to the residue class of 1 or 5 in Z6

[stray reef]

yes

[stray reef]

well try turning it around: show that any number that isn't 2 or 3 themselves, but isn't 1 or 5 mod 6, is necessarily composite.

[gusty grove]

cool, thanks for the feedback😉

[foggy sentinel]

Does someone have a good explanation towards the rule of implication?

[muted gate]

hey, how to go about this one?

[safe steppe]

Hi guys, so I have this proof I have to do, can someone just scan through my answer real quick and check if it is allowed what I did.

[sterile flame]

Wait, here $\mu \rightarrow \lnot \psi \lor \theta$ means $(\mu \rightarrow \lnot \psi) \lor \theta$ or $\mu \rightarrow (\lnot \psi \lor \theta)$?

[vital dew]

davide

[safe steppe]

2nd one

Sry bout that

[sterile flame]

Don't worry about it. It seems right enough to me.

[narrow pecan]

hi

[safe steppe]

Hi again, with this question, what would you do to determine if it is valid. Because I dont have a statement to get the negative of which I would use to prove or disprove the statement.

Is the statement the part in the last sentence which I would prove or disprove?

This is what i have so far

[ebon python]

Hi guys, I'm currently stuck on this question:

do we use proof by induction?

what am i trying to prove here?

this is my current working out

but it's wrong because N = 2022 doesn't work

[safe steppe]

If you reach (not a or a) in a resolution proof like this👆, does it mean you have reached a contradiction?

[cloud portal]

why is the overlap between a, b, and c filled in in the solution?

I thought because we are using exclusive or, overlapping regions won't be filled in

[sterile flame]

You can prove that the symmetric difference $A_1\oplus\ldots\oplus A_n$ contains exactly all the elements that belong to an odd number of sets $A_i$

[vital dew]

davide

[sterile flame]

Here $N=6000$ because it satisfies the given inequality. Now, to prove that $\forall n\ge N(2023^n\le n!)$ you can proceed by induction. The case $n=6000$ is obvious. You can now suppose that $2023^n \le n!$ and notice that $2023^n \cdot 2023 = 2023^{n+1}\le (n+1)! = n\cdot n!$. Using the inductive hypotesis the proof is thus concluded.

[vital dew]

davide

[ebon python]

Don't you mean $2023^n \cdot 2023 = 2023^{n+1}\le (n+1)! = (n+1) \cdot n!$?

[vital dew]

clacii

[sterile flame]

Oh yeah, my bad.

In that case $n+1\ge 2023$ as well. So it doesn't affect the proof.

[vital dew]

davide

[ebon python]

In that case would stating that $ n+1\le 2023$ implies $n\le 2022$ be valid?

[vital dew]

clacii

[sterile flame]

Yes, it would.

[ebon python]

And thus the value of $N$ which exists for $2023^n \le n!$ must be 2022?

[vital dew]

clacii

[ebon python]

Is that a valid answer to the question?

this is what i'm confused about because another help said that this is not what the question is trying to ask

because i tried comparing $2023^2022 and 2022!$ and $2022$ was smaller so i'm confused on what i should be doing in this question

[vital dew]

clacii

[ebon python]

My reasoning is that because this is a 'there exists' question, we should find a singular value of $N$ no?

[vital dew]

clacii

[ebon python]

Or is my brain just fried from lack of sleep and not functioning properly 😭

[sterile flame]

Here you're of course trying to find a singular value of $N$, but you also need to prove that, for each $n\ge N$, $2023^n\le n!$. In fact, I found a singular value of $N$ in the proof (which is 6000) and then proved the property that number should have

[vital dew]

davide

[ebon python]

So the question proved itself?

Because i kept assuming it was asking for the lowest value of N but it seems that's not the case

And yeah 6000 is by fact a valid answer for N

idk the wording is just really weird

[sterile flame]

The question is asking you if there 'exists' an $N$ that satisfies the given properties. You don't have to look for the lowest value of $N$...

[vital dew]

davide

[ebon python]

right righttt

yeahh that's why i was confused sorrys

so to answer the question i just need to state that there IS an N that satisfies it, and then i prove it via induction?

[sterile flame]

Exactly

[ebon python]

thank you thank you!

much appreciated

i'll see if there's anything else i'm unsure about when i type it up but i think i should be fine

[ebon python]

oh btw could you just explain why $2023^{n+1}\le n\cdot n!$ I thought I understood this part but I forgot how...

[vital dew]

clacii

[cloud portal]

can anyone explain how this set would be evaluated

i am confused on "001x"

[sterile flame]

Oh you just use the induction hypotesis, which is $2023^n \le n!$ and then rewrite it as $2023\cdot 2023^n \le (n+1)\cdot n!$ which is the wanted inequality. By the way the inequality hold because $n+1 \ge 2023$.

[vital dew]

davide

[cloud portal]

Does it just mean 001x will be appended to each element of {0, 1}^2

[sterile flame]

It could be.

I don't know though, the context might help.

[ebon python]

Do we assume that $n+1\ge 2023$?

[vital dew]

clacii

[ebon python]

Or is that derived from somewhere?

[sterile flame]

n has to be greater than N which is 6000 so...

[cloud portal]

this is the full context

[ebon python]

So we can take the basis value of N and use that?

[sterile flame]

Yes, we can.

[ebon python]

Ahh okok thanks !

[sterile flame]

Oh yeah, then your guess is definitely correct. Also, it would make sense since the powers of ${0,1}$ are in descending order.

[vital dew]

davide

[sterile flame]

Anytime

[safe steppe]

Hi guys, any advice on how to approach this question.

[jolly jolt]

Use a generating function to determine thenumber of positive integers less than 1 million (1 000 000) that contain an odd number of even digits, at most one 1, at least one 3, at most two 5s, and having no restrictions on the number of 7s or 9s
E.g. 000001 == 1

[wicked bolt]

are you familiar with exponential generating functions? i think that is the way to go since the question is basically asking for strings of length 6 made from elements in {0,1,2,3,4,5,6,7,8,9}

[jolly jolt]

I am yes, but the odd number of even digits makes it real tricky

[wicked bolt]

yes actually that is the condition i also don’t know how to encode

[jolly jolt]

😭

[wicked bolt]

well

[jolly jolt]

Trust me, the more you think about it the more lost you get

[wicked bolt]

all the other conditions are on the odd digits at least

maybe uh

handle strings with 1 even digit, 3 even digits, and 5 even digits separately

like make 3 generating functions

if you can do that, adding them up will do it?

[jolly jolt]

How are you supposed to construct them with 3 even digits? For example you could have 696969 but also 662 999 i.e. you can't just 'select' even digits

[wicked bolt]

do you know how to deal with the at most and at least conditions on the odd digits?

[jolly jolt]

Yes, the odd digits arent of concern

[coral parcel]

Can you count strings from the alphabet {1,3,5,7,9,E} that contain at most one 1, at least one 3, at most two 5s and exactly three Es? Then multiply that by 5^3 to account for which even digit each of the three Es is.

[wicked bolt]

that’s what i was thinking but much cleaner than what i was about to send lol

[jolly jolt]

Is this what you mean?

I think I gotcha now

Like thats the generating function for the permutations of length 3 from the 5 even digits

How do I now combine them?

[wicked bolt]

idk what that means tbh

[jolly jolt]

Its just the exponential generating function for the permtations of n objects of length r with repition

For example it could be the permutations with repetitions of length 7 from the set {a,b,c}

n = 3 r = 7

[wicked bolt]

not sure that matches the above image, r is just a dummy variable there

the number of strings of each length would correspond to the coefficients on the terms in the series

[jolly jolt]

Have you solved it yet? I think I have but don't know how to write math in discord

[wicked bolt]

the coefficient on x^7/7! would be that

[jolly jolt]

Yes thats what i mean

[wicked bolt]

i have not but i have the solution in my head

[jolly jolt]

Do you mind putting down dotpoints of yours so I can try to implement it?

[wicked bolt]

ok let me get on my computer then i’ll explain more

[jolly jolt]

Ok thank you

[wicked bolt]

ok back

tbh i'm just gonna steal what troposphere said with a little more detail

[jolly jolt]

It is fine

[wicked bolt]

following that... we can count strings from the alphabet {1,3,5,7,9,E} that contain at most one 1, at least one 3, at most two 5s and exactly three Es (and the same thing with exactly one E, and exactly five Es)

for the three Es case:

i think you know how to encode the functions for the odd digits already (each one should resemble the exponential power series or a truncated version of it or something) and for the Es, do you know that will look like?

and do you understand why {1,3,5,7,9,E} is relevant?

[jolly jolt]

I'm just not sure how to put it together 🥲

[wicked bolt]

i asked two questions about putting it together lol

yes or no to those?

[jolly jolt]

My problem is that when you try to use the formula I sent, it becomes a convolution, so we may be overcounting

[wicked bolt]

wdym a convolution?

[jolly jolt]

So in the entire expression we are looking for the coefficient of 6, but since we are multiplying by an independent power series (the one I sent), the coefficient of 6, becomes the sum of all t's that add to 6,

We only want the one with three

[wicked bolt]

in the end we're going to look for the coefficient of x^6/6! in something right

[wicked bolt]

three Es?

[jolly jolt]

Yes to get all ones possible permutations of 3 even digits from the 5 that we have, this is the coefficient of t^3/3! in the expression I sent abouve with n = 5, but then how do you proceed

[wicked bolt]

nono

it sounds like you're overcomplicating the 3 even digits thing

right now we're just counting strings from the alphabet {1,3,5,7,9,E} that have exactly 3 Es (and all the other conditions)

that doesn't mean have exactly 3 even digits, just literally "E"s

[jolly jolt]

Ok thats easy enough then

Im following at this point

[wicked bolt]

strings like EE51E9

[jolly jolt]

I know how to do this part yes

[wicked bolt]

ok cool

do you know how to "fix" that so that it counts strings with 3 even digits?

[jolly jolt]

No

How do I do this?

[wicked bolt]

you have strings like EE51E9

for each way you could replace the Es with even digits, that's a string with 3 even digits

and there are simply 5^3 ways to do that

[jolly jolt]

So do I just muliply each coefficient by 5^3?

[wicked bolt]

yes

[jolly jolt]

Ok great, thank you for your help, it is very much appreciated

[wicked bolt]

^_^

[wraith mist]

Can I just make an equivalence class however I want so long as I create a partition of a set?

[abstract whale]

Hey guys. I have a question regarding proving programs using induction. When it comes to proving programs that use a while loop, are you supposed to find the loop invariant? How do you find the loop invariant? After you find the loop invariant, what are the next steps?

[faint sphinx]

For a fixed set X, there is a bijective correspondence between set of equivalence classes / partitions on X and equivalence relations on X. That is, every equivalence relation comes from a partition of X, and every partition of X comes from an equivalence relation

[warm flower]

I'm trying to prove that (Z) is a cyclic flat of (M = (E, \beta)) if and only if (E \setminus Z) is a cyclic flat of (M^), and right now I've got to where if (Z) is a cyclic flat then I can show (E \setminus Z) is a flat of (M^) if for (x \in Z), (x \in cl(Z \setminus {x})) but I'm struggling to see if that's true

[vital dew]

StarvinPig

[ember coral]

Can anyone help me with basic proofs

( A ∪ C ) - ( B - A ) = A ∪ ( C - B ). need to understand how to proof this

[sterile turret]

@ember coral can you start that by pulling out the A?

[faint sphinx]

what do you mean

[sterile turret]

Like say i'm working on the left hand side first, A is common in both so would the next step be -> A SOMETHING (C - (B -A))

I can get my notes later, we JUST finished this in the first half of class.

[faint sphinx]

I would just show they are subsets of each other. That the right hand side is a subset of the left hand side shouldn't be too hard. For the left hand side to be a subset of the right, you might want to break it into cases (i.e., you'll have x in A or C such that (something). Then consider the cases x in A and x in C separately)

[glossy marsh]

What would the expression be

[granite forge]

how is it a contradiction? kinda confused.

[elder berry]

c² = 4(m² + n² + m + n) + 2 so it is not divisible by 4

[granite forge]

having trouble understanidng still.

so we said that if they are both odd.

we get c^2 as even

[elder berry]

yes

[granite forge]

and thus c is even

and so we can say c = 2k

[elder berry]

c must be even for c² to be even

[granite forge]

then 4k^2

[elder berry]

mhm

[granite forge]

OH

so using our 2k+1 and 2l + 1

we got an expression not divisible by 4

but c^2 is

but this is a contradiction

because both are equivalent.

[elder berry]

precisely

[rugged scaffold]

can someone help me with this?

[granite forge]

tyvm 🙏

[elder berry]

what are you struggling with?

[rugged scaffold]

graph theory

[wraith mist]

So I can form a set of equivalence classes out of any partition.

[faint sphinx]

It's kinda like partitions = sets of equivalence classes. So you can form an equivalence relation from any partition, for which the partition is the set of equivalence classes

[wraith mist]

Thank you!

[hushed comet]

Can someone help me by providing the main idea behind this graph problem?
link of the problem - https://codeforces.com/problemset/problem/1578/C

[median flint]

What’s a good way to do practice problems online for this course? My professor giving me jack s**t to do.

[regal gate]

is there a nice closed formula for the number of finite tuples formed from the set {1,2,3,..,n} ?

wait, no repetitions allowed

ig its $\sum_{k=0}^n \frac{n!}{(n-k)!}$

[vital dew]

Croqueta

[regal gate]

here Im also counting the zero tuple, but you can start at k=1 if you want

but I dont think you can sum that? 🤔

[ivory badge]

Why can’t you?

Should be something like

k tuples of n is (n choose k) * k! orderings yeah?

Which is what you have summing up no?

[unique dove]

I was wondering, with bijections, is it possible to have a bijection that maps an uncountable infinity to a countable infinity?
ex f: R->Z, f is a bijection

My head is telling me it wouldn't be possible but I cant find anything online to confirm this

[faint sphinx]

nope

one of the important properties about bijections is that, if f : A --> B is a bijection, then A and B have the same cardinality: |A| = |B|. In particular, countable and any uncountable infinity are distinct cardinalities.

[faint sphinx]

In the specific case with R and a countable set, this is pretty much just Cantor's diagonalization argument that this does not work

[unique dove]

ok that makes sense, thanks

[wheat geode]

Charles Petzold has a book, The Annotated Turing. Countability ties in tightly with computability, and is the motivation behind Turing's original work. It's a good read if you're a math/compute nerd.

Tying back into the bijections problem and Cantor's infinites

[vestal bronze]

https://oeis.org/A007526

so no formula i assume

[regal gate]

yeah but no closed form ig (by closed form here I mean something not involving sigma)

[ivory badge]

Fair

[cyan viper]

Hello can i haz some help? Im stuck with this proof:
Can you see whats wrong with it?

Pls ping me if u find something. While i search too

[faint sphinx]

If n = 3, then the LHS is 6 * (5 choose 4) = 6 * 5 = 30, but the right hand side is (4 choose 1)^2 - (4 choose 2) = 4^2 - 6 = 10. So this is false as written.

[faint sphinx]

It looks like it's tru if you replace (n+1 choose 1)^2 with (n+1 choose 2)^2.

[civic iris]

Need some help. Approach?

[cyan viper]

Thank you, sometimes books have mistakes....

[frozen girder]

Think about the two people who shake hands with 0 and n-1 people, then 1 and n-2...

[split jay]

Is this the incorrect negation since theres a then, so would it be a conditional statement?

[glossy osprey]

Alright resident number theorists, help me out if you don't mind.

Is there some general formula that can give me this?

I imagine there isn't.

I know the function exists and there's probably a general algorithm it.

Hold up, wouldn't this always be some number that's a power of two?

[faint sphinx]

no

consider that 6 has 4 divisors, but 8 is the least power of 2 with 4 divisors

[coral parcel]

The smallest number with 4 divisors is 6.

[glossy osprey]

Okay.

hmmm...

[haughty garden]

If the prime factorisation of $N$ is $N = p_1^{a_1} \dots p_k^{a_k}$, then the number of divisors of $N$ is given explicitly by $(a_1 + 1) \dots (a_k + 1)$

[faint sphinx]

dammit you sniped me

[haughty garden]

😳

[glossy osprey]

I think I see it.

[faint sphinx]

Anyways, consider, for instance, that 4 = 2*2. We could write this in the format of the number of divisors above as either (1 + 1) * (1 + 1) or as (3 + 1)

So we would need to choose either 2 distinct primes and multiply them together, or raise one prime to the power 3 in order to have 4 divisors

Clearly, we should be choosing the smallest prime numbers to minimize this integer. So we just have to choose the lesser of 2^1 * 3^1 = 6 and 2^3 = 8

[twilit sundial]

walled on this, im currently trying to write the sum as 2^3n minus something but its not playing nicely

[coral parcel]

And it's not as simple as "always split in as many factors as possible", because the first number with 8 divisors is 2^(4-1)·3^(2-1) = 24 rather than 2^(2-1)·3^(2-1)·5^(2-1) = 30.

[faint sphinx]

Yeah you can reduce it to just checking a few different cases, but it depends on the specific k

There's possibly a nice algorithm for deciding which, but it would be a pain to write

[glossy osprey]

Yea I realized this pretty quickly lol.

[twilit sundial]

the stuff under the limit is like $\frac{1}{2^{3n}}(2^{3n}-\sum^{n-1}_{i=0}\left(\binom{3n}{3i+1}+\binom{3n}{3i+2}\right)$

but idk what to do with that

[vital dew]

elrichardo1337

[glossy osprey]

Thanks it makes sense.

Well it makes sense if I start out with the fact that the number of divisors for a number N is given by (a_1 + 1)... (a_k+1)

But I don't quite understand how (a_1 +1)...(a_k+1) actually counts the number of divisors for a given number N.

[weary tiger]

guys any youtubers that cover discrete mathematics?

im currently taking discrete math for cs

[coral parcel]

Each divisor has the form p1^b1·p2^b2···pn^bn, where b1 must be one of {0,1,2,...,a1} -- that is, a1+1 different possibilities for b1 -- b2 must be one of {0,1,...,a2), and so forth.

[twilit sundial]

^?

[weary tiger]

why is p and c == c instead of false?

[glossy osprey]

Okay, I see.

Thanks a lot.

I'm trying to learn this stuff out of a book on cryptography. The book starts out with chapter dedicated to number theory concepts that'll be crucial for understanding algorithms later on. But maybe I should just start with a number theory book or something.

[twilit sundial]

ive been stuck on this for a while with no idea on how to proceed 😭 tried smth with binomial theorem but it got nowhere

[iron marsh]

Hmmm, for starters, instead of starting with 3n, see what happens if you start with just n, so 1/2^n times the sum of (n,i). This problem is significantly easier. From here, see what happens when you do 2n instead. How much does that change things?

This one also shouldn't be too bad

[twilit sundial]

replacing by $n$ would give $\frac{1}{2^n}\sum^n_{i=0}\binom{n}{i}=1$

[vital dew]

elrichardo1337

[twilit sundial]

and clearly that's invariant in n

hmm for 2n

$\dfrac{1}{2^{2n}}\sum^n_{i=0}\binom{2n}{2i}$

[vital dew]

elrichardo1337

[iron marsh]

Yea, the first one is pretty trivial when you know the identity

[twilit sundial]

so for the 2n case we try writing as $\dfrac{1}{2^{2n}}\left[\sum^n_{i=0}\binom{2n}{i}-\sum^{n-1}_{i=0}\binom{2n}{2i+1}\right]$

or actually

[iron marsh]

not quite

[twilit sundial]

$\frac{1}{2^{2n}}(2^n+(1-1)^n)?$

[vital dew]

elrichardo1337

[twilit sundial]

so by binomial theorem all the terms with odd second argument would cancel

[iron marsh]

Not sure what you did, but that is indeed correct

[vital dew]

elrichardo1337

[twilit sundial]

corrected what i had before but that's probably not the best approach anyway

[iron marsh]

actually no, that isn't quite right just yet

[twilit sundial]

we still need to divide by 2 again i think?

[iron marsh]

Bingo!

[twilit sundial]

so each term of $2^n$ is positive, while all the terms with odd $i$ in $(1-1)^n$ are negative

[vital dew]

elrichardo1337

[twilit sundial]

that leads to duplicates of the terms with even $i,$ so divide through by 2

[vital dew]

elrichardo1337

[iron marsh]

A much simpler observation, which I think you eventually pointed out, is that sum (2n,2i) is exactly half of the total sum of (2n,i)

[twilit sundial]

the issue now is how to prove that for the 3n case

i've tried a similar idea of using various binomial sums to "filter" the ones we don't want

but haven't really gotten anywhere

[iron marsh]

Unlike the n and 2n case, we run into the problem that this isn't always the same for any choice of n like the others were

However, based on our observations, what do you think the limit might be?

[twilit sundial]

probably 1/3? (the textbook for my class says as much) but i still need to prove it lmao

[iron marsh]

Yep, from what I'm seeing case by case, it's definitely converging to 1/3

Not quite a proof, but what we have now is a goal

[twilit sundial]

so we want to filter out everything that's 1 or 2 mod 3

ohhhhhh wait

is it gonna involve multinomials

hmm actually idk

[iron marsh]

Tbh, I don't know what it's gonna take yet. Still trying to think on it

[twilit sundial]

since the only reason that the (1-1)^n trick works for 2n is that the sign of each term is directly tied to the parity of its index

how do we get smth that selectively changes sign to negative at 1 mod 3 or 2 mod 3?

[iron marsh]

So it seems like what we need to establish is that $\sum_{i=0}^n \binom{3n}{3i} \approx \frac{2^{3n}}{3}$ for large enough $n$.

[vital dew]

dackid

[twilit sundial]

yea

earlier i had wolfram alpha try this sum and it had a bunch of other $(-1)^n$ terms slapped on at the end, don't know how those get there tho

[vital dew]

elrichardo1337

[twilit sundial]

if i try smth like $(1-2)^{3n}$ the $2^i$s are just gonna grow out of control

[vital dew]

elrichardo1337

[iron marsh]

Ngl, this one's hurting my brain a bit

[twilit sundial]

yea lol

[iron marsh]

Something I found interesting is that for 3,6, and 9, the sums all evaluated to something of the form k/(3k+-2).

[twilit sundial]

:o

and clearly that converges to 1/3 for large k

[iron marsh]

For 3, it was 2/8, for 6 it was 22/64, and for 9 it is 170/512

It does indeed

Now, the question is whether this property holds as n gets large

[twilit sundial]

according to wolfram this is what we're looking to prove

and that would explain the $\pm 2$ you were finding

[vital dew]

elrichardo1337