login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 two-dimensional 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 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

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

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..n-1) (-1)^k * C(n, k) * (n-k)^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 + [1-exp(x t)]/t} = 1 + 1 x + (2 + t) x^2/2! + (6 + 6t + 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 + 4t + 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 + 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(n-1, k) + Q(n-1, k-1)). - 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+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.

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 27 02:08 EDT 2017. Contains 284143 sequences.