|
%I #14 Feb 16 2024 08:01:22
%S 1,1,1,2,2,1,5,5,2,2,14,14,5,4,5,42,42,14,10,10,14,132,132,42,28,25,
%T 28,42,429,429,132,84,70,70,84,132,1430,1430,429,264,210,196,210,264,
%U 429,4862,4862,1430,858,660,588,588,660,858,1430,16796,16796,4862,2860,2145,1848,1764,1848,2145,2860,4862
%N Triangle read by rows: T(n,k) is the number of permutations p of {1,2,...,n} having genus 0 and such that p(1)=k (see first comment for definition of genus).
%C The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p) = (1/2)[n+1-z(p)-z(cp')], where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q.
%C Row sums are A000108 (Catalan numbers).
%C T(n,1) = A000108(n-1) (n >= 1).
%C T(n,2) = A000108(n-1) (n >= 2).
%C T(n,3) = A000108(n-2) (n >= 3).
%C T(n,n) = A000108(n-2) (n >= 2).
%C A permutation p of {1,2,...,n} has genus 0 if and only if the cycle decomposition of p gives a noncrossing partition of {1,2,...,n} and each cycle of p is increasing (see Lemma 2.1 of the Dulucq-Simion reference).
%D S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191.
%F T(n,1)=c(n-1); T(n,k) = c(n-k+1)*c(k-2) if 2 <= k <= n, where c(j) = binomial(2j,j)/(j+1) = A000108(j) are the Catalan numbers.
%F G.f. = G(t,z) = t*z*C(z)+t^2*z*(C(z)-1)*C(tz), where C(z) = (1-sqrt(1-4*z))/(2z) is the Catalan function.
%e T(4,3)=2 because we have 3214=(13)(2)(4) and 3241=(134)(2).
%e Triangle starts:
%e 1;
%e 1, 1;
%e 2, 2, 1;
%e 5, 5, 2, 2;
%e 14, 14, 5, 4, 5;
%p c := proc (n) options operator, arrow: binomial(2*n, n)/(n+1) end proc: a := proc (n, k) if k = 1 then c(n-1) elif k <= n then c(n-k+1)*c(k-2) else 0 end if end proc: for n to 11 do seq(a(n, k), k = 1 .. n) end do; # yields sequence in triangular form
%t t[n_, 1] := CatalanNumber[n-1]; t[n_, k_] := CatalanNumber[n-k+1] * CatalanNumber[k-2]; Table[t[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jul 10 2013 *)
%Y Cf. A000108.
%K nonn,tabl
%O 1,4
%A _Emeric Deutsch_, May 31 2010
|
