|
%I M4167 N1734 #212 Aug 29 2022 02:21:22
%S 0,0,0,1,6,25,90,301,966,3025,9330,28501,86526,261625,788970,2375101,
%T 7141686,21457825,64439010,193448101,580606446,1742343625,5228079450,
%U 15686335501,47063200806,141197991025,423610750290,1270865805301
%N Stirling numbers of second kind S(n,3).
%C Number of palindromic structures using exactly three different symbols; Mobius transform: A056279. - _Marks R. Nester_
%C Number of ways of placing n labeled balls into k=3 indistinguishable boxes. - _Thomas Wieder_, Nov 30 2004
%C 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 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 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 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 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 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 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 From _M. Sinan Kul_, Sep 08 2016: (Start)
%C 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 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 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 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 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 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 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 F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 223.
%D 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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A000392/b000392.txt">Table of n, a(n) for n = 0..200</a>
%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
%H Harry Crane, <a href="https://ajc.maths.uq.edu.au/pdf/61/ajc_v61_p057.pdf">Left-right arrangements, set partitions, and pattern avoidance</a>, Australasian Journal of Combinatorics, 61(1) (2015), 57-72.
%H John Elias, <a href="/A000392/a000392.png">Illustration: Stirling-Sierpinski triangles</a>, <a href="/A000392/a000392_1.png">Nicomachus-Sierpinski towers</a>
%H M. Griffiths and I. Mezo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Griffiths/griffiths11.html">A generalization of Stirling Numbers of the Second Kind via a special multiset</a>, JIS 13 (2010) #10.2.5.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=346">Encyclopedia of Combinatorial Structures 346</a>
%H Fred Kline and Peter Taylor, <a href="http://math.stackexchange.com/q/926105/28555">Partial sums of Nicomachus' Triangle rows produce Stirling numbers of the 2nd kind</a>, Mathematics Stack Exchange. - _Fred Daniel Kline_, Sep 22 2014
%H Ross La Haye, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/LaHaye/lahaye5.html">Binary Relations on the Power Set of an n-Element Set</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.
%H Kai Wang, <a href="https://www.fq.math.ca/Papers1/58-5/wang.pdf">Girard-Waring Type Formula For A Generalized Fibonacci Sequence</a>, Fibonacci Quarterly (2020) Vol. 58, No. 5, 229-235.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalCover.html">Minimal Cover</a>.
%H Thomas Wieder, <a href="http://www.math.nthu.edu.tw/~amen/2008/070301.pdf">The number of certain k-combinations of an n-set</a>, Applied Mathematics Electronic Notes, vol. 8 (2008).
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6,-11,6).
%F G.f.: x^3/((1-x)*(1-2*x)*(1-3*x)).
%F E.g.f.: ((exp(x) - 1)^3) / 3!.
%F 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 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 a(n) = (1 + 3^(n-1) - 2^n)/2, n > 0. - _Dennis P. Walsh_, Feb 20 2007
%F For n >= 3, a(n) = 3*a(n-1) + 2^(n-2) - 1. - _Geoffrey Critzer_, Mar 03 2009
%F a(n) = 5*a(n-1) - 6*a(n-2) + 1, for n > 3. - _Vincenzo Librandi_ Nov 25 2010
%F 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 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 a(n + 2) = (1 - 2^(2 + n) + 3^(1 + n))/2 for n > 0. - _Fred Daniel Kline_, Oct 02 2014
%F 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 a(n) = Sum_{k=0..n-3} 2^(k-1)*(3^(n-2-k) - 1). - _J. M. Bergot_, Feb 05 2018
%e 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 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 G.f. = x^3 + 6*x^4 + 25*x^5 + 90*x^6 + 301*x^7 + 966*x^8 + 3025*x^9 + ...
%e 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 := 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:=-1/(z-1)/(3*z-1)/(2*z-1); # _Simon Plouffe_ in his 1992 dissertation
%t StirlingS2[Range[0,30],3] (* _Harvey P. Dale_, Dec 29 2011 *)
%o (PARI) {a(n) = 3^(n-1) / 2 - 2^(n-1) + 1/2};
%o (Sage) [stirling_number2(i,3) for i in (0..40)] # _Zerinvary Lajos_, Jun 26 2008
%o (GAP) List([0..400], n->Stirling2(n,3)); # _Muniru A Asiru_, Feb 04 2018
%Y Cf. A008277 (Stirling2 triangle), A007051, A056509, A000225.
%Y Cf. A003462, A003463, A003464, A023000, A023001, A002452, A002275, A016123, A016125, A016256.
%Y Cf. A028243, A122554.
%K nonn,nice,easy
%O 0,5
%A _N. J. A. Sloane_
%E Offset changed by _N. J. A. Sloane_, Feb 08 2008
|
