login
Triangle read by rows: T(n,k) is the number of permutations p of [n] in which the length of the longest initial segment avoiding the 123-, the 132- and the 231-pattern is equal to k.
1

%I #20 Sep 09 2020 18:14:36

%S 1,0,2,0,3,3,0,12,8,4,0,60,40,15,5,0,360,240,90,24,6,0,2520,1680,630,

%T 168,35,7,0,20160,13440,5040,1344,280,48,8,0,181440,120960,45360,

%U 12096,2520,432,63,9,0,1814400,1209600,453600,120960,25200,4320,630,80,10,0

%N Triangle read by rows: T(n,k) is the number of permutations p of [n] in which the length of the longest initial segment avoiding the 123-, the 132- and the 231-pattern is equal to k.

%C Row sums are the factorial numbers (A000142).

%H Michael De Vlieger, <a href="/A094112/b094112.txt">Table of n, a(n) for n = 1..11325</a> (rows 1 <= n <= 150, flattened)

%H Olivier Bodini, Antoine Genitrini, Mehdi Naima, <a href="https://arxiv.org/abs/1808.08376">Ranked Schröder Trees</a>, arXiv:1808.08376 [cs.DS], 2018.

%H Olivier Bodini, Antoine Genitrini, Cécile Mailler, Mehdi Naima, <a href="https://hal.archives-ouvertes.fr/hal-02865198">Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study</a>, hal-02865198 [math.CO] / [math.PR] / [cs.DS] / [cs.DM], 2020.

%H E. Deutsch and W. P. Johnson, <a href="http://www.jstor.org/stable/3219101">Create your own permutation statistics</a>, Math. Mag., 77, 130-134, 2004.

%H R. Simion and F. W. Schmidt, <a href="https://doi.org/10.1016/S0195-6698(85)80052-4">Restricted permutations</a>, European J. Combin., 6, 383-406, 1985.

%F T(n, k) = n!/[(k-2)!k] for 2<=k<=n-1; T(n, n)=n; T(n, 1)=0 for n>=2; T(n, k)=0 for k>n.

%F G.f.: sum(T(n, k)t^k z^n/n!, n, k>=1) = z[(t-1)exp(tz)+1]/(1-z).

%e T(4,3)=8 because the permutations 2134, 2143, 3124, 3142, 3241, 4123, 4132 and 4231 do not avoid all three patterns 123, 132 and 231, but their initial segments of length three, namely 213, 214, 312, 314, 324, 412, 413 and 423, do.

%e Triangle begins:

%e 1;

%e 0,2;

%e 0,3,3;

%e 0,12,8,4;

%e 0,60,40,15,5;

%e 0,360,240,90,24,6;

%e ...

%p T:=proc(n,k) if n=1 and k=1 then 1 elif n=1 then 0 elif k=1 then 0 elif k=n then n elif k>1 and k<n then n!/(k-2)!/k else 0 fi end: seq(seq(T(n,k),k=1..n),n=1..11);

%t T[n_, k_] := Which[n == 1 && k == 1, 1, n == 1, 0, k == 1, 0, k == n, n, k > 1 && k < n, n!/(k-2)!/k, True, 0]; Table[T[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jan 22 2019, from PARI *)

%Y Cf. A000142.

%K nonn,tabl

%O 1,3

%A _Emeric Deutsch_, May 31 2004