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.

A002724 Number of inequivalent n X n binary matrices, where equivalence means permutations of rows or columns.

Original entry on oeis.org

1, 2, 7, 36, 317, 5624, 251610, 33642660, 14685630688, 21467043671008, 105735224248507784, 1764356230257807614296, 100455994644460412263071692, 19674097197480928600253198363072, 13363679231028322645152300040033513414, 31735555932041230032311939400670284689732948
Offset: 0

Views

Author

Keywords

Comments

A diagonal of the array A(m,n) described in A028657. - N. J. A. Sloane, Sep 01 2013
Also, number of bipartite graphs with both partite sets of size n, one of which is marked. For connected bipartite graphs, see A363846. - Max Alekseyev, Jun 24 2023

References

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

Crossrefs

Cf. A028657 (this sequence is the diagonal). - N. J. A. Sloane, Sep 01 2013
Column k=2 of A246106.

Programs

  • Maple
    # See Marko Riedel link.
  • Mathematica
    b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i < 1, {}, Union[Flatten[Table[ Function[{p}, p + j*x^i] /@ b[n - i*j, i - 1], {j, 0, n/i}]]]]];
    g[n_, k_] := g[n, k] = Sum[Sum[2^Sum[Sum[GCD[i, j]*Coefficient[s, x, i]* Coefficient[t, x, j], {j, 1, Exponent[t, x]}], {i, 1, Exponent[s, x]}]/ Product[i^Coefficient[s, x, i]*Coefficient[s, x, i]!, {i, 1, Exponent[s, x]}]/Product[i^Coefficient[t, x, i]*Coefficient[t, x, i]!, {i, 1, Exponent[t, x]}], {t, b[n + k, n + k]}], {s, b[n, n]}];
    A[n_, k_] := g[Min[n, k], Abs[n - k]];
    Table[A[n, n], {n, 0, 15}] (* Jean-François Alcover, Aug 10 2018, after Alois P. Heinz *)
  • PARI
    a(n) = A(n,n) \\ A defined in A028657. - Andrew Howroyd, Mar 01 2023

Formula

a(n) = Sum_{1*s_1+2*s_2+...=n, 1*t_1+2*t_2+...=n} (fixA[s_1, s_2, ...;t_1, t_2, ...]/(1^s_1*s_1!*2^s_2*s_2!*...*1^t_1*t_1!*2^t_2*t_2!*...)) where fixA[...] = 2^Sum_{i, j>=1} (gcd(i, j)*s_i*t_j). - Christian G. Bower, Dec 18 2003
a(n) = A028657(2*n, n). - Max Alekseyev, Jun 24 2023

Extensions

More terms from Vladeta Jovovic, Feb 04 2000
a(15) from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 24 2008

A242095 Number A(n,k) of inequivalent n X n matrices with entries from [k], where equivalence means permutations of rows or columns or the symbol set; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 5, 1, 0, 1, 1, 8, 18, 1, 0, 1, 1, 9, 139, 173, 1, 0, 1, 1, 9, 408, 15412, 2812, 1, 0, 1, 1, 9, 649, 332034, 10805764, 126446, 1, 0, 1, 1, 9, 749, 2283123, 3327329224, 50459685390, 16821330, 1, 0
Offset: 0

Views

Author

Alois P. Heinz, Aug 14 2014

Keywords

Comments

A(n,k) = A(n,k+1) for k >= n^2.

Examples

			A(2,2) = 5:
  [1 1]  [2 1]  [2 2]  [2 1]  [2 1]
  [1 1], [1 1], [1 1], [2 1], [1 2].
Square array A(n,k) begins:
  1, 1,    1,        1,          1,            1, ...
  0, 1,    1,        1,          1,            1, ...
  0, 1,    5,        8,          9,            9, ...
  0, 1,   18,      139,        408,          649, ...
  0, 1,  173,    15412,     332034,      2283123, ...
  0, 1, 2812, 10805764, 3327329224, 173636442196, ...
		

Crossrefs

Main diagonal gives A091058.
A(n,n^2) gives A091057.

Programs

  • Maple
    with(numtheory):
    b:= proc(n, i) option remember; `if`(n=0, {0}, `if`(i<1, {},
          {seq(map(p-> p+j*x^i, b(n-i*j, i-1) )[], j=0..n/i)}))
        end:
    A:= proc(n, k) option remember; add(add(add(mul(mul(add(d*
          coeff(u, x, d), d=divisors(ilcm(i, j)))^(igcd(i, j)*
          coeff(s, x, i)*coeff(t, x, j)), j=1..degree(t)),
          i=1..degree(s))/mul(i^coeff(u, x, i)*coeff(u, x, i)!,
          i=1..degree(u))/mul(i^coeff(t, x, i)*coeff(t, x, i)!,
          i=1..degree(t))/mul(i^coeff(s, x, i)*coeff(s, x, i)!,
          i=1..degree(s)), u=b(k$2)), t=b(n$2)), s=b(n$2))
        end:
    seq(seq(A(n, d-n), n=0..d), d=0..10);
  • Mathematica
    b[n_, i_] := b[n, i] = If[n==0, {0}, If[i<1, {}, Flatten@Table[Map[ Function[p, p + j*x^i], b[n - i*j, i - 1]], {j, 0, n/i}]]];
    A[n_, k_] := A[n, k] = Sum[Sum[Sum[Product[Product[With[{g = GCD[i, j]* Coefficient[s, x, i]*Coefficient[t, x, j]}, If[g == 0, 1, Sum[d* Coefficient[u, x, d], {d, Divisors[LCM[i, j]]}]^g]], {j, Exponent[t, x]} ],
    {i, Exponent[s, x]}]/Product[i^Coefficient[u, x, i]*Coefficient[u, x, i]!,
    {i, Exponent[u, x]}]/Product[i^Coefficient[t, x, i]*Coefficient[t, x, i]!,
    {i, Exponent[t, x]}]/Product[i^Coefficient[s, x, i]*Coefficient[s, x, i]!,
    {i, Exponent[s, x]}], {u, b[k, k]}], {t, b[n, n]}], {s, b[n, n]}];
    Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Feb 21 2016, after Alois P. Heinz, updated Jan 01 2021 *)

A242093 Number A(n,k) of inequivalent n X k binary matrices, where equivalence means permutations of rows or columns or the symbol set; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 5, 2, 1, 1, 3, 8, 8, 3, 1, 1, 3, 14, 18, 14, 3, 1, 1, 4, 20, 47, 47, 20, 4, 1, 1, 4, 30, 95, 173, 95, 30, 4, 1, 1, 5, 40, 200, 545, 545, 200, 40, 5, 1, 1, 5, 55, 367, 1682, 2812, 1682, 367, 55, 5, 1, 1, 6, 70, 674, 4745, 14386, 14386, 4745, 674, 70, 6, 1
Offset: 0

Views

Author

Alois P. Heinz, Aug 14 2014

Keywords

Examples

			A(1,4) = 3: [0 0 0 0], [1 0 0 0], [1 1 0 0].
A(1,5) = 3: [0 0 0 0 0], [1 0 0 0 0], [1 1 0 0 0].
A(2,2) = 5:
  [0 0]  [1 0]  [1 1]  [1 0]  [1 0]
  [0 0], [0 0], [0 0], [1 0], [0 1].
A(3,2) = 8:
  [0 0]  [1 0]  [1 1]  [1 0]  [1 0]  [1 0]  [1 0]  [1 1]
  [0 0], [0 0], [0 0], [1 0], [0 1], [1 0], [0 1], [1 0].
  [0 0]  [0 0]  [0 0]  [0 0]  [0 0]  [1 0]  [1 0]  [0 0]
Square array A(n,k) begins:
  1, 1,  1,   1,    1,     1,       1,        1, ...
  1, 1,  2,   2,    3,     3,       4,        4, ...
  1, 2,  5,   8,   14,    20,      30,       40, ...
  1, 2,  8,  18,   47,    95,     200,      367, ...
  1, 3, 14,  47,  173,   545,    1682,     4745, ...
  1, 3, 20,  95,  545,  2812,   14386,    68379, ...
  1, 4, 30, 200, 1682, 14386,  126446,  1072086, ...
  1, 4, 40, 367, 4745, 68379, 1072086, 16821330, ...
		

Crossrefs

Columns (or rows) k=0-10 give: A000012, A008619, A006918(n+1), A246148, A246149, A246150, A246151, A246152, A246153, A246154, A246155.
Main diagonal gives A091059.

Programs

  • Maple
    with(numtheory):
    b:= proc(n, i) option remember; `if`(n=0, {0}, `if`(i<1, {},
          {seq(map(p-> p+j*x^i, b(n-i*j, i-1) )[], j=0..n/i)}))
        end:
    g:= proc(n, k) option remember; add(add(add(mul(mul(add(d*
          coeff(u, x, d), d=divisors(ilcm(i, j)))^(igcd(i, j)*
          coeff(s, x, i)*coeff(t, x, j)), j=1..degree(t)),
          i=1..degree(s))/mul(i^coeff(u, x, i)*coeff(u, x, i)!,
          i=1..degree(u))/mul(i^coeff(t, x, i)*coeff(t, x, i)!,
          i=1..degree(t))/mul(i^coeff(s, x, i)*coeff(s, x, i)!,
          i=1..degree(s)), u=b(2$2)), t=b(n$2)), s=b(k$2))
        end:
    A:= (n, k)-> g(sort([n, k])[]):
    seq(seq(A(n, d-n), n=0..d), d=0..12);
  • Mathematica
    b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i < 1, {}, Flatten[Table[Map[ Function[p, p + j*x^i], b[n - i*j, i - 1]], {j, 0, n/i}]]]];
    g[n_, k_] := g[n, k] = Sum[Sum[Sum[Product[Product[With[{gc = GCD[i, j]* Coefficient[s, x, i]*Coefficient[t, x, j]}, If[gc == 0, 1, Sum[d* Coefficient[u, x, d], {d, Divisors[LCM[i, j]]}]^gc]], {j, 1, Exponent[t, x]}],
    {i, Exponent[s, x]}]/Product[i^Coefficient[u, x, i]*Coefficient[u, x, i]!,
    {i, Exponent[u, x]}]/Product[i^Coefficient[t, x, i]*Coefficient[t, x, i]!,
    {i, Exponent[t, x]}]/Product[i^Coefficient[s, x, i]*Coefficient[s, x, i]!,
    {i, Exponent[s, x]}], {u, b[2, 2]}], {t, b[n, n]}], {s, b[k, k]}];
    A[n_, k_] := g @@ Sort[{n, k}];
    Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Apr 25 2016, adapted from Maple, updated Jan 01 2021 *)

A091058 Number of n X n matrices over symbol set {1,...,n} equivalent under any permutation of row, columns or the symbol set.

Original entry on oeis.org

1, 1, 5, 139, 332034, 173636442196, 27652322898323351716, 2006943506669869627232430791792, 95763314593596534914617136274432901605313744, 4114852471732264714685900791520508800628430894815984377778000
Offset: 0

Views

Author

Christian G. Bower, Dec 17 2003

Keywords

Crossrefs

Main diagonal of A242095.

Programs

  • Mathematica
    b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i < 1, {}, Flatten @ Table[Map[Function[p, p + j*x^i], b[n - i*j, i - 1]], {j, 0, n/i}]]];
    A242095[n_, k_] := A242095[n, k] = With[{co = Coefficient, ex = Exponent}, Sum[Sum[Sum[Product[Product[With[{g = GCD[i, j]*co[s, x, i]*co[t, x, j]}, If[g == 0, 1, Sum[d*co[u, x, d], {d, Divisors[LCM[i, j]]}]^g]], {j, ex[t, x]}], {i, ex[s, x]}]/Product[i^co[u, x, i]*co[u, x, i]!, {i, ex[u, x]}]/Product[i^co[t, x, i]*co[t, x, i]!, {i, ex[t, x]}]/Product[i^co[s, x, i]*co[s, x, i]!, {i, ex[s, x]}], {u, b[k, k]}], {t, b[n, n]}], {s, b[n, n]}]];
    a[n_] := A242095[n, n];
    Table[Print[n, " ", a[n]]; a[n], {n, 0, 12}] (* Jean-François Alcover, May 29 2023, after Alois P. Heinz in A242095 *)
  • Sage
    Pol. = InfinitePolynomialRing(QQ)
    @cached_function
    def Z(n):
        if n == 0: return Pol.one()
        return sum(x[k]*Z(n-k) for k in (1..n))/n
    @cached_function
    def monprod(M):
        p = Pol.one()
        V = [m.variables() for m in M]
        T = cartesian_product(V)
        for t in T:
            r = [Pol.varname_key(str(u))[1] for u in t]
            j = [Pol(M[u[0]]).degree(u[1]) for u in enumerate(t)]
            lcm_r = lcm(r)
            p *= x[lcm_r]^(prod(r)/lcm_r*prod(j))
        return p
    @cached_function
    def pol_isotop(n,k):
        P = Z(n)
        p = Pol.zero()
        coeffs = P.coefficients()
        mons = P.monomials()
        C = cartesian_product(k*[mons])
        Csorted = [tuple(sorted(u)) for u in C]
        Cset = set(Csorted)
        for c in Cset:
            p += Csorted.count(c)*prod([coeffs[mons.index(u)] for u in c])*monprod(c)
        return p
    @cached_function
    def rule_sub(r,m):
        D = 0
        for d in divisors(r):
            try: D += d*m.degrees()[-d-1]
            except: break
        return D
    def a(n,k=2):
        P = Z(n)
        coeffs = P.coefficients()
        Q = pol_isotop(n,k)
        inds = [Pol.varname_key(str(u))[1] for u in Q.variables()]
        p = 0
        for mon in enumerate(P.monomials()):
            m = Pol(mon[1])
            p += coeffs[mon[0]]*Q.subs({x[i]:rule_sub(i,m) for i in inds})
        return p
    # Philip Turecek, Jun 17 2023

Formula

a(n) = Sum_{1*s_1+2*s_2+...=n, 1*t_1+2*t_2+...=n, 1*u_1+2*u_2+...=n} (fixA[s_1, s_2, ...;t_1, t_2, ...;u_1, u_2, ...]/ (1^s_1*s_1!*2^s_2*s_2!*... *1^t_1*t_1!*2^t_2*t_2!*... *1^u_1*u_1!*2^u_2*u_2!*...)) where fixA[...] = Product_{i, j>=1} ( (Sum_{d|lcm(i, j)} (d*u_d))^(gcd(i, j)*s_i*t_j)).
a(n) asymptotic to n^(n^2)/(n!^3) = A002489(n)/(A000142(n)^3).

Extensions

a(9) from Alois P. Heinz, Aug 14 2014

A353585 Square array T(n,k): row n lists the number of inequivalent matrices over Z/nZ, modulo permutations of rows and columns, of size r X c, 1 <= r <= c, c >= 1.

Original entry on oeis.org

1, 1, 2, 1, 3, 3, 1, 7, 6, 4, 1, 4, 27, 10, 5, 1, 13, 10, 76, 15, 6, 1, 36, 92, 20, 175, 21, 7, 1, 5, 738, 430, 35, 351, 28, 8, 1, 22, 15, 8240, 1505, 56, 637, 36, 9, 1, 87, 267, 35, 57675, 4291, 84, 1072, 45, 10, 1, 317, 5053, 1996, 70, 289716, 10528, 120, 1701, 55, 11
Offset: 1

Views

Author

M. F. Hasler, Apr 28 2022

Keywords

Comments

The array is read by falling antidiagonals.
Each row lists the number of inequivalent matrices of size 1 X 1, then 2 X 1, 2 X 2, then 3 X 1, 3 X 2, 3 X 3, etc., with coefficients in Z/nZ (or equivalently, in {1, ..., n}). See Examples for more.
Row 1 counts the zero matrices, there is only one of any size. Row 2 counts binary matrices, this is the lower triangular part of A028657, without the trivial row & column 0. (This table might have been extended with a trivial column 0 = A000012 (counting the 1 matrix of size 0) and row 0 = A000007 counting the number of r X c matrices with no entry, as done in A246106.)
The square matrices (size 1 X 1, 2 X 2, 3 X 3, ...) are counted in columns with triangular numbers, k = T(r) = r(r+1)/2 = (1, 3, 6, 10, 15, ...) = A000217.

Examples

			The table starts
   n \ k=1,  2,   3,   4,   5,   6, ...: T(n,k)
  ----+--------------------------------------
   1  |  1   1    1    1    1     1 ...
   2  |  2   3    7    4   13    36 ...
   3  |  3   6   27   10   92   738 ...
   4  |  4  10   76   20  430  8240 ...
   5  |  5  15  175   35 1505 57675 ...
  ...
Columns 2, 3 and 4, 5, 6 correspond to matrices of size 1 X 2, 2 X 2 and 1 X 3, 2 X 3, 3 X 3, respectively.
Column 4 says that there are (1, 4, 10, 20, 35, ...) inequivalent matrices of size 1 X 3 with entries in Z/nZ (n = 1, 2, 3, 4, ...); these numbers are given by (n+2 choose 3) = binomial(n+2, 3) = n(n+1)(n+2)/6 = A000292(n).
		

Crossrefs

All of the following related sequences can be expressed in terms of T(n, k, r) := T(n, k(k-1)/2 + r), WLOG r <= k:
A028657(n,k) = A353585(2,n,k): inequivalent m X n binary matrices,
A002723(n) = T(2,n,2): size n X 2, A002724(n) = T(2,n,n): size n X n,
A002727(n) = T(2,n,3): size n X 3, A002725(n) = T(2,n,n+1): size n X (n+1),
A006148(n) = T(2,n,4): size n X 4, A002728(n) = T(2,n,n+2): size n X (n+2),
A052264(n) = T(2,n,5): size n X 5,
A052269(n) = T(3,n,n): number of inequivalent ternary matrices of size n X n,
A052271(n) = T(4,n,n): number of inequivalent matrices over Z/4Z of size n X n,
A052272(n) = T(5,n,n): number of inequivalent matrices over Z/5Z of size n X n,
A246106(n,k) = A353585(k,n,n): number of inequivalent n X n matrices over Z/kZ, and its diagonal A091058 and columns 1, 2, ..., 10: A000012, A091059, A091060, A091061, A091062, A246122, A246123, A246124, A246125, A246126.

Programs

  • PARI
    A353585(n,k,r)={if(!r,r=sqrtint(8*k)\/2; k-=r*(r-1)\2); my(m(c, p=1, L=0)=for(i=1,#c, if(i==#c || c[i+1]!=c[i], p *= c[i]^(i-L)*(i-L)!; L=i )); p, S=0); forpart(P=k, my(T=0); forpart(Q=r, T += n^sum(i=1,#P, sum(j=1,#Q, gcd(P[i],Q[j]) ))/m(Q)); S += T/m(P)); S}

Formula

Let k = c(c-1)/2 + r, 1 <= r <= c, then
T(n, c, r) := T(n, k) = Sum_{p in P(c), q in P(r)} n^S(p, q)/(N(p)*N(q)), where P(r) are the partitions of r, S(p, q) = Sum_{i in p, j in q} gcd(i, j), N(p) = Product_{distinct parts x in p} x^m(x)*m(x)!, m(x) = multiplicity of x in p.
(See, e.g., A080577 for a list of partitions of positive integers.)
In particular:
T(n, 1) = n, T(n, 2) = n(n+1)/2 = A000217(n), T(n, 4) = C(n+2, 3) = A000292(n), T(n, 7) = C(n+3, 4) = A000332(n+3), etc.: T(n, k(k+1)/2 + 1) = C(n+k, k+1),
T(n, k(k+1)/2) = A246106(k, n).

A360660 Number of inequivalent n X n {0,1} matrices modulo permutation of the rows, with exactly n 1's.

Original entry on oeis.org

1, 1, 4, 20, 133, 1027, 9259, 94033, 1062814, 13176444, 177427145, 2573224238, 39924120823, 658921572675, 11513293227271, 212109149134617, 4105637511110979, 83238756058333277, 1762856698153603049, 38905470655863251479, 892840913430059075405
Offset: 0

Views

Author

Alois P. Heinz, Feb 15 2023

Keywords

Comments

Also the number of multisets of n words of length n over binary alphabet where the first letter occurs n times. E.g., a(2) = 4: {aa,bb}, {ab,ab}, {ab,ba}, {ba,ba}.

Examples

			a(3) = 20: [111/000/000], [110/100/000], [110/010/000], [110/001/000], [101/100/000], [101/010/000], [101/001/000], [100/100/100], [100/100/010], [100/100/001], [100/011/000], [100/010/010], [100/010/001], [100/001/001], [011/010/000], [011/001/000], [010/010/010], [010/010/001], [010/001/001], [001/001/001].
		

Crossrefs

Programs

  • Maple
    g:= proc(n, i, j) option remember; expand(`if`(j=0, 1, `if`(i<0, 0, add(
          g(n, i-1, j-k)*x^(i*k)*binomial(binomial(n, i)+k-1, k), k=0..j))))
        end:
    a:= n-> coeff(g(n$3), x, n):
    seq(a(n), n=0..20);
  • Mathematica
    g[n_, i_, j_] := g[n, i, j] = Expand[If[j == 0, 1, If[i < 0, 0, Sum[g[n, i - 1, j - k]*x^(i*k)*Binomial[Binomial[n, i] + k - 1, k], {k, 0, j}]]]];
    a[n_] := SeriesCoefficient[g[n, n, n], {x, 0, n}];
    Table[a[n], {n, 0, 20}] (* Jean-François Alcover, May 28 2023, after Alois P. Heinz *)
    Table[SeriesCoefficient[Product[1/(1 - x^k)^Binomial[n, k], {k, 1, n}], {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Apr 15 2025 *)

Formula

a(n) = A220886(n,n).
a(n) = [x^n] Product_{k=1..n} 1/(1 - x^k)^binomial(n,k). - Vaclav Kotesovec, Apr 15 2025
Showing 1-6 of 6 results.