

A090582


Numerator Q(m,n) of 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 twodimensional array read by antidiagonals with Q(m,m) as first row and Q(m,1) as first column.


17



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

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!).
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
Let P[n] be the set of all npermutations. Build a superset Q[n] of P[n] composed of npermutations 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 <= n1. Row sums are A000670. E.g.f. is y/(1+yexp(y*x)). For example, T(3,1)=6 because there are four 3permutations 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,nk+1) = a(n,k) * C(n,k1) / 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 mpermutohedra for m=1,2,3,4 are the line segment, hexagon, truncated octahedron and omnitruncated 5cell. The first three are wellknown 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 CalabiYau 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.
Tom Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms
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 [hepth], 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

Q(m, n) = Sum_(k=0..n1) (1)^k * binomial(n, k) * (nk)^m.
Generated by Stirling numbers of the second kind multiplied by a factorial.  Victor Adamchik, Oct 05 2005
From Tom Copeland, Oct 07 2008: (Start)
G(x,t) = 1/ (1 + (1exp(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 fpolynomials for the permutohedra (see A019538).
G(x,t1) = 1 + 1*x + (1 + t)*x^2/2! + (1 + 4*t + t^2)*x^3/3! + ...
gives row polynomials for A008292, the hpolynomials 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(n1, k) + Q(n1, k1)).  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.


MATHEMATICA

In[1]:= Table[Table[k! StirlingS2[n, k], {k, n, 1, 1}], {n, 1, 6}] (* Victor Adamchik, Oct 05 2005 *)
nn=6; a=y/(1+yExp[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 !! (n1) !! (k1)
a090582_row n = a090582_tabl !! (n1)
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^(m1)*binomial(k1, i1))} \\ 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



