Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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