A161126 -id:A161126 - cp's OEIS frontend

A138177 Triangle T(n,k) read by rows: number of k X k symmetric matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n, n>=1, 1<=k<=n.

1, 1, 2, 1, 4, 4, 1, 7, 15, 10, 1, 10, 36, 52, 26, 1, 14, 74, 176, 190, 76, 1, 18, 132, 460, 810, 696, 232, 1, 23, 222, 1060, 2705, 3756, 2674, 764, 1, 28, 347, 2180, 7565, 15106, 17262, 10480, 2620, 1, 34, 525, 4204, 19013, 51162, 83440, 80816, 42732, 9496, 1, 40

Offset: 1

Vladeta Jovovic, Mar 03 2008

See the Brualdi/Ma reference for the connection to A161126. - Joerg Arndt, Nov 02 2014
T(n,k) is also the number of semistandard Young tableaux of size n whose entries span the interval 1..k. See also Gus Wiseman's comment in A138178. The T(4,2) = 7 semi-standard Young tableaux of size 4 spanning the interval 1..2 are:
   11  122  112  111  1222  1122  1112
   22  2    2    2                      . - Jacob Post, Jun 15 2018

			Triangle T(n,k) begins:
  1;
  1,  2;
  1,  4,   4;
  1,  7,  15,   10;
  1, 10,  36,   52,   26;
  1, 14,  74,  176,  190,   76;
  1, 18, 132,  460,  810,  696,  232;
  1, 23, 222, 1060, 2705, 3756, 2674, 764;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Richard A. Brualdi, Shi-Mei Ma, Enumeration of involutions by descents and symmetric matrices, European Journal of Combinatorics, vol.43, pp.220-228, (January 2015).
FindStat - Combinatorial Statistic Finder, Semistandard Young tableaux
Samantha Dahlberg, Combinatorial Proofs of Identities Involving Symmetric Matrices, arXiv:1410.7356 [math.CO], (27-October-2014)

Cf. (row sums) A138178, A135589, A135588, A161126, A210391.
Main diagonal gives A000085. - Alois P. Heinz, Apr 06 2015
T(2n,n) gives A266305.
T(n^2,n) gives A268309.

gf:= k-> 1/((1-x)^k*(1-x^2)^(k*(k-1)/2)):
A:= (n, k)-> coeff(series(gf(k), x, n+1), x, n):
T:= (n, k)-> add(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Apr 06 2015

gf[k_] := 1/((1-x)^k*(1-x^2)^(k*(k-1)/2)); A[n_, k_] := Coefficient[ Series [gf[k], {x, 0, n+1}], x, n]; T[n_, k_] := Sum[(-1)^j*Binomial[k, j]*A[n, k-j], {j, 0, k}]; Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 31 2016, after Alois P. Heinz *)

T(n,k) = Sum_{i=0..k} (-1)^i * binomial(k,i) * A210391(n,k-i). - Alois P. Heinz, Apr 06 2015

A161125 Number of descents in all involutions of {1,2,...,n}.

Original entry on oeis.org

0, 0, 1, 4, 15, 52, 190, 696, 2674, 10480, 42732, 178480, 770836, 3411024, 15538120, 72446752, 346550520, 1694394496, 8477167504, 43287312960, 225707308912, 1199526928960, 6498288708576, 35836282708864, 201160191642400, 1148165325126912, 6662315102507200, 39268797697682176

Offset: 0

Emeric Deutsch, Jun 09 2009

nonn

Also total number of descents in all tableaux of size n (see Stanley ref.).

A descent in a standard Young tableau is a entry i such that i+1 lies strictly below and weakly left of i. [Joerg Arndt, Feb 18 2014]

			a(3)=4 because in the involutions 123, 132, 213, and 321 we have 0 + 1 + 1 + 2 descents.

R. P. Stanley, Enumerative Combinatorics Vol 2., Lemma 7.19.6, p. 361

Alois P. Heinz, Table of n, a(n) for n = 0..500
J. Désarménien and D. Foata, Fonctions symétriques et séries hypergéométriques basiques multivariées, Bull. Soc. Math. France, 113, 1985, 3-22.
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, A161126.

a[0] := 0: a[1] := 0: a[2] := 1: a[3] := 4: for n from 4 to 27 do a[n] := (n-1)*(a[n-1]/(n-2)+(n-1)*a[n-2]/(n-3)) end do: seq(a[n], n = 0 .. 27); # end of program
g := (1-(1-z-z^2)*exp(z+(1/2)*z^2))*1/2: gser := series(g, z = 0, 30): seq(factorial(n)*coeff(gser, z, n), n = 0 .. 27); # end of program

CoefficientList[Series[(1-(1-z-z^2)*Exp[z+(1/2)*z^2])/2,{z,0,24}],z] Range[0,24]!; (* Emeric Deutsch, Jun 09 2009 *)
descentset[t_?TableauQ]:=Sort[Cases[t,i_Integer /; Position[t,i+1][[1,1]] > Position[t,i][[1,1]], {2}]]; Table[Tr[Length[descentset[#]]& /@Tableaux[n]], {n,1,12}] (* Wouter Meeussen, Aug 04 2013 *)

x='x+O('x^66);  concat([0,0],Vec(serlaplace((1/2)*(1-(1-x-x^2)*exp(x+x^2/2))))) \\ Joerg Arndt, Aug 04 2013

a(n) = (n-1)*A000085(n)/2.
a(n) = Sum(k*A161126(n,k), k=0..n-1).
Rec. rel.: a(n)/(n-1) = a(n-1)/(n-2) + (n-1)*a(n-2)/(n-3) for n>=4 (see 1st Maple program).
E.g.f.: (1/2)*(1 - (1 - z - z^2)*exp(z + z^2/2)).

cp's OEIS Frontend

A138177 Triangle T(n,k) read by rows: number of k X k symmetric matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n, n>=1, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula