cp's OEIS Frontend

A178518 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).

%I A178518 #14 Feb 16 2024 08:01:22
%S A178518 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 A178518 28,42,429,429,132,84,70,70,84,132,1430,1430,429,264,210,196,210,264,
%U A178518 429,4862,4862,1430,858,660,588,588,660,858,1430,16796,16796,4862,2860,2145,1848,1764,1848,2145,2860,4862
%N A178518 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 A178518 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 A178518 Row sums are A000108 (Catalan numbers).
%C A178518 T(n,1) = A000108(n-1) (n >= 1).
%C A178518 T(n,2) = A000108(n-1) (n >= 2).
%C A178518 T(n,3) = A000108(n-2) (n >= 3).
%C A178518 T(n,n) = A000108(n-2) (n >= 2).
%C A178518 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 A178518 S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191.
%F A178518 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 A178518 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 A178518 T(4,3)=2 because we have 3214=(13)(2)(4) and 3241=(134)(2).
%e A178518 Triangle starts:
%e A178518    1;
%e A178518    1,  1;
%e A178518    2,  2,  1;
%e A178518    5,  5,  2,  2;
%e A178518   14, 14,  5,  4,  5;
%p A178518 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 A178518 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 A178518 Cf. A000108.
%K A178518 nonn,tabl
%O A178518 1,4
%A A178518 _Emeric Deutsch_, May 31 2010