A138177 -id:A138177 - cp's OEIS frontend

A138178 Number of symmetric matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n.

1, 1, 3, 9, 33, 125, 531, 2349, 11205, 55589, 291423, 1583485, 8985813, 52661609, 319898103, 2000390153, 12898434825, 85374842121, 580479540219, 4041838056561, 28824970996809, 210092964771637, 1564766851282299, 11890096357039749, 92151199272181629

Offset: 0

Vladeta Jovovic, Mar 03 2008

Number of normal semistandard Young tableaux of size n, where a tableau is normal if its entries span an initial interval of positive integers. - Gus Wiseman, Feb 23 2018

			a(4) = 33 because there are 1 such matrix of type 1 X 1, 7 matrices of type 2 X 2, 15 of type 3 X 3 and 10 of type 4 X 4, cf. A138177.
From _Gus Wiseman_, Feb 23 2018: (Start)
The a(3) = 9 normal semistandard Young tableaux:
1   1 2   1 3   1 2   1 1   1 2 3   1 2 2   1 1 2   1 1 1
2   3     2     2     2
3
(End)
From _Gus Wiseman_, Nov 14 2018: (Start)
The a(4) = 33 matrices:
[4]
.
[30][21][20][11][10][02][01]
[01][10][02][11][03][20][12]
.
[200][200][110][101][100][100][100][100][011][010][010][010][001][001][001]
[010][001][100][010][020][011][010][001][100][110][101][100][020][010][001]
[001][010][001][100][001][010][002][011][100][001][010][002][100][101][110]
.
[1000][1000][1000][1000][0100][0100][0010][0010][0001][0001]
[0100][0100][0010][0001][1000][1000][0100][0001][0100][0010]
[0010][0001][0100][0010][0010][0001][1000][1000][0010][0100]
[0001][0010][0001][0100][0001][0010][0001][0100][1000][1000]
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..500

Row sums of A138177.
Cf. A007716, A120733, A135588, A296188.
Cf. A057151, A104601, A104602, A120732, A316983, A320796, A321401, A321405, A321407.

gf:= proc(j) local k, n; add(add((-1)^(n-k) *binomial(n, k) *(1-x)^(-k) *(1-x^2)^(-binomial(k, 2)), k=0..n), n=0..j) end: a:= n-> coeftayl(gf(n+1), x=0, n): seq(a(n), n=0..25); # Alois P. Heinz, Sep 25 2008

Table[Sum[SeriesCoefficient[1/(2^(k+1)*(1-x)^k*(1-x^2)^(k*(k-1)/2)),{x,0,n}],{k,0,Infinity}],{n,0,20}]  (* Vaclav Kotesovec, Jul 03 2014 *)
multsubs[set_,k_]:=If[k==0,{{}},Join@@Table[Prepend[#,set[[i]]]&/@multsubs[Drop[set,i-1],k-1],{i,Length[set]}]]; Table[Length[Select[multsubs[Tuples[Range[n],2],n],And[Union[First/@#]==Range[Max@@First/@#],Union[Last/@#]==Range[Max@@Last/@#],Sort[Reverse/@#]==#]&]],{n,5}] (* Gus Wiseman, Nov 14 2018 *)

G.f.: Sum_{n>=0} Sum_{k=0..n} (-1)^(n-k)*C(n,k)*(1-x)^(-k)*(1-x^2)^(-C(k,2)).

G.f.: Sum_{n>=0} 2^(-n-1)*(1-x)^(-n)*(1-x^2)^(-C(n,2)). - Vladeta Jovovic, Dec 09 2009

More terms from Alois P. Heinz, Sep 25 2008

A210391 Number A(n,k) of semistandard Young tableaux over all partitions of n with maximal element <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 4, 1, 0, 1, 4, 9, 6, 1, 0, 1, 5, 16, 19, 9, 1, 0, 1, 6, 25, 44, 39, 12, 1, 0, 1, 7, 36, 85, 116, 69, 16, 1, 0, 1, 8, 49, 146, 275, 260, 119, 20, 1, 0, 1, 9, 64, 231, 561, 751, 560, 189, 25, 1, 0

Offset: 0

Alois P. Heinz, Mar 20 2012

			Square array A(n,k) begins:
  1,  1,   1,   1,   1,    1,    1, ...
  0,  1,   2,   3,   4,    5,    6, ...
  0,  1,   4,   9,  16,   25,   36, ...
  0,  1,   6,  19,  44,   85,  146, ...
  0,  1,   9,  39, 116,  275,  561, ...
  0,  1,  12,  69, 260,  751, 1812, ...
  0,  1,  16, 119, 560, 1955, 5552, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
FindStat - Combinatorial Statistic Finder, Semistandard Young tableaux
Wikipedia, Young tableau

Rows n=0-10 give: A000012, A001477, A000290, A005900, A139594, A210427, A210428, A210429, A210430, A210431, A210432.
Columns k=0-8 give: A000007, A000012, A002620(n+2), A038163, A054498, A181477, A181478, A181479, A181480.
Main diagonal gives: A209673.
Cf. A138177, A191714.

# First program:
h:= (l, k)-> mul(mul((k+j-i)/(1+l[i] -j +add(`if`(l[t]>=j, 1, 0)
                 , t=i+1..nops(l))), j=1..l[i]), i=1..nops(l)):
g:= proc(n, i, k, l)
      `if`(n=0, h(l, k), `if`(i<1, 0, g(n, i-1, k, l)+
      `if`(i>n, 0, g(n-i, i, k, [l[], i]))))
    end:
A:= (n, k)-> `if`(n=0, 1, g(n, n, k, [])):
seq(seq(A(n, d-n), n=0..d), d=0..12);
# second program:
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):
seq(seq(A(n, d-n), n=0..d), d=0..12);

(* First program: *)
h[l_, k_] := Product[Product[(k+j-i)/(1+l[[i]]-j + Sum[If[l[[t]] >= j, 1, 0], {t, i+1, Length[l]}]), {j, 1, l[[i]]}], {i, 1, Length[l]}]; g [n_, i_, k_, l_] := If[n == 0, h[l, k], If[i < 1, 0, g[n, i-1, k, l] + If[i > n, 0, g[n-i, i, k, Append[l, i]]]]]; a[n_, k_] := If[n == 0, 1, g[n, n, k, {}]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten
(* second program: *)
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]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Dec 09 2013, translated from Maple *)

G.f. of column k: 1/((1-x)^k*(1-x^2)^(k*(k-1)/2)).

A(n,k) = Sum_{i=0..k} C(k,i) * A138177(n,k-i). - Alois P. Heinz, Apr 06 2015

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

Original entry on oeis.org

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

A266305 Number of n X n symmetric matrices with nonnegative integer entries and without zero rows or columns such that the sum of all entries is equal to 2n.

Original entry on oeis.org

1, 1, 7, 74, 1060, 19013, 408650, 10219360, 291158230, 9302358947, 329192040880, 12775809098058, 539351216354728, 24600280965461923, 1205263251360664310, 63115789721408960624, 3517483455875467926588, 207834769804597591153769, 12976002600530598793672490

Offset: 0

Alois P. Heinz, Jan 31 2016

nonn

			a(2) = 7:
  [1 1]  [2 1]  [0 1]  [2 0]  [0 2]  [3 0]  [1 0]
  [1 1]  [1 0]  [1 2]  [0 2]  [2 0]  [0 1]  [0 3].

Alois P. Heinz, Table of n, a(n) for n = 0..200

Cf. A138177, 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):
a:= n-> add(A(2*n, n-j)*(-1)^j*binomial(n, j), j=0..n):
seq(a(n), n=0..20);

gf[k_] := 1/((1-x)^k*(1-x^2)^(k*(k-1)/2)); A[n_, k_] := SeriesCoefficient[ gf[k], {x, 0, n}]; a[n_] := Sum[A[2*n, n-j]*(-1)^j*Binomial[n, j], {j, 0, n}]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Feb 25 2017, translated from Maple *)

a(n) = A138177(2n,n).

A268309 Number of n X n symmetric matrices with nonnegative integer entries and without zero rows or columns such that the sum of all entries is equal to n^2.

Original entry on oeis.org

1, 1, 7, 347, 83785, 85813461, 362302219609, 6227015262941276, 433865390872310453097, 122285854086662347886884837, 139236232279790897112737794283927, 639720298831885406784643598607618757713, 11848024220605180271987429760766015754937928643

Offset: 0

Alois P. Heinz, Jan 31 2016

nonn

			a(2) = 7:
  [1 1]  [2 1]  [0 1]  [2 0]  [0 2]  [3 0]  [1 0]
  [1 1]  [1 0]  [1 2]  [0 2]  [2 0]  [0 1]  [0 3].

Alois P. Heinz, Table of n, a(n) for n = 0..45

Cf. A138177, A266305.

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):
a:= n-> add(A(n^2, n-j)*(-1)^j*binomial(n, j), j=0..n):
seq(a(n), n=0..15);

gf[k_] := 1/((1-x)^k*(1-x^2)^(k*(k-1)/2)); A[n_, k_] := SeriesCoefficient[ gf[k], {x, 0, n}]; a[n_] := Sum[A[n^2, n-j]*(-1)^j*Binomial[n, j], {j, 0, n}]; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Feb 25 2017, translated from Maple *)

a(n) = A138177(n^2,n).

cp's OEIS Frontend

A138178 Number of symmetric matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A210391 Number A(n,k) of semistandard Young tableaux over all partitions of n with maximal element <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A266305 Number of n X n symmetric matrices with nonnegative integer entries and without zero rows or columns such that the sum of all entries is equal to 2n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A268309 Number of n X n symmetric matrices with nonnegative integer entries and without zero rows or columns such that the sum of all entries is equal to n^2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula