A048291 -id:A048291 - cp's OEIS frontend

A173403 Inverse binomial transform of A002416.

1, 1, 13, 469, 63577, 33231721, 68519123173, 562469619451069, 18442242396353040817, 2417685638793025070212561, 1267626422541873052658376446653, 2658442047546208031914776455678477989, 22300713297142388711251601783864453690641417

Offset: 0

Brian Drake, Feb 17 2010

nonn

a(n) is the number of n X n matrices of 0's and 1's with the property that there is no index k such that both the k-th column and the k-th row consist of all zeros.

a(n) is the number of binary relations on n labeled vertices with no vertex of indegree and outdegree = 0. - Geoffrey Critzer, Oct 02 2012

E. A. Bender and S. G. Williamson, Foundations of Combinatorics with Applications, Dover, 2005, exercise 4.1.6.

Brian Drake, Table of n, a(n) for n = 0..50

Cf. A002416, A135748, A287065, A048291.

N:=8: seq( sum(binomial(n,i)*2^((n-i)^2)*(-1)^(i), i=0..n), n=0..N);

Table[Sum[(-1)^k Binomial[n,k] 2^(n-k)^2,{k,0,n}],{n,0,20}]  (* Geoffrey Critzer, Oct 02 2012 *)

a(n) = Sum_{k=0..n} (-1)^k*binomial(n,k)*2^((n-k)^2).

a(n) ~ 2^(n^2). - Vaclav Kotesovec, Oct 30 2017

A321615 Triangle read by rows: T(n,k) is the number of k X k integer matrices with sum of elements n, with no zero rows or columns, up to row and column permutation.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 6, 3, 1, 0, 1, 9, 13, 3, 1, 0, 1, 17, 38, 20, 3, 1, 0, 1, 23, 97, 82, 23, 3, 1, 0, 1, 36, 217, 311, 126, 24, 3, 1, 0, 1, 46, 453, 968, 624, 151, 24, 3, 1, 0, 1, 65, 868, 2825, 2637, 933, 162, 24, 3, 1, 0, 1, 80, 1585, 7394, 10098, 4942, 1132, 165, 24, 3, 1

Offset: 0

Andrew Howroyd, Nov 14 2018

Also the number of non-isomorphic multiset partitions of weight n with k parts and k vertices, where the weight of a multiset partition is the sum of sizes of its parts. - Gus Wiseman, Nov 18 2018

			Triangle begins:
    1
    0  1
    0  1    1
    0  1    2    1
    0  1    6    3    1
    0  1    9   13    3    1
    0  1   17   38   20    3    1
    0  1   23   97   82   23    3    1
    0  1   36  217  311  126   24    3    1
    0  1   46  453  968  624  151   24    3    1
    0  1   65  868 2825 2637  933  162   24    3    1

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Columns k=0..3 are A000007, A000012, A054974, A054975.
Row sums are A319616.
Cf. A007716, A048291, A054976, A057149, A057150, A104601, A120732, A318795, A320808.

(* See A318795 for M[m, n, k]. *)
T[n_, k_] := M[k, k, n] - 2 M[k, k-1, n] + M[k-1, k-1, n];
Table[T[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 24 2018, from PARI *)

\\ See A318795 for M.
T(n, k) = if(k==0, n==0, M(k, k, n) - 2*M(k, k-1, n) + M(k-1, k-1, n));

\\ See A340652 for G.
T(n)={[Vecrev(p) | p<-Vec(1 + sum(k=1, n, y^k*(polcoef(G(k, n, n, y), k, y) - polcoef(G(k-1, n, n, y), k, y))))]}
{ my(A=T(10)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Jan 16 2024

Column k=0 inserted by Andrew Howroyd, Jan 17 2024

A055082 Number of 4 X n binary matrices with no zero rows or columns, up to row and column permutation.

Original entry on oeis.org

1, 8, 42, 179, 633, 2001, 5745, 15274, 38000, 89331, 199715, 427184, 878152, 1741964, 3345562, 6239390, 11327863, 20065972, 34747460, 58924066, 98002370, 160086580, 257148244, 406637336, 633669040, 973971441, 1477810227, 2215179768, 3282598034, 4811946882

Offset: 1

Vladeta Jovovic, Jun 13 2000

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..1000
F. Harary, L. March and R. W. Robinson, On enumerating certain design problems in terms of bicolored graphs with no isolates, Environment and Planning, B 5 (1978), 31-43.
F. Harary, L. March and R. W. Robinson, On enumerating certain design problems in terms of bicolored graphs with no isolates, Environment and Planning B: Urban Analytics and City Science, 5 (1978), 31-43. [Annotated scanned copy]

Column k=4 of A056152.

Cf. A024206, A055609, A054976, A048291.

Vec((G(4, x) - G(3, x))*(1 - x) + O(x^30)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

Terms a(21) and beyond from Andrew Howroyd, Mar 25 2020

A055083 Number of 5 X n binary matrices with no zero rows or columns, up to row and column permutation.

Original entry on oeis.org

1, 11, 91, 633, 3835, 20755, 102089, 461272, 1930310, 7534742, 27602968, 95428291, 312864361, 976985630, 2917175450, 8357692894, 23046527311, 61337188725, 157950527167, 394427897066, 957058104818, 2260601179661, 5206447640059, 11709619965923, 25752660738209

Offset: 1

Vladeta Jovovic, Jun 13 2000

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Column k=5 of A056152.

Cf. A024206, A055609, A054976, A048291.

Vec((G(5, x) - G(4, x))*(1 - x) + O(x^30)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

Terms a(21) and beyond from Andrew Howroyd, Mar 25 2020

A283500 Triangle read by rows: T(n,k) = number of n X n (0,1) matrices with at most k 1's in each row or column.

Original entry on oeis.org

2, 7, 16, 34, 265, 512, 209, 7343, 41503, 65536, 1546, 304186, 6474726, 24997921, 33554432, 13327, 17525812, 1709852332, 21252557377, 57366997447, 68719476736, 130922, 1336221251, 702998475376, 34215495252681, 252540841305558, 505874809287625

Offset: 1

R. J. Mathar, Mar 09 2017

			Triangle begins:
2;
7,     16;
34,    265,      512;
209,   7343,     41503,      65536;
1546,  304186,   6474726,    24997921,    33554432;
13327, 17525812, 1709852332, 21252557377, 57366997447, 68719476736;
...

Andrew Howroyd, Table of n, a(n) for n = 1..84

Cf. A002720 (column k=1), A197458 (column k=2), A008300 (exactly k 1s).
Main diagonal and first lower diagonal give: A002416, A048291.
Cf. A247158 (k=n/2).

A116507 Number of singular n X n rational {0,1}-matrices with no zero rows or columns.

Original entry on oeis.org

0, 1, 91, 18943, 12483601, 28530385447, 235529139302185, 7183142489571818623

Offset: 1

Vladeta Jovovic, Apr 03 2006

Cf. A000410, A116506, A116527, A116532.

a(n) = A048291(n) - A055165(n).

A230879 Number of 2-packed n X n matrices.

Original entry on oeis.org

1, 2, 56, 16064, 39156608, 813732073472, 147662286695991296, 237776857718965784182784, 3425329990022686416530808209408, 443021337239562368918979788606843912192, 515203019085226443540506018909263027730003787776

Offset: 0

N. J. A. Sloane, Nov 09 2013

nonn

A k-packed matrix of size n X n is a matrix with entries in the alphabet A_k = {0,1, ..., k} such that each row and each column contains at least one nonzero entry.

Andrew Howroyd, Table of n, a(n) for n = 0..30
H. Cheballah, S. Giraudo, R. Maurice, Combinatorial Hopf algebra structure on packed square matrices, arXiv preprint arXiv:1306.6605 [math.CO], 2013.

Row sums of A230878.

Cf. A048291, A055599, A230880, A104602.

p[k_, n_] := Sum[(-1)^(i + j)*Binomial[n, i]*Binomial[n, j]*(k + 1)^(i*j), {i, 0, n}, {j, 0, n}];
a[n_] := p[2, n];
Table[a[n], {n, 0, 10}] (* Jean-François Alcover, Oct 08 2017, translated from PARI *)

\\ here p(k,n) is number of k-packed matrices of size n.
p(k,n)={sum(i=0, n, sum(j=0, n, (-1)^(i+j) * binomial(n,i) * binomial(n,j) * (k+1)^(i*j)))}
a(n) = p(2,n); \\ Andrew Howroyd, Sep 20 2017

Cheballah et al. give an explicit formula.

a(n) = Sum_{i=0..n} Sum_{j=0..n} (-1)^(i+j) * binomial(n,i) * binomial(n,j) * 3^(i*j). - Andrew Howroyd, Sep 20 2017

Terms a(7) and beyond from Andrew Howroyd, Sep 20 2017

A230880 Number of 2-packed matrices with exactly n nonzero entries.

Original entry on oeis.org

1, 2, 8, 80, 1120, 20544, 463744, 12422656, 384947200, 13541822464, 533049493504, 23210958688256, 1107652218822656, 57482801016422400, 3223015475535380480, 194157345516262588416, 12505948470244176953344, 857670052436844788318208, 62395270194815987194789888

Offset: 0

N. J. A. Sloane, Nov 09 2013

nonn

A k-packed matrix of size n X n is a matrix with entries in the alphabet A_k = {0,1, ..., k} such that each row and each column contains at least one nonzero entry.

Andrew Howroyd, Table of n, a(n) for n = 0..100
H. Cheballah, S. Giraudo, R. Maurice, Combinatorial Hopf algebra structure on packed square matrices, arXiv preprint arXiv:1306.6605 [math.CO], 2013.

Cf. A048291, A055599, A230878, A230879, A104602.

b[n_] := Sum[StirlingS1[n, k]*Sum[(m!)^2*StirlingS2[k, m]^2, {m, 0, k}], {k, 0, n}]/n!;
a[n_] := 2^n*b[n];
Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Oct 08 2017, translated from PARI *)

\\ here b(n) is A104602.
b(n) = {sum(m=0, n, sum(k=0, n, stirling(n,k,1) * m!^2 * stirling(k,m,2)^2)) / n!}
a(n) = 2^n * b(n); \\ Andrew Howroyd, Sep 20 2017

Cheballah et al. give an explicit formula.
From Andrew Howroyd, Sep 20 2017: (Start)
a(n) = Sum_{r=1..n} Sum_{i=0..r} Sum_{j=0..r} (-1)^(i+j) * binomial(r,i) * binomial(r,j) * binomial(i*j,n) * 2^n.
a(n) = 2^n * A104602(n).
(End)

Terms a(9) and beyond from Andrew Howroyd, Sep 20 2017

A377649 Number of edge cuts in the complete bipartite graph K_n,n.

Original entry on oeis.org

1, 11, 307, 29219, 9874531, 12425270531, 60192210392707, 1137427102035774659, 84343238614611474677731, 24650360937055503837110148611, 28488029177253725394061756995395587, 130493124785564166325712467713764904289859, 2373201513573386990964332212910033418138729872611

Offset: 1

Eric W. Weisstein, Nov 03 2024

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
Eric Weisstein's World of Mathematics, Edge Cut.

Cf. A005333, A048291 (edge covers), A379215.

a(n) = 2^(n^2) - A005333(n). - Andrew Howroyd, Dec 18 2024

a(6) onwards from Andrew Howroyd, Dec 18 2024

A122801 Number of labeled bipartite graphs on 2n vertices having equal parts and no isolated vertices.

Original entry on oeis.org

1, 1, 21, 2650, 1452605, 3149738046, 26503552820514, 868081172737564500, 111606080497500509325405, 56762846667123360827351083510, 114847831981827229530824587617895286, 927685362544629192461621864598358779955500, 29976424929810726580224613882836823991388901138994

Offset: 0

Max Alekseyev, Sep 11 2006

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50

Cf. A122802, A048291, A052332, A001831, A002031, A047863, A001700.

{ A122801(n) = binomial(2*n-1,n) * sum(k=0, n, binomial(n, k) * (-1)^k * (2^(n-k)-1)^n ); }

For n>0, a(n) = A001700(n-1) * A048291(n) = A052332(2n) - A122802(2n).

Terms a(11) and beyond from Andrew Howroyd, Nov 07 2019

cp's OEIS Frontend

A173403 Inverse binomial transform of A002416.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A321615 Triangle read by rows: T(n,k) is the number of k X k integer matrices with sum of elements n, with no zero rows or columns, up to row and column permutation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A055082 Number of 4 X n binary matrices with no zero rows or columns, up to row and column permutation.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A055083 Number of 5 X n binary matrices with no zero rows or columns, up to row and column permutation.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A283500 Triangle read by rows: T(n,k) = number of n X n (0,1) matrices with at most k 1's in each row or column.

Views

Author

Keywords

Examples

Links

Crossrefs

A116507 Number of singular n X n rational {0,1}-matrices with no zero rows or columns.

Views

Author

Keywords

Crossrefs

Formula

A230879 Number of 2-packed n X n matrices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A230880 Number of 2-packed matrices with exactly n nonzero entries.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula