discrete-math

[hidden totem]

because if you plug in n=0

you can prove the case for P(0)

which is fine but not necessary

the problem only asks to prove from P(1) onwards

you CAN start with P(0)

[muted basin]

im just utterly confused

if we need 2 bases for strong induction

why wouldnt we want the decremented base from our first base test

[hidden totem]

you can use a single base for strong induction

strong induction is about the inductive step

so look

your inductive step is

if P(n-1) and P(n), then P(n+1)

the strong inductive step is

if P(n) for all n from something to n, then P(n+1)

this is way more powerful than you need

but you can still use it with a single base case

how many base cases is not what makes it strong induction

again

you CAN use P(0) and P(1) as a base

ive said that like a hundred times already

its a valid proof

but you dont HAVE to do that

because the problem does not ask you to prove P(0)

it only asks you of P(1) onwards

thats why it chooses P(1) and P(2) as the base cases

if i asked you to prove P(n) for all integers from -3 onwards

why would you start with a P(-4) base case

[muted basin]

i just dont understand why you need P(2) here or a second base case at all

when induction implies it already

[hidden totem]

right here

induction does NOT imply it

you must assume P(2) in order for this to hold true

but you have not yet established P(2)

you ONLY have a P(1) base case

without P(2), you cannot do this substitution, so your proof fails to prove P(3)

and if you dont have P(3), then you dont have P(4)

[muted basin]

im confused on why youre proving F(5) in the first place

it never occurs in the problem or is needed

[hidden totem]

how would you prove P(3)

show me the steps

[muted basin]

our induction conclusion is P(n+1) = “F(n+4) = 2F(n+2) + F(n+1)”

for all n >= 1

[hidden totem]

no, not correct

[hidden totem]

this is wrong

also your induction sentence is not complete

a simple inductive step to prove would be like

IF P(n) THEN P(n+1)

[muted basin]

the way my prof described induction conclusion is its what we want to go for

by manipulating the hypotht

hypothesis

[hidden totem]

write me the FULL inductive statement to prove

write it in FULL

[muted basin]

i dont know what that means. he has us do it procedurally with base case, inductive hypothesis which is usually P(n) or whatever statement it is, induction conclusion which is P(n+1), and then inductive step is the proof

[hidden totem]

ok so thats the problem

you dont know how induction works yet

stop saying prof said this or prof said that

the problem is your logic isnt clear

so lets look at simple induction first

[muted basin]

im just telling you what i know based on what ive been taught

[hidden totem]

ok well stop

[muted basin]

he expects us to solve it in only that format

[hidden totem]

do you want to assert what you remembered from class for which you dont know the reasoning for

or do you want to actually learn how it works and actually follow my explanation

because im volunteering my free time here

[muted basin]

i want to learn how it works but i just simply dont understand

[hidden totem]

then for a minute

forget whatever your prof said

and focus on the logic of my explanation

ok?

or im out

[muted basin]

can do

[hidden totem]

ok

so lets understand simple induction first

suppose we want to show that P(n) is true for all n at least 0

we cannot brute force this

because there are an infinite number of cases to test, yes?

[muted basin]

yes

[hidden totem]

ok so we start by proving P(0)

now we prove the following statement:

IF P(n), THEN P(n+1)

once we show this statement is true

can you see that this means:

IF P(0), THEN P(1)

and now we have P(1)

is this clear?

[muted basin]

yes

[hidden totem]

ok

but can you see that this only works if we have P(0)

without P(0), we cannot show P(1)

[muted basin]

right

[hidden totem]

ok good

now how would we prove P(2)

[muted basin]

my intuition says prove P(1)

[hidden totem]

(which we have now)

[muted basin]

but also if we proved P(0) then we can show P(1)

[hidden totem]

yes

[muted basin]

so instantly P(2) works

[hidden totem]

bingo

can you see that the starting seed of P(0) gives us everything

up to infinity

[muted basin]

yes

[hidden totem]

ok good

so now lets summarize

we are trying to prove:

P(n) for all n at least 0

we do this by breaking this into two things to prove:

P(0)
IF P(n), THEN P(n+1)

can you now see why the "if then" is critical

the inductive step in full is "IF P(n), THEN P(n+1)"

at least for this simple induction case

following?

[muted basin]

right

[hidden totem]

ok

now lets see what happens if i do the following

suppose i want to prove the same thing

that P(n) from 0 on

i once again have P(0)

but this time, i have proved the statement:

IF P(n-1) AND P(n), THEN P(n+1)

question, how would we prove P(3)?

[muted basin]

i would need to prove P(n+1) and P(n+2)

[hidden totem]

no

what even is n here?

what does that even mean?

[muted basin]

sorry i guess rather P(1) and P(2)

[hidden totem]

good

actually i made a mistake

meant to write P(2) but you got the idea

we are definitely missing P(1)

if we have that, then we have P(2)

and then we have P(3)

and so on, this keeps going again

but notice we need two base cases now

so far so good?

[muted basin]

yes

[hidden totem]

ok now for the problem you are trying to solve

can you now write your inductive step IN FULL in terms of either the F statement or just using the P placeholder?

[muted basin]

i think im starting to get the picture a little bit better

here one sec

We want to prove F(n+3) = 2F(n+1) + F(n) for n >= 1.

Base: P(n) = P(1) = F(4) = 2*F(2) + F(1) which holds
Because we want to prove a recurrence relation we need the gaps as well, and P(n+1) works here as a base case to fit that P(n-1) and P(n) then P(n+1). F(5) is valid so now we have, in regards to the example you gave, the equivalent of P(1) and P(2) so we can find P(3) now.

this is where my last gap of confusion is

in this problems context P(2) is the F(5) if n is 1

but were still safe to make the conclusion goal F(n+4) right

[hidden totem]

I think you got the idea here about whats wrong with your solution

[muted basin]

we want it to be equal to 2F(n+2) + F(n+1)

[hidden totem]

im not sure what this means

because

the F(n+3) = blah

and the F(n+4) = blah

is the same thing? it just depends on what n is

if n=2 in the first one, thats the same as n=1 in the second one

so like

if you can show F(n+3) = blah for n at least 3

that is the exact same thing as F(n+4) = blah for n at least 2

does that make sense?

[muted basin]

yeah

[hidden totem]

ok cool

anything else unclear?

does everything make sense now?

[muted basin]

yeah i think

let me rephrase to clarify

the P(n) we want to prove has 2 previous terms

so we meed two succeeding base cases to prove thst relation works

[hidden totem]

perfect

remember that the inductive step is always an "if then" statement

its not something you just take for granted

[muted basin]

gotcha, thank you for the help i appreciate it a lot

[grand totem]

a bit late but this particular problem won't give too much insight into induction since it admits a very quick direct proof
||F(n + 3) = F(n + 2) + F(n + 1) = F(n + 1) + F(n) + F(n + 1) = 2F(n + 1) + F(n)||

[lethal linden]

hax

[stray reef]

#prealg-and-algebra

[stoic sky]

can someone help me with this True or False question

If a 10-vertex graph G has 2 edge-disjoint spanning trees, then G contains at least 38 different cycles

[stray reef]

do you think it's true or do you think it's false

[stoic sky]

hmmm i do know that the edges must be at least 18

im trying to draw some small example atm

but im leaning toward true

also i know that adding an edge to a tree increase it cycle count by 1

so hmm

[tardy tangle]

Does every finite sequence of digits occur infinitely many times in the decimal representation of π?

[odd heart]

We don't know

We don't even know if every finite sequence of digits occurs at least once.

[tardy tangle]

Interesting

I remember Harold Finch in the TV show Person of Interest said that every finite sequence does occur. But of course that was a fictional show

This line of thinking seems to give rise to a whole new system for categorizing irrational numbers

[odd heart]

https://en.wikipedia.org/wiki/Disjunctive_sequence

There's this ,but as said, we don't know whether pi is disjunctive

[odd heart]

Actually if every finite sequence appears, then every finite sequence appears infinitely many times, so it's going to be equivalent

[odd heart]

A related, stronger notion is normality (https://en.wikipedia.org/wiki/Normal_number)

Every normal number is disjunctive, and every disjunctive number is irrational, but the converse implications don't hold (and we do know that pi is irrational, but we don't know whether it's disjunctive, let alone normal)

[hidden totem]

normal feels significantly stronger than disjunctive

i wonder if there is anything in between other than n number of bases where it is disjunctive

like some kind of more natural property

[iron marsh]

I could use some help with this. It has to do with the general binomial functions, but that dang and seeing it as a product of 2 sums, but that 2n-k in the 2nd binomial coefficient is really messing with me!

In particular, these coefficients correspond to the product:
$\sum_{k} \binom{2k-1}{k} \frac{(-1)^{k-1}}{2k-1} \cdot \sum_{k} \binom{2k+2n-1}{n+k} \frac{1}{2k+2n-1}$

[vital dew]

dackid

[iron marsh]

It's that dang n+k that is messing things up

Note the first sum is $B_2(-1)^{-1}$, where $B$ refers to the general binomial function

[vital dew]

dackid

[iron marsh]

Better question: why is this true? In particular, the end is almost Vandermonde convolution, but where'd that extra fraction go?

[median flame]

What are the possible rational outputs for $\cos\left(\frac{2}{3}\arccos\left(x\sqrt{3}\right)\right)$ if x is rational?
According to Niven's theorem, the only rational outputs of cos(n) are -1, -1/2, 0, 1/2, or 1 if n is a rational multiple of pi (or just rational, for degrees), but I'm not sure if those cases where n don't meet that stipulation are just cases like cos(arccos(m)), etc.

[vital dew]

Tiger Ros

[drifting sand]

Sanity check, if a planar embedding with n vertices has 3n-6 edges, every face is bounded by 3 edges right

n >=3

[torn sierra]

Is there any non- bashy solution for this problem ?

[primal valley]

any idea on how to do this

i got 12,3,5 using a spiral strategy but am very unsure of my answer

[tired summit]

Yeah

[fossil torrent]

The 3, and 5, seems right. But 12? I got 13.

[granite wharf]

any hint on this? , I tried to apply induction, but I got stuck in proving P(n) --> P(n+1), I dont really understand what happens to the graph when adding one node, and I am not sure if it will work for the induction step

[stray reef]

i don't think ordinary induction is gonna do you much good

strong induction somehow maybe?

[primal valley]

yea realized i did it wrong, got 13 also

[lethal linden]

What are you inducting on?

[lethal linden]

Hint: For every vertex v, either deg(v) <= |V|/2 or deg(v) > |V|/2

[granite wharf]

thanks , I will check this approach

[bright zenith]

Given $d, k, n$, how many $k-$element subsets $S$ of ${1, 2, \ldots, n }$ are such that any two distinct elements of $S$ differ by at least $d$?

[vital dew]

phoenixperson

[tulip cliff]

Revisited an old topic, hopefully it's better this time! https://www.youtube.com/watch?v=rvTkN2wDdm0

[median flame]

can $c$ in $c=\sqrt{a^{3}b-ab^{3}}$ ever be in integer if $a$ and $b$ are integers?

[vital dew]

Tiger Ros

[median flame]

(and ab=/=0)

[rustic star]

fork

[rustic star]

a = 1, b = 1 gives c = 0

ab = 1

a = b all gives 0

because the thingy under the root is ab(a-b)(a+b)

[median flame]

oh right, i should've said a=/=b lol

[hearty spoke]

What if you have an alternating series that alternates a non-integer amount of times

For example
(-1)^(n/zeta(2))/n

How would you calculate the convergence of such a series and what it even converges to

?

[stray reef]

raising -1 to a non integer power is highly sus

[bright zenith]

Source for solution:

https://math.stackexchange.com/questions/4791237/selecting-k-elements-from-the-set-n-such-that-the-numbers-selected-differ

Let $A$ be the set of sequences we want to count, and $B$ be the set of strictly increasing functions from $[k] = {1, \ldots k }$ to $[n - (d - 1)k + (d - 1)]$. They correspond bijectively by $H:A \to B$ given by $H(f)(i) = f(i) - 2i + 2$ for given $f$ in $A$, with inverse being $H^{-1}(g)(i) = g(i) + 2i - 2$. So the answer is $\binom{n - (d - 1)k + d - 1)}{k}$. If anybody cared, I leave to them to check that the functions go to the appropriate ranges.

[vital dew]

phoenixperson

[echo niche]

OK SO UR TELLING ME THE SUM OF ALL NATURAL NUMBERS IS -1/12 AND THE HARMONIC SERIES DIVERGES???

[fossil mural]

nobody is telling you that

1 + 2 + 3 + 4 + ... diverges

[echo niche]

I mean ramanujan proved its -1/12

[fossil mural]

no he didn't

[echo niche]

Yes he did 👍

[fossil mural]

none of the partial sums of 1 + 2 + 3 + 4 + ... are negative, so none of them are ever within 1/12 of -1/12, so it doesn't converge to -1/12

[echo niche]

U can google more proofs of it

[hearty spoke]

Isnt it analytical continuation?

[fossil mural]

he guessed (i'm not convinced that what he did constituted a proof) that there is a complicated relationship between 1 + 2 + 3 + 4 + ... and the number -1/12

[echo niche]

Ye

[fossil mural]

this relationship is not equality, because 1 + 2 + 3 + 4 + ... diverges

in particular it approaches infinity, because for every N, after ceil(N) terms the partial sums are all above N

[hearty spoke]

If its not continuing the domain of the zeta function then it diverges but if it does continue the domain of the zeta function it converges

iirc

[fossil mural]

you can say a lot of interesting stuff about like, zeta(-1) or whatever, but none of those are "actually the sequence 1 + 2 + 3 + 4 + ... converges", because it doesn't

[hearty spoke]

I agree

[echo niche]

Use the dirichlet regularization

[hearty spoke]

It doesnt converge on its own man

If you apply stuff then ok

But if you dont

[fossil mural]

or more precisely, you can say things about "1 + 2 + 3 + 4 + ..." if you use a different notion of what an infinite sum is

[hearty spoke]

Let it go

[fossil mural]

if you use the usual notion of an infinite sum, then "1 + 2 + 3 + 4 + ..." is the limit of its partial sums 1, 3, 6, 10, 15, 21, etc., and the partial sums are monotonically increasing and unbounded so they approach infinity

[hearty spoke]

Also guys i made something a little interesting
I turned the oplus function into an infinite version
The oplus function btw is the one 3b1b referenced in his video about the triangle of power where its (a^-1 - b^-1)^-1 and so i extended the function to be infinite wheres its basically
1 oplus 2 oplus 3 oplus 4…
I haven’t fully refined it or even know all of its nature but I want to share it to see if anyone can add anything to it

[echo niche]

,w zeta(-1)

[vital dew]

Results provided by WolframAlpha

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

Requested by sigmaboy0222

[fossil mural]

yep, zeta(-1) is equal to -1/12 and isn't equal to 1 + 2 + 3 + 4 + ... which diverges

the fact that if you take the formula that defines zeta for inputs with real part > 1 and just naively plug in -1 and rearrange you get 1 + 2 + 3 + 4 + ... isn't really relevant because the real part of -1 is not > 1, so the actual definition of the zeta function there isn't that it's an infinite sum, it's an analytic continuation

[echo niche]

Ok zetax=∑1/k^x

[fossil mural]

that's true if Re(x) > 1

the right-hand side isn't defined if, for instance, x = -1

so if you're taking this as your definition of zeta, then zeta(-1) isn't defined

[echo niche]

🤨

Fine

But why does the harmonic series also diverge?

[fossil mural]

well it's also monotonically increasing and unbounded, so it also goes to infinity

[hearty spoke]

1 not > and including 1 plus what bee said

[fossil mural]

the counterintuitive part here is that it's unbounded, but if you just
1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + ...
decrease each term to the nearest power of two
1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + ...

now if you group them together, 1/2, then 1/4 + 1/4 = 1/2, then 1/8 + 1/8 + 1/8 + 1/8 = 1/2

you get 2^(k-1) copies of 1/2^k, which always sums to 1/2

so it ends up as just 1/2 + 1/2 + 1/2 + 1/2 + 1/2 + ... which clearly diverges to +inf

[echo niche]

I read that every little sum is bigger than 1/2 so thats why

[fossil mural]

and the partial sums of the harmonic series are strictly bigger than this, so, they also diverge to +inf

[hearty spoke]

Does the alternating series of zeta(-1) converge or oscillate?

[fossil mural]

...well zeta(-1) isn't a series, do you mean 1 - 2 + 3 - 4 + 5 - 6 + ...?

that diverges, its partial sums are 1, -1, 2, -2, 3, -3, etc

so it doesn't converge to anything (not even positive or negative infinity), it just keeps flipping between big positive numbers and big negative numbers

[echo niche]

Using other things its 1/4

[fossil mural]

1 - 2 + 3 - 4 + 5 - 6 + ... is not 1/4

some other notion of summation applied to the sequence 1, -2, 3, -4, 5, -6, ..., is 1/4

[echo niche]

It keeps bouncing between 1 and -1

Oh nvm

[fossil mural]

...no it doesn't

[glossy roost]

Hi, I have a question about solving for the variance of a random variable. Since Var[X] = E[X^2] - (E[X])^2 and we can easily solve for E[X] using linearity of expectation, is there a similar method that we can use to solve for E[X^2] or do we always need to compute it manually using the formula?

[twilit sundial]

for some discrete distributions you can use indicator variables (specifically computing the moments of the number of events that occur), see 7.3 in ross first course in probability for some examples

<@&268886789983436800>

[hearty spoke]

Testing out TeXit

$x$ - $y$ = $5$,
$x$ = $zeta($y$)$

[vital dew]

Cheetle

[true venture]

#latex-testing

If I have a collection of n distinct subsets of N, all being of cardinality k, how many different collections can I have if collections with a similar intersection pattern are considered the same?

For example: n=2, k=2 there are two collections I can have (1,2),(1,3) and (1,2),(3,4).
The collections (1,2), (1,3) and (1,2),(1,4) are considered the same as they both have 2 sets with 1 element in both.

I'd think there is some binomial expression T(n,k) for this, or maybe it is better rephrased with graphs or something?

[true venture]

Think these collections can be thought of as hypergraphs

[true venture]

as I have written above the hypergraphs would be unlabeled, but maybe it is easier to consider labeled

My motivation for this is looking at all collections of subsets of [n] of the same size. For example for [3] and subsets of size 2, there are the collections ((1,2)), ((1,3)), ((2,3)), ((1,2),(1,3)), ((1,2),(2,3)), ((1,3),(2,3)), ((1,2),(1,3),(2,3)). So there are 3 collections with a single element, 3 with two elements and 1 with 3 elements.

[stray reef]

#bots but also this is not how to use TeX. dollars should enclose entire formulas and not individual symbols.

[quick folio]

To do that, consider instead $x-y = 5, x = \zeta(y)$

[vital dew]

HChan

[strong cloud]

i forgot this place exist

well

[vital dew]

theaveragejoe6029

[limpid coyote]

I only just realised that there was an error in formatting. I'll resend it now lol. sorry.

So I’m trying to solve $x^{134843} = 19$ mod $203299$ I’ve found that 203299 is semi prime and factors into 773 and 263 by using difference of squares. So I can solve it in two equations and combine it later using crt. So basically, I’ve got the two equations and I reduce them using fermats little theorem and I end up getting as one of them $x^{175} = 19 $ mod $ 263$ but I have no idea where to go from there.

[vital dew]

theaveragejoe6029

[twilit sundial]

you can probably reduce further by looking at $x^{131}?$

[vital dew]

elrichardo1337

[twilit sundial]

for mod 263

[limpid coyote]

how come? Sorry, I don't see how.

[light mango]

this might be a stupid question but can some one help me understand how the last step of the kv map is determined? i don't really get how the biconditional i.e if and only if is evaluated. why is the bottom row shaded for this?

[light mango]

got it never mind

[drowsy frost]

can i ask questions here?

[lethal linden]

!da2a

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[torn sierra]

I am stuck on this. Can anyone help ?

[mild aspen]

can anyone give me a small crash course on group theory and graph theory for exam ?

[torn sierra]

I want to study Group theory and Graph theory. Does anyone want to be my study partner ?

[copper inlet]

Yes

[hidden totem]

so i dont have a solution to this problem unfortunately

but i do have an answer

https://oeis.org/A000757

basically you do this:
||write out the sequence n! in a row, prepending a 1 to the front
then continue taking finite differences at each row
the diagonal along the left edge is your sequence that solves your problem generally, find the 7th term for your answer (remember it indexes from 0, not 1)||

however i am now mega interested in this problem and will be looking for a solution

[old hatch]

Hello ✌️

I'm studying discrete mathematics, currently I'm in the applications part of the principle of mathematical induction, and I ended up coming across the following problem:

Prove that for every n greater than 3 there exists a convex n-gon with exactly 3 acute angles.

What I've tried so far:

I started with an equilateral triangle ABC, and I kept adding vertices on the BC side, it turns out that angle A is still acute, and B,C too because they are angles between a chord and a radius, but I don't know how to put this into an induction... (this exercise is in a book I'm using as a study guide, but it's in Portuguese, so I'm trying my best to translate my problem)

Does anyone have any suggestions on how to start demonstrating for k+1?

[hidden totem]

so lets say the statement you want to prove is P(n) for all relevant n

in this case, P(n) = "there exists a convex n-gon with exactly 3 acute angles"

and you want to prove this for all n>3

there are two key steps to simple induction: the base step (prove P(4) in this case) and the inductive step, which is

if P(k), then P(k+1)

so to do the inductive step, you first assume that P(k) works

in this case it means taking the polygon that satisfied the conditions of P(k)

and then showing that you can apply your steps to add a vertex so that you get a polygon that prove P(k+1)

[sick grail]

(I also have a suspicion that there has been a mistranslation and it is quite likely that in Engish it would be n greater than or equal to 3, since taking P(3) and not P(4) as the base case makes a lot more sense)

[trim thicket]

i have this question and i dont get what its asking

theres no other context given
it also doesnt say like $k_{0}=0,k_{1}=1$ or something like that

it also doesnt say what T(n) could also possibly equal to

[vital dew]

2ndchar

[lethal linden]

Really? There's no other context? It's not contained on a larger page? The expressions k_n,r_n, T(n), etc. don't occur anywhere previous in the text?

[trim thicket]

nope

i asked my classmates

they're clueless too

i just emailed the teacher

tbh i mostly wanted a sanity check because

i thought this was too little information

but like i wasnt sure if i was just being really dumb or something

if the context is in the textbook or something

theres not even like a line that says "go look to page ??? for this question"

i dont understand 😭

[hidden totem]

100% not enough information

[trim thicket]

great, now how the heck am i gonna explain that to my teacher 😭
because i emailed them about it and they said
"Prove the second expression by using the first"
which is not helpful in the least????????

im not confident in my math terms but

so we dont know:
k_n's definition
k_n initial conditions
what T(n) equals

[hidden totem]

@torn sierra ooooh from the spoiler tags i gave, i found a lead:

||let A(n) be the number of ways to seat n people according to the conditions of the problem

A(n) + A(n+1) = D(n), where D(n) is the number of derangements of n objects||

[sour magnet]

Can somebody help me with finding the discrete Fourier transform of signum function in discrete time domain?

[worldly fulcrum]

this is wild. would love to get an update on this

[lethal linden]

I'm guessing based on the form and names that a candidate for $T(n)$ is the n-th triangular number, i.e., $$T(n) = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$$

And that $r_n$ is somehow related to remainders. Maybe you're in a class that's talking about algorithms or circuits for adding binary numbers, like adders and half-adders?

[vital dew]

Cufflink

[outer bridge]

what should be the answer of this question?

: not home work exercise it is a workbook question that i am stuck at

[hidden totem]

ignoring the answer choices, how would you solve this?

[bright zenith]

What's an explicit bijection between the compositions of size n with k parts (1 <= k <= n), and the compositions of the same size of (n + 1 - k) parts? I have nothing to show for the time I've spent thinking about it so I guess I'll spend some time reviewing and stuff . Fingers crossed I'm not being overly dumb......

Wait you could just translate a composition (a_1, ... , a_k) to the word 0^(a_1 - 1)1...10^(a_k - 1). Then switch that to 1^(a_1 - 1)0........01^(a_k - 1) to get a composition in (n + k - 1) parts. Then this mapping is its own bijective inverse . Any kinks in this?

[twilit sundial]

I’m trying to count the number of (nonisomorphic) 8 participant tournament brackets with “depth” 4 (ie the largest number of matches someone can play is 4); I’m getting 7 but some online sources are saying.6, where am I overcounting?

[hidden totem]

wait im confused, are these compositions or weak compositions?

suppose n=4, k=2

you could do like (2,2)

but now you want a composition with n-1+k parts, which is 5

you cant do this unless you allow zero

also based on your word method, if im understanding correctly, (2,2) would give 01, which you flip to 10, but i dont see how this word converts back to a composition in a different number of parts

also i dont think it works, no matter whether its a composition or weak composition

[twilit sundial]

seems like you could just use binomial coefficients?

[bright zenith]

If it starts or ends iwth a 1, it's assumed to have a "0" before (if it starts with a 1) or after (if it ends with a 1) , with an exponent being with a (a_1 - 1) or (a_(x) - 1), where a_i = 1. So then the difference is effectively 0, which is why it doesn't appear. Forgot to mention that part.

So for example, 010 turns to 101. The middle 0 gives (a_2 - 1) = 1, so a_2 = 2. Then the "first" and "last" 0s gives 2 more +1s, completing the composition. But those wouldn't get switched with the mapping

Edit: No wait I'm dumb it works. First has 4 components, 2 parts. Seconds has 4 + 1 - 2 = 3 parts.

[twilit sundial]

or ||swap the balls for dividers and vice versa||

[hidden totem]

i reconstructed the same cases myself recursively, i think 7 is correct

[twilit sundial]

nice so the online sources might be wrong

[hidden totem]

oh you meant n+1-k

you typed n-1+k earlier so i got hella confused

[bright zenith]

ohhh my bad!

sorry for taking up your time

[twilit sundial]

https://oeis.org/A002083 which is strange bc taking all the depth cases together gets an answer off by one from what this sequence would suggest

am I tripping

[hidden totem]

submit a correction

rare to see an error in oeis, amusing

[twilit sundial]

lmao

hopefully I’m not just taking crazy pills

[hidden totem]

we will see

i checked your 7 person 4 depth case but i didn't look into this larger one yet

but if youre taking crazy pills then so am i

ill check in detail soon

[twilit sundial]

7?

[hidden totem]

er 8 person

typo

[twilit sundial]

lmao

[hidden totem]

ok so here's what i figured out

let $f(n,k)$ be the number of ways to tournament n people at k depth

[vital dew]

Cozmogrgdfschkipkhrshtensi

[hidden totem]

we have to start f(1,0) = 1, f(2,1) = 1, all other f(1,k) and f(2,k) = 0

we have a recursive relationship:
$$f(n,k) = \left[-\frac{f(n/2, k-1)^2-n/2)}{2}\right] + \sum_{i=0}^{n-1} \sum_{j=0}^k f(i,k) f(n-i,j)$$

I obtained this by saying:

ok let's suppose we want to find the number of ways to tournament 8 people at depth 4

the very last finals at the top contributes one "depth" and has two nodes, left and right

wlog assume the left node goes the full depth, maybe the right node matches

[vital dew]

Cozmogrgdfschkipkhrshtensi

[hidden totem]

we check by doing like

the left node is a depth 3, and the right node has depth up to 3, add all the cases where the total number of people in the two nodes add up to 8

but the ugly thing in brackets is subtracting out the overcounted cases in the specific case where n is even only

because let's say you're counting 14 people at depth 5, you could split the two nodes into something with 7 people at depth 4

there are 5 of these cases, let's call them A-E

you could count AB and then count BA, so you gotta remove these

building this table out using this formula, I get:

  | 0 1 2 3 4 5 6 7
-------------------
1 | 1 0 0 0 0 0 0 0
2 | 0 1 0 0 0 0 0 0
3 | 0 0 1 0 0 0 0 0
4 | 0 0 1 1 0 0 0 0
5 | 0 0 0 2 1 0 0 0
6 | 0 0 0 2 3 1 0 0
7 | 0 0 0 1 5 4 1 0
8 | 0 0 0 1 7 9 5 1

where n goes down, k goes across

and this matches what you have

i would still need to write this out in a program to fully test it

might do that later

lemme know if my methodology looks correct

[twilit sundial]

yea this looks right

[twilit sundial]

the discrepancy is at T(8,4)

[scarlet oxide]

is this a typo?

should it not be n-1

[oblique pelican]

Yeah that's a typo

[hidden totem]

# cache values
vals = {}

# actually compute f(n,k)
def f(n,k):
    # some base cases
    if n==1:
        if k==0: return 1
        return 0
    if k==0: return 0
    if n==2:
        if k==1: return 1
        return 0
    if k==1: return 0

    # check if already cached
    if (n,k) in vals:
        #print('cached f(' + str(n) + ',' + str(k) + ') = ' + str(vals[(n,k)]))
        return vals[(n,k)]
    
    # eval sum
    #print('evaluating f(' + str(n) + ',' + str(k) + ')')
    sum = 0
    # we don't want to repeat like f(6,4)*f(7,4) and f(7,4)*f(6,4)
    if n%2 == 0:
        start = n//2
    else:
        start = n//2+1
    # sum all the cases
    for i in range(start,n):
        for j in range(k):
            #print('adding f('+str(i)+','+str(k-1)+')*f('+str(n-i)+','+str(j)+')')
            a = f(i,k-1) # left node
            b = f(n-i,j) # right node
            #if a != 0 and b != 0: print(str(a) + '*' + str(b))
            sum += a*b
    # still some overcounting cases within like f(6,4)*f(6,4)
    # f(6,4) = 3, so let's say those trees are A, B, C
    # you will overcount A-B and B-A, so we remove these
    if n%2 == 0:
        over = f(start,k-1)
        adj = (over*(over - 1))//2
        #print("adjust " + str(adj))
        sum -= adj
    
    # cache the value
    vals[(n,k)] = sum
    
    #print('calc f(' + str(n) + ',' + str(k) + ') = ' + str(sum))
    return sum

# print table
for n in range(11):
    row_ele = []
    for k in range(11):
        v = str(f(n,k))
        v = ' '*(4-len(v))+v
        row_ele.append(v)
    print(' '.join(row_ele))

it seems the discrepency at T(8,4) is also causing a cascade of wrong values later on

but maybe my code/logic is just gigabad

it's a lot messier than i expected and so i suspect I might have made a mistake somewhere

the sum I wrote earlier was actually slightly wrong in a couple of places, found the problems when I wrote the code

let me know if you end up checking this

i kept my debugging prints if you need them lol

i suppose the next step could be to write a program that actually prints all the trees visually to be explicit

[true venture]

nice recurence, why do you all think the row sums of this triangle should be A002083?

Say I have a length n word over some k-ary alphabet {1,2,...k} for example a length 4 word over 3-ary aphabet is 1132. Then I define an equivalence class to be the words that can be reached by some permutation on the letters, ex. 1132 is similar to 2213, 3312, ect. How many equivalence classes are there for length n words over a k-ary alphabet?

In that case the relative order of the letters does not matter, but adding that reqirement seems interesting too.

[true venture]

Is what your counting the same as the comment on that page about ordered trees?

[twilit sundial]

nope, see my earlier diagrams

[true venture]

Oh I see

[true venture]

If the number of these tournaments is not A002083, you should add it as a new sequence

[gaunt nest]

These are called necklaces: https://en.m.wikipedia.org/wiki/Necklace_(combinatorics)

You can count them with orbit stabilizer

[true venture]

Oh, they are the same?

[gaunt nest]

Sorry, are what the same as what?

[true venture]

Words that are equivalent by permutung the groups of letters.

I wasn't thinking of rotating the letters so not seeing how they are necklaces. I probably don't see it yet

[gaunt nest]

Oh, you want arbitrary permutations, not just cyclic?

Ah I see I misread

[true venture]

I think yes

[gaunt nest]

That should be easy to count, it's just this, right? https://mathworld.wolfram.com/Multichoose.html

[true venture]

Hmm I need a better definition, like the blocks of equal letters stay constant, but some arbitarty permutation swaps the letters

If it's just binomial coeff I will facepalm

[gaunt nest]

Oh you're permuting the labels not the string itself

[true venture]

Yes

[gaunt nest]

Gotcha. I should read more carefully lmao

[true venture]

Np

[gaunt nest]

I suspect the forbidden tools would know the answer 🙂

[true venture]

Is that a user?

[gaunt nest]

I mean chatgpt etc

Which is discouraged for obvious reasons on this discord

[true venture]

Oh lol, I will first write some code to brute force small n and check the oeis, but I'm lazy rn

I feel like this will be hard to explain to gpt

But let me try

[gaunt nest]

https://en.m.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind I think your thing is the sum of the first k of these?

Well, sum of s(n,i) times (n choose i) times i!

[true venture]

Ah, I see it. As each pattern of letters just partitions the set of n letters

Thanks!

[gaunt nest]

Right

[true venture]

But the second case where say 113 and 112 are equivalent but not 221...

[gaunt nest]

Stirling counts nonempty partitions which is where the tricky bit comes in

[true venture]

Yes here for a n letter word I want all n letters

Or some letter pattern can't have 0 letters

[gaunt nest]

This case looks kind of annoying but I imagine you could still do it with Stirling

[true venture]

Yea that's what I mainly wanted to know, is what known combo object I was getting at

[gaunt nest]

221 is also equivalent to 331 right

[true venture]

Yes

Also gpt got to integer partitions, so maybe after some more correcting it would have gotten to Stirling2 😵‍💫

[gaunt nest]

So maybe you can start by saying, for a fixed number of letters being used, how many are there. So for 221 and 331 there are exactly 2 groups, and all the possibilities are

AAB, ABB, ABA

(have I missed any)?

That's just Stirling 2

Then from there you can say, how many ways can I choose 1 <= A < B <= k

And factor that out, if that makes sense

Then sum over number of groups?

[true venture]

221 and 331 are one group they are similar

[gaunt nest]

Right

Uh, I'm using "group" to mean something different

[true venture]

Oh you mean possibilities with two groups ic

I think I see what you mean

[gaunt nest]

IOW,

• take an equivalence class like {331, 332, 221}
• for each element, there are let's say i <= k distinct letters, i does not change within a single class
• reorder with each of the i! to get a new equivalence class, in this case i=2

{113, 223, 112}

These all used to be equivalent but aren't now.

Like there used to be a class of size 6 and now there are 2 of size 3

I think you just need to add or remove a factor of I! From the sum above

[true venture]

Nice

[gaunt nest]

Claude got it on the first try FWIW, I just pasted in your original problem statement (and then verified myself before posting here of course)

[true venture]

Dang I never try that one

[gaunt nest]

I like Claude better and pay for it, but I haven't done a rigorous comparison

It's still sometimes hilariously wrong, definitely need to double check!

[true venture]

Do you know any more interesting equivalence classes on words?

[gaunt nest]

I asked it a linguistics question and it told me people with my accent pronounce "Alan" and "Allen" differently (I had not told it my accent) (we definitely do not)

Hmm, well you can do Burnside for any group I guess, to extend necklaces

[true venture]

Cool, I will look into necklaces more.

[gaunt nest]

Do you know the Myhill nerode theorem?

[true venture]

No

[gaunt nest]

Or the pumping lemma, very similar

It's a cs theory thing

[true venture]

Oh I see it's about words cool

[gaunt nest]

Given a language (which is just what the cst people call sets of strings, usually infinite), two strings are equivalent if for any suffix s, xs and ys are either both in the language or both not in the language

That's an equivalence relation on the set of all strings (not just of finite length)

Then the language can be recognized with a dfa iff the number of classes is finite

[true venture]

Oh wow, I Def like to think of finite strings/languages

[gaunt nest]

There's also free groups I guess

[true venture]

Thanks these are good similat things to look into. Im still new to group stuff.

Another class I was thinking of was like the pattern of equal letters in the whole word

[gaunt nest]

You can count how many strings have no (nontrivial) rotations that make them equivalent to themselves

So 1234 is like that but 1212 is not

Counting that is hard I believe

[true venture]

interesting

[gaunt nest]

The other thing that comes to mind is using the stars and bars trick to turn counting multisets into regular old binomials, that's a combinatorics classic

[true venture]

my other idea was to define a tuple E each corresponding to some k-ary word W = (w_1, ..., w_n), where E is a tuple (e_1, ..., e_{n-1}) with e_i being the number of pairs of equal letters (w_j,w_k) in W such that j + i = k. then two words are equivalent if they have the same E

[gaunt nest]

Interesting

Burnside's lemma is sometimes useful for counting these kinds of things

But I took abstract algebra like 15 years ago so...

I am a little rusty on it

[true venture]

yea, I sort of understand it, but I need more practise with burnside and the cycles counting

[gaunt nest]

Where does this come from?

[true venture]

my recreations on words

[gaunt nest]

It looks gnarly. But very oeis-able.

[true venture]

yes I added a triangle there

yea brute force doesnt get very far

I guess it was inspired by the descent set of a permutation which has been studied more

[gaunt nest]

Interesting

It's late here, I'm off to bed. Thanks for the interesting problems!

[true venture]

no problem, thank for the good info as well!

[shut ivy]

How can i approach this kind of problem to find the recurrence relation

[bright zenith]

What's the identity for $\sum_{k = 0}^n k\cdot\binom{n}{k}\cdot a^{n - k}\cdot b^k$? I know there must be one because $\sum_{k = 0}^n k\cdot \binom{6}{k} \cdot 9^{6 - k}$ adds up to exactly 600,000 (it's a more convoluted way of counting the number of appearances 7 makes between numbers 1, 1,000,000)

[cerulean wind]

do you mean k instead of i?

[bright zenith]

yeah

[vital dew]

phoenixperson

[bright zenith]

or at the very least ignore the b^k

[cerulean wind]

differentiate (a + b)^n w.r.t. b using the binomial theorem and rearrange

[bright zenith]

alright I'll try that, thanks!

[cerulean wind]

the sum in question should be something like nb(a + b)^{n - 1}

but i’m not sure at the moment. tired and i’m doing this in my head lol

[bright zenith]

oh now that i think about i think i'd seen something like this a while ago in the derivation of bernstein polynomials for a version of the weierstrass approximation theorem (both of which I'd completely forgotten about until this moment )

[cerulean wind]

lol hopefully it helps

[bright zenith]

it does wouldn't have thought to recall that in a million years

[kind needle]

does johnson algorithm to enumerate cycles work on a multidigraph?

or does his algo require it to be a directed graph only?

[shut ivy]

anyone?

[true venture]

Think of the smallest strings with an odd number of 1s, how can you build all the other strings from those?

[true venture]

Still thinking of this, what about ABCAC and ACBAC? Both correspond to the S2(5,5) =1 set partition, and there is no permutation of letters between them.

But I think I'm starting to see it now for each set partition of the n letters into m letters, each class can be represented by another word with first letter A and no adjacent equal letters.

This still isn't completely right as words that don't use all the letters of the given alphabet will be overcounted. Ex the set partition {1}{2} then by the process above we have AB and AC, giving two classes, but the words formed by AB and AC mapped onto {1}{2} given AB and AC which are considered equivalent. So there is some nuance to when there are unused letters

[gaunt nest]

I'm not totally following but I think that's why you need to do this sum of Sterling numbers

[true venture]

Ok, I'll look into it more

[lethal linden]

Say you have an n-symbol string containing an odd number of 1s. Look at the prefix made from the first (n-1) symbols, which may or may not have an odd number of 1s.

What can you say about the relationship between the number of 1s in that (n-1)-length prefix and the number of ways you can append a new symbol so that the n-length string has an odd number of 1s?

[true venture]

Yea, I agree about summing over the stirling numbers but each S2(n,i) has some multiplier I don't know

[gaunt nest]

Something like this?

[true venture]

For 2 letter words over {1,2,3}, there is only 1 class for s2(2,2) not s2(2,2) * 2! * C(2,2)

[true venture]

Yea, something like that.

[bright zenith]

Any book recommendations that could help me learn how to solve binary guessing games like this? I don't want direct help solving it just yet. Problem came from a combinatorics book, but I'm only on the first chapter and it hasn't taught me anything like this . It's one of the last problems in the chapter fwiw.

" Consider a game in which player 1 picks a permutation
w of n letters, and player 2 must determine w by asking player 1 a sequence of yes/no
questions. (Player 2 can choose later questions in the sequence based on the answers to
earlier questions.) Let K(n) be the minimum number such that, no matter what w player
1 chooses, player 2 can correctly identify w after at most K(n) questions.

(a)Prove that (n/2)log_2(n/2) <= ceil(log_2(n!) <= K(n)
(b)K(n)= ceil(log_2(n!) for n <= 5 (guess you could just write a program to analyze all 120 cases for n = 5, but I think there should be a mathematical way of doing it)"
(c) Prove
that (b) still holds if we restrict player 2 to ask only questions of the form “is w_i < w_j?"

[lethal linden]

You should say more. Where are you stuck with (a)?

[bright zenith]

nvm I got (a). Just order all theword permutations into 1,...,n ! and ask questions as if you're doing a binary search?

Then I guess we can skip (b) since (c) answers it, but OTOH maybe answering (b) helps answer (c)

[lethal linden]

If you flesh that you, you'll be able to conclude ceil(log_2(n!) <= K(n), but that won't immediately help with (n/2) log_2(n/2) <= ceil(log_2(n!).

[bright zenith]

yeah fair enough

[lethal linden]

I'm not totally sure why they want you to prove (n/2) log_2(n/2) <= ceil(log_2(n!). I don't immediately see how it's connected to the rest of the exercise. 🤷‍♂️

[bright zenith]

same 🤷‍♂️

[lethal linden]

Yes, I think (b) is probably there as scaffolding. A very common problem-solving technique is to look at some small examples and get a feel for what happens.

You can often get a sense for what's impeding a more general proof.

Like, maybe for n <= 5, every question you ask winds up being a comparison question no matter what, just because the permutations are so small. Then at n=6 there's suddenly another sort of question you can ask.

(I'm not saying that's the case, just giving one possible reason they might be telling you to look at n = {0,1,2,3,4,5} specifically.)

[bright zenith]

alright, thanks

[hidden totem]

does anyone know how to prove this? struggling to see any way to make the cases line up, not seeing any bijections

[brazen mortar]

What will be the answer for this

[twilit sundial]

wrong channel

#prealg-and-algebra

[bright zenith]

ok so I took a nap, but after a lil research I realized n/2log_2(n/2) is of a type of loglinear complexity. So I guess the solution may involve showing that some algorithm to do something involving n/2 objects that has loglinear complexity always takes less steps than or equal to some binary search algorithm involving n! objects.

I know virtually nothing about algorithms so idk where to go from here. But I don't feel like giving up on the problem. I'm willing to spend days if not take an entire detour into TCS if I have to

[muted basin]

Hey, I'm trying to answer: How many 5 card hands contain at least one card of each suit?

I'm a little lost by the answer, which is: (52/5) - (4/1)(39/5) + (4/2)(26/5) - (4/3)(13/5)

Ignore the /, it's just there for clarity but it's the "out of _ choose _" notation thing

and I'm guessing using inclusion exclusion rule

How do I approach this properly? I understand there are 52 cards so you can only choose 5 for a hand obviously

but I'm a little lost at the application of IE

[vestal bronze]

each set is missing one suit

you find the total, and subtract from 52c5

39c5 times 4 adds up the circles, then you correct the overlaps

it's really hard to see the logic btw

with 3 sets it makes sense, but it keep working for any number, and that's super not obvious

"the motivation" is not hard, you use it when you want to find "the total of a diagram"

[stray reef]

better to write C(n,k) tbh

[hidden totem]

ok made some progress on this

let B[n] = the permutations of [n] that do not ever have consecutive increasing integers and does not start with 1 (indexing starting from 1)

let D[n] = derangements of [n]

|B[n]| = |D[n]|

for example, in B[5], we have permutations like:
42513
32514
because they end in 5, however we cannot count permutations like:
42351
51243
because there are consecutively increasing integers

can anyone find a constructive bijection between these two classes B[n] and D[n]? it doesn't seem obvious why they should be equal

[hidden totem]

oops small error, fixed

[bright zenith]

Ok I think I figured out this problem.

The first part of the inequality in (a) is just simple algebra . compare the latter half of (log(n) + log(n - 1) +.... to adding up n/2 (or ceil(n/2) instances of log(n/2)

(b) is sort of a trick question I think? I found this post to compute the n-th location of a permutation in lexicographical ordering and vice versa (https://math.stackexchange.com/questions/2717475/finding-position-of-specific-permutation-in-alphabetically-ordered-list-of-permu). Then this (https://stackoverflow.com/questions/39822756/worst-case-for-a-binary-search-if-youre-not-dealing-with-a-power-of-2) post claims worst case time complexity for a binary search is exactly floor(log(k) + 1), which is basically ceil(log(k)) for non-powers of 2. So I think it applies for all n, not just up to n = 5.

(c) The comparisons are basically equivalent to doing a merge sort. You can check by hand the worst possible sorts for 3 and 5, and you could look up an exact formula for 1,2,4 pretty easily if you want since they're powers of 2. Or you could also just use easy reasoning for 1,2, and again check the worst possible sort by hand with 4.

[bright zenith]

this problem

[waxen dune]

I have a question: real number with decimal representations consisting of all 1s. it means whatever numbers have to be having 1s otherwise false. So is this one finite?

[odd heart]

What does "finite" mean here?

0.1111.... is the decimal representation of the real number which we can also denote as 1/9

If you mean ...111111.11111... then this is not a valid decimal representation of any real number.

[waxen dune]

yes I mean to

ah i see

thank you for the clearly explaining

The finite is a limited numbers

[waxen dune]

if uncountable set B then B is R\Z, is the B count consider as uncountable?

[agile magnet]

Can you form your question better?

Is B = R \ Z?

or are you asking if every uncountable set B is equal to R \ Z?

[waxen dune]

yes if B = R\Z then would B be uncountable set?

[agile magnet]

Do you know that R is uncountable and Z is countable? If so what do you think the answer is?

and why

[waxen dune]

yes R is uncountable because R is rational number which are can including pi or e, etc while Z are integers including negative and positive. I assumed B is uncountable because R-Z which keep numbers exclude integers therefore B is uncountable set

does my answer make sense?

@agile magnet

[agile magnet]

R is not rational numbers, R is the set of real numbers

[waxen dune]

my bad

[agile magnet]

you haven't really given a proof

Here's my hint for a proof

assume towards contradiction that R \ Z is countable

go from there

[waxen dune]

since R \ Z is countable then R is the set of real numbers which is rational and/or irrational numbers and Z is the set of integers.

Since R is the real numbers then it is uncountable number

Since Z is the integers then it is countable numbers

I forgot to add R that R is proved via Cantor’s diagonal argument.

By definition of \ is keep elements except exclude some elements if A and B have same elements

Then set of R \ Z contains all real numbers except a set of integers

Since there are infinitely many real numbers between any two consecutive integers which is remaining is still uncountable

Thus R \ Z is uncountable.

That is all my answer

@agile magnet

[agile magnet]

no you haven't proven anything.

[waxen dune]

really?

[agile magnet]

The only thing you've done is state some definitions

Also read what you wrote, you never derived a contradiction

[agile magnet]

this is not a proof

there are infinitely many rational numbers between two integers but the rational numbers are countable

[waxen dune]

That is why I don't like to write a proof haha

anyway

First step: Proof: [by contradiction]

Two step: suppose R \ Z is countable

[silent hazel]

i’m thinking this

R is uncountable, no matter how many numbers you remove

[waxen dune]

yeah you have to proof that R \ Z is uncountable

[silent hazel]

so long as you don’t remove an uncountable set of irrational numbers, as that would make the set Q (and a countable number of irrational numbers) and therefore countably infinite

[waxen dune]

I have to figure out that how I proof that it is uncountable

[silent hazel]

since N is not an uncountable set of irrational numbers, removing elements of N from R makes it still uncountable

⬜️

[waxen dune]

is that all proof?

[silent hazel]

idk i just started proofs 😭

but logically it makes sense

[waxen dune]

ah i see, my gut tells me that is incomplete proof but you are good to start

yes in logical, it does make sense

I can't imagine I write all these sentences that make a proof

Proof: [by contradiction]
Suppose R \ Z is countable then a list all elements of R \ Z as a sequence r_1. r_2. r_3, ....
We know that the set of all real numbers R is uncountable (by Cantor's diagonal; argument) and the set of integers Z is countable.
If we remove a countable set Z from the uncountable set R, the remaining set should still be uncountable.
However, assumed that R \ Z is countable.
assumption that R \ Z is countable must be false.
Therefore, R \ Z is uncountable.

@agile magnet

[agile magnet]

that's not really a full diagonalization proof

ok ok I'll just write out the proof

since I think that'll be more valuable at this point for you to see an example of a proof by contradiction

[waxen dune]

yeah it would be nice to see a full of proof that R \ Z

why does my proof is not completely diagonalization proof?

[agile magnet]

because you haven't actually given any diagonal construction of a new element not in your supposed listing of all elements of R \ Z

[waxen dune]

May i ask you @agile magnet what is your career or major? seems you are expert in discrete math

[agile magnet]

Suppose towards contradiction that R \ Z is countable. Then R = (R \ Z) ∪ Z. But since Z is countable, this means that R is the union of two countable sets, and thus R itself is countable. However, we know that R is uncountable. This is a contradiction, and thus R \ Z must be uncountable.

I'm doing my PhD in math right now (in my first year)

[waxen dune]

nice no wonder you are expert in that stuff

I am just freshman undergraduate student

😦

[agile magnet]

we all start somewhere, don't worry

[waxen dune]

thank you so much for giving me a full proof

[agile magnet]

I struggled with proofs a ton when I was learning

[agile magnet]

does this make sense?

[waxen dune]

yes it is clear now

[waxen dune]

I get you

[steel agate]

So uh

How would I approach this problem

nvm i got it

[terse wyvern]

this isn't very discrete

[odd heart]

Indiscreet mathematics

Anyway, "basic properties and operations on sets" does seem to be in the purview of this channel:

[agile magnet]

alot of schools call their intro to proofs courses (especially ones designed for CS and engineering majors) "discrete math"

[dreamy coral]

Mine does that

[agile magnet]

I was a TA for such a course for CS majors in my UG and it was called discrete math

[weary tiger]

We call it discrete structures here in my course

[agile magnet]

oops you've reminded me

we also called it discrete strutures lmfao

[weary tiger]

Lmaoo

[muted pumice]

how to find the maximum value of theta and the corresponding value of t in a summation of the continuous periodic model?
Like theta(t) = a + summation 3 k=1, [ck* cos(k* omega * t) +sk* sin(k* omega* t] +c4 * cos(4* omega* t),
where a is 34.0926, c1 is 6.1189, s1 is -25.2, c2 is -9.2409, s2 is 5.2747, c3 is 9.0272, s3 is -16.9892, c4 is -19.9977, omega is 20pi/9

[terse wyvern]

<@&268886789983436800>

[weary tiger]

Did u call moderators on ztorm or was there someone else

[agile magnet]

probably something else

[thick copper]

i have this question and i dont know how to solve

[left stratus]

n^3 - n can be factored as n(n-1)(n+1)

then you know that its 3 consecutive integers and since theyre consecutive so one of them must be divisible by 3 and
n is odd, both n-1 and n+1 are even, and among any two consecutive numbers, one is divisible by 4

then the product is divisible by 3*4 =12

[thick copper]

yeah i got it thanks
can you help me with this also if possible

[graceful shell]

so true

[odd heart]

all numbers are imaginary

[graceful shell]

it just me hating on imaginary numbers

[hidden totem]

i think most mathematicians, once they really understand complex numbers more deeply, appreciate complex numbers more than real numbers

[odd heart]

Eh, both fields have their uses.

They're nice in different ways

[hidden totem]

obviously, and so do the integers, nice in their own way

[odd heart]

The complex field is algebraically closed, but the real field is totally (and completely) ordered

[hidden totem]

but none of those systems are beautiful the way complex numbers are imo

[odd heart]

Depending on situation you'll prefer either of those

Well, beauty is a hugely subjective judgment.

I confess I don't feel particularly strongly about any number field

[graceful shell]

same

[chrome sand]

Hi given the below Relation, can i argue for transitivity, that there are no 2 different values only pairs of the same value. There trtransitivity is given?

R1 ⊂ {a, b, c} × {a, b, c} a R1 a, b R1 b, c R1 c

[dreamy coral]

It's hard to not like algebraic closure

[rigid oriole]

its not hard to give a formal argument though

Suppose xRy and yRz
Given the above relations, we must have x = y and y = z

[hollow gyro]

It kinda sucks that imaginary numbers are called that

[halcyon slate]

Hi

Can someone motivate how the strong form of Induction is a refinement of the weak form?

Can it be used to attack problems that the weak form can't?

[quick folio]

Yes, absolutely

[halcyon slate]

um can you talk a bit about why we need all these additional base cases and how does that help us solve these type of problems?

maybe some explicit example would help

[quick folio]

See example 5 here:
https://courses.grainger.illinois.edu/cs173/sp2009/lectures/lect_18.pdf

Goal. Prove that prime factorisation is unique for all positive integers
Here strong induction is absolutely necessary

[agile magnet]

typically any time when you're inducting over recursive structures where there aren't clear "this is the exact previous case"

for example sub-trees / subgraphs (what would be correct notion of a single "previous" graph even be?)

strong induction is the way to go

[rigid night]

A lot of propositions about finite-dimensional vector spaces also require strong induction on the dimension.

[graceful shell]

im dead

exam is bad

[hidden totem]

i always thought about it like this:

there are two steps to simple induction

P(0) is true (or whatever your base case is)

if P(n) then P(n+1)

[hidden totem]

this induction step has to be proven

but maybe P(n) is not sufficient to prove P(n+1), maybe you also need P(n-1), or you dont know which of your previous P(k)'s youll need, so may as well grab all of them just in case

[hidden totem]

and then that lines up with this

[bright zenith]

is $\sum_{0 \leq j < k \leq n}\binom{n}{j} \binom{n}{k} = \frac{2^{2n} - \binom{2n}{n}}{2}?$

My reasoning is that you take $(2^n)^2 = \left(\sum_{k = 0}^n \binom{n}{k}\right)^2$. Then substract $\sum_{k = 0}^n \binom{n}{k}^2 = \binom{2n}{n}$ because $j \neq k$. Then divide by $2$ because the original summation range only represents the strictly upper triangular half of the whole thing.

[vital dew]

phoenixperson

[hidden totem]

looks right to me, probably sanity check by plugging in a few base cases

[bright zenith]

Thanks,I'll try that
Edit: compiled TeX says 1 is lowerbound in the summand,but it should be 0. It's better for it to be 0 anyways, since that's what this problem statement says and also where my reasoning would actually work

Yeah checks out up to n = 3, I'm satisfied

[tall comet]

can someone help me with this question

[hidden totem]

hint: figure out how the prime factorizations of a and b get you the prime factorization of d

then consider how to generalize the logic by separating it into independent "pieces"

[tall comet]

d is the minimum of the powers of each prime in the factorization right

[hidden totem]

yeah

and each prime power is independent

so if you prove the claim for any p^n you prove it for all numbers

[tall comet]

sorry i dont understand what does it mean that each prime power is independent

[hidden totem]

so like first pretend that the claim is true for all cases in which all values a, b, c, d are all powers of 2

now pretend that this claim is also true for all powers of 3

so now you know that for any set of a, b, c, d for which all of these values are of the form 2^x 3^y

this claim only holds true if you can separate the powers of 2 and powers of 3, and show that they each work

if the powers of 3 work but powers of 2 dont, this fails

it also works the other way

if both powers of 2 and powers of 3 work

combine the a, b, c, d values on each side and now it works for all 2^x 3^y

this logic can then be extended to all prime powers, aka all natural numbers

[tall comet]

wdym by showing that they each work?

[hidden totem]

ok lets do this

suppose

all the variables are powers of 2

so for convenience, instead of a i will write 2^A

b is 2^B

[tall comet]

okay

[hidden totem]

the claim is now to show that:

if 2^D = GCD(2^A, 2^B), 2^A | 2^B, and 2^C | 2^D, then 2^(A+C) | 2^(B+D)

this should be pretty easy

but now if you extend the logic so that every variable is represented as their full prime factorization

say a = 2^x 3^x 5^x ... (where each x is potentially different)

what would the reasoning look like?

notice that the logic we need to convert the powers of 2 to the general case is almost identical, you just need to do it separately for each prime power

for instance, 2^A | 2^B is the same as saying A<=B

but for an arbitrary prime factorization, it would mean that

for every p
let the exponent of p in a be a_p etc
a | b is the same as p_a <= p_b for all p

its like you split each prime power by column and check all the corresponding columns together

but 2 was an arbitrary choice of prime, it works for any p, and so this is proven

[random sparrow]

can someone explain what $\supseteq$ is

[vital dew]

938c2cc0dcc05f2b68c4287040cfcf71

[tall comet]

it means it contains the set

[random sparrow]

can you elaborate?

[odd heart]

$B\supseteq A$ is equivalent to $A\subseteq B$

[vital dew]

Outsider

[random sparrow]

lmao, is this true or a joke?

[odd heart]

It's true

A is a subset of B, B is a superset of A

It means that every element of A is also an element of B

[random sparrow]

why would someone use superseteq instead of exchanging the places in a subseteq

[odd heart]

Why would someone use > instead of exchanging the places in an inequality with <

[tall comet]

so here we will get that d = gcd(a,b) is just a? then we want to show ac | ab, but also c | b and so this is true ?

[hidden totem]

uhh small typo and skipped a few steps but it seems like you get the idea?

the rest is just how would you write it out formally so it is accepted as a proof

[tall comet]

yes yes

[tall comet]

but whats the typo sorry

[hidden totem]

ac | bd, not ab

[tall comet]

yeah but d = a right?

[hidden totem]

in the case of a single prime power yes

[tall comet]

like the prime factorization being only one prime?

[hidden totem]

yes

[tall comet]

But isn't this generalizable because as you said if a | b then $p_1^{A_1} \cdot p_2^{A_2} \cdot \ldots \cdot p_k^{A_k} | p_1^{B_1} \cdot p_2^{B_2} \cdot \ldots \cdot p_k^{B_k}$ then $A_i \leq B_i$ and so $d =p_1^{A_1} \cdot p_2^{A_2} \cdot \ldots \cdot p_k^{A_k} = a$

[vital dew]

XDStar

[tall comet]

or is there something wrong here

[tall comet]

does it work for any number of prime powers like i did here?

[hidden totem]

oh wait i think d is just a

if a divides b then the gcd(a,b) is just a

[tall comet]

yes thats what i got

[hidden totem]

then yeah i think thats right then

[tall comet]

then the question boils down to proving ac | ab which is true iff c | b which is given

[hidden totem]

ok i missed that simplification hahaha

that makes it so much easier than what i had in mind

sorry

[tall comet]

no its okay i got it from what you said thank you so much!

[rigid oriole]

$A\supset X\subseteq C$

[rigid oriole]

More realistically "Let A supset B" for an existent B

[random sparrow]

wdym?

[silent hazel]

X is a subset of A

and X is either a subset or equal to C

[random sparrow]

yep

[silent hazel]

similar to $a > x \leq c$ for variables instead of sets

[vital dew]

Gyro

[random sparrow]

I guess?

[silent hazel]

just a similar example

[random sparrow]

yep but the symbols have completely different meanings , but I think I see what you mean ( sorry for the pedantry )

you guys still talking about the analogy someone said above, when explaining why dont just change the order of the operands

[random sparrow]

supset is an actual word? to abbreviate super set?

[rigid oriole]

superset is a word yes...

supset is just the command

[silent hazel]

[rain ivy]

Hello everyone, I have just started the automata theory course and we have a lot of tasks to prove that a language is regular. Is it enough to show that the language can be read by a finite state machine?

[cerulean radish]

Languages read by a finite state machine are regular, so doing that would be sufficient as long as the former has been shown

[radiant gale]

accepted precisely*, but yes

[waxen dune]

Let A be a 3 x 4 matrix and B be a 4 x 5 matrix then BA is not defined because $5 \neq 3$

[vital dew]

E_2xi

[waxen dune]

am I right?

[neon harbor]

yes

[waxen dune]

thank you

[iron marsh]

I am going through a geometric argument of Raney's Lemma (or a baby version of it). Namely, if (x_1,...,x_m) is any finite sequence of integers that add up to 1, then there is exactly one cyclic shift of (x_1,...,x_m) where all partial sums are strictly positive.

I could use some help understanding this idea of "average slope" though. I am very confused on how the relation s_m+n=s_n+1 gives an "average slope" of 1/m...

Ah, I see what it means. I got it from here.

[waxen dune]

my answer for question B is $[
A_{2\times2} =
\left[ {\begin{array}{cc}
n+n & n_{2} \
n_{2} & n_{1} \
\end{array} } \right]
]$ am i right?

[vital dew]

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

[opal crescent]

can you explain your answer ? not sure what you mean by n1 and n2

@waxen dune

[waxen dune]

I don't sure how to explain about it but i know that when increasing power then n2 will became n1 then n+n into n_2.

you can tell it has the repeat of process

@opal crescent

[opal crescent]

ok

what do you get if you list say the top left element of A, A^2, A^3, A^4, A^5, A^6 ?

@waxen dune

[waxen dune]

yes, A^2 = $[
A{2\times2} =
\left[ {\begin{array}{cc}
2 & 1
1 & 1
\end{array} } \right]
]$

[vital dew]

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

[opal crescent]

I'm only talking about the top left elements, don't go listing the whole matrices

[waxen dune]

increasing by Z^+

[opal crescent]

what does that even mean

[waxen dune]

1+2 = 3 then 2+ 3= 5 then 5+3 = 8 then so on

[opal crescent]

ok yeah

so you get something like 1, 2, 3, 5, 8, 13

[waxen dune]

yes

[opal crescent]

does that look familiar to you ?

it even has a name

[waxen dune]

Yes it look familiar to me, like n!?

[opal crescent]

not rlly no

n! grows much faster than this

[waxen dune]

yeah right

[opal crescent]

https://en.wikipedia.org/wiki/Fibonacci_sequence

rings a bell ?

[waxen dune]

yes i got you

that is one

[opal crescent]

aight and as you noticed already the top-right/bottom-left/bottom-right are just shifted versions of the top left

like top-left is 1 step ahead of top-right/bot-left, and 2 steps ahead of bot-right

[waxen dune]

then x_n = x_(n-1) + x_(n-2)

[opal crescent]

yea right

[waxen dune]

is that answer?

[opal crescent]

well the answer will involve the fibonacci sequence yes

like if you take $F_1 = 0, F_2 = 1,$ and $F_{n+2} = F_{n+1} + F_n$ for $n>=1$,then your matrices are

[vital dew]

aPlatypus

[waxen dune]

let me draw the matrice

if i am right

[opal crescent]

alright

[waxen dune]

my answer is

F is Fibonacci sequence

@opal crescent

[opal crescent]

yea if you started with F_0=0, F_1=1

[waxen dune]

i guess it is not really exactly the answer?

[opal crescent]

well it all depends how you define the fibonacci sequence exactly

it's just minute off-by-one details

[waxen dune]

makes sense

it should be proof that is the definition of fibonacci sequence

?

@opal crescent

[opal crescent]

well this ain't a proof, you're just saying it is

[waxen dune]

then top-left corner will jump into the next sequence while Fn would be normal and F_(n-1) is the previous of the sequence

[opal crescent]

I haven't proved anything yet either I just whispered it in your ear

[waxen dune]

I just explain at the simple

lol

[opal crescent]

that's an idea of proof sure

[waxen dune]

at least I get it

[opal crescent]

if you actually wanna prove it, go for induction

a pretty easy one at that

[waxen dune]

I don't want proving because i just need a conjecture lol

are you sure that the proof of that one is a pretty easy one?

Now I am learning about the induction

[opal crescent]

it's pretty straightforward for an induction proof yes

it's "I can hold the entire proof in my head" levels

now if you're not super familiar with induction it can be hard

[waxen dune]

wow impress

yeah I am not familiar with it

[opal crescent]

it's the first time you've been reading on it right now or you've had a class on it or something ?

[waxen dune]

yes I was in a class that I learned about it

[opal crescent]

well we can go through it if you want

[waxen dune]

my answer for the proof is Proof: (induction), (basic) f_0 = 0, f_1 = 1. (recursive step [like the loop function]) f_n = f_n-1 + f_n-2 for n>1. [final] thus, (f_n) from n= 0 to infinity equal to (0, 1, 1, 2, 3, 5, 8, 13, and so on) #

That is pretty basic of proof by induction?

@opal crescent

[opal crescent]

well you're not involving the matrix at all, that's an issue

[waxen dune]

right i forgot

i have to get it before diving into the matrix

it is a basic concept of proof of fibonacci sequence

right?

[opal crescent]

but that's the info from the fibonacci sequence that you will use in each case yes

[opal crescent]

you don't prove an object

you prove a statement about an object

[waxen dune]

what do i need to prove that it is an object?

[opal crescent]

is that what you want to prove tho

you've written a conjecture about A^n earlier

isn't that what you're looking to prove ?

[waxen dune]

i don;t know what i should say but as the answer, I just want a conjecture

but I want to learn about induction more because i have a hard time to understand what my professor said about induction

[opal crescent]

what are you confused about ?

[waxen dune]

how to use induction

[true venture]

I have a sum involving repeated applications of inclusion exclusion,
Writing C(k) as just k the sum Expands to:
1

• 12 - 1 - 2
• 123 - 12 -13 -23 + 1 + 2 +3
  ...
  So each previous row is canceled out by the next, can this property be used to simplify the sum? Are there any identities for something like this?

[timber trellis]

Hello

I need someone to help me with my test tomorrow

Permutations, combinations and probability

[true venture]

Any specific questions your stuck on?

[night urchin]

yea fr bro low effort you aren't studying if your questions don't hold specific content relative to the test

[night urchin]

bro what the heck

have you read literally anything about it? you use it whenever you need to find something which depends on the structure of the problem in a way that you can isolate out a pattern into a recursive step

imo low effort zone let's pump it up

actually I forgive you, it's not that low effort. Anyways, the way you use it by identifying and specifying the structure of the problem into recursive and base cases.

[hidden totem]

i agree that their questions could be more specific but can we tone down the hostile attitude a bit

otherwise whats the point

[waxen dune]

ok i got you, I have six classes, most of them are hard core. I have a hard time to do all

thank you for explaining

that is what I need

[waxen dune]

yeah that is my point because some cases would be complex while others are not

hard to track all induction problems

you know what i mean

[stray reef]

<@&268886789983436800> disturbing&offtopic video

[shrewd obsidian]

and disturbing username too

[stray reef]

...true

[rain ivy]

Hey guys what is (1+0)*

Is it 101010100001

and something like this

[terse bison]

can i get help with Strong Induction

[azure wind]

How do I approach these types of problems

[dire notch]

I need to refresh myself on some of this but the first one is simple enough

No Bs or Cs means you’re just picking from the letters ADEFGHI

So it’s 5 letter strings that start with A

Or, it’s ‘A’ then ‘4 letter combination of DEFGHI’

[azure wind]

Okay that’s what I was thinking, I ended up with 360 as the answer

[dire notch]

yep

[slim garden]

You have a bag with n > 1 M&Ms, m > 0 are green and n − m > 0 are red. One at a time, you randomly pull candies out of the bag and eat them until you pick one of the other color. (That is, you stop eating candies if you started with a green one and then picked a red one, or started with the red one and then pick a green one.) When you get to a candy of the other color, you put it back in the bag, and start picking candies again using the same rule. You keep going until you have eaten all n M&Ms. What is the probability that the last candy you eat is a red M&M?

im having some difficulty with this problem

it feels to me like the answer is intuitively like red/total, but im drawing trees and getting 1/2

which i believe since like youre more likely to select the higher colored one, so the process always favors high colored one until you're even

[weary tiger]

Cant you also reuse A after the second place? I thought words like ADADA are also candidates?

Or does repitition mean using every letter once?

[dire notch]

without repetition, yes

[weary tiger]

Okay

[weary tiger]

Still need help?

[frozen tangle]

Help :Advanced Probability Problem (Graph Theory):
Consider a complete graph with ( n ) vertices (every pair of vertices is connected by an edge). You start coloring each edge independently with:

• Red with probability ( p )
• Blue with probability ( 1-p )

Question:
Given that there exists a monochromatic ( k )-vertex subgraph (all edges red or blue, where ( 3 \leq k \leq n )), what is the conditional probability that this subgraph is entirely red?

Hint: The answer has a surprising symmetry! The solution reveals a beautiful independence from ( k ).

[vital dew]

Erfan59

Help :**Advanced Probability Problem (Graph Theory):**  
Consider a complete graph with \( n \) vertices (every pair of vertices is connected by an edge). You start coloring each edge **independently** with:  
- **Red** with probability \( p \)  
- **Blue** with probability \( 1-p \)  

**Question:**  
Given that there exists a monochromatic \( k \)-vertex subgraph (all edges red *or* blue, where \( 3 \leq k \leq n \)), what is the conditional probability that this subgraph is **entirely red**?  

*Hint: The answer has a surprising symmetry!*  The solution reveals a beautiful independence from \( k \).

[twilit sundial]

did you ask chatgpt for this question

the markdown syntax has me suspicious

[frozen tangle]

This was a question posed by the math teacher, and I am unaware of the source they used.

[hollow token]

Hi all, I have a specific question about a task I did, this is how the question is formed.

I first interpret both of these operators as XNOR, and OR, respectively.

I prove that (S, ⟺) is an Abelian group, then I prove associativity, LHS/RHS distributivity for (S, ⟺ ∨). My question is: For (S, ⟺), the identity element turns out to be T, however, for the ∨ operator, it turns out to be F. Why is it F? I'm wondering this because T ∨ T = T, meanwhile T ∨ F = T as well. I could just be thinking too much on it, but this has me a bit confused, since the identity is defined as ∀x ∈ S, ∃e ∈ S : x ∨ e = x

Well, I know that T cannot be identity element of the ∨ operator since F ∨ T = T, which doesn't hold. But I'm wondering if T ∨ T = T can just be ignored

[opal crescent]

Why does it matter that T or T is T if you're checking whether F is the identity for or ?

If you wanna check that F is the identity, you need to look at
F or F
F or T

T or T is irrelevant here

Nvm I misunderstood your question
The fact that T or F is T is already enough grounds to eliminate T as an identity element here

[hollow token]

I see, thank you!

[visual hawk]

hi, i found this on a book from the 50s .

[waxen dune]

hi guys, I have a question about propositional function. this question said, "Suppose that P(n) is a propositional function. Determine for which nonnegative integers n the statement P(n) must be true for each of the conditions below. [Instructor comment(s): Write your answer as a set and be sure to use proper notation for the set.] so D) P(0) is true; for all nonnegative integers n, if P(n) is true, then P(n + 2) and P(n + 3) are true.

my answer is {0} ∪ { n ∈ ℕ : n ≥ 2 }.

is it right answer?

or { n ∈ ℕ : n = 0 or n ≥ 2 }.

[stray reef]

my answer is {0} ∪ { n ∈ ℕ : n ≥ 2 }.
is it right answer?
or { n ∈ ℕ : n = 0 or n ≥ 2 }.

@waxen dune are you asking "Is either of these correct?" or "Which is the proper way to write it?"

[waxen dune]

which one is correct or both

@stray reef

if my write is not proper way then please tell me that which is the proper way to write it

[stray reef]

both are correct and both are OK imo

i would probably do it as just N \ {1} to be more compact

but your notations are also good

[waxen dune]

Let P(n) be the statement that a postage of n cents can be formed using just 3-cent stamps and 5-cent stamps. [Instructor comment(s): The parts of this exercise outline a strong induction proof that P(n) is true for all integers n ≥ 8.] part c, To complete the inductive step, you would need to establish that P(k+1) is true. Show that P(k+1) is true using the inductive hypothesis

so my answer is:

Proof: [by the strong inductive].( Basic) For n ≥ 8, P(8) is true

(inductive steps) suppose P(8), P(9), so on, P(k+1) are all true.

then the left i do not sure to write

my guess..

if k+1 is combination of 3 cent and 5-cent stamps since k ≥ 8 then k = 9 is true

wait a minute, I am wrong

for n = 8, n is written as 8 = 3 + 5 which is true.