IMO ShortList 1999, combinatorics problem 1

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

14 users

TOPICS

No tags match your search

M

No tags match your search

M

IMO ShortList 1999, combinatorics problem 1

G H J

Reveal topic tags

binomial coefficients

L

G H BBookmark kLocked kLocked NReply

Source: IMO ShortList 1999, combinatorics problem 1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#1 h Nov 14, 2004, 12:13 AM • 3 Y

Y by Adventure10, megarnie, Mango247

Let $n \geq 1$ be an integer. A path from $(0,0)$ to $(n,n)$ in the $xy$ plane is a chain of consecutive unit moves either to the right (move denoted by $E$ ) or upwards (move denoted by $N$ ), all the moves being made inside the half-plane $x \geq y$ . A step in a path is the occurence of two consecutive moves of the form $EN$ . Show that the number of paths from $(0,0)$ to $(n,n)$ that contain exactly $s$ steps $(n \geq s \geq 1)$ is

$\frac{1}{s} \binom{n-1}{s-1} \binom{n}{s-1}.$

Attachments:

This post has been edited 1 time. Last edited by orl, Nov 14, 2004, 10:27 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#2 h Nov 14, 2004, 12:14 AM • 2 Y

Y by Adventure10, Mango247

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1434 posts

rem

#3 h Sep 15, 2007, 12:16 AM • 4 Y

Y by arandomperson123, Adventure10, Mango247, and 1 other user

Define by $f(k,l)$ the number of paths from $(0,0)$ to $(k,k)$ containing exactly $l$ steps ( $1\leq l\leq k$ ).
We will prove the result of the problem using mathematical induction, ie for any positive integers $n, s$ and $1\leq s\leq n$ we have $f(n,s) = \frac{1}{s}\binom{n - 1}{s - 1}\binom{n}{s - 1}$
Base Step: For $s = 1$ because the first move is $E$ and last one is $N$ (as we can only move in the half-plane $x\geq y$ ), and there is only one move $EN$ then there is only one path from $(0,0)$ to $(n,n)$ -- $n$ $E$ moves followed by $n$ $N$ moves. Therefore, $f(n,1) = 1$ and $\frac{1}{1}\binom{n - 1}{1 - 1}\binom{n}{1 - 1} = 1$ so the result is true for $(n,1)$ . Also, for $n = 2$ if $s = 1$ get the case $(n,1)$ and if $s = 2$ by inspection there is only one path with required properties, so $f(2,2) = 1$ and $\frac{1}{2}\binom{2 - 1}{2 - 1}\binom{2}{2 - 1} = 1$ so result is true for $(2,2)$ .
Induction Step: Assume for $n$ the result is true, ie for any $1\leq s\leq n$ where $s$ is an integer, we have $f(n,s) = \frac{1}{s}\binom{n - 1}{s - 1}\binom{n}{s - 1}$ .
Call a path $(k,l)$ a path from $(0,0)$ to $(k,k)$ with $l$ steps.
Now, every path $(n,s)$ can be transformed into a path from $(0,0)$ to $(n + 1,n + 1)$ by inserting a step between any two consecutive moves, or in the beginning or in the end of the $(n,s)$ path -- note the new path will still completely stay in the required half-plane, this is really nice. Then, if this step is inserted in between an $E$ and a $N$ steps (in this order) then, the number of steps in the new path will be $s$ -- so we get a path $(n + 1,s)$ , and otherwise get $s + 1$ steps so get a path $(n + 1,s + 1)$ .
Now, for a $(n,s)$ path there are $s$ ways in which a step can be inserted in between an $E$ and a $N$ steps (in this order), so $s$ transformations of a $(n,s)$ path give a $(n + 1,s)$ path. And there are $2n + 1 - s$ ways in which the step in not inserted in between an $E$ and a $N$ step in this order -- as in total there are $2n + 1$ spaces for the "new" step to go in the sequence of moves in path $(n,s)$ -- so $2n + 1 - s$ transformations of a $(n,s)$ path give a $(n + 1,s + 1)$ path.
Therefore, there are $s + 1$ ways to transform a $(n,s + 1)$ path into a $(n + 1,s + 1)$ path and $2n + 1 - s$ ways to transform a $(n,s)$ path into a $(n + 1,s + 1)$ path. But in each $(n + 1,s + 1)$ path, there are $s + 1$ steps so $s + 1$ ways to reduce it to a $(n,s + 1)$ or a $(n,s)$ path by removing one step. Therefore:
$(s + 1)f(n + 1,s + 1) = (2n + 1 - s)f(n,s) + (s + 1)f(n,s + 1)$
$= (2n + 1 - s)\frac{1}{s}\binom{n - 1}{s - 1}\binom{n}{s - 1} + (s + 1)\frac{1}{s + 1}\binom{n - 1}{s}\binom{n}{s}$
$= \binom{n}{s}\left(\frac{2n + 1 - s}{n - s + 1}\binom{n - 1}{s - 1} + \binom{n - 1}{s}\right)$
$= \binom{n}{s}\left(\frac{(n - 1)!}{(s - 1)!(n - s)!}\right)\left(\frac{2n + 1 - s}{n - s + 1} + \frac{n - s}{s}\right)$
$= \binom{n}{s}\left(\frac{(n - 1)!}{(s - 1)!(n - s)!}\right)\left(\frac{n^{2} + n}{(n - s + 1)s}\right)$
$= \binom{n}{s}\binom{n + 1}{s}$
Therefore, $f(n + 1,s + 1) = \frac{1}{s + 1}\binom{n}{s}\binom{n + 1}{s}$ so result is true for $n + 1$ and the result follows by mathematical induction.

This post has been edited 1 time. Last edited by darij grinberg, Mar 20, 2012, 3:20 AM
Reason: typos (mostly latex) repaired

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4302 posts

#4 h Oct 24, 2011, 7:54 PM • 4 Y

Y by fx1007, Adventure10, and 2 other users

Inserting steps works nicely, but just for another method...

Let $f(p,q,s)$ denote the number of pairs of sequences of nonnegative integers $(\{a_i\}_{i=1}^{s},\{b_i\}_{i=1}^{s})$ such that
$a_1+\cdots+a_i\ge b_1+\cdots + b_i$ for all $1\le i\le s$ and $p=a_1+\cdots+a_s$ while $q=b_1+\cdots+b_s$ . For $s=1$ , $f(p,q,s)=[p\ge q]$ , and for $s\ge 2$ ,
$f(p,q,s)=[p\ge q]\sum_{b_s=0}^{q}\sum_{a_s=0}^{p}f(p-a_s,q-b_s,s-1)=[p\ge q]\sum_{j=0}^{p}\sum_{k=0}^{q}f(j,k,s-1).$ By induction on $s$ , we show that
$\implies f(p,q,s)=[p\ge q]\left(\binom{p+s-1}{s-1}\binom{q+s-1}{s-1}-\binom{p+s-1}{s-2}\binom{q+s-1}{s}\right).$ Indeed, for $s=1$ and $s=2$ this is easy to verify, and for $s=3$ (assuming $p\ge q$ , of course), the inductive hypothesis combined with repeated Vandermonde yields
$\begin{align*} f(p,q,s) &= \sum_{j=0}^{p}\sum_{k=0}^{q}f(j,k,s-1) \\ &= \sum_{k=0}^{q}\sum_{j=k}^{p}\binom{j+s-2}{s-2}\binom{k+s-2}{s-2}-\binom{j+s-2}{s-3}\binom{k+s-2}{s-1} \\ &= \sum_{k=0}^{q}\binom{k+s-2}{s-2}\left(\binom{p+s-1}{s-1}-\binom{k+s-2}{s-1}\right)-\binom{k+s-2}{s-1}\left(\binom{p+s-1}{s-2}-\binom{k+s-2}{s-2}\right) \\ &= \sum_{k=0}^{q}\binom{k+s-2}{s-2}\binom{p+s-1}{s-1}-\binom{k+s-2}{s-1}\binom{p+s-1}{s-2} \\ &= \binom{q+s-1}{s-1}\binom{p+s-1}{s-1}-\binom{q+s-1}{s}\binom{p+s-1}{s-2}, \end{align*}$ as desired.

Returning to the original problem, it's not hard to see that there are $s-1$ corners of the form $NE$ if there are $s$ steps; these "upper" corners, including $(0,0)$ and $(n,n)$ , form a sequence $(0,0),(x_1,y_1),(x_1+x_2,y_1+y_2),\ldots,(x_1+\cdots+x_s,y_1+\cdots+y_s)$ where $x_i,y_i\ge 1$ are integers for all $i$ , $x_1+\cdots+x_i\ge y_1+\cdots+y_i$ for all $i$ , and $x_1+\cdots+x_s=n=y_1+\cdots+y_s$ . Hence our desired answer is
$\begin{align*} f(n-s,n-s,s) &=\binom{n-1}{s-1}\binom{n-1}{s-1}-\binom{n-1}{s}\binom{n-1}{s-2} \\ &=\binom{n-1}{s-1}^2\left(1-\frac{n-s}{s}\frac{s-1}{n-s+1}\right) \\ &=\frac{(n-1)!^2}{(s-1)!^2(n-s)!^2}\frac{n}{s(n-s+1)} \\ &= \frac{1}{s}\binom{n-1}{s-1}\binom{n}{s-1}, \end{align*}$ as desired.

Motivation

[Moderator edit: The above is a nice solution, but I think that what is referred to as "Vandermonde" is actually better known as the "hockey-stick identity" (the identity claiming that $\sum_{i=a}^b \binom{i+c}{d} = \binom{b+c+1}{d+1}-\binom{a+c}{d+1}$ for all integers $a$ , $b$ , $c$ , $d$ satisfying $a\geq b+1$ ). Also, the induction base $s=2$ is unneeded, at least as long as binomial coefficients are extended to negative entries in an appropriate way (i. e., in a way respecting the recurrence equation). -- Darij]

This post has been edited 2 times. Last edited by darij grinberg, Mar 20, 2012, 4:13 AM
Reason: $x_1+\cdots+x_i\le y_1+\cdots+y_i$ corrected to $x_1+\cdots+x_i\ge y_1+\cdots+y_i$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

290 posts

ep4ma

#5 h Jan 20, 2013, 8:18 PM • 2 Y

Y by Adventure10, Mango247

Can somebody post a solution using generating functions

?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

16123 posts

JBL

#6 h Jan 20, 2013, 8:51 PM • 3 Y

Y by fx1007, Adventure10, Mango247

Here's a start. What the problem calls "steps" I'll call "peaks". Let the number of $n$ -paths with $s$ peaks be $f(n, s)$ , and let $F(x, t) = \sum_{n, s} f(n, s) x^n t^s$ . For $n \geq 0$ , every path from $(0, 0)$ to $(n + 1, n + 1)$ with $s$ peaks can be decomposed as follows: let $k$ be the smallest nonneginteger such that $(k + 1, k + 1)$ belongs to the path. Then either $k = 0$ and the portion of the path from $(1, 1)$ to $(n + 1, n + 1)$ is itself a path with $s - 1$ peaks, or $k > 0$ and there is some $j$ such that the portion of the path from $(1, 0)$ to $(k + 1, k)$ is a path with $j$ peaks while the portion of the path from $(k + 1, k + 1)$ to $(n + 1, n + 1)$ has $s - j$ peaks. It follows immediately that $f(n + 1, s) = f(n, s - 1) + \sum_{k \geq 1} \sum_{j} f(k, j) f(n - k, s - j).$ Multiplying by $x^{n + 1}t^s$ and summing over all nonnegative $n$ and $s$ gives $F(x, t) - 1 = xt F(x, t) + x F(x, t)(F(x, t) - 1).$ Solving this quadratic equation gives $F(x, t) = \frac{1 + x - xt - \sqrt{(1 + x - tx)^2 - 4x}}{2x}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1514 posts

ksun48

#7 h Aug 20, 2013, 4:40 AM • 8 Y

Y by math154, randomusername, reveryu, JasperL, rayfish, N1RAV, Adventure10, Mango247

I'm surprised that this method (a "bijection") has not been posted yet?

If we consider any path from (0,0) to (n, n+1) such that they have s steps (and start with E, end with N), then we can cyclicly rotate the steps in this path to obtain s distinct paths, and then we can show that exactly one of them is a valid path for the original problem with an additional N step appended to the end. Since there are $\binom{n-1}{s-1} \binom{n}{s-1}$ paths from (0,0) to (n,n+1) with s steps (we can use balls and urns), we conclude that the answer is $\frac{1}{s}\binom{n-1}{s-1} \binom{n}{s-1}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1135 posts

#8 h Jul 24, 2015, 12:24 AM • 2 Y

Y by Adventure10, Mango247

rem wrote:

But in each $(n + 1,s + 1)$ path, there are $s + 1$ steps so $s + 1$ ways to reduce it to a $(n,s + 1)$ or a $(n,s)$ path by removing one step.

Why is this true? Is it not possible to have the following sequence: $EENENN$ ? There are two steps but if you remove the first $EN$ , you'll get the exact sequence as if you remove the second $EN$ ?

This post has been edited 1 time. Last edited by MathPanda1, Jul 24, 2015, 12:25 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#9 h Oct 26, 2017, 8:59 AM • 2 Y

Y by Adventure10, Mango247

MathPanda1 wrote:

Why is this true? Is it not possible to have the following sequence: $EENENN$ ? There are two steps but if you remove the first $EN$ , you'll get the exact sequence as if you remove the second $EN$ ?

rem is talking about "ways to remove"; he isn't a building a bijection, so it is perfectly possible that two "ways to remove" yield the same result.

Let me use this occasion to comment on where the problem comes from. The number $\frac{1}{s} \binom{n-1}{s-1} \binom{n}{s-1}$ is the so-called Narayana number $N_{n, s-1}$ . The statement of the problem is the well-known interpretation of this Narayana number as the number of Dyck paths of semilength $n$ with $k$ peaks. This is proven in §2.4.2 of Kyle Petersen's Eulerian Numbers text.

This post has been edited 2 times. Last edited by darij grinberg, Oct 26, 2017, 9:08 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2726 posts

#10 h Nov 1, 2020, 4:41 AM

Y by

Say hello to Alice, a step:
$[asy] unitsize(24); draw((0.0,0.0)--(1,0)--(1,1),blue); [/asy]$
Now say hello to Bob, not a step:
$[asy] unitsize(24); draw((0.0,0.0)--(1,0)--(1,1)--(2, 1)--(2,2),green); [/asy]$ This is just to make sure it's clear that we're on the lookout for Alices, not Bobs. Now we've got that sorted, we can start on the problem.

Consider paths from $(0, 0)$ to $(m, n)$ using only $E$ 's and $N$ 's that start with $E$ and end with $N$ (which we call $\textit{derkish}$ ) - this is to make sure that the path doesnt cross $x \leq y$ in the first move or has crossed $x \leq y$ by the last move. I claim that there are $\binom{m-1}{a-1}\binom{n-1}{a-1}$ derkish paths with $a$ Alices. Call the bottom right corner of an Alice its anchor. Since derkish paths start with $E$ and end with $N$ , their first anchor must be on the $x$ -axis and their last anchor must be on $x = m$ . I claim that we can biject derkish paths with $a$ anchors to selecting two sequences of integers $0 < x_1 < x_2 < \ldots < x_a = m$ and $0 = y_1 < y_2 \ldots < y_a < n$ . Indeed, any derkish paths with $a$ Alices can extrapolate such a sequence; simply consider the $x$ -coordinates and $y$ -coordinates of the anchors arranged in increasing order. Furthermore, it is also clear that each pair of such sequences generates at least one derkish path with $a$ Alices; simply let $(x_i, y_i)$ be the $i$ th anchor. Indeed, each anchor is to the top-right of the previous one, so such a path can always be generated. So indeed, this bijection is formed, and it is easy to count the number of pairs of such sequences, which does indeed match what we claimed earlier.

Now, consider derkish paths with $s$ Alices from $(0, 0)$ to $(n, n+1)$ ; there are $\tbinom{n-1}{s-1}\tbinom{n}{s-1}$ of those. Among its $2n+1$ cyclic shifts, note that the number of them that produce derkish paths is the same as the number of adjacent pairs of $NE$ ; this must be the same as the number of Alices, which is $a$ . Furthermore, no two cyclic shifts may be the same since $n$ and $n+1$ are relatively prime. Furthermore, exactly one of them does not cross the line $(0, 0) \to (n, n+1)$ , which is the same condition as not crossing $x \geq y$ .

Hence, among every derkish path with $s$ Alices, $\tfrac{1}{s}$ of them are satisfying the problem, and this yields our final desired answer. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

11102 posts

#11 h Nov 1, 2020, 4:44 AM

Y by

$~~~~~~~~~$

This post has been edited 1 time. Last edited by jasperE3, Jun 10, 2022, 7:05 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1065 posts

Eyed

#12 h Jan 10, 2021, 5:17 AM • 1 Y

Y by Stuffybear

Probably shouldn't have tried recursion for the first 3 hours, oh well.

Consider any path from $(0, 0)$ to $(n, n+1)$ that has $s$ steps (not necessarily in the half plane) that starts with a E and ends with an N. The number of such paths is $\binom{n-1}{s-1}\binom{n}{s-1}$ , since we can choose points $p_{1}, p_{2}, \ldots p_{s-1}$ such that $p_{i}$ is to the right and above $p_{i-1}$ , and there is exactly one step from $p_{i-1}$ to $p_{i}$ (Let $p_{0} = (0, 0), p_{s} = (n, n+1)$ ). Since the x and y coordinates of these points are distinct, in increasing order, and range from $(0, n)$ for x coordinates and $(0, n+1)$ for y coordinates, there are $\binom{n-1}{s-1}\binom{n}{s-1}$ ways to choose such points.

Now consider taking this path, and putting the starting point at $(n, n+1)$ . Now we have a path that goes from $(0, 0)$ to $(2n, 2n+2)$ . Furthermore, if point $p_{i} = (x_{i}, y_{i}),$ let point $p_{i+n} = (x_{i} + n, y_{i} + n + 1)$ (which is also on this path). Now, for each $0\leq i < n$ , consider the sub-section of this path from $p_{i}$ to $p_{i+n}$ . I claim exactly one $i$ exists such that this subpath is below or on the line between $(x_{i}, y_{i})$ and $(x_{i}+n, y_{i} + n)$ (excluding the last move of this path, which is north). This is because, if we consider the point with the maximal $y_{i} - x_{i}$ , and if there are multiple such points take the leftmost one, then this point must satisfy that condition, while no other point can (because of maximality and leftmost, leftmost ensures that the line of any other point will run into $(x_{i} + n, y_{i} + n+1)$ ). Let this path be the "mapped path". For each path that is in the half plane $y\leq x$ , we can do the same thing to show that $s$ of the paths in the entire plane has it's mapped path as the path in the half plane (up to translation), by just appending a "N" at the end of it and copying it over. Thus, the number of paths in the half plane with $s$ steps is $\frac{1}{s}$ of the number of paths in the full plane, or $\frac{1}{s}\binom{n-1}{s-1}\binom{n}{s-1}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

496 posts

#13 h Jun 10, 2022, 4:12 AM

Y by

We will prove this by induction on $n$ , with $n=1$ as the base case. Let $f(n, s)$ denote the number of paths from $(0, 0)$ to $(n, n)$ with $s$ steps.

The number of ways to choose a path with $s$ steps and color one of the steps blue is $sf(n, s)$ .

Consider removing the blue step. Then, you get a path from $(0, 0)$ to $(n-1, n-1)$ .

Consider the case where the point where the blue step was removed has $E$ before it and $N$ after it. This case is equivalent to starting with a path from $(0, 0)$ to $(n-1, n-1)$ with $s$ steps, choosing a step, and turning it from $EN$ to $EENN$ . There are $sf(n-1, s)$ ways to do this.

Consider the other case, where the point isn't in the middle of a step. This is equivalent to starting with a path from $(0, 0)$ to $(n-1, n-1)$ with $s-1$ steps, choosing a point that isn't in the middle of a step, and inserting a step into it. There are $2n-1$ total points, so there are $2n-s$ that aren't steps. So, there are $(2n-s)f(n-1, s-1)$ ways to do this.

So, adding, we get $sf(n, s)=sf(n-1, s)+(2n-s)f(n-1, s-1)$ . By the inductive hypothesis,
$sf(n, s)={{n-2}\choose{s-1}}{{n-1}\choose{s-1}}+\frac{2n-s}{s-1}{{n-2}\choose{s-2}}{{n-1}\choose{s-2}}={{n-2}\choose{s-1}}{{n-1}\choose{s-1}}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1665 posts

awesomeming327.

#14 h Dec 2, 2022, 5:15 AM • 2 Y

Y by Mango247, Mango247

Let $f(n,s)$ be the number of paths from going $n$ up and $n$ right containing exactly $s$ steps. Clearly, we have $f(n,1)=1$ and $f(n,n)=1.$

$~$
Consider any path from $(0,0)$ to $(n,n)$ with $s$ steps. Now, you can at any point in the path, insert a step without making any part of the path go over the line $x=y$ . This is because any part of the path that is past the insertion will be shifting parallel to the line $x=y$ .

$~$
With a path with $s+1$ steps, you can add a step where there already is a step in $s+1$ ways to make a path that is just two longer but preserve the number of steps. With a path with $s$ steps, you can add a step where there is not already a step in $2n+1-s$ ways to make a path that is just two longer and makes $s+1$ steps. Now, for a path from $(0,0)$ to $(n+1,s+1)$ with $s+1$ , we can remove a step in $s+1$ ways to go back to a path from $(0,0)$ to $(n,n)$ , with either $s$ or $s+1$ paths.

$~$
Since insertion and removal is two related transformations, and the ratio between insertions from $s$ steps and from $s+1$ is $2n+1-s:s+1$ , the ratio for the removal to $s$ steps and to $s+1$ will be $2n+1-s:s+1$ . Therefore, $f(n+1,s+1)=(2n+1-s)/(s+1)f(n,s)+f(n,s+1)$ at which point induction can be used to finish.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1869 posts

#15 h Jul 29, 2023, 11:16 PM • 1 Y

Y by Toinfinity

Let $f_s(m,n)$ be the answer but you start at $(n-m,0)$ instead of $(0,0)$ . Our constraints are now $1\le s\le m\le n$ .
We can really just visualize this problem as having $s$ "horizontally flipped L shapes" with their endpoints connected. This lends itself to this following formula, where $1<s\le M\le N\colon$
$f_s(M,N)=\sum_{m=s-1}^{M-1}\sum_{n=m}^{N-1}f_{s-1}(m,n).$ Now we will prove our main claim.

Main Claim. For all positive integers $1\le s\le M\le N$ ,
$f_s(M,N)=\binom{N}{s-1}\binom{M-1}{s-1}-\binom{N-1}{s-2}\binom{M}{s}.$ Proof. We proceed by induction on $s$ . Base case $s=1$ is trivial, so assume $s-1$ works. Now
$\begin{align*} &f_s(M,N) \\ &=\sum_{m=s-1}^{M-1}\sum_{n=m}^{N-1}f_{s-1}(m,n) \\ &=\sum_{m=s-1}^{M-1}\sum_{n=m}^{N-1}\left(\rule{0cm}{1cm}\binom{n}{s-2}\binom{m-1}{s-2}-\binom{n-1}{s-3}\binom{m}{s-1}\right) \\ &=\sum_{m=s-1}^{M-1}\left(\rule{0cm}{1.2cm}\left(\rule{0cm}{1cm}\binom{N}{s-1}-\binom{m}{s-1}\right)\binom{m-1}{s-2}-\left(\rule{0cm}{1cm}\binom{N-1}{s-2}-\binom{m-1}{s-2}\right)\binom{m}{s-1}\right) \\ &=\sum_{m=s-1}^{M-1}\left(\rule{0cm}{1.2cm}\left(\rule{0cm}{1cm}\binom{N}{s-1}-\binom{m}{s-1}\right)\binom{m-1}{s-2}-\left(\rule{0cm}{1cm}\binom{N-1}{s-2}-\binom{m-1}{s-2}\right)\binom{m}{s-1}\right) \\ &=\binom{N}{s-1}\binom{M-1}{s-1}-\binom{N-1}{s-2}\binom{M}{s}+\sum_{m=s-1}^{M-1}\left(\rule{0cm}{1cm}\binom{m-1}{s-2}\binom{m}{s-1}-\binom{m}{s-1}\binom{m-1}{s-2}\right) \\ &=\binom{N}{s-1}\binom{M-1}{s-1}-\binom{N-1}{s-2}\binom{M}{s}\;\blacksquare \end{align*}$
Now note that for any $1\le s\le n$ ,
$\begin{align*} &f_s(n,n) \\ &=\binom{n}{s-1}\binom{n-1}{s-1}-\binom{n-1}{s-2}\binom{n}{s} \\ &=\frac{n!(n-1)!}{(s-1)!^2(n-s+1)!(n-s)!}-\frac{n!(n-1)!}{s!(s-2)!(n-s+1)!(n-s)!} \\ &=\frac{n!(n-1)!}{(s-1)!(s-2)!(n-s+1)!(n-s)!}\cdot\left(\frac{1}{s-1}-\frac{1}{s}\right) \\ &=\frac{n!(n-1)!}{(s-1)!(s-2)!(n-s+1)!(n-s)!(s)(s-1)} \\ &=\frac{1}{s}\binom{n-1}{s-1}\binom{n}{s-1}\;\blacksquare \end{align*}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

577 posts

#16 h Sep 8, 2023, 6:15 AM

Y by

The gist of the problem is to solve it with endpoint $(n, n+1)$ without the restriction of the path within the half plane by using $s$ obvious cyclic shifts of the paths. Thus we need to show that the number of paths is $\binom{n-1}{s-1} \binom{n}{s-1}.$ Now the path can be split up into a sequence of ``fat steps" consisting of multiple right moves followed by multiple up moves, so we finish by Stars and Bars.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

123 posts

abeot

#17 h Nov 24, 2023, 4:17 PM • 1 Y

Y by centslordm

Inspired by the "cyclic shift" method of proving the Catalan number problem:

We instead consider paths from $(0, 0)$ to $(n, n+1)$ of $s$ steps below the slightly raised line from $(0, 0)$ to $(n, n+1)$ . Obviously, counting the number of possible paths in this case is equivalent to the original question (an $N$ is forced to go last following any valid path). Here is an example for $n = 5$ and $s = 2$ :
$EENNEEENNNN$ Consider the $s$ cyclic shifts of this path, where we shift by consecutive $E$ 's and $N$ 's that precede and come after a step (call these big steps); in this case, the other shift is
$EEENNNNEENN$ Claim: Exactly one of these shifts lies below the slightly raised line.

Indeed, we just note that there must be a big step consisting of more $N$ 's than $E$ 's. In particular, this big step must come last to satisfy the problem statement. $\square$

Thus, we just need to count the total number of paths from $(0, 0)$ to $(n, n+1)$ that have $s$ big steps, but do not need to stay below $y = x$ .
To do this, we use stars and bars twice. First, we need to place the $E$ 's to form $s$ groups of conseuctive $E$ 's. First place $s$ $E$ 's so these groups are nonzero, and then we have to place $n-s$ objects into $s$ buckets; this gives $\binom{n-1}{s-1}$ ways.
Similarly for the $N$ 's, we want to form $s$ groups of consecutive $N$ 's, so get rid of the nonzero condition by placing $s$ $N$ 's. Then we have $n+1-s$ objects to place into $s$ buckets, giving $\binom{n}{s-1}$ ways.

This proves that the answer is $\frac{1}{s} \binom{n-1}{s-1}\binom{n}{s}$ , as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1249 posts

ezpotd

#18 h Aug 21, 2024, 10:36 PM

Y by

(bad formatting because copied from what i wrote on mathdash, but also because trying to be formal on this problem sucks)

consider path from 0,0 to n,n + 1 with s steps, ending on N, starting on E, ignoring the half plane condition. first, observe that each of these paths that remains in the half plane until the last move has a direct correspondence with the a path in the set of paths that we want. parameterize each path as a set of points s + 1 points (0,0) ... (n, n + 1), such that between two consecutive points, we go all east and then all north to get to there, hence between each set of two points there is a step. we claim that for all cyclic shifts of these points (not exactly cyclic shifts, just double the path and then take a path starting at the next point, then translate down, you cant take a path starting at the last point since its equivalent to starting at the first point), exactly one of the paths determined stays in the half plane. this is trivial, just take the point with max y - x gap, and that is leftmost. it is easy to see that this point actually works, as no one else can gap harder so you never go above. all points with smaller y - x fail cuz they must go above the half plane while hitting that point, all points with equal y - x to the right fail because they hit the translation of the original point on the doubled path, which has a gap one higher.

to compute the number of paths, just stars and bars, we have n - s Es and n + 1 - s Ns, both to be distributed amongst s groups, giving s times the desired expression, then taking 1/s for cyclic shifts finishes.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a