|
%I #101 Jun 18 2023 12:00:16
%S 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,
%T 6,1,877,1421,1092,525,175,42,7,1,4140,7016,5684,2912,1050,280,56,8,1,
%U 21147,37260,31572,17052,6552,1890,420,72,9,1,115975,211470,186300,105240,42630,13104,3150,600,90,10,1
%N Triangle read by rows: T(n,c) = number of successive equalities in set partitions of n.
%C 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.
%C 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
%C 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]
%C From David Pasino (davepasino(AT)yahoo.com), Apr 15 2009: (Start)
%C 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.
%C Also, S P S^-1 = (1/e)*exp(P). (End)
%C Exponential Riordan array [exp(exp(x)-1), x]. Equal to A007318*A124323. - _Paul Barry_, Apr 23 2009
%C Equal to A049020*A048994 as infinite lower triangular matrices. - _Philippe Deléham_, Nov 19 2011
%C 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
%C 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
%D W. C. Yang, Conjectures on some sequences involving set partitions and Bell numbers, preprint, 2000. [Apparently unpublished]
%H Alois P. Heinz, <a href="/A056857/b056857.txt">Rows n = 1..141, flattened</a>
%H H. W. Becker, <a href="http://www.jstor.org/stable/3029709">Rooks and rhymes</a>, Math. Mag., 22 (1948/49), 23-26. See Table III.
%H H. W. Becker, <a href="/A056857/a056857.pdf">Rooks and rhymes</a>, Math. Mag., 22 (1948/49), 23-26. [Annotated scanned copy]
%H Fufa Beyene, Jörgen Backelin, Roberto Mantaci, and Samuel A. Fufa, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Beyene/beyene13.html">Set Partitions and Other Bell Number Enumerated Objects</a>, J. Int. Seq., Vol. 26 (2023), Article 23.1.8.
%H A. Hennessy and Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry6/barry161.html">Generalized Stirling Numbers, Exponential Riordan Arrays, and Orthogonal Polynomials</a>, J. Int. Seq. 14 (2011) # 11.8.2, Corollary 17.
%H G. Hurst and A. Schultz, <a href="http://arxiv.org/abs/0906.0696">An elementary (number theory) proof of Touchard's congruence</a>, arXiv:0906.0696v2 [math.CO], 2009.
%H A. O. Munagi, <a href="http://dx.doi.org/10.1155/IJMMS.2005.451">Set partitions with successions and separations</a>, Intl. J. Math. Math. Sci. 2005 (2005) 451-463.
%H M. Spivey, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Spivey/spivey25.html">A generalized recurrence for Bell numbers</a>, J. Int. Seq., 11 (2008), no. 2, Article 08.2.5
%H W. Yang, <a href="http://dx.doi.org/10.1016/0012-365X(96)00034-9">Bell numbers and k-trees</a>, Disc. Math. 156 (1996) 247-252.
%F 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.
%F E.g.f.: exp(exp(x)+x*y-1). - _Vladeta Jovovic_, Feb 13 2003
%F 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
%F 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
%F 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
%e 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.
%e Triangle begins:
%e 1;
%e 1, 1;
%e 2, 2, 1;
%e 5, 6, 3, 1;
%e 15, 20, 12, 4, 1;
%e 52, 75, 50, 20, 5, 1;
%e 203, 312, 225, 100, 30, 6, 1;
%e ...
%e From _Paul Barry_, Apr 23 2009: (Start)
%e Production matrix is
%e 1, 1;
%e 1, 1, 1;
%e 1, 2, 1, 1;
%e 1, 3, 3, 1, 1;
%e 1, 4, 6, 4, 1, 1;
%e 1, 5, 10, 10, 5, 1, 1;
%e 1, 6, 15, 20, 15, 6, 1, 1;
%e 1, 7, 21, 35, 35, 21, 7, 1, 1;
%e 1, 8, 28, 56, 70, 56, 28, 8, 1, 1; ... (End)
%p 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
%p with(linalg): # Yields sequence in matrix form:
%p A056857_matrix := n -> subs(exp(1)=1, exponential(exponential(
%p matrix(n,n,[seq(seq(`if`(j=k+1,j,0),k=0..n-1),j=0..n-1)])))):
%p A056857_matrix(8); # _Peter Luschny_, Apr 18 2011
%t 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_ *)
%o (PARI)
%o B(n) = sum(k=0, n, stirling(n, k, 2));
%o tabl(nn)={for(n=1, nn, for(k=0, n - 1, print1(B(n - 1 - k) * binomial(n - 1, k),", ");); print(););};
%o tabl(12); \\ _Indranil Ghosh_, Mar 19 2017
%o (Python)
%o from sympy import bell, binomial
%o for n in range(1,12):
%o print([bell(n - 1 - k) * binomial(n - 1, k) for k in range(n)]) # _Indranil Ghosh_, Mar 19 2017
%o (SageMath)
%o def a(n): return (-1)^n / factorial(n)
%o @cached_function
%o def p(n, m):
%o R = PolynomialRing(QQ, "x")
%o if n == 0: return R(a(m))
%o return R((m + x)*p(n - 1, m) - (m + 1)*p(n - 1, m + 1))
%o for n in range(11): print(p(n, 0).list()) # _Peter Luschny_, Jun 18 2023
%Y Cf. Bell numbers A000110 (column c=0), A052889 (c=1), A105479 (c=2), A105480 (c=3).
%Y Cf. A056858-A056863. Essentially same as A056860, where the rows are read from right to left.
%Y Cf. also A007318, A005493, A270953.
%Y See A259691 for another version.
%Y T(2n+1,n+1) gives A124102.
%Y T(2n,n) gives A297926.
%K easy,nonn,tabl,nice
%O 1,4
%A Winston C. Yang (winston(AT)cs.wisc.edu), Aug 31 2000
%E More terms from _David Wasserman_, Apr 22 2002
|
