A116539 -id:A116539

A255906

Number of collections of nonempty multisets with a total of n objects having color set {1,...,k} for some k<=n.

+10
87

1, 1, 4, 16, 76, 400, 2356, 15200, 106644, 806320, 6526580, 56231024, 513207740, 4941362512, 50013751812, 530481210672, 5880285873060, 67954587978448, 816935340368068, 10196643652651664, 131904973822724540, 1765645473517011568, 24420203895517396180

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

Number of multiset partitions of normal multisets of size n, where a multiset is normal if it spans an initial interval of positive integers. - Gus Wiseman, Jul 30 2018

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..300

FORMULA

a(n) = Sum_{k=0..n} A255903(n,k).

EXAMPLE

a(0) = 1: {}.

a(1) = 1: {{1}}.

a(2) = 4: {{1},{1}}, {{1,1}}, {{1},{2}}, {{1,2}}.

a(3) = 16: {{1},{1},{1}}, {{1},{1,1}}, {{1,1,1}}, {{1},{1},{2}}, {{1},{2},{2}}, {{1},{1,2}}, {{1},{2,2}}, {{2},{1,1}}, {{2},{1,2}}, {{1,1,2}}, {{1,2,2}}, {{1},{2},{3}}, {{1},{2,3}}, {{2},{1,3}}, {{3},{1,2}}, {{1,2,3}}.

MATHEMATICA

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];

mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

allnorm[n_]:=Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1];

Table[Length[Join@@mps/@allnorm[n]], {n, 6}] (* Gus Wiseman, Jul 30 2018 *)

PROG

(PARI)

R(n, k)={Vec(-1 + 1/prod(j=1, n, (1 - x^j + O(x*x^n))^binomial(k+j-1, j) ))}

seq(n) = {concat([1], sum(k=1, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) ))} \\ Andrew Howroyd, Sep 23 2023

CROSSREFS

Row sums of A255903. Also row sums of A317532.

Cf. A007716, A034691, A116539, A317073.

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Mar 10 2015

STATUS

approved

A322661

Number of graphs with loops spanning n labeled vertices.

+10
68

1, 1, 5, 45, 809, 28217, 1914733, 254409765, 66628946641, 34575388318705, 35680013894626133, 73392583417010454429, 301348381381966079690489, 2471956814761996896091805993, 40530184362443281653842556898237, 1328619783326799871943604598592805525

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

The span of a graph is the union of its edges.

LINKS

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

FORMULA

Exponential transform of A062740, if we assume A062740(1) = 1.

Inverse binomial transform of A006125(n+1) = 2^binomial(n+1,2).

EXAMPLE

The a(2) = 5 edge-sets:

{{1,1},{1,2}}

{{1,1},{2,2}}

{{1,2},{2,2}}

{{1,1},{1,2},{2,2}}

MATHEMATICA

Table[Sum[(-1)^(n-k)*Binomial[n, k]*2^Binomial[k+1, 2], {k, 0, n}], {n, 10}]

(* second program *)

Table[Select[Expand[Product[1+x[i]*x[j], {j, n}, {i, j}]], And@@Table[!FreeQ[#, x[i]], {i, n}]&]/.x[_]->1, {n, 7}]

PROG

(PARI) a(n) = sum(k=0, n, (-1)^(n-k)*binomial(n, k)*2^binomial(k+1, 2)) \\ Andrew Howroyd, Jan 06 2024

CROSSREFS

Cf. A000666, A006125, A006129 (loops not allowed), A054921, A062740, A116539, A320461, A322635, A048291 (for directed edgs).

KEYWORD

nonn

AUTHOR

Gus Wiseman, Dec 22 2018

STATUS

approved

A295193

Number of regular simple graphs on n labeled nodes.

+10
32

1, 2, 2, 8, 14, 172, 932, 45936, 1084414, 155862512, 10382960972, 6939278572096, 2203360500122300, 4186526756621772344, 3747344008241368443820, 35041787059691023579970848, 156277111373303386104606663422, 4142122641757598618318165240180096

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

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

E. A. Bender and E. R. Canfield, The asymptotic number of labeled graphs with given degree sequences, Journal of Combinatorial Theory, Series A, 24 (1978), 296-307.

Andrew Howroyd, PARI Program

Atabey Kaygun, Enumerating Labeled Graphs that Realize a Fixed Degree Sequence, arXiv:2101.02299 [math.CO], 2021.

B. D. McKay, Applications of a technique for labelled enumeration, Congress. Numerantium, 40 (1983), 207-221.

Wikipedia, Regular graph

EXAMPLE

From Gus Wiseman, Dec 19 2018: (Start)

A graph is regular if all vertices have the same degree. For example, the a(4) = 8 simple regular graphs are:

1 2

3 4

.

4---1 3---1 2---1

3---2 4---2 4---3

.

3---4 4---3 4---2

| | | | | |

1---2 1---2 1---3

.

4---3

| X |

2---1

(End)

MATHEMATICA

Table[Sum[SeriesCoefficient[Product[1+Times@@x/@s, {s, Subsets[Range[n], {2}]}], Sequence@@Table[{x[i], 0, k}, {i, n}]], {k, 0, n-1}], {n, 1, 9}] (* Gus Wiseman, Dec 19 2018 *)

PROG

(PARI) \\ See link for program file.

for(n=1, 10, print1(A295193(n), ", ")) \\ Andrew Howroyd, Aug 28 2019

CROSSREFS

Row sums of A059441.

Cf. A005176 (unlabeled equivalent), A058891, A116539, A299353, A306017, A306021, A319189, A319190, A319612, A319729.

KEYWORD

nonn

AUTHOR

Álvar Ibeas, Nov 16 2017

EXTENSIONS

a(16)-a(18) from Andrew Howroyd, Aug 28 2019

STATUS

approved

A319190

Number of regular hypergraphs spanning n vertices.

+10
20

1, 1, 3, 19, 879, 5280907, 1069418570520767

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

We define a hypergraph to be any finite set of finite nonempty sets. A hypergraph is regular if all vertices have the same degree. The span of a hypergraph is the union of its edges.

LINKS

Table of n, a(n) for n=0..6.

EXAMPLE

The a(3) = 19 regular hypergraphs:

{{1},{2,3}}

{{2},{1,3}}

{{3},{1,2}}

{{1},{2},{3}}

{{1},{2,3},{1,2,3}}

{{2},{1,3},{1,2,3}}

{{3},{1,2},{1,2,3}}

{{1,2},{1,3},{2,3}}

{{1},{2},{3},{1,2,3}}

{{1},{2},{1,3},{2,3}}

{{1},{3},{1,2},{2,3}}

{{2},{3},{1,2},{1,3}}

{{1,2},{1,3},{2,3},{1,2,3}}

{{1},{2},{1,3},{2,3},{1,2,3}}

{{1},{3},{1,2},{2,3},{1,2,3}}

{{2},{3},{1,2},{1,3},{1,2,3}}

{{1},{2},{3},{1,2},{1,3},{2,3}}

{{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

MATHEMATICA

Table[Sum[SeriesCoefficient[Product[1+Times@@x/@s, {s, Subsets[Range[n], {1, n}]}], Sequence@@Table[{x[i], 0, k}, {i, n}]], {k, 1, 2^n}], {n, 5}]

CROSSREFS

Column sums of A188445.

Cf. A002829, A005176, A049311, A058891, A110100, A110101, A116539, A283877, A295193, A306017, A319189.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Dec 17 2018

EXTENSIONS

a(6) from Andrew Howroyd, Mar 12 2020

STATUS

approved

A181230

Square array T(m,n) giving the number of m X n (0,1)-matrices with pairwise distinct rows and pairwise distinct columns.

+10
18

2, 2, 2, 0, 10, 0, 0, 24, 24, 0, 0, 24, 264, 24, 0, 0, 0, 1608, 1608, 0, 0, 0, 0, 6720, 33864, 6720, 0, 0, 0, 0, 20160, 483840, 483840, 20160, 0, 0, 0, 0, 40320, 5644800, 19158720, 5644800, 40320, 0, 0, 0, 0, 40320, 57415680, 595506240, 595506240, 57415680, 40320

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

Table starts

.2..2.....0...........0...............0..................0

.2.10....24..........24...............0..................0

.0.24...264........1608............6720..............20160

.0.24..1608.......33864..........483840............5644800

.0..0..6720......483840........19158720..........595506240

.0..0.20160.....5644800.......595506240........44680224960

.0..0.40320....57415680.....16388749440......2881362718080

.0..0.40320...518676480....418910083200....172145618789760

.0..0.....0..4151347200..10136835072000...9841604944066560

.0..0.....0.29059430400.233811422208000.546156941728204800

LINKS

R. H. Hardin, Table of n, a(n) for n=1..180

MathOverflow, Number of matrices with no repeated columns or rows

FORMULA

T(m,n) = Sum_{i=0..n} Sum_{j=0..m} stirling1(n,i) * stirling1(m,j) * 2^(i*j) = n! * Sum_{j=0..m} stirling1(m,j) * binomial(2^j,n) = m! * Sum_{i=0..n} stirling1(n,i) * binomial(2^i,m). - Max Alekseyev, Jun 18 2016

T(m,n) = A059084(m,n) * n!.

CROSSREFS

Cf. A088310 (diagonal), A181231, A181232, A181233 (subdiagonals).

Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763

KEYWORD

nonn,tabl

AUTHOR

R. H. Hardin Oct 10 2010

STATUS

approved

A059202

Triangle T(n,m) of numbers of m-block T_0-covers of a labeled n-set, m = 0..2^n - 1.

+10
17

1, 0, 1, 0, 0, 3, 1, 0, 0, 3, 29, 35, 21, 7, 1, 0, 0, 0, 140, 1015, 2793, 4935, 6425, 6435, 5005, 3003, 1365, 455, 105, 15, 1, 0, 0, 0, 420, 13965, 126651, 661801, 2533135, 7792200, 20085000, 44307120, 84651840, 141113700, 206251500, 265182300

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,6

COMMENTS

A cover of a set is a T_0-cover if for every two distinct points of the set there exists a member (block) of the cover containing one but not the other point.

Also, T(n,m) is the number of n X m (0,1)-matrices with pairwise distinct nonzero columns and pairwise distinct nonzero rows, up to permutation of columns.

LINKS

Robert Israel, Table of n, a(n) for n = 0..4094 (rows 0 to 11, flattened).

T_0-covers of a labeled 3-set

FORMULA

T(n, m) = (1/m!)*Sum_{1..m + 1} stirling1(m + 1, i)*[2^(i - 1) - 1]_n, where [k]_n := k*(k - 1)*...*(k - n + 1), [k]_0 = 1.

E.g.f: Sum((1+x)^(2^n-1)*log(1+y)^n/n!, n=0..infinity)/(1+y). - Vladeta Jovovic, May 19 2004

Also T(n, m) = Sum_{i=0..n} Stirling1(n+1, i+1)*binomial(2^i-1, m). - Vladeta Jovovic, Jun 04 2004

T(n,m) = A181230(n,m)/m! - n*T(n-1,m) - T(n,m-1) - n*T(n-1,m-1). - Max Alekseyev, Dec 11 2017

EXAMPLE

[1],

[0,1],

[0,0,3,1],

[0,0,3,29,35,21,7,1],

...

There are 35 4-block T_0-covers of a labeled 3-set.

MAPLE

with(combinat): for n from 0 to 10 do for m from 0 to 2^n-1 do printf(`%d, `, (1/m!)*sum(stirling1(m+1, i)*product(2^(i-1)-1-j, j=0..n-1), i=1..m+1)) od: od:

MATHEMATICA

T[n_, m_] = Sum[ StirlingS1[n + 1, i + 1]*Binomial[2^i - 1, m], {i, 0, n}]; Table[T[n, m], {n, 0, 5}, {m, 0, 2^n - 1}] (* G. C. Greubel, Dec 28 2016 *)

CROSSREFS

Cf. A059201 (row sums), A059203 (column sums), A094000 (main diagonal).

Cf. A059084, A059085, A059086, A059087, A059088, A059089, A181230.

Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763

KEYWORD

easy,nonn,tabf

AUTHOR

Vladeta Jovovic, Goran Kilibarda, Jan 18 2001

EXTENSIONS

More terms from James A. Sellers, Jan 24 2001

STATUS

approved

A088310

Number of n X n (0,1)-matrices with all rows distinct and all columns distinct.

+10
17

1, 2, 10, 264, 33864, 19158720, 44680224960, 413586858182400, 14960200449325582080, 2109063823453947981680640, 1162864344149083760773678387200, 2520991223487759548686737154649702400, 21598422878151131130336454273775859841843200, 734233037731110118818452425552296701963294284185600

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

LINKS

G. C. Greubel, Table of n, a(n) for n = 0..57

FORMULA

a(n) = n! * Sum_{k=0..n} Stirling1(n, k)*binomial(2^k, n). - Vladeta Jovovic, Nov 07 2003

a(n) = Sum_{i=0..n} Sum_{j=0..n} stirling1(n, i) * stirling1(n, j) * 2^(i*j). - Max Alekseyev, Nov 07 2003

a(n) ~ 2^(n^2). - Vaclav Kotesovec, Jul 02 2016

a(n) = A181230(n,n).

EXAMPLE

a(2) = 10: 00/01, 00/10, 01/00, 01/10, 01/11, 10/00, 10/01, 10/11, 11/01, 11/10.

MATHEMATICA

Table[n!*Sum[StirlingS1[n, k]*Binomial[2^k, n], {k, 0, n}], {n, 0, 15}] (* Vaclav Kotesovec, Jul 02 2016 *)

PROG

(Magma)

A088310:= func< n | Factorial(n)*(&+[Binomial(2^k, n)*StirlingFirst(n, k): k in [0..n]]) >;

[A088310(n): n in [0..30]]; // G. C. Greubel, Dec 14 2022

(SageMath)

@CachedFunction

def A088310(n): return (-1)^n*factorial(n)*sum((-1)^k*binomial(2^k, n)*stirling_number1(n, k) for k in (0..n))

[A088310(n) for n in range(31)] # G. C. Greubel, Dec 14 2022

CROSSREFS

Cf. A088229, A088309.

Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Nov 07 2003

EXTENSIONS

Suggested by Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 06 2003

a(0)-a(5) from W. Edwin Clark, Nov 07 2003

STATUS

approved

A116532

Number of singular n X n rational {0,1}-matrices with no zero rows or columns and with all rows distinct, up to permutation of rows.

+10
17

0, 0, 3, 285, 50820, 23551920, 31898503077, 134251404794199

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

LINKS

Table of n, a(n) for n=1..8.

FORMULA

a(n) = A054780(n) - A088389(n).

CROSSREFS

Cf. A000410, A116506, A116527.

Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763

KEYWORD

more,nonn

AUTHOR

Vladeta Jovovic, Apr 03 2006

STATUS

approved

A094000

Number of n X n (0,1)-matrices with no zero rows or columns and with all rows distinct and all columns distinct, up to permutation of rows.

+10
16

1, 1, 3, 29, 1015, 126651, 53354350, 74698954306, 350688201987402, 5624061753186933530, 314512139441575825493524, 62498777166571927258267336860, 44831219113504221199415663547412096

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

Main diagonal of A059202.

REFERENCES

G. Kilibarda and V. Jovovic, "Enumeration of some classes of T_0-hypergraphs", in

LINKS

G. C. Greubel, Table of n, a(n) for n = 0..59

Goran Kilibarda and Vladeta Jovovic, Enumeration of some classes of T_0-hypergraphs, arXiv:1411.4187 [math.CO], 2014.

FORMULA

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

a(n) ~ binomial(2^n,n). - Vaclav Kotesovec, Mar 18 2014

MATHEMATICA

f[n_] := Sum[ StirlingS1[n + 1, k] Binomial[2^(k - 1) - 1, n], {k, 0, n + 1}]; Table[ f[n], {n, 0, 12}] (* Robert G. Wilson v, Jun 01 2004 *)

PROG

(PARI) a(n) = sum(k=0, n+1, stirling(n+1, k, 1)*binomial(2^(k-1)-1, n)); \\ Michel Marcus, Dec 17 2022

CROSSREFS

Cf. A048291, A059202, A088309.

Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763

KEYWORD

nonn,easy

AUTHOR

Goran Kilibarda and Vladeta Jovovic, May 30 2004

EXTENSIONS

More terms from Robert G. Wilson v, Jun 01 2004

STATUS

approved

A088309

Number of equivalence classes of n X n (0,1)-matrices with all rows distinct and all columns distinct.

+10
15

1, 2, 5, 44, 1411, 159656, 62055868, 82060884560, 371036717493194, 5812014504668066528, 320454239459072905856944, 63156145369562679089674952768, 45090502574837184532027563736271152, 117910805393665959622047902193019284914432, 1139353529410754170844431642119963019965901238144

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

Two such matrices are equivalent if they differ just by a permutation of the rows.

LINKS

G. C. Greubel, Table of n, a(n) for n = 0..59

G. Kilibarda and V. Jovovic, Enumeration of some classes of T_0-hypergraphs, arXiv:1411.4187 [math.CO], 2014.

FORMULA

a(n) = Sum_{k=0..n} Stirling1(n, k)*binomial(2^k, n). - Vladeta Jovovic, Nov 07 2003

a(n) = A088310(n) / n!.

EXAMPLE

a(2) = 5: 00/01, 00/10, 01/10, 01/11, 10/11.

MATHEMATICA

A088309[n_]:= A088309[n]=Sum[Binomial[2^j, n]*StirlingS1[n, j], {j, 0, n}];

Table[A088309[n], {n, 0, 30}] (* G. C. Greubel, Dec 15 2022 *)

PROG

(Magma)

A088309:= func< n | (&+[Binomial(2^k, n)*StirlingFirst(n, k): k in [0..n]]) >;

[A088309(n): n in [0..30]]; // G. C. Greubel, Dec 15 2022

(SageMath)

@CachedFunction

def A088309(n): return (-1)^n*sum((-1)^k*binomial(2^k, n)*stirling_number1(n, k) for k in (0..n))

[A088309(n) for n in range(31)] # G. C. Greubel, Dec 15 2022

(PARI) a(n) = sum(k=0, n, stirling(n, k, 1)*binomial(2^k, n)); \\ Michel Marcus, Dec 16 2022

CROSSREFS

Cf. A088229, A088310, A088616.

Main diagonal of A059084.

Binary matrices with distinct rows and columns, various versions: A059202, this sequence, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763.

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Nov 07 2003

EXTENSIONS

Suggested by Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 06 2003

a(0)-a(5) from W. Edwin Clark, Nov 07 2003

STATUS

approved