Skip to main content
added 405 characters in body
Source Link
David E Speyer
  • 156.3k
  • 14
  • 421
  • 763

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.

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.

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.

Source Link
David E Speyer
  • 156.3k
  • 14
  • 421
  • 763

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.