A055602 -id:A055602 - cp's OEIS frontend

A058481 a(n) = 3^n - 2.

1, 7, 25, 79, 241, 727, 2185, 6559, 19681, 59047, 177145, 531439, 1594321, 4782967, 14348905, 43046719, 129140161, 387420487, 1162261465, 3486784399, 10460353201, 31381059607, 94143178825, 282429536479, 847288609441

Offset: 1

Vladeta Jovovic, Nov 26 2000

a(n) = number of 2 X n binary matrices with no zero rows or columns.
a(n)^2 + 2*a(n+1) + 1 is a square number, i.e., a(n)^2 + 2*a(n+1) + 1 = (a(n)+3)^2: for n=2, a(2)^2 + 2*a(3) + 1 = 7^2 + 2*25 + 1 = 100 = (7+3)^2; for n=3, a(3)^2 + 2*a(4) + 1 = 25^2 + 2*79 + 1 = 784 = (25+3)^2. - Bruno Berselli, Apr 23 2010
Sum of n-th row of triangle of powers of 3: 1; 3 1 3; 9 3 1 3 9; 27 9 3 1 3 9 27; ... . - Philippe Deléham, Feb 24 2014
a(n) = least k such that k*3^n + 1 is a square. Thus, the square is given by (3^n-1)^2. - Derek Orr, Mar 23 2014
Binomial transform of A058481: (1, 6, 12, 24, 48, 96, ...) and second binomial transform of (1, 5, 1, 5, 1, 5, ...). - Gary W. Adamson, Aug 24 2016
Number of ordered pairs of nonempty sets whose union is [n]. a(2) = 7: ({1,2},{1,2}), ({1,2},{1}), ({1,2},{2}), ({1},{1,2}), ({1},{2}), ({2},{1,2}), ({2},{1}). If "nonempty" is omitted we get A000244. - Manfred Boergens, Mar 29 2023

			G.f. = x + 7*x^2 + 25*x^3 + 79*x^4 + 241*x^5 + 727*x^6 + 2185*x^7 + 6559*x^8 + ...
a(1) = 1;
a(2) = 3 + 1 + 3 = 7;
a(3) = 9 + 3 + 1 + 3 + 9 = 25;
a(4) = 27 + 9 + 3 + 1 + 3 + 9 + 27 = 79; etc. - _Philippe Deléham_, Feb 24 2014

G. C. Greubel, Table of n, a(n) for n = 1..1000
John Elias, Illustration: Union of Triple-Sierpinski Triangles
Index entries for linear recurrences with constant coefficients, signature (4,-3).

Cf. A055602, A024206 (unlabeled case), A055609, A058482, A000244.

Cf. A003462, A007051, A034472, A024023, A067771, A029858, A134931, A115099, A100774, A079004.

A058481:=n->3^n-2; seq(A058481(n), n=1..30); # Wesley Ivan Hurt, Mar 24 2014

a=1;lst={a};Do[a=a*3+4;AppendTo[lst,a],{n,0,5!}];lst (* Vladimir Joseph Stephan Orlovsky, Dec 25 2008 *)
3^Range[30]-2  (* Harvey P. Dale, Mar 28 2011 *)
LinearRecurrence[{4, -3}, {1, 7}, 25] (* G. C. Greubel, Aug 25 2016 *)

a(n)=3^n-2 \\ Charles R Greathouse IV, Feb 06 2017

{a(n) = if( n<1, 0, 3^n - 2)}; /* Michael Somos, Feb 17 2017 */

Number of m X n binary matrices with no zero rows or columns is Sum_{j=0..m} (-1)^j*C(m, j)*(2^(m-j)-1)^n.
From Mohammad K. Azarian, Jan 14 2009: (Start)
G.f.: 1/(1-3*x)-2/(1-x)+1.
E.g.f.: e^(3*x)-2*(e^x)+1. (End)
a(n) = 3*a(n-1) + 4 (with a(1)=1). - Vincenzo Librandi, Aug 07 2010
a(n) = 4*a(n-1) - 3*a(n-2). - G. C. Greubel, Aug 25 2016

More terms from Larry Reeves (larryr(AT)acm.org), Dec 04 2000

A104601 Triangle T(r,n) read by rows: number of n X n (0,1)-matrices with exactly r entries equal to 1 and no zero row or columns.

Original entry on oeis.org

1, 0, 2, 0, 4, 6, 0, 1, 45, 24, 0, 0, 90, 432, 120, 0, 0, 78, 2248, 4200, 720, 0, 0, 36, 5776, 43000, 43200, 5040, 0, 0, 9, 9066, 222925, 755100, 476280, 40320, 0, 0, 1, 9696, 727375, 6700500, 13003620, 5644800, 362880, 0, 0, 0, 7480, 1674840

Offset: 1

Ralf Stephan, Mar 27 2005

			1
0,2
0,4,6
0,1,45,24
0,0,90,432,120
0,0,78,2248,4200,720
0,0,36,5776,43000,43200,5040
0,0,9,9066,222925,755100,476280,40320
0,0,1,9696,727375,6700500,13003620,5644800,362880
0,0,0,7480,1674840,37638036,179494350,226262400,71850240,3628800

M. Maia and M. Mendez, On the arithmetic product of combinatorial species, arXiv:math/0503436 [math.CO], 2005.

Right-edge diagonals include A000142, A055602, A055603. Row sums are in A104602.
Column sums are in A048291. The triangle read by columns = A055599.
Cf. A049311, A054976, A057150, A057151, A101370, A120732, A120733, A138178, A316983, A319616.

t[r_, n_] := Sum[ Sum[ (-1)^(2n - d - k/d)*Binomial[n, d]*Binomial[n, k/d]*Binomial[k, r], {d, Divisors[k]}], {k, r, n^2}]; Flatten[ Table[t[r, n], {r, 1, 10}, {n, 1, r}]] (* Jean-François Alcover, Jun 27 2012, from formula *)
Table[Length[Select[Subsets[Tuples[Range[n],2],{n}],Union[First/@#]==Union[Last/@#]==Range[k]&]],{n,6},{k,n}] (* Gus Wiseman, Nov 14 2018 *)

T(r, n) = Sum{l>=r, Sum{d|l, (-1)^(2n-d-l/d)*C(n, d)*C(n, l/d)*C(l, r) }}.

E.g.f.: Sum(((1+x)^n-1)^n*exp((1-(1+x)^n)*y)*y^n/n!,n=0..infinity). - Vladeta Jovovic, Feb 24 2008

A055603 Number of n X n binary matrices with no zero rows or columns and with n+2 ones.

Original entry on oeis.org

0, 1, 90, 2248, 43000, 755100, 13003620, 226262400, 4037765760, 74481120000, 1425927888000, 28389466828800, 588245898240000, 12685887076262400, 284623499160000000, 6639289429893120000, 160886197351047168000, 4046412223559946240000, 105527367894862577664000

Offset: 1

Vladeta Jovovic, Jun 01 2000

nonn

A diagonal of triangle A104601.

Cf. A055602.

Number of m X n binary matrices with no zero rows or columns and with k=0..m*n ones is Sum_{i=0..n} (-1)^i*C(n, i)*a(m, n-i, k) where a(m, n, k)=Sum_{i=0..m} (-1)^i*C(m, i)*C((m-i)*n, k).

a(n) = n*(n-1)*(9*n^4+42*n^3+7*n^2-122*n-120)*n!/576. - Vladeta Jovovic, Mar 25 2006

More terms from Vaclav Kotesovec, Jul 12 2018

A058482 Number of 3 X n binary matrices with no zero rows or columns.

Original entry on oeis.org

1, 25, 265, 2161, 16081, 115465, 816985, 5745121, 40294561, 282298105, 1976795305, 13839692881, 96884227441, 678208723945, 4747518463225, 33232801429441, 232630126566721, 1628412435648985, 11398891698588745, 79792255837258801, 558545832702224401

Offset: 1

Vladeta Jovovic, Nov 26 2000

Index entries for linear recurrences with constant coefficients, signature (11,-31,21).

Cf. A055602, A024206, A055609 (unlabeled case), A058481, column 3 of A183109 and A218695.

LinearRecurrence[{11,-31,21},{1,25,265},30] (* Harvey P. Dale, Aug 15 2014 *)

a(n) = 7^n-3*3^n+3 \\ Charles R Greathouse IV, Feb 10 2017

Number of m X n binary matrices with no zero rows or columns is Sum_{j=0..m}(-1)^j*C(m, j)*(2^(m-j)-1)^n.
a(n) = 7^n-3*3^n+3.
a(n) = 11*a(n-1)-31*a(n-2)+21*a(n-3). G.f.: -x*(21*x^2+14*x+1) / ((x-1)*(3*x-1)*(7*x-1)). - Colin Barker, Jul 10 2013

More terms from Larry Reeves (larryr(AT)acm.org), Dec 04 2000

More terms from Colin Barker, Jul 10 2013

A084485 Number of 3 X n 0-1 matrices which have n+2 1's and have no zero rows or zero columns.

Original entry on oeis.org

1, 12, 90, 522, 2595, 11673, 49014, 195828, 753813, 2819475, 10308144, 36998118, 130786695, 456452493, 1575799290, 5389290792, 18281487081, 61569776727, 206040460212, 685584843450, 2269566343611, 7478425876977, 24538396875870, 80206515476892, 261239771497725

Offset: 1

W. Edwin Clark, May 27 2003

This is the number of spanning subgraphs of the complete bipartite graph K(3,n) with n + 2 edges and no isolated vertices. If the subgraphs are also connected then they are spanning trees. The number of spanning trees in K(m,n) is known. See A001787.

M. Janjic and B. Petkovic, A Counting Function, arXiv preprint arXiv:1301.4550, 2013. - From N. J. A. Sloane, Feb 13 2013
M. Janjic, B. Petkovic, A Counting Function Generalizing Binomial Coefficients and Some Other Classes of Integers, J. Int. Seq. 17 (2014) # 14.3.5
Index entries for linear recurrences with constant coefficients, signature (15,-93,305,-558,540,-216)

Cf. A001787.

Cf. A084486, A055602, A055603.

with(LinearAlgebra): num1s:= (M, m, n)->add(ListTools[Flatten](convert(M, listlist))[j], j=1..m*n): binrows:= n->[seq(convert(i+2^n, base, 2)[1..n], i=1..2^n-1)]: a:= proc(n) local A, L, i, j, k, S, M: S := 0: L := binrows(n): for i from 1 to 2^n-1 do for j from 1 to 2^n-1 do for k from 1 to 2^n-1 do A := Matrix([L[i], L[j], L[k]]); if num1s(A, 3, n)=n+2 and (not has(Matrix([1, 1, 1]).A, 0)) then S := S+1; end if; od; od; od; S; end proc: seq (a(n), n=1..5);

a[n_] := n*(4*(3*n - 1)*3^n - 9*(n - 1)*2^n)/24;
Array[a, 25] (* Jean-François Alcover, Nov 10 2017, after Vladeta Jovovic *)

a(n) = n*(4*(3*n-1)*3^n-9*(n-1)*2^n)/24. - Vladeta Jovovic, May 28 2003

G.f.: x*(1-3*x+3*x^2-17*x^3+33*x^4)/((3*x-1)^3*(2*x-1)^3). - Alois P. Heinz, Sep 24 2012

Comment corrected by W. Edwin Clark, Sep 24 2012

A084486 Number of 4 X n 0-1 matrices which have n+3 1's and have no zero rows or zero columns.

Original entry on oeis.org

1, 32, 522, 5776, 50600, 380424, 2570932, 16073600, 94748400, 533515240, 2896652396, 15268777440, 78544641448, 395875164104, 1960998472260, 9570684204544, 46112171619296, 219682468794600, 1036237335593500

Offset: 1

W. Edwin Clark, May 27 2003

This is the number of spanning subgraphs of the complete bipartite graph K(4,n) which have n+3 edges and no isolated vertices. If the subgraphs are also connected then they are spanning trees. The number of spanning trees in K(m,n) is known. See A001787.

M. Janjic and B. Petkovic, A Counting Function, arXiv preprint arXiv:1301.4550, 2013. - From N. J. A. Sloane, Feb 13 2013
M. Janjic, B. Petkovic, A Counting Function Generalizing Binomial Coefficients and Some Other Classes of Integers, J. Int. Seq. 17 (2014) # 14.3.5

Cf. A001787.

Cf. A084485, A055602, A055603.

with(LinearAlgebra): num1s := (M,m,n)->add(ListTools[Flatten](convert(M,listlist))[j],j=1..m*n): binrows := n->[seq(convert(i+2^n,base,2)[1..n],i=1..2^n-1)]; a := proc(n) local A,L,i,j,k,el,S,M: S := 0: L := binrows(n): for i from 1 to 2^n-1 do for j from 1 to 2^n-1 do for k from 1 to 2^n-1 do for el from 1 to 2^n-1 do A := Matrix([L[i],L[j],L[k],L[el]]); if num1s(A,4,n)=n+3 and (not has(Matrix([1,1,1,1]).A,0)) then S := S+1; end if; od; od; od; od; S; end proc: seq (a(n), n=1..2);

a[n_] := n/48*((27*4^n - 32*3^n + 6*2^n)*n^2 + (-9*4^n + 32*3^n - 18*2^n)*n + (-6*4^n + 12*2^n));
Array[a, 20] (* Jean-François Alcover, Nov 10 2017, after Vladeta Jovovic *)

n/48*((27*4^n-32*3^n+6*2^n)*n^2+(-9*4^n+32*3^n-18*2^n)*n+(-6*4^n+12*2^n)). - Vladeta Jovovic, May 28 2003

G.f.: x * (1 -4*x -40*x^2 +44*x^3 +2885*x^4 -19624*x^5 +59014*x^6 -97728*x^7 +98064*x^8 -67200*x^9 +28800*x^10) / ((3*x-1)^4*(2*x-1)^4*(4*x-1)^4). - Alois P. Heinz, Sep 24 2012

Comment corrected by W. Edwin Clark, Sep 24 2012

A135593 Number of n X n symmetric (0,1)-matrices with exactly n+1 entries equal to 1 and no zero rows or columns.

Original entry on oeis.org

2, 9, 36, 140, 540, 2142, 8624, 35856, 152280, 666380, 2982672, 13716144, 64487696, 310693320, 1528801920, 7691652992, 39474925344, 206758346256, 1103332900160, 5999356762560, 33197323465152, 186925844947424, 1069977071943936

Offset: 2

Vladeta Jovovic, Feb 25 2008

Vincenzo Librandi, Table of n, a(n) for n = 2..200

Cf. A000085, A055602, A086364.

A135593 := proc(n) n!*coeftayl( x^2*(x+2)/2*exp(x*(x+2)/2),x=0,n) ; end: seq(A135593(n),n=2..40) ; # R. J. Mathar, Mar 31 2008

Rest[Rest[CoefficientList[Series[x^2*(x+2)/2*E^(x*(x+2)/2), {x, 0, 20}], x]* Range[0, 20]!]] (* Vaclav Kotesovec, Oct 20 2012 *)
Flatten[{2,9,RecurrenceTable[{(n-5)*(n-2)*a[n]==(n-6)*n*a[n-1]+(n-4)*(n-1)*n*a[n-2],a[4]==36,a[5]==140},a,{n,4,20}]}] (* Vaclav Kotesovec, Oct 20 2012 *)

E.g.f.: x^2*(x+2)/2*exp(x*(x+2)/2).
Recurrence (for n>5): (n-5)*(n-2)*a(n) = (n-6)*n*a(n-1) + (n-4)*(n-1)*n*a(n-2). - Vaclav Kotesovec, Oct 20 2012
a(n) ~ 1/4*sqrt(2)*exp(sqrt(n)-n/2-1/4)*n^(n/2+3/2). - Vaclav Kotesovec, Oct 20 2012

More terms from R. J. Mathar, Mar 31 2008

A307232 a(n) is the number of n X n {0,1}-matrices (over the reals) that contain no zeros when squared.

Original entry on oeis.org

1, 1, 3, 73, 6003, 2318521, 4132876803

Offset: 0

Christopher Cormier, Mar 29 2019

For every n, there are trivial solutions where an entire row is filled with 1's and an entire column is filled with 1's, and the column index is equal to the row index. This easily follows from the nature of matrix multiplication. Every matrix that has at least one of these row/column pairs along with any other 1's is also a solution because there are no negative numbers involved here. The number of trivial solutions is given by A307248.

			For n = 2, the a(2) = 3 solutions are
  1 1    0 1    1 1
  1 0    1 1    1 1

Wikipedia, Logical matrix.

Cf. A002720, A055601, A055602.
A002416 is the total number of possible square binary matrices.
A307248 gives a lower bound.

%Exhaustively searches all matrices
%from n = 1 to 5
result = zeros(1,5);
for n = 1:5
for m = 0:2^(n^2)-1
    p = fliplr(dec2bin(m,n^2) - '0');
    M = reshape(p,[n n]);
    D = M^2;
    if(isempty(find(D==0, 1)))
        result(n) = result(n) + 1;
    end
end
end

a[n_] := Module[{b, iter, cnt = 0}, iter = Sequence @@ Table[{b[k], 0, 1}, {k, 1, n^2}]; Do[If[FreeQ[MatrixPower[Partition[Array[b, n^2], n], 2], 0], cnt++], iter // Evaluate]; cnt]; a[0] = 1;
Do[Print[a[n]], {n, 0, 5}] (* Jean-François Alcover, Jun 23 2019 *)

a(6) from Giovanni Resta, May 29 2019

cp's OEIS Frontend

A058481 a(n) = 3^n - 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A104601 Triangle T(r,n) read by rows: number of n X n (0,1)-matrices with exactly r entries equal to 1 and no zero row or columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A055603 Number of n X n binary matrices with no zero rows or columns and with n+2 ones.

Views

Author

Keywords

Crossrefs

Formula

Extensions

A058482 Number of 3 X n binary matrices with no zero rows or columns.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A084485 Number of 3 X n 0-1 matrices which have n+2 1's and have no zero rows or zero columns.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A084486 Number of 4 X n 0-1 matrices which have n+3 1's and have no zero rows or zero columns.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A135593 Number of n X n symmetric (0,1)-matrices with exactly n+1 entries equal to 1 and no zero rows or columns.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A307232 a(n) is the number of n X n {0,1}-matrices (over the reals) that contain no zeros when squared.