A001500 -id:A001500 - cp's OEIS frontend

A246968 Erroneous version of A001500.

Original entry on oeis.org

1, 4, 55, 2008, 153040, 20987840, 4672874360

Offset: 1

N. J. A. Sloane, Sep 09 2014

dead

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.

R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971

Cf. A001500.

A058916 Erroneous version of A001500.

Original entry on oeis.org

1, 1, 4, 5, 2008, 153040, 20933840, 4662857360, 1579060246400

Offset: 0

dead

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 125, b_n.

A257493 Number A(n,k) of n X n nonnegative integer matrices with all row and column sums equal to k; square array A(n,k), n >= 0, k >= 0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 6, 1, 1, 1, 4, 21, 24, 1, 1, 1, 5, 55, 282, 120, 1, 1, 1, 6, 120, 2008, 6210, 720, 1, 1, 1, 7, 231, 10147, 153040, 202410, 5040, 1, 1, 1, 8, 406, 40176, 2224955, 20933840, 9135630, 40320, 1, 1, 1, 9, 666, 132724, 22069251, 1047649905, 4662857360, 545007960, 362880, 1

Offset: 0

Alois P. Heinz, Apr 26 2015

Also the number of ordered factorizations of m^k into n factors, where m is a product of exactly n distinct primes and each factor is a product of k primes (counted with multiplicity). A(2,2) = 3: (2*3)^2 = 36 = 4*9 = 6*6 = 9*4.

			Square array A(n,k) begins:
  1,   1,      1,        1,          1,           1,            1, ...
  1,   1,      1,        1,          1,           1,            1, ...
  1,   2,      3,        4,          5,           6,            7, ...
  1,   6,     21,       55,        120,         231,          406, ...
  1,  24,    282,     2008,      10147,       40176,       132724, ...
  1, 120,   6210,   153040,    2224955,    22069251,    164176640, ...
  1, 720, 202410, 20933840, 1047649905, 30767936616, 602351808741, ...

Alois P. Heinz, Antidiagonals n = 0..20, flattened
E. Banaian, S. Butler, C. Cox, J. Davis, J. Landgraf and S. Ponce, A generalization of Eulerian numbers via rook placements, arXiv:1508.03673 [math.CO], 2015.
D. M. Jackson & G. H. J. van Rees, The enumeration of generalized double stochastic nonnegative integer square matrices, SIAM J. Comput., 4.4 (1975), 474-477. (Annotated scanned copy)
Richard J. Mathar, 2-regular Digraphs of the Lovelock Lagrangian, arXiv:1903.12477 [math.GM], 2019.
Dennis Pixton, Ehrhart polynomials for n = 1, ..., 9
M. L. Stein and P. R. Stein, Enumeration of Stochastic Matrices with Integer Elements, Report LA-4434, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Jun 1970. [Annotated scanned copy]

Columns k=0-9 give: A000012, A000142, A000681, A001500, A172806, A172862, A172894, A172919, A172944, A172958.
Rows n=0+1, 2-9 give: A000012, A000027(k+1), A002817(k+1), A001496, A003438, A003439, A008552, A160318, A160319.
Main diagonal gives A110058.
Cf. A257463 (unordered factorizations), A333733 (non-isomorphic matrices), A008300 (binary matrices).

with(numtheory):
b:= proc(n, k) option remember; `if`(n=1, 1, add(
      `if`(bigomega(d)=k, b(n/d, k), 0), d=divisors(n)))
    end:
A:= (n, k)-> b(mul(ithprime(i), i=1..n)^k, k):
seq(seq(A(n, d-n), n=0..d), d=0..8);

b[n_, k_] := b[n, k] = If[n==1, 1, Sum[If[PrimeOmega[d]==k, b[n/d, k], 0], {d, Divisors[n]}]]; A[n_, k_] := b[Product[Prime[i], {i, 1, n}]^k, k]; Table[A[n, d-n], {d, 0, 10}, {n, 0, d}] // Flatten (* Jean-François Alcover, Feb 20 2016, after Alois P. Heinz *)

T(n, k)={
  local(M=Map(Mat([n, 1])));
  my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
  my(recurse(h, p, q, v, e) = if(!p, if(!e, acc(q, v)), my(i=poldegree(p), t=pollead(p)); self()(k, p-t*x^i, q+t*x^i, v, e); for(m=1, h-i, for(j=1, min(t, e\m), self()(if(j==t, k, i+m-1), p-j*x^i, q+j*x^(i+m), binomial(t, j)*v, e-j*m)))));
  for(r=1, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], recurse(k, src[i, 1], 0, src[i, 2], k))); vecsum(Mat(M)[, 2])
} \\ Andrew Howroyd, Apr 04 2020

bigomega = sloane.A001222
@cached_function
def b(n, k):
    if n == 1:
        return 1
    return sum(b(n//d, k) if bigomega(d) == k else 0 for d in n.divisors())
def A(n, k):
    return b(prod(nth_prime(i) for i in (1..n))^k, k)
[A(n, d-n) for d in (0..10) for n in (0..d)] # Freddy Barrera, Dec 27 2018, translated from Maple

from sage.combinat.integer_matrices import IntegerMatrices
[IntegerMatrices([d-n]*n, [d-n]*n).cardinality() for d in (0..10) for n in (0..d)] # Freddy Barrera, Dec 27 2018

A000681 Number of n X n matrices with nonnegative entries and every row and column sum 2.

Original entry on oeis.org

1, 1, 3, 21, 282, 6210, 202410, 9135630, 545007960, 41514583320, 3930730108200, 452785322266200, 62347376347779600, 10112899541133589200, 1908371363842760216400, 414517594539154672566000, 102681435747106627787376000, 28772944645196614863048048000

Offset: 0

N. J. A. Sloane, Simon Plouffe

Or, number of labeled 2-regular pseudodigraphs (multiple arcs and loops allowed) of order n.

Also, number of permutations of the multiset {1^2,2^2,...,n^2} with the descent set consisting of multiples of 2. - Max Alekseyev, Apr 28 2014

			G.f. = 1 + x + 3*x^2 + 21*x^3 + 282*x^4 + 6210*x^5 + 202410*x^6 + 9135630*x^7 + ...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 125, #25, a_n.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, section 3.5.10.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1982.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Cor. 5.5.11 (a).
M. L. Stein and P. R. Stein, Enumeration of Stochastic Matrices with Integer Elements. Report LA-4434, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Jun 1970.
C. B. Tompkins, Methods of successive restrictions in computational problems involving discrete variables. 1963, Proc. Sympos. Appl. Math., Vol. XV pp. 95-106; Amer. Math. Soc., Providence, R.I.

Alois P. Heinz, Table of n, a(n) for n = 0..250 (first 49 terms from R. W. Robinson)
H. Anand, V. C. Dumir and H. Gupta, A combinatorial distribution problem, Duke Math. J., 33 (1996), 757-769.
Esther M. Banaian, Generalized Eulerian Numbers and Multiplex Juggling Sequences, (2016). All College Thesis Program. Paper 24.
E. Banaian, S. Butler, C. Cox, J. Davis, J. Landgraf and S. Ponce A generalization of Eulerian numbers via rook placements, arXiv:1508.03673 [math.CO], 2015.
S. Cockburn and J. Lesperance, Deranged socks, Mathematics Magazine, 86 (2013), 97-109.
Ira Gessel, Enumerative applications of symmetric functions, Séminaire Lotharingien de Combinatoire, B17a (1987), 17 pp.
William George Griffiths, On Integer Solutions to Linear Equations, Annals of Combinatorics 12:1 (2008), pp. 53-70.
Rui-Li Liu, Feng-Zhen Zhao, New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
Richard J. Mathar, 2-regular Digraphs of the Lovelock Lagrangian, arXiv:1903.12477 [math.GM], 2019.
M. L. Stein and P. R. Stein, Enumeration of Stochastic Matrices with Integer Elements, Report LA-4434, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Jun 1970. [Annotated scanned copy]
Index entries for sequences related to magic squares

Column k=2 of A257493.
Row sums of A269742 and A307804.
Row and column sums equal s: A000142 (s=1), A001500 (s=3), A172806 (s=4), A172862 (s=5), A172894 (s=6), A172919 (s=7), A172944 (s=8), A172958 (s=9).
Cf. A001499, A005650, A123544.

A000681 := proc(n)
    coeftayl( exp(x/2)/sqrt(1-x),x=0,n) ;
    %*(n!)^2 ;
end proc:
seq(A000681(n),n=0..10) ; # R. J. Mathar, May 01 2019

a[n_] := Sum[ ((2*i)!*n!^2) / (2^i*(i!^2*(n - i)!)), {i, 0, n}]/2^n; Table[ a[n], {n, 0, 17}] (* Jean-François Alcover, Dec 08 2011 *)
a[n_] := n!*HypergeometricPFQ[{1/2, -n}, {}, -2]/2^n; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Aug 08 2012 *)

Vec( serlaplace(serlaplace( exp(x/2)/sqrt(1-x) )) ) /* Max Alekseyev, Apr 28 2014 */

from sage.combinat.integer_matrices import IntegerMatrices
def a(n): return IntegerMatrices([2]*n, [2]*n).cardinality() # Ralf Stephan, Mar 02 2014

Sum_{n >= 0} a(n) x^n / n!^2 = exp(x/2) / sqrt(1-x).
D-finite with recurrence a(n) = n^2*a(n-1) - (1/2)*n*(n-1)^2*a(n-2).
a(n) is asymptotic to c/sqrt(n)*(n!)^2 where c=0.93019... - Benoit Cloitre, Jun 25 2004
a(n) = sum(i=0..n, 2^(i-2*n) * C(n, i)^2 * (2*n-2*i)! * i! ).
a(n) = 2^(-n) * sum(i=0..n, ((n!)^2*(2*i)!) / ((i!)^2*((n-i)!*2^i)) ). - Shanzhen Gao, Nov 05 2007
In Cloitre's formula is c = exp(1/2)/sqrt(Pi) = 0.9301913671026328586. - Vaclav Kotesovec, Aug 12 2013
With c as used above by Cloitre and Kotesovec, a(n) is asymptotic to c/sqrt(n)*(n!)^2 * (1 + 2/(16*n) + 50/(16*n)^2 + 1100/(16*n)^3 + 32438/(16*n)^4 + 1185660/(16*n)^5 + 50498228/(16*n)^6 + 2438464600/(16*n)^7 + 131323987366/(16*n)^8 + 7782036656108/(16*n)^9 + 501905392385436/(16*n)^10 + ...). - Jon E. Schoenfield, Mar 03 2014
E.g.f.: 2/((2-x)*W(0)), where W(k) = 1 - (2*k+1)*x/(2-x-2*(k+1)*x/W(k+1)); (continued fraction). - Sergei N. Gladkovskii, Nov 25 2014

More terms from David W. Wilson

A269743 Triangle of generalized Eulerian numbers T(n,k) = _3 read by rows, n >= 1, 0 <= k <= 3*(n-1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 4, 11, 23, 11, 4, 1, 1, 11, 72, 325, 595, 595, 325, 72, 11, 1, 1, 26, 367, 3368, 14679, 34679, 46800, 34679, 14679, 3368, 367, 26, 1, 1, 57, 1630, 28819, 253247, 1212440, 3382133, 5588593, 5588593, 3382133, 1212440, 253247, 28819, 1630, 57, 1

Offset: 1

N. J. A. Sloane, Mar 16 2016

T(n,k) is the number of nonnegative integer n X n matrices with every row and column sum 3 and sum of entries below the main diagonal k. The case when every row and column sum is 1 is given by the Eulerian numbers (A008292). - Andrew Howroyd, Feb 22 2020

			Triangle begins:
1,
1,1,1,1,
1,4,11,23,11,4,1,
1,11,72,325,595,595,325,72,11,1,
...

Andrew Howroyd, Table of n, a(n) for n = 1..925 (first 25 rows)
Esther M. Banaian, Generalized Eulerian Numbers and Multiplex Juggling Sequences, (2016). All College Thesis Program. Paper 24.
E. Banaian, S. Butler, C. Cox, J. Davis, J. Landgraf and S. Ponce, A generalization of Eulerian numbers via rook placements, arXiv:1508.03673 [math.CO], 2015.
Andrew Howroyd, PARI Program

Row sums are A001500.
Columns k=0..4 are A000012, A000295, A260585, A260727, A260583.
Cf. A008292, A269742, A269744.

\\ See link. - Andrew Howroyd, Feb 22 2020

Terms a(23) and beyond from Andrew Howroyd, Feb 22 2020

A007105 Number of labeled Eulerian 3-regular digraphs with n nodes.

Original entry on oeis.org

1, 0, 0, 0, 1, 44, 7570, 1975560, 749649145, 399035751464, 289021136349036, 277435664056527360, 345023964977303838105, 545099236551025860229460, 1075595203804151695555622446

Offset: 0

N. J. A. Sloane

nonn

Apparently this counts the binary variant (all elements in {0,1}) of A001500 with zero trace. - R. J. Mathar, May 16 2021

R. W. Robinson, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Óscar González, Carlos Beltrán, and Ignacio Santamaría, On the Number of Interference Alignment Solutions for the K-User MIMO Channel with Constant Coefficients, arXiv preprint arXiv:1301.6196 [cs.IT], 2013-2014. - From _N. J. A. Sloane_, Feb 19 2013
Jan Tóth and Ondřej Kuželka, Complexity of Weighted First-Order Model Counting in the Two-Variable Fragment with Counting Quantifiers: A Bound to Beat, arXiv:2404.12905 [cs.LO], 2024. See p. 18.

Cf. A001500, A284990.

A172806 Number of n X n of nonnegative integers with all row and column sums equal to 4.

Original entry on oeis.org

1, 1, 5, 120, 10147, 2224955, 1047649905, 936670590450, 1455918295922650, 3680232136895819610, 14356628851597700179050, 82857993930808028192521800, 683327637694741065563262206250, 7821620120684573354895941635688250

Offset: 0

R. H. Hardin, Feb 06 2010

nonn

R. H. Hardin, Table of n, a(n) for n = 0..56
Esther M. Banaian, Generalized Eulerian Numbers and Multiplex Juggling Sequences, (2016). All College Thesis Program. Paper 24.
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967.
M. L. Stein and P. R. Stein, Enumeration of Stochastic Matrices with Integer Elements, Report LA-4434, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Jun 1970. [Annotated scanned copy]

Cf. A000681, A001500, A172862, A172894, A172919, A172944, A172958.

Column k=4 of A257493.

A246970 Number of connected bicubical multigraphs on 2n labeled nodes of two colors.

Original entry on oeis.org

1, 2, 31, 1272, 105720

Offset: 1

N. J. A. Sloane, Sep 09 2014

Read's 1971 letter includes additional terms for both this sequence and A001500. But the terms a(6) and a(7) given for A001500 are wrong, so presumably those for this sequence are also wrong. See A246968 and A246969 for the sequences as given in Read's letter and (presumably) also in his dissertation.

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.

R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971

Cf. A001500, A246968, A246969.

A246969 Erroneous version of A246970.

Original entry on oeis.org

1, 2, 31, 1272, 105720, 15492600, 3621844800

Offset: 1

N. J. A. Sloane, Sep 09 2014

dead

This is the "connected" version of the problem studied by Read in A001500. Since the terms a(6) and a(7) for A001500 given in his letter (and presumably also in his dissertation) are known to be wrong, it is extremely likely that the values of a(6) and a(7) shown here are also wrong.

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 195

R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971

A344379 Triangle read by rows: T(n,k) is the number of labeled 3-regular digraphs (multiple arcs and loops allowed) on n nodes with k components.

Original entry on oeis.org

1, 3, 1, 45, 9, 1, 1782, 207, 18, 1, 142164, 10260, 585, 30, 1, 19943830, 953424, 35235, 1305, 45, 1, 4507660380, 151369792, 3731049, 93555, 2520, 63, 1, 1540185346560, 38205961380, 657600076, 11122209, 211680, 4410, 84, 1, 757560406751120, 14455803484728

Offset: 1

R. J. Mathar, May 16 2021

Derived by interpreting A001500 as the number of labeled 3-regular digraphs (in-degree and out-degree at each node=3), without regarding the trace (which means loops are allowed) and no limit on the individual entries (so multiple arcs in the same direction between nodes are allowed).

Then the formula of A123543 (Gilbert's article) allows these values to be refined by the number of weakly connected components.

			Triangle begins:
              1;
              3,           1;
             45,           9,         1;
           1782,         207,        18,        1;
         142164,       10260,       585,       30,      1;
       19943830,      953424,     35235,     1305,     45,    1;
     4507660380,   151369792,   3731049,    93555,   2520,   63,  1;
  1540185346560, 38205961380, 657600076, 11122209, 211680, 4410, 84, 1;
...

E. N. Gilbert, Enumeration of labelled graphs, Can. J. Math. 8 (1956) 405-411.

Cf. A307804 (2-regular analog), A001500 (row sums), A045943 (subdiagonal).

# Given a list L[1], L[2],... for labeled not necessarily connected graphs, generate
# triangle of labeled graphs with k weakly connected components.
lblNonc := proc(L::list)
    local k,x,g,Lkx,t,Lkxt,n,c ;
    add ( op(k,L)*x^k/k!,k=1..nops(L)) ;
    log(1+%) ; # formula from A123543
    g := taylor(%,x=0,nops(L)) ;
    seq( coeftayl(g,x=0,i)*i!,i=1..nops(L)) ;
    print(lc) ;# first column
    Lkx := add ( coeftayl(g,x=0,i)*x^i,i=1..nops(L)) ;
    Lkxt := exp(t*%) ;
    for n from 0 to nops(L)-1 do
        tmp := coeftayl(Lkxt,x=0,n) ;
        for c from 0 to n do
            printf("%a ", coeftayl(tmp,t=0,c)*n!) ;
        end do:
        printf("\n") ;
    end do:
end proc:
L := [1, 4, 55, 2008, 153040, 20933840, 4662857360, 1579060246400, 772200774683520, 523853880779443200, 477360556805016931200, 569060910292172349004800, 868071731152923490921728000, 1663043727673392444887284377600, 3937477620391471128913917360384000] ;
lblNonc(L) ;

T(n,n) = 1. [n nodes, each with a triple loop].
T(n,n-1) = A045943(n-1). [n-1 isolated nodes, one labeled pair with n(n-1)/2 choices of labels and 3 choices of zero, one or two loops at the lower label].
T(n,k) = Sum_{Compositions n=n_1+n_2+...n_k, n_i>=1} multinomial(n; n_1,n_2,...,n_k) * T(n_1,1) * T(n_2,1) * ... *T(n_k,1) / k!.

cp's OEIS Frontend

A246968 Erroneous version of A001500.

Views

Author

Keywords

References

Links

Crossrefs

A058916 Erroneous version of A001500.

Views

Author

Keywords

References

A257493 Number A(n,k) of n X n nonnegative integer matrices with all row and column sums equal to k; square array A(n,k), n >= 0, k >= 0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Sage

A000681 Number of n X n matrices with nonnegative entries and every row and column sum 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A269743 Triangle of generalized Eulerian numbers T(n,k) = _3 read by rows, n >= 1, 0 <= k <= 3*(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A007105 Number of labeled Eulerian 3-regular digraphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A172806 Number of n X n of nonnegative integers with all row and column sums equal to 4.

Views

Author

Keywords

Links

Crossrefs

A246970 Number of connected bicubical multigraphs on 2n labeled nodes of two colors.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A246969 Erroneous version of A246970.

Views

Author

Keywords