A087648 -id:A087648 - cp's OEIS frontend

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

1, 1, 1, 2, 2, 1, 5, 5, 3, 2, 15, 15, 9, 5, 2, 52, 52, 31, 16, 7, 3, 203, 203, 120, 59, 25, 10, 4, 877, 877, 514, 244, 100, 38, 14, 5, 4140, 4140, 2407, 1112, 442, 161, 56, 19, 6, 21147, 21147, 12205, 5516, 2134, 750, 249, 80, 25, 8, 115975, 115975, 66491, 29505, 11147, 3799, 1213, 372, 111, 33, 10

Offset: 0

Alois P. Heinz, Jul 21 2021

Also number A(n,k) of factorizations of 2^n * Product_{i=1..k} prime(i+1) into distinct factors; A(3,1) = 5: 2*3*4, 4*6, 3*8, 2*12, 24; A(1,2) = 5: 2*3*5, 5*6, 3*10, 2*15, 30.

			A(2,2) = 9: 00|1|2, 001|2, 1|002, 0|01|2, 0|1|02, 01|02, 00|12, 0|012, 0012.
Square array A(n,k) begins:
  1,  1,   2,   5,   15,    52,   203,    877,    4140, ...
  1,  2,   5,  15,   52,   203,   877,   4140,   21147, ...
  1,  3,   9,  31,  120,   514,  2407,  12205,   66491, ...
  2,  5,  16,  59,  244,  1112,  5516,  29505,  168938, ...
  2,  7,  25, 100,  442,  2134, 11147,  62505,  373832, ...
  3, 10,  38, 161,  750,  3799, 20739, 121141,  752681, ...
  4, 14,  56, 249, 1213,  6404, 36332, 220000, 1413937, ...
  5, 19,  80, 372, 1887, 10340, 60727, 379831, 2516880, ...
  6, 25, 111, 539, 2840, 16108, 97666, 629346, 4288933, ...
  ...

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

Columns k=0-10 give: A000009, A036469, A346822, A346823, A346824, A346825, A346826, A346827, A346828, A346829, A346830.
Rows n=0+1,2-10 give: A000110, A087648, A346813, A346814, A346815, A346816, A346817, A346818, A346819, A346820.
Main diagonal gives A346519.
Antidiagonal sums give A346521.
Cf. A000040, A000079, A045778, A048993, A070826, A346426.

g:= proc(n) option remember; `if`(n=0, 1, add(g(n-j)*add(
     `if`(d::odd, d, 0), d=numtheory[divisors](j)), j=1..n)/n)
    end:
s:= proc(n) option remember; expand(`if`(n=0, 1,
      x*add(s(n-j)*binomial(n-1, j-1), j=1..n)))
    end:
S:= proc(n, k) option remember; coeff(s(n), x, k) end:
b:= proc(n, i) option remember; `if`(n=0, 1,
     `if`(i=0, g(n), add(b(n-j, i-1), j=0..n)))
    end:
A:= (n, k)-> add(S(k, j)*b(n, j), j=0..k):
seq(seq(A(n, d-n), n=0..d), d=0..12);

g[n_] := g[n] = If[n == 0, 1, Sum[g[n - j]*Sum[If[OddQ[d], d, 0], {d, Divisors[j]}], {j, 1, n}]/n];
s[n_] := s[n] = Expand[If[n == 0, 1, x*Sum[s[n - j]*Binomial[n - 1, j - 1], {j, 1, n}]]];
S[n_, k_] := S[n, k] = Coefficient[s[n], x, k];
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i == 0, g[n], Sum[b[n - j, i - 1], {j, 0, n}]]];
A[n_, k_] := Sum[S[k, j]*b[n, j], {j, 0, k}];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Jul 31 2021, after Alois P. Heinz *)

A(n,k) = A045778(A000079(n)*A070826(k+1)).

A(n,k) = Sum_{j=0..k} Stirling2(k,j)*Sum_{i=0..n} binomial(j+i-1,i)*A000009(n-i).

A035098 Near-Bell numbers: partitions of an n-multiset with multiplicities 1, 1, 1, ..., 1, 2.

Original entry on oeis.org

1, 2, 4, 11, 36, 135, 566, 2610, 13082, 70631, 407846, 2504071, 16268302, 111378678, 800751152, 6027000007, 47363985248, 387710909055, 3298841940510, 29119488623294, 266213358298590, 2516654856419723, 24566795704844210

Offset: 1

George Beck

nonn

A035098 and A000070 are near the two ends of a spectrum. Another way to look at A000070 is as the number of partitions of an n-multiset with multiplicities n-1, 1.
The very ends are the number of partitions and the Stirling numbers of the second kind, which count the n-multiset partitions with multiplicities n and 1,1,1,...,1, respectively.
Intermediate sequences are the number of ways of partitioning an n-multiset with multiplicities some partition of n.

			a(3)=4 because there are 4 ways to partition the multiset {1,2,2} (with multiplicities {1,2}): {{1,2,2}} {{1,2},{2}} {{1},{2,2}} {{1},{2},{2}}.

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Table A-1, page 778. - N. J. A. Sloane, Dec 30 2018

Alois P. Heinz, Table of n, a(n) for n = 1..576 (first 200 terms from Vincenzo Librandi)
M. Griffiths, Generalized Near-Bell Numbers, JIS 12 (2009) 09.5.7.
M. Griffiths, I. Mezo, A generalization of Stirling Numbers of the Second Kind via a special multiset, JIS 13 (2010) #10.2.5.
Martin Griffiths, Generating Functions for Extended Stirling Numbers of the First Kind, Journal of Integer Sequences, 17 (2014), #14.6.4.

Cf. A000070, A000110, A059606, A087648.
Row sums of A241500.
Column 1 of array in A322765.
Row n=2 of A346426.

with(combinat): a:= n-> floor(1/2*(bell(n-2)+bell(n-1)+bell(n))): seq(a(n), n=1..25); # Zerinvary Lajos, Oct 07 2007

f[n_] := Sum[ StirlingS2[n, k] ((k + 1) (k + 2)/2 + 1), {k, 0, n}]; Array[f, 22, 0]
f[n_] := (BellB[n] + BellB[n + 1] + BellB[n + 2])/2; Array[f, 22, 0]
Range[0, 21]! CoefficientList[ Series[ (1 + Exp@ x)^2/2 Exp[ Exp@ x - 1], {x, 0, 21}], x] (* 3 variants by Robert G. Wilson v, Jan 13 2011 *)
Join[{1},Total[#]/2&/@Partition[BellB[Range[0,30]],3,1]] (* Harvey P. Dale, Jan 02 2019 *)

Sum_{k=0..n} Stirling2(n, k)*((k+1)*(k+2)/2+1). E.g.f.: 1/2*(1+exp(x))^2*exp(exp(x)-1). (1/2)*(Bell(n)+Bell(n+1)+Bell(n+2)). - Vladeta Jovovic, Sep 23 2003 [for offset -1]

a(n) ~ Bell(n)/2 * (1 + LambertW(n)/n). - Vaclav Kotesovec, Jul 28 2021

More terms from Vladeta Jovovic, Sep 23 2003

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)).

A322770 Array read by upwards antidiagonals: T(m,n) = number of set partitions into distinct parts 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, 1, 2, 3, 5, 5, 9, 18, 40, 15, 31, 70, 172, 457, 52, 120, 299, 801, 2295, 6995, 203, 514, 1393, 4025, 12347, 40043, 136771, 877, 2407, 7023, 21709, 70843, 243235, 875936, 3299218, 4140, 12205, 38043, 124997, 431636, 1562071, 5908978, 23308546, 95668354

Offset: 0

N. J. A. Sloane, Dec 30 2018

			The array begins:
     1,    1,     5,     40,      457,      6995,      136771, ...
     1,    3,    18,    172,     2295,     40043,      875936, ...
     2,    9,    70,    801,    12347,    243235,     5908978, ...
     5,   31,   299,   4025,    70843,   1562071,    41862462, ...
    15,  120,  1393,  21709,   431636,  10569612,   310606617, ...
    52,  514,  7023, 124997,  2781372,  75114998,  2407527172, ...
   203, 2407, 38043, 764538, 18885177, 559057663, 19449364539, ...
   ...

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

Alois P. Heinz, Antidiagonals n = 0..140, flattened
D. E. Knuth, Partitioning a multiset into submultisets, Email to N. J. A. Sloane, Dec 29 2018.

Rows include A094574, A322771, A322772.
Columns include A000110, A087648, A322773, A322774.
Main diagonal is A322775.

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

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}])];
Table[Q[m-n, n], {m, 0, 8}, {n, 0, m}] // Flatten (* Jean-François Alcover, Jan 02 2019, from Maple *)

Knuth gives a recurrence using the Bell numbers A000110 (see Maple program).

A120057 Table T(n,k) = sum over all set partitions of n of number at index k.

Original entry on oeis.org

1, 2, 3, 5, 8, 9, 15, 25, 29, 31, 52, 89, 106, 115, 120, 203, 354, 431, 474, 499, 514, 877, 1551, 1923, 2141, 2273, 2355, 2407, 4140, 7403, 9318, 10489, 11224, 11695, 12002, 12205, 21147, 38154, 48635, 55286, 59595, 62434, 64331, 65614, 66491, 115975, 210803, 271617, 311469, 338019, 355951, 368205, 376665, 382559, 386699

Offset: 1

Franklin T. Adams-Watters, Jun 06 2006, Jun 07 2006

			The set partitions of 3 are {1,1,1}, {1,1,2}, {1,2,1}, {1,2,2} and {1,2,3}. Summing these componentwise gives the third row: 5,8,9.
Table starts:
   1;
   2,  3;
   5,  8,   9;
  15, 25,  29,  31;
  52, 89, 106, 115, 120;
  ...

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A120058, A120095. First column is A000110.
Main diagonal is A087648(n-1).
Row sums give A346772.

b:= proc(n, m) option remember; `if`(n=0, [1, 0],
      add((p-> [p[1], expand(p[2]*x+p[1]*j)])(
        b(n-1, max(m, j))), j=1..m+1))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n-1))(b(n, 0)[2]):
seq(T(n), n=1..10);  # Alois P. Heinz, Mar 24 2016

b[n_, m_] := b[n, m] = If[n == 0, {1, 0}, Sum[Function[p, {p[[1]], p[[2]]*x + p[[1]]*j}][b[n-1, Max[m, j]]], {j, 1, m+1}]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n-1}]][b[n, 0][[2]]];
Table[T[n], {n, 1, 10}] // Flatten (* Jean-François Alcover, Apr 08 2016, after Alois P. Heinz *)

T(n,k) = Sum_{i=1..k} A120058(n,i)*B(n-i+1), where B(n) are the Bell numbers, (A000110).

A120095 Triangle T(n,k) = total of number at last index for all set partitions of n into k parts.

Original entry on oeis.org

1, 1, 2, 1, 5, 3, 1, 11, 15, 4, 1, 23, 57, 34, 5, 1, 47, 195, 200, 65, 6, 1, 95, 633, 1010, 550, 111, 7, 1, 191, 1995, 4704, 3850, 1281, 175, 8, 1, 383, 6177, 20874, 24255, 11886, 2646, 260, 9, 1, 767, 18915, 89800, 143115, 97272, 31458, 4992, 369, 10

Offset: 1

Franklin T. Adams-Watters, Jun 07 2006

			The set partitions of 4 objects into 2 parts are {1,1,1,2}, {1,1,2,1}, {1,1,2,2}, {1,2,1,1}, {1,2,1,2}, {1,2,2,1} and {1,2,2,2}. The last terms of these sum to 2+1+2+1+2+1+2 = 11, so T(4,2) = 11.
Table starts:
  1;
  1,  2;
  1,  5,   3;
  1, 11,  15,   4;
  1, 23,  57,  34,  5;
  1, 47, 195, 200, 65, 6;
  ...

Alois P. Heinz, Rows n = 1..150, flattened

Cf. A008277, A120058.

Row sums are A087648(n-1).

A120095:= func< n,k | (&+[Binomial(j+k,j+1)*StirlingSecond(n-1,k+j-1): j in [0..1]]) >;
[A120095(n,k): k in [1..n], n in [1..15]]; // G. C. Greubel, May 03 2023

b:= proc(n, m) option remember; `if`(n=0, 1, add((t->
     `if`(n=1, j*x^t, b(n-1, t)))(max(m, j)), j=1..m+1))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 0)):
seq(T(n), n=1..10);  # Alois P. Heinz, Aug 02 2021

b[n_, m_]:= b[n, m]= If[n==0, 1, Sum[
     If[n==1, j*x^#, b[n-1, #]]&[Max[m, j]], {j,m+1}]];
T[n_] := Table[Coefficient[#, x, i], {i, 1, n}]&[b[n, 0]];
Table[T[n], {n,10}]//Flatten (* Jean-François Alcover, Aug 19 2021, after Alois P. Heinz *)

def A120095(n,k):
    return sum(binomial(j+k,j+1)*stirling_number2(n-1,k+j-1) for j in range(2))
flatten([[A120095(n,k) for k in range(1,n+1)] for n in range(1,16)]) # G. C. Greubel, May 03 2023

T(n,k) = (k*(k+1)/2)*S2(n-1,k) + k*S2(n-1,k-1) = 1/2 (S2(n+1,k) + S2(n,k) - S2(n-1,k-2)) = k T(n-1,k) + T(n-1,k-1) + S2(n-2,k-2), where S2 is the Stirling numbers of the second kind (A008277).

cp's OEIS Frontend

A346520 Number A(n,k) of partitions of the (n+k)-multiset {0,...,0,1,2,...,k} with n 0's 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

A035098 Near-Bell numbers: partitions of an n-multiset with multiplicities 1, 1, 1, ..., 1, 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

A322770 Array read by upwards antidiagonals: T(m,n) = number of set partitions into distinct parts 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

Formula

A120057 Table T(n,k) = sum over all set partitions of n of number at index k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A120095 Triangle T(n,k) = total of number at last index for all set partitions of n into k parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula