

A194354


Updown permutations on [n] whose peaks have k rises.


1



1, 1, 0, 1, 0, 2, 0, 3, 2, 0, 8, 8, 0, 15, 38, 8, 0, 48, 176, 48, 0, 105, 692, 540, 48, 0, 384, 3584, 3584, 384, 0, 945, 13884, 26204, 9104, 384, 0, 3840, 78848, 188416, 78848, 3840, 0, 109, 315294, 1194380, 997576, 181280, 3840
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


COMMENTS

Triangle read by rows: T(n,k) is the number of updown permutations (a(i),i=1..n)) on [n] such that the subpermutation of peaks (a(2),a(4),a(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 updown permutations by number of rises, Pacific Journal of Mathematics, Vol. 45, no.1, 1973, 4958.


LINKS

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


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 updown 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[2n1, 2k+1]A[2k+1, s]A[2n2k2, rs], {k, 0, n2}, {s, 0, r}] + A[2n1, r1] ];
A[m_, r_]/; m>=2 && 1<=r<=m/2 && OddQ[m] := A[m, r] = Module[{n=(m1)/2},
Sum[Binomial[2n, 2k+1]A[2k+1, s]A[2n2k1, rs], {k, 0, n2}, {s, 0, r}] + 2n A[2n1, r1] ];
Table[A[m, r], {m, 0, 12}, {r, 0, m/2}]


CROSSREFS

Row sums are A000111. Column k=1 is the double factorials A006882.
Sequence in context: A097418 A154752 A271868 * A156776 A292108 A342176
Adjacent sequences: A194351 A194352 A194353 * A194355 A194356 A194357


KEYWORD

nonn,tabl


AUTHOR

David Callan, Aug 23 2011


STATUS

approved



