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
Examples
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)
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.
Crossrefs
Programs
-
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 *) -
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
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
Extensions
More terms from David Wasserman, Apr 22 2002
Comments