A346500 -id:A346500 - cp's OEIS frontend

A020555 Number of multigraphs on n labeled edges (with loops). Also number of genetically distinct states amongst n individuals.

1, 2, 9, 66, 712, 10457, 198091, 4659138, 132315780, 4441561814, 173290498279, 7751828612725, 393110572846777, 22385579339430539, 1419799938299929267, 99593312799819072788, 7678949893962472351181, 647265784993486603555551, 59357523410046023899154274

Offset: 0

Gilbert Labelle (gilbert(AT)lacim.uqam.ca), Simon Plouffe, N. J. A. Sloane

nonn

Also the number of factorizations of (p_n#)^2. - David W. Wilson, Apr 30 2001
Also the number of multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}. - Gus Wiseman, Jul 18 2018
a(n) gives the number of genetically distinct states for n diploid individuals in the case that maternal and paternal alleles transmitted to the individuals are not distinguished (if maternal and paternal alleles are distinguished, then the number of states is A000110(2n)). - Noah A Rosenberg, Aug 23 2022

			From _Gus Wiseman_, Jul 18 2018: (Start)
The a(2) = 9 multiset partitions of {1, 1, 2, 2}:
  (1122),
  (1)(122), (2)(112), (11)(22), (12)(12),
  (1)(1)(22), (1)(2)(12), (2)(2)(11),
  (1)(1)(2)(2).
(End)

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Table A-1, page 778. - N. J. A. Sloane, Dec 30 2018
E. Keith Lloyd, Math. Proc. Camb. Phil. Soc., vol. 103 (1988), 277-284.
A. Murthy, Generalization of partition function, introducing Smarandache factor partitions. Smarandache Notions Journal, Vol. 11, No. 1-2-3, Spring 2000.
G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004.

Alois P. Heinz, Table of n, a(n) for n = 0..310 (first 101 terms from Vincenzo Librandi)
G. Labelle, Counting enriched multigraphs according to the number of their edges (or arcs), Discrete Math., 217 (2000), 237-248.
G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004. [Cached copy, with permission]
Marko Riedel et al., Set partitions of {1,1,2,2,...,n,n}
E. A. Thompson, Gene identities and multiple relationships. Biometrics 30 (1974), 667-680. See Table 5.

Row n=2 of A219727. - Alois P. Heinz, Nov 26 2012
Cf. A007716, A007717, A014500, A014501, A020554, A094574, A316974.
See also A322764. Row 0 of the array in A322765.
Main diagonal of A346500.
Cf. A001055, A002110.

B := n -> combinat[bell](n):
P := proc(m,n) local k; global B; option remember;
if n = 0 then B(m)  else
(1/2)*( P(m+2,n-1) + P(m+1,n-1) + add( binomial(n-1,k)*P(m,k), k=0..n-1) ); fi; end;
r:=m->[seq(P(m,n),n=0..20)]; r(0); # N. J. A. Sloane, Dec 30 2018

max = 16; s = Series[Exp[-3/2 + Exp[x]/2]*Sum[Exp[Binomial[n+1, 2]*x]/n!, {n, 0, 3*max }], {x, 0, max}] // Normal; a[n_] := SeriesCoefficient[s, {x, 0, n}]*n!; Table[a[n] // Round, {n, 0, max} ] (* Jean-François Alcover, Apr 23 2014, after Vladeta Jovovic *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
Table[Length[mps[Ceiling[Range[1/2,n,1/2]]]],{n,5}] (* Gus Wiseman, Jul 18 2018 *)

Lloyd's article gives a complicated explicit formula.
E.g.f.: exp(-3/2 + exp(x)/2)*Sum_{n>=0} exp(binomial(n+1, 2)*x)/n! [probably in the Labelle paper]. - Vladeta Jovovic, Apr 27 2004
a(n) = A001055(A002110(n)^2). - Alois P. Heinz, Aug 23 2022

A346517 Number A(n,k) of partitions of the (n+k)-multiset {1,2,...,n,1,2,...,k} into distinct multisets; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 5, 3, 3, 5, 15, 9, 5, 9, 15, 52, 31, 18, 18, 31, 52, 203, 120, 70, 40, 70, 120, 203, 877, 514, 299, 172, 172, 299, 514, 877, 4140, 2407, 1393, 801, 457, 801, 1393, 2407, 4140, 21147, 12205, 7023, 4025, 2295, 2295, 4025, 7023, 12205, 21147

Offset: 0

Alois P. Heinz, Jul 21 2021

Also number A(n,k) of factorizations of Product_{i=1..n} prime(i) * Product_{i=1..k} prime(i) into distinct factors; A(2,2) = 5: 2*3*6, 4*9, 3*12, 2*18, 36.

			A(2,2) = 5: 1122, 11|22, 1|122, 112|2, 1|12|2.
Square array A(n,k) begins:
    1,    1,    2,     5,    15,     52,    203,     877, ...
    1,    1,    3,     9,    31,    120,    514,    2407, ...
    2,    3,    5,    18,    70,    299,   1393,    7023, ...
    5,    9,   18,    40,   172,    801,   4025,   21709, ...
   15,   31,   70,   172,   457,   2295,  12347,   70843, ...
   52,  120,  299,   801,  2295,   6995,  40043,  243235, ...
  203,  514, 1393,  4025, 12347,  40043, 136771,  875936, ...
  877, 2407, 7023, 21709, 70843, 243235, 875936, 3299218, ...
  ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns (or rows) k=0-10 give: A000110, A087648, A322773, A322774, A346897, A346898, A346899, A346900, A346901, A346902, A346903.
Main diagonal gives A094574.
First upper (or lower) diagonal gives A322771.
Second upper (or lower) diagonal gives A322772.
Antidiagonal sums give A346518.
Cf. A002110, A045778, A322770, A346500.

g:= proc(n, k) option remember; uses numtheory; `if`(n>k, 0, 1)+
     `if`(isprime(n), 0, add(`if`(d>k or max(factorset(n/d))>d, 0,
        g(n/d, d-1)), d=divisors(n) minus {1, n}))
    end:
p:= proc(n) option remember; `if`(n=0, 1, p(n-1)*ithprime(n)) end:
A:= (n, k)-> g(p(n)*p(k)$2):
seq(seq(A(n, d-n), n=0..d), d=0..10);
# second Maple program:
b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-j)*binomial(n-1, j-1), j=1..n))
    end:
A:= proc(n, k) option remember; `if`(n

(* Q is A322770 *)
Q[m_, n_] := Q[m, n] = If[n == 0, BellB[m], (1/2)(Q[m+2, n-1] + Q[m+1, n-1] - Sum[Binomial[n-1, k] Q[m, k], {k, 0, n-1}])];
A[n_, k_] := Q[Abs[n-k], Min[n, k]];
Table[A[n, d-n], {d, 0, 10}, {n, 0, d}] // Flatten (* Jean-François Alcover, Aug 19 2021 *)

A(n,k) = A045778(A002110(n)*A002110(k)).
A(n,k) = A(k,n).
A(n,k) = A322770(abs(n-k),min(n,k)).

A322765 Array read by upwards antidiagonals: T(m,n) = number of set partitions of the multiset consisting of one copy each of x_1, x_2, ..., x_m, and two copies each of y_1, y_2, ..., y_n, for m >= 0, n >= 0.

Original entry on oeis.org

1, 1, 2, 2, 4, 9, 5, 11, 26, 66, 15, 36, 92, 249, 712, 52, 135, 371, 1075, 3274, 10457, 203, 566, 1663, 5133, 16601, 56135, 198091, 877, 2610, 8155, 26683, 91226, 325269, 1207433, 4659138, 4140, 13082, 43263, 149410, 537813, 2014321, 7837862, 31638625, 132315780

Offset: 0

N. J. A. Sloane, Dec 30 2018

			The array begins:
    1,    2,     9,     66,      712,     10457,      198091, ...
    1,    4,    26,    249,     3274,     56135,     1207433, ...
    2,   11,    92,   1075,    16601,    325269,     7837862, ...
    5,   36,   371,   5133,    91226,   2014321,    53840640, ...
   15,  135,  1663,  26683,   537813,  13241402,   389498179, ...
   52,  566,  8155, 149410,  3376696,  91914202,  2955909119, ...
  203, 2610, 43263, 894124, 22451030, 670867539, 23456071495, ...
  ...

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Table A-1, page 778.

Seiichi Manyama, Antidiagonals n = 0..139, flattened

Rows include A020555, A322766, A322767.
Columns include A000110, A035098, A322764, A322768.
Main diagonal is A322769.
See A322770 for partitions into distinct parts.
Cf. A001055, A002110, A346500.

B := n -> combinat[bell](n):
P := proc(m,n) local k; global B; option remember;
if n = 0 then B(m)  else
(1/2)*( P(m+2,n-1) + P(m+1,n-1) + add( binomial(n-1,k)*P(m,k), k=0..n-1) ); fi; end; # P(m,n) (which is Knuth's notation) is T(m,n)

P[m_, n_] := P[m, n] = If[n == 0, BellB[m], (1/2)(P[m+2, n-1] + P[m+1, n-1] + Sum[Binomial[n-1, k] P[m, k], {k, 0, n-1}])];
Table[P[m-n, n], {m, 0, 8}, {n, 0, m}] // Flatten (* Jean-François Alcover, Jan 02 2019, from Maple *)

{T(n, k) = if(k==0, sum(j=0, n, stirling(n, j, 2)), (T(n+2, k-1)+T(n+1, k-1)+sum(j=0, k-1, binomial(k-1, j)*T(n, j)))/2)} \\ Seiichi Manyama, Nov 21 2020

Knuth p. 779 gives a recurrence using the Bell numbers A000110 (see Maple program).
From Alois P. Heinz, Jul 21 2021: (Start)
A(n,k) = A001055(A002110(n+k)*A002110(k)).
A(n,k) = A346500(n+k,k). (End)

A346490 Total number of partitions of all n-multisets {1,2,...,n-j,1,2,...,j} for 0 <= j <= n.

Original entry on oeis.org

1, 2, 6, 18, 61, 228, 926, 4126, 19688, 101582, 556763, 3258810, 20134527, 131591030, 902915694, 6506096000, 48986713992, 385159376478, 3151457714098, 26806601933838, 236457090358459, 2160451562170100, 20408176433186475, 199086685731569740, 2002713693735431017

Offset: 0

Alois P. Heinz, Jul 19 2021

nonn

Also total number of factorizations of Product_{i=1..n-j} prime(i) * Product_{i=1..j} prime(i) for 0 <= j <= n.

Alois P. Heinz, Table of n, a(n) for n = 0..576

Antidiagonal sums of A346500.

Cf. A001055, A002110, A346428, A346518.

b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-j)*binomial(n-1, j-1), j=1..n))
    end:
A:= proc(n, k) option remember; `if`(n add(A(n-j, j), j=0..n):
seq(a(n), n=0..24);

b[n_] := b[n] = If[n == 0, 1,
     Sum[b[n - j]*Binomial[n - 1, j - 1], {j, 1, n}]];
A[n_, k_] := A[n, k] = If[n < k, A[k, n],
     If[k == 0, b[n], (A[n + 1, k - 1] + Sum[A[n - k + j, j]
     *Binomial[k - 1, j], {j, 0, k - 1}] + A[n, k - 1])/2]];
a[n_] := Sum[A[n - j, j], {j, 0, n}];
Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Mar 12 2022, after Alois P. Heinz *)

a(n) = Sum_{j=0..n} A001055(A002110(n-j)*A002110(j)).

a(n) = Sum_{j=0..n} A346500(n-j,j).

A322766 Row 1 of array in A322765.

Original entry on oeis.org

1, 4, 26, 249, 3274, 56135, 1207433, 31638625, 987249425, 36030130677, 1515621707692, 72603595393584, 3920675798922189, 236615520916677436, 15840357595697061964, 1168697367186883073296, 94486667847573203169757, 8328527812527985862657297, 796762955545266206229493979

Offset: 0

N. J. A. Sloane, Dec 30 2018

nonn

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Table A-1, page 778.

Seiichi Manyama, Table of n, a(n) for n = 0..300

Cf. A322765, A346500.

b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-j)*binomial(n-1, j-1), j=1..n))
    end:
A:= proc(n, k) option remember; `if`(n A(n, n+1):
seq(a(n), n=0..22);  # Alois P. Heinz, Jul 21 2021

b[n_] := b[n] = If[n == 0, 1,
     Sum[b[n - j]*Binomial[n-1, j-1], {j, 1, n}]];
A[n_, k_] := A[n, k] = If[n < k, A[k, n],
     If[k == 0, b[n], (A[n+1, k - 1] + Sum[A[n - k + j, j]*
     Binomial[k-1, j], {j, 0, k - 1}] + A[n, k - 1])/2]];
a[n_] := A[n, n + 1];  Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Jun 01 2022, after Alois P. Heinz *)

a(n) = A346500(n,n+1) = A346500(n+1,n). - Alois P. Heinz, Jul 21 2021

A322767 Row 2 of array in A322765.

Original entry on oeis.org

2, 11, 92, 1075, 16601, 325269, 7837862, 226700129, 7720099374, 304732680254, 13763771702539, 703691774091622, 40351866669219915, 2574830780826344436, 181574292457398520558, 14065771632972561098569, 1190588796562104776974207

Offset: 0

N. J. A. Sloane, Dec 30 2018

nonn

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Table A-1, page 778.

Seiichi Manyama, Table of n, a(n) for n = 0..300

Cf. A322765, A346500.

b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-j)*binomial(n-1, j-1), j=1..n))
    end:
A:= proc(n, k) option remember; `if`(n A(n, n+2):
seq(a(n), n=0..22);  # Alois P. Heinz, Jul 21 2021

P[m_, n_] := P[m, n] = If[n == 0, BellB[m], (1/2)(P[m+2, n-1] + P[m+1, n-1] + Sum[Binomial[n-1, k] P[m, k], {k, 0, n-1}])];
a[n_] := P[2, n];
Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Apr 29 2022 *)

a(n) = A346500(n,n+2) = A346500(n+2,n). - Alois P. Heinz, Jul 21 2021

A322769 Main diagonal of array in A322765.

Original entry on oeis.org

1, 4, 92, 5133, 537813, 91914202, 23456071495, 8411911367949, 4055497274641836, 2540939492105630071, 2014322292658946180922, 1977121111959534634757742, 2360026677940190304494287625, 3374607252811005168634470847052, 5706308288951111509370981721908854

Offset: 0

N. J. A. Sloane, Dec 30 2018

nonn

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Table A-1, page 778.

Seiichi Manyama, Table of n, a(n) for n = 0..200

Cf. A322765, A346500.

b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-j)*binomial(n-1, j-1), j=1..n))
    end:
A:= proc(n, k) option remember; `if`(n A(2*n, n):
seq(a(n), n=0..15);  # Alois P. Heinz, Jul 21 2021

P[m_, n_] := P[m, n] = If[n == 0, BellB[m], (1/2)(P[m+2, n-1] + P[m+1, n-1] + Sum[Binomial[n-1, k] P[m, k], {k, 0, n-1}])];
a[n_] := P[n, n];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Apr 29 2022 *)

a(n) = A346500(2n,n). - Alois P. Heinz, Jul 20 2021

A346881 Number of partitions of the (n+4)-multiset {1,2,...,n,1,2,3,4}.

Original entry on oeis.org

15, 36, 92, 249, 712, 3274, 16601, 91226, 537813, 3376696, 22451030, 157351792, 1158085539, 8921446554, 71736592681, 600613793322, 5224699647616, 47130663392158, 440121213096745, 4248057380997578, 42319698380927573, 434577434511268764, 4594614286246088158

Offset: 0

Alois P. Heinz, Aug 06 2021

nonn

Also number of factorizations of Product_{i=1..n} prime(i) * Product_{i=1..4} prime(i).

Alois P. Heinz, Table of n, a(n) for n = 0..572

Column (or row) k=4 of A346500.

Cf. A346897.

A346882 Number of partitions of the (n+5)-multiset {1,2,...,n,1,2,...,5}.

Original entry on oeis.org

52, 135, 371, 1075, 3274, 10457, 56135, 325269, 2014321, 13241402, 91914202, 670867539, 5130574485, 40989058693, 341205653979, 2952731951176, 26510494023154, 246500382677473, 2369854608269687, 23523121378151405, 240746022804236085, 2537378601343161682

Offset: 0

Alois P. Heinz, Aug 06 2021

nonn

Also number of factorizations of Product_{i=1..n} prime(i) * Product_{i=1..5} prime(i).

Alois P. Heinz, Table of n, a(n) for n = 0..571

Column (or row) k=5 of A346500.

Cf. A346898.

A346883 Number of partitions of the (n+6)-multiset {1,2,...,n,1,2,...,6}.

Original entry on oeis.org

203, 566, 1663, 5133, 16601, 56135, 198091, 1207433, 7837862, 53840640, 389498179, 2955909119, 23456071495, 194085705507, 1670557123494, 14925918737608, 138171493962579, 1323014338459417, 13083446209405171, 133442756205787837, 1401971566195451042

Offset: 0

Alois P. Heinz, Aug 06 2021

nonn

Also number of factorizations of Product_{i=1..n} prime(i) * Product_{i=1..6} prime(i).

Alois P. Heinz, Table of n, a(n) for n = 0..571

Column (or row) k=6 of A346500.

Cf. A346899.

cp's OEIS Frontend

A020555 Number of multigraphs on n labeled edges (with loops). Also number of genetically distinct states amongst n individuals.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A346517 Number A(n,k) of partitions of the (n+k)-multiset {1,2,...,n,1,2,...,k} into distinct multisets; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A322765 Array read by upwards antidiagonals: T(m,n) = number of set partitions of the multiset consisting of one copy each of x_1, x_2, ..., x_m, and two copies each of y_1, y_2, ..., y_n, for m >= 0, n >= 0.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A346490 Total number of partitions of all n-multisets {1,2,...,n-j,1,2,...,j} for 0 <= j <= n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A322766 Row 1 of array in A322765.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A322767 Row 2 of array in A322765.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A322769 Main diagonal of array in A322765.

Views

Author

Keywords

References

Links

Crossrefs

Programs