cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

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

Original entry on oeis.org

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
Offset: 1

Views

Author

Emeric Deutsch, May 27 2010

Keywords

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.]

Examples

			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, ...,
...

References

  • S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191.

Links

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.
Cf. A000108, A002802.

Programs

  • 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 *)

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

Extensions

Terms for rows 12 and 13 from Joerg Arndt, Jan 24 2011.

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

Original entry on oeis.org

1, 1, 0, 4, 0, 0, 11, 4, 0, 0, 36, 40, 0, 0, 0, 117, 290, 48, 0, 0, 0, 393, 1785, 1008, 0, 0, 0, 0, 1339, 9996, 12712, 1440, 0, 0, 0, 0, 4630, 52584, 123858, 48312, 0, 0, 0, 0, 0, 16193, 264720, 1027446, 904840, 80640, 0, 0, 0, 0, 0, 57201, 1290135, 7627158, 12449800, 3807936, 0
Offset: 1

Views

Author

Emeric Deutsch, May 30 2010

Keywords

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 A002467(n).
The number of entries in row n is floor(n/2).
T(n,0) = A106640(n-1) .

Examples

			T(3,0)=4 because all non-derangements of {1,2,3}, namely 123=(1)(2)(3), 132=(1)(23), 213=(12)(3), and 321=(13)(2) have genus 0. This follows easily 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).
Triangle starts:
[ 1]  1,
[ 2]  1, 0,
[ 3]  4, 0, 0,
[ 4]  11, 4, 0, 0,
[ 5]  36, 40, 0, 0, 0,
[ 6]  117, 290, 48, 0, 0, 0,
[ 7]  393, 1785, 1008, 0, 0, 0, 0,
[ 8]  1339, 9996, 12712, 1440, 0, 0, 0, 0,
[ 9]  4630, 52584, 123858, 48312, 0, 0, 0, 0, 0,
[10]  16193, 264720, 1027446, 904840, 80640, 0, 0, 0, 0, 0,
[11]  57201, 1290135, 7627158, 12449800, 3807936, 0, 0, 0, 0, 0, 0,
[12]  203799, 6133930, 52188774, 140356480, 96646176, 7257600, 0, ...,
[13]  731602, 28603718, 335517468, 1373691176, 1749377344, 448306560, 0, ...,
...

References

  • S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8 (1998), 169-191.

Crossrefs

Cf. A177267 (genus of all permutations).
Cf. A178514 (genus of derangements), A178515 (genus of involutions), A178516 (genus of up-down permutations), A178518 (permutations of [n] having genus 0 and p(1)=k), A185209 (genus of connected permutations).
Cf. A002467, A106640.

Programs

  • Maple
    n := 7: 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: 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: nrcyc := proc (p) local pc: 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: NDER := {}: for i to factorial(n) do if nrfp(P[i]) > 0 then NDER := `union`(NDER, {P[i]}) else end if end do: f[n] := sort(add(t^gen(NDER[j]), j = 1 .. nops(NDER))): seq(coeff(f[n], t, j), j = 0 .. floor((1/2)*n)-1); # yields the entries in the specified row n

Extensions

Terms beyond row 7 from Joerg Arndt, Nov 01 2012.

A218538 Triangle read by rows: T(n,k) is the number of permutations of{1,2,...,n} avoiding [x,x+1] having genus k (see first comment for definition of genus).

Original entry on oeis.org

1, 1, 0, 3, 0, 0, 7, 4, 0, 0, 19, 29, 5, 0, 0, 53, 180, 76, 0, 0, 0, 153, 1004, 901, 61, 0, 0, 0, 453, 5035, 8884, 2315, 0, 0, 0, 0, 1367, 23653, 74177, 46285, 2847, 0, 0, 0, 0, 4191, 106414, 546626, 667640, 143586, 0, 0, 0, 0, 0, 13015, 463740, 3658723, 7777935, 3896494, 209624, 0
Offset: 1

Views

Author

Joerg Arndt, Nov 01 2012

Keywords

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.
Row sums are A000255 (permutations with no substring [x,x+1]).
First column is A078481.

Examples

			Triangle starts:
[ 1]  1,
[ 2]  1, 0,
[ 3]  3, 0, 0,
[ 4]  7, 4, 0, 0,
[ 5]  19, 29, 5, 0, 0,
[ 6]  53, 180, 76, 0, 0, 0,
[ 7]  153, 1004, 901, 61, 0, 0, 0,
[ 8]  453, 5035, 8884, 2315, 0, 0, 0, 0,
[ 9]  1367, 23653, 74177, 46285, 2847, 0, 0, 0, 0,
[10]  4191, 106414, 546626, 667640, 143586, 0, 0, 0, 0, 0,
[11]  13015, 463740, 3658723, 7777935, 3896494, 209624, 0, 0, 0, 0, 0,
[12]  40857, 1972339, 22712736, 77535694, 74678363, 13959422, 0, 0, ...,
[13]  129441, 8228981, 132804891, 685673340, 1131199122, 485204757, 23767241, 0, ...,
...

Crossrefs

Cf. A177267 (genus of all permutations).
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).
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.