A056860 -id:A056860 - cp's OEIS frontend

A056857 Triangle read by rows: T(n,c) = number of successive equalities in set partitions of n.

1, 1, 1, 2, 2, 1, 5, 6, 3, 1, 15, 20, 12, 4, 1, 52, 75, 50, 20, 5, 1, 203, 312, 225, 100, 30, 6, 1, 877, 1421, 1092, 525, 175, 42, 7, 1, 4140, 7016, 5684, 2912, 1050, 280, 56, 8, 1, 21147, 37260, 31572, 17052, 6552, 1890, 420, 72, 9, 1, 115975, 211470, 186300, 105240, 42630, 13104, 3150, 600, 90, 10, 1

Offset: 1

Winston C. Yang (winston(AT)cs.wisc.edu), Aug 31 2000

Number of successive equalities s_i = s_{i+1} in a set partition {s_1, ..., s_n} of {1, ..., n}, where s_i is the subset containing i, s(1) = 1 and s(i) <= 1 + max of previous s(j)'s.
T(n,c) = number of set partitions of the set {1,2,...,n} in which the size of the block containing the element 1 is k+1. Example: T(4,2)=3 because we have 123|4, 124|3 and 134|2. - Emeric Deutsch, Nov 10 2006
Let P be the lower-triangular Pascal-matrix (A007318), Then this is exp(P) / exp(1). - Gottfried Helms, Mar 30 2007. [This comment was erroneously attached to A011971, but really belongs here. - N. J. A. Sloane, May 02 2015]
From David Pasino (davepasino(AT)yahoo.com), Apr 15 2009: (Start)
As an infinite lower-triangular matrix (with offset 0 rather than 1, so the entries would be B(n - c)*binomial(n, c), B() a Bell number, rather than B(n - 1 - c)*binomial(n - 1, c) as below), this array is S P S^-1 where P is the Pascal matrix A007318, S is the Stirling2 matrix A048993, and S^-1 is the Stirling1 matrix A048994.
Also, S P S^-1 = (1/e)*exp(P). (End)
Exponential Riordan array [exp(exp(x)-1), x]. Equal to A007318*A124323. - Paul Barry, Apr 23 2009
Equal to A049020*A048994 as infinite lower triangular matrices. - Philippe Deléham, Nov 19 2011
Build a superset Q[n] of set partitions of {1,2,...,n} by distinguishing "some" (possibly none or all) of the singletons. Indexed from n >= 0, 0 <= k <= n, T(n,k) is the number of elements in Q[n] that have exactly k distinguished singletons. A singleton is a subset containing one element. T(3,1) = 6 because we have {{1}'{2,3}}, {{1,2}{3}'}, {{1,3}{2}'}, {{1}'{2}{3}}, {{1}{2}'{3}}, {{1}{2}{3}'}. - Geoffrey Critzer, Nov 10 2012
Let Bell(n,x) denote the n-th Bell polynomial, the n-th row polynomial of A048993. Then this is the triangle of connection constants when expressing the basis polynomials Bell(n,x + 1) in terms of the basis polynomials Bell(n,x). For example, row 3 is (5, 6, 3, 1) and 5 + 6*Bell(1,x) + 3*Bell(2,x) + Bell(3,x) = 5 + 6*x + 3*(x + x^2) + (x + 3*x^2 + x^3) = 5 + 10*x + 6*x^2 + x^3 = (x + 1) + 3*(x + 1)^2 + (x + 1)^3 = Bell(3,x + 1). - Peter Bala, Sep 17 2013

			For example {1, 2, 1, 2, 2, 3} is a set partition of {1, 2, 3, 4, 5, 6} and has 1 successive equality, at i = 4.
Triangle begins:
    1;
    1,   1;
    2,   2,   1;
    5,   6,   3,   1;
   15,  20,  12,   4,   1;
   52,  75,  50,  20,   5,   1;
  203, 312, 225, 100,  30,   6,   1;
  ...
From _Paul Barry_, Apr 23 2009: (Start)
Production matrix is
  1,  1;
  1,  1,  1;
  1,  2,  1,  1;
  1,  3,  3,  1,  1;
  1,  4,  6,  4,  1,  1;
  1,  5, 10, 10,  5,  1,  1;
  1,  6, 15, 20, 15,  6,  1,  1;
  1,  7, 21, 35, 35, 21,  7,  1,  1;
  1,  8, 28, 56, 70, 56, 28,  8,  1,  1; ... (End)

W. C. Yang, Conjectures on some sequences involving set partitions and Bell numbers, preprint, 2000. [Apparently unpublished]

Alois P. Heinz, Rows n = 1..141, flattened
H. W. Becker, Rooks and rhymes, Math. Mag., 22 (1948/49), 23-26. See Table III.
H. W. Becker, Rooks and rhymes, Math. Mag., 22 (1948/49), 23-26. [Annotated scanned copy]
Fufa Beyene, Jörgen Backelin, Roberto Mantaci, and Samuel A. Fufa, Set Partitions and Other Bell Number Enumerated Objects, J. Int. Seq., Vol. 26 (2023), Article 23.1.8.
A. Hennessy and Paul Barry, Generalized Stirling Numbers, Exponential Riordan Arrays, and Orthogonal Polynomials, J. Int. Seq. 14 (2011) # 11.8.2, Corollary 17.
G. Hurst and A. Schultz, An elementary (number theory) proof of Touchard's congruence, arXiv:0906.0696v2 [math.CO], 2009.
A. O. Munagi, Set partitions with successions and separations, Intl. J. Math. Math. Sci. 2005 (2005) 451-463.
M. Spivey, A generalized recurrence for Bell numbers, J. Int. Seq., 11 (2008), no. 2, Article 08.2.5
W. Yang, Bell numbers and k-trees, Disc. Math. 156 (1996) 247-252.

Cf. Bell numbers A000110 (column c=0), A052889 (c=1), A105479 (c=2), A105480 (c=3).
Cf. A056858-A056863. Essentially same as A056860, where the rows are read from right to left.
Cf. also A007318, A005493, A270953.
See A259691 for another version.
T(2n+1,n+1) gives A124102.
T(2n,n) gives A297926.

with(combinat): A056857:=(n,c)->binomial(n-1,c)*bell(n-1-c): for n from 1 to 11 do seq(A056857(n,c),c=0..n-1) od; # yields sequence in triangular form; Emeric Deutsch, Nov 10 2006
with(linalg): # Yields sequence in matrix form:
A056857_matrix := n -> subs(exp(1)=1, exponential(exponential(
matrix(n,n,[seq(seq(`if`(j=k+1,j,0),k=0..n-1),j=0..n-1)])))):
A056857_matrix(8); # Peter Luschny, Apr 18 2011

t[n_, k_] := BellB[n-1-k]*Binomial[n-1, k]; Flatten[ Table[t[n, k], {n, 1, 11}, {k, 0, n-1}]](* Jean-François Alcover, Apr 25 2012, after Emeric Deutsch *)

B(n) = sum(k=0, n, stirling(n, k, 2));
tabl(nn)={for(n=1, nn, for(k=0, n - 1, print1(B(n - 1 - k) * binomial(n - 1, k),", ");); print(););};
tabl(12); \\ Indranil Ghosh, Mar 19 2017

from sympy import bell, binomial
for n in range(1,12):
    print([bell(n - 1 - k) * binomial(n - 1, k) for k in range(n)]) # Indranil Ghosh, Mar 19 2017

def a(n): return (-1)^n / factorial(n)
@cached_function
def p(n, m):
    R = PolynomialRing(QQ, "x")
    if n == 0: return R(a(m))
    return R((m + x)*p(n - 1, m) - (m + 1)*p(n - 1, m + 1))
for n in range(11): print(p(n, 0).list())  # Peter Luschny, Jun 18 2023

T(n,c) = B(n-1-c)*binomial(n-1, c), where T(n,c) is the number of set partitions of {1, ..., n} that have c successive equalities and B() is a Bell number.
E.g.f.: exp(exp(x)+x*y-1). - Vladeta Jovovic, Feb 13 2003
G.f.: 1/(1-xy-x-x^2/(1-xy-2x-2x^2/(1-xy-3x-3x^2/(1-xy-4x-4x^2/(1-... (continued fraction). - Paul Barry, Apr 23 2009
Considered as triangle T(n,k), 0 <= k <= n: T(n,k) = A007318(n,k)*A000110(n-k) and Sum_{k=0..n} T(n,k)*x^k = A000296(n), A000110(n), A000110(n+1), A005493(n), A005494(n), A045379(n) for x = -1, 0, 1, 2, 3, 4 respectively. - Philippe Deléham, Dec 13 2009
Let R(n,x) denote the n-th row polynomial of the triangle. Then A000110(n+j) = Bell(n+j,1) = Sum_{k = 1..n} R(j,k)*Stirling2(n,k) (Spivey). - Peter Bala, Sep 17 2013

More terms from David Wasserman, Apr 22 2002

A283424 Number T(n,k) of blocks of size >= k in all set partitions of [n], assuming that every set partition contains one block of size zero; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 2, 1, 5, 3, 1, 15, 10, 4, 1, 52, 37, 17, 5, 1, 203, 151, 76, 26, 6, 1, 877, 674, 362, 137, 37, 7, 1, 4140, 3263, 1842, 750, 225, 50, 8, 1, 21147, 17007, 9991, 4307, 1395, 345, 65, 9, 1, 115975, 94828, 57568, 25996, 8944, 2392, 502, 82, 10, 1

Offset: 0

Alois P. Heinz, May 14 2017

T(n,k) is defined for all n,k >= 0. The triangle contains only the terms with k<=n. T(n,k) = 0 for k>n.

			T(3,2) = 4 because the number of blocks of size >= 2 in all set partitions of [3] (123, 12|3, 13|2, 1|23, 1|2|3) is 1+1+1+1+0 = 4.
Triangle T(n,k) begins:
      1;
      2,     1;
      5,     3,    1;
     15,    10,    4,    1;
     52,    37,   17,    5,    1;
    203,   151,   76,   26,    6,   1;
    877,   674,  362,  137,   37,   7,  1;
   4140,  3263, 1842,  750,  225,  50,  8, 1;
  21147, 17007, 9991, 4307, 1395, 345, 65, 9, 1;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
Wikipedia, Partition of a set

Columns k=0-10 give: A000110(n+1), A138378 or A005493(n-1), A124325, A288785, A288786, A288787, A288788, A288789, A288790, A288791, A288792.
Row sums give A124427(n+1).
T(2n,n) gives A286896.
Cf. A005493, A056857, A056860, A070071, A224271, A285595.

T:= proc(n, k) option remember; `if`(k>n, 0,
      binomial(n, k)*combinat[bell](n-k)+T(n, k+1))
    end:
seq(seq(T(n, k), k=0..n), n=0..14);

T[n_, k_] := Sum[Binomial[n, j]*BellB[j], {j, 0, n - k}];
Table[T[n, k], {n, 0, 14}, {k, 0, n}] // Flatten (* Jean-François Alcover, Apr 30 2018 *)

T(n,k) = Sum_{j=0..n-k} binomial(n,j) * Bell(j).
T(n,k) = Bell(n+1) - Sum_{j=0..k-1} binomial(n,j) * Bell(n-j).
T(n,k) = Sum_{j=k..n} A056857(n+1,j) = Sum_{j=k..n} A056860(n+1,n+1-j).
Sum_{k=0..n} T(n,k) = n*Bell(n)+Bell(n+1) = A124427(n+1).
Sum_{k=1..n} T(n,k) = n*Bell(n) = A070071(n).
T(n,0)-T(n,1) = Bell(n).
Sum_{k=0..n} (-1)^k * T(n,k) = A224271(n+1). - Alois P. Heinz, May 17 2023

A297926 Number of set partitions of [2n] in which the size of the first block is n.

Original entry on oeis.org

1, 1, 6, 50, 525, 6552, 93786, 1504932, 26640900, 514083570, 10713538550, 239342496120, 5697111804566, 143759365731100, 3829115870472600, 107260549881604200, 3149703964487098665, 96686987797052290440, 3094969650442399156350, 103079905957566679518300

Offset: 0

Alois P. Heinz, Jan 08 2018

nonn

The blocks are ordered with increasing least elements.

a(0) = 1 by convention.

			a(1) = 1: 1|2.
a(2) = 6: 12|34, 12|3|4, 13|24, 13|2|4, 14|23, 14|2|3.

Alois P. Heinz, Table of n, a(n) for n = 0..445
Wikipedia, Partition of a set

Cf. A000110, A056857, A056860, A276961, A297924.

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

b[n_] := b[n] = If[n == 0, 1, Sum[b[n-j]*Binomial[n-1, j-1], {j, 1, n}]];
a[n_] := Binomial[2*n-1, n-1] * b[n];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, May 20 2018, translated from Maple *)

a(n) = binomial(2*n-1,n-1) * Bell(n).

a(n) = A056857(2n,n) = A056860(2n,n).

A175757 Triangular array read by rows: T(n,k) is the number of blocks of size k in all set partitions of {1,2,...,n}.

Original entry on oeis.org

1, 2, 1, 6, 3, 1, 20, 12, 4, 1, 75, 50, 20, 5, 1, 312, 225, 100, 30, 6, 1, 1421, 1092, 525, 175, 42, 7, 1, 7016, 5684, 2912, 1050, 280, 56, 8, 1, 37260, 31572, 17052, 6552, 1890, 420, 72, 9, 1, 211470, 186300, 105240, 42630, 13104, 3150, 600, 90, 10, 1

Offset: 1

Geoffrey Critzer, Dec 04 2010

The row sums of this triangle equal A005493. Equals A056857 without its leftmost column.

T(n,k) = binomial(n,k)*B(n-k) where B is the Bell number.

			The set {1,2,3} has 5 partitions, {{1, 2, 3}}, {{2, 3}, {1}}, {{1, 3}, {2}}, {{1, 2}, {3}}, and {{2}, {3}, {1}}, and there are a total of 3 blocks of size 2, so T(3,2)=3.
Triangle begins:
    1;
    2,   1;
    6,   3,   1;
   20,  12,   4,  1;
   75,  50,  20,  5, 1;
  312, 225, 100, 30, 6, 1;
  ...

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

Cf. A000110, A056860, A052889, A070071, A105479, A105480, A105481, A105482, A285595.

b:= proc(n) option remember; `if`(n=0, [1, 0],
      add((p-> p+[0, p[1]*x^j])(b(n-j)*
      binomial(n-1, j-1)), j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n)[2]):
seq(T(n), n=1..12);  # Alois P. Heinz, Apr 24 2017

Table[Table[Length[Select[Level[SetPartitions[m],{2}],Length[#]==n&]],{n,1,m}],{m,1,10}]//Grid

E.g.f. for column k is x^k/k!*exp(exp(x)-1).

Sum_{k=1..n} k * T(n,k) = A070071(n). - Alois P. Heinz, Mar 03 2020

A124102 a(n) = C(2n,n)*Bell(n).

Original entry on oeis.org

1, 2, 12, 100, 1050, 13104, 187572, 3009864, 53281800, 1028167140, 21427077100, 478684992240, 11394223609132, 287518731462200, 7658231740945200, 214521099763208400, 6299407928974197330, 193373975594104580880, 6189939300884798312700, 206159811915133359036600

Offset: 0

Zerinvary Lajos, Nov 26 2006

nonn

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

Cf. A000110, A056857, A056860.

with(combinat): a:=n->binomial(2*n,n)*bell(n): seq(a(n), n=0..20);

Table[Binomial[2n,n]*BellB[n],{n,0,20}] (* Harvey P. Dale, Apr 20 2012 *)

a(n) = A056857(2n+1,n+1) = A056860(2n+1,n+1). - Alois P. Heinz, May 25 2016

A055883 Exponential transform of Pascal's triangle A007318.

Original entry on oeis.org

1, 1, 1, 2, 4, 2, 5, 15, 15, 5, 15, 60, 90, 60, 15, 52, 260, 520, 520, 260, 52, 203, 1218, 3045, 4060, 3045, 1218, 203, 877, 6139, 18417, 30695, 30695, 18417, 6139, 877, 4140, 33120, 115920, 231840, 289800, 231840, 115920, 33120, 4140, 21147

Offset: 0

Christian G. Bower, Jun 09 2000

Triangle T(n,k), 0 <= k <= n, read by rows, given by [1, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, ...] DELTA [1, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Aug 10 2005

			   1;
   1,  1;
   2,  4,  2;
   5, 15, 15,  5;
  15, 60, 90, 60, 15;
  ...

N. J. A. Sloane, Transforms
Index entries for triangles and arrays related to Pascal's triangle

Cf. A000110, A007318, A056860.

Row sums give A055882.

T[ n_, k_] := Binomial[n, k] * BellB[n]; (* Michael Somos, Apr 09 2025 *)

T(n, k) = binomial(n, k) * sum(j=0, n, stirling(n, j, 2)); /* Michael Somos, Apr 09 2025 */

a(n,k) = Bell(n)*C(n,k).

E.g.f.: A(x,y) = exp(exp(x+xy)-1).

cp's OEIS Frontend

A056857 Triangle read by rows: T(n,c) = number of successive equalities in set partitions of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

SageMath

Formula

Extensions

A283424 Number T(n,k) of blocks of size >= k in all set partitions of [n], assuming that every set partition contains one block of size zero; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A297926 Number of set partitions of [2n] in which the size of the first block is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A175757 Triangular array read by rows: T(n,k) is the number of blocks of size k in all set partitions of {1,2,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A124102 a(n) = C(2n,n)*Bell(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A055883 Exponential transform of Pascal's triangle A007318.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A079005 Exponential transform of unsigned Lah-triangle |A008297(n,k)|.

Views

Author

Keywords