We have your learning goals covered with Spring and Summer courses available. Enroll today!

G
Topic
First Poster
Last Poster
k a March Highlights and 2025 AoPS Online Class Information
jlacosta   0
Mar 2, 2025
March is the month for State MATHCOUNTS competitions! Kudos to everyone who participated in their local chapter competitions and best of luck to all going to State! Join us on March 11th for a Math Jam devoted to our favorite Chapter competition problems! Are you interested in training for MATHCOUNTS? Be sure to check out our AMC 8/MATHCOUNTS Basics and Advanced courses.

Are you ready to level up with Olympiad training? Registration is open with early bird pricing available for our WOOT programs: MathWOOT (Levels 1 and 2), CodeWOOT, PhysicsWOOT, and ChemWOOT. What is WOOT? WOOT stands for Worldwide Online Olympiad Training and is a 7-month high school math Olympiad preparation and testing program that brings together many of the best students from around the world to learn Olympiad problem solving skills. Classes begin in September!

Do you have plans this summer? There are so many options to fit your schedule and goals whether attending a summer camp or taking online classes, it can be a great break from the routine of the school year. Check out our summer courses at AoPS Online, or if you want a math or language arts class that doesn’t have homework, but is an enriching summer experience, our AoPS Virtual Campus summer camps may be just the ticket! We are expanding our locations for our AoPS Academies across the country with 15 locations so far and new campuses opening in Saratoga CA, Johns Creek GA, and the Upper West Side NY. Check out this page for summer camp information.

Be sure to mark your calendars for the following events:
[list][*]March 5th (Wednesday), 4:30pm PT/7:30pm ET, HCSSiM Math Jam 2025. Amber Verser, Assistant Director of the Hampshire College Summer Studies in Mathematics, will host an information session about HCSSiM, a summer program for high school students.
[*]March 6th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar on Math Competitions from elementary through high school. Join us for an enlightening session that demystifies the world of math competitions and helps you make informed decisions about your contest journey.
[*]March 11th (Tuesday), 4:30pm PT/7:30pm ET, 2025 MATHCOUNTS Chapter Discussion MATH JAM. AoPS instructors will discuss some of their favorite problems from the MATHCOUNTS Chapter Competition. All are welcome!
[*]March 13th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar about Summer Camps at the Virtual Campus. Transform your summer into an unforgettable learning adventure! From elementary through high school, we offer dynamic summer camps featuring topics in mathematics, language arts, and competition preparation - all designed to fit your schedule and ignite your passion for learning.[/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Sunday, Mar 2 - Jun 22
Friday, Mar 28 - Jul 18
Sunday, Apr 13 - Aug 10
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Tuesday, Mar 25 - Jul 8
Sunday, Apr 13 - Aug 10
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21


Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, Mar 23 - Jul 20
Monday, Apr 7 - Jul 28
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Sunday, Mar 16 - Jun 8
Wednesday, Apr 16 - Jul 2
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Monday, Mar 17 - Jun 9
Thursday, Apr 17 - Jul 3
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Sunday, Mar 2 - Jun 22
Wednesday, Apr 16 - Jul 30
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Tuesday, Mar 4 - Aug 12
Sunday, Mar 23 - Sep 21
Wednesday, Apr 23 - Oct 1
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Mar 16 - Sep 14
Tuesday, Mar 25 - Sep 2
Monday, Apr 21 - Oct 13
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Sunday, Mar 23 - Aug 3
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Friday, Apr 11 - Jun 27
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Sunday, Mar 16 - Aug 24
Wednesday, Apr 9 - Sep 3
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Wednesday, Mar 5 - May 21
Tuesday, Jun 10 - Aug 26

Calculus
Sunday, Mar 30 - Oct 5
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Sunday, Mar 23 - Jun 15
Wednesday, Apr 16 - Jul 2
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Friday, Apr 11 - Jun 27
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Tuesday, Mar 4 - May 20
Monday, Mar 31 - Jun 23
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT

Programming

Introduction to Programming with Python
Monday, Mar 24 - Jun 16
Thursday, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Sunday, Mar 30 - Jun 22
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Tuesday, Mar 25 - Sep 2
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Sat & Sun, Apr 26 - Apr 27 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
Mar 2, 2025
0 replies
Inequality => square
Rushil   12
N 7 minutes ago by ohiorizzler1434
Source: INMO 1998 Problem 4
Suppose $ABCD$ is a cyclic quadrilateral inscribed in a circle of radius one unit. If $AB \cdot BC \cdot CD \cdot DA \geq 4$, prove that $ABCD$ is a square.
12 replies
+1 w
Rushil
Oct 7, 2005
ohiorizzler1434
7 minutes ago
p + q + r + s = 9 and p^2 + q^2 + r^2 + s^2 = 21
who   28
N 24 minutes ago by asdf334
Source: IMO Shortlist 2005 problem A3
Four real numbers $ p$, $ q$, $ r$, $ s$ satisfy $ p+q+r+s = 9$ and $ p^{2}+q^{2}+r^{2}+s^{2}= 21$. Prove that there exists a permutation $ \left(a,b,c,d\right)$ of $ \left(p,q,r,s\right)$ such that $ ab-cd \geq 2$.
28 replies
who
Jul 8, 2006
asdf334
24 minutes ago
H not needed
dchenmathcounts   44
N an hour ago by Ilikeminecraft
Source: USEMO 2019/1
Let $ABCD$ be a cyclic quadrilateral. A circle centered at $O$ passes through $B$ and $D$ and meets lines $BA$ and $BC$ again at points $E$ and $F$ (distinct from $A,B,C$). Let $H$ denote the orthocenter of triangle $DEF.$ Prove that if lines $AC,$ $DO,$ $EF$ are concurrent, then triangle $ABC$ and $EHF$ are similar.

Robin Son
44 replies
dchenmathcounts
May 23, 2020
Ilikeminecraft
an hour ago
IZHO 2017 Functional equations
user01   51
N an hour ago by lksb
Source: IZHO 2017 Day 1 Problem 2
Find all functions $f:R \rightarrow R$ such that $$(x+y^2)f(yf(x))=xyf(y^2+f(x))$$, where $x,y \in \mathbb{R}$
51 replies
user01
Jan 14, 2017
lksb
an hour ago
No more topics!
IMO ShortList 1999, combinatorics problem 1
orl   17
N Aug 21, 2024 by ezpotd
Source: IMO ShortList 1999, combinatorics problem 1
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}.\]
17 replies
orl
Nov 14, 2004
ezpotd
Aug 21, 2024
IMO ShortList 1999, combinatorics problem 1
G H J
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.
orl
3647 posts
#1 • 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.
orl
3647 posts
#2 • 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.
rem
1434 posts
#3 • 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.
math154
4302 posts
#4 • 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.
ep4ma
290 posts
#5 • 2 Y
Y by Adventure10, Mango247
Can somebody post a solution using generating functions :D ?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JBL
16123 posts
#6 • 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.
ksun48
1514 posts
#7 • 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.
MathPanda1
1135 posts
#8 • 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.
darij grinberg
6555 posts
#9 • 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.
jj_ca888
2726 posts
#10
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.
jasperE3
11091 posts
#11
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.
Eyed
1065 posts
#12 • 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.
awesomehuman
496 posts
#13
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.
1664 posts
#14 • 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.
cj13609517288
1862 posts
#15 • 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.
Leo.Euler
577 posts
#16
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.
abeot
123 posts
#17 • 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.
ezpotd
1245 posts
#18
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
=
a