|
%I #34 Feb 16 2024 07:49:31
%S 1,2,0,5,1,0,14,10,0,0,42,70,8,0,0,132,420,168,0,0,0,429,2310,2121,
%T 180,0,0,0,1430,12012,20790,6088,0,0,0,0,4862,60060,174174,115720,
%U 8064,0,0,0,0,16796,291720,1309308,1624480,386496,0,0,0,0,0,58786,1385670,9087078,18748730,10031736,604800,0,0,0,0,0,208012,6466460,59306676,188208020,186698512,38113920,0
%N Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having genus 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 The sum of the entries in row n is n!.
%C The number of nonzero entries in row n is floor((n+1)/2).
%C T(n,0) = A000108(n) (the Catalan numbers).
%C Apparently T(n,1) = A002802(n-3).
%C Last nonzero terms in rows with odd n appear to be A060593. [_Joerg Arndt_, Nov 01 2012.]
%D S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191.
%H Alois P. Heinz, <a href="/A177267/b177267.txt">Rows n = 1..141, flattened</a>
%F Let p(n, x) := g.f. of row n. Then (n+1) * p(n, x) = (4*n-2) * p(n-1, x) + x * (n-2) * (n-1)^2 * p(n-2, x). - _Michael Somos_, Sep 02 2017
%e T(3,1)=1 because 312 is the only permutation of {1,2,3} with genus 1 (we have p=312=(132), cp'=231*231=312=(132) and so g(p)=(1/2)(3+1-1-1)=1).
%e Triangle starts:
%e [ 1] 1,
%e [ 2] 2, 0,
%e [ 3] 5, 1, 0,
%e [ 4] 14, 10, 0, 0,
%e [ 5] 42, 70, 8, 0, 0,
%e [ 6] 132, 420, 168, 0, 0, 0,
%e [ 7] 429, 2310, 2121, 180, 0, 0, 0,
%e [ 8] 1430, 12012, 20790, 6088, 0, 0, 0, 0,
%e [ 9] 4862, 60060, 174174, 115720, 8064, 0, 0, 0, 0,
%e [10] 16796, 291720, 1309308, 1624480, 386496, 0, 0, 0, 0, 0,
%e [11] 58786, 1385670, 9087078, 18748730, 10031736, 604800, 0, 0, ...,
%e [12] 208012, 6466460, 59306676, 188208020, 186698512, 38113920, 0, ...,
%e [13] 742900, 29745716, 368588220, 1700309468, 2788065280, 1271140416, 68428800, 0, ...,
%e ...
%p n := 8: with(combinat): P := permute(n): 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: 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(P[j]), j = 1 .. factorial(n))): seq(coeff(f[n], t, j), j = 0 .. ceil((1/2)*n)-1); # yields the entries in the specified row n
%p # second Maple program:
%p b:= proc(n) option remember; `if`(n<2, 1, ((4*n-2)*
%p b(n-1)+(n-2)*(n-1)^2*expand(x*b(n-2)))/(n+1))
%p end:
%p T:= (n, k)-> coeff(b(n), x, k):
%p seq(seq(T(n, k), k=0..n-1), n=1..12); # _Alois P. Heinz_, Feb 16 2024
%t T[ n_, k_] := If[ n < 1 || k >= n, 0, Module[{pn = Table[i, {i, n}]}, Do[ pn[[i]] = ((4 i - 2) pn[[i - 1]] + x (i - 2) (i - 1)^2 pn[[i - 2]])/(i + 1) // Expand, {i, 3, n}]; Coefficient[pn[[n]], x, k]]]; (* _Michael Somos_, Sep 02 2017 *)
%Y Cf. A178514 (genus of derangements), A178515 (genus of involutions), A178516 (genus of up-down permutations), A178517 (genus of non-derangement permutations), A178518 (permutations of [n] having genus 0 and p(1)=k), A185209 (genus of connected permutations), A218538 (genus of permutations avoiding [x,x+1]).
%Y Row sums give A000142.
%Y T(2n+1,n) gives A060593.
%Y Cf. A000108, A002802.
%K nonn,tabl
%O 1,2
%A _Emeric Deutsch_, May 27 2010
%E Terms for rows 12 and 13 from _Joerg Arndt_, Jan 24 2011.
|
