A098906 - OEIS

%I #22 Apr 27 2023 10:47:29

%S 1,1,1,1,2,3,5,8,3,16,30,15,61,121,75,15,272,588,420,105,1385,3128,

%T 2478,840,105,7936,18960,16380,6300,945,50521,124921,115350,51030,

%U 11025,945,353792,911328,893640,429660,103950,10395,2702765,7158128,7365633

%N Triangle read by rows: T(n,k) is the number of down-up permutations on [n] with k left-to-right maxima.

%C T(n,k)=0 unless 1 <= k <= (n+1)/2.

%H L. Carlitz and R. Scoville, <a href="http://www.digizeitschriften.de/main/dms/img/?PPN=GDZPPN002479079">Enumeration of up-down permutations by upper records</a>, Monatshefte für Mathematik, 79 (1975) 3-12.

%H Alan D. Sokal, <a href="https://arxiv.org/abs/1804.04498">The Euler and Springer numbers as moment sequences</a>, arXiv:1804.04498 [math.CO], 2018.

%F The even-indexed rows have g.f. A(x, y):=Sum_{k=1..n} a(n, k)x^(2n)*y^k satisfying the functional equation A(x, y)(1+x*y^2) = x*y(1+(y+1)A(x, y+2)). The odd-indexed rows have g.f. B(x, y):=Sum_{k=1..n} b(n, k)x^(2n-1)*y^k satisfying the slightly different equation B(x, y)(1+x*(y+1)^2) = x*y(1+(y+1)B(x, y+2)). The recurrence relations underlying these functional equations are given in the Mathematica code below.

%F G.f.: 1 + Sum_{n>=1,k=1..n} T(2n,k)x^(2n)/(2n)!*y^k = (sec x)^y,

%F Sum_{n>=1, k=1..n} T(2n-1,k)x^(2n-2)/(2n-2)!y^k = y(sec x)^(1+y) (see Carlitz and Scoville link). - _David Callan_, Nov 21 2011

%e Table begins

%e   n\k|  1    2    3    4

%e -----+------------------

%e   1  |  1

%e   2  |  1

%e   3  |  1    1

%e   4  |  2    3

%e   5  |  5    8    3

%e   6  | 16   30   15

%e   7  | 61  121   75   15

%e   8  |272  588  420  105

%e For example, w = 21534 has 2 left-to-right maxima: w_1 = 2 and w_3 = 5.

%e T(4,2) = 3 because 2143, 3142, 3241 each have 2 left-to-right maxima.

%t Clear[a, b] EvenMultiplier[k_, j_]/;j<=k-2 := 0; EvenMultiplier[k_, j_]/;j>=k-1 := (2^(j+1-k) (Binomial[j, k-2]+Binomial[j+1, k-1])); a[1, 1]=1;a[n_, 0]:=0; a[n_, k_]/;1<=k<=n && n>1 := a[n, k] = Sum[EvenMultiplier[k, j]a[n-1, j], {j, k-1, n-1}]; OddMultiplier[k_, j_]:=EvenMultiplier[k, j]-If[j==k-1, 2, 0]-If[j==k, 1, 0]; b[1, 1]=1;b[n_, 0]:=0; b[n_, k_]/;1<=k<=n && n>1 := b[n, k] = Sum[OddMultiplier[k, j]b[n-1, j], {j, k-1, n-1}] Flatten[Table[{ Table[b[n, k], {k, n}], Table[a[n, k], {k, n}] }, {n, 7} ], 1]

%Y Row sums are the up-down numbers (A000111), as is column k=1. Topmost entries in each column form the double factorials (A001147). The even-indexed rows form A085734.

%K nonn,tabf

%O 1,5

%A _David Callan_, Nov 04 2004