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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000392 Stirling numbers of second kind S(n,3).
(Formerly M4167 N1734)
53
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 (nesterm(AT)dpi.qld.gov.au)

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 n-3 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(n-1). 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 n-th 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 n-element 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 2-combinations". - Ross La Haye, Jan 11 2008; corrected by Ross La Haye, Oct 29 2008

Also, let P(A) be the power set of an n-element 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 degree-n 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 n-1 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 n-1 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..n-1} Stirling2(i,2)*binomial(n-1,i).

Also for n > 0, a(n) = (d(m^2)+1)/2 - d(m) where m is equal to the product of n-1 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.

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, Left-right arrangements, set partitions, and pattern avoidance, Australasian Journal of Combinatorics, 61(1) (2015), 57-72.

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 n-Element 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 k-combinations of an n-set, Applied Mathematics Electronic Notes, vol. 8 (2008).

Index entries for linear recurrences with constant coefficients, signature (6,-11,6).

FORMULA

G.f.: x^3/((1-x)*(1-2*x)*(1-3*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^(n-1)-2^n)/2, n>0. - Dennis P. Walsh, Feb 20 2007

For n>=3, a(n) = 3*a(n-1) + 2^(n-2) - 1. - Geoffrey Critzer, Mar 03 2009

a(n) = 5*a(n-1)-6*a(n-2)+1, for n>3. - Vincenzo Librandi Nov 25 2010

a(n) = det(|s(i+3,j+2)|, 1 <= i,j <= n-3), 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+1-8*2^k)*(81*3^k+1-32*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

EXAMPLE

a(4) = 6. Let denote Z[i] the i-th 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^n-4*2^n+1/2;  [ seq(9/2*3^n-4*2^n+1/2, n=0..30) ]; # Thomas Wieder

A000392:=-1/(z-1)/(3*z-1)/(2*z-1); # Simon Plouffe in his 1992 dissertation.

MATHEMATICA

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

PROG

(PARI) {a(n) = 3^(n-1) / 2 - 2^(n-1) + 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 A143815 A209241

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

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.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 29 14:57 EDT 2016. Contains 276614 sequences.