A003087 -id:A003087

Search: a003087 -id:a003087

Displaying 21-23 of 23 results found.

page 1 2 3

A350448

Triangle read by rows: T(n,k) is the number of acyclic graphs on n unlabeled nodes whose longest directed path has k arcs.

+10
2

1, 1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 8, 14, 8, 0, 1, 20, 89, 128, 64, 0, 1, 55, 634, 1934, 2336, 1024, 0, 1, 163, 5668, 36428, 83648, 84992, 32768, 0, 1, 556, 67926, 959718, 3919584, 7097088, 6144000, 2097152, 0, 1, 2222, 1137641, 37205922, 268989920, 793138688, 1175224320, 880803840, 268435456, 0

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

OFFSET

0,8

LINKS

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

EXAMPLE

Triangle begins:

1, 0;

1, 1, 0;

1, 3, 2, 0;

1, 8, 14, 8, 0;

1, 20, 89, 128, 64, 0;

1, 55, 634, 1934, 2336, 1024, 0;

1, 163, 5668, 36428, 83648, 84992, 32768, 0;

...

PROG

(PARI) \\ See PARI link in A122078 for program code.

{ my(T=AcyclicDigraphsByLongestPath(8)); for(n=1, #T, print(T[n])) }

CROSSREFS

Row sums are A003087.

Diagonals include A000007, A006125.

Cf. A122078.

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Dec 31 2021

STATUS

approved

A368602

Triangle read by rows where T(n,k) is the number of labeled acyclic digraphs on {1..n} with sinks {1..k}.

+10
2

1, 0, 1, 0, 1, 1, 0, 5, 3, 1, 0, 79, 33, 7, 1, 0, 3377, 1071, 161, 15, 1, 0, 362431, 92289, 10591, 705, 31, 1, 0, 93473345, 19856703, 1832705, 93375, 2945, 63, 1, 0, 56272471039, 10249747713, 789619327, 32382465, 782719, 12033, 127, 1

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

OFFSET

0,8

COMMENTS

Also the number of set-systems with n vertices and n edges such that {i} is a singleton edge iff i <= k, and such that there is only one way to choose a different vertex from each edge.

LINKS

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

FORMULA

T(n,k) = A361718(n,k)/binomial(n,k).

EXAMPLE

Triangle begins:

0 1

0 1 1

0 5 3 1

0 79 33 7 1

0 3377 1071 161 15 1

...

Row n = 3 counts the following set-systems:

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

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

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

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

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

MATHEMATICA

Table[Length[Select[Subsets[Subsets[Range[n]], {n}], Union@@Cases[#, {_}]==Range[k] && Length[Select[Tuples[#], UnsameQ@@#&]]==1&]], {n, 0, 3}, {k, 0, n}]

CROSSREFS

Column k = n-1 is A000225 = A058877(n)/n.

Column k = 1 is A134531 (up to sign) or A003025(n)/n, non-fixed A350415.

For any choice of k sinks we get A361718.

A058891 counts set-systems, unlabeled A000612.

A059201 counts covering T_0 set-systems.

A323818 counts covering connected set-systems, unlabeled A323819.

Cf. A000169, A003024, A003087, A082402, A088957, A334282, A367862, A367904, A367908, A368600, A368601.

KEYWORD

nonn,tabl

AUTHOR

Gus Wiseman, Jan 02 2024

EXTENSIONS

More terms from Alois P. Heinz, Jan 04 2024

STATUS

approved

A361589

Number of acyclic digraphs on n unlabeled nodes without isolated nodes.

+10
1

1, 0, 1, 4, 25, 271, 5682, 237684, 20042357, 3404651985, 1162523674892, 796395726736678, 1093229314594543016, 3004753338859186373234, 16527845763725396055765240, 181891586856152393087373330332, 4004313490358484085907684748704180, 176328671349936542115174881107633828418

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

OFFSET

0,4

LINKS

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

FORMULA

a(n) = A003087(n) - A003087(n-1) for n >= 1.

PROG

(PARI) A361589seq(16) \\ See PARI link in A350794 for program code.

CROSSREFS

Row sums of A361588.

Cf. A003087, A350794.

KEYWORD

nonn

AUTHOR

Andrew Howroyd, Mar 16 2023

STATUS

approved

page 1 2 3

Search completed in 0.030 seconds