From: james@crc.ricoh.com (James Allen)
Subject: Re: Something to look at.
Organization: RICOH California Research Center
Date: Thu, 30 Jul 92 13:50:17 GMT

In <1992Jul28.040923.23847@athena.mit.edu>
	jimhsu@athena.mit.edu (Jimmy M.D. Hsu) [aka James Amdee] writes:
]
]Suppose you had a pattern like this:
]
]        O   O
]     O         O
]          O
]     O         O
]        O   O
]
	[et cetera -- see below]
]--
]James Amdee  MIT
]"Drum Solo!"  -Weird Al
]

There is a general method for performing this kind of enumeration.  The
idea is to treat non-numeric variables in an algebraic form.  Polya
introduced the method about half-a-century ago though there are still
many textbooks that don't discuss it.

For example a Blue-Red-Red-White-Blue combination can be represented

		             2 2
		B*R*R*W*B = B R W

or a composite combination comprising Blue-Blue or two cases of Red-White
might be
		 2
		B  + 2RW

Let's look at a recent posting which shows a simple application of this idea:

In <1494@idacrd.UUCP> desj@ccr-p.ida.org (David desJardins) writes
]Newsgroups: rec.games.bridge
]Subject: Re: Hand Strength Probabilities
]Date: 15 Jul 92 14:35:44 GMT
]
]Ben Wing <bpwing@phoenix.princeton.edu> writes:
]>Calculating the mathematical probabilities of particular point count
]>totals is a bit tricky (it's easier for particular distributions)

	(A bridge hand consists of 13 cards drawn from a 52-card deck;
	each card is assigned a "point count": (A=4, K=3, Q=2, J=1, other=0).
]
]% math
]Mathematica 2.1 for SPARC
]Copyright 1988-92 Wolfram Research, Inc.
] -- X11 windows graphics initialized --
]
]In[1]:= z1 = ((1+x*y^4) (1+x*y^3) (1+x*y^2) (1+x*y) (1+x)^9)^4 ;

	x and y aren't numbers, but rather placeholders for symbols.
	x is a card, y is a "point"; x*y^4, for example represents an Ace.
	King-Queen-Two would be x^3*y^(3+2+0)
]
]In[2]:= z2 = Coefficient [z1, x, 13] / Binomial [52, 13] ;

	...extract the combinations of 13 cards...
]
]In[3]:= Table [Coefficient [z2, y, p], {p, 0, 37}]

	...and print the answer!
]
]Out[3]= {0.00363896, 0.00788442, 0.0135612, 0.0246236, 0.0384544, 0.0518619,
]			[et cetera]
]
]                                        David desJardins

	The 9-point 3-color enumeration of James Amdee is more difficult
because of the symmetry equivalence condition.  (Amdee's buttons are
"fermions" but desJardins' playing cards are not.)  Nevertheless Polya
discovered a beautiful theorem which allows the enumeration to be made.
For a simple problem it may be faster to count the distinct patterns
by hand, but Polya's method will work on problems far too difficult for
manual solution.  The approach should be described in terms of group theory
but I will proceed with a minimum of math jargon.

]	[repeated]
]Suppose you had a pattern like this:
]
]	O   O
]     O         O
]          O
]     O         O
]        O   O
]
]With nine points, one in the middle.
]How many different ways are there
]of placing four red buttons, four
]blue buttons, and one white button
]on the nine spots.  If you can rotate
]the pattern to get a new one, it does
]not count as "different."  Is there
]a generic formula for x red, y blue,
]and z white with x+y+z=9?  How about
]for more points in the circle?
]
	Begin by writing a symbolic formula for the equivalent transformations
(rotations) of the arrangement.  Here there are eight.

	8 * F =  Identity + Rotate_45 + Rotate_90 + Rotate_135
		+ Rotate_180 + Rotate_225 + Rotate_270 + Rotate_315

Each transformation is a permutation; represent it with its cyclic structure:

	Identity = X_1 ^ 9		/* 9 one-cycles */
	Rotate_45 = X_1 * X_8		/* 1 one-cycle, 1 eight-cycle */
	Rotate_90 = X_1 * X_4 ^ 2	/* 1 one-cycle, 2 four-cycles */
		et cetera

On completing this you discover

	8 * F = X_1^9  +  4 * X_1 * X_8  +  X_1 * X_2^4  +  2 * X_1 * X_4^2

Remember that X_i is not a number, but a symbol representing i buttons.

Make the substitutions

	X_i = R^i + B^i + W^i

where R (red), B (blue) and W (white) are the types of button.

Solve for F; the coefficient of R^4*B^4*W will be the number of distinct
arrangements of 4 red buttons, 4 blue buttons and a white button !

If you don't have access to Mathematica this can still be done without much
trouble; you get

	8 * F = (9*C(8,4) + C(4,2) + 2*2) * RRRR*BBBB*W + other terms
or
	F = 80 * RRRR*BBBB*W + other terms

To illustrate the versatility of the method, suppose we change the problem
so that an arrangement and its mirror image are considered equivalent.
Now there are 16 transformations (G).

	16 * G  = 8 * F  +  4 * X_1^3 * X_2^3  +  4 * X_1 * X_2^4

where again, X_2 = R^2 + B^2 + W^2 etc.
Discarding all but the RRRR*BBBB*W terms, we get

	G = F/2 + 4*2*C(3,1)*C(3,1)/16 + 4*C(4,2)/16 = 40 + 4.5 + 1.5 = 46

The solution (46) must of course be an integer, even though some intermediate
terms are fractions.

There are many ways to use the method.  For example if you simply set
	X_i = k,  where k is the number of button colors
you get the total number of arrangements when there is no constraint on
how many buttons of each color you use.  Thus

	8 * F = X_1^9  +  4 * X_1 * X_8  +  X_1 * X_2^4  +  2 * X_1 * X_4^2

	F = (3^9  +  4 * 3 * 3  +  3 * 3^4  +  2 * 3 * 3^2) / 8 = 2502


	16 * G  = 8 * F  +  4 * X_1^3 * X_2^3  +  4 * X_1 * X_2^4

	G  = F/2  +  (4 * 3^3 * 3^3  +  4 * 3 * 3^4) / 16 = 1494

Effortlessly we have found that if all color combinations are allowed,
there are 2502 distinct ways to populate Amdee's 9-point arrangement, but
only 1494 ways if mirror images are considered equivalent.

An extension of Polya's theorem handles the case where the color-naming
is arbitary (ie, where RRRBW and BBBWR are considered equivalent) but I
will not cover that here.

James