Partitions into 0,1, and 2 with a partial sum condition. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T20:58:58Z http://mathoverflow.net/feeds/question/64795 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/64795/partitions-into-0-1-and-2-with-a-partial-sum-condition Partitions into 0,1, and 2 with a partial sum condition. Cam McLeman 2011-05-12T14:58:34Z 2011-05-12T16:04:44Z <p>On a tangent to a problem I've been working on, I've run into a combinatorial/partition-theoretic problem that I wondered if anyone had run into before. </p> <p>Let $N$ be a positive integer, and <em>ad-hoc</em>-ly call an (ordered) non-negative partition of $N$ into exactly $N$ parts $$N=n_1+n_2+\cdots+n_N$$ <em>valid</em> if</p> <p></p> <ul> <li>$0\leq n_i\leq 2$ for all $i$; and </li> </ul> <p><ul> <li><code>$\sum\limits_{k=1}^i n_k&lt;i$</code> for all <code>$i&lt;N$</code>.</li></ul></p> <p>So these are something like partitions where the running total is always bounded by the number of terms added thus far. (So the running average of the elements of the partition is less than 1.) In particular, this forces $n_1=0$ and $n_N=2$.</p> <p>I'm more interested in whether this notion of a "valid" partition has arisen previously in the literature than an explicit count of how many of them there are for a given $N$ (probably a reasonably straight-forward linear recurrence or something), so any such references would be appreciated.</p> http://mathoverflow.net/questions/64795/partitions-into-0-1-and-2-with-a-partial-sum-condition/64797#64797 Answer by Aaron Meyerowitz for Partitions into 0,1, and 2 with a partial sum condition. Aaron Meyerowitz 2011-05-12T15:34:34Z 2011-05-12T15:34:34Z <p>Sounds like ballot paths and Catalan numbers. Replace each 0,1,2 with UU,UR,RR respectively to get an Up Right path from (0,0) to (n,n) which stays above the diagonal until the end. </p> http://mathoverflow.net/questions/64795/partitions-into-0-1-and-2-with-a-partial-sum-condition/64802#64802 Answer by David Speyer for Partitions into 0,1, and 2 with a partial sum condition. David Speyer 2011-05-12T15:52:28Z 2011-05-12T16:04:44Z <p>This is <a href="http://oeis.org/A168049" rel="nofollow">A168049</a> or, with slightly different indexing, the <a href="http://oeis.org/A001006" rel="nofollow">Motzkin numbers</a>. </p> <p>The general question of counting nondecreasing sequences which stay below the diagonal is very common in combinatorics and goes by the name Lukasiewicz words. Stanley has a good discussion Enumerative Combinatorics II, Sections 5.3 and 5.4 and I <a href="http://www.math.lsa.umich.edu/~speyer/LagrangeInversion.pdf" rel="nofollow">wrote up some notes</a> when I taught this material last Fall. </p> <p>In general, to count Lukaswiecz sequences from $(0,0)$ to $(n,n)$, one uses the generating function relation $$P = x W(P(x))$$ where $W = \sum w_k x^k$ and sequences are counted with weight $w_0^{a_0} \cdots w_i^{a_i}$, where $a_i$ is the number of times you increase by $i$. In your case, you want to permit increases by $(0,1,2)$, and not keep track of how many of each you are using, so you want to look at $$P = x(1+P+P^2)$$ which has the solution $P(x) = (-1 + x + \sqrt{1 - 2 x - 3 x^2})/(2 x)$. Unlike the Catalan case, I don't think you can get any simpler than this.</p> <p>To make my notes match up with your indexing, discard the final $2$ from your sequence, and take your $n_i$ to be my $d_i$, if I am not mistaken.</p> <p>To add a bit of self promotion, call your sequence $a(n)$. It starts out $1$, $1$, $2$, $4$, $9$, $21$, $51$ ... Define $b(n)$ so that $a(n) = b(n) + b(n+1)$. So the $b$'s start out $1$, $0$, $1$, $1$, $3$, $6$, $15$, $36$ ... That sequence is <a href="http://oeis.org/A005043" rel="nofollow">A005043</a> and I <a href="http://sbseminar.wordpress.com/2010/10/06/a-peculiar-numerical-coincidence/" rel="nofollow">blogged about it</a>.</p>