login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Up-down permutations on [n] whose peaks have k rises.
1

%I #18 Oct 22 2024 05:37:21

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

%T 3584,3584,384,0,945,13884,26204,9104,384,0,3840,78848,188416,78848,

%U 3840,0,109,315294,1194380,997576,181280,3840

%N Up-down permutations on [n] whose peaks have k rises.

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

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

%D L. Carlitz, Enumeration of up-down permutations by number of rises, Pacific Journal of Mathematics, Vol. 45, no.1, 1973, 49-58.

%F Carlitz's recurrence underlies the Mathematica code below.

%e Table begins

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

%e n

%e 0 |.1

%e 1 |.1

%e 2 |.0....1

%e 3 |.0....2

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

%e 5 |.0....8.....8

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

%e 7 |.0...48...176....48

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

%e 9 |.0..384..3584..3584...384

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

%e T(4,1)=3 counts 1423, 2413, 3412.

%t Clear[A];

%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 Table[A[m,r],{m,0,12},{r,0,m/2}]

%Y Row sums are A000111. Column k=1 is the double factorials A006882.

%K nonn,tabl

%O 0,6

%A _David Callan_, Aug 23 2011