OFFSET
0,6
COMMENTS
Triangle read by rows: T(n,k) is the number of up-down permutations (p(i),i=1..n) on [n] such that the subpermutation of peaks (p(2),p(4),p(6),...) consists of k decreasing runs, equivalently, has k ascents where the first entry of a nonempty permutation is conventionally considered to be an ascent.
For n>=1, T(n,k) is nonzero only for 1 <= k <= n/2.
REFERENCES
L. Carlitz, Enumeration of up-down permutations by number of rises, Pacific Journal of Mathematics, Vol. 45, no.1, 1973, 49-58.
FORMULA
Carlitz's recurrence underlies the Mathematica code below.
EXAMPLE
Table begins
\ k.0....1.....2.....3.....4
n
0 |.1
1 |.1
2 |.0....1
3 |.0....2
4 |.0....3.....2
5 |.0....8.....8
6 |.0...15....38.....8
7 |.0...48...176....48
8 |.0..105...692...540....48
9 |.0..384..3584..3584...384
The up-down permutation 1 9 3 10 6 8 2 5 4 7 is counted by T(10,3) because the subpermutation of peaks splits into 3 decreasing runs: 9, 10 8 5, 7.
T(4,1)=3 counts 1423, 2413, 3412.
MATHEMATICA
Clear[A];
A[m_, r_]/; 0<=m<=1 := If[r==0, 1, 0];
A[m_, r_]/; m>=2 && (r<1 || r>m/2) := 0;
A[m_, r_]/; m>=2 && 1<=r<=m/2 && EvenQ[m] := A[m, r] = Module[{n=m/2},
Sum[Binomial[2n-1, 2k+1]A[2k+1, s]A[2n-2k-2, r-s], {k, 0, n-2}, {s, 0, r}] + A[2n-1, r-1] ];
A[m_, r_]/; m>=2 && 1<=r<=m/2 && OddQ[m] := A[m, r] = Module[{n=(m-1)/2},
Sum[Binomial[2n, 2k+1]A[2k+1, s]A[2n-2k-1, r-s], {k, 0, n-2}, {s, 0, r}] + 2n A[2n-1, r-1] ];
Table[A[m, r], {m, 0, 12}, {r, 0, m/2}]
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
David Callan, Aug 23 2011
STATUS
approved