Starling Sum

Probability Level 5

Let A ( n , k ) = ∑ S ∈ [ n ] k 1 Π ( S ) A(n,k)=\sum_{S\in[n]^{k}}\frac{1}{\Pi(S)} .

Then A ( 200 , 197 ) A(200,197) can be expressed as x × 1 0 − 363 x\times10^{-363} . Find x x up to 3 decimal places.

Details and Notations

i. [ n ] [n] means the set { 1 , 2 , . . . , n } . \{1,2,...,n\}.

ii. [ n ] k [n]^{k} means the set of all subsets of [ n ] [n] that have k k elements.

iii. ∈ \in means belongs to, i.e, S ∈ [ n ] k S\in[n]^{k} means S S is a subset of [ n ] [n] with k k elements.

iv. Π ( S ) \Pi(S) denotes the product of the elements of S S .

v. The sum is over all k k -element subsets S S of [ n ] [n] .

vi. By convection Π ( ϕ ) = 1 \Pi(\phi)=1 where ϕ \phi denotes the empty set.

vii. One must know about Stirling Numbers in order to solve it.

Example

A ( n , 1 ) = ∑ S ∈ [ n ] 1 1 Π ( S ) = 1 + 1 2 + ⋯ + 1 n A(n,1)=\sum_{S∈[n]^{1}}\frac{1}{\Pi(S)}=1+\frac{1}{2}+\cdots+\frac{1}{n}

A ( n , 2 ) = ∑ S ∈ [ n ] 2 1 Π ( S ) = 1 + 1 1 × 2 + 1 2 × 3 + 1 2 × 4 + ⋯ A(n,2)=\sum_{S∈[n]^{2}}\frac{1}{\Pi(S)}=1+\frac{1}{1\times2}+\frac{1}{2\times3}+\frac{1}{2\times4}+\cdots

Try other interesting combinatorics in my set Hard


The answer is 1.682.

Souryajit Roy by Souryajit Roy , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Souryajit Roy
Dec 1, 2014

Let A ( n , k ) = ∑ S ∈ [ n ] k 1 π ( S ) A(n,k)=\sum_{S∈[n]^{k}}\frac{1}{π(S)}

The required generating function is G n ( x ) = ( 1 + x 1 ) . . . ( 1 + x n ) G_{n}(x)=(1+\frac{x}{1})...(1+\frac{x}{n}) since a typical term of the product is x k a 1 . . a k \frac{x^{k}}{a_{1}..a_{k}} where ( a 1 , . . a k ) ∈ [ n ] (a_{1},..a_{k})∈[n] .

Now, G n ( x ) = 1 n ! ( x + 1 ) ( x + 2 ) . . . ( x + n ) G_{n}(x)=\frac{1}{n!}(x+1)(x+2)...(x+n)

Again, H n ( x ) = x ( x + 1 ) . . ( x + n − 1 ) = ∑ k = 1 n s ( n , k ) x k H_{n}(x)=x(x+1)..(x+n-1)=\sum_{k=1}^{n}s(n,k)x^{k} where s ( n . k ) s(n.k) is the Stirling number of first kind.

Hence, x G n ( x ) = 1 n ! H n + 1 ( x ) xG_{n}(x)=\frac{1}{n!}H_{n+1}(x)

Now, A ( n , k ) = c o − e f f i c i e n t A(n,k)=co-efficient o f of x k x^{k} i n in G n ( x ) G_{n}(x)

= c o − e f f i c i e n t =co-efficient o f of x k + 1 i n 1 n ! H n + 1 ( x ) = 1 n ! s ( n + 1 , k + 1 ) x^{k+1} in \frac{1}{n!}H_{n+1}(x)=\frac{1}{n!}s(n+1,k+1)

Hence, A = 1 200 ! s ( 201 , 198 ) = 1.6820561... × 1 0 − 363 A=\frac{1}{200!}s(201,198)=1.6820561...\times10^{-363} .

In computing the above expression I used the identity s ( n , n − 3 ) = ( n 2 ) ( n 4 ) s(n,n-3)=\binom{n}{2}\binom{n}{4}

1 Helpful 0 Interesting 0 Brilliant 0 Confused

Nice writeup, I used the same generating function in expanded form, but I could reduce it further to 201 198 ! [ z n ] log ⁡ ( 1 1 − z ) 198 \frac{201}{198!}[z^n] \log\left(\frac{1}{1-z}\right)^{198}

Lee Gao - 6 years, 6 months ago

Log in to reply

yes,you are right.

Basically, a generating function for s ( n , k ) s(n,k) is-

∑ n = k ∞ ( − 1 ) n − k z n n ! s ( n , k ) = l o g k ( 1 + z ) k ! \sum_{n=k}^{∞}(-1)^{n-k}\frac{z^{n}}{n!}s(n,k)=\frac{log^{k}(1+z)}{k!}

Souryajit Roy - 6 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...