

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.


12



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


LINKS

Reinhard Zumkeller, Rows n=1..125 of triangle, flattened
Kevin Buhr, Michael Press and DMB, Collecting a deck of cards on the street. Thread in NG sci.math.
T. Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009, page 209.
Hugo Pfoertner, "Hit all" probabilities: Program and results.


FORMULA

Q(m, n) = sum_(k=0..n1) (1)^k * C(n, k) * (nk)^m where C(n, k) is the binomial coefficient "n choose k".
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 + 6t + 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 + 4t + 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 + 3t + 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


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.
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



