Catalan numbers: why is there a division by $(n+1)$












1












$begingroup$


There are many interpretations of the Catalan numbers. The one I relate to most readily is the number of paths from the bottom-left to the top-right of an $n times n$ grid which don't cross the main diagonal. The number of ways to do this is:



$$C_n = frac{2n choose n}{n+1} = {2n choose n} - {2n choose n-1}$$



The second expression in the equation above has a very neat, intuitive explanation which is described in the answer by @Marcus M here which involves mapping the undesirable paths (that do cross the main diagonal) to a smaller grid. That explanation, I understand.



However, there must also be a way to directly interpret the first expression. The total paths in the grid are $2n choose n$. and the number of paths that don't cross the main diagonal are a very specific fraction of the total paths: $frac{2n choose n}{n+1}$. What is the intuitive reason that for every $n+1$ paths in the grid, one of them doesn't cross the main diagonal?



When I ask this question to people who haven't heard of it before, their first instinct is to say half the paths should not cross the main diagonal. I know one of the things that makes them way off is that towards the end of the path, the probability that you'll cross the main diagonal becomes quite high. Is there a more concrete line of attack?






combinatorics combinations catalan-numbers







share|cite|improve this question











$endgroup$








  • 3




    $begingroup$
    You might want to look at the third proof on Wikipedia.
    $endgroup$
    – Slade
    Dec 20 '18 at 8:49










  • $begingroup$
    Thanks for the pointer, wasn't aware of that Wikipedia article. Got a rough understanding, but will need to read it a few times to fully grasp it.
    $endgroup$
    – Rohit Pandey
    Dec 20 '18 at 9:05
















1












$begingroup$


There are many interpretations of the Catalan numbers. The one I relate to most readily is the number of paths from the bottom-left to the top-right of an $n times n$ grid which don't cross the main diagonal. The number of ways to do this is:



$$C_n = frac{2n choose n}{n+1} = {2n choose n} - {2n choose n-1}$$



The second expression in the equation above has a very neat, intuitive explanation which is described in the answer by @Marcus M here which involves mapping the undesirable paths (that do cross the main diagonal) to a smaller grid. That explanation, I understand.



However, there must also be a way to directly interpret the first expression. The total paths in the grid are $2n choose n$. and the number of paths that don't cross the main diagonal are a very specific fraction of the total paths: $frac{2n choose n}{n+1}$. What is the intuitive reason that for every $n+1$ paths in the grid, one of them doesn't cross the main diagonal?



When I ask this question to people who haven't heard of it before, their first instinct is to say half the paths should not cross the main diagonal. I know one of the things that makes them way off is that towards the end of the path, the probability that you'll cross the main diagonal becomes quite high. Is there a more concrete line of attack?






combinatorics combinations catalan-numbers







share|cite|improve this question











$endgroup$








  • 3




    $begingroup$
    You might want to look at the third proof on Wikipedia.
    $endgroup$
    – Slade
    Dec 20 '18 at 8:49










  • $begingroup$
    Thanks for the pointer, wasn't aware of that Wikipedia article. Got a rough understanding, but will need to read it a few times to fully grasp it.
    $endgroup$
    – Rohit Pandey
    Dec 20 '18 at 9:05














1












1








1





$begingroup$


There are many interpretations of the Catalan numbers. The one I relate to most readily is the number of paths from the bottom-left to the top-right of an $n times n$ grid which don't cross the main diagonal. The number of ways to do this is:



$$C_n = frac{2n choose n}{n+1} = {2n choose n} - {2n choose n-1}$$



The second expression in the equation above has a very neat, intuitive explanation which is described in the answer by @Marcus M here which involves mapping the undesirable paths (that do cross the main diagonal) to a smaller grid. That explanation, I understand.



However, there must also be a way to directly interpret the first expression. The total paths in the grid are $2n choose n$. and the number of paths that don't cross the main diagonal are a very specific fraction of the total paths: $frac{2n choose n}{n+1}$. What is the intuitive reason that for every $n+1$ paths in the grid, one of them doesn't cross the main diagonal?



When I ask this question to people who haven't heard of it before, their first instinct is to say half the paths should not cross the main diagonal. I know one of the things that makes them way off is that towards the end of the path, the probability that you'll cross the main diagonal becomes quite high. Is there a more concrete line of attack?






combinatorics combinations catalan-numbers







share|cite|improve this question











$endgroup$




There are many interpretations of the Catalan numbers. The one I relate to most readily is the number of paths from the bottom-left to the top-right of an $n times n$ grid which don't cross the main diagonal. The number of ways to do this is:



$$C_n = frac{2n choose n}{n+1} = {2n choose n} - {2n choose n-1}$$



The second expression in the equation above has a very neat, intuitive explanation which is described in the answer by @Marcus M here which involves mapping the undesirable paths (that do cross the main diagonal) to a smaller grid. That explanation, I understand.



However, there must also be a way to directly interpret the first expression. The total paths in the grid are $2n choose n$. and the number of paths that don't cross the main diagonal are a very specific fraction of the total paths: $frac{2n choose n}{n+1}$. What is the intuitive reason that for every $n+1$ paths in the grid, one of them doesn't cross the main diagonal?



When I ask this question to people who haven't heard of it before, their first instinct is to say half the paths should not cross the main diagonal. I know one of the things that makes them way off is that towards the end of the path, the probability that you'll cross the main diagonal becomes quite high. Is there a more concrete line of attack?






combinatorics combinations catalan-numbers




combinatorics combinations catalan-numbers






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 20 '18 at 8:46









Key Flex

8,27261233




8,27261233










asked Dec 20 '18 at 8:39









Rohit PandeyRohit Pandey

1,2871022




1,2871022








  • 3




    $begingroup$
    You might want to look at the third proof on Wikipedia.
    $endgroup$
    – Slade
    Dec 20 '18 at 8:49










  • $begingroup$
    Thanks for the pointer, wasn't aware of that Wikipedia article. Got a rough understanding, but will need to read it a few times to fully grasp it.
    $endgroup$
    – Rohit Pandey
    Dec 20 '18 at 9:05














  • 3




    $begingroup$
    You might want to look at the third proof on Wikipedia.
    $endgroup$
    – Slade
    Dec 20 '18 at 8:49










  • $begingroup$
    Thanks for the pointer, wasn't aware of that Wikipedia article. Got a rough understanding, but will need to read it a few times to fully grasp it.
    $endgroup$
    – Rohit Pandey
    Dec 20 '18 at 9:05








3




3




$begingroup$
You might want to look at the third proof on Wikipedia.
$endgroup$
– Slade
Dec 20 '18 at 8:49




$begingroup$
You might want to look at the third proof on Wikipedia.
$endgroup$
– Slade
Dec 20 '18 at 8:49












$begingroup$
Thanks for the pointer, wasn't aware of that Wikipedia article. Got a rough understanding, but will need to read it a few times to fully grasp it.
$endgroup$
– Rohit Pandey
Dec 20 '18 at 9:05




$begingroup$
Thanks for the pointer, wasn't aware of that Wikipedia article. Got a rough understanding, but will need to read it a few times to fully grasp it.
$endgroup$
– Rohit Pandey
Dec 20 '18 at 9:05










1 Answer
1






active

oldest

votes


















1












$begingroup$

I think there’s an easier way to see this than the third proof on Wikipedia, modulo one detail I haven’t fully justified (marked with * below).



Each of the $2nchoose n$ paths from $(0,0)$ to $(n,n)$ can be identified with an $n+1$-tuple, where the $i$-th entry is the number of vertical steps taken at $x=i$. For example, this image shows the vertical portions of the $n=7$ path with $8$-tuple $(0,2,0,1,3,0,0,1)$.



enter image description here



Now, if you look at the paths corresponding to all $n+1$ cyclic permutations (rotations) of the tuple (these are all distinct, because the sum of the entries, $n$ is relatively prime to $n+1$), exactly one of the paths stays below the diagonal*.



Here are the $8$ paths for the tuple $(0,2,0,1,3,0,0,1)$ and the $8$ paths for the tuple $(1,1,3,0,0,2,0,0)$, again with just the vertical segments shown.



enter image description here



Thus $1over n+1$ of the $2nchoose n$ paths stays below the diagonal.



These groups of paths (corresponding to the rotations of a single tuple) are the same groups of paths given in the Wikipedia proof, but not in the same order.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    So, there will be non-circular permutations of the (0,2,0,1,3,0,0,1) sequence that don't map to those 8 paths and will have their own family of 8 paths.. very cool proof.
    $endgroup$
    – Rohit Pandey
    Dec 24 '18 at 23:08











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047309%2fcatalan-numbers-why-is-there-a-division-by-n1%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









1












$begingroup$

I think there’s an easier way to see this than the third proof on Wikipedia, modulo one detail I haven’t fully justified (marked with * below).



Each of the $2nchoose n$ paths from $(0,0)$ to $(n,n)$ can be identified with an $n+1$-tuple, where the $i$-th entry is the number of vertical steps taken at $x=i$. For example, this image shows the vertical portions of the $n=7$ path with $8$-tuple $(0,2,0,1,3,0,0,1)$.



enter image description here



Now, if you look at the paths corresponding to all $n+1$ cyclic permutations (rotations) of the tuple (these are all distinct, because the sum of the entries, $n$ is relatively prime to $n+1$), exactly one of the paths stays below the diagonal*.



Here are the $8$ paths for the tuple $(0,2,0,1,3,0,0,1)$ and the $8$ paths for the tuple $(1,1,3,0,0,2,0,0)$, again with just the vertical segments shown.



enter image description here



Thus $1over n+1$ of the $2nchoose n$ paths stays below the diagonal.



These groups of paths (corresponding to the rotations of a single tuple) are the same groups of paths given in the Wikipedia proof, but not in the same order.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    So, there will be non-circular permutations of the (0,2,0,1,3,0,0,1) sequence that don't map to those 8 paths and will have their own family of 8 paths.. very cool proof.
    $endgroup$
    – Rohit Pandey
    Dec 24 '18 at 23:08
















1












$begingroup$

I think there’s an easier way to see this than the third proof on Wikipedia, modulo one detail I haven’t fully justified (marked with * below).



Each of the $2nchoose n$ paths from $(0,0)$ to $(n,n)$ can be identified with an $n+1$-tuple, where the $i$-th entry is the number of vertical steps taken at $x=i$. For example, this image shows the vertical portions of the $n=7$ path with $8$-tuple $(0,2,0,1,3,0,0,1)$.



enter image description here



Now, if you look at the paths corresponding to all $n+1$ cyclic permutations (rotations) of the tuple (these are all distinct, because the sum of the entries, $n$ is relatively prime to $n+1$), exactly one of the paths stays below the diagonal*.



Here are the $8$ paths for the tuple $(0,2,0,1,3,0,0,1)$ and the $8$ paths for the tuple $(1,1,3,0,0,2,0,0)$, again with just the vertical segments shown.



enter image description here



Thus $1over n+1$ of the $2nchoose n$ paths stays below the diagonal.



These groups of paths (corresponding to the rotations of a single tuple) are the same groups of paths given in the Wikipedia proof, but not in the same order.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    So, there will be non-circular permutations of the (0,2,0,1,3,0,0,1) sequence that don't map to those 8 paths and will have their own family of 8 paths.. very cool proof.
    $endgroup$
    – Rohit Pandey
    Dec 24 '18 at 23:08














1












1








1





$begingroup$

I think there’s an easier way to see this than the third proof on Wikipedia, modulo one detail I haven’t fully justified (marked with * below).



Each of the $2nchoose n$ paths from $(0,0)$ to $(n,n)$ can be identified with an $n+1$-tuple, where the $i$-th entry is the number of vertical steps taken at $x=i$. For example, this image shows the vertical portions of the $n=7$ path with $8$-tuple $(0,2,0,1,3,0,0,1)$.



enter image description here



Now, if you look at the paths corresponding to all $n+1$ cyclic permutations (rotations) of the tuple (these are all distinct, because the sum of the entries, $n$ is relatively prime to $n+1$), exactly one of the paths stays below the diagonal*.



Here are the $8$ paths for the tuple $(0,2,0,1,3,0,0,1)$ and the $8$ paths for the tuple $(1,1,3,0,0,2,0,0)$, again with just the vertical segments shown.



enter image description here



Thus $1over n+1$ of the $2nchoose n$ paths stays below the diagonal.



These groups of paths (corresponding to the rotations of a single tuple) are the same groups of paths given in the Wikipedia proof, but not in the same order.






share|cite|improve this answer











$endgroup$



I think there’s an easier way to see this than the third proof on Wikipedia, modulo one detail I haven’t fully justified (marked with * below).



Each of the $2nchoose n$ paths from $(0,0)$ to $(n,n)$ can be identified with an $n+1$-tuple, where the $i$-th entry is the number of vertical steps taken at $x=i$. For example, this image shows the vertical portions of the $n=7$ path with $8$-tuple $(0,2,0,1,3,0,0,1)$.



enter image description here



Now, if you look at the paths corresponding to all $n+1$ cyclic permutations (rotations) of the tuple (these are all distinct, because the sum of the entries, $n$ is relatively prime to $n+1$), exactly one of the paths stays below the diagonal*.



Here are the $8$ paths for the tuple $(0,2,0,1,3,0,0,1)$ and the $8$ paths for the tuple $(1,1,3,0,0,2,0,0)$, again with just the vertical segments shown.



enter image description here



Thus $1over n+1$ of the $2nchoose n$ paths stays below the diagonal.



These groups of paths (corresponding to the rotations of a single tuple) are the same groups of paths given in the Wikipedia proof, but not in the same order.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Dec 24 '18 at 21:30

























answered Dec 24 '18 at 17:44









Steve KassSteve Kass

11.4k11530




11.4k11530












  • $begingroup$
    So, there will be non-circular permutations of the (0,2,0,1,3,0,0,1) sequence that don't map to those 8 paths and will have their own family of 8 paths.. very cool proof.
    $endgroup$
    – Rohit Pandey
    Dec 24 '18 at 23:08


















  • $begingroup$
    So, there will be non-circular permutations of the (0,2,0,1,3,0,0,1) sequence that don't map to those 8 paths and will have their own family of 8 paths.. very cool proof.
    $endgroup$
    – Rohit Pandey
    Dec 24 '18 at 23:08
















$begingroup$
So, there will be non-circular permutations of the (0,2,0,1,3,0,0,1) sequence that don't map to those 8 paths and will have their own family of 8 paths.. very cool proof.
$endgroup$
– Rohit Pandey
Dec 24 '18 at 23:08




$begingroup$
So, there will be non-circular permutations of the (0,2,0,1,3,0,0,1) sequence that don't map to those 8 paths and will have their own family of 8 paths.. very cool proof.
$endgroup$
– Rohit Pandey
Dec 24 '18 at 23:08


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047309%2fcatalan-numbers-why-is-there-a-division-by-n1%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







-

Popular posts from this blog

Mont Emei

Image
Mont Emei.mw-parser-output .entete.map{background-image:url("//upload.wikimedia.org/wikipedia/commons/7/7a/Picto_infobox_map.png")} Vue du sommet Wanfo du mont Emei Géographie Altitude 3 099  m , Wanfo Coordonnées 29° 31′ 11″ nord, 103° 19′ 57″ est Administration Pays   Chine Province Sichuan Ville-préfecture Leshan Géolocalisation sur la carte : Sichuan Mont Emei Géolocalisation sur la carte : Chine Mont Emei modifier   Paysage panoramique du mont Emei, incluant le paysage panoramique du grand Bouddha de Leshan *   Patrimoine mondial de l'UNESCO Passerelle en bois sur le versant ouest Pays   Chine Subdivision Sichuan Type Mixte Critères (iv) (vi) (x) Superficie 15 400 ha Numéro d’identification 779 Zone géographique Asie et Pacifique  ** Année d’inscription 1996 (20 e session) * Descriptif officiel UNESCO ** Classification géog...
Read more

Province de Neuquén

Image
Province de Neuquén Provincia del Neuquén .mw-parser-output .entete.map{background-image:url("//upload.wikimedia.org/wikipedia/commons/7/7a/Picto_infobox_map.png")} Héraldique Drapeau Localisation de la province de Neuquén Administration Pays   Argentine Capitale Neuquén Gouverneur Omar Gutiérrez ISO 3166-2 AR-Q Démographie Gentilé Neuquino/a Population 550 344  hab. (2010) Densité 5,8  hab./km 2 Géographie Superficie 94 078  km 2 Liens Site web http://www.neuquen.gov.ar modifier   La province de Neuquén est une province d'Argentine, qui se trouve à l'extrémité nord-ouest de la Patagonie argentine. Avec une superficie de 94 378  km 2 , elle est la plus petite province des régions australes du pays. Sa géographie s'abîme sur l'imposante Cordillère des Andes. Sommaire 1 Histoire 1.1 Avant la découverte par les Espagnols 1.2 ...
Read more

Soliste

Image
Un soliste est un interprète qui assure seul l'exécution d'une partie musicale dans un ensemble ou de manière isolée. Le soliste s'oppose donc au musicien qui, au sein d'un pupitre, exécute collectivement une partie musicale (un choriste dans une chorale, un violoniste dans un orchestre symphonique, etc.). Par exemple, dans un concerto pour piano, le soliste est le pianiste, alors que les différents musiciens de l'orchestre réalisant leurs parties musicales respectives sont des musiciens de pupitre . Les parties musicales confiées à un soliste sont d'ordinaire plus virtuoses que celles des autres musiciens : vélocité, puissance, étendue du registre, etc. En musique classique | Depuis la période baroque, le soliste s'est nettement différencié du musicien de pupitre, par une spécialisation et une technicité tout à fait particulières, encouragées ou exigées par les compositeurs eux-mêmes. En ce qui concerne la musique vocale, le soliste apparaî...
Read more