A111924 -id:A111924 - cp's OEIS frontend

A369146 Number of unlabeled loop-graphs with up to n vertices such that it is not possible to choose a different vertex from each edge (non-choosable).

0, 0, 1, 8, 60, 471, 4911, 78797, 2207405, 113740613, 10926218807, 1956363413115, 652335084532025, 405402273420833338, 470568642161119515627, 1023063423471189429817807, 4178849203082023236054797465, 32168008290073542372004072630072, 468053896898117580623237189882068990

Offset: 0

Gus Wiseman, Jan 22 2024

nonn

			The a(0) = 0 through a(3) = 8 loop-graphs (loops shown as singletons):
  .  .  {{1},{2},{1,2}}  {{1},{2},{1,2}}
                         {{1},{2},{3},{1,2}}
                         {{1},{2},{1,2},{1,3}}
                         {{1},{2},{1,3},{2,3}}
                         {{1},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3}}
                         {{1},{2},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3},{2,3}}

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

Without the choice condition we have A000666, labeled A006125 (shifted).
For a unique choice we have A087803, labeled A088957.
The case without loops is A140637, labeled A367867 (covering A367868).
For exactly n edges we have A368835, labeled A368596.
The labeled complement is A368927, covering A369140.
The labeled version is A369141, covering A369142.
The complement is counted by A369145, covering A369200.
The covering case is A369147.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A129271 counts connected choosable simple graphs, unlabeled A005703.
A322661 counts labeled covering loop-graphs, unlabeled A322700.
Cf. A000088, A000612, A006649, A062740, A134964, A137917, A140638, A368600, A368984, A369199.

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]}, {i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n],{1,2}]], Select[Tuples[#],UnsameQ@@#&]=={}&]]],{n,0,4}]

Partial sums of A369147.

a(n) = A000666(n) - A369145(n). - Andrew Howroyd, Feb 02 2024

a(6) onwards from Andrew Howroyd, Feb 02 2024

A130757 Triangular table of coefficients of Laguerre-Sonin polynomials n!2^nLag(n,x/2,1/2) of order 1/2.

Original entry on oeis.org

1, 3, -1, 15, -10, 1, 105, -105, 21, -1, 945, -1260, 378, -36, 1, 10395, -17325, 6930, -990, 55, -1, 135135, -270270, 135135, -25740, 2145, -78, 1, 2027025, -4729725, 2837835, -675675, 75075, -4095, 105, -1, 34459425, -91891800, 64324260, -18378360, 2552550, -185640, 7140, -136

Offset: 0

Wolfdieter Lang, Jul 13 2007

These polynomials appear in the radial l=0 (s) wave functions of the isotropic three-dimensional harmonic quantum oscillator with the dimensionless variable x=(r/L)^2 with r>=0 and L^2=h/(m*f0). h is Planck's constant and m and f0 are the mass and the frequency of the oscillator.
From Tom Copeland, Dec 13 2015: (Start)
See A099174 for relations to the Hermite polynomials and the link in A176230 for operator relations. The infinitesimal generator for this matrix contains A014105.
The row polynomials are P(n,x) = 2^n n! Lag(n,x/2,1/2), where Lag(n,x,q) is the associated Laguerre polynomial of order q, with raising operator R = -x^(-2) [x^(3/2) (1 - 2D)]^2 = 3 - x + (4x - 6) D - 4x D^2 with D = d/dx, i.e., R P(n,x) - P(n+1,x). A matrix reresentation of R acting on an o.g.f. (formal power series) is given by the transpose of the production matrix below. The diagonal corresponds to (3 + 4 xD) x^n = (3 + 4n) x^n; the upper diagonal, to -x x^n = -x^(n+1); and the lower diagonal, to (-6 - 4 xD) D x^n = -n (6 + 4(n-1)) x^(n-1), the sequence A002943. See A176230 for a similar relation.
The triangles of Bessel numbers entries A122848, A049403, A096713, A104556 contain these polynomials as even or odd rows. Also the aerated version A099174 and A066325. Reversed, these entries are A100861, A144299, A111924.
(End)
Exponential Riordan array [1/(1-2x)^(3/2), -x/(1-2x)]. - Paul Barry, Mar 07 2017

			[1]; [3,-1]; [15,-10,1]; [105,-105,21,-1]; [945,-1260,378,-36,1]; ...

Robert Israel, Table of n, a(n) for n = 0..10010 (rows 0 to 140, flattened)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972, p. 775, 22.3.9.
T. Copeland, Juggling Zeros in the Matrix: Example II, 2020.
Wolfdieter Lang, First ten rows and more.

Cf. A021009 (Coefficient table of n!*L(n, 0, x)).
Row sums (signed) give A131441. Row sums (unsigned) give A066224.
Cf. A001147, A002943, A014105, A049403, A066325, A096713, A099174, A100861, A104556, A111924, A122848, A144299, A176230.

seq(seq(n!*2^(n-m)*(-1)^m*binomial(n+1/2,n-m)/m!,m=0..n),n=0..10); # Robert Israel, Dec 25 2015

Table[n! (2^(n - m)) ((-1)^m) Binomial[n + 1/2, n - m]/m!, {n, 0, 8}, {m, 0, n}] // Flatten (* Michael De Vlieger, Dec 24 2015 *)

a(n,m) = n!*(2^(n-m))*L(1/2,n,m) with L(1/2,n,m) = ((-1)^m)*binomial(n+1/2,n-m)/m!, n >= m >= 0, otherwise 0.
Let IP be the lower triangular matrix with its first subdiagonal equal to the first subdiagonal (cf. A014105) of this entry's unsigned matrix M and with all other elements equal to zero. Then IP is the infinitesimal generator of M, i.e., M = exp(IP). - Tom Copeland, Dec 12 2015
From Tom Copeland, Dec 14 2015: (Start)
Production matrix is
   3,   -1;
  -6,    7,   -1;
   0,  -20,   11,   -1;
   0,    0,  -42,   15,   -1;
   0,    0,    0,  -72,   19,   -1;
   0,    0,    0,    0, -110,   23,   -1;
   0,    0,    0,    0,    0, -156,   27,   -1;
   0,    0,    0,    0,    0,    0, -210,   31,   -1;
   0,    0,    0,    0,    0,    0,    0, -272,   35,   -1;
  ... (End)

Title formula corrected by Tom Copeland, Dec 12 2015

A368730 Number of n-element sets of singletons or pairs of distinct elements of {1..n} with union {1..n}, or loop-graphs covering n vertices with n edges, such that it is not possible to choose a different element from each.

Original entry on oeis.org

0, 0, 0, 0, 6, 180, 4560, 117600, 3234588, 96119982, 3092585310, 107542211535, 4029055302855, 162040513972623, 6970457656110039, 319598974394563500, 15568332397812799920, 803271954062642638830, 43778508937914677872788, 2513783434620146896920843

Offset: 0

Gus Wiseman, Jan 04 2024

nonn

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.

			The a(4) = 6 set-systems:
  {{1},{2},{1,2},{3,4}}
  {{1},{3},{1,3},{2,4}}
  {{1},{4},{1,4},{2,3}}
  {{2},{3},{1,4},{2,3}}
  {{2},{4},{1,3},{2,4}}
  {{3},{4},{1,2},{3,4}}

Andrew Howroyd, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Graph Loop.
ProofWiki, Definition:Loop-Graph

The case of a unique choice appears to be A000272.
The version without the choice condition is A368597, non-covering A014068.
The complement appears to be A333331.
The non-covering case is A368596, allowing edges of any size A368600.
Allowing any number of edges of any size gives A367903, ranks A367907.
Allowing any number of non-singletons gives A367868, non-covering A367867.
A000085 counts set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A100861 counts set partitions into singletons or pairs by number of pairs.
A111924 counts set partitions into singletons or pairs by length.
A322661 counts labeled covering half-loop-graphs, connected A062740.
Cf. A000666, A116508, A133686, A367863, A367869, A367901, A368532.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}], {n}],Union@@#==Range[n] && Length[Select[Tuples[#],UnsameQ@@#&]]==0&]],{n,0,5}]

a(n) = A368596(n) + A368597(n) - A014068(n). - Andrew Howroyd, Jan 10 2024

Terms a(7) and beyond from Andrew Howroyd, Jan 10 2024

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.

Original entry on oeis.org

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

Gus Wiseman, Jan 10 2024

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.

			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}}

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

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.
Cf. A000169, A057500, A062740, A129271, A133686, A322661, A367869, A367902, A368601, A368835, A368836, A368927.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}],{n}], Count[#,{_}]==k&&Length[Select[Tuples[#], UnsameQ@@#&]]!=0&]],{n,0,5},{k,0,n}]

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

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

a(36) onwards from Andrew Howroyd, Jan 14 2024

A369145 Number of unlabeled loop-graphs with up to n vertices such that it is possible to choose a different vertex from each edge (choosable).

Original entry on oeis.org

1, 2, 5, 12, 30, 73, 185, 467, 1207, 3147, 8329, 22245, 60071, 163462, 448277, 1236913, 3432327, 9569352, 26792706, 75288346, 212249873, 600069431, 1700826842, 4831722294, 13754016792, 39224295915, 112048279650, 320563736148, 918388655873, 2634460759783, 7566000947867

Offset: 0

Gus Wiseman, Jan 22 2024

nonn

a(n) is the number of graphs with loops on n unlabeled vertices with every connected component having no more edges than vertices. - Andrew Howroyd, Feb 02 2024

			The a(0) = 1 through a(3) = 12 loop-graphs (loops shown as singletons):
  {}  {}     {}           {}
      {{1}}  {{1}}        {{1}}
             {{1,2}}      {{1,2}}
             {{1},{2}}    {{1},{2}}
             {{1},{1,2}}  {{1},{1,2}}
                          {{1},{2,3}}
                          {{1,2},{1,3}}
                          {{1},{2},{3}}
                          {{1},{2},{1,3}}
                          {{1},{1,2},{1,3}}
                          {{1},{1,2},{2,3}}
                          {{1,2},{1,3},{2,3}}

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

Without the choice condition we get A000666, labeled A006125 (shifted left).
The case of a unique choice is A087803, labeled A088957.
Without loops we have A134964, labeled A133686 (covering A367869).
For exactly n edges and no loops we have A137917, labeled A137916.
The labeled version is A368927, covering A369140.
The labeled complement is A369141, covering A369142.
For exactly n edges we have A368984, labeled A333331 (maybe).
The complement for exactly n edges is A368835, labeled A368596.
The complement is counted by A369146, labeled A369141 (covering A369142).
The covering case is A369200.
The complement for exactly n edges and no loops is A369201, labeled A369143.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A129271 counts connected choosable simple graphs, unlabeled A005703.
A322661 counts labeled covering loop-graphs, unlabeled A322700.
A367867 counts non-choosable labeled graphs, covering A367868.
A368927 counts choosable labeled loop-graphs, covering A369140.
Cf. A000088, A006649, A062740, A140638, A368924, A369194.

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]}, {i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n],{1,2}]], Length[Select[Tuples[#], UnsameQ@@#&]]!=0&]]],{n,0,4}]

Partial sums of A369200.

Euler transform of A369289. - Andrew Howroyd, Feb 02 2024

a(7) onwards from Andrew Howroyd, Feb 02 2024

A144299 Triangle of Bessel numbers read by rows. Row n gives T(n,n), T(n,n-1), T(n,n-2), ..., T(n,0) for n >= 0.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 3, 0, 0, 1, 6, 3, 0, 0, 1, 10, 15, 0, 0, 0, 1, 15, 45, 15, 0, 0, 0, 1, 21, 105, 105, 0, 0, 0, 0, 1, 28, 210, 420, 105, 0, 0, 0, 0, 1, 36, 378, 1260, 945, 0, 0, 0, 0, 0, 1, 45, 630, 3150, 4725, 945, 0, 0, 0, 0, 0, 1, 55, 990, 6930, 17325, 10395, 0, 0, 0, 0, 0, 0

Offset: 0

David Applegate and N. J. A. Sloane, Dec 06 2008

T(n,k) is the number of partitions of an n-set into k nonempty subsets, each of size at most 2.
The Grosswald and Choi-Smith references give many further properties and formulas.
Considered as an infinite lower triangular matrix T, lim_{n->infinity} T^n = A118930: (1, 1, 2, 4, 13, 41, 166, 652, ...) as a vector. - Gary W. Adamson, Dec 08 2008

			Triangle begins:
  n:
  0: 1
  1: 1  0
  2: 1  1   0
  3: 1  3   0    0
  4: 1  6   3    0   0
  5: 1 10  15    0   0  0
  6: 1 15  45   15   0  0  0
  7: 1 21 105  105   0  0  0  0
  8: 1 28 210  420 105  0  0  0  0
  9: 1 36 378 1260 945  0  0  0  0  0
  ...
The row sums give A000085.
For some purposes it is convenient to rotate the triangle by 45 degrees:
  1 0 0 0 0  0  0   0   0    0    0     0 ...
    1 1 0 0  0  0   0   0    0    0     0 ...
      1 3 3  0  0   0   0    0    0     0 ...
        1 6 15 15   0   0    0    0     0 ...
          1 10 45 105 105    0    0     0 ...
             1 15 105 420  945  945     0 ...
                1  21 210 1260 4725 10395 ...
                    1  28  378 3150 17325 ...
                        1   36  630  6930 ...
                             1   45   990 ...
  ...
The latter triangle is important enough that it has its own entry, A144331. Here the column sums give A000085 and the rows sums give A001515.
If the entries in the rotated triangle are denoted by b1(n,k), n >= 0, k <= 2n, then we have the recurrence b1(n, k) = b1(n - 1, k - 1) + (k - 1)*b1(n - 1, k - 2).
Then b1(n,k) is the number of partitions of [1, 2, ..., k] into exactly n blocks, each of size 1 or 2.

E. Grosswald, Bessel Polynomials, Lecture Notes Math., Vol. 698, 1978.

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
David Applegate and N. J. A. Sloane, The Gift Exchange Problem, arXiv:0907.0513 [math.CO], 2009.
J. Y. Choi and J. D. H. Smith, On the unimodality and combinatorics of Bessel numbers, Discrete Math., 264 (2003), 45-53.
Tom Copeland, Infinitesimal Generators, the Pascal Pyramid, and the Witt and Virasoro Algebras
Toufik Mansour, Matthias Schork, and Mark Shattuck, The Generalized Stirling and Bell Numbers Revisited, Journal of Integer Sequences, Vol. 15 (2012), #12.8.3.
T. Mansour and M. Shattuck, Partial matchings and pattern avoidance, Appl. Anal. Discrete Math. 7 (2013) 25-50.

Other versions of this same triangle are given in A111924 (which omits the first row), A001498 (which left-adjusts the rows in the bottom view), A001497 and A100861. Row sums give A000085.

Cf. A000085, A000217, A001464, A004526, A118930, A144385, A144643..

a144299 n k = a144299_tabl !! n !! k
a144299_row n = a144299_tabl !! n
a144299_tabl = [1] : [1, 0] : f 1 [1] [1, 0] where
   f i us vs = ws : f (i + 1) vs ws where
               ws = (zipWith (+) (0 : map (i *) us) vs) ++ [0]
-- Reinhard Zumkeller, Jan 01 2014

A144299:= func< n,k | k le Floor(n/2) select Factorial(n)/(Factorial(n-2*k)*Factorial(k)*2^k) else 0 >;
[A144299(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Sep 29 2023

Maple code producing the rotated version:
b1 := proc(n, k)
option remember;
if n = k then 1;
elif k < n then 0;
elif n < 1 then 0;
else b1(n - 1, k - 1) + (k - 1)*b1(n - 1, k - 2);
end if;
end proc;
for n from 0 to 12 do lprint([seq(b1(n,k),k=0..2*n)]); od:

T[n_,0]=0; T[1,1]=1; T[2,1]=1; T[n_, k_]:= T[n-1,k-1] + (n-1)T[n-2,k-1];
Table[T[n,k], {n,12}, {k,n,1,-1}]//Flatten (* Robert G. Wilson v *)
Table[If[k<=Floor[n/2],n!/((n-2 k)! k! 2^k),0], {n, 0, 12},{k,0,n}]//Flatten (* Stefano Spezia, Jun 15 2023 *)

def A144299(n,k): return factorial(n)/(factorial(n-2*k)*factorial(k)*2^k) if k <= (n//2) else 0
flatten([[A144299(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Sep 29 2023

T(n, k) = T(n-1, k-1) + (n-1)*T(n-2, k-1).
E.g.f.: Sum_{k >= 0} Sum_{n = 0..2k} T(n,k) y^k x^n/n! = exp(y(x+x^2/2)). (The coefficient of y^k is the e.g.f. for the k-th row of the rotated triangle shown below.)
T(n, k) = n!/((n - 2*k)!*k!*2^k) for 0 <= k <= floor(n/2) and 0 otherwise. - Stefano Spezia, Jun 15 2023
From G. C. Greubel, Sep 29 2023: (Start)
T(n, 1) = A000217(n-1).
Sum_{k=0..n} T(n,k) = A000085(n).
Sum_{k=0..n} (-1)^k*T(n,k) = A001464(n). (End)

Offset fixed by Reinhard Zumkeller, Jan 01 2014

A369196 Number of labeled loop-graphs with n vertices and at most as many edges as covered vertices.

Original entry on oeis.org

1, 2, 7, 39, 320, 3584, 51405, 900947, 18661186, 445827942, 12062839691, 364451604095, 12157649050827, 443713171974080, 17583351295466338, 751745326170662049, 34485624653535808340, 1689485711682987916502, 88030098291829749593643, 4860631073631586486397141

Offset: 0

Gus Wiseman, Jan 17 2024

nonn

			The a(0) = 1 through a(2) = 7 loop-graphs:
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1,2}}
             {{1},{2}}
             {{1},{1,2}}
             {{2},{1,2}}

The version counting all vertices is A066383, without loops A369192.
The loopless case is A369193, with case of equality A367862.
The covering case is A369194, connected A369197, minimal case A001862.
The case of equality is A369198, covering case A368597.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts simple graphs, also loop-graphs if shifted left.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A322661 counts covering loop-graphs, unlabeled A322700.
A368927 counts choosable loop-graphs, covering A369140.
A369141 counts non-choosable loop-graphs, covering A369142.
Cf. A000169, A000272, A000666, A001187, A006649, A057500, A062740, A116508, A367863, A369145.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}]],Length[#]<=Length[Union@@#]&]],{n,0,5}]

Binomial transform of A369194.

A079491 Numerator of Sum_{k=0..n} binomial(n,k)/2^(k*(k-1)/2).

Original entry on oeis.org

1, 2, 7, 45, 545, 12625, 564929, 49162689, 8361575425, 2789624383745, 1830776926245889, 2368773751202917377, 6053217182280501452801, 30595465072175429929979905, 306239118989330960523869667329, 6076268165073202122463201684865025

Offset: 0

N. J. A. Sloane, Jan 20 2003

Conjecture: Also the number of loop-graphs on n vertices without any non-loop edge having loops at both ends, with formula a(n) = Sum_{k=0..n} binomial(n,k) 2^(k*(n-k) + binomial(k,2)). The unlabeled version is A339832. - Gus Wiseman, Jan 25 2024

The above conjecture is true since (n-k)*k + binomial(n-k,2) = binomial(n,2) - binomial(k,2) and A006125 gives the denominators for this sequence. - Andrew Howroyd, Feb 20 2024

			1, 2, 7/2, 45/8, 545/64, 12625/1024, 564929/32768, 49162689/2097152, ...

D. L. Kreher and D. R. Stinson, Combinatorial Algorithms, CRC Press, 1999, p. 113.

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

Denominators are in A006125.
Cf. A079492.
The unlabeled version is A339832 (loop-graphs interpretation).
A000085, A100861, A111924 count set partitions into singletons or pairs.
A000666 counts unlabeled loop-graphs, covering A322700.
A006125 (shifted left) counts labeled loop-graphs, covering A322661.
A006129 counts labeled covering graphs, connected A001187.

[Numerator( (&+[Binomial(n,k)/2^Binomial(k,2): k in [0..n]]) ): n in [0..20]]; // G. C. Greubel, Jun 19 2019

f := n->add(binomial(n,k)/2^(k*(k-1)/2),k=0..n);

Table[Numerator[Sum[Binomial[n,k]/2^Binomial[k,2], {k,0,n}]], {n,0,20}] (* G. C. Greubel, Jun 19 2019 *)

{a(n)=n!*polcoeff(sum(k=0, n, exp(2^k*x +x*O(x^n))*2^(k*(k-1)/2)*x^k/k!), n)} \\ Paul D. Hanna, Sep 14 2009

a(n) = sum(k=0, n, binomial(n,k)*2^(binomial(n,2)-binomial(k,2))) \\ Andrew Howroyd, Feb 20 2024

[numerator( sum(binomial(n,k)/2^binomial(k,2) for k in (0..n)) ) for n in (0..20)] # G. C. Greubel, Jun 19 2019

E.g.f.: Sum_{n>=0} a(n)*x^n/n! = Sum_{n>=0} exp(2^n*x)*2^(n(n-1)/2)*x^n/n!. - Paul D. Hanna, Sep 14 2009

a(n) = Sum_{k=0..n} binomial(n,k) * 2^(binomial(n,2)-binomial(k,2)). - Andrew Howroyd, Feb 20 2024

A369147 Number of unlabeled loop-graphs covering n vertices such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 1, 7, 52, 411, 4440, 73886, 2128608, 111533208, 10812478194, 1945437194308, 650378721118910, 404749938336301313, 470163239887698682289, 1022592854829028310302180, 4177826139658552046624979658, 32163829440870460348768017832607, 468021728889827507080865185809438918

Offset: 0

Gus Wiseman, Jan 23 2024

nonn

			The a(0) = 0 through a(3) = 7 loop-graphs (loops shown as singletons):
  .  .  {{1},{2},{1,2}}  {{1},{2},{3},{1,2}}
                         {{1},{2},{1,2},{1,3}}
                         {{1},{2},{1,3},{2,3}}
                         {{1},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3}}
                         {{1},{2},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3},{2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(3) = 7 unlabeled non-choosable loop-graphs.

Without the choice condition we have A322700, labeled A322661.
The complement for exactly n edges is A368984, labeled A333331 (maybe).
The labeled complement is A369140, covering case of A368927.
The labeled version is A369142, covering case of A369141.
This is the covering case of A369146.
The complement is counted by A369200, covering case of A369145.
Without loops we have A369202, covering case of A140637.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A000666 counts unlabeled loop-graphs, labeled A006125 (shifted left).
A002494 counts unlabeled covering graphs, labeled A006129.
A007716 counts non-isomorphic multiset partitions, connected A007718.
Cf. A000088, A000612, A005703, A055621, A062740, A134964, A137917, A140638, A367868, A368835, A369199.

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]}, {i,Length[p]}])],{p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n],{1,2}]], Union@@#==Range[n] && Length[Select[Tuples[#],UnsameQ@@#&]]==0&]]],{n,0,4}]

First differences of A369146.

a(n) = A322700(n) - A369200(n). - Andrew Howroyd, Feb 02 2024

a(6) onwards from Andrew Howroyd, Feb 02 2024

A144331 Triangle b(n,k) for n >= 0, 0 <= k <= 2n, read by rows. See A144299 for definition and properties.

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 1, 3, 3, 0, 0, 0, 1, 6, 15, 15, 0, 0, 0, 0, 1, 10, 45, 105, 105, 0, 0, 0, 0, 0, 1, 15, 105, 420, 945, 945, 0, 0, 0, 0, 0, 0, 1, 21, 210, 1260, 4725, 10395, 10395, 0, 0, 0, 0, 0, 0, 0, 1, 28, 378, 3150, 17325, 62370, 135135, 135135, 0, 0, 0, 0, 0, 0

Offset: 0

David Applegate and N. J. A. Sloane, Dec 07 2008

Although this entry is the last of the versions of the underlying triangle to be added to the OEIS, for some applications it is the most important.
Row n has 2n+1 entries.
A001498 has a b-file.

			Triangle begins:
  1
  0 1 1
  0 0 1 3 3
  0 0 0 1 6 15 15
  0 0 0 0 1 10 45 105 105
  0 0 0 0 0  1 15 105 420  945  945
  0 0 0 0 0  0  1  21 210 1260 4725 10395 10395
  ...

Reinhard Zumkeller, Rows n = 0..100 of triangle, flattened
Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, Analysis of the Gift Exchange Problem, arXiv:1701.08394 [math.CO], 2017.
David Applegate and N. J. A. Sloane, The Gift Exchange Problem (arXiv:0907.0513, 2009)

Cf. A144299, A278990.
Row sums give A001515, column sums A000085.
Other versions of this triangle are given in A001497, A001498, A111924 and A100861.
See A144385 for a generalization.

a144331 n k = a144331_tabf !! n !! k
a144331_row n = a144331_tabf !! n
a144331_tabf = iterate (\xs ->
  zipWith (+) ([0] ++ xs ++ [0]) $ zipWith (*) (0:[0..]) ([0,0] ++ xs)) [1]
-- Reinhard Zumkeller, Nov 24 2014

A144331:= func< n,k | k le n-1 select 0 else Factorial(k)/(2^(k-n)*Factorial(k-n)*Factorial(2*n-k)) >;
[A144331(n,k): k in [0..2*n], n in [0..12]]; // G. C. Greubel, Oct 04 2023

Flatten[Table[PadLeft[Table[(n+k)!/(2^k*k!*(n-k)!), {k,0,n}], 2*n+1, 0], {n,0,12}]] (* Jean-François Alcover, Oct 14 2011 *)

def A144331(n, k): return 0 if kA144331(n,k) for k in range(2*n+1)] for n in range(13)]) # G. C. Greubel, Oct 04 2023

E.g.f.: Sum_{n >= 0} Sum_{k = 0..2n} b(n,k) y^n * x^k/k! = exp(x*y*(1 + x/2)).
b(n, k) = 2^(n-k)*k!/((2*n-k)!*(k-n)!).
Sum_{k=0..2*n} b(n, k) = A001515(n).
Sum_{n >= 0} b(n, k) = A000085(k).
From G. C. Greubel, Oct 04 2023: (Start)
T(n, k) = 0 for 0 <= k <= n-1, otherwise T(n, k) = k!/(2^(k-n)*(k-n)!*(2*n-k)!) for n <= k <= 2*n.
Sum_{k=0..2*n} (-1)^k * T(n, k) = A278990(n). (End)

cp's OEIS Frontend

A369146 Number of unlabeled loop-graphs with up to n vertices such that it is not possible to choose a different vertex from each edge (non-choosable).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A130757 Triangular table of coefficients of Laguerre-Sonin polynomials n!*2^n*Lag(n,x/2,1/2) of order 1/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A368730 Number of n-element sets of singletons or pairs of distinct elements of {1..n} with union {1..n}, or loop-graphs covering n vertices with n edges, such that it is not possible to choose a different element from each.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A369145 Number of unlabeled loop-graphs with up to n vertices such that it is possible to choose a different vertex from each edge (choosable).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A144299 Triangle of Bessel numbers read by rows. Row n gives T(n,n), T(n,n-1), T(n,n-2), ..., T(n,0) for n >= 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

SageMath

Formula

Extensions

A369196 Number of labeled loop-graphs with n vertices and at most as many edges as covered vertices.

A130757 Triangular table of coefficients of Laguerre-Sonin polynomials n!2^nLag(n,x/2,1/2) of order 1/2.