Combinations with repetition (an intuitive way to it?)

[Ryker]

Hey guys (and gals),

I've been wondering whether there's an intuitive way to understanding combinations with repetition, so that you would just use the basic rules of the sum and product instead of going with the handy formula that pertains to said combinations.

I had an example where in a flowershop you have 4 different kinds of flowers. You want to make bouquets of 7 flowers, and the question is how many different kinds of bouquets you can thus make. Now if you plug everything in the (n+k-1 k) it's all good and you get the result, but I just can't get my head around how you'd do that without using the said equation. Or if you use it, how do you make intuitive sense of it? I guess what I'm asking is is whether there's something akin to the connection between the rule of product and permutations where, for example, if you have to set up 4 different kinds of flowers into a bouquet of 4 flowers where order plays a role you can pretty much see where the 4! equation comes from, as you can just as easily write down 4 (options for the first flower), 3 (options for the second flower), 2 (-||-) and 1.

Now I've read the example on http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition", but I didn't find it to help me understand why you're plugging in those numbers on an intuitive level, it just helps in understanding why you use the above-mentioned formula.

 

[JSuarez]

Personally, I like this one:

Suppose that you want to choose, with repetition and disregarding order, n objects of k distinct types. You can encode each selection as a binary sequence like this:

- Take k - 1 0's and n 1's; the 0's function as markers to separate the distinct kinds of objects, while the 1's represent the selected objects.

- The sequence has the form 1...101...101...1.

To give an example, suppose that you have three objects, {a,b,c} and choose 5 of them each time; then typical selections will look like (disregarding order):

aabcc, abbbc, bbccc, aaacc, etc.

And the corresponding sequences are: 1101011, 1011101, 0110111, 1110011

Note that you need only two 0's to distinguish three kinds, and that the sequences begins, ends, or have consective 0's iff at least one of the kinds is not selected.

But then you reduced the original problem to the one of counting a particular class of binary sequences which is typically much easier: the sequences will have length n + k - 1, and k - 1 0's; as C(m,j) counts the number of length m sequences with j 1's, then you have C(n + k - 1,n).

Just two notes: relative to your post, I inadvertedly exchanged the n and k and this interpretation is not original; in fact, it's in most good combinatorics books; see, for example, Biggs' "Discrete Mathematics".

 

[Ryker]

Thanks a lot for the response and it does help somewhat. Your example seems similar to the one given on wikipedia, so unfortunately I still don't really have an intuitive grasp of the concept, but then again, maybe this isn't supposed to be as intuitive as basic permutations and variations. I understand the formula a bit better now, but I guess I still see the solution only in the context of said formula as opposed to feeling natural enough to only use the rule of product to derive the result.

This is not your fault, though, so don't take it as not providing good enough help :) It really is greatly appreciated, and if you have anything to add that would aid me in getting a better feel for these combinations, please do so.