|
%I #18 Sep 10 2016 10:21:31
%S 1,55,1866,49523,1147175,24446239,492996938,9566197039,180473841477,
%T 3333072098404,60544351368853,1085308194335997,19246250384730902,
%U 338260488991568790,5900404989342994004,102262917165512555831,1762556960555529202081,30231974203021095081766,516347665987538314322805,8785795492453186831736382
%N The number of 321-avoiding linear extensions of the comb poset K_{4,n}^beta.
%H C. Defant, <a href="http://arxiv.org/abs/1608.03951">Poset Pattern-Avoidance Problems Posed by Yakoubov</a>, arXiv:1608.03951 [math.CO], 2016.
%H S. Yakoubov, <a href="http://arxiv.org/abs/1310.2979">Pattern Avoidance in Extensions of Comb-Like Posets</a>, arXiv preprint arXiv:1310.2979 [math.CO], 2013.
%F 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=4..(3n+1)}(F_{4,n}(k)*Binomial(4n-k,n-1)).
%F lim_{n->inf}(a(n)^(1/n))=16.
%e One of the a(2)=55 321-avoiding linear extensions of K_{4,2}^beta is 12534678 because this permutation avoids the pattern 321, the entries 1,2,3,4 appear in increasing order, 1 precedes 5, 2 precedes 6, 3 precedes 7, and 4 precedes 8.
%t F[s_, t_, k_] :=
%t If[s <= k <= (s - 1) t + 1,
%t If[s == 2, 1,
%t Sum[F[s - 1, t, i] Sum[
%t Binomial[k - i - 1, j], {j, k - (s - 2) t - 2, t - 1}], {i,
%t s - 1, k - 1}]], 0]
%t Table[Sum[F[4, n, k] Binomial[4 n - k, n - 1], {k, 4, 3 n + 1}], {n, 1, 17}]
%K nonn
%O 1,2
%A _Colin Defant_, Aug 13 2016
|
