cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-6 of 6 results.

A333157 Triangle read by rows: T(n,k) is the number of n X n symmetric binary matrices with k ones in every row and column.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 10, 18, 10, 1, 1, 26, 112, 112, 26, 1, 1, 76, 820, 1760, 820, 76, 1, 1, 232, 6912, 35150, 35150, 6912, 232, 1, 1, 764, 66178, 848932, 1944530, 848932, 66178, 764, 1, 1, 2620, 708256, 24243520, 133948836, 133948836, 24243520, 708256, 2620, 1
Offset: 0

Views

Author

Andrew Howroyd, Mar 09 2020

Keywords

Comments

T(n,k) is the number of k-regular symmetric relations on n labeled nodes.
T(n,k) is the number of k-regular graphs with half-edges on n labeled vertices.
Terms may be computed without generating all graphs by enumerating the number of graphs by degree sequence. A PARI program showing this technique is given below. Burnside's lemma as applied in A122082 and A000666 can be used to extend this method to the case of unlabeled vertices A333159 and A333161 respectively.

Examples

			Triangle begins:
  1,
  1,   1;
  1,   2,     1;
  1,   4,     4,      1;
  1,  10,    18,     10,       1;
  1,  26,   112,    112,      26,      1;
  1,  76,   820,   1760,     820,     76,     1;
  1, 232,  6912,  35150,   35150,   6912,   232,   1;
  1, 764, 66178, 848932, 1944530, 848932, 66178, 764, 1;
  ...

Links

Crossrefs

Columns k=0..8 are A000012, A000085, A000986, A110040, A139670, A139671, A139673, A139674, A139675.
Row sums are A322698.
Central coefficients are A333164.
Cf. A188448 (transposed as array).
Cf. A059441, A295193, A333158, A333159, A333161.

Programs

  • PARI
    \\ See script in A295193 for comments.
GraphsByDegreeSeq(n, limit, ok)={
  local(M=Map(Mat([x^0,1])));
  my(acc(p,v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
  my(recurse(r,p,i,q,v,e) = if(e<=limit && poldegree(q)<=limit, if(i<0, if(ok(x^e+q, r), acc(x^e+q, v)), my(t=polcoeff(p,i)); for(k=0,t,self()(r,p,i-1,(t-k+x*k)*x^i+q,binomial(t,k)*v,e+k)))));
  for(k=2, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], my(p=src[i,1]); recurse(n-k, p, poldegree(p), 0, src[i,2], 0))); Mat(M);
}
Row(n)={my(M=GraphsByDegreeSeq(n, n\2, (p,r)->poldegree(p)-valuation(p,x) <= r + 1), v=vector(n+1)); for(i=1, matsize(M)[1], my(p=M[i,1], d=poldegree(p)); v[1+d]+=M[i,2]; if(pollead(p)==n, v[2+d]+=M[i,2])); for(i=1, #v\2, v[#v+1-i]=v[i]); v}
for(n=0, 8, print(Row(n))) \\ Andrew Howroyd, Mar 14 2020

Formula

T(n,k) = T(n,n-k).

A110040 Number of {2,3}-regular graphs; i.e., labeled simple graphs (no multi-edges or loops) on n vertices, each of degree 2 or 3.

Original entry on oeis.org

1, 0, 0, 1, 10, 112, 1760, 35150, 848932, 24243520, 805036704, 30649435140, 1322299270600, 64008728200384, 3447361661136640, 205070807479444088, 13388424264027157520, 953966524932871436800, 73817914562041635228928
Offset: 0

Views

Author

Marni Mishna, Jul 08 2005

Keywords

Comments

P-recursive.
Starting at n=3, number of symmetric binary matrices with all row sums 3. - R. H. Hardin, Jun 12 2008
From R. J. Mathar, Apr 07 2017: (Start)
These are the row sums of the following matrix, which counts symmetric n X n {0,1} matrices with each row and column sum equal to 3 and trace t, 0 <= t <= n:
0: 1
1: 0 0
2: 0 0 0
3: 0 0 0 1
4: 1 0 6 0 3
5: 0 30 0 70 0 12
6: 70 0 810 0 810 0 70
7: 0 5670 0 19355 0 9660 0 465
This has A001205 on the diagonal. (End)
The traceless (2n) X (2n) binary matrices in that triangle seem to be counted in A002829. - Alois P. Heinz, Apr 07 2017

Examples

			(Graphs listed by edgeset)
a(3)=1: {(1,2), (2,3), (3,1)}
a(4)=10: {(1,2), (2,3), (3,4), (4,1)}, {(1,2), (2,3), (3,4), (4,1), (1,4)}, {(1,2), (2,3), (3,4), (4,1), (2,3)}, {(1,2), (2,4), (3,4), (1,3)}, {(1,2), (2,4), (3,4), (1,3), (2,3)}, {(1,2), (2,4), (3,4), (1,3), (1,4)}, {(1,3), (2,3), (2,4), (1,4)}, {(1,3), (2,3), (2,4), (1,4), (1,2)}, {(1,3), (2,3), (2,4), (1,4), (3,4)}, {(1,2), (1,3), (1,4) (2,3), (2,4), (3,4)},

References

  • Tan and S. Gao, Enumeration of (0,1)-Symmetric Matrices, submitted [From Shanzhen Gao, Jun 05 2009]

Links

Crossrefs

Cf. A002829, A110039, A110041.
Cf. A000986 (sums 2), A000085 (sums 1), A139670 (sums 3).

Programs

  • Mathematica
    RecurrenceTable[{-b[n] - b[1 + n] + (-2 + 3*n)*b[2 + n] - 14*b[3 + n] + (105 + 30*n)*b[4 + n] + (-69 - 12*n)*b[5 + n] + (582 + 147*n + 9*n^2)* b[6 + n] + (-20 - 6*n)*b[7 + n] + (1160 + 363*n + 27*n^2)*b[8 + n] + (1554 + 255*n + 9*n^2)* b[9 + n] + (-2340 - 414*n - 18*n^2)*b[10 + n] + (-528 - 48*n)*b[11 + n] + (288 + 24*n)*b[12 + n] == 0, b[0] == 1, b[1] == 0, b[2] == 0, b[3] == 1/6, b[4] == 5/12, b[5] == 14/15, b[6] == 22/9, b[7] == 3515/504, b[8] == 30319/1440, b[9] == 10823/162, b[10] == 8385799/37800, b[11] == 510823919/665280}, b, {n, 0, 25}] * Range[0, 25]! (* Vaclav Kotesovec, Oct 23 2023 *)

Formula

Satisfies the linear recurrence: (-150917976*n^2 - 105258076*n^3 - 1925*n^9 - 13339535*n^5 - 45995730*n^4 - 357423*n^7 - 2637558*n^6 - 120543840*n - n^11 - 66*n^10 - 39916800 - 32670*n^8)*a(n) + (-11028590*n^4 - 65*n^9 - n^10 - 2310945*n^5 - 1860*n^8 - 30810*n^7 - 326613*n^6 - 80627040*n - 39916800 - 34967140*n^3 - 70290936*n^2)*a(n + 1) + (3*n^10 - 39916800 + 187*n^9 + 5076*n^8 + 78558*n^7 + 761103*n^6 + 4757403*n^5 + 18949074*n^4 + 44946092*n^3 + 51046344*n^2 - 793440*n)*a(n + 2) + (-93139200 - 16175880*n^3 - 56394184*n^2 - 110513760*n - 2854446*n^4 - 14*n^8 - 840*n^7 - 21756*n^6 - 317520*n^5)*a(n + 3) + (45780*n^6 + 1785*n^7 + 111580320*n^2 + 660450*n^5 + 5856270*n^4 + 32645865*n^3 + 174636000 + 213450300*n + 30*n^8)*a(n + 4) + (-22952160 - 681*n^6 - 16419*n^5 - 217995*n^4 - 8082204*n^2 - 20896956*n - 12*n^7 - 1721253*n^3)*a(n + 5) + (1804641*n^3 + 9*n^7 + 14442*n^5 + 208920*n^4 + 32266080 + 9307488*n^2 + 26537388*n + 552*n^6)*a(n + 6) + (-158400 - 15160*n - 3994*n^3 - 31072*n^2 - 6*n^5 - 248*n^4)*a(n + 7) + (20123*n^3 + 706210*n + 27*n^5 + 170067*n^2 + 1148400 + 1173*n^4)*a(n + 8) + (7899*n^2 + 60684*n + 444*n^3 + 9*n^4 + 170940)*a(n + 9) + (-6894*n - 25740 - 18*n^3 - 612*n^2)*a(n + 10) + (-48*n - 528)*a(n + 11) + 24*a(n + 12).
Differential equation satisfied by the exponential generating function {F(0) = 1, 9*t^4*(t^4 + t - 2 + 3*t^2)^2*(d^2/dt^2)F(t) + 3*t*(t^4 + t - 2 + 3*t^2)*(10*t^8 + 34*t^3 - 16*t + 16*t^6 - 2*t^5 - 24*t^2 - 4*t^7 + 8 + t^10 - 14*t^4)*(d/dt)F(t) - t^3*(-22*t^2 + t^8 - 24*t^3 + t^9 + 8*t^7 + 14*t^6 + 15*t^5 + 12 + 16*t + 9*t^4)*(t^4 + t - 2 + 3*t^2)*F(t)}.
Sum_{a_2 = 0..n} Sum_{d_2 = 0..min(floor((3n - 2a_2)/2), floor(n/2), n - a_2)} Sum_{d_3 = 0..min(floor((3n - 2a_2 - 2d_2)/3), floor((n-2d_2)/3), n - a_2 - d_2} Sum_{d_1 = 0..min(3n - 2a_2 - 2d_2 - 3d_3, n - 2d_2 - 3d_3) Sum_{b = 0..min(floor((3n - 2a_2 - 2d_2 - 3d_3 - d_1)/4), floor((n - d_2 - d_3 - a_2)/2)} Sum_{c = 0..min(floor((3n - 2a_2 - 2d_2 - 3d_3 - d_1 - 4b)/6), floor((n - a_2 - 2b - d_2 - d_3)/2))} Sum_{a_1 = ceiling((3n - (2a_2 + 4b + 6c + d_1 + 2d_2 + 3d_3))/2)..floor((3n - (2a_2 + 4b + 6c + d_1 + 2d_2 + 3d_3))/2)} (-1)^(a_2 + b + d_2)*n!*(2a_1 + d_1)!/(2^(n + a_1 - c - d_3)*3^(n - a_2 - 2b - d_2 - c)*a_1!*a_2!*b!*c!*d_1!*d_2!*d_3!*(n - a_2 - 2b - d_2 - 2c - d_3)!). - Shanzhen Gao, Jun 05 2009
Recurrence (of order 8): 12*(27*n^4 - 423*n^3 + 2427*n^2 - 5639*n + 4384)*a(n) = 6*(n-1)*(81*n^4 - 1242*n^3 + 7011*n^2 - 15528*n + 10352)*a(n-1) + 3*(n-2)*(n-1)*(81*n^5 - 1269*n^4 + 7551*n^3 - 20841*n^2 + 29934*n - 16040)*a(n-2) - 3*(n-2)*(n-1)*(135*n^5 - 2115*n^4 + 13287*n^3 - 37537*n^2 + 46430*n - 21848)*a(n-3) + (n-3)*(n-2)*(n-1)*(567*n^5 - 9396*n^4 + 59895*n^3 - 169590*n^2 + 191744*n - 57040)*a(n-4) - 2*(n-4)*(n-3)*(n-2)*(n-1)*(135*n^4 - 1386*n^3 + 5034*n^2 - 6529*n + 648)*a(n-5) + (n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(81*n^5 - 1566*n^4 + 11367*n^3 - 37080*n^2 + 47872*n - 17424)*a(n-6) - (n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(27*n^4 - 315*n^3 + 1113*n^2 - 1433*n + 348)*a(n-7) - (n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(27*n^4 - 315*n^3 + 1320*n^2 - 1946*n + 776)*a(n-8). - Vaclav Kotesovec, Oct 23 2023
a(n) ~ 3^(n/2) * n^(3*n/2) / (2^(n + 1/2) * exp(3*n/2 - sqrt(3*n) + 13/4)) * (1 + 119/(24*sqrt(3*n)) - 2519/(3456*n)). - Vaclav Kotesovec, Oct 27 2023, extended Oct 28 2023

Extensions

Edited and extended by Max Alekseyev, May 08 2010

A188448 T(n,k)=Number of (n*k)Xk binary arrays with nonzero rows in decreasing order, no more than 2 ones in any row and exactly n ones in every column.

Original entry on oeis.org

1, 2, 0, 4, 1, 0, 10, 4, 0, 0, 26, 18, 1, 0, 0, 76, 112, 10, 0, 0, 0, 232, 820, 112, 1, 0, 0, 0, 764, 6912, 1760, 26, 0, 0, 0, 0, 2620, 66178, 35150, 820, 1, 0, 0, 0, 0, 9496, 708256, 848932, 35150, 76, 0, 0, 0, 0, 0, 35696, 8372754, 24243520, 1944530, 6912, 1, 0, 0, 0, 0
Offset: 1

Views

Author

R. H. Hardin Mar 31 2011

Keywords

Comments

Table starts
.1.2.4.10..26...76...232.....764......2620........9496.........35696
.0.1.4.18.112..820..6912...66178....708256.....8372754.....108306280
.0.0.1.10.112.1760.35150..848932..24243520...805036704...30649435140
.0.0.0..1..26..820.35150.1944530.133948836.11234051976.1127512146540
.0.0.0..0...1...76..6912..848932.133948836.26615510712
.0.0.0..0...0....1...232...66178..24243520
.0.0.0..0...0....0.....1.....764
.0.0.0..0...0....0.....0
.0.0.0..0...0....0
.0.0.0..0...0

Examples

			All solutions for 9X3
..1..1..0
..1..0..1
..1..0..0
..0..1..1
..0..1..0
..0..0..1
..0..0..0
..0..0..0
..0..0..0

Links

Crossrefs

Row 1 is A000085
Row 2 is A000986
Row 3 is A110040
Row 4 is A139670
Row 5 is A139671
Row 6 is A139673
Row 7 is A139674
Row 8 is A139675

A134648 Number of 2n X n (0,1)-matrices with row sums 2 and column sums 4.

Original entry on oeis.org

0, 1, 90, 44730, 56586600, 154700988750, 807998767676100, 7373018003758407000, 109829050417159537464000, 2532230252503738514963235000, 86574740102712303011539719750000, 4237239732072431006302896746240010000
Offset: 1

Views

Author

Shanzhen Gao, Nov 05 2007

Keywords

Comments

t(m,n) in the formula gives the number of (0,1)-matrices of size m*n with row sum 4 and column sum 2. a(n) in the formula gives the number of (0,1)-matrices of size n*(2n) with row sum 4 and column sum 2. - Shanzhen Gao, Feb 16 2010

Examples

			Number of  4 X 2 (0,1)-matrices:       1;
Number of  6 X 3 (0,1)-matrices:      90;
Number of  8 X 4 (0,1)-matrices:   44730;
Number of 10 X 5 (0,1)-matrices: 5658660.

References

  • Gao, Shanzhen, and Matheis, Kenneth, Closed formulas and integer sequences arising from the enumeration of (0,1)-matrices with row sum two and some constant column sums. In Proceedings of the Forty-First Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Numer. 202 (2010), 45-53.

Links

Crossrefs

Cf. A000681, A000986, A132202, A134645, A134646, A139670, etc.

Programs

  • Magma
    B:=Binomial; F:=Factorial;
f:= func< m,n,k,j | B(m, k)*B(m-k, j)*B(2*m+2*k-2*j, m+k-j)*F(m+k-j) >;
t:= func< m,n | ((-1)^m*F(n)/8^m)*(&+[(&+[f(m,n,k,j)*(-1)^(j+k)/(12)^k: k in [0..m-j]]): j in [0..m]]) >;
A134648:= func< n | F(2*n)*t(n,n)/F(n) >;
[A134648(n): n in [1..30]]; // G. C. Greubel, Oct 13 2023
  • Mathematica
    t[m_, n_]:= t[m, n]= ((-1)^m*n!/8^m)*Sum[Binomial[m,k]*Binomial[m-k,j]*Binomial[2*m+2*k-2*j,m+k-j]*(m+k-j)!*(-1)^(j+k)/(12)^k, {j,0, m}, {k,0,m-j}];
A134648[n_]:= (2*n)!*t[n,n]/n!;
Table[A134648[n], {n,30}] (* G. C. Greubel, Oct 13 2023 *)
  • SageMath
    b=binomial; F=factorial;
def f(m,n,k,j): return b(m, k)*b(m-k, j)*b(2*m+2*k-2*j, m+k-j)*F(m+k-j)
def t(m,n): return ((-1)^m*F(n)/8^m)*sum(sum(f(m,n,k,j)*(-1)^(j+k)/(12)^k for k in range(m-j+1)) for j in range(m+1))
def A134648(n): return F(2*n)*t(n,n)/F(n)
[A134648(n) for n in range(1,31)] # G. C. Greubel, Oct 13 2023

Formula

a(n) = (2*n)!*t(n,n)/n!, where t(m, n) = (1/24^m)*Sum_{j=0..m} Sum_{k=0..m-j} ( (-1)^(m-j-k)*3^j*6^(m-j-k)*m!*n!*(4*k+2*(m-j-k))! )/( j!*k!*(m-j-k)!*(2*k+(m-j-k))!*2^(2*k+(m-j-k)) ).
a(n) = (1/24^n)*Sum_{j=0..n} Sum_{k=0..n-j} ((-1)^(n-j-k)*3^j*6^(n-j-k)*n!(2n)!(2n-2j+2k)!/(j!k!(n-j-k)!(n-j+k)!*2^(n-j+k))). - Shanzhen Gao, Feb 16 2010
a(n) ~ sqrt(Pi) * 2^(3*n + 3/2) * n^(4*n + 1/2) / (3^n * exp(4*n + 3/2)). - Vaclav Kotesovec, Oct 21 2023

Extensions

a(7) onwards from R. H. Hardin, Oct 18 2009

A284991 Triangle T(n,t) read by rows: the number of n X n {0,1} matrices with trace t where each row sum and each column sum is 4.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 10, 20, 45, 44, 265, 1920, 6300, 13720, 20175, 18000, 7570, 357435, 2398900, 7499940, 14372820, 18433415, 15729000, 8171730, 1975560, 749649145, 4695264000, 13718863480, 24545693760, 29544855480, 24545693760, 13718863480, 4695264000, 749649145
Offset: 0

Views

Author

R. J. Mathar, Apr 07 2017

Keywords

Examples

			0:       1
1:       0       0
2:       0       0       0
3:       0       0       0        0
4:       0       0       0        0        1
5:       1       0      10       20       45       44
6:     265    1920    6300    13720    20175    18000    7570
7:  357435 2398900 7499940 14372820 18433415 15729000 8171730 1975560

Links

Crossrefs

Cf. A058528 (row sums), A007105 (diagonal?), A139670 (symmetric matrices).

Extensions

More terms from Alois P. Heinz, Apr 09 2017

A188405 Number of (4*n) X n binary arrays with rows in nonincreasing order, 4 ones in every column and no more than 2 ones in any row.

Original entry on oeis.org

1, 1, 5, 42, 641, 14751, 478711, 20758650, 1158207312, 80758709676, 6877184737416, 701994697409136, 84574042067524470, 11870290445670605262, 1919446717950100963626, 354168049679464581788796, 73947210994621695613727526, 17342441149450781813176059990
Offset: 0

Views

Author

R. H. Hardin, Mar 30 2011

Keywords

Comments

Number of n X n symmetric matrices with nonnegative integer entries and all row and column sums 4. - Andrew Howroyd, Apr 07 2020
In A005816 matrix elements on the diagonal are counted with a factor 2. This sequence here counts labeled multigraphs with n nodes (may be disconnected, undirected edges) without loops and degree at each node <=4. - R. J. Mathar, Jun 05 2022

Examples

			All solutions for 8X2
..1..1....1..1....1..1....1..0....1..1
..1..0....1..1....1..1....1..0....1..1
..1..0....1..1....1..0....1..0....1..1
..1..0....1..0....1..0....1..0....1..1
..0..1....0..1....0..1....0..1....0..0
..0..1....0..0....0..1....0..1....0..0
..0..1....0..0....0..0....0..1....0..0
..0..0....0..0....0..0....0..1....0..0

Links

Crossrefs

Row 4 of A188403.
Cf. A139670 (matrix elements 0 or 1).

Extensions

a(0)=1 prepended and terms a(12) and beyond from Andrew Howroyd, Apr 07 2020
Showing 1-6 of 6 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.