A194365 Triangle read by rows: T(n,k) is the number of down-up permutations on [n] whose peaks have k rises.

1, 0, 1, 0, 1, 0, 1, 1, 0, 2, 3, 0, 3, 10, 3, 0, 8, 38, 15, 0, 15, 121, 121, 15, 0, 48, 540, 692, 105, 0, 105, 1804, 4118, 1804, 105, 0, 384, 9104, 26204, 13884, 945, 0, 945, 32493, 143458, 143458, 32493, 945, 0, 3840, 181280, 997576, 1194380, 315294, 10395

Offset

0,10

Comments

T(n,k) is the number of down-up permutations (a(i),i=1..n)) on [n] such that the subpermutation of peaks (a(1),a(3),a(5),...) 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.

Links

Table of n, a(n) for n=0..54.

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, where A[m,r] generates A194354.

Example

Table begins
\ k.0....1.....2.....3.....4.....5
n
0 |.1
1 |.0....1
2 |.0....1
3 |.0....1.....1
4 |.0....2.....3
5 |.0....3....10.....3
6 |.0....8....38....15
7 |.0...15...121...121....15
8 |.0...48...540...692...105
9 |.0..105..1804..4118..1804...105
T(10,3) counts the down-up permutation (9 3 10 6 8 2 5 4 7 1) because the subpermutation of peaks splits into 3 decreasing runs: 9, 10 8 5, 7.
T(4,1)=2 counts 4231, 4132.

Mathematica

Unprotect[C]; Clear[A, C];
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] ];
C[m_, r_]/; 0<=m<=1 := If[r==m, 1, 0];
C[m_, r_]/; m>=2 && (r<1 || r>Floor[(m+1)/2]) := 0;
C[m_, r_]/; EvenQ[m] && 1<=r<=(m+1)/2 := C[m, r] = Module[{n=(m-2)/2},
Sum[Binomial[2n+1, 2k]C[2k, s]A[2n-2k+1, r-s], {k, 0, n-1}, {s, 0, r}] + (2n+1) C[2n, r-1] ];
C[m_, r_]/; OddQ[m] && m>=2 && 1<=r<=(m+1)/2 := C[m, r] = Module[{n=(m-1)/2},
Sum[Binomial[2n, 2k]C[2k, s]A[2n-2k, r-s], {k, 0, n-1}, {s, 0, r}] + C[2n, r-1] ];
Table[C[m, r], {m, 0, 12}, {r, 0, (m+1)/2}]

Crossrefs

Row sums are A000111. Column k=1 is the double factorials A006882. The main diagonal is A001147. The analogous array for up-down sequences is A194354.

Sequence in context: A245255 A180188 A316607 * A216217 A253283 A261719

Adjacent sequences: A194362 A194363 A194364 * A194366 A194367 A194368

Keyword

nonn,tabl

Author

David Callan, Aug 23 2011

Status

approved