login
A368924
Triangle read by rows where T(n,k) is the number of labeled loop-graphs on n vertices with k loops and n-k non-loops such that it is possible to choose a different vertex from each edge.
12
1, 0, 1, 0, 2, 1, 1, 9, 6, 1, 15, 68, 48, 12, 1, 222, 720, 510, 150, 20, 1, 3670, 9738, 6825, 2180, 360, 30, 1, 68820, 159628, 110334, 36960, 6895, 735, 42, 1, 1456875, 3067320, 2090760, 721560, 145530, 17976, 1344, 56, 1, 34506640, 67512798, 45422928, 15989232, 3402756, 463680, 40908, 2268, 72, 1
OFFSET
0,5
COMMENTS
The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
Wikipedia, Axiom of choice.
FORMULA
E.g.f.: A(x,y) = exp(-log(1-T(x))/2 - T(x)/2 + y*T(x) - T(x)^2/4) where T(x) = -LambertW(-x) is the e.g.f. of A000169. - Andrew Howroyd, Jan 14 2024
EXAMPLE
Triangle begins:
1
0 1
0 2 1
1 9 6 1
15 68 48 12 1
222 720 510 150 20 1
3670 9738 6825 2180 360 30 1
68820 159628 110334 36960 6895 735 42 1
Row n = 3 counts the following loop-graphs:
{{1,2},{1,3},{2,3}} {{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},{3},{1,2}}
{{2},{1,2},{1,3}} {{1},{3},{2,3}}
{{2},{1,2},{2,3}} {{2},{3},{1,2}}
{{2},{1,3},{2,3}} {{2},{3},{1,3}}
{{3},{1,2},{1,3}}
{{3},{1,2},{2,3}}
{{3},{1,3},{2,3}}
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {1, 2}], {n}], Count[#, {_}]==k&&Length[Select[Tuples[#], UnsameQ@@#&]]!=0&]], {n, 0, 5}, {k, 0, n}]
PROG
(PARI) T(n)={my(t=-lambertw(-x + O(x*x^n))); [Vecrev(p) | p <- Vec(serlaplace(exp(-log(1-t)/2 - t/2 + t*y - t^2/4)))]}
{ my(A=T(8)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Jan 14 2024
CROSSREFS
Column k = n-1 is A002378.
The case of a unique choice is A061356, row sums A000272.
Column k = 0 is A137916, unlabeled version A137917.
Row sums appear to be A333331.
The complement has row sums A368596, covering case A368730.
The unlabeled version is A368926.
Without the choice condition we have A368928, A116508, A367863, A368597.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A014068 counts loop-graphs, unlabeled A000666.
Sequence in context: A016540 A132620 A156883 * A019803 A214506 A246664
KEYWORD
nonn,tabl
AUTHOR
Gus Wiseman, Jan 10 2024
EXTENSIONS
a(36) onwards from Andrew Howroyd, Jan 14 2024
STATUS
approved