Talk by Daniel Zwillinger
Raytheon
5 April 2001


This file contains: (1) a list of slide titles (hyperlinked), and (2) the contents of each slide.
A pdf version of the talk is available here

Contents

  1. Polya theory
  2. Abstract
  3. Outline
  4. Daniel Zwillinger
  5. Combinatorial problems
  6. Sample selection
  7. Balls into cells
  8. Example: Switching functions (I)
  9. Example: Switching functions (II)
  10. Example: Radar filtering (I)
  11. Example: Radar filtering (II)
  12. Example: Radar filtering (III)
  13. Example: Radar filtering (IV)
  14. Counting transition diagrams
  15. Permutation groups: Fast review
  16. Permutation groups: Example
  17. Burnside's Lemma
  18. Example: 4-bead necklaces
  19. Example: Necklaces with colored beads (I)
  20. Example: Necklaces with colored beads (II)
  21. Example: Rotations of an equilateral triangle
  22. Example: Rotations of an equilateral triangle with colored beads (I)
  23. Example: Rotations of an equilateral triangle with colored beads (II)
  24. Special case of Polya's Theorem
  25. Example: Necklaces with colored beads (III)
  26. Example: Necklaces with colored beads (IV)
  27. Example: Rotations of an equilateral triangle with colored beads (III)
  28. Permutation groups: Cycle index
  29. Polya's Theorem
  30. Example: Necklaces with colored beads (V a)
  31. Example: Necklaces with colored beads (V b)
  32. Example: Necklaces with colored beads (V c)
  33. Example: Necklaces with colored beads (V d)
  34. Example: Necklaces with colored beads (V e)
  35. Example: Rotations of an equilateral triangle with colored beads (IV)
  36. Conclusion
  37. References




Polya theory


(With a radar application motivation)

Daniel Zwillinger, PhD

5 April 2001

Sudbury 1-1-623    telephone 4-1660
Daniel_I_Zwillinger@raytheon.com

http://www.mathtable.com/zwillinger/talks/20010405/
http://nesystemsengineering.rsc.ray.com/training/memo.polya.pdf




Abstract

This lecture will show how Polya theory can be used in counting objects, which is often the design basis for statistical tests. Specifically, Polya theory determines the number of distinct equivalence classes of objects. It can also give counts for specific types of patterns within equivalence classes. While sounding esoteric, this simple-to-apply technique easily counts non-isomorphic (i.e., different) graphs, and many other combinatorial structures. An application to radar filtering of hard-limited data will be used to motivate the topic.




Outline




Daniel Zwillinger




Combinatorial problems




Sample selection

Choosing a sample of size r from m objects

Repetitions allowed? Order counts? The sample is called an Number of ways to choose the sample
No No r-combination C(m,r)
No Yes r-permutation P(m,r)
Yes No r-combination with replacement CR(m,r)
Yes Yes r-permutation with replacement PR(m,r)

\begin{displaymath}
\begin{split}
C(m,r) &= \binom{m}{r}=\frac{m!}{r!(m-r)!} \\ ...
 ...,r)=\frac{(m+r-1)!}{r!(m-1)!} \\ P^R(m,r) &= m^r \\
 \end{split}\end{displaymath}




Balls into cells

Distinguish the cells Distinguish the balls Can cells be empty Number of ways to place n balls into k cells
Yes Yes Yes kn
Yes Yes No $k! \genfrac{\{}{\}}{0pt}{}{n}{k}$
Yes No Yes $C(k+n-1,n)=\binom{k+n-1}{n}$
Yes No No $C(n-1,k-1)=\binom{n-1}{k-1}$
No Yes Yes $\genfrac{\{}{\}}{0pt}{}{n}{1}+\genfrac{\{}{\}}{0pt}{}{n}{2}+\cdots+\genfrac{\{}{\}}{0pt}{}{n}{k}$
No Yes No $\genfrac{\{}{\}}{0pt}{}{n}{k}$
No No Yes $p_1(n)+p_2(n)+\cdots+p_k(n)$
No No No pk(n)




Example: Switching functions (I)




Example: Switching functions (II)


\begin{picture}
(4824,1839)(0,-10)
\path(12,612)(1812,612)
\path(1692.000,582.00...
 ...492.000)
\path(1182.000,132.000)(1212.000,12.000)(1242.000,132.000)\end{picture}




Example: Radar filtering (I)




Example: Radar filtering (II)

Transition diagram is


\begin{picture}
(5235,2439)(0,-10)
\path(312,2412)(1212,2412)(1212,1512)
 (312,1...
 ...12,1512){R}
\put(3312,1812){R}
\put(3312,500){R}
\put(3000,1100){R}\end{picture}

``N'' is shown as a solid line

``D'' is shown as a dashed line




Example: Radar filtering (III)




Example: Radar filtering (IV)




Counting transition diagrams




Permutation groups: Fast review




Permutation groups: Example

If $G=\{\pi_1,\pi_2\}$ with

Then




Burnside's Lemma

If

\begin{displaymath}
\begin{split}
A &= \text{set of elements} \\ G &= \text{perm...
 ...quivalence relation on $A$\space induced by $G$} \\ \end{split}\end{displaymath}

Then the number of equivalence classes in S is

\begin{displaymath}
\frac{1}{\vert G\vert}\sum_{\pi\in G}
 \textrm{Inv}(\pi)\end{displaymath}




Example: 4-bead necklaces


\begin{picture}
(9044,1244)(0,-10)
\put(1822,607){\ellipse{1200}{1200}}
\put(362...
 ...(5422,607){\small\scriptsize 3}
\put(7222,607){\small\scriptsize 4}\end{picture}




Example: Necklaces with colored beads (I)




Example: Necklaces with colored beads (II)




Example: Rotations of an equilateral triangle


\begin{picture}
(1325,1350)(0,-10)
\path(633,1227)(33,252)(1233,252)(633,1227)
\put(-250,150){1}
\put(1400,150){2}
\put(600,1350){3}\end{picture}




Example: Rotations of an equilateral triangle with colored beads (I)




Example: Rotations of an equilateral triangle with colored beads (II)




Special case of Polya's Theorem

If

\begin{displaymath}
\begin{split}
G &= \text{group of permutations of $D=\{\pi_1...
 ...t of colorings of $D$\space using colors in $C$} \\ \end{split}\end{displaymath}

Then the number of distinct colorings in S(D,C) is

\begin{displaymath}
\frac{1}{\vert G\vert}\sum_{\pi\in G}
 m^{\textrm{cyc}(\pi)}\end{displaymath}




Example: Necklaces with colored beads (III)




Example: Necklaces with colored beads (IV)

Number of equivalence classes for various k and m

  k=2 beads k=3 beads k=4 beads k=5 beads k=6 beads
m=2 colors 3 \fbox {6}
10 20 36
m=3 colors 6 18 45 185 378
m=4 colors 10 40 136 544 2080




Example: Rotations of an equilateral triangle with colored beads (III)




Permutation groups: Cycle index




Polya's Theorem

Let color c have ``weight'' w(c). The pattern inventory describes the colorings, of a certain kind, as functions of the weights.

\begin{displaymath}
\begin{split}
G &= \text{group of permutations on $D=\{\pi_1...
 ...t of colorings of $D$\space using colors in $C$} \\ \end{split}\end{displaymath}

Then the pattern inventory of colorings in S(D,C) is

\begin{displaymath}
P_G\left( 
\sum_{c\in C} w (c),
\sum_{c\in C} w^2(c),
\sum_{c\in C} w^3(c),
\dots
 \right)\end{displaymath}

Note: for w(c)=1 have $\displaystyle
P_G(m,m,\dots,m)=
\frac{1}{\vert G\vert}\sum_{\pi\in G}m^{\textrm{cyc}(\pi)}$




Example: Necklaces with colored beads (V a)




Example: Necklaces with colored beads (V b)




Example: Necklaces with colored beads (V c)

If m=2 colors (Black, White) available: x1=(B+W), x2=(B2+W2)




Example: Necklaces with colored beads (V d)

If m=2 colors (B, W) are available, then




Example: Necklaces with colored beads (V e)

If m=3 colors (Black, White, Shade) available: x1=(B+W+S), x2=(B2+W2+S2)

\begin{displaymath}
\begin{split}
P_G&= \frac{1}{2}\left( (B+W+S)^3+(B+W+S)(B^2+...
 ...+2(B^2W+W^2B+B^2S\\ & \quad +S^2B+W^2S+S^2W)+3BWS\\
 \end{split}\end{displaymath}




Example: Rotations of an equilateral triangle with colored beads (IV)




Conclusion




References

1
For pictures of colored necklaces, bracelets, unlabeled necklaces, etc, visit http://www.theory.csc.uvic.ca/~cos/gen/neck.html
(be careful of terms!)

2
Harvard Computation Laboratory Staff, Synthesis of electronic computing and control circuits, Harvard University Press, Cambridge, MA, 1951.

3
Fred S. Roberts, Applied Combinatorics, Prentice-Hall, 1984.

4
Sloane's on-line encyclopedia: http://www.research.att.com/~njas/sequences/

5
F. Harary and E. Palmer, ``Number of non-isomorphic binary n-state automata'', Graphical Enumeration, 1973.

6
Daniel Zwillinger, CRC Standard Mathematical Tables and Formulae, CRC, Boca Raton, FL, 1995.