A194365 - OEIS

%I #15 Oct 23 2024 14:39:24

%S 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,

%T 692,105,0,105,1804,4118,1804,105,0,384,9104,26204,13884,945,0,945,

%U 32493,143458,143458,32493,945,0,3840,181280,997576,1194380,315294,10395

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

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

%C For n>=1, T(n,k) is nonzero only for 1 <= k <= n/2.

%H L. Carlitz, <a href="http://projecteuclid.org/euclid.pjm/1102947707">Enumeration of up-down permutations by number of rises</a>, Pacific Journal of Mathematics vol.45, no.1, 1973, 49-58.

%F Carlitz's recurrence underlies the Mathematica code below, where A[m,r] generates A194354.

%e Table begins

%e \ k.0....1.....2.....3.....4.....5

%e n

%e 0 |.1

%e 1 |.0....1

%e 2 |.0....1

%e 3 |.0....1.....1

%e 4 |.0....2.....3

%e 5 |.0....3....10.....3

%e 6 |.0....8....38....15

%e 7 |.0...15...121...121....15

%e 8 |.0...48...540...692...105

%e 9 |.0..105..1804..4118..1804...105

%e 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.

%e T(4,1)=2 counts 4231, 4132.

%t Unprotect[C];Clear[A,C];

%t A[m_,r_]/;0<=m<=1 := If[r==0,1,0];

%t A[m_,r_]/;m>=2 && (r<1 || r>m/2) := 0;

%t A[m_,r_]/;m>=2 && 1<=r<=m/2 && EvenQ[m] := A[m,r] = Module[{n=m/2},

%t 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] ];

%t A[m_,r_]/; m>=2 && 1<=r<=m/2 && OddQ[m] := A[m,r] = Module[{n=(m-1)/2},

%t 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] ];

%t C[m_,r_]/;0<=m<=1 := If[r==m,1,0];

%t C[m_,r_]/;m>=2 && (r<1 || r>Floor[(m+1)/2]) := 0;

%t C[m_,r_]/;EvenQ[m] && 1<=r<=(m+1)/2 := C[m,r] = Module[{n=(m-2)/2},

%t 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] ];

%t C[m_,r_]/;OddQ[m] && m>=2 && 1<=r<=(m+1)/2 := C[m,r] = Module[{n=(m-1)/2},

%t Sum[Binomial[2n,2k]C[2k,s]A[2n-2k,r-s],{k,0,n-1},{s,0,r}] + C[2n,r-1] ];

%t Table[C[m,r],{m,0,12},{r,0,(m+1)/2}]

%Y 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.

%K nonn,tabl

%O 0,10

%A _David Callan_, Aug 23 2011