Divisible binomial coefficients

  • Thread starter stlukits
  • Start date
  • #1
56
3

Homework Statement



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?

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

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.

Homework Statement





Homework Equations





The Attempt at a Solution

 

Answers and Replies

  • #2
56
3
binomial coefficients problem

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 t-multiple 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]
 
Last edited by a moderator:

Related Threads on Divisible binomial coefficients

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
695
  • Last Post
Replies
2
Views
519
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
5K
  • Last Post
Replies
1
Views
1K
  • Last Post
2
Replies
29
Views
6K
  • Last Post
Replies
6
Views
4K
Top