A100861 -id:A100861 - cp's OEIS frontend

A370165 Number of labeled loop-graphs covering n vertices without a non-loop edge with loops at both ends.

1, 1, 4, 29, 400, 10289, 496548, 45455677, 7983420736, 2716094133313, 1803251169342820, 2348787270663723581, 6024912118926389490448, 30516957491540079828757553, 305811332460677494410532494660, 6071677788061208810793717466942237

Offset: 0

Gus Wiseman, Feb 12 2024

nonn

Number of ways to choose a stable vertex set of a simple graph with n vertices.

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

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

Without loops we have A006129, connected A001187.
The non-covering version is A079491.
The unlabeled version is A370166, non-covering A339832.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A000666 counts unlabeled loop-graphs, covering A322700.
A006125 counts labeled loop-graphs (shifted left), covering A322661.
Cf. A048291, A062740, A116539, A320461, A322635.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}]], Union@@#==Range[n]&&!MatchQ[#, {_,{x_},_,{y_},_,{x_,y_},_}]&]],{n,0,5}]

seq(n)={Vec(serlaplace(sum(k=0, n, exp((2^k-1)*x + O(x*x^n))*2^(k*(k-1)/2)*x^k/k!)))} \\ Andrew Howroyd, Feb 20 2024

Inverse binomial transform of A079491.

E.g.f.: Sum_{k >= 0} exp((2^k-1)*x)*2^(k*(k-1)/2)*x^k/k!. - Andrew Howroyd, Feb 20 2024

A181386 Tetrahedron of terms C(r,n,m) representing the number of ways of choosing m disjoint subsets of r members from an original set of n members.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 1, 1, 4, 6, 4, 1, 1, 3, 1, 1, 1, 1, 5, 10, 10, 5, 1, 1, 6, 3, 1, 1, 1, 1, 1, 1, 6, 15, 20, 15, 6, 1, 1, 10, 15, 1, 4, 1, 1, 1, 1, 1, 7, 21, 35, 35, 21, 7, 1, 1, 15, 45, 15, 1, 10, 1, 1, 1, 1, 1, 1, 1, 8, 28, 56, 70, 56, 28, 8, 1, 1, 21, 105, 105, 1, 20

Offset: 1

Frank M Jackson, Oct 16 2010

The start index for r is 1 but the start index for m and n is 0. For each value of r, the triangle T_r(n,m) has row n containing 1 + floor(n/r) terms.
From Frank M Jackson, Nov 20 2010: (Start)
C(r,mr,m) = C(r,mr-1,m-1).
C(1,m,m) = A000012, C(2,2m,m) = A001147,
C(3,3m,m), ..., C(10,10m,m) = A025035, ..., A025042.
C(2,26,10) = 150738274937250 and represents the number of possible plugboard settings for a WWII German Enigma Enciphering Machine.
C(r,2r,2) = A001700, C(r,3r,3) = A060542, C(r,4r,4) = A082368.
C(r,n,m) = C(r,mr-1,m-1)*binomial(n,rm),
  and applied recursively gives the identity
C(r,n,m) = Binomial(n,r*m) * Product_{p=1..m} Binomial(r*(m-p+1)-1,r-1).
(End)
C(2,26,10) = A266365(10), where 26 is the size of the alphabet. - Jonathan Sondow, Dec 29 2015

			r=1, C(1,n,m) is
  1
  1, 1
  1, 2,  1
  1, 3,  3,  1
  1, 4,  6,  4, 1
  1, 5, 10, 10, 5, 1
r=2, C(2,n,m) is
  1
  1
  1,  1
  1,  3
  1,  6,  3
  1, 10, 15
r=3, C(3,n,m) is
  1
  1
  1
  1,  1
  1,  4
  1, 10

C(1,n,m) = T_1(n,m) = A007318, C(2,n,m) = T_2(n,m) = A100861, and C(2,26,m) = A266365.

Flatten[Table[{n!/((n-r*m)!*m!*r!^m)}, {r, 1, 50}, {n, 0, 50}, {m, 0, Floor[n/r]}]]

C(r,n,m) = n!/((n-r*m)!*m!*(r!)^m).

A369198 Number of labeled loop-graphs with n vertices and the same number of edges as covered vertices.

Original entry on oeis.org

1, 2, 6, 30, 241, 2759, 40824, 736342, 15622835, 380668095, 10467815086, 320529284621, 10813165015074, 398413594789777, 15917197015926392, 685312404706694574, 31631317971844128229, 1558017329350990780607, 81567807853701988869120, 4522975947689168088308305

Offset: 0

Gus Wiseman, Jan 18 2024

nonn

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

The version counting all vertices is A014068.
The loopless case is A367862, counting all vertices A116508.
The covering case is A368597, connected A368951.
With inequality we have A369196, covering A369194, connected A369197.
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. A000272, A000666, A006649, A062740, A066383, A367863, A369192, A369193.

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

Binomial transform of A368597.

A111805 Number triangle T(n,k)=binomial(2(n+k),4k).

Original entry on oeis.org

1, 1, 1, 1, 15, 1, 1, 70, 45, 1, 1, 210, 495, 91, 1, 1, 495, 3003, 1820, 153, 1, 1, 1001, 12870, 18564, 4845, 231, 1, 1, 1820, 43758, 125970, 74613, 10626, 325, 1, 1, 3060, 125970, 646646, 735471, 230230, 20475, 435, 1, 1, 4845, 319770, 2704156, 5311735

Offset: 0

Paul Barry, Aug 17 2005

Related to matchings of the complete graph K_2n: T(n,k)=A100861(2(n+k),2k)/f(2k), where f(n)=(2n-1)!! Column k gives number of standard tableaux of shape (2n+1,1^(4k)).

			Rows begin
1;
1,1;
1,15,1;
1,70,45,1;
1,210,495,91,1;

Table[Binomial[2(n+k),4k],{n,0,10},{k,0,n}]//Flatten (* Harvey P. Dale, Mar 30 2019 *)

Column k has g.f. x^k*sum{j=0..2k+1, binomial(4k+1, 2j)x^j}/(1-x)^(4k+1)

cp's OEIS Frontend

A370165 Number of labeled loop-graphs covering n vertices without a non-loop edge with loops at both ends.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A181386 Tetrahedron of terms C(r,n,m) representing the number of ways of choosing m disjoint subsets of r members from an original set of n members.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A369198 Number of labeled loop-graphs with n vertices and the same number of edges as covered vertices.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A111805 Number triangle T(n,k)=binomial(2(n+k),4k).

Views

Author

Keywords

Comments

Examples

Programs

Mathematica

Formula