login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A299927 Number of permutations of length n that avoid the patterns 213 and 312 and have k double ascents, read by rows. 1
1, 1, 2, 3, 1, 4, 3, 1, 5, 6, 4, 1, 6, 10, 10, 5, 1, 7, 15, 20, 15, 6, 1, 8, 21, 35, 35, 21, 7, 1, 9, 28, 56, 70, 56, 28, 8, 1, 10, 36, 84, 126, 126, 84, 36, 9, 1, 11, 45, 120, 210, 252, 210, 120, 45, 10, 1, 12, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

In a permutation avoiding 213 and 312, all digits before n are increasing and all digits after n are decreasing.  If k=0, either n is the first digit or the second digit of the permutation.  If k >= 1, there are binomial(n-1, k+1) ways to choose k+1 digits before n; these digits together with n account for k double ascents.

For n >= 1, the sum of row n is 2^(n-1).

LINKS

Michael De Vlieger, Table of n, a(n) for n = 0..11176 (rows 0 <= n <= 150, flattened).

M. Bukata, R. Kulwicki, N. Lewandowski, L. Pudwell, J. Roth, and T. Wheeland, Distributions of Statistics over Pattern-Avoiding Permutations, arXiv preprint arXiv:1812.07112 [math.CO], 2018.

FORMULA

If k=0 and n>0, a(n,k)=n.

If k >= 1, a(n,k) = binomial(n-1,k+1).

EXAMPLE

a(5,0)=5.  This counts the permutations 15432, 25431, 35421, 45321, and 54321.

a(5,1)=6.  This counts the permutations 12543, 13542, 14532, 23541, 24531, and 34521.

Triangle begins:

   1;

   1;

   2;

   3,  1;

   4,  3,   1;

   5,  6,   4,   1;

   6, 10,  10,   5,   1;

   7, 15,  20,  15,   6,   1;

   8, 21,  35,  35,  21,   7,   1;

   9, 28,  56,  70,  56,  28,   8,   1;

  10, 36,  84, 126, 126,  84,  36,   9,  1;

  11, 45, 120, 210, 252, 210, 120,  45, 10,  1;

  12, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1;

MAPLE

f:= proc(n, k)

if n = 0 and k = 0 then return 1:

elif k = 0 then return n:

else return binomial(n-1, k+1):

fi: end:

f(0, 0), f(1, 0), seq(seq(f(i, j), j = 0 .. i-2), i = 2 .. 12)

MATHEMATICA

Table[Which[And[n > 0, k == 0], n, k >= 1, Binomial[n - 1, k + 1], True, 1], {n, 0, 12}, {k, 0, If[n < 2, 0, n - 2]}] // Flatten (* Michael De Vlieger, Feb 07 2019 *)

CROSSREFS

Sequence in context: A255054 A011857 A242360 * A006021 A002186 A125936

Adjacent sequences:  A299924 A299925 A299926 * A299928 A299929 A299930

KEYWORD

easy,nonn,tabf

AUTHOR

Lara Pudwell, Dec 15 2018

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 March 23 04:46 EDT 2019. Contains 321422 sequences. (Running on oeis4.)