Mixes of picking $n$ things with $k$ various kinds

Intend that I am acquiring cakes for an event. There are $k$ various kinds and also I plan to acquire a total amount of $n$ cakes. The amount of various mixes of cakes could I perhaps offer the event?

2019-05-07 02:00:04
Source Share
Answers: 2

Let g (n, k) = # mixes of cakes.

Notification that:

  • g (n,1) = 1. (all the cakes coincide)
  • g (n,2) = n+1. (as an example for 5 cakes, the # of cakes of type 1 can be 0, 1, 2, 3, 4, 5)
  • g (1, k) = k.
  • g (2, k) = k * (k - 1)/ 2+k (the first term is 2 various cakes ; the 2nd term is when both cakes coincide), as long as k > 1. (or else g (2,1) = 1)
  • g (3, k) = k * (k - 1) * (k - 2)/ 6+k * (k - 1)/ 2 * 2+k (the first term is 3 various cakes ; the 2nd term is 2 various cakes, with a *2 given that there are 2 selections for which one to replicate, the 3rd term is when all 3 cakes coincide), as long as k > 2.

If we consider k as a radix as opposed to the # of cakes, after that this trouble amounts sharing the # of distinctive n - figure numbers in base k whose figures remain in arranged order. (as an example 1122399 amounts 9921231)

I assume I can share it as a nonrecursive amount:

g (n, k) = amount from j = 1 to max (n, k) of (k pick j) * h (n, j)

where h (n, j) is the # of means to dividing N cakes making use of j various kinds. (the term in the amount is when there are j distinctive cakes in fact picked.)

Yet that's around regarding I can get ... :/

modify : resemble it's combinations with repetitions = (( k+n - 1) pick n). (like the wikipedia write-up with n and also k exchanged)

2019-05-09 00:47:51

Using a method that's usually called "celebrities and also bars":

We attract $n$ celebrities straight to stand for the cakes, and also $k-1$ bars to separate them up. Every one of the celebrities to the left of the first bar are cakes of the first type ; celebrities in between the first 2 bars are of the 2nd type ;...


Here's an instance with $n=6$ and also $k=5$. We're obtaining 2 of the first type, 3 of the 2nd type, 0 of the 3rd type, 1 of the 4th type, and also 0 of the 5th type.

In order to address the trouble, we simply require to reorder the celebrities and also bars by picking the $k-1$ places for benches out of the $n+k-1$ complete places, so our solution is:

$$ \binom{n+k-1}{k-1}. $$

2019-05-09 00:45:13