Displaying 1-10 of 33 results found.
a(n) = BS2(n) * W(n) where BS2 = sum_{k=0..n} ((-1)^k*k!/(k+1)) S_{2}(n, k) and S_{2}(n, k) are the Stirling-Frobenius subset numbers A039755(n, k). W(n) = product{p primes <= n+1 such that p divides n+1 or p-1 divides n} = A225481(n).
+20
3
1, 1, -2, -2, 14, 33, -62, -132, 254, 14585, -5110, -313266, 2828954, 38669001, -573370, -404801672, 237036478, 117650567067, -11499383114, -24255028327410, 1281647882998, 8203584532193105, -3584085584926, -418397193140056356, 3965530936622474, 405233976502715850633
COMMENTS
a(n)/ A225481(n) is case m = 2 of the scaled generalized Bernoulli numbers defined as Sum_{k=0..n} ((-1)^k*k!/(k+1)) S_{m}(n, k) where S_{m}(n, k) are Stirling-Frobenius subset numbers. A225481(n) can be seen as an analog of the Clausen numbers A141056(n).
EXAMPLE
The numerators of 1/1, 1/2, -2/6, -2/2, 14/30, 33/6, -62/42, -132/2, 254/30, 14585/10, -5110/66, ...(the denominators are A225481(n)).
MATHEMATICA
EulerianNumber[n_, k_, m_] := EulerianNumber[n, k, m] = If[n == 0, If[k == 0, 1 , 0], (m*(n-k) + m - 1)*EulerianNumber[n-1, k-1, m] + (m*k + 1)* EulerianNumber[n-1, k, m]];
BS[n_, m_] := Sum[Sum[EulerianNumber[n, j, m]*Binomial[j, n-k], {j, 0, n}]/ ((-m)^k*(k+1)), {k, 0, n}]
a[n_] := Product[If[Divisible[n+1, p] || Divisible[n, p-1], p, 1], {p, Prime /@ Range @ PrimePi[n+1]}] * BS[n, 2];
PROG
(Sage)
@CachedFunction
def EulerianNumber(n, k, m) : # The Eulerian numbers
if n == 0: return 1 if k == 0 else 0
return ((m*(n-k)+m-1)*EulerianNumber(n-1, k-1, m) +
(m*k+1)*EulerianNumber(n-1, k, m))
@CachedFunction
def BS(n, m): # The generalized scaled Bernoulli numbers
return (add(add(EulerianNumber(n, j, m)*binomial(j, n - k)
for j in (0..n))/((-m)^k*(k+1)) for k in (0..n)))
C = mul(filter(lambda p: ((n+1)%p == 0) or (n%(p-1) == 0), primes(n+2)))
return C*BS(n, 2)
Array T(n,k) read by antidiagonals: the k-th column contains the first column of the k-th power of A039755.
+20
1
1, 1, 1, 1, 2, 1, 1, 3, 6, 1, 1, 4, 15, 24, 1, 1, 5, 28, 105, 116, 1, 1, 6, 45, 280, 929, 648, 1, 1, 7, 66, 585, 3600, 9851, 4088, 1, 1, 8, 91, 1056, 9865, 56240, 121071, 28640, 1
FORMULA
Let A039755 (an analog of Stirling numbers of the second kind) be an infinite lower triangular matrix M; then the vector M^k * [1, 0, 0, 0, ...] (first column of the k-th power) is the k-th column of this array.
EXAMPLE
1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8
1 6 15 28 45 66 91 120
1 24 105 280 585 1056 1729 2640
1 116 929 3600 9865 22036 43001 76224
1 648 9851 56240 203565 565096 1318023 2717856
1 4088 121071 1029920 4953205 17148936 47920803 115146816
1 28640 1685585 21569600 138529105 600001696 2012844225 5644055040
MAPLE
local A, i, j ;
A := Matrix(n, n) ;
for i from 1 to n do
for j from 1 to n do
end do:
end do:
LinearAlgebra[MatrixPower](A, k) ;
%[n, 1] ;
end proc:
for d from 2 to 12 do
for n from 1 to d-1 do
end do:
MATHEMATICA
nmax = 10;
A[n_, k_] := Sum[(-1)^(k-j)*(2j+1)^n*Binomial[k, j], {j, 0, k}]/(2^k*k!);
A039755 = Array[A, {nmax, nmax}, {0, 0}];
T = Table[MatrixPower[ A039755, n][[All, 1]], {n, 1, nmax}] // Transpose;
Column k=4 of triangle A039755, Sheffer(exp(x), (exp(2*x) - 1)/2).
+20
1
1, 25, 395, 5075, 58086, 618870, 6289690, 61885450, 595122671, 5629238615, 52605474285, 487197745125, 4481780785756, 41018845739260, 373968405050180, 3399402534376100, 30830907772159341, 279134548584080805, 2523817507756513375, 22795663165336810375, 205730405672107235426, 1855561201430080303250, 16727971116048518559870, 150747219419372400319950, 1358093516662781192486011
COMMENTS
For a combinatorial interpretation following from the g.f. and the a(n) = h^{(5)}_n formula below see A039755.
FORMULA
G.f.: 1/Product_{j=0..4}(1 - (1+2*j)*x).
E.g.f.: (d^4/dx^4)(exp(x)*((exp(2*x)-1)/2)^4/4!) = (2187/128)*exp(9*x) - (2401/96)*exp(7*x) + (625/64)*exp(5*x) - (27/32)*exp(3*x) + (1/384)*exp(x).
a(n) = h^{(5)}_n, the complete homogeneous symmetric function of degree n of the five symbols 1, 3, 5, 7, 9.
G.f.: 1 / ((1 - x)*(1 - 3*x)*(1 - 5*x)*(1 - 7*x)*(1 - 9*x)).
a(n) = (1 - 4*3^(4+n) + 6*5^(4+n) - 4*7^(4+n) + 9^(4+n)) / 384.
a(n) = 25*a(n-1) - 230*a(n-2) + 950*a(n-3) - 1689*a(n-4) + 945*a(n-5) for n>4.
(End)
EXAMPLE
a(2) = h^{(5)}_2 = 1^2 + 3^2 + 5^2 + 7^2 + 9^2 + 1^1*(3^1 + 5^1 + 7^1 + 9^1) + 3^1*(5^1 + 7^1 + 9^1) + 5^1*(7^1 + 9^1) + 7^1*9^1 = 165 + 230 = 395. The multichoose(5, 2) = binomial(6, 2) = 15 polytopes are five squares and ten rectangles of total area 165 and 230, respectively.
PROG
(PARI) Vec(1 / ((1 - x)*(1 - 3*x)*(1 - 5*x)*(1 - 7*x)*(1 - 9*x)) + O(x^40)) \\ Colin Barker, Dec 23 2017
Triangle of Stirling numbers of the second kind, S2(n,k), n >= 1, 1 <= k <= n.
+10
638
1, 1, 1, 1, 3, 1, 1, 7, 6, 1, 1, 15, 25, 10, 1, 1, 31, 90, 65, 15, 1, 1, 63, 301, 350, 140, 21, 1, 1, 127, 966, 1701, 1050, 266, 28, 1, 1, 255, 3025, 7770, 6951, 2646, 462, 36, 1, 1, 511, 9330, 34105, 42525, 22827, 5880, 750, 45, 1, 1, 1023, 28501, 145750, 246730, 179487, 63987, 11880, 1155, 55, 1
COMMENTS
Also known as Stirling set numbers and written {n, k}.
S2(n,k) counts partitions of an n-set into k nonempty subsets.
With regard to the preceding comment: For arbitrary (including non-disjoint) covers of an n-set by k nonempty subsets see A055154. - Manfred Boergens, May 20 2024 Triangle S2(n,k), 1 <= k <= n, read by rows, given by [0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...] where DELTA is Deléham's operator defined in A084938. Number of partitions of {1, ..., n+1} into k+1 nonempty subsets of nonconsecutive integers, including the partition 1|2|...|n+1 if n=k. E.g., S2(3,2)=3 since the number of partitions of {1,2,3,4} into three subsets of nonconsecutive integers is 3, i.e., 13|2|4, 14|2|3, 1|24|3. - Augustine O. Munagi, Mar 20 2005 Draw n cards (with replacement) from a deck of k cards. Let prob(n,k) be the probability that each card was drawn at least once. Then prob(n,k) = S2(n,k)*k!/k^n (see A090582). - Rainer Rosenthal, Oct 22 2005 Define f_1(x), f_2(x), ..., such that f_1(x)=e^x and for n = 2, 3, ..., f_{n+1}(x) = (d/dx)(x*f_n(x)). Then f_n(x) = e^x*Sum_{k=1..n} S2(n,k)*x^(k-1). - Milan Janjic, May 30 2008 For tables of restricted Stirling numbers of the second kind see A143494 - A143496. S2(n,k) gives the number of 'patterns' of words of length n using k distinct symbols - see [Cooper & Kennedy] for an exact definition of the term 'pattern'. As an example, the words AADCBB and XXEGTT, both of length 6, have the same pattern of letters. The five patterns of words of length 3 are AAA, AAB, ABA, BAA and ABC giving row 3 of this table as (1,3,1).
Equivalently, S2(n,k) gives the number of sequences of positive integers (N_1,...,N_n) of length n, with k distinct entries, such that N_1 = 1 and N_(i+1) <= 1 + max{j = 1..i} N_j for i >= 1 (restricted growth functions). For example, Stirling(4,2) = 7 since the sequences of length 4 having 2 distinct entries that satisfy the conditions are (1,1,1,2), (1,1,2,1), (1,2,1,1), (1,1,2,2), (1,2,2,2), (1,2,2,1) and (1,2,1,2).
(End)
Number of combinations of subsets in the plane. - Mats Granvik, Jan 13 2009 S2(n+1,k+1) is the number of size k collections of pairwise disjoint, nonempty subsets of [n]. For example: S2(4,3)=6 because there are six such collections of subsets of [3] that have cardinality two: {(1)(23)},{(12)(3)}, {(13)(2)}, {(1)(2)}, {(1)(3)}, {(2)(3)}. - Geoffrey Critzer, Apr 06 2009 Consider a set of A000217(n) balls of n colors in which, for each integer k = 1 to n, exactly one color appears in the set a total of k times. (Each ball has exactly one color and is indistinguishable from other balls of the same color.) a(n+1, k+1) equals the number of ways to choose 0 or more balls of each color in such a way that exactly (n-k) colors are chosen at least once, and no two colors are chosen the same positive number of times. - Matthew Vandermast, Nov 22 2010 S2(n,k) is the number of monotonic-labeled forests on n vertices with exactly k rooted trees, each of height one or less. See link "Counting forests with Stirling and Bell numbers" below. - Dennis P. Walsh, Nov 16 2011 If D is the operator d/dx, and E the operator xd/dx, Stirling numbers are given by: E^n = Sum_{k=1..n} S2(n,k) * x^k*D^k. - Hyunwoo Jang, Dec 13 2011
The Stirling polynomials of the second kind (a.k.a. the Bell / Touchard polynomials) are the umbral compositional inverses of the falling factorials (a.k.a. the Pochhammer symbol or Stirling polynomials of the first kind), i.e., binomial(Bell(.,x),n) = x^n/n! (cf. Copeland's 2007 formulas), implying binomial(xD,n) = binomial(Bell(.,:xD:),n) = :xD:^n/n! where D = d/dx and :xD:^n = x^n*D^n. - Tom Copeland, Apr 17 2014 S2(n,k) is the number of ways to nest n matryoshkas (Russian nesting dolls) so that exactly k matryoshkas are not contained in any other matryoshka. - Carlo Sanna, Oct 17 2015 The row polynomials R(n, x) = Sum_{k=1..n} S2(n, k)*x^k appear in the numerator of the e.g.f. of n-th powers, E(n, x) = Sum_{m>=0} m^n*x^m/m!, as E(n, x) = exp(x)*x*R(n, x), for n >= 1. - Wolfdieter Lang, Apr 02 2017 With offsets 0 for n and k this is the Sheffer product matrix A007318* A048993 denoted by (exp(t), (exp(t) - 1)) with e.g.f. exp(t)*exp(x*(exp(t) - 1)). - Wolfdieter Lang, Jun 20 2017 Number of words on k+1 unlabeled letters of length n+1 with no repeated letters. - Thomas Anton, Mar 14 2019 Also coefficients of moments of Poisson distribution about the origin expressed as polynomials in lambda. [Haight] (see also A331155). - N. J. A. Sloane, Jan 14 2020 k!*S2(n,k) is the number of surjections from an n-element set to a k-element set. - Jianing Song, Jun 01 2022
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.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 103ff.
B. A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
G. Boole, Finite Differences, 5th ed. New York, NY: Chelsea, 1970.
C. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, 2002, Theorem 8.11, pp. 298-299.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 310.
J. H. Conway and R. K. Guy, The Book of Numbers, Springer, p. 92.
F. N. David, M. G. Kendall, and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 223.
S.N. Elaydi, An Introduction to Difference Equations, 3rd ed. Springer, 2005.
H. H. Goldstine, A History of Numerical Analysis, Springer-Verlag, 1977; Section 2.7.
R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 244.
Frank Avery Haight, Handbook of the Poisson distribution, John Wiley, 1967. See pages 6,7.
A. D. Korshunov, Asymptotic behavior of Stirling numbers of the second kind. (Russian) Metody Diskret. Analiz. No. 39 (1983), 24-41.
E. Kuz'min and A. I. Shirshov: On the number e, pp. 111-119, eq.(6), in: Kvant Selecta: Algebra and Analysis, I, ed. S. Tabachnikov, Am.Math.Soc., 1999, p. 116, eq. (11).
J. Riordan, An Introduction to Combinatorial Analysis, p. 48.
J. Stirling, The Differential Method, London, 1749; see p. 7.
LINKS
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]. T. Copeland's Shadows of Simplicity, A Class of Differential Operators and the Stirling Numbers,2015; Generators, Inversion, and Matrix, Binomial, and Integral Transforms, 2015; The Inverse Mellin Transform, Bell Polynomials, a Generalized Dobinski Relation, and the Confluent Hypergeometric Functions, 2011; Mathemagical Forests, 2008; and Addendum to "Mathemagical Forests", 2010.
FORMULA
S2(n, k) = k*S2(n-1, k) + S2(n-1, k-1), n > 1. S2(1, k) = 0, k > 1. S2(1, 1) = 1.
E.g.f.: A(x, y) = e^(y*e^x-y). E.g.f. for m-th column: (e^x-1)^m/m!.
S2(n, k) = (1/k!) * Sum_{i=0..k} (-1)^(k-i)*binomial(k, i)*i^n.
Row sums: Bell number A000110(n) = Sum_{k=1..n} S2(n, k), n>0. S(n, k) = Sum (i_1*i_2*...*i_(n-k)) summed over all (n-k)-combinations {i_1, i_2, ..., i_k} with repetitions of the numbers {1, 2, ..., k}. Also S(n, k) = Sum (1^(r_1)*2^(r_2)*...* k^(r_k)) summed over integers r_j >= 0, for j=1..k, with Sum{j=1..k} r_j = n-k. [Charalambides]. - Wolfdieter Lang, Aug 15 2019. For asymptotics see Hsu (1948), among other sources.
Sum_{n>=0} S2(n, k)*x^n = x^k/((1-x)(1-2x)(1-3x)...(1-kx)).
Let P(n) = the number of integer partitions of n ( A000041), p(i) = the number of parts of the i-th partition of n, d(i) = the number of distinct parts of the i-th partition of n, p(j, i) = the j-th part of the i-th partition of n, m(i, j) = multiplicity of the j-th part of the i-th partition of n, and Sum_{i=1..P(n), p(i)=m} = sum running from i=1 to i=P(n) but taking only partitions with p(i)=m parts into account. Then S2(n, m) = Sum_{i=1..P(n), p(i)=m} n!/(Product_{j=1..p(i)} p(i, j)!) * 1/(Product_{j=1..d(i)} m(i, j)!). For example, S2(6, 3) = 90 because n=6 has the following partitions with m=3 parts: (114), (123), (222). Their complexions are: (114): 6!/(1!*1!*4!) * 1/(2!*1!) = 15, (123): 6!/(1!*2!*3!) * 1/(1!*1!*1!) = 60, (222): 6!/(2!*2!*2!) * 1/(3!) = 15. The sum of the complexions is 15+60+15 = 90 = S2(6, 3). - Thomas Wieder, Jun 02 2005 Sum_{k=1..n} k*S2(n,k) = B(n+1)-B(n), where B(q) are the Bell numbers ( A000110). - Emeric Deutsch, Nov 01 2006 Recurrence: S2(n+1,k) = Sum_{i=0..n} binomial(n,i)*S2(i,k-1). With the starting conditions S2(n,k) = 1 for n = 0 or k = 1 and S2(n,k) = 0 for k = 0 we have the closely related recurrence S2(n,k) = Sum_{i=k..n} binomial(n-1,i-1)*S2(i-1,k-1). - Thomas Wieder, Jan 27 2007 Representation of Stirling numbers of the second kind S2(n,k), n=1,2,..., k=1,2,...,n, as special values of hypergeometric function of type (n)F(n-1): S2(n,k)= (-1)^(k-1)*hypergeom([ -k+1,2,2,...,2],[1,1,...,1],1)/(k-1)!, i.e., having n parameters in the numerator: one equal to -k+1 and n-1 parameters all equal to 2; and having n-1 parameters in the denominator all equal to 1 and the value of the argument equal to 1. Example: S2(6,k)= seq(evalf((-1)^(k-1)*hypergeom([ -k+1,2,2,2,2,2],[1,1,1,1,1],1)/(k-1)!),k=1..6)=1,31,90,65,15,1. - Karol A. Penson, Mar 28 2007 Bell_n(x) = Sum_{j=0..n} S2(n,j) * x^j = Sum_{j=0..n} E(n,j) * Lag(n,-x, j-n) = Sum_{j=0..n} (E(n,j)/n!) * (n!*Lag(n,-x, j-n)) = Sum_{j=0..n} E(n,j) * binomial(Bell.(x)+j, n) umbrally where Bell_n(x) are the Bell / Touchard / exponential polynomials; S2(n,j), the Stirling numbers of the second kind; E(n,j), the Eulerian numbers; and Lag(n,x,m), the associated Laguerre polynomials of order m.
For x = 0, the equation gives Sum_{j=0..n} E(n,j) * binomial(j,n) = 1 for n=0 and 0 for all other n. By substituting the umbral compositional inverse of the Bell polynomials, the lower factorial n!*binomial(y,n), for x in the equation, the Worpitzky identity is obtained; y^n = Sum_{j=0..n} E(n,j) * binomial(y+j,n).
Note that E(n,j)/n! = E(n,j)/(Sum_{k=0..n}E(n,k)). Also (n!*Lag(n, -1, j-n)) is A086885 with a simple combinatorial interpretation in terms of seating arrangements, giving a combinatorial interpretation to the equation for x=1; n!*Bell_n(1) = n!*Sum_{j=0..n} S2(n,j) = Sum_{j=0..n} E(n,j) * (n!*Lag(n, -1, j-n)). (Appended Sep 16 2020) For connections to the Bernoulli numbers, extensions, proofs, and a clear presentation of the number arrays involved in the identities above, see my post Reciprocity and Umbral Witchcraft. (End)
n-th row = leftmost column of nonzero terms of A127701^(n-1). Also, (n+1)-th row of the triangle = A127701 * n-th row; deleting the zeros. Example: A127701 * [1, 3, 1, 0, 0, 0, ...] = [1, 7, 6, 1, 0, 0, 0, ...]. - Gary W. Adamson, Nov 21 2007 The row polynomials are given by D^n(e^(x*t)) evaluated at x = 0, where D is the operator (1+x)*d/dx. Cf. A147315 and A094198. See also A185422. - Peter Bala, Nov 25 2011 O.g.f. for the n-th diagonal is D^n(x), where D is the operator x/(1-x)*d/dx. - Peter Bala, Jul 02 2012 n*i!*S2(n-1,i) = Sum_{j=(i+1)..n} (-1)^(j-i+1)*j!/(j-i)*S2(n,j). - Leonid Bedratyuk, Aug 19 2012 G.f.: (1/Q(0)-1)/(x*y), where Q(k) = 1 - (y+k)*x - (k+1)*y*x^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 09 2013 Multiply each n-th diagonal of the Pascal lower triangular matrix by x^n and designate the result as A007318(x) = P(x). With Bell(n,x)=B(n,x) defined above, D = d/dx, and :xD:^n = x^n*D^n, a Dobinski formula gives umbrally f(y)^B(.,x) = e^(-x)*e^(f(y)*x). Then f(y)^B(.,:xD:)g(x) = [f(y)^(xD)]g(x) = e^[-(1-f(y)):xD:]g(x) = g[f(y)x].
In particular, for f(y) = (1+y),
A) (1+y)^B(.,x) = e^(-x)*e^((1+y)*x) = e^(x*y) = e^[log(1+y)B(.,x)],
B) (I+dP)^B(.,x) = e^(x*dP) = P(x) = e^[x*(e^M-I)]= e^[M*B(.,x)] with dP = A132440, M = A238385-I = log(I+dP), and I = identity matrix, and C) (1+dP)^(xD) = e^(dP:xD:) = P(:xD:) = e^[(e^M-I):xD:] = e^[M*xD] with action e^(dP:xD:)g(x) = g[(I+dP)*x].
D) P(x)^m = P(m*x), which implies (Sum_{k=1..m} a_k)^j = B(j,m*x) where the sum is umbrally evaluated only after exponentiation with (a_k)^q = B(.,x)^q = B(q,x). E.g., (a1+a2+a3)^2=a1^2+a2^2+a3^2+2(a1*a2+a1*a3+a2*a3) = 3*B(2,x)+6*B(1,x)^2 = 9x^2+3x = B(2,3x).
E) P(x)^2 = P(2x) = e^[M*B(.,2x)] = A038207(x), the face vectors of the n-Dim hypercubes. (End)
As a matrix equivalent of some inversions mentioned above, A008277* A008275 = I, the identity matrix, regarded as lower triangular matrices. - Tom Copeland, Apr 26 2014 O.g.f. for the n-th diagonal of the triangle (n = 0,1,2,...): Sum_{k>=0} k^(k+n)*(x*e^(-x))^k/k!. Cf. the generating functions of the diagonals of A039755. Also cf. A112492. - Peter Bala, Jun 22 2014 Floor(1/(-1 + Sum_{n>=k} 1/S2(n,k))) = A034856(k-1), for k>=2. The fractional portion goes to zero at large k. - Richard R. Forberg, Jan 17 2015 Let x_(n), called a factorial term (Boole, 1970) or a factorial polynomial (Elaydi, 2005: p. 60), denote the falling factorial Product_{k=0..n-1} (x-k). Then, for n >= 1, x_(n) = Sum_{k=1..n} A008275(n,k) * x^k, x^n = Sum_{k=1..n} T(n,k) * x_(k), where A008275(n,k) are Stirling numbers of the first kind. For n >= 1, the row sums yield the exponential numbers (or Bell numbers): Sum_{k=1..n} T(n,k) = A000110(n), and Sum_{k=1..n} (-1)^(n+k) * T(n,k) = (-1)^n * Sum_{k=1..n} (-1)^k * T(n,k) = (-1)^n * A000587(n), where A000587 are the complementary Bell numbers. (End) O.g.f. for the m-th column: x^m/(Product_{j=1..m} 1-j*x). - Daniel Checa, Aug 25 2022 S2(n,k) ~ (k^n)/k!, for fixed k as n->oo. - Daniel Checa, Nov 08 2022 S2(2n+k, n) ~ (2^(2n+k-1/2) * n^(n+k-1/2)) / (sqrt(Pi*(1-c)) * exp(n) * c^n * (2-c)^(n+k)), where c = -LambertW(-2 * exp(-2)). - Miko Labalan, Dec 21 2024
EXAMPLE
The triangle S2(n, k) begins:
\ k 1 2 3 4 5 6 7 8 9
n \ 10 11 12 13 14 15 ...
----------------------------------------------------------------------------------
1 | 1
2 | 1 1
3 | 1 3 1
4 | 1 7 6 1
5 | 1 15 25 10 1
6 | 1 31 90 65 15 1
7 | 1 63 301 350 140 21 1
8 | 1 127 966 1701 1050 266 28 1
9 | 1 255 3025 7770 6951 2646 462 36 1
10 | 1 511 9330 34105 42525 22827 5880 750 45
1
11 | 1 1023 28501 145750 246730 179487 63987 11880 1155
55 1
12 | 1 2047 86526 611501 1379400 1323652 627396 159027 22275
1705 66 1
13 | 1 4095 261625 2532530 7508501 9321312 5715424 1899612 359502
39325 2431 78 1
14 | 1 8191 788970 10391745 40075035 63436373 49329280 20912320 5135130
752752 66066 3367 91 1
15 | 1 16383 2375101 42355950 210766920 420693273 408741333 216627840 67128490
12662650 1479478 106470 4550 105 1
...
----------------------------------------------------------------------------------
x^4 = 1 x_(1) + 7 x_(2) + 6 x_(3) + 1 x_(4), where x_(k) = P(x,k) = k!*C(x,k). - Daniel Forgues, Jan 16 2016
MAPLE
seq(seq(combinat[stirling2](n, k), k=1..n), n=1..10); # Zerinvary Lajos, Jun 02 2007 stirling_2 := (n, k) -> (1/k!) * add((-1)^(k-i)*binomial(k, i)*i^n, i=0..k);
MATHEMATICA
BellMatrix[f_, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
rows = 12;
B = BellMatrix[1&, rows];
a[n_, n_] := 1; a[n_, 1] := 1;
a[n_, k_] := a[n, k] = a[n-1, k-1] + k a[n-1, k]; Flatten@
Table[a[n, k], {n, 1, 11}, {k, 1, n}] (* Oliver Seipel, Jun 12 2024 *) With[{m = 11},
Flatten@MapIndexed[Take[#, #2[[1]]] &,
Transpose@
Table[Range[1, m]! Coefficient[(E^x-1)^k/k! + O[x]^(m+1), x,
PROG
(PARI) for(n=1, 22, for(k=1, n, print1(stirling(n, k, 2), ", ")); print()); \\ Joerg Arndt, Apr 21 2013 (PARI) Stirling2(n, k)=sum(i=0, k, (-1)^i*binomial(k, i)*i^n)*(-1)^k/k! \\ M. F. Hasler, Mar 06 2012 (Haskell)
a008277 n k = a008277_tabl !! (n-1) !! (k-1)
a008277_row n = a008277_tabl !! (n-1)
(Maxima) create_list(stirling2(n+1, k+1), n, 0, 30, k, 0, n); /* Emanuele Munarini, Jun 01 2012 */ (J) n ((] (1 % !)) * +/@((^~ * (] (_1 ^ |.)) * (! {:)@]) i.@>:)) k NB. Stephen Makdisi, Apr 06 2016 (Magma) [[StirlingSecond(n, k): k in [1..n]]: n in [1..12]]; // G. C. Greubel, May 22 2019
CROSSREFS
Cf. A008275 (Stirling numbers of first kind), A048993 (another version of this triangle). Cf. A000217, A001296, A001297, A001298, A007318, A028246, A039810- A039813, A048994, A087107- A087111, A087127, A094262, A127701.
KEYWORD
nonn, easy, tabl, nice, core, changed
a(n) = (3^n - 1)/2.
(Formerly M3463)
+10
292
0, 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 1743392200, 5230176601, 15690529804, 47071589413, 141214768240, 423644304721, 1270932914164
COMMENTS
Partial sums of A000244. Values of base 3 strings of 1's. a(n) = (3^n-1)/2 is also the number of different nonparallel lines determined by pair of vertices in the n dimensional hypercube. Example: when n = 2 the square has 4 vertices and then the relevant lines are: x = 0, y = 0, x = 1, y = 1, y = x, y = 1-x and when we identify parallel lines only 4 remain: x = 0, y = 0, y = x, y = 1 - x so a(2) = 4. - Noam Katz (noamkj(AT)hotmail.com), Feb 11 2001
3^a(n) is the highest power of 3 dividing (3^n)!. - Benoit Cloitre, Feb 04 2002 Apart from the a(0) and a(1) terms, maximum number of coins among which a lighter or heavier counterfeit coin can be identified (but not necessarily labeled as heavier or lighter) by n weighings. - Tom Verhoeff, Jun 22 2002, updated Mar 23 2017 Consider the mapping f(a/b) = (a + 2b)/(2a + b). Taking a = 1, b = 2 to start with and carrying out this mapping repeatedly on each new (reduced) rational number gives the sequence 1/2, 4/5, 13/14, 40/41, ... converging to 1. Sequence contains the numerators = (3^n-1)/2. The same mapping for N, i.e., f(a/b) = (a + Nb)/(a+b) gives fractions converging to N^(1/2). - Amarnath Murthy, Mar 22 2003 Number of walks of length 2*n + 2 in the path graph P_5 from one end to the other one. Example: a(2) = 4 because in the path ABCDE we have ABABCDE, ABCBCDE, ABCDCDE and ABCDEDE. - Emeric Deutsch, Apr 02 2004 The number of triangles of all sizes (not counting holes) in Sierpiński's triangle after n inscriptions. - Lee Reeves (leereeves(AT)fastmail.fm), May 10 2004
Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| = 1 for i = 1, 2, ..., 2*n + 1, s(0) = 1, s(2n+1) = 4. - Herbert Kociemba, Jun 10 2004 Number of non-degenerate right-angled incongruent integer-edged Heron triangles whose circumdiameter is the product of n distinct primes of shape 4k + 1. - Alex Fink and R. K. Guy, Aug 18 2005 Also numerator of the sum of the reciprocals of the first n powers of 3, with A000244 being the sequence of denominators. With the exception of n < 2, the base 10 digital root of a(n) is always 4. In base 3 the digital root of a(n) is the same as the digital root of n. - Alonso del Arte, Jan 24 2006 The sequence 3*a(n), n >= 1, gives the number of edges of the Hanoi graph H_3^{n} with 3 pegs and n >= 1 discs. - Daniele Parisse, Jul 28 2006 Numbers n such that a(n) is prime are listed in A028491 = {3, 7, 13, 71, 103, 541, 1091, ...}. 2^(m+1) divides a(2^m*k) for m > 0. 5 divides a(4k). 5^2 divides a(20k). 7 divides a(6k). 7^2 divides a(42k). 11^2 divides a(5k). 13 divides a(3k). 17 divides a(16k). 19 divides a(18k). 1093 divides a(7k). 41 divides a(8k). p divides a((p-1)/5) for prime p = {41, 431, 491, 661, 761, 1021, 1051, 1091, 1171, ...}. p divides a((p-1)/4) for prime p = {13, 109, 181, 193, 229, 277, 313, 421, 433, 541, ...}. p divides a((p-1)/3) for prime p = {61, 67, 73, 103, 151, 193, 271, 307, 367, ...} = A014753, 3 and -3 are both cubes (one implies other) mod these primes p = 1 mod 6. p divides a((p-1)/2) for prime p = {11, 13, 23, 37, 47, 59, 61, 71, 73, 83, 97, ...} = A097933(n). p divides a(p-1) for prime p > 7. p^2 divides a(p*(p-1)k) for all prime p except p = 3. p^3 divides a(p*(p-1)*(p-2)k) for prime p = 11. - Alexander Adamchuk, Jan 22 2007 Let P(A) be the power set of an n-element set A. Then a(n) = the number of [unordered] pairs of elements {x,y} of P(A) for which x and y are disjoint [and both nonempty]. Wieder calls these "disjoint usual 2-combinations". - Ross La Haye, Jan 10 2008 [This is because each of the elements of {1, 2, ..., n} can be in the first subset, in the second or in neither. Because there are three options for each, the total number of options is 3^n. However, since the sets being empty is not an option we subtract 1 and since the subsets are unordered we then divide by 2! (The number of ways two objects can be arranged.) Thus we obtain (3^n-1)/2 = a(n). - Chayim Lowen, Mar 03 2015] Also, still with P(A) being the power set of a n-element set A, a(n) is the number of 2-element subsets {x,y} of P(A) such that the union of x and y is equal to A. Cf. A341590. - Fabio Visonà, Feb 20 2021 Starting with offset 1 = binomial transform of A003945: (1, 3, 6, 12, 24, ...) and double bt of (1, 2, 1, 2, 1, 2, ...); equals polcoeff inverse of (1, -4, 3, 0, 0, 0, ...). - Gary W. Adamson, May 28 2009 Also the constant of the polynomials C(x) = 3x + 1 that form a sequence by performing this operation repeatedly and taking the result at each step as the input at the next. - Nishant Shukla (n.shukla722(AT)gmail.com), Jul 11 2009
Let A be the Hessenberg matrix of order n, defined by: A[1,j] = 1, A[i, i] := 3, (i > 1), A[i, i-1] = -1, and A[i, j] = 0 otherwise. Then, for n >= 1, a(n) = det(A). - Milan Janjic, Jan 27 2010 This is the sequence A(0, 1; 2, 3; 2) = A(0, 1; 4, -3; 0) of the family of sequences [a, b:c, d:k] considered by Gary Detlefs, and treated as A(a, b; c, d; k) in the Wolfdieter Lang link given below. - Wolfdieter Lang, Oct 18 2010 It appears that if s(n) is a first order rational sequence of the form s(0) = 0, s(n) = (2*s(n-1)+1)/(s(n-1)+2), n > 0, then s(n)= a(n)/(a(n)+1). - Gary Detlefs, Nov 16 2010 This sequence also describes the total number of moves to solve the [RED ; BLUE ; BLUE] or [RED ; RED ; BLUE] pre-colored Magnetic Towers of Hanoi puzzle (cf. A183111 - A183125). a(n) is number of compositions of odd numbers into n parts less than 3. For example, a(3) = 13 and there are 13 compositions odd numbers into 3 parts < 3:
1: (0, 0, 1), (0, 1, 0), (1, 0, 0);
3: (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0), (1, 1, 1);
5: (1, 2, 2), (2, 1, 2), (2, 2, 1).
(End)
Pisano period lengths: 1, 2, 1, 2, 4, 2, 6, 4, 1, 4, 5, 2, 3, 6, 4, 8, 16, 2, 18, 4, ... . - R. J. Mathar, Aug 10 2012 a(n) is the total number of holes (triangles removed) after the n-th step of a Sierpiński triangle production. - Ivan N. Ianakiev, Oct 29 2013 a(n) solves Sum_{j = a(n) + 1 .. a(n+1)} j = k^2 for some integer k, given a(0) = 0 and requiring smallest a(n+1) > a(n). Corresponding k = 3^n. - Richard R. Forberg, Mar 11 2015 a(n+1) equals the number of words of length n over {0, 1, 2, 3} avoiding 01, 02 and 03. - Milan Janjic, Dec 17 2015 For n >= 1, a(n) is also the total number of words of length n, over an alphabet of three letters, such that one of the letters appears an odd number of times (See A006516 for 4 letter words, and the Balakrishnan reference there). - Wolfdieter Lang, Jul 16 2017 Also, the number of maximal cliques, maximum cliques, and cliques of size 4 in the n-Apollonian network. - Andrew Howroyd, Sep 02 2017 For n > 1, the number of triangles (cliques of size 3) in the (n-1)-Apollonian network. - Andrew Howroyd, Sep 02 2017 a(n) is the largest number that can be represented with n trits in balanced ternary. Correspondingly, -a(n) is the smallest number that can be represented with n trits in balanced ternary. - Thomas König, Apr 26 2020 These form Sierpinski nesting-stars, which alternate pattern on 3^n+1/2 star numbers A003154, based on the square configurations of 9^n. The partial sums of 3^n are delineated according to the geometry of a hexagram, see illustrations in links. (3*a(n-1) + 1) create Sierpinski-anti-triangles, representing the number of holes in a (n+1) Sierpinski triangle (see illustrations). - John Elias, Oct 18 2021 For n > 1, a(n) is the number of iterations necessary to calculate the hyperbolic functions with CORDIC. - Mathias Zechmeister, Jul 26 2022 For all n >= 0, Sum_{k=a(n)+1..a(n+1)} 1/k < Sum_{j=a(n+1)+1..a(n+2)} 1/j. These are the minimal points which partition the infinite harmonic series into a monotonically increasing sequence. Each partition approximates log(3) from below as n tends to infinity. - Joseph Wheat, Apr 15 2023 a(n) is also the number of 3-cycles in the n-Dorogovtsev-Goltsev-Mendes graph (using the convention the 0-Dorogovtsev-Goltsev-Mendes graph is P_2). - Eric W. Weisstein, Dec 06 2023
REFERENCES
J. G. Mauldon, Strong solutions for the counterfeit coin problem, IBM Research Report RC 7476 (#31437) 9/15/78, IBM Thomas J. Watson Research Center, P. O. Box 218, Yorktown Heights, N. Y. 10598.
Paulo Ribenboim, The Book of Prime Number Records, Springer-Verlag, NY, 2nd ed., 1989, p. 60.
Paulo Ribenboim, The Little Book of Big Primes, Springer-Verlag, NY, 1991, p. 53.
Amir Sapir, The Tower of Hanoi with Forbidden Moves, The Computer J. 47 (1) (2004) 20, case three-in-a row, sequence a(n).
Robert Sedgewick, Algorithms, 1992, pp. 109.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Max A. Alekseyev and Toby Berger, Solving the Tower of Hanoi with Random Moves. In: J. Beineke, J. Rosenhouse (eds.) The Mathematics of Various Entertaining Subjects: Research in Recreational Math, Princeton University Press, 2016, pp. 65-79. ISBN 978-0-691-16403-8 G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy] Eric Weisstein's World of Mathematics, Repunit. Eric Weisstein's World of Mathematics, Weighing.
FORMULA
G.f.: x/((1-x)*(1-3*x)).
a(n) = 4*a(n-1) - 3*a(n-2), n > 1. a(0) = 0, a(1) = 1.
a(n) = 3*a(n-1) + 1, a(0) = 0.
E.g.f.: (exp(3*x) - exp(x))/2. - Paul Barry, Apr 11 2003 a(n+1) = Sum_{k = 0..n} binomial(n+1, k+1)*2^k. - Paul Barry, Aug 20 2004 a(n) = Sum_{i = 0..n-1} 3^i, for n > 0; a(0) = 0.
a(n) = StirlingS2(n+1, 3) + StirlingS2(n+1, 2). - Ross La Haye, Jan 10 2008 a(n) = 2*a(n-1) + 3*a(n-2) + 2, n > 1. - Gary Detlefs, Jun 21 2010 a(n) = 3*a(n-1) + a(n-2) - 3*a(n-3) = 5*a(n-1) - 7*a(n-2) + 3*a(n-3), a(0) = 0, a(1) = 1, a(2) = 4. Observation by G. Detlefs. See the W. Lang comment and link. - Wolfdieter Lang, Oct 18 2010 G.f.: Q(0)/2 where Q(k) = 1 - 1/(9^k - 3*x*81^k/(3*x*9^k - 1/(1 - 1/(3*9^k - 27*x*81^k/(9*x*9^k - 1/Q(k+1)))))); (continued fraction ). - Sergei N. Gladkovskii, Apr 12 2013
EXAMPLE
There are 4 3-block bicoverings of a 3-set: {{1, 2, 3}, {1, 2}, {3}}, {{1, 2, 3}, {1, 3}, {2}}, {{1, 2, 3}, {1}, {2, 3}} and {{1, 2}, {1, 3}, {2, 3}}.
Ternary........Decimal
0.................0
1.................1
11................4
111..............13
There are altogether a(3) = 13 three letter words over {A,B,C} with say, A, appearing an odd number of times: AAA; ABC, ACB, ABB, ACC; BAC, CAB, BAB, CAC; BCA, CBA, BBA, CCA. - Wolfdieter Lang, Jul 16 2017
MATHEMATICA
LinearRecurrence[{4, -3}, {0, 1}, 30] (* Harvey P. Dale, Jul 13 2011 *) CoefficientList[Series[x/(1 - 4x + 3x^2), {x, 0, 30}], x] (* Eric W. Weisstein, Sep 28 2017 *) Table[FromDigits[PadRight[{}, n, 1], 3], {n, 0, 30}] (* Harvey P. Dale, Jun 01 2022 *)
PROG
(PARI) a(n)=(3^n-1)/2
(Haskell)
a003462 = (`div` 2) . (subtract 1) . (3 ^)
(PARI) concat(0, Vec(x/((1-x)*(1-3*x)) + O(x^30))) \\ Altug Alkan, Nov 01 2015 (GAP)
CROSSREFS
Cf. A064099 (minimal number of weightings to detect lighter or heavier coin among n coins). Cf. A006516 (binomial transform, and special 4 letter words).
EXTENSIONS
Corrected my comment of Jan 10 2008. - Ross La Haye, Oct 29 2008 Removed comment that duplicated a formula. - Joerg Arndt, Mar 11 2010
Triangle read by rows: 2-Stirling numbers of the second kind.
+10
31
1, 2, 1, 4, 5, 1, 8, 19, 9, 1, 16, 65, 55, 14, 1, 32, 211, 285, 125, 20, 1, 64, 665, 1351, 910, 245, 27, 1, 128, 2059, 6069, 5901, 2380, 434, 35, 1, 256, 6305, 26335, 35574, 20181, 5418, 714, 44, 1, 512, 19171, 111645, 204205, 156660, 58107, 11130, 1110, 54, 1
COMMENTS
This is the case r = 2 of the r-Stirling numbers of the second kind. The 2-Stirling numbers of the second kind give the number of ways of partitioning the set {1,2,...,n} into k nonempty disjoint subsets with the restriction that the elements 1 and 2 belong to distinct subsets.
More generally, the r-Stirling numbers of the second kind give the number of ways of partitioning the set {1,2,...,n} into k nonempty disjoint subsets with the restriction that the numbers 1, 2, ..., r belong to distinct subsets. The case r = 1 gives the usual Stirling numbers of the second kind A008277; for other cases see A143495 (r = 3) and A143496 (r = 4). The lower unitriangular array of r-Stirling numbers of the second kind equals the matrix product P^(r-1) * S (with suitable offsets in the row and column indexing), where P is Pascal's triangle, A007318 and S is the array of Stirling numbers of the second kind, A008277. For the definition of and entries relating to the corresponding r-Stirling numbers of the first kind see A143491. For entries on r-Lah numbers refer to A143497. The theory of r-Stirling numbers of both kinds is developed in [Broder]. Let D be the derivative operator d/dx and E the Euler operator x*d/dx. Then x^(-2)*E^n*x^2 = Sum_{k = 0..n} T(n+2,k+2)*x^k*D^k.
The row generating polynomials R_n(x) := Sum_{k= 2..n} T(n,k)*x^k satisfy the recurrence R_(n+1)(x) = x*R_n(x) + x*d/dx(R_n(x)) with R_2(x) = x^2. It follows that the polynomials R_n(x) have only real zeros (apply Corollary 1.2. of [Liu and Wang]).
Relation with the 2-Eulerian numbers E_2(n,j) := A144696(n,j): T(n,k) = 2!/k!*Sum_ {j = n-k..n-2} E_2(n,j)*binomial(j,n-k) for n >= k >= 2. (End) T(n,k)=S(n,k,2), n>=k>=2, in Mikhailov's first paper, eq.(28) or (A3). E.g.f. column no. k from (A20) with k->2, r->k. Therefore, with offset [0,0], this triangle is the Sheffer triangle (exp(2*x),exp(x)-1) with e.g.f. of column no. m>=0: exp(2*x)*((exp(x)-1)^m)/m!. See one of the formulas given below. For Sheffer matrices see the W. Lang link under A006232 with the S. Roman reference, also found in A132393. (End)
LINKS
Andrei Z. Broder, The r-Stirling numbers, Report Number: CS-TR-82-949, 1982, Stanford University, Department of Computer Science.
FORMULA
T(n+2,k+2) = (1/k!)*Sum_{i = 0..k} (-1)^(k-i)*C(k,i)*(i+2)^n, n,k >= 0. T(n,k) = Stirling2(n,k) - Stirling2(n-1,k) for n, k >= 2.
Recurrence relation: T(n,k) = T(n-1,k-1) + k*T(n-1,k) for n > 2, with boundary conditions T(n,1) = T(1,n) = 0 for all n, T(2,2) = 1 and T(2,k) = 0 for k > 2. Special cases: T(n,2) = 2^(n-2); T(n,3) = 3^(n-2) - 2^(n-2).
As a sum of monomial functions of degree m: T(n+m,n) = Sum_{2 <= i_1 <= ... <= i_m <= n} (i_1*i_2*...*i_m). For example, T(6,4) = Sum_{2 <= i <= j <= 4} (i*j) = 2*2 + 2*3 + 2*4 + 3*3 + 3*4 + 4*4 = 55.
E.g.f. column k+2 (with offset 2): 1/k!*exp(2*x)*(exp(x) - 1)^k.
O.g.f. k-th column: Sum_{n = k..oo} T(n,k)*x^n = x^k/((1-2*x)*(1-3*x)*...*(1-k*x)).
E.g.f.: exp(2*t + x*(exp(t) - 1)) = Sum_{n = 0..oo} Sum_{k = 0..n} T(n+2,k+2) *x^k*t^n/n! = Sum_{n = 0..oo} B_n(2;x)*t^n/n! = 1 + (2 + x)*t/1! + (4 + 5*x + x^2)*t^2/2! + ..., where the row polynomial B_n(2;x) := Sum_{k = 0..n} T(n+2,k+2)*x^k denotes the 2-Bell polynomial.
Dobinski-type identities: Row polynomial B_n(2;x) = exp(-x)*Sum_{i = 0..oo} (i + 2)^n*x^i/i!. Sum_{k = 0..n} k!*T(n+2,k+2)*x^k = Sum_{i = 0..oo} (i + 2)^n*x^i/(1 + x)^(i+1).
The T(n,k) are the connection coefficients between falling factorials and the shifted monomials (x + 2)^(n-2). For example, from row 4 we have 4 + 5*x + x*(x - 1) = (x + 2)^2, while from row 5 we have 8 + 19*x + 9*x*(x - 1) + x*(x - 1)*(x - 2) = (x + 2)^3.
The row sums of the array are the 2-Bell numbers, B_n(2;1), equal to A005493(n-2). The alternating row sums are the complementary 2-Bell numbers, B_n(2;-1), equal to (-1)^n* A074051(n-2). This array is the matrix product P * S, where P denotes the Pascal triangle, A007318 and S denotes the lower triangular array of Stirling numbers of the second kind, A008277 (apply Theorem 10 of [Neuwirth]). Also, this array equals the transpose of the upper triangular array A126351. The inverse array is A049444, the signed 2-Stirling numbers of the first kind. See A143491 for the unsigned version of the inverse. Let f(x) = exp(exp(x)). Then for n >= 1, the row polynomials R(n,x) are given by R(n+2,exp(x)) = 1/f(x)*(d/dx)^n(exp(2*x)*f(x)). Similar formulas hold for A008277, A039755, A105794, A111577 and A154537. - Peter Bala, Mar 01 2012
EXAMPLE
Triangle begins
n\k|...2....3....4....5....6....7
=================================
2..|...1
3..|...2....1
4..|...4....5....1
5..|...8...19....9....1
6..|..16...65...55...14....1
7..|..32..211..285..125...20....1
...
T(4,3) = 5. The set {1,2,3,4} can be partitioned into three subsets such that 1 and 2 belong to different subsets in 5 ways: {{1}{2}{3,4}}, {{1}{3}{2,4}}, {{1}{4}{2,3}}, {{2}{3}{1,4}} and {{2}{4}{1,3}}; the remaining possibility {{1,2}{3}{4}} is not allowed.
MAPLE
with combinat: T := (n, k) -> (1/(k-2)!)*add ((-1)^(k-i)*binomial(k-2, i)*(i+2)^(n-2), i = 0..k-2): for n from 2 to 11 do seq(T(n, k), k = 2..n) end do;
MATHEMATICA
t[n_, k_] := StirlingS2[n, k] - StirlingS2[n-1, k]; Flatten[ Table[ t[n, k], {n, 2, 11}, {k, 2, n}]] (* Jean-François Alcover, Dec 02 2011 *)
PROG
(Sage)
@CachedFunction
def stirling2r(n, k, r) :
if n < r: return 0
if n == r: return 1 if k == r else 0
return stirling2r(n-1, k-1, r) + k*stirling2r(n-1, k, r)
A143494 = lambda n, k: stirling2r(n, k, 2)
for n in (2..6):
CROSSREFS
Cf. A001047 (column 3), A005493 (row sums), A008277, A016269 (column 4), A025211 (column 5), A049444 (matrix inverse), A074051 (alt. row sums), A143491, A143495, A143496, A143497.
Dowling numbers: e.g.f.: exp(x + (exp(b*x) - 1)/b) with b=2.
(Formerly M1674)
+10
26
1, 2, 6, 24, 116, 648, 4088, 28640, 219920, 1832224, 16430176, 157554048, 1606879040, 17350255744, 197553645440, 2363935624704, 29638547505408, 388328781668864, 5304452565517824, 75381218537805824, 1112348880749130752, 17014743624340539392, 269360902955086379008
COMMENTS
Equals leftmost term in iterates of M^n * [1,1,1,...], where M = a bidiagonal matrix with (1,3,5,7,...) in the main diagonal and (1,1,1,...) in the superdiagonal. - Gary W. Adamson, Apr 13 2009
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Jean-Luc Baril, Pamela E. Harris, and José L. Ramírez, Flattened Catalan Words, arXiv:2405.05357 [math.CO], 2024. See p. 2. Adam Buck, Jennifer Elder, Azia A. Figueroa, Pamela E. Harris, Kimberly Harry, and Anthony Simpson, Flattened Stirling Permutations, arXiv:2306.13034 [math.CO], 2023. See p. 14.
FORMULA
E.g.f.: exp(x + (exp(2*x) - 1)/2).
a(n) = sum of top row terms of M^n, M = an infinite square production matrix in which a diagonal of 1's is appended to the right of Pascal's triangle squared; as follows:
1, 1, 0, 0, 0, 0, ...
2, 1, 1, 0, 0, 0, ...
4, 4, 1, 1, 0, 0, ...
8, 12, 6, 1, 1, 0, ...
16, 32, 24, 8, 1, 1, ...
G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - 1/(1-(2*k+1)*x)/(1-x/(x-1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 16 2013 G.f.: -G(0) where G(k) = 1 - (x*(2*k+1) - 2)/(x*(2*k+1) - 1 - x*(x*(2*k+1) - 1)/(x + (x*(2*k+1) - 2)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 29 2013 G.f.: 1/Q(0), where Q(k) = 1 - 2*(k+1)*x - 2*(k+1)*x^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 03 2013 G.f.: 1/Q(0), where Q(k) = 1 - x - x/(1 - x*(2*k+2)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, May 13 2013 G.f.: 1/(1-x*Q(0)), where Q(k) = 1 + x/(1 - x + 2*x*(k+1)/(x - 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 19 2013 Conjecture: Let M_n be an n X n matrix whose elements are m_ij = 1 for i < j - 1, m_ij = -1 for i = j - 1, and m_ij = binomial(n - i,j - i) otherwise. Then a(n - 1) = Det(M_n). - Benedict W. J. Irwin, Apr 19 2017 a(n) = exp(-1/2) * Sum_{k>=0} (2*k + 1)^n / (2^k * k!). - Ilya Gutkovskiy, Apr 16 2020 a(n) ~ 2^(n + 1/2) * n^(n + 1/2) * exp(n/LambertW(2*n) - n - 1/2) / (sqrt(1 + LambertW(2*n)) * LambertW(2*n)^(n + 1/2)). - Vaclav Kotesovec, Jun 26 2022
EXAMPLE
a(4) = 116 = sum of top row terms of M^3 = (49 + 44 + 18 + 4 + 1).
MATHEMATICA
max = 19; f[x_]:= Exp[x + Exp[2x]/2 -1/2]; CoefficientList[Series[f[x], {x, 0, max}], x]*Range[0, max]! (* Jean-François Alcover, Nov 22 2011 *) Table[Sum[Binomial[n, k] * 2^k * BellB[k, 1/2], {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Apr 17 2020 *)
PROG
(PARI) x='x+O('x^66); Vec(serlaplace(exp(x+1/2*exp(2*x)-1/2))) \\ Joerg Arndt, May 13 2013 (Sage)
@CachedFunction
def S(n, k, m):
if k > n or k < 0 : return 0
if n == 0 and k == 0: return 1
return S(n-1, k-1, m) + (m*(k+1)-1)*S(n-1, k, m)
(Sage)
b=2;
P.<x> = PowerSeriesRing(QQ, prec)
return P( exp(x +(exp(b*x)-1)/b) ).egf_to_ogf().list()
(Magma) m:=20; c:=2; R<x>:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( Exp(x +(Exp(c*x)-1)/c) )); [Factorial(n-1)*b[n]: n in [1..m-1]]; // G. C. Greubel, Feb 24 2019
Exponential Riordan array (1, x(1+x/2)).
+10
23
1, 0, 1, 0, 1, 1, 0, 0, 3, 1, 0, 0, 3, 6, 1, 0, 0, 0, 15, 10, 1, 0, 0, 0, 15, 45, 15, 1, 0, 0, 0, 0, 105, 105, 21, 1, 0, 0, 0, 0, 105, 420, 210, 28, 1, 0, 0, 0, 0, 0, 945, 1260, 378, 36, 1, 0, 0, 0, 0, 0, 945, 4725, 3150, 630, 45, 1, 0, 0, 0, 0, 0, 0, 10395, 17325, 6930, 990, 55, 1, 0, 0
COMMENTS
T(n,k) is the number of self-inverse permutations of {1,2,...,n} having exactly k cycles. - Geoffrey Critzer, May 08 2012 Also the inverse Bell transform of the double factorial of odd numbers Product_{k= 0..n-1} (2*k+1) ( A001147). For the definition of the Bell transform see A264428 and for cross-references A265604. - Peter Luschny, Dec 31 2015
FORMULA
Number triangle T(n,k) = k!*C(n,k)/((2k-n)!*2^(n-k)).
Triangle equals the matrix product A008275* A039755. Equivalently, the n-th row polynomial R(n,x) is given by the Type B Dobinski formula R(n,x) = exp(-x/2)*Sum_{k>=0} P(n,2*k+1)*(x/2)^k/k!, where P(n,x) = x*(x-1)*...*(x-n+1) denotes the falling factorial polynomial. Cf. A113278. - Peter Bala, Jun 23 2014 E.g.f. for the m-th column: (x^2/2+x)^m/m!.
T(n,k) = T(n-1,k-1) + (n-1)*T(n-2,k-1) for n>1 and k=1..n, T(0,0) = 1. (End)
EXAMPLE
Triangle begins:
1
0 1
0 1 1
0 0 3 1
0 0 3 6 1
0 0 0 15 10 1
0 0 0 15 45 15 1
0 0 0 0 105 105 21 1
0 0 0 0 105 420 210 28 1
0 0 0 0 0 945 1260 378 36 1
As noted above, a(n) is the number of set partitions of {1..n} into k singletons or pairs. This is also the number of set partitions of subsets of {1..n} into n - k pairs. In the first case, row n = 5 counts the following set partitions:
{{1},{2,3},{4,5}} {{1},{2},{3},{4,5}} {{1},{2},{3},{4},{5}}
{{1,2},{3},{4,5}} {{1},{2},{3,4},{5}}
{{1,2},{3,4},{5}} {{1},{2,3},{4},{5}}
{{1,2},{3,5},{4}} {{1,2},{3},{4},{5}}
{{1},{2,4},{3,5}} {{1},{2},{3,5},{4}}
{{1},{2,5},{3,4}} {{1},{2,4},{3},{5}}
{{1,3},{2},{4,5}} {{1},{2,5},{3},{4}}
{{1,3},{2,4},{5}} {{1,3},{2},{4},{5}}
{{1,3},{2,5},{4}} {{1,4},{2},{3},{5}}
{{1,4},{2},{3,5}} {{1,5},{2},{3},{4}}
{{1,4},{2,3},{5}}
{{1,4},{2,5},{3}}
{{1,5},{2},{3,4}}
{{1,5},{2,3},{4}}
{{1,5},{2,4},{3}}
In the second case, we have:
{{1,2},{3,4}} {{1,2}} {}
{{1,2},{3,5}} {{1,3}}
{{1,2},{4,5}} {{1,4}}
{{1,3},{2,4}} {{1,5}}
{{1,3},{2,5}} {{2,3}}
{{1,3},{4,5}} {{2,4}}
{{1,4},{2,3}} {{2,5}}
{{1,4},{2,5}} {{3,4}}
{{1,4},{3,5}} {{3,5}}
{{1,5},{2,3}} {{4,5}}
{{1,5},{2,4}}
{{1,5},{3,4}}
{{2,3},{4,5}}
{{2,4},{3,5}}
{{2,5},{3,4}}
(End)
MAPLE
# The function BellMatrix is defined in A264428. BellMatrix(n -> `if`(n<2, 1, 0), 9); # Peter Luschny, Jan 27 2016
MATHEMATICA
t[n_, k_] := k!*Binomial[n, k]/((2 k - n)!*2^(n - k)); Table[ t[n, k], {n, 0, 11}, {k, 0, n}] // Flatten
(* Second program: *)
rows = 12;
t = Join[{1, 1}, Table[0, rows]];
T[n_, k_] := BellY[n, k, t];
sbs[{}]:={{}}; sbs[set:{i_, ___}]:=Join@@Function[s, (Prepend[#1, s]&)/@sbs[Complement[set, s]]]/@Cases[Subsets[set], {i}|{i, _}];
Table[Length[Select[sbs[Range[n]], Length[#]==k&]], {n, 0, 6}, {k, 0, n}] (* Gus Wiseman, Jan 12 2021 *)
PROG
(PARI) {T(n, k)=if(2*k<n||k>n, 0, n!/(2*k-n)!/(n-k)!*2^(k-n))} /* Michael Somos, Oct 03 2006 */ (Sage) # uses[inverse_bell_transform from A265605] multifact_2_1 = lambda n: prod(2*k + 1 for k in (0..n-1))
inverse_bell_matrix(multifact_2_1, 9) # Peter Luschny, Dec 31 2015
CROSSREFS
Same as A049403 but with a first column k = 0. The same set partitions counted by number of pairs are A100861. Reversing rows gives A111924 (without column k = 0). A047884 counts standard Young tableaux by size and greatest row length.
A238123 counts standard Young tableaux by size and least row length.
A320663/ A339888 count unlabeled multiset partitions into singletons/pairs.
A322661 counts labeled covering half-loop-graphs.
A339742 counts factorizations into distinct primes or squarefree semiprimes.
Numerators of the rational sequence with e.g.f. 1/(1+exp(-x)).
+10
23
1, 1, 0, -1, 0, 1, 0, -17, 0, 31, 0, -691, 0, 5461, 0, -929569, 0, 3202291, 0, -221930581, 0, 4722116521, 0, -968383680827, 0, 14717667114151, 0, -2093660879252671, 0, 86125672563201181, 0, -129848163681107301953, 0, 868320396104950823611, 0
COMMENTS
The corresponding denominator sequence looks like 2* A006519(n+1) when n is odd. Also numerator of the value at the origin of the n-th derivative of the standard logistic function. - Enrique Pérez Herrero, Feb 15 2016
FORMULA
a(n) = numerator(sum(E(n,m),m=0..n)), n>=0, with the Euler triangle E(n,m)= A060096(n,m)/ A060097(n,m). E.g.f.: 2/(1+exp(-x)) (see a comment in A060096). r(n) := sum(E(n,m),m=0..n) = ((-1)^n)*sum(((-1)^m)*m!*S2(n,m)/2^m, m=0..n), n>=0, where S2 are the Stirling numbers of the second kind A048993. From the e.g.f. with y=exp(-x), dx=-y*dy, putting y=1 at the end. - Wolfdieter Lang, Nov 03 2011 a(n) = numerator(euler(n,1)/(2^n-1)) for n > 0. - Peter Luschny, Jul 14 2013 a(n) = numerator(2*(2^n-1)*B(n,1)/n) for n > 0, B(n,x) the Bernoulli polynomials. - Peter Luschny, May 24 2014 Numerators of the Taylor series coefficients 4*(2^(n+1)-1)*B(n+1)/(n+1) for n>0 of 1 + 2 * tanh(x/2) (cf. A000182 and A089171). - Tom Copeland, Oct 19 2016 Conjecture: r(n) = Sum_{k=0..n} A001147(k) * A039755(n, k) * (-1)^k / (k+1) where r(n) = a(n) / A006519(n+1) = (n!) * ([x^n] (2 / (1 + exp(-x)))), for n >= 0. - Werner Schulte, Feb 16 2024
EXAMPLE
The rational sequence r(n) = a(n) / A006519(n+1) starts: 1, 1/2, 0, -1/4, 0, 1/2, 0, -17/8, 0, 31/2, 0, -691/4, 0, 5461/2, 0, -929569/16, 0, 3202291/2, 0, -221930581/4, 0, 4722116521/2, 0, -968383680827/8, 0, 14717667114151/2, 0, -2093660879252671/4, ...
MAPLE
seq(denom(euler(i, x))*euler(i, 1), i=0..33); # Peter Luschny, Jun 16 2012
MATHEMATICA
Join[{1}, Table[Numerator[EulerE[n, 1]/(2^n-1)], {n, 34}]] (* Peter Luschny, Jul 14 2013 *)
PROG
(Sage)
x = var('x')
s = (1/(1+exp(-x))).series(x, n+2)
return [(factorial(i)*s.coefficient(x, i)).numerator() for i in (0..n)]
(Sage) # Alternatively:
e, f, R, C = 2, 1, [], [1]+[0]*(len-1)
for n in (1..len-1):
for k in range(n, 0, -1):
C[k] = -C[k-1] / (k+1)
C[0] = -sum(C[k] for k in (1..n))
R.append(numerator((e-1)*f*C[0]))
f *= n; e <<= 1
return R
EXTENSIONS
New name, a simpler standalone definition by Peter Luschny, Jul 13 2012
Triangle of f-vectors of the simplicial complexes dual to the permutohedra of type B_n.
+10
21
1, 1, 2, 1, 8, 8, 1, 26, 72, 48, 1, 80, 464, 768, 384, 1, 242, 2640, 8160, 9600, 3840, 1, 728, 14168, 72960, 151680, 138240, 46080, 1, 2186, 73752, 595728, 1948800, 3037440, 2257920, 645120, 1, 6560, 377504, 4612608, 22305024, 52899840
COMMENTS
The Coxeter group of type B_n may be realized as the group of n X n matrices with exactly one nonzero entry in each row and column, that entry being either +1 or -1. The order of the group is 2^n*n!. The orbit of the point (1,2,...,n) (or any sufficiently generic point (x_1,...,x_n)) under the action of this group is a set of 2^n*n! distinct points whose convex hull is defined to be the permutohedron of type B_n. The rows of this table are the f-vectors of the simplicial complexes dual to these type B permutohedra. Some examples are given in the Example section below. See A060187 for the corresponding table of h-vectors of type B permutohedra. This is the (unsigned) triangle of connection constants between the polynomial sequences (2*x + 1)^n, n >= 0, and binomial(x+k,k), k >= 0. For example, (2*x + 1)^2 = 8*binomial(x+2,2) - 8*binomial(x+1,1) + 1 and (2*x + 1)^3 = 48*binomial(x+3,3) - 72*binomial(x+2,2) + 26*binomial(x+1,1) - 1. Cf. A163626. - Peter Bala, Jun 06 2019
FORMULA
T(n,k) = Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i)*(2*i+1)^n.
Recurrence relation: T(n,k) = (2*k + 1)*T(n-1,k) + 2*k*T(n-1,k-1) with T(0,0) = 1 and T(0,k) = 0 for k >= 1.
Relation with type B Stirling numbers of the second kind: T(n,k) = 2^k*k!* A039755(n,k). E.g.f.: exp(t)/(1 + x - x* exp(2*t)) = 1 + (1 + 2*x)*t + (1 + 8*x + 8*x^2 )*t^2/2! + ... .
The polynomials in the first column of the array ((1+t)*P^(-1)-t*P)^(-1), P Pascal's triangle and I the identity, are the row polynomials of this table.
The polynomials in the first column of the array ((1+t)*I-t* A062715)^(-1) are, apart from the initial 1, the row polynomials of this table with an extra factor of t. Cf. A060187. (End) Integrating the above e.g.f. with respect to x from x = 0 to x = 1 gives Sum_{k = 0..n} (-1)^k*T(n,k)/(k + 1) = 2^n*Bernoulli(n,1/2), the n-th cosecant number.
The corresponding Type A result is considered in A028246 as Worpitzky's algorithm. Also for n >= 0, Sum_{k = 0..2*n} (-1)^k*T(2*n,k)/((k + 1)*(k + 2)) = 1/2*2^(2*n)*Bernoulli(2*n,1/2) and for n >= 1, Sum_{k = 0..2*n-1} (-1)^k*T(2*n - 1,k)/((k + 1)*(k + 2)) = -1/2 * 2^(2*n)* Bernoulli(2*n,1/2).
The row polynomials R(n,x) satisfy the recurrence equation R(n+1,x) = D(R(n,x)) with R(0,x) = 1, where D is the operator 1 + 2*x + 2*x(1 + x)*d/dx.
R(n,x) = 1/(1 + x)* Sum_{k = 0..inf} (2*k + 1)^n*(x/(1 + x))^k, valid for x in the open interval (-1/2, inf). Cf. A019538. The shifted row polynomial x*R(n,x) = (1 + x)^n*P(n,x/(1 + x)) where P(n,x) denotes the n-th row polynomial of A060187. The row polynomials R(n,x) have only real zeros.
Symmetry: R(n,x) = (-1)^n*R(n,-1 - x). Consequently the zeros of R(n,x) lie in the open interval (-1, 0). (End)
Recurrence for row polynomials: R(n,x) = 1 + x*Sum_{k = 0..n-1} binomial(n,k)2^(n-k)*R(k,x) with R(0,x) = 1.
For a fixed integer k, the expansion of the function A(k,z) := exp( Sum_{n >= 1} R(n,k)*z^n/n ) has integer coefficients and satisfies the functional equation A(k,z)^(k + 1) = 1/(1 - z)*( BINOMIAL(BINOMIAL(A(k,z))) )^k, where BINOMIAL(F(z))= 1/(1 - z)*F(z/(1 - z)) denotes the binomial transform of the o.g.f. F(z). A(k,z) = A(-(k + 1),-z). Cf. A019538. n-th row polynomial R(n,x) = (1 + 2*x) o (1 + 2*x) o ... o (1 + 2*x) (n factors), where o denotes the black diamond multiplication operator of Dukes and White. See example E13 in the Bala link.
R(n,x) = Sum_{k = 0..n} binomial(n,k)*2^k*F(k,x) where F(k,x) is the Fubini polynomial of order k, the k-th row polynomial of A019538. (End)
EXAMPLE
The triangle begins
n\k|..0.....1.....2.....3.....4.....5
=====================================
0..|..1
1..|..1.....2
2..|..1.....8.....8
3..|..1....26....72....48
4..|..1....80...464...768...384
5..|..1...242..2640..8160..9600..3840
...
Row 2: the permutohedron of type B_2 is an octagon with 8 vertices and 8 edges. Its dual, also an octagon, has f-vector (1,8,8) - row 3 of this triangle.
Row 3: for an appropriate choice of generic point in R_3, the permutohedron of type B_3 is realized as the great rhombicuboctahedron, also known as the truncated cuboctahedron, with 48 vertices, 72 edges and 26 faces (12 squares, 8 regular hexagons and 6 regular octagons). See the Wikipedia entry and also [Fomin and Reading p.22]. Its dual polyhedron is a simplicial polyhedron, the disdyakis dodecahedron, with 26 vertices, 72 edges and 48 triangular faces and so its f-vector is (1,26,72,48) - row 4 of this triangle.
Examples of falling factorials identities for odd numbered rows: Let (x)_n = x*(x - 1)*...*(x - n + 1) with (x)_0 = 1 denote the falling factorial power.
Row 1: 2*(x)_1 + (0 - 2*x)_1 = 0.
Row 3: 48*(x)_3 + 72*(x)_2 * (2 - 2*x)_1 + 26*(x)_1 * (2 - 2*x)_2 + (2 - 2*x)_3 = 0
Row 5: 3840*(x)_5 + 9600*(x)_4 * (4 - 2*x)_(1) + 8160*(x)_3 * (4 - 2*x)_2 + 2640*(x)_2 * (4 - 2*x)_3 + 242*(x)_1 * (4 - 2*x)_4 + (4 - 2*x)_5 = 0. (End)
MAPLE
with(combinat):
T:= (n, k) -> add((-1)^(k-i)*binomial(k, i)*(2*i+1)^n, i = 0..k):
for n from 0 to 9 do
seq(T(n, k), k = 0..n);
end do;
MATHEMATICA
T[n_, k_] := Sum[(-1)^(k - i)*Binomial[k, i]*(2*i + 1)^n, {i, 0, k}];
Search completed in 0.045 seconds
|