Displaying 1-10 of 11 results found.
1, 4, 55, 2008, 153040, 20987840, 4672874360
REFERENCES
R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
1, 1, 4, 5, 2008, 153040, 20933840, 4662857360, 1579060246400
REFERENCES
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 125, b_n.
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.
+10
28
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
COMMENTS
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.
EXAMPLE
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, ...
MAPLE
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);
MATHEMATICA
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 *)
PROG
(Sage)
@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 (Sage)
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 (PARI)
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])
Number of n X n matrices with nonnegative entries and every row and column sum 2.
(Formerly M3084 N1250)
+10
15
1, 1, 3, 21, 282, 6210, 202410, 9135630, 545007960, 41514583320, 3930730108200, 452785322266200, 62347376347779600, 10112899541133589200, 1908371363842760216400, 414517594539154672566000, 102681435747106627787376000, 28772944645196614863048048000
COMMENTS
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
REFERENCES
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.
LINKS
S. Cockburn and J. Lesperance, Deranged socks, Mathematics Magazine, 86 (2013), 97-109.
FORMULA
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
EXAMPLE
G.f. = 1 + x + 3*x^2 + 21*x^3 + 282*x^4 + 6210*x^5 + 202410*x^6 + 9135630*x^7 + ...
MAPLE
coeftayl( exp(x/2)/sqrt(1-x), x=0, n) ;
%*(n!)^2 ;
end proc:
MATHEMATICA
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 *)
PROG
(Sage) from sage.combinat.integer_matrices import IntegerMatrices
def a(n): return IntegerMatrices([2]*n, [2]*n).cardinality() # Ralf Stephan, Mar 02 2014 (PARI) Vec( serlaplace(serlaplace( exp(x/2)/sqrt(1-x) )) ) /* Max Alekseyev, Apr 28 2014 */
Triangle of generalized Eulerian numbers T(n,k) = <n,k>_3 read by rows, n >= 1, 0 <= k <= 3*(n-1).
+10
5
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
COMMENTS
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
EXAMPLE
Triangle begins:
1,
1,1,1,1,
1,4,11,23,11,4,1,
1,11,72,325,595,595,325,72,11,1,
...
Number of labeled Eulerian 3-regular digraphs with n nodes.
(Formerly M5285)
+10
3
1, 0, 0, 0, 1, 44, 7570, 1975560, 749649145, 399035751464, 289021136349036, 277435664056527360, 345023964977303838105, 545099236551025860229460, 1075595203804151695555622446
COMMENTS
Apparently this counts the binary variant (all elements in {0,1}) of A001500 with zero trace. - R. J. Mathar, May 16 2021
REFERENCES
R. W. Robinson, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Number of n X n of nonnegative integers with all row and column sums equal to 4.
+10
3
1, 1, 5, 120, 10147, 2224955, 1047649905, 936670590450, 1455918295922650, 3680232136895819610, 14356628851597700179050, 82857993930808028192521800, 683327637694741065563262206250, 7821620120684573354895941635688250
Number of connected bicubical multigraphs on 2n labeled nodes of two colors.
+10
2
COMMENTS
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.
REFERENCES
R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
1, 2, 31, 1272, 105720, 15492600, 3621844800
COMMENTS
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.
REFERENCES
R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 195
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.
+10
1
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
COMMENTS
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.
FORMULA
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!.
EXAMPLE
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;
...
MAPLE
# 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)) ;
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) ;
Search completed in 0.022 seconds
|