MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

Let $N$ be a positive integer, and ad-hoc-ly call an (ordered) non-negative partition of $N$ into exactly $N$ parts $$ N=n_1+n_2+\cdots+n_N $$ valid if

  • $0\leq n_i\leq 2$ for all $i$; and

  • $\sum\limits_{k=1}^i n_k<i$ for all $i<N$.

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$.

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.

share|cite|improve this question
Cam: the trick with these kinds of questions is to work out the first few terms of the sequence, search for it online in the OEIS and then look at the references that show up in the notes for that sequence. It's a surprisingly powerful technique! – Kevin Buzzard May 12 '11 at 19:47
Completely agreed, this was shameful laziness on my part. On the other hand, I suspect that I would not have found as nice of an answer as found in David's notes via that route; my laziness has been rewarded yet again. So really, shame on you, David. Tsk tsk. – Cam McLeman May 12 '11 at 20:54
up vote 8 down vote accepted

This is A168049 or, with slightly different indexing, the Motzkin numbers.

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 wrote up some notes when I taught this material last Fall.

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.

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.

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 A005043 and I blogged about it.

share|cite|improve this answer
For n=5 I see 00122 00212 01022 01112 and 01022 am I misunderstanding? This is a Catalan number but not a Motzkin number. – Aaron Meyerowitz May 12 '11 at 16:03
You listed 01022 twice. – David Speyer May 12 '11 at 16:08
Excellent, thanks very much. – Cam McLeman May 12 '11 at 17:07

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.

share|cite|improve this answer
This doesn't work (although I have fallen into this trap many times myself.) Look at the Catalan path UURURR. It cannot occur in this manner. You have only given an injection to ballot paths. – David Speyer May 12 '11 at 15:56
True enough! Thanks – Aaron Meyerowitz May 12 '11 at 16:39
Thanks to both of you. – Cam McLeman May 12 '11 at 17:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.