1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Divisible binomial coefficients

  1. Jul 3, 2011 #1
    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.


    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


    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. jcsd
  3. Jul 10, 2011 #2
    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.

    Last edited by a moderator: Jul 10, 2011
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook