A058482 -id:A058482 - 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

A183109 Triangle read by rows: T(n,m) = number of n X m binary matrices with no zero rows or columns (n >= 1, 1 <= m <= n).

Original entry on oeis.org

1, 1, 7, 1, 25, 265, 1, 79, 2161, 41503, 1, 241, 16081, 693601, 24997921, 1, 727, 115465, 10924399, 831719761, 57366997447, 1, 2185, 816985, 167578321, 26666530801, 3776451407065, 505874809287625

Offset: 1

Steffen Eger, Feb 01 2011

T(n,m) = T(m,n) is also the number of complete alignments between two strings of sizes m and n, respectively; i.e. the number of complete matchings in a bipartite graph
From Manfred Boergens, Jul 25 2021: (Start)
The matrices in the definition are a superset of the matrices in the comment to A019538 by Manfred Boergens.
T(n,m) is the number of coverings of [n] by tuples (A_1,...,A_m) in P([n])^m with nonempty A_j, with P(.) denoting the power set (corrected for clarity by Manfred Boergens, May 26 2024). For the disjoint case see A019538.
For tuples with "nonempty" dropped see A092477 and A329943 (amendment by Manfred Boergens, Jun 24 2024). (End)

			Triangle begins:
  1;
  1,    7;
  1,   25,    265;
  1,   79,   2161,     41503;
  1,  241,  16081,    693601,    24997921;
  1,  727, 115465,  10924399,   831719761,   57366997447;
  1, 2185, 816985, 167578321, 26666530801, 3776451407065, 505874809287625;
  ...

Indranil Ghosh, Rows 1..50, flattened
Ch. A. Charalambides, A problem of arrangements on chessboards and generalizations, Discrete Mathematics 27.2 (1979): 179-186. (Generalizations.)
D. E. Knuth, Problem 11243, Am. Math. Montly 113 (8) (2006) page 759.
John Riordan and Paul R. Stein, Arrangements on chessboards, Journal of Combinatorial Theory, Series A 12.1 (1972): 72-80. See Table page 78.

Cf. A218695 (same sequence with restriction m<=n dropped).
Cf. A058482 (this gives the general formula, but values only for m=3).
Main diagonal gives A048291.
Column 2 is A058481.
Cf. A019538, A092477, A329943.

A183109 := proc(n,m)
    add((-1)^j*binomial(m,j)*(2^(m-j)-1)^n,j=0..m) ;
end proc:
seq(seq(A183109(n,m),m=1..n),n=1..10) ; # R. J. Mathar, Dec 03 2015

Flatten[Table[Sum[ (-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}], {n, 1, 7}, {m, 1, n}]] (* Indranil Ghosh, Mar 14 2017 *)

tabl(nn) = {for(n=1, nn, for(m = 1, n, print1(sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n),", ");); print(););};
tabl(8); \\ Indranil Ghosh, Mar 14 2017

import math
f = math.factorial
def C(n,r): return f(n)//f(r)//f(n - r)
def T(n,m):
    return sum((-1)**j*C(m,j)*(2**(m - j) - 1)**n for j in range (m+1))
i=1
for n in range(1,21):
    for m in range(1, n+1):
        print(str(i)+" "+str(T(n, m)))
        i+=1 # Indranil Ghosh, Mar 14 2017

T(n,m) = Sum_{j=0..m}(-1)^j*C(m, j)*(2^(m-j)-1)^n.
Recursion: T(m,n) = Sum_{k=1..m} T(k,n-1)*C(m,k)*2^k - T(m,n-1).
From Robert FERREOL, Mar 14 2017: (Start)
T(n,m) = Sum_{i = 0 .. n,j = 0 ..m}(-1)^(n+m+i+j)*C(n,i)*C(m,j)*2^(i*j).
Inverse formula of: 2^(n*m) = Sum_{i = 0 .. n , j = 0 ..m} C(n,i)*C(m,j)*T(i,j). (End)
A019538(j) <= a(j). - Manfred Boergens, Jul 25 2021

A218695 Square array A(h,k) = (2^h-1)A(h,k-1) + Sum_{i=1..h-1} binomial(h,h-i)2^i*A(i,k-1), with A(1,k) = A(h,1) = 1; read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 7, 1, 1, 25, 25, 1, 1, 79, 265, 79, 1, 1, 241, 2161, 2161, 241, 1, 1, 727, 16081, 41503, 16081, 727, 1, 1, 2185, 115465, 693601, 693601, 115465, 2185, 1, 1, 6559, 816985, 10924399, 24997921, 10924399, 816985, 6559, 1

Offset: 1

M. F. Hasler, Nov 04 2012

This symmetric table is defined in the Kreweras papers, used also in A223911. Its upper or lower triangular part equals A183109, which might provide a simpler formula.
Number of h X k binary matrices with no zero rows or columns. - Andrew Howroyd, Mar 29 2023
A(h,k) is the number of coverings of [h] by tuples (A_1,...,A_k) in P([h])^k with nonempty A_j, with P(.) denoting the power set. For the disjoint case see A019538. For tuples with "nonempty" omitted see A092477 and A329943 (amendment by Manfred Boergens, Jun 24 2024). - Manfred Boergens, May 26 2024

			Array A(h,k) begins:
=====================================================
h\k | 1   2      3        4         5           6 ...
----+------------------------------------------------
  1 | 1   1      1        1         1           1 ...
  2 | 1   7     25       79       241         727 ...
  3 | 1  25    265     2161     16081      115465 ...
  4 | 1  79   2161    41503    693601    10924399 ...
  5 | 1 241  16081   693601  24997921   831719761 ...
  6 | 1 727 115465 10924399 831719761 57366997447 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals)
G. Kreweras, Dénombrements systématiques de relations binaires externes, Math. Sci. Humaines 26 (1969) 5-15.
G. Kreweras, Dénombrement des ordres étagés, Discrete Math., 53 (1985), 147-149.

Columns 1..3 are A000012, A058481, A058482.
Main diagonal is A048291.
Cf. A019538, A056152 (unlabeled case), A052332, A092477, A183109, A223911, A329943.

c(h,k)={(h<2 || k<2) & return(1); sum(i=1,h-1,binomial(h,h-i)*2^i*c(i,k-1))+(2^h-1)*c(h,k-1)}
/* For better performance when h and k are large, insert the following memoization code before "sum(...)": cM=='cM & cM=matrix(h,k); my(s=matsize(cM));
s[1] >= h & s[2] >= k & cM[h,k] & return(cM[h,k]);
s[1]

A(m, n) = sum(k=0, m, (-1)^(m-k) * binomial(m, k) * (2^k-1)^n ) \\ Andrew Howroyd, Mar 29 2023

From Andrew Howroyd, Mar 29 2023: (Start)
A(h, k) = Sum_{i=0..h} (-1)^(h-i) * binomial(h, i) * (2^i-1)^k.
A052332(n) = Sum_{i=1..n-1} binomial(n,i)*A(i, n-i) for n > 0. (End)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A183109 Triangle read by rows: T(n,m) = number of n X m binary matrices with no zero rows or columns (n >= 1, 1 <= m <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A218695 Square array A(h,k) = (2^h-1)*A(h,k-1) + Sum_{i=1..h-1} binomial(h,h-i)*2^i*A(i,k-1), with A(1,k) = A(h,1) = 1; read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A218695 Square array A(h,k) = (2^h-1)A(h,k-1) + Sum_{i=1..h-1} binomial(h,h-i)2^i*A(i,k-1), with A(1,k) = A(h,1) = 1; read by antidiagonals.