

A000392


Stirling numbers of second kind S(n,3).
(Formerly M4167 N1734)


55



0, 0, 0, 1, 6, 25, 90, 301, 966, 3025, 9330, 28501, 86526, 261625, 788970, 2375101, 7141686, 21457825, 64439010, 193448101, 580606446, 1742343625, 5228079450, 15686335501, 47063200806, 141197991025, 423610750290, 1270865805301
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

Number of palindromic structures using exactly three different symbols; Mobius transform: A056279.  Marks R. Nester
Number of ways of placing n labeled balls into k=3 indistinguishable boxes.  Thomas Wieder, Nov 30 2004
With two leading zeros, this is the second binomial transform of cosh(x)1 and the binomial transform of A000225 (with extra leading zero).  Paul Barry, May 13 2003
Let [m] denote the first m positive integers. Then a(n) is the number of functions f from [n] to [n+1] that satisfy (i) f(x) > x for all x, (ii) f(x) = n+1 for exactly 3 elements and (iii) f(f(x)) = n+1 for the remaining n3 elements of [n]. For example, a(4)=6 since there are exactly 6 functions from {1,2,3,4} to {1,2,3,4,5} such that f(x) > x, f(x) = 5 for 3 elements and f(f(x)) = 5 for the remaining element. The functions are f1 = {(1,5), (2,5), (3,4), (4,5)}, f2 = {(1,5), (2,3), (3,5), (4,5)}, f3 = {(1,5), (2,4), (3,5), (4,5)}, f4 = {(1,2), (2,5), (3,5), (4,5)}, f5 = {(1,3), (2,5), (3,5), (4,5)}, f6 = {(1,4), (2,5), (3,5), (4,5)}.  Dennis P. Walsh, Feb 20 2007
Conjecture. Let S(1)={1} and, for n > 1, let S(n) be the smallest set containing x, 2x and 3x for each element x in S(n1). Then a(n+2) is the sum of the elements in S(n). (It is easy to prove that the number of elements in S(n) is the nth triangular number given by A001952.) See A122554 for a sequence defined in this way.  John W. Layman, Nov 21 2007; corrected (a(n) to a(n+2) due to offset change) by Fred Daniel Kline, Oct 02 2014
Let P(A) be the power set of an nelement set A. Then a(n+1) = the number of pairs of elements {x,y} of P(A) for which x and y are disjoint and for which x is not a subset of y and y is not a subset of x. Wieder calls these "disjoint strict 2combinations".  Ross La Haye, Jan 11 2008; corrected by Ross La Haye, Oct 29 2008
Also, let P(A) be the power set of an nelement set A. Then a(n+2) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which either x is a subset of y or y is a subset of x, or 1) x and y are disjoint and for which x is not a subset of y and y is not a subset of x, or 2) x and y are intersecting and for which either x is a proper subset of y or y is a proper subset of x.  Ross La Haye, Jan 11 2008
3 * a(n+1) = p(n+1) where p(x) is the unique degreen polynomial such that p(k) = a(k+1) for k = 0, 1, ..., n.  Michael Somos, Apr 29 2012
John W. Layman's conjecture that a(n+2) is the sum of elements in S(n) follows from the identification of S(n) with the first n rows of A036561, whose row sums are A001047.  Fred Daniel Kline, Oct 02 2014
From M. Sinan Kul, Sep 08 2016: (Start)
Let m be equal to the product of n1 distinct primes. Then a(n) is equal to the number of distinct fractions >=1 that may be created by dividing a divisor of m by another divisor. For example for m = 2*3*5 = 30, we would have the following 6 fractions: 6/5, 3/2, 5/3, 5/2, 10/3, 15/2.
Here finding the number of fractions would be equivalent to distributing n1 balls (distinct primes) to two bins (numerator and denominator) with no empty bins which can be found by Stirling numbers of the second kind. So another definition for a(n) is a(n) = Sum_{i=2..n1} Stirling2(i,2)*binomial(n1,i).
Also for n > 0, a(n) = (d(m^2)+1)/2  d(m) where m is equal to the product of n1 distinct primes. Example for a(5): m = 2*3*5*7 = 210 (product of four distinct primes) so a(5) = (d(210^2)+1)/2  d(210) = 41  16 = 25. (End)


REFERENCES

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 835.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 223.
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

T. D. Noe, Table of n, a(n) for n = 0..200
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Harry Crane, Leftright arrangements, set partitions, and pattern avoidance, Australasian Journal of Combinatorics, 61(1) (2015), 5772.
M. Griffiths, I. Mezo, A generalization of Stirling Numbers of the Second Kind via a special multiset, JIS 13 (2010) #10.2.5
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 346
Fred Kline and Peter Taylor, Partial sums of Nicomachus' Triangle rows produce Stirling numbers of the 2nd kind, MathStackExchange.  Fred Daniel Kline, Sep 22 2014
Ross La Haye, Binary Relations on the Power Set of an nElement Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.
Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.
Eric Weisstein's World of Mathematics, Minimal Cover.
Thomas Wieder, The number of certain kcombinations of an nset, Applied Mathematics Electronic Notes, vol. 8 (2008).
Index entries for linear recurrences with constant coefficients, signature (6,11,6).


FORMULA

G.f.: x^3/((1x)*(12*x)*(13*x)).
E.g.f.: ((exp(x)  1)^3) / 3!.
Recurrence: a(n+3) = 6*a(n+2)  11*a(n+1) + 6*a(n), a(3) = 1, a(4) = 6, a(5) = 25.  Thomas Wieder, Nov 30 2004
With offset 0, this is 9*3^n/2  4*2^n + 1/2, the partial sums of 3*3^n  2*2^n = A001047(n+1).  Paul Barry, Jun 26 2003
a(n) = (1 + 3^(n1)  2^n)/2, n > 0.  Dennis P. Walsh, Feb 20 2007
For n >= 3, a(n) = 3*a(n1) + 2^(n2)  1.  Geoffrey Critzer, Mar 03 2009
a(n) = 5*a(n1)  6*a(n2) + 1, for n > 3.  Vincenzo Librandi Nov 25 2010
a(n) = det(s(i+3,j+2), 1 <= i,j <= n3), where s(n,k) are Stirling numbers of the first kind.  Mircea Merca, Apr 06 2013
G.f.: x^3 + 12*x^4/(G(0)12*x), where G(k) = x+1 + 9*(3*x+1)*3^k  8*(2*x+1)*2^k  x*(9*3^k+18*2^k)*(81*3^k+132*2^k)/G(k+1) ; (continued fraction).  Sergei N. Gladkovskii, Feb 01 2014
a(n + 2) = (1  2^(2 + n) + 3^(1 + n))/2 for n > 0.  Fred Daniel Kline, Oct 02 2014
For n > 0, a(n) = (1/2) * Sum_{k=1..n1} Sum_{i=1..n1} C(nk1,i) * C(n1,k).  Wesley Ivan Hurt, Sep 22 2017


EXAMPLE

a(4) = 6. Let denote Z[i] the ith labeled element = "ball". Then one has for n=4 six different ways to fill sets = "boxes" with the labeled elements:
Set(Set(Z[3], Z[4]), Set(Z[1]), Set(Z[2])), Set(Set(Z[3], Z[1]), Set(Z[4]), Set(Z[2])), Set(Set(Z[4], Z[1]), Set(Z[3]), Set(Z[2])), Set(Set(Z[4]), Set(Z[1]), Set(Z[3], Z[2])), Set(Set(Z[3]), Set(Z[1], Z[2]), Set(Z[4])), Set(Set(Z[3]), Set(Z[1]), Set(Z[4], Z[2]))
G.f. = x^3 + 6*x^4 + 25*x^5 + 90*x^6 + 301*x^7 + 966*x^8 + 3025*x^9 + ...


MAPLE

A000392 := n > 9/2*3^n4*2^n+1/2; [ seq(9/2*3^n4*2^n+1/2, n=0..30) ]; # Thomas Wieder
A000392:=1/(z1)/(3*z1)/(2*z1); # Simon Plouffe in his 1992 dissertation.


MATHEMATICA

StirlingS2[Range[0, 30], 3] (* Harvey P. Dale, Dec 29 2011 *)


PROG

(PARI) {a(n) = 3^(n1) / 2  2^(n1) + 1/2};
(Sage) [stirling_number2(i, 3) for i in (0..40)] # Zerinvary Lajos, Jun 26 2008


CROSSREFS

Cf. A008277 (Stirling2 triangle), A007051, A056509, A000225.
Cf. A003462, A003463, A003464, A023000, A023001, A002452, A002275, A016123, A016125, A016256.
Cf. A028243, A122554.
Sequence in context: A056279 A055337 A001871 * A099948 A277973 A143815
Adjacent sequences: A000389 A000390 A000391 * A000393 A000394 A000395


KEYWORD

nonn,nice,easy


AUTHOR

N. J. A. Sloane


EXTENSIONS

Offset changed by N. J. A. Sloane, Feb 08 2008


STATUS

approved



