OFFSET
1,4
COMMENTS
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)
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
REFERENCES
W. C. Yang, Conjectures on some sequences involving set partitions and Bell numbers, preprint, 2000. [Apparently unpublished]
LINKS
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.
FORMULA
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
EXAMPLE
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)
MAPLE
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
MATHEMATICA
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 *)
PROG
(PARI)
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
(Python)
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
(SageMath)
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
KEYWORD
AUTHOR
Winston C. Yang (winston(AT)cs.wisc.edu), Aug 31 2000
EXTENSIONS
More terms from David Wasserman, Apr 22 2002
STATUS
approved