Impact factor for posts is a measurement of importance.

Impact factor for users reflect their authority, reputation and contribution on a particular topic.

Rating reflects the quality of posts.

Rating on Voofie is not a simple average of all ratings, but a weighted average of rating, weighted by the impact factor of users who rated.

Explore exciting communities of

Sum of subsets with k elements having a total sum of r

Bookmark and Share
Avatar for sciencolic

Sciencolic (sciencolic)

I love Physics, Mathematics and Science.
Japan

  • Combinatorics
    		• 0
  • Mathematics
    		• 597
  • Partition (number theory)
    		• 0
    19 Aug 10

    This question is a mirror of the question Sum of subsets which I found interesting. The problem is like this:

    Let \f$U_n = \{1,2,...,n\}\f$ , how many subsets with k elements that are having the sum of value r?

    For instance, if n = 6, k = 3, r = 10:

    The following sets:

    {1,3,6}

    {1,4,5}

    {2,3,5}

    are all the solutions. So the number of solutions is 3.

    Add comments >
    		0
    Avatar for ross_tang

    Ross Tang (ross_tang)

    Degree in Physics and Mathematics, Master in Physics
    香港

  • Combinatorics
    		• 0
  • Mathematics
    		• 809
    19 Aug 10

    In fact, your problem is quite difficult. Since it involves 3 indices.

    Let \f$A_{r,k}^n\f$ be the number of subsets of \f$U_n\f$ having k elements with the total sum of values of r.

    Now, I am going to give you the generating function.

    \f$\begin{align*} G_n(x,y) &= (1+x y)(1+x^2 y)(1+x^3 y)...(1+x^n y) \\ &= \prod_{r=1}^n (1+x^r y) \end{align*}\f$

    And \f$A_{r,k}^n\f$ is the coefficient of the \f$x^r y^k\f$ term. First of all, we required there are k elements. Therefore we find the k-th power of y, since each power of y corresponds to an element in \f$U_n\f$ . We required the k elements summing to the values r, therefore we need to find the r-th power of x. In short, you can expand the generating function for small values of n, and you will know that it is indeed the correct generating function.

    At last, to find \f$A_{r,k}^n\f$ , we use differentiation:

    \f$\displaystyle A_{r,k}^n = \frac{G_n^{(r,k)}(0,0)}{r! k!}\f$

    However it should be very difficult to find a closed-form of it. Finally, you can write down a partial difference equation of A as well.

    Add comments >

    Please login to post answer.

    Page Info
    35Impacts
    0/0 rates
    978
    Your Rating: