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.

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

Offset: 1

Author

Hugo Pfoertner, Jan 11 2004

Keywords

• frac
• nonn
• tabl

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

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

Examples

			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] 1;
  [2] 2,      1;
  [3] 6,      6,       1;
  [4] 24,     36,      14,      1;
  [5] 120,    240,     150,     30,      1;
  [6] 720,    1800,    1560,    540,     62,     1;
  [7] 5040,   15120,   16800,   8400,    1806,   126,    1;
  [8] 40320,  141120,  191520,  126000,  40824,  5796,   254,   1;
  [9] 362880, 1451520, 2328480, 1905120, 834120, 186480, 18150, 510, 1.
		

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

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.

Programs

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

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[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 *)

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

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