Re: Combinatorica questions!!!
- To: mathgroup at smc.vnet.net
- Subject: [mg20545] Re: [mg20499] Combinatorica questions!!!
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Sat, 30 Oct 1999 00:13:59 -0400
- Sender: owner-wri-mathgroup at wolfram.com
These questions sound to me suspiciously like some sort of homework? Arn't
they? I guess we should have some sort of policy here whether we should
answer such questions...
Anyway, in the absence of any guidance I have decided that it is O.K. to
answer such questions provided one uses Mathematica in doing so. So let's
start with the first. By a castle I assume you mean the chess piece that is
normally in English called a rook. The question is not completely clear in
that yo do not explain whether you want to count the number of distinct
moves or distinct paths a rook must follow to get from the bottom left hand
corner to the upper right hand corner. I assume you mean the number of
paths. That means that we can assume that a path is determined by a sequence
of moves:
(right, up, right, up, ...).
Let's call the length of such a path the number of right moves in it (which
is half the total length of such a list). O.K., there is clearly only one
path of length 1, which means the rook goes all the way to the right and
then all the way to the top. Let's count the number of paths of length 2.
First, let's calculate the number of different ways we can move from the
bottom left hand corner to the bottom right hand corner in two steps. That's
the same as the number of partitions of 8 into a sum of two positive
integers, counting partitions like 3+5 and 5+3 as different. This can be
found as the coefficient of x^8 in the expression:
In[1]:=
Coefficient[Sum[x^i, {i, 1, 8}]^2, x^8]
Out[1]=
7
In other words, there are 7 different ways to get from the bottom left hand
corner to the top left hand corner in two steps. Just to be sure let's list
them:
{1,7},{7,1},{2,6},{6,2},{3,5},{5,3},{4,4}
Of course there is exactly the same number of ways to get from the bottom
right hand corner to the top right hand corner in two steps. So the total
number of ways to get from the bottom left hand corner to the top right hand
corner in a path of length 2 is 7^2, i.e. 49 (each way of going from left to
right can be paired with each way of going from bottom to top).
Similarly the number of ways of getting from the bottom left hand corner to
the top right hand corner in a path of lenght 3 is
In[2]:=
Coefficient[Sum[x^i, {i, 1, 8}]^3, x^8]
Out[2]=
21
So the total number of ways (unless I have made some bad mistake somewhere)
is:
In[3]:=
Sum[Coefficient[Sum[x^i, {i, 1, 8}]^j, x^8]^2, {j, 1, 8}]
Out[3]=
3432
The second question is much easier. A choice of 10 balls in your situation
is exactly the same as a choice of an integer between 0 and 8, an integer
betwen 0 and 9 and an integer between 0 and 7 so that the sum is 10. That's
the same as the coeficient of x^10 in the following expression:
In[5]:=
Sum[x^i, {i, 0, 8}]*Sum[x^i, {i, 0, 9}]*Sum[x^i, {i, 0, 7}] // Expand
Out[5]=
2 3 4 5 6 7
1 + 3 x + 6 x + 10 x + 15 x + 21 x + 28 x + 36 x +
8 9 10 11 12 13
44 x + 51 x + 56 x + 59 x + 60 x + 59 x +
14 15 16 17 18 19
56 x + 51 x + 44 x + 36 x + 28 x + 21 x +
20 21 22 23 24
15 x + 10 x + 6 x + 3 x + x
As you can see it is 56. (One could also just get the answer using the
function Coefficient). In part 2 you require that each color be chosen at
least one. That means that we want to know
In[6]:=
Coefficient[Sum[x^i, {i, 1, 8}]*Sum[x^i, {i, 1, 9}]*Sum[x^i, {i, 1, 7}],
x^10]
Out[6]=
35
--
Andrzej Kozlowski
Toyama International University
JAPAN
http://sigma.tuins.ac.jp
> From: "Keren Edwards" <kedwards at cobol2java.com>
To: mathgroup at smc.vnet.net
> Organization: NetVision Israel
> Date: Wed, 27 Oct 1999 02:04:59 -0400
> To: mathgroup at smc.vnet.net
> Subject: [mg20545] [mg20499] Combinatorica questions!!!
>
> Hi all!!
>
> 2 different questions:
>
> 1. how many ways does a castle have to reach from the bottom left side
> corner
> of a chess board to the upper right corner of the board if he can
> move right
> and up only?
>
>
>
> 2. you have 8 red identical balls, 9 purple identical balls and 7 white
> identical ones.
> a. How many ways can you choose 10 balls with no matter to the
> order of the balls?
> b. How many ways can you choose 10 balls with no matter to the
> order of the balls, if each color must
> be chosen once at least?
>
>
>
> Many thanx.
>
>
>