#Combi question (reminds Catalan numbers)

191 messages · Page 1 of 1 (latest)

autumn rover
#

We will say a series (w1, w2, ..., w2n) e {H, T}^2n is balanced if H and T appear n times.
How many balanced series with length of 2n, n>=2, have at most one reisha (w1, w2, ..., wk), 0<k<2n, that is also ballanced.

bleak zealotBOT
#
  1. Do not ping the Moderators, unless someone is breaking the rules.
  2. Do not ping the Helper Moderators, unless there is a conflict between helpers.
  3. Do not ping other members randomly for help.
  4. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
  5. Wait patiently for a helper to come along.
  6. If the Helper has answered your question, remember to thank them with the Mathematics Ranks bot and close the thread with:

+close
Feel free to nominate the person for helper of the week in #helper-nominations
If you're happy with the help you got here, and the server overall, you can contribute financially as well:

autumn rover
#

Reminds me Catalan numbers.

rotund canyon
autumn rover
#

no, not really

rotund canyon
#

did you the :

  1. induction
  2. using generating functions in some way
#

(2) is very useful in these kinds of problems

#

correlate H with up and T with down

#

draw out relevant lattice walks (what I'm saying is very vague, I don't want to spoil it for you)

autumn rover
#

I tried recurrence relation

#

Ok, I will try using generating functions

autumn rover
#

@rotund canyon I tried solkving the problem with generating functions, and didn't find much success. I also tried lattice walks, and wanted to prove the answer like we did with Catalan numbers. That didn't work as well since the function from the walks I defined isn't surjective (I tried flipping the path after walking up/ right the second time we cross y=x line)

#

I am really lost right now

#

I think the answer is H_n = 2C_n

#

when C_n is the nth catalan number, and H_n is the number of legal series

rotund canyon
autumn rover
#

yes

#

like

#

H_3 = 2C_3

#

and H_2 = 2C_2

autumn rover
#

@rotund canyon can you give me a hint?

#

about how to use generating functions

#

or lattice walks

rotund canyon
#

by a bit I mean quite some time I'm studying for an exam right now sorry

autumn rover
#

all good, good luck!

rotund canyon
#

this is how you set it up

#

@autumn rover

rn_image_picker_lib_temp_e667bd5d-8110-4da6-b4df-c57a16a669aa.jpg
autumn rover
#

ok

#

yeah

#

How can we bound the number of mountins

rotund canyon
#

but with paths that never touch the x axis

#

except at the ends ofc

autumn rover
#

@rotund canyon I still can't figure it out. I guess it is about flipping the ends of the extra mountains, but I can't figure out how to count it or even what function I should use to flip the illegal ends

normal adderBOT
#

@autumn rover

:HelpIcon:| Help Reminder

Hello silverlionag, this is a friendly reminder that your help request has been inactive for more than 24 hours. If you no longer need assistance, please consider closing the thread using the +close command. This thread will be automatically closed in 3 days if it remains inactive.

normal adderBOT
#

@rotund canyon The user still needs help with this help request.

rotund canyon
autumn rover
#

No

#

I see the similarities

autumn rover
rotund canyon
#

does this work

autumn rover
rotund canyon
#

but it never crosses the axis

#

so double the paths

autumn rover
#

and we got rid of that by creating a function that "flips" the path from the first point that touches y=-1

rotund canyon
#

above or below

autumn rover
#

I understand that if we can count all the legal paths, we multiply the ones with two mountains by four and the ones with 1 mountain by two

#

but I can't figure out how to count them with Catalan

rotund canyon
#

you first get to mountains

#

then from mountains to stairs

autumn rover
#

because catalan also counts paths with more than two mountains

rotund canyon
#

then stairs to catalan

#

a whole journey out here 🤣

autumn rover
#

we did Catalan with mountains

rotund canyon
autumn rover
#

that's what I am trying to solve

rotund canyon
#

oh wait

#

@autumn rover I am so sorry I have been wrong the whole time for 2 days atleast

#

I completely missed the fact that we might have reisha(s) in between the sequence too

#

I was only accounting for the reishas starting from the front

#

give me 10 minutes or so I'll be back ASAP

autumn rover
#

no problem

#

thanks for helping

rotund canyon
#

I'm back

rotund canyon
#

I wasn't wrong then

#

Associate H with up T with right
If we start with H (up) from (0,0) the origin then we can't ever touch the y=x line except at (n, n)

#

If we start with T (right) what happens? @autumn rover

rotund canyon
#

clearly we see that the last term must be a T if we start with a H (why)?

autumn rover
#

Catalan paths can touch the line

rotund canyon
autumn rover
#

right

rotund canyon
#

now when we have something like say

#

x>1 and x is an integer

#

we can say x>=2

autumn rover
#

I think

rotund canyon
#

Think of it from the walk perspective

autumn rover
#

yeah

#

you go below the line

rotund canyon
#

if we are always above y=x how can we approach it from below?

autumn rover
#

and then you can go above

rotund canyon
#

so we mush approach it from the right

rotund canyon
autumn rover
#

after you touch it for the first time

rotund canyon
#

mhm

autumn rover
#

and that's legal

rotund canyon
#

now we enumerate sequences starting with H

#

instead of working with the line y=x, look at the line y=x+1

#

does it ring a bell?

#

as we can never touch y=x, are always either above y=x+1 or we may touch it

autumn rover
#

Yes

#

but I don't understand why it works

rotund canyon
#

the idea is :
we know the path ends in a right and starts with an up

autumn rover
#

you can get to x+1 even if you start with T

rotund canyon
#

so we might as well ignore these two bits

#

and look at the path in between with respect to y=x+1

#

take some examples

#

and you'll see

autumn rover
#

I don't understand why it works

#

like you can do T,H,H

#

and get to y = 1

#

@rotund canyon

rotund canyon
autumn rover
#

wait

rotund canyon
#

and each sequence has 2n moves so take 4 of them into account

autumn rover
#

H is up or down?

rotund canyon
#

Up

#

and T is right

autumn rover
#

oh

#

we doing latex walks

#

lattice

rotund canyon
#

how are you here while playing among us

rotund canyon
autumn rover
#

oh

#

we are counting the amount of paths that have one mountain

#

@rotund canyon

#

and that is 2C_n

#

right

#

but what about paths that have two mountains?

#

oh

#

I get it

#

no

#

wait

#

I don't

#

hold on

#

let me read it again

#

oh

#

I got it

#

yeah

#

thank you

#

@rotund canyon

#

Can you check my reasoning

#

?

#

First of all, we count all of the paths that have no mountains

#

this is 2C_n-1

#

since what we proved

#

then we count the amount of paths with one mountain

#

which is 4C_n

#

because we choose one intersection with y=x

#

and then we get the sum of H_n-k-1 * H_k

#

from k=0 till k=n-1

#

and that's why the amount of ways is 2C_n-1 + 4C_n

rotund canyon
autumn rover
#

kk

rotund canyon
autumn rover
#

thank you @rotund canyon !

rotund canyon
#

the answer is 2Cn-1

autumn rover
#

why

#

we can have 2 mountains

rotund canyon
#

the problem asked you to find paths without reishas

#

that begin from the front

autumn rover
#

since the reisha doesn't include 2n

rotund canyon
#

(w1, w2,..., wk)

autumn rover
#

it doesn't include the whole series

rotund canyon
#

not (wm,wm+1,...,wk)

#

so the only thing is if you start with H, the number of H you encountered is strictly > Ts

autumn rover
#

I don't understand why H, H, T, T, H, T is illegal

#

@rotund canyon

rotund canyon
autumn rover
#

because 0<k<2n

rotund canyon
autumn rover
#

There are only two balanced reishas

#

one for k=4

#

and the second is the whole series

#

and since we have at most 1 reisha that is balanced and is not the whole series, this is legal

#

@rotund canyon

rotund canyon
#

now count the way to have exactly one

#

join two of the previous types together

autumn rover
#

Yeah

#

I wrote that above

autumn rover
rotund canyon
#

so what is your question

autumn rover
#

I just wanted you to check if my way is correct, and what can I do to write more structured proofs

#

because I feel like if I would have done that in my exam, the professor would have taken off points.

rotund canyon
#

ill check it

autumn rover
#

Thanks

#

Imma write this now

autumn rover
#

+close

normal adderBOT
# autumn rover +close
Please thank your Helpers before closing!

Please thank the helpers who assisted you by clicking the buttons below. You can thank each helper only once. Once you're done, click "Close Post" to close this thread.

normal adderBOT
# normal adder

Thank you for your feedback! Coffey [\asymp] has been awarded 1 helper_points. They now have 41 helper_points. They have 3 helper_points daily left for today.