A088957 -id:A088957 - cp's OEIS frontend

A144303 Square array A(n,m), n>=0, m>=0, read by antidiagonals: A(n,m) = n-th number of the m-th iteration of the hyperbinomial transform on the sequence of 1's.

1, 1, 1, 1, 2, 1, 1, 3, 6, 1, 1, 4, 13, 29, 1, 1, 5, 22, 81, 212, 1, 1, 6, 33, 163, 689, 2117, 1, 1, 7, 46, 281, 1564, 7553, 26830, 1, 1, 8, 61, 441, 2993, 18679, 101961, 412015, 1, 1, 9, 78, 649, 5156, 38705, 268714, 1639529, 7433032, 1, 1, 10, 97, 911, 8257, 71801, 592489, 4538209, 30640257, 154076201, 1

Offset: 0

Alois P. Heinz, Sep 17 2008, revised Oct 30 2012

See A088956 for the definition of the hyperbinomial transform.

A(n,m), n>=0, m>=0, is the number of subtrees of the complete graph K_{n+m} on n+m vertices containing a given, fixed subtree on m vertices. - Alex Chin, Jul 25 2013

			Square array begins:
  1,     1,      1,      1,      1,       1,       1, ...
  1,     2,      3,      4,      5,       6,       7, ...
  1,     6,     13,     22,     33,      46,      61, ...
  1,    29,     81,    163,    281,     441,     649, ...
  1,   212,    689,   1564,   2993,    5156,    8257, ...
  1,  2117,   7553,  18679,  38705,   71801,  123217, ...
  1, 26830, 101961, 268714, 592489, 1166886, 2120545, ...

Alois P. Heinz, Rows n = 0..140, flattened
N. J. A. Sloane, Transforms

Columns m=0-10 give: A000012, A088957, A089461, A089464, A218496, A218497, A218498, A218499, A218500, A218501, A218502.
Rows n=0-2 give: A000012, A000027, A028872.
Main diagonal gives A252766.
Cf. A007318, A088956.

hymtr:= proc(p) proc(n,m) `if`(m=0, p(n), m*add(
           p(k)*binomial(n, k) *(n-k+m)^(n-k-1), k=0..n))
        end end:
A:= hymtr(1):
seq(seq(A(n, d-n), n=0..d), d=0..12);

a[, 0] = 1; a[n, k_] := Sum[k*(n - j + k)^(n - j - 1)*Binomial[n, j], {j, 0, n}]; Table[a[n - k, k], {n, 0, 10}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Jun 24 2013 *)

E.g.f. of column k: exp(x) * (-LambertW(-x)/x)^k.

A(n,k) = Sum_{j=0..n} k * (n-j+k)^(n-j-1) * C(n,j).

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

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

Original entry on oeis.org

-1, 0, 2, 9, 52, 445, 5166, 75019, 1300776, 26167257, 598577770, 15337224991, 435020120316, 13529095809541, 457727913937854, 16736043791509995, 657590281425958096, 27631245762003186865, 1236355641557737359570, 58689534518861119967287

Offset: 0

Seiichi Manyama, Mar 05 2023

Winston de Greef, Table of n, a(n) for n = 0..385
Eric Weisstein's World of Mathematics, Lambert W-Function.

Cf. A088957, A105785, A177885, A277473.

a(n) = sum(k=0, n, (k-1)^(k-1)*binomial(n, k));

my(N=30, x='x+O('x^N)); Vec(serlaplace(-exp(x+lambertw(-x))))

my(N=30, x='x+O('x^N)); Vec(serlaplace(x*exp(x)/lambertw(-x)))

E.g.f.: -exp(x + LambertW(-x)).
E.g.f.: x * exp(x) / LambertW(-x).
a(n) ~ exp(exp(-1)-1) * n^(n-1). - Vaclav Kotesovec, Mar 06 2023

A362522 a(n) = n! * Sum_{k=0..floor(n/2)} (k+1)^(k-1) / (k! * (n-2*k)!).

Original entry on oeis.org

1, 1, 3, 7, 49, 201, 2491, 14743, 266337, 2055889, 49051891, 466650471, 13873711633, 156839920537, 5591748678699, 73222243463671, 3046762637864641, 45346835284775073, 2158148557098011107, 35980450963558606279, 1928292118820446611441

Offset: 0

Seiichi Manyama, Apr 23 2023

Seiichi Manyama, Table of n, a(n) for n = 0..416
Eric Weisstein's World of Mathematics, Lambert W-Function.

Cf. A088957, A362523.

Cf. A089461, A362347.

my(N=30, x='x+O('x^N)); Vec(serlaplace(exp(x-lambertw(-x^2))))

E.g.f.: exp(x - LambertW(-x^2)) = -LambertW(-x^2)/x^2 * exp(x).

a(n) ~ sqrt(2) * (exp(2*exp(-1/2)) + (-1)^n) * n^(n-1) / exp(n/2 + exp(-1/2) - 1). - Vaclav Kotesovec, Aug 05 2025

A362523 a(n) = n! * Sum_{k=0..floor(n/3)} (k+1)^(k-1) / (k! * (n-3*k)!).

Original entry on oeis.org

1, 1, 1, 7, 25, 61, 1201, 7771, 30577, 1058905, 9904321, 53722351, 2708688841, 33126146197, 228967340785, 15262865820931, 230517745701601, 1936173471789361, 161021598306402817, 2894434429492525015, 28614958982310290041

Offset: 0

Seiichi Manyama, Apr 23 2023

Seiichi Manyama, Table of n, a(n) for n = 0..427
Eric Weisstein's World of Mathematics, Lambert W-Function.

Cf. A088957, A362522.

Cf. A089464, A362348.

my(N=30, x='x+O('x^N)); Vec(serlaplace(exp(x-lambertw(-x^3))))

E.g.f.: exp(x - LambertW(-x^3)) = -LambertW(-x^3)/x^3 * exp(x).

a(n) ~ sqrt(3) * (exp(3*exp(-1/3)/2) + 2*cos(sqrt(3)*exp(-1/3)/2 - 2*Pi*n/3)) * n^(n-1) / exp(2*n/3 + exp(-1/3)/2 - 1). - Vaclav Kotesovec, Aug 05 2025

A372315 Expansion of e.g.f. exp( x - LambertW(-2*x)/2 ).

Original entry on oeis.org

1, 2, 8, 68, 960, 18832, 471136, 14324480, 512733696, 21119803136, 984029612544, 51169331031040, 2937675286583296, 184560174104465408, 12594824112085327872, 927757127285523243008, 73369903633161123397632, 6200198958236463387836416

Offset: 0

Seiichi Manyama, Apr 27 2024

nonn

Eric Weisstein's World of Mathematics, Lambert W-Function.

Cf. A088957, A360193, A372316, A372320, A372321.

Cf. A362694.

my(N=20, x='x+O('x^N)); Vec(serlaplace(exp(x-lambertw(-2*x)/2)))

a(n) = sum(k=0, n, (2*k+1)^(k-1)*binomial(n, k));

a(n) = Sum_{k=0..n} (2*k+1)^(k-1) * binomial(n,k).
G.f.: Sum_{k>=0} (2*k+1)^(k-1) * x^k / (1-x)^(k+1).
a(n) ~ 2^(n-1) * n^(n-1) * exp((exp(-1) + 1)/2). - Vaclav Kotesovec, May 04 2024

A372316 Expansion of e.g.f. exp( x - LambertW(-3*x)/3 ).

Original entry on oeis.org

1, 2, 10, 125, 2644, 77597, 2904382, 132169403, 7083715240, 437031850841, 30506442905194, 2377038378159359, 204521399708464252, 19259006462435865413, 1970114326513629358654, 217556451608123850352523, 25794252755430105917806288, 3268152272130255473300883377

Offset: 0

Seiichi Manyama, Apr 27 2024

nonn

Eric Weisstein's World of Mathematics, Lambert W-Function.

Cf. A088957, A360193, A372315, A372320, A372321.

Cf. A362734.

my(N=20, x='x+O('x^N)); Vec(serlaplace(exp(x-lambertw(-3*x)/3)))

a(n) = sum(k=0, n, (3*k+1)^(k-1)*binomial(n, k));

a(n) = Sum_{k=0..n} (3*k+1)^(k-1) * binomial(n,k).
G.f.: Sum_{k>=0} (3*k+1)^(k-1) * x^k / (1-x)^(k+1).
a(n) ~ 3^(n-1) * n^(n-1) * exp((exp(-1) + 1)/3). - Vaclav Kotesovec, May 04 2024

A144289 Triangle T(n,k), n >= 0, 0 <= k <= n, read by rows: Number T(n,k) of forests of labeled rooted trees on n or fewer nodes using a subset of labels 1..n and k edges.

Original entry on oeis.org

1, 2, 0, 4, 2, 0, 8, 12, 9, 0, 16, 48, 84, 64, 0, 32, 160, 480, 820, 625, 0, 64, 480, 2160, 6120, 10230, 7776, 0, 128, 1344, 8400, 34720, 94500, 155274, 117649, 0, 256, 3584, 29568, 165760, 647920, 1712592, 2776200, 2097152, 0, 512, 9216, 96768, 701568, 3669120, 13783392, 35630784, 57138120, 43046721, 0

Offset: 0

Alois P. Heinz, Sep 17 2008

			T(3,1) = 12, because there are 12 forests of labeled rooted trees on 3 or fewer nodes using a subset of labels 1..3 and 1 edge:
  .1<2. .2<1. .1<3. .3<1. .2<3. .3<2. .1<2. .2<1. .1<3. .3<1. .2<3. .3<2.
  ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... .....
  ..... ..... ..... ..... ..... ..... .3... .3... .2... .2... .1... .1...
Triangle begins:
   1;
   2,   0;
   4,   2,   0;
   8,  12,   9,   0;
  16,  48,  84,  64,   0;
  32, 160, 480, 820, 625,  0;

Alois P. Heinz, Rows n = 0..140, flattened
Index entries for sequences related to rooted trees

Columns 0, 1 give A000079, A001815.
First lower diagonal gives A000169 with first term 2.
Row sums give A088957.
Cf. A007318, A000142.

T:= proc(n,k) option remember;
      if k=0 then 2^n
    elif k<0 or n<=k then 0
    elif k=n-1 then n^(n-1)
    else add(binomial(n-1, j) *T(j+1, j) *T(n-1-j, k-j), j=0..k)
      fi
    end:
seq(seq(T(n, k), k=0..n), n=0..11);

T[n_, k_] := T[n, k] = Which[k == 0, 2^n, k<0 || n <= k, 0, k == n-1, n^(n-1), True, Sum[Binomial[n-1, j]*T[j+1, j]*T[n-1-j, k-j], {j, 0, k}]]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 11}] // Flatten (* Jean-François Alcover, Jan 21 2014, translated from Alois P. Heinz's Maple code *)

T(n,0) = 2^n, T(n,k) = 0 if k < 0 or n <= k, otherwise T(n,k) = n^(n-1) if k=n-1, otherwise T(n,k) = Sum_{j=0..k} C(n-1,j)*T(j+1,j)*T(n-1-j,k-j).

A361718 Triangular array read by rows. T(n,k) is the number of labeled directed acyclic graphs on [n] with exactly k nodes of indegree 0.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 15, 9, 1, 0, 316, 198, 28, 1, 0, 16885, 10710, 1610, 75, 1, 0, 2174586, 1384335, 211820, 10575, 186, 1, 0, 654313415, 416990763, 64144675, 3268125, 61845, 441, 1, 0, 450179768312, 286992935964, 44218682312, 2266772550, 43832264, 336924, 1016, 1

Offset: 0

Geoffrey Critzer, Apr 02 2023

Also the number of sets of n nonempty subsets of {1..n}, k of which are singletons, such that there is only one way to choose a different element from each. For example, 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},{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}}    {{1},{2},{1,2,3}}
  {{3},{1,2},{2,3}}    {{1},{3},{1,2,3}}
  {{3},{1,3},{2,3}}    {{2},{3},{1,2,3}}
  {{1},{1,2},{1,2,3}}
  {{1},{1,3},{1,2,3}}
  {{2},{1,2},{1,2,3}}
  {{2},{2,3},{1,2,3}}
  {{3},{1,3},{1,2,3}}
  {{3},{2,3},{1,2,3}}

			Triangle begins:
  1;
  0,     1;
  0,     2,     1;
  0,    15,     9,    1;
  0,   316,   198,   28,  1;
  0, 16885, 10710, 1610, 75, 1;
  ...

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.

Cf. A058876 (mirror), A361579, A224069.
Row-sums are A003024, unlabeled A003087.
Column k = 1 is A003025(n) = |n*A134531(n)|.
Column k = n-1 is A058877.
For fixed sinks we get A368602.
A058891 counts set-systems, unlabeled A000612.
A323818 counts covering connected set-systems, unlabeled A323819.
Cf. A000169, A059201, A082402, A088957, A133686, A334282, A350415, A367904, A367908, A368600, A368601.

nn = 8; B[n_] := n! 2^Binomial[n, 2] ;ggf[egf_] := Normal[Series[egf, {z, 0, nn}]] /. Table[z^i -> z^i/2^Binomial[i, 2], {i, 0, nn}];Table[Take[(Table[B[n], {n, 0, nn}] CoefficientList[ Series[ggf[Exp[(u - 1) z]]/ggf[Exp[-z]], {z, 0, nn}], {z, u}])[[i]], i], {i, 1, nn + 1}] // Grid
nv=4;Table[Length[Select[Subsets[Subsets[Range[n]],{n}], Count[#,{_}]==k&&Length[Select[Tuples[#], UnsameQ@@#&]]==1&]],{n,0,nv},{k,0,n}]

T(n,k) = A368602(n,k) * binomial(n,k). - Gus Wiseman, Jan 03 2024

A372320 Expansion of e.g.f. -exp( x + LambertW(-2*x)/2 ).

Original entry on oeis.org

-1, 0, 4, 36, 464, 8560, 206112, 6104896, 214376192, 8701657344, 400748710400, 20642974511104, 1175888936749056, 73389707156586496, 4980134850525986816, 365062349226075463680, 28747688571714736160768, 2420266280392895064506368

Offset: 0

Seiichi Manyama, Apr 27 2024

sign

Eric Weisstein's World of Mathematics, Lambert W-Function.

Cf. A088957, A360193, A372315, A372316, A372321.

my(N=20, x='x+O('x^N)); Vec(serlaplace(-exp(x+lambertw(-2*x)/2)))

a(n) = sum(k=0, n, (2*k-1)^(k-1)*binomial(n, k));

a(n) = Sum_{k=0..n} (2*k-1)^(k-1) * binomial(n,k).
G.f.: Sum_{k>=0} (2*k-1)^(k-1) * x^k / (1-x)^(k+1).
a(n) ~ 2^(n-1) * n^(n-1) * exp((exp(-1) - 1)/2). - Vaclav Kotesovec, May 06 2024

cp's OEIS Frontend

A144303 Square array A(n,m), n>=0, m>=0, read by antidiagonals: A(n,m) = n-th number of the m-th iteration of the hyperbinomial transform on the sequence of 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

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

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

PARI

Formula

A362522 a(n) = n! * Sum_{k=0..floor(n/2)} (k+1)^(k-1) / (k! * (n-2*k)!).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A362523 a(n) = n! * Sum_{k=0..floor(n/3)} (k+1)^(k-1) / (k! * (n-3*k)!).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A372315 Expansion of e.g.f. exp( x - LambertW(-2*x)/2 ).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

A372316 Expansion of e.g.f. exp( x - LambertW(-3*x)/3 ).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

A144289 Triangle T(n,k), n >= 0, 0 <= k <= n, read by rows: Number T(n,k) of forests of labeled rooted trees on n or fewer nodes using a subset of labels 1..n and k edges.

Views

Author

Keywords

Examples

Links