divisible binomial coefficientsby stlukits Tags: binomial coeffs, combinatorics, divisors, expectation 

#1
Jul311, 11:30 AM

P: 35

1. The problem statement, all variables and given/known data
I need to sum the binomial coefficients that are divisible by a positive integer t, i.e. [tex]\sum_{i=0}^{s}\binom{ts}{ti}[/tex] Is there any way to get rid of the sum sign? 2. Relevant equations Let t be fixed and s go to (positive) infinity (both t and s are positive integers). Let M(s) be a set with #M(s)=ts, then I am really interested in the expected value of the number of elements when you choose subsets from M whose cardinality is a multiple of t. For example, what is the mean number of elements picking subsets with cardinality 0, 3, 6, or 9 from a set with cardinality 9 (t=3, s=3)? Where does this expected value go as s (the ``grain'' of M) goes to infinity? [tex]EX=\frac{\sum_{i=0}^{s}ti\binom{ts}{ti}}{\sum_{i=0}^{s}\binom{ts}{ti}}[/tex] 3. The attempt at a solution I anticipate the solution to be lim(s>infty)EX(s)=ts/2, but I'd love to prove it. 1. The problem statement, all variables and given/known data 2. Relevant equations 3. The attempt at a solution 



#2
Jul1011, 11:53 AM

P: 35

Clarifying and rephrasing:
I have two finite sets A_{1} and A_{2} with the same number of elements (let their cardinality be s times t, where t is a fixed positive integer). Let me randomly pick elements from these two sets, with one constraint, however: the number of elements picked from A_{2} must be a tmultiple of the number of elements picked from A_{1}. If t=3, for example, and s=2, there are six elements in A_{i} and I can either pick 0 elements from A_{1} and 0 from A_{2} (there is only one way of doing this), or 1 element from A_{1} and 3 elements from A_{2} (there are 120 ways of doing this), or 2 element from A_{1} and 6 elements from A_{2} (there are 15 ways of doing this). Let X be the random variable counting the elements picked from both sets. In the example, X can be 0, 4, or 8, and the associated probabilities are 1/136, 120/136, and 15/136, so that the expectation for X is EX=4.41. I want to know what this expectation is for fixed t and variable s as s increases. I can provide the formula for fixed s and t, but I have no idea how to investigate the behaviour of this formula as s increases. [tex]EX=(1+t)\frac{\sum_{i=0}^{s}i\binom{ts}{i}\binom{ts}{ti}}{\sum_{i=0}^{s }\binom{ts}{i}\binom{ts}{ti}}[/tex] 


Register to reply 
Related Discussions  
Casio fx9860G  calculating binomial coefficients and binomial distribution  General Math  3  
Binomial Coefficients  Set Theory, Logic, Probability, Statistics  2  
binomial coefficients  Calculus & Beyond Homework  2  
Binomial Coefficients  Calculus & Beyond Homework  6  
Binomial Coefficients  Introductory Physics Homework  4 