A161125 -id:A161125 - cp's OEIS frontend

A161126 Triangle read by rows: T(n,k) is the number of involutions of {1,2,...,n} having k descents (n >= 1; 0 <= k < n).

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 6, 12, 6, 1, 1, 9, 28, 28, 9, 1, 1, 12, 57, 92, 57, 12, 1, 1, 16, 105, 260, 260, 105, 16, 1, 1, 20, 179, 630, 960, 630, 179, 20, 1, 1, 25, 289, 1397, 3036, 3036, 1397, 289, 25, 1, 1, 30, 444, 2836, 8471, 12132, 8471, 2836, 444, 30, 1, 1, 36

Offset: 1

Emeric Deutsch, Jun 09 2009

Also number of ballot sequences of length n with k ascents; also number of standard Young tableaux with n cells such that there are k pairs of cells (v,v+1) with v+1 lying in a row below v. - Joerg Arndt, Feb 21 2014

See the Brualdi/Ma reference for the connection to A138177. - Joerg Arndt, Nov 02 2014

			T(4,2)=4 because we have 1432, 2143, 4231, and 3214.
Triangle starts:
  01: 1
  02: 1,  1
  03: 1,  2,   1
  04: 1,  4,   4,    1
  05: 1,  6,  12,    6,     1
  06: 1,  9,  28,   28,     9,      1
  07: 1, 12,  57,   92,    57,     12,      1
  08: 1, 16, 105,  260,   260,    105,     16,      1
  09: 1, 20, 179,  630,   960,    630,    179,     20,     1
  10: 1, 25, 289, 1397,  3036,   3036,   1397,    289,    25,    1
  11: 1, 30, 444, 2836,  8471,  12132,   8471,   2836,   444,   30,   1
  12: 1, 36, 659, 5434, 21529,  42417,  42417,  21529,  5434,  659,  36,  1
  13: 1, 42, 945, 9828, 50423, 132146, 181734, 132146, 50423, 9828, 945, 42, 1
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Richard A. Brualdi and Shi-Mei Ma, Enumeration of involutions by descents and symmetric matrices, European Journal of Combinatorics, vol. 43, pp. 220-228, (January 2015).
J. Désarménien and D. Foata, Fonctions symétriques et séries hypergéometriques basiques multivariées, Bull. Soc. Math. France, 113, 1985, 3-22.
Samantha Dahlberg, Combinatorial Proofs of Identities Involving Symmetric Matrices, arXiv:1410.7356 [math.CO], 2014-2017.
I. M. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory, Ser. A, 64, 1993, 189-215.
V. J. W. Guo and J. Zeng, The Eulerian distribution on involutions is indeed unimodal, J. Combin. Theory, Ser. A, 113, 2006, 1061-1071.

Cf. A000085, A161125, A138177.

P := proc (n) options operator, arrow: sort(simplify((1-t)^(n+1)*(sum(t^r*(sum(binomial((1/2)*r*(r+1)+k-1, k)*binomial(r+n-2*k, n-2*k), k = 0 .. floor((1/2)*n))), r = 0 .. infinity)))) end proc: for n to 12 do seq(coeff(P(n), t, j), j = 0 .. n-1) end do; # yields sequence in triangular form
T := proc(n, k) option remember; if k < 0 then 0 elif n <= k then 0 elif n = 1 and k = 0 then 1 elif n = 2 and k = 0 then 1 elif n = 2 and k = 1 then 1 else ((k+1)*T(n-1, k)+(n-k)*T(n-1, k-1)+((k+1)^2+n-2)*T(n-2, k)+(2*k*(n-k-1)-n+3)*T(n-2, k-1)+((n-k)^2+n-2)*T(n-2, k-2))/n end if end proc: for n to 12 do seq(T(n, k), k = 0 .. n-1) end do; # yields sequence in triangular form

P[n_, t_] := (1-t)^(n+1)*Sum[t^r*Binomial[n+r, n]*HypergeometricPFQ[{(1 - n)/2, -n/2, r(r+1)/2}, {(-n-r)/2, (1-n-r)/2}, 1], {r, 0, n}]; row[n_] := CoefficientList[P[n, t] + O[t]^n, t]; Table[row[n], {n, 1, 13}] // Flatten (* Jean-François Alcover, Dec 20 2016 *)

Sum_{k=1..n} T(n,k) = A000085(n) (row sums).
Sum_{k=0..n-1} k*T(n,k) = A161125(n).
Generating polynomial of row n is P(n,t) = (1-t)^(n+1) * Sum_{r>=0} t^r*Sum_{k=0..floor(n/2)} C(r(r+1)/2+k-1,k)*C(r+n-2k,n-2k) (see Eq. (2.5) in the Guo-Zeng paper; see first Maple program).
Recursive relation for n >= 3, k >= 0: n*T(n,k) = (k+1)*T(n-1,k) + (n-k)*T(n-1,k-1) + ((k+1)^2 + n-2)*T(n-2,k) + (2*k*(n-k-1)-n+3)*T(n-2,k-1) + ((n-k)^2+n-2)*T(n-2,k-2) (see Eq. (2.4) in the Guo-Zeng paper; see 2nd Maple program).

A225617 Number of (strict) inversions in all standard Young tableaux of size n.

Original entry on oeis.org

0, 0, 1, 7, 39, 188, 884, 4116, 19108, 89926, 427386, 2068934, 10163358, 50888024, 258983668, 1342912608, 7079970072, 38000183102, 207309599246, 1150329076074, 6484351459090, 37143321514076, 216001121263896, 1275332898098744, 7639400455469944, 46423461664822648

Offset: 1

Wouter Meeussen, Aug 04 2013

nonn

A (strict) inversion is a pair of cells (i,j) with iJoerg Arndt, Feb 18 2014]

Alois P. Heinz, Table of n, a(n) for n = 1..50
M. Shynar, On Inversions in Standard Young Tableaux
Wikipedia, Young tableau

Cf. A225618 (weak inversions), A161125 (descent numbers).

Cf. A000085 (Young tableaux with n cells).

b:= proc(l) option remember; `if`({l[]}={0}, [1, 0],
      add(`if`(l[j]>`if`(j=1, 0, l[j-1]), (f->f+[0, f[1]*
      add(l[h]-l[j], h=j+1..nops(l))])
      (b(subsop(j=l[j]-1, l))), 0), j=1..nops(l)))
    end:
g:= proc(n, i, l) `if`(n=0 or i=1, b([1$n, l[]]),
      `if`(i<1, 0, g(n, i-1, l)+
      `if`(i>n, 0, g(n-i, i, [i, l[]]))))
    end:
a:= n-> g(n$2, [])[2]:
seq(a(n), n=1..23);  # Alois P. Heinz, Aug 09 2013

inversions[t_?TableauQ]:= Block[{t0},t0=(First[Position[t,#1]]&) /@ Range[Max[t]]; Cases[Table[{i,j},{j,2,Max[t]},{i,j-1}],{i_,j_}/; MatchQ[t0[[i]]-t0[[j]],{?Negative,?Positive}]->{i,j},{2}]];
Table[Tr[Length[inversions[#]]& /@ Tableaux[n]],{n,13}]

Terms verified and more terms added, Joerg Arndt, Aug 07 2013

a(19)-a(26) from Alois P. Heinz, Aug 08 2013

A225618 Number of weak inversions in all standard Young tableaux of size n.

Original entry on oeis.org

0, 1, 6, 29, 125, 538, 2282, 9916, 43416, 195206, 891638, 4176002, 19920914, 97248184, 483752596, 2458123328, 12722535412, 67155870194, 360792258750, 1974047659038, 10983669569446, 62162472053580, 357454683655920, 2088497013864312, 12387836332741800

Offset: 1

Wouter Meeussen, Aug 04 2013

nonn

A weak inversion is a pair of cells (i,j) with iJoerg Arndt, Feb 18 2014]

Alois P. Heinz, Table of n, a(n) for n = 1..50
M. Shynar, On Inversions in Standard Young Tableaux
Wikipedia, Young tableau

Cf. A225617 (strict inversions), A161125 (descent numbers).

Cf. A000085 (Young tableaux with n cells).

b:= proc(l) option remember; `if`({l[]}={0}, [1, 0],
      add(`if`(l[j]>`if`(j=1, 0, l[j-1]), (f->f+[0, f[1]*
      add(l[h]-l[j]+1, h=j+1..nops(l))])
      (b(subsop(j=l[j]-1, l))), 0), j=1..nops(l)))
    end:
g:= proc(n, i, l) `if`(n=0 or i=1, b([1$n, l[]]),
      `if`(i<1, 0, g(n, i-1, l)+
      `if`(i>n, 0, g(n-i, i, [i, l[]]))))
    end:
a:= n-> g(n$2, [])[2]:
seq(a(n), n=1..23);  # Alois P. Heinz, Aug 09 2013

inversions[t_?TableauQ]:=Block[{t0},t0=(First[Position[t,#1]]&) /@ Range[Max[t]]; Cases[Table[{i,j},{j,2,Max[t]},{i,j-1}],{i_,j_}/;MatchQ[t0[[i]]-t0[[j]],{?Negative,?Positive}]->{i,j},{2}]];
Table[Tr[Length[weakinversions[#]]& /@ Tableaux[n]],{n,12}]

Terms verified and more terms added, Joerg Arndt, Aug 07 2013

a(19)-a(25) from Alois P. Heinz, Aug 08 2013

cp's OEIS Frontend

A161126 Triangle read by rows: T(n,k) is the number of involutions of {1,2,...,n} having k descents (n >= 1; 0 <= k < n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A225617 Number of (strict) inversions in all standard Young tableaux of size n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A225618 Number of weak inversions in all standard Young tableaux of size n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions