A275941 The number of 321-avoiding linear extensions of the comb poset K_{3,n}^beta.

1, 12, 127, 1222, 11096, 97140, 830152, 6977918, 57968938, 477479647, 3908025133, 31832823274, 258341395508, 2090604162540, 16880171617952, 136054564607870, 1095059149237006, 8803843758642693, 70715260139217139, 567591311612071157, 4553028235287085366

Offset

1,2

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 39 terms from Colin Defant)

C. Defant, Poset Pattern-Avoidance Problems Posed by Yakoubov, arXiv:1608.03951 [math.CO], 2016.

S. Yakoubov, Pattern Avoidance in Extensions of Comb-Like Posets, arXiv preprint arXiv:1310.2979 [math.CO], 2013.

Formula

Define F_{2,t}(k)=1 if 2<=k<=t+1 and 0 otherwise. For s>=3, let F_{s,t}(k) = Sum_{i=(s-1)..(k-1)} (F_{s-1,t}(i) Sum_{j=(k-(s-2)t-2)..(t-1)} (binomial(k-i-1,j))). Then a(n) = Sum_{k=3..(2n+1)} (F_{3,n}(k)*binomial(3n-k,n-1)).

limit_{n-> infinity} a(n)^(1/n) = 8.

Example

The a(2)=12 321-avoiding linear extensions of K_{3,2}^beta are 123456, 123465, 123546, 123564, 123645, 124356, 124365, 124536, 125346, 125364, 142356, 142365

Maple

a:= proc(n) option remember; `if`(n<4, [0, 1, 12, 127][n+1],
     ((n-1)*(2*n-3)*(-22080-140168*n+729723*n^4-1060811*n^3
     +702042*n^2+28875*n^6-235565*n^5)*a(n-1) -(2*(-144000
     -1406688*n+29671327*n^4-23732755*n^3+9830558*n^2
     +8703775*n^6-1912636*n^7+174020*n^8-21187921*n^5))*a(n-2)
     +(48*(3*n-7))*(2*n-1)*(2*n-5)*(3*n-8)*(385*n^4-1298*n^3
     +1411*n^2-618*n+144)*a(n-3)) / ((2*(385*n^4-2838*n^3
     +7615*n^2-8874*n+3856))*(n-1)*n*(2*n-3)*(2*n-1)))
    end:
seq(a(n), n=1..30);  # Alois P. Heinz, Aug 18 2016

Mathematica

F[s_, t_, k_] :=
If[s <= k <= (s - 1) t + 1,
  If[s == 2, 1,
   Sum[F[s - 1, t, i] Sum[
      Binomial[k - i - 1, j], {j, k - (s - 2) t - 2, t - 1}], {i,
     s - 1, k - 1}]], 0]
Table[Sum[F[3, n, k] Binomial[3 n - k, n - 1], {k, 3, 2 n + 1}], {n,
  1, 20}]

Crossrefs

Sequence in context: A204768 A045508 A215774 * A173359 A199037 A099157

Adjacent sequences: A275938 A275939 A275940 * A275942 A275943 A275944

Keyword

nonn,easy

Author

Colin Defant, Aug 12 2016

Status

approved