[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include(/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php) [function.include]: failed to open stream: No such file or directory
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include() [function.include]: Failed opening '/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php' for inclusion (include_path='.:/opt/php53/lib/php')
[phpBB Debug] PHP Warning: in file [ROOT]/includes/session.php on line 1042: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4786: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4788: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4789: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4790: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
BdMO Online Forum • View topic - Sequence count

Sequence count

For discussing Olympiad Level Combinatorics problems
Facebook Twitter

Sequence count

Post Number:#1  Unread postby SANZEED » Sun Dec 28, 2014 8:47 pm

Find the number of possible sequences $(a_1,a_2,...,a_n)$ in terms of $n$, with the following conditions:
(i)$a_1=a_2=0$
(ii)$a_1\leq a_2\leq ...\leq a_n$
(iii)$a_i\leq (i-2)$
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$
User avatar
SANZEED
 
Posts: 550
Joined: Wed Dec 28, 2011 6:45 pm
Location: Mymensingh, Bangladesh

Re: Sequence count

Post Number:#2  Unread postby Phlembac Adib Hasan » Sat Jan 03, 2015 11:33 am

Start the sequence from $a_0$ and toss out the first term. So the third condition turns into $a_i\leq i-1$. Now consider the following bijection: take any $A$ dominated sequence of length $n$ and set $a_i$ as the number of $B$'s preceding $i$-th $A$. Since the sequence is $A$ dominating, there will be at most $i-1$ $B$'s before $i$-th $A$. And obviously the derived sequence will be non-decreasing.
Also, from a given sequence of $a_i$s, it is possible to reverse this move and make an $A$ dominated sequence. Thus the number of sequences is $C_n=\frac{1}{n+1}\binom {2n}{n}$

And here are two examples of the bijection, for clarification:
$AABABB\to 0,0,1$
$AABBAB\to 0,0,2$
Welcome to BdMO Online Forum. Check out Forum Guides & Rules: viewtopic.php?f=25&t=6
User avatar
Phlembac Adib Hasan
 
Posts: 1012
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1

Re: Sequence count

Post Number:#3  Unread postby asif e elahi » Sun Jan 04, 2015 7:00 pm

We consider a $n\times n$ board and color the upper $a_{i}$ cells black of column $i-1$ for $i=2,3......n$. Now the board is divided into $2$ parts. This makes a path from the upper left vertex to the lower right vertex of length $2n-2$.The $3rd$ condition implies that the black squares don't intersect the main diagonal containing the upper left vertex. It's easy to see that this is a catalan path.(Just rotate the board $45^{\circ}$ in counterclockwise direction). Again any such catalan path indicates a sequence of length $n-1$. So we have got a bijection between the sequences and the catalan paths of length $2n-2$.
The number of sequences= number of catalan paths of length $2n-2$ = $\dfrac{1}{n}\binom{2n-2}{n-1}$.
User avatar
asif e elahi
 
Posts: 183
Joined: Mon Aug 05, 2013 12:36 pm
Location: Sylhet,Bangladesh


Share with your friends: Facebook Twitter

  • Similar topics
    Replies
    Views
    Author

Return to Combinatorics

Who is online

Users browsing this forum: No registered users and 1 guest