|
%I #111 May 21 2021 10:18:02
%S 1,2,1,6,6,1,24,36,14,1,120,240,150,30,1,720,1800,1560,540,62,1,5040,
%T 15120,16800,8400,1806,126,1,40320,141120,191520,126000,40824,5796,
%U 254,1,362880,1451520,2328480,1905120,834120,186480,18150,510,1,3628800,16329600,30240000,29635200,16435440,5103000,818520,55980,1022,1
%N 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.
%C 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.
%C 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:
%C 11 22 33 44 55 66 77 ...
%C 21 32 43 54 65 76 87 ...
%C 31 42 53 64 75 86 97 ...
%C 41 52 63 74 85 .. .. ...
%C read by antidiagonals ->:
%C 11, 22, 21, 33, 32, 31, 44, 43, 42, 41, 55, 54, 53, 52, ....
%C The probabilities are given by Q(m,n)/n^m:
%C .(m,n):.....11..22..21..33..32..31..44..43..42..41...55...54..53..52..51
%C .....Q:......1...2...1...6...6...1..24..36..14...1..120..240.150..30...1
%C ...n^m:......1...4...1..27...8...1.256..81..16...1.3125.1024.243..32...1
%C %.Success:.100..50.100..22..75.100...9..44..88.100....4...23..62..94.100
%C P(n,n) = n!/n^n which can be approximated by sqrt(Pi*(2n+1/3))/e^n (Gosper's approximation to n!).
%C 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 s[1]s[2]...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
%C 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
%C A141618(n,n-k+1) = a(n,k) * C(n,k-1) / k. - _Tom Copeland_, Oct 25 2014
%C 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
%C 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
%C 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
%C 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
%H Reinhard Zumkeller, <a href="/A090582/b090582.txt">Rows n = 1..125 of triangle, flattened</a>
%H Paul Barry, <a href="https://arxiv.org/abs/1803.06408">Three Études on a sequence transformation pipeline</a>, arXiv:1803.06408 [math.CO], 2018.
%H Kevin Buhr, Michael Press and DMB, <a href="http://groups.google.com/group/alt.sci.math.probability/browse_thread/thread/767e45790b6c1c6b/77cb4b2e3c75ae20">Collecting a deck of cards on the street.</a> Thread in NG sci.math.
%H José L. Cereceda, <a href="https://arxiv.org/abs/2001.03208">Figurate numbers and sums of powers of integers</a>, arXiv:2001.03208 [math.NT], 2020. See triangle Table 1 p. 5.
%H Tom Copeland, <a href="http://tcjpn.wordpress.com/2015/12/21/generators-inversion-and-matrix-binomial-and-integral-transforms/">Generators, Inversion, and Matrix, Binomial, and Integral Transforms</a>
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, 2009, page 209.
%H S. Franco and A. Hasan, <a href="https://arxiv.org/abs/1904.07954">Graded Quivers, Generalized Dimer Models and Toric Geometry </a>, arXiv preprint arXiv:1904.07954 [hep-th], 2019.
%H A. Hasan, <a href="https://academicworks.cuny.edu/gc_etds/3321/">Physics and Mathematics of Graded Quivers</a>, dissertation, Graduate Center, City University of New York, 2019.
%H Hugo Pfoertner, <a href="http://www.randomwalk.de/sequences/a090582.txt">"Hit all" probabilities: Program and results.</a>
%F 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
%F 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
%F From _Tom Copeland_, Oct 07 2008: (Start)
%F 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).
%F 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.
%F 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)
%F From _Tom Copeland_, Oct 11 2011: (Start)
%F With e.g.f. A(x,t) = G(x,t) - 1, the compositional inverse in x is
%F 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)
%F 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
%F T = A008292*A007318. - _Tom Copeland_, Nov 13 2016
%F 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
%e 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.
%e Table starts:
%e [1] 1;
%e [2] 2, 1;
%e [3] 6, 6, 1;
%e [4] 24, 36, 14, 1;
%e [5] 120, 240, 150, 30, 1;
%e [6] 720, 1800, 1560, 540, 62, 1;
%e [7] 5040, 15120, 16800, 8400, 1806, 126, 1;
%e [8] 40320, 141120, 191520, 126000, 40824, 5796, 254, 1;
%e [9] 362880, 1451520, 2328480, 1905120, 834120, 186480, 18150, 510, 1.
%p T := (n, k) -> add((-1)^j*binomial(n - k + 1, j)*(n - k + 1 - j)^n, j = 0..n-k):
%p # Or:
%p T := (n, k) -> (n - k + 1)!*Stirling2(n, n - k + 1):
%p for n from 1 to 9 do seq( T(n, k), k = 1..n) od; # _Peter Luschny_, May 21 2021
%t In[1]:= Table[Table[k! StirlingS2[n, k], {k, n, 1, -1}], {n, 1, 6}] (* Victor Adamchik, Oct 05 2005 *)
%t 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 *)
%o FORTRAN program given at Pfoertner link.
%o (Haskell)
%o a090582 n k = a090582_tabl !! (n-1) !! (k-1)
%o a090582_row n = a090582_tabl !! (n-1)
%o a090582_tabl = map reverse a019538_tabl
%o -- _Reinhard Zumkeller_, Dec 15 2013
%o (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
%Y Cf. A073593 first m >= n giving at least 50% probability, A085813 ditto for 95%, A055775 n^n/n!, A090583 Gosper's approximation to n!.
%Y Reflected version of A019538.
%Y Cf. A233734 (central terms).
%Y Cf. A074909, A008292, A028246.
%Y Cf. A046802, A119879, A123125, A130850, and A248727.
%K frac,nonn,tabl
%O 1,2
%A _Hugo Pfoertner_, Jan 11 2004
|
