# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a000392
Showing 1-1 of 1
%I A000392 M4167 N1734 #216 Oct 24 2024 12:33:58
%S A000392 0,0,0,1,6,25,90,301,966,3025,9330,28501,86526,261625,788970,2375101,
%T A000392 7141686,21457825,64439010,193448101,580606446,1742343625,5228079450,
%U A000392 15686335501,47063200806,141197991025,423610750290,1270865805301
%N A000392 Stirling numbers of second kind S(n,3).
%C A000392 Number of palindromic structures using exactly three different symbols; Mobius transform: A056279. - _Marks R. Nester_
%C A000392 Number of ways of placing n labeled balls into k=3 indistinguishable boxes. - _Thomas Wieder_, Nov 30 2004
%C A000392 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
%C A000392 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
%C A000392 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
%C A000392 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
%C A000392 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
%C A000392 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
%C A000392 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
%C A000392 From _M. Sinan Kul_, Sep 08 2016: (Start)
%C A000392 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.
%C A000392 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).
%C A000392 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)
%C A000392 6*a(n) is the number of ternary strings of length n that contain at least one of each of the 3 symbols on which they are defined. For example, for n=4, the strings are the 12 permutations of 0012, the 12 permutations of 0112, and the 12 permutations of 0122. - _Enrique Navarrete_, Aug 23 2021
%C A000392 A simpler form of La Haye's first comment is: a(n+1) is the number of ways we can form disjoint unions of two nonempty subsets of [n] (see example below). Cf. A001047 for the requirement that the union contains n. - _Enrique Navarrete_, Aug 24 2021
%C A000392 As partial sums of the Nicomachus triangle's rows and the differences of the powers of 3 and 2 (A001047), each iteration corresponds to two figurate variations of the Sierpinski triangle (3^n) with cross-correlation to the Nicomachus triangle, see illustrations in links. The Sierpinski half-hexagons of (A001047) stack and conform to the footprint of 2^n - 1 triangular numbers. The 3^n Sierpinski triangle minus its 2^n bottom row, also correlates to the Nicomachus triangle according to each Sierpinski triangular sub-row. - _John Elias_, Oct 04 2021
%D A000392 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.
%D A000392 F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 223.
%D A000392 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]
%D A000392 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000392 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000392 T. D. Noe, Table of n, a(n) for n = 0..200
%H A000392 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].
%H A000392 Harry Crane, Left-right arrangements, set partitions, and pattern avoidance, Australasian Journal of Combinatorics, 61(1) (2015), 57-72.
%H A000392 John Elias, Illustration: Stirling-Sierpinski triangles, Nicomachus-Sierpinski towers
%H A000392 M. Griffiths and I. Mezo, A generalization of Stirling Numbers of the Second Kind via a special multiset, JIS 13 (2010) #10.2.5.
%H A000392 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 346
%H A000392 Fred Kline and Peter Taylor, Partial sums of Nicomachus' Triangle rows produce Stirling numbers of the 2nd kind, Mathematics Stack Exchange. - _Fred Daniel Kline_, Sep 22 2014
%H A000392 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.
%H A000392 Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A000392 Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
%H A000392 Anthony G. Shannon, Hakan Akkuş, Yeşim Aküzüm, Ömür Deveci, and Engin Özkan, A partial recurrence Fibonacci link, Notes Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 530-537. See Table 1, p. 531.
%H A000392 Kai Wang, Girard-Waring Type Formula For A Generalized Fibonacci Sequence, Fibonacci Quarterly (2020) Vol. 58, No. 5, 229-235.
%H A000392 Eric Weisstein's World of Mathematics, Minimal Cover.
%H A000392 Thomas Wieder, The number of certain k-combinations of an n-set, Applied Mathematics Electronic Notes, vol. 8 (2008).
%H A000392 Index entries for linear recurrences with constant coefficients, signature (6,-11,6).
%F A000392 G.f.: x^3/((1-x)*(1-2*x)*(1-3*x)).
%F A000392 E.g.f.: ((exp(x) - 1)^3) / 3!.
%F A000392 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
%F A000392 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
%F A000392 a(n) = (1 + 3^(n-1) - 2^n)/2, n > 0. - _Dennis P. Walsh_, Feb 20 2007
%F A000392 For n >= 3, a(n) = 3*a(n-1) + 2^(n-2) - 1. - _Geoffrey Critzer_, Mar 03 2009
%F A000392 a(n) = 5*a(n-1) - 6*a(n-2) + 1, for n > 3. - _Vincenzo Librandi_ Nov 25 2010
%F A000392 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
%F A000392 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
%F A000392 a(n + 2) = (1 - 2^(2 + n) + 3^(1 + n))/2 for n > 0. - _Fred Daniel Kline_, Oct 02 2014
%F A000392 For n > 0, a(n) = (1/2) * Sum_{k=1..n-1} Sum_{i=1..n-1} C(n-k-1,i) * C(n-1,k). - _Wesley Ivan Hurt_, Sep 22 2017
%F A000392 a(n) = Sum_{k=0..n-3} 2^(k-1)*(3^(n-2-k) - 1). - _J. M. Bergot_, Feb 05 2018
%e A000392 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:
%e A000392 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])).
%e A000392 G.f. = x^3 + 6*x^4 + 25*x^5 + 90*x^6 + 301*x^7 + 966*x^8 + 3025*x^9 + ...
%e A000392 For example, for n=3, a(4)=6 since the disjoint unions are: {1}U{2}, {1}U{3}, {1}U{2,3}, {2}U{3}, {2}U{1,3}, and {1,2}U{3}. - _Enrique Navarrete_, Aug 24 2021
%p A000392 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_
%p A000392 A000392:=-1/(z-1)/(3*z-1)/(2*z-1); # _Simon Plouffe_ in his 1992 dissertation
%t A000392 StirlingS2[Range[0,30],3] (* _Harvey P. Dale_, Dec 29 2011 *)
%o A000392 (PARI) {a(n) = 3^(n-1) / 2 - 2^(n-1) + 1/2};
%o A000392 (Sage) [stirling_number2(i,3) for i in (0..40)] # _Zerinvary Lajos_, Jun 26 2008
%o A000392 (GAP) List([0..400], n->Stirling2(n,3)); # _Muniru A Asiru_, Feb 04 2018
%Y A000392 Cf. A008277 (Stirling2 triangle), A007051, A056509, A000225.
%Y A000392 Cf. A003462, A003463, A003464, A023000, A023001, A002452, A002275, A016123, A016125, A016256.
%Y A000392 Cf. A028243, A122554.
%K A000392 nonn,nice,easy
%O A000392 0,5
%A A000392 _N. J. A. Sloane_
%E A000392 Offset changed by _N. J. A. Sloane_, Feb 08 2008
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE