login
Number of incidence matrices: n X (n+1) binary matrices under row and column permutations.
(Formerly M2957 N1195)
6

%I M2957 N1195 #41 Mar 01 2023 11:24:34

%S 1,3,13,87,1053,28576,2141733,508147108,402135275365,1073376057490373,

%T 9700385489355970183,298434346895322960005291,

%U 31479360095907908092817694945,11474377948948020660089085281068730,14568098446466140788730090352230460100956

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

%C a(0) = 1 by convention.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Andrew Howroyd, <a href="/A002725/b002725.txt">Table of n, a(n) for n = 0..50</a> (terms 0..23 from Alois P. Heinz)

%H A. Kerber, <a href="/A002727/a002727.pdf">Experimentelle Mathematik</a>, Séminaire Lotharingien de Combinatoire. Institut de Recherche Math. Avancée, Université Louis Pasteur, Strasbourg, Actes 19 (1988), 77-83. [Annotated scanned copy]

%H B. Misek, <a href="http://dml.cz/dmlcz/108444">On the number of classes of strongly equivalent incidence matrices</a>, (Czech with English summary) Casopis Pest. Mat. 89 1964 211-218.

%F 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

%e a(1) = 3: [0,0], [0,1], [1,1].

%e a(2) = 13:

%e 000 000 000 000 001 001 001 001 001 011 011 011 111

%e 000 001 011 111 001 010 011 110 111 011 101 111 111

%p b:= proc(n, i) option remember; `if`(n=0, {0}, `if`(i<1, {},

%p {seq(map(p-> p+j*x^i, b(n-i*j, i-1))[], j=0..n/i)}))

%p end:

%p a:= n-> add(add(2^add(add(igcd(i, j)* coeff(s, x, i)*

%p coeff(t, x, j), j=1..degree(t)), i=1..degree(s))/

%p mul(i^coeff(s, x, i)*coeff(s, x, i)!, i=1..degree(s))/

%p mul(i^coeff(t, x, i)*coeff(t, x, i)!, i=1..degree(t)),

%p t=b(n+1$2)), s=b(n$2)):

%p seq(a(n), n=0..12); # _Alois P. Heinz_, Aug 01 2014

%t 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}]]];

%t 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]}];

%t Table[a[n], {n, 0, 12}] (* _Jean-François Alcover_, Feb 25 2015, after _Alois P. Heinz_ *)

%o (PARI) a(n) = A(n+1,n) \\ A defined in A028657. - _Andrew Howroyd_, Mar 01 2023

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

%Y A diagonal of the array A(m,n) described in A028657. - _N. J. A. Sloane_, Sep 01 2013

%K nonn,nice

%O 0,2

%A _N. J. A. Sloane_

%E More terms from _Vladeta Jovovic_, Feb 04 2000