login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A056857 Triangle T(n,c) of number of successive equalities in set partitions of n. 27
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 (list; table; graph; refs; listen; history; text; internal format)
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 1342. - Emeric Deutsch, Nov 10 2006

Contribution 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. [From Paul Barry, Apr 23 2009]

Equal to A049020*A048994 as infinite lower triangular matrices. - From 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

REFERENCES

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

LINKS

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

G. Hurst and A. Schultz, An elementary (number theory) proof of Touchard's congruence, arXiv:0906.0696v2 [math.CO]

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). [From 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<=k<=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. [From 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.

1;

1,1;

2,2,1;

5,6,3,1;

15,20,12,4,1;

52,75,50,20,5,1; ...

Contribution 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 *)

CROSSREFS

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.

Sequence in context: A118806 A171670 A124644 * A175579 A129100 A162382

Adjacent sequences:  A056854 A056855 A056856 * A056858 A056859 A056860

KEYWORD

easy,nonn,tabl,nice

AUTHOR

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

EXTENSIONS

More terms from David Wasserman, Apr 22 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified November 28 04:34 EST 2014. Contains 250286 sequences.