The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A090582 T(n, k) = Sum_{j=0..n-k} (-1)^j*binomial(n - k + 1, j)*(n - k + 1 - j)^n. Triangle read by rows, T(n, k) for 1 <= k <= n. 20
 1, 2, 1, 6, 6, 1, 24, 36, 14, 1, 120, 240, 150, 30, 1, 720, 1800, 1560, 540, 62, 1, 5040, 15120, 16800, 8400, 1806, 126, 1, 40320, 141120, 191520, 126000, 40824, 5796, 254, 1, 362880, 1451520, 2328480, 1905120, 834120, 186480, 18150, 510, 1, 3628800, 16329600, 30240000, 29635200, 16435440, 5103000, 818520, 55980, 1022, 1 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS Let Q(m, n) = Sum_(k=0..n-1) (-1)^k * binomial(n, k) * (n-k)^m. Then Q(m,n) is the numerator of the probability P(m,n) = Q(m,n)/n^m of seeing each card at least once if m >= n cards are drawn with replacement from a deck of n cards, written in a two-dimensional array read by antidiagonals with Q(m,m) as first row and Q(m,1) as first column. The sequence is given as a matrix with the first row containing the cases #draws = size_of_deck. The second row contains #draws = 1 + size_of_deck. If "mn" indicates m cards drawn from a deck with n cards then the locations in the matrix are:   11 22 33 44 55 66 77 ...   21 32 43 54 65 76 87 ...   31 42 53 64 75 86 97 ...   41 52 63 74 85 .. .. ... read by antidiagonals ->:   11, 22, 21, 33, 32, 31, 44, 43, 42, 41, 55, 54, 53, 52, .... The probabilities are given by Q(m,n)/n^m: .(m,n):.....11..22..21..33..32..31..44..43..42..41...55...54..53..52..51 .....Q:......1...2...1...6...6...1..24..36..14...1..120..240.150..30...1 ...n^m:......1...4...1..27...8...1.256..81..16...1.3125.1024.243..32...1 %.Success:.100..50.100..22..75.100...9..44..88.100....4...23..62..94.100 P(n,n) = n!/n^n which can be approximated by sqrt(Pi*(2n+1/3))/e^n (Gosper's approximation to n!). Let P[n] be the set of all n-permutations. Build a superset Q[n] of P[n] composed of n-permutations in which some (possibly all or none) ascents have been designated. An ascent in a permutation ss...s[n] is a pair of consecutive elements s[i],s[i+1] such that s[i] < s[i+1]. As a triangular array read by rows T(n,k) is the number of elements in Q[n] that have exactly k distinguished ascents, n >= 1, 0 <= k <= n-1. Row sums are A000670. E.g.f. is y/(1+y-exp(y*x)). For example, T(3,1)=6 because there are four 3-permutations with one ascent, with these we would also count 1->2 3, and 1 2->3 where exactly one ascent is designated by "->". (After Flajolet and Sedgewick.) - Geoffrey Critzer, Nov 13 2012 Sum_(k=1..n) Q(n, k)*binomial(x, k) = x^n such that Sum_{k=1..n} Q(n, i)*binomial(x+1,i+1) = Sum_{k=1..x} k^n. - David A. Corneth, Feb 17 2014 A141618(n,n-k+1) = a(n,k) * C(n,k-1) / k. - Tom Copeland, Oct 25 2014 See A074909 and above g.f.s below for associations among this array and the Bernoulli polynomials and their umbral compositional inverses. - Tom Copeland, Nov 14 2014 For connections to toric varieties and Eulerian polynomials (in addition to those noted below), see the Dolgachev and Lunts and the Stembridge links in A019538. - Tom Copeland, Dec 31 2015 See A008279 for a relation between the e.g.f.s enumerating the faces of permutahedra (this entry) and stellahedra. - Tom Copeland, Nov 14 2016 From the Hasan and Franco and Hasan papers: The m-permutohedra for m=1,2,3,4 are the line segment, hexagon, truncated octahedron and omnitruncated 5-cell. The first three are well-known from the study of elliptic models, brane tilings and brane brick models. The m+1 torus can be tiled by a single (m+2)-permutohedron. Relations to toric Calabi-Yau Kahler manifolds are also discussed. - Tom Copeland, May 14 2020 LINKS Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018. Kevin Buhr, Michael Press and DMB, Collecting a deck of cards on the street. Thread in NG sci.math. José L. Cereceda, Figurate numbers and sums of powers of integers, arXiv:2001.03208 [math.NT], 2020. See triangle Table 1 p. 5. P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009, page 209. S. Franco and A. Hasan, Graded Quivers, Generalized Dimer Models and Toric Geometry , arXiv preprint arXiv:1904.07954 [hep-th], 2019. A. Hasan, Physics and Mathematics of Graded Quivers, dissertation, Graduate Center, City University of New York, 2019. Hugo Pfoertner, "Hit all" probabilities: Program and results. FORMULA T(n, k) = (n - k + 1)!*Stirling2(n, n - k + 1), generated by Stirling numbers of the second kind multiplied by a factorial. - Victor Adamchik, Oct 05 2005 Triangle T(n,k), 1 <= k <= n, read by rows given by [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...] DELTA [[0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 10 2006 From Tom Copeland, Oct 07 2008: (Start) G(x,t) = 1/ (1 + (1-exp(x*t))/t) = 1 + 1*x + (2 + t)*x^2/2! + (6 + 6*t + t^2)*x^3/3! + ... gives row polynomials of A090582, the f-polynomials for the permutohedra (see A019538). G(x,t-1) = 1 + 1*x + (1 + t)*x^2/2! + (1 + 4*t + t^2)*x^3/3! + ... gives row polynomials for A008292, the h-polynomials of permutohedra. G[(t+1)x,-1/(t+1)] = 1 + (1 + t)*x + (1 + 3*t + 2*t^2)*x^2/2! + ... gives row polynomials of A028246. (End) From Tom Copeland, Oct 11 2011: (Start) With e.g.f. A(x,t) = G(x,t) - 1, the compositional inverse in x is B(x,t) = log((t+1)-t/(1+x))/t. Let h(x,t) = 1/(dB/dx) = (1+x)*(1+(1+t)x), then the row polynomial P(n,t) is given by (1/n!)*(h(x,t)*d/dx)^n x, evaluated at x=0, A=exp(x*h(y,t)*d/dy) y, eval. at y=0, and dA/dx = h(A(x,t),t).  (End) k <= 0 or k > n yields Q(n, k) = 0; Q(1,1) = 1; Q(n, k) = k * (Q(n-1, k) + Q(n-1, k-1)). - David A. Corneth, Feb 17 2014 T = A008292*A007318. - Tom Copeland, Nov 13 2016 With all offsets 0 for this entry, let A_n(x;y) = (y + E.(x))^n, an Appell sequence in y where E.(x)^k = E_k(x) are the Eulerian polynomials of A123125 with offsets -1 so that the array becomes A008292; i.e., we ignore the first row and first column of A123125. Then the row polynomials of this entry, A090582, are given by A_n(1 + x;0). Other specializations of A_n(x;y) give A028246, A046802, A119879, A130850, and A248727. - Tom Copeland, Jan 24 2020 EXAMPLE For m = 4, n = 2, we draw 4 times from a deck of two cards. Call the cards "a" and "b" - of the 16 possible combinations of draws (each of which is equally likely to occur), only two do not contain both a and b: a, a, a, a and b, b, b, b. So the probability of seeing both a and b is 14/16. Therefore Q(m, n) = 14. Table starts:  1;  2,      1;  6,      6,       1;  24,     36,      14,      1;  120,    240,     150,     30,      1;  720,    1800,    1560,    540,     62,     1;  5040,   15120,   16800,   8400,    1806,   126,    1;  40320,  141120,  191520,  126000,  40824,  5796,   254,   1;  362880, 1451520, 2328480, 1905120, 834120, 186480, 18150, 510, 1. MAPLE T := (n, k) -> add((-1)^j*binomial(n - k + 1, j)*(n - k + 1 - j)^n, j = 0..n-k): # Or: T := (n, k) -> (n - k + 1)!*Stirling2(n, n - k + 1): for n from 1 to 9 do seq( T(n, k), k = 1..n) od; # Peter Luschny, May 21 2021 MATHEMATICA In:= Table[Table[k! StirlingS2[n, k], {k, n, 1, -1}], {n, 1, 6}] (* Victor Adamchik, Oct 05 2005 *) nn=6; a=y/(1+y-Exp[y x]); Range[0, nn]! CoefficientList[Series[a, {x, 0, nn}], {x, y}]//Grid (* Geoffrey Critzer, Nov 10 2012 *) PROG FORTRAN program given at Pfoertner link. (Haskell) a090582 n k = a090582_tabl !! (n-1) !! (k-1) a090582_row n = a090582_tabl !! (n-1) a090582_tabl = map reverse a019538_tabl -- Reinhard Zumkeller, Dec 15 2013 (PARI) a(n)={m=ceil((-1+sqrt(1+8*n))/2); k=m+1+binomial(m, 2)-n; k*sum(i=1, k, (-1)^(i+k)*i^(m-1)*binomial(k-1, i-1))} \\ David A. Corneth, Feb 17 2014 CROSSREFS Cf. A073593 first m >= n giving at least 50% probability, A085813 ditto for 95%, A055775 n^n/n!, A090583 Gosper's approximation to n!. Reflected version of A019538. Cf. A233734 (central terms). Cf. A074909, A008292, A028246. Cf. A046802, A119879, A123125, A130850, and A248727. Sequence in context: A066667 A105278 A008297 * A079641 A222864 A232433 Adjacent sequences:  A090579 A090580 A090581 * A090583 A090584 A090585 KEYWORD frac,nonn,tabl AUTHOR Hugo Pfoertner, Jan 11 2004 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 7 09:17 EDT 2022. Contains 357270 sequences. (Running on oeis4.)