Divisible binomial coefficients

In summary: The expectation for the number of elements picked when given a set witha t-multiple of the number of elements in a given set A (A_{1} and A_{2} in theexample) is given by:EX=\frac{\sum_{i=0}^{s}i\binom{ts}{i}\binom{ts}{ti}}{\sum_{i=0}^{s}\binom{ts}{i}\binom{ts}{ti}}
  • #1
noowutah
57
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.
 
Physics news on Phys.org
  • #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.

[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:

FAQ: Divisible binomial coefficients

What are divisible binomial coefficients?

Divisible binomial coefficients refer to the coefficients that appear in the expansion of a binomial expression, such as (a+b)^n, that are divisible by a given number.

How do you identify divisible binomial coefficients?

To identify divisible binomial coefficients, you can expand the binomial expression using the binomial theorem and then check if any of the coefficients are divisible by the given number. Alternatively, you can use the divisibility rules for numbers to quickly identify divisible coefficients.

What is the significance of divisible binomial coefficients?

Divisible binomial coefficients have various applications in mathematics, including combinatorics, number theory, and algebra. They are used to solve problems related to counting, divisibility, and properties of polynomials.

Can you provide an example of divisible binomial coefficients?

An example of divisible binomial coefficients is in the expansion of (2x+4)^5. The coefficients of x^3 and x^4, which are 40 and 80 respectively, are both divisible by 5.

How can divisible binomial coefficients be used in real-world applications?

Divisible binomial coefficients have practical applications in fields such as computer science, cryptography, and statistics. For example, in cryptography, they are used to generate secure encryption keys, and in statistics, they are used to calculate probabilities and make predictions.

Similar threads

Replies
4
Views
1K
Replies
6
Views
2K
Replies
2
Views
2K
Replies
9
Views
992
Replies
5
Views
1K
Replies
2
Views
2K
Replies
1
Views
1K
Replies
43
Views
4K
Replies
3
Views
894
Back
Top