A002725 Number of incidence matrices: n X (n+1) binary matrices under row and column permutations.

1, 3, 13, 87, 1053, 28576, 2141733, 508147108, 402135275365, 1073376057490373, 9700385489355970183, 298434346895322960005291, 31479360095907908092817694945, 11474377948948020660089085281068730, 14568098446466140788730090352230460100956

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

a(0) = 1 by convention.

Examples

			a(1) = 3: [0,0], [0,1], [1,1].
a(2) = 13:
000 000 000 000 001 001 001 001 001 011 011 011 111
000 001 011 111 001 010 011 110 111 011 101 111 111
		

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

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 0..23 from Alois P. Heinz)
• A. Kerber, Experimentelle Mathematik, Séminaire Lotharingien de Combinatoire. Institut de Recherche Math. Avancée, Université Louis Pasteur, Strasbourg, Actes 19 (1988), 77-83. [Annotated scanned copy]
• B. Misek, On the number of classes of strongly equivalent incidence matrices, (Czech with English summary) Casopis Pest. Mat. 89 1964 211-218.

Crossrefs

Cf. A002623, A002727, A006148, A002728, A002724.

A diagonal of the array A(m,n) described in A028657. - N. J. A. Sloane, Sep 01 2013

Programs

Maple

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:= n-> add(add(2^add(add(igcd(i, j)* coeff(s, x, i)*
      coeff(t, x, j), j=1..degree(t)), i=1..degree(s))/
      mul(i^coeff(s, x, i)*coeff(s, x, i)!, i=1..degree(s))/
      mul(i^coeff(t, x, i)*coeff(t, x, i)!, i=1..degree(t)),
      t=b(n+1$2)), s=b(n$2)):
seq(a(n), n=0..12);  # Alois P. Heinz, Aug 01 2014

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_] := 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+1, n+1]}], {s,  b[n, n]}];
Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Feb 25 2015, after Alois P. Heinz *)

PARI

a(n) = A(n+1,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+1} (fix A[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 fix A[...] = 2^sum_{i, j>=1} (gcd(i, j)*s_i*t_j). - Sean A. Irvine, Jul 31 2014

Extensions

More terms from Vladeta Jovovic, Feb 04 2000