login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A098906 Triangle read by rows: T(n,k) is the number of down-up permutations on [n] with k left-to-right maxima. 0
1, 1, 1, 1, 2, 3, 5, 8, 3, 16, 30, 15, 61, 121, 75, 15, 272, 588, 420, 105, 1385, 3128, 2478, 840, 105, 7936, 18960, 16380, 6300, 945, 50521, 124921, 115350, 51030, 11025, 945, 353792, 911328, 893640, 429660, 103950, 10395, 2702765, 7158128, 7365633 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

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

LINKS

Table of n, a(n) for n=1..45.

L. Carlitz and R. Scoville, Enumeration of up-down permutations by upper records, Monatshefte für Mathematik, 79 (1975) 3-12.

Alan D. Sokal, The Euler and Springer numbers as moment sequences, arXiv:1804.04498 [math.CO], 2018.

FORMULA

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.

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

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

EXAMPLE

Table begins

  n\k|  1    2    3    4

-----+------------------

  1  |  1

  2  |  1

  3  |  1    1

  4  |  2    3

  5  |  5    8    3

  6  | 16   30   15

  7  | 61  121   75   15

  8  |272  588  420  105

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

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

MATHEMATICA

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]

CROSSREFS

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.

Sequence in context: A064737 A246558 A307638 * A007887 A105472 A030132

Adjacent sequences:  A098903 A098904 A098905 * A098907 A098908 A098909

KEYWORD

nonn,tabl

AUTHOR

David Callan, Nov 04 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 22 16:37 EST 2020. Contains 331152 sequences. (Running on oeis4.)