login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A177267 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). 9
1, 2, 0, 5, 1, 0, 14, 10, 0, 0, 42, 70, 8, 0, 0, 132, 420, 168, 0, 0, 0, 429, 2310, 2121, 180, 0, 0, 0, 1430, 12012, 20790, 6088, 0, 0, 0, 0, 4862, 60060, 174174, 115720, 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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
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.
The sum of the entries in row n is n!.
The number of nonzero entries in row n is floor((n+1)/2).
T(n,0) = A000108(n) (the Catalan numbers).
Apparently T(n,1) = A002802(n-3).
Last nonzero terms in rows with odd n appear to be A060593. [Joerg Arndt, Nov 01 2012.]
REFERENCES
S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191.
LINKS
FORMULA
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
EXAMPLE
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).
Triangle starts:
[ 1] 1,
[ 2] 2, 0,
[ 3] 5, 1, 0,
[ 4] 14, 10, 0, 0,
[ 5] 42, 70, 8, 0, 0,
[ 6] 132, 420, 168, 0, 0, 0,
[ 7] 429, 2310, 2121, 180, 0, 0, 0,
[ 8] 1430, 12012, 20790, 6088, 0, 0, 0, 0,
[ 9] 4862, 60060, 174174, 115720, 8064, 0, 0, 0, 0,
[10] 16796, 291720, 1309308, 1624480, 386496, 0, 0, 0, 0, 0,
[11] 58786, 1385670, 9087078, 18748730, 10031736, 604800, 0, 0, ...,
[12] 208012, 6466460, 59306676, 188208020, 186698512, 38113920, 0, ...,
[13] 742900, 29745716, 368588220, 1700309468, 2788065280, 1271140416, 68428800, 0, ...,
...
MAPLE
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
# second Maple program:
b:= proc(n) option remember; `if`(n<2, 1, ((4*n-2)*
b(n-1)+(n-2)*(n-1)^2*expand(x*b(n-2)))/(n+1))
end:
T:= (n, k)-> coeff(b(n), x, k):
seq(seq(T(n, k), k=0..n-1), n=1..12); # Alois P. Heinz, Feb 16 2024
MATHEMATICA
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 *)
CROSSREFS
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]).
Row sums give A000142.
T(2n+1,n) gives A060593.
Sequence in context: A202209 A201730 A188449 * A188445 A350158 A327806
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, May 27 2010
EXTENSIONS
Terms for rows 12 and 13 from Joerg Arndt, Jan 24 2011.
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)