cp's OEIS Frontend

A178516 Triangle read by rows: T(n,k) is the number of up-down permutations of {1,2,...,n} having genus k (see first comment for definition of genus).

%I A178516 #21 Nov 25 2019 00:59:07
%S A178516 1,1,0,2,0,0,2,3,0,0,6,10,0,0,0,6,38,17,0,0,0,22,142,104,4,0,0,0,22,
%T A178516 351,778,234,0,0,0,0,90,1419,4086,2235,106,0,0,0,0,90,2856,17402,
%U A178516 24357,5816,0,0,0,0,0,394,12208,87434,171305,78705,3746,0,0,0,0,0,394,21676,278062,1053425,1120648,228560,0
%N A178516 Triangle read by rows: T(n,k) is the number of up-down permutations of {1,2,...,n} having genus k (see first comment for definition of genus).
%C A178516 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 A178516 The sum of the entries in row n is A000111(n) (Euler or up-down numbers).
%C A178516 Apparently, row n contains ceiling(n/2) nonzero entries.
%C A178516 T(2n-1,0) = T(2n,0) = A006318(n-1) (the large Schroeder numbers).
%H A178516 S. Dulucq and R. Simion, <a href="http://dx.doi.org/10.1023/A:1008689811936">Combinatorial statistics on alternating permutations</a>, J. Algebraic Combinatorics, 8, 1998, 169-191.
%e A178516 T(4,0)=2. From the fact that 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), it follows that the up-down permutations 2314 = (123)(4) and 1324 = (1)(23)(4) have genus 0, while 2413 = (1243), 3412 = (13)(24), and 1423 = (1)(243) do not.
%e A178516 Triangle starts:
%e A178516 [ 1]   1,
%e A178516 [ 2]   1,     0,
%e A178516 [ 3]   2,     0,      0,
%e A178516 [ 4]   2,     3,      0,       0,
%e A178516 [ 5]   6,    10,      0,       0,       0,
%e A178516 [ 6]   6,    38,     17,       0,       0,      0,
%e A178516 [ 7]  22,   142,    104,       4,       0,      0, 0,
%e A178516 [ 8]  22,   351,    778,     234,       0,      0, 0, 0,
%e A178516 [ 9]  90,  1419,   4086,    2235,     106,      0, 0, 0, 0,
%e A178516 [10]  90,  2856,  17402,   24357,    5816,      0, 0, 0, 0, 0,
%e A178516 [11] 394, 12208,  87434,  171305,   78705,   3746, 0, 0, 0, 0, 0,
%e A178516 [12] 394, 21676, 278062, 1053425, 1120648, 228560, 0, 0, 0, 0, 0, 0,
%e A178516 ...
%p A178516 n := 7: with(combinat): descents := proc (p) local A, i: A := {}: for i to nops(p)-1 do if p[i+1] < p[i] then A := `union`(A, {i}) else end if end do: A end proc; UD := proc (n) local ud, P, j: ud := {}: P := permute(n): for j to factorial(n) do if descents(P[j]) = {seq(2*k, k = 1 .. ceil((1/2)*n)-1)} then ud := `union`(ud, {P[j]}) else end if end do: ud end proc; inv := proc (p) local j, q: for j to nops(p) do q[p[j]] := j end do: [seq(q[i], i = 1 .. nops(p))] end proc: nrcyc := proc (p) local nrfp, pc: nrfp := proc (p) local ct, j: ct := 0: for j to nops(p) do if p[j] = j then ct := ct+1 else end if end do: ct end proc:
%p A178516 pc := convert(p, disjcyc): nops(pc)+nrfp(p) end proc: b := proc (p) local c: c := [seq(i+1, i = 1 .. nops(p)-1), 1]: [seq(c[p[j]], j = 1 .. nops(p))] end proc: gen := proc (p) options operator, arrow: (1/2)*nops(p)+1/2-(1/2)*nrcyc(p)-(1/2)*nrcyc(b(inv(p))) end proc: f[n] := sort(add(t^gen(UD(n)[j]), j = 1 .. nops(UD(n)))): seq(coeff(f[n], t, j), j = 0 .. ceil((1/2)*n)-1); # yields the entries in the specified row n
%Y A178516 Cf. A177267.
%Y A178516 Cf. A000111, A006318, A169816.
%K A178516 nonn,hard,tabl
%O A178516 1,4
%A A178516 _Emeric Deutsch_, May 29 2010
%E A178516 Terms beyond row 7 from _Joerg Arndt_, Nov 01 2012