Wikipedia:Reference desk/Archives/Mathematics/2013 May 10

Mathematics desk
< May 9	<< Apr | May | Jun >>	May 11 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 10

Combinatorics

Suppose you have a bag with an infinite number of tiles, each labelled with a nonnegative integer. Exactly one tile is labelled "0", two tiles are labelled "1", three tiles are labelled "2", four tiles are labelled "3" etc.

Now suppose you have N such identical bags.

Given a nonnegative integer M, how many ways can you select one tile from each bag such that the sum of the selected tiles is M?

AnalysisAlgebra (talk) 13:00, 10 May 2013 (UTC)

Think of N as fixed. A generating function is $x^{N}(1-x)^{-2N}$. Sławomir Biały (talk) 13:33, 10 May 2013 (UTC)

I didn't get an $x^{N}$, but yes otherwise and the Binomial theorem is your friend. Dmcq (talk) 13:37, 10 May 2013 (UTC)

Sorry, I was inattentive. That's if the tiles are labelled starting with 1 instead of 0. It should be $(1-x)^{-2N}$. (And, as you say, the answer is clearly (the absolute value of) −2N choose M. In fact, it's just the ordered partitions of N into M parts: N+M-1 choose M-1. Sławomir Biały (talk) 13:45, 10 May 2013 (UTC)

How did you derive that generating function? AnalysisAlgebra (talk) 04:11, 13 May 2013 (UTC)

Generating function talks about it and actually gives the case of $1+2x+3x^{2}+4x^{3}+\dots$. But I just worked it out from subtracting x times that from that and you get the familiar $(1-x)^{-1}$. And then just multiplied it out N times for the different ones to give all the combinations of exactly one from each. In fact just having looked at that article it isn't very good at all, it doesn't say why one chooses one type of generating function or another (this one uses an ordinary generating function) or really what multiplying does for the different types. So a good candidate for improving. Dmcq (talk) 09:00, 13 May 2013 (UTC)

A clearer way to get the final answer is to reason as follows. Forget about the tiles and bags. Arrange N objects in a line. The problem is equivalent to the number of ways of inserting M−1 (indistinguishable) dividers between some of these objects, since they will then have been divided into M groups. (We do not exclude the possibility of two dividers being inserted between the same two objects: this corresponds to there being zero objects in the corresponding group.) Now for the clever part: think of the gaps that the dividers occupy as additional objects. The problem then boils down to the following: suppose that $N+M-1$ objects are arranged in a line. Designate $M-1$ of these as "dividers" and the remaining $N$ as "objects". This can be done in $N+M-1$ choose $M-1$ ways. Sławomir Biały (talk) 11:49, 13 May 2013 (UTC)

I should be less literal and read 'how did you...' as ' what is a good way of...' ;-) Dmcq (talk) 15:21, 13 May 2013 (UTC)

No. That is not the correct answer. The correct answer is $2N+M+1$ choose $M$. AnalysisAlgebra (talk) 04:02, 14 May 2013 (UTC)