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

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

Introduction
Who am I? Why am I talking?
Talk is about combinatorial counting method
Problem motivation
- Switching functions
- Radar filtering
- Necklaces: using 3 beads of 3 different colors, how many different necklaces are there?
Polya theory
- Permutation groups
- Burnside's Lemma

Daniel Zwillinger

Education: MIT, Caltech
Joined Raytheon in 2001 (Sr Principal Engineer)
Formerly at: RPI, JPL, BBN, IDA, MITRE, Exxon, Sandia Labs, Ironbridge Networks, consulting
Broad expertise in applied mathematics (continuous and discrete)
Books on: differential equations, statistics, integration methods, table of integrals
Editor-in-chief of $30^{\text{th}}$ edition of CRC's Standard Mathematical Tables and Formulae
Home page: http://www.mathtable.com/zwillinger

Combinatorial problems

Combinatorial optimization
- How to define a problem?
- How many solutions are there?
- How to identify the solutions?
- How to find the best solution?
Today's focus is on the number of solutions
- Standard counting problems (next 2 slides)
- Generating functions
- Standard problems (assignment problem, etc.)
- Polya theory

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	C^R(m,r)
Yes	Yes	r-permutation with replacement	P^R(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	kⁿ
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	p_k(n)

$\genfrac{\{}{\}}{0pt}{}{n}{k}$ is a Stirling cycle number
p_k(n) is the number of partitions of n into k parts

Example: Switching functions (I)

A switching function (Boolean function) assigns a 0 or 1 to each bit string of length n

$\begin{picture} (4824,1995)(0,-10) \path(12,636)(1812,636) \path(1692.000,606.00... ...\put(-1150,536){\small $\{0,1\}$} \put(-1150,-64){\small $\{0,1\}$}\end{picture}$
There are 2^2ⁿ different switching functions (For n=4 have 65,536 switching functions)

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}$

Allowing symmetries, there are only 3,984 different switching functions (see [2])!
Allowing an inverter and symmetries, there are only 222 different switching functions (see [2])!
Polya theory easily gives the number 222.

Example: Radar filtering (I)

D be a ``detection'', N is a ``no detection''
R is a ``report'', ``-'' is ``no report''
Sample filter result for ``2 out of 3'' filter
$\fbox { $ \genfrac{}{}{0pt}{}{\text{ }}{\text{ }} \genfrac{}{}{0pt}{}{\text{ inp... ...{0pt}{}{\text{ N}}{\text{ $-$}} \genfrac{}{}{0pt}{}{\text{ N}}{\text{ $-$}} $ }$
``2 out of 3'' filter has 4 states:
- State ``W'', last two input elements are ``NN''
- State ``X'', last two input elements are ``ND''
- State ``Y'', last two input elements are ``DN''
- State ``Z'', last two input elements are ``DD''

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)

For iid inputs (D has a probability of p) have transition matrix
From state $\displaystyle \bordermatrix{ & W & X & Y & Z \cr W & 1-p & p & 0 & 0 \cr X & 0 & 0 & 1-p & p \cr Y & 1-p & p & 0 & 0 \cr Z & 0 & 0 & 1-p & p \cr }$
Usual eigen-analysis yields steady state distribution:

state W X Y Z

probability (1-p)² p(1-p) p(1-p) p²

Example: Radar filtering (IV)

Hence, probability of an ``R'' is $P_{\text{D}_{\text{2 of 3}}}=p^2(3-2p)$
For a given $P_{\text{FA}}$ want to maximize $P_{\text{D}_{\text{2 of 3}}}$
Can use input distributions other than iid ...
Concept: enumerate all possible filters, pick the best
How many are there? (Look at decomposition)

$\begin{picture} (4266,1839)(0,-10) \path(633,1212)(633,1812)(3633,1812)(3633,121... ...,612)(33,1212) \path(33,1212)(633,1212)(633,612) (33,612)(33,1212)\end{picture}$
$\Longleftrightarrow$

$\begin{picture} (4266,3081)(0,-10) \path(3633,33)(2433,33) \path(2553.000,63.000... ...33,633) \path(3603.000,753.000)(3633.000,633.000)(3663.000,753.000)\end{picture}$

Counting transition diagrams

Need to know the number of directed graphs with out-degree one for different numbers of vertices.
Find (using Polya theory)

number of states S 2 3 4

naive counting S^2S 16 729 65536

number of actual filters 10 129 2836
Use Sloane [4] to identify sequence A054050: $\{$ 10, 129, 2836, 83061, 3076386, 136647824, ... $\}$ :``Number of non-isomorphic binary n-state automata'' [5]

Permutation groups: Fast review

Consider permutations of $\{1,2,3,\dots,n\}$
$\pi=$ $\begin{pmatrix} 1 & 2 & \cdots & n \\ a_1 & a_2 & \cdots & a_n \\ \end{pmatrix}$ $=\begin{pmatrix} a_1 & a_2 & \cdots & a_n \\ \end{pmatrix}$
means $\{1\to a_1$ , $2\to a_2$ ,..., $n\to a_n\}$ .
Operation: $\pi_1\circ\pi_2$ means: permute by $\pi_2$ then by $\pi_1$
$\{\pi_1,\pi_2,\dots,\pi_n\}$ can be closed to form a group G
``a'' is invariant if $\pi(a)=a$ ; `` $\textrm{Inv}(\pi)$ '' is number of elements invariant under $\pi$
Write $\pi$ as unique product of disjoint cycles; `` $\textrm{cyc}(\pi)$ '' is number of cycles in $\pi$
An equivalence relation S (on G) is defined by `` $a\ S \ b$ '' iff there exists a $\pi \in G$ such that $\pi(a)=b$

Permutation groups: Example

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

$\pi_1= \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 2 & 1 & 3 \\ \end{pmatrix}= \begin{pmatrix} 1 & 4 & 3\end{pmatrix}\begin{pmatrix} 2\end{pmatrix}$
$\pi_2= \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ \end{pmatrix}= \begin{pmatrix} 1 & 2\end{pmatrix}\begin{pmatrix} 3 & 4\end{pmatrix}$

Then

|G|=2
$\pi_2\circ\pi_1= \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \\ \end{pmatrix... ...pi_1\circ\pi_2= \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \\ \end{pmatrix}$
$\textrm{Inv}(\pi_1)=1$ $\textrm{Inv}(\pi_2)=0$
$\textrm{cyc}(\pi_1)=2$ $\textrm{cyc}(\pi_2)=2$

Burnside's Lemma

$\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}$

$G =\left\{ \pi_1,\pi_2 \right\} =\left\{ \begin{pmatrix} 1 & 2 & 3 & 4\\ 1 & 2... ...matrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\ 4 & 3 & 2 & 1\\ \end{pmatrix} \right\}$
|G|=2
$\textrm{Inv}(\pi_1)=4$ $\textrm{Inv}(\pi_2)=0$
Burnside's lemma: $\frac{1}{2}(4+0)=2$ equivalence classes
The 2 equivalence classes are $\{1,4\}$ and $\{2,3\}$

Example: Necklaces with colored beads (I)

Example: have 3 beads and 2 bead colors (B, W)
$G =\left\{ \pi_1,\pi_2 \right\} =\left\{ \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3\\ \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1\\ \end{pmatrix} \right\}$
Colorings are:
- $a=\{W,W,W\}$
- $b=\{W,W,B\}$
- $c=\{W,B,W\}$
- $d=\{W,B,B\}$
- $e=\{B,W,W\}$
- $f=\{B,W,B\}$
- $g=\{B,B,W\}$
- $h=\{B,B,B\}$
Mappings: under $\pi_2$ have $b\Longleftrightarrow e$ and $d\Longleftrightarrow g$

Example: Necklaces with colored beads (II)

$G^*=\left\{ \pi_1^*,\pi_2^* \right\}$
$\pi_1^*= \begin{pmatrix} a & b & c & d & e & f & g & h\\ a & b & c & d & e & f & g & h\\ \end{pmatrix}$
$\pi_2^*= \begin{pmatrix} a & b & c & d & e & f & g & h\\ a & e & c & g & b & f & d & h\\ \end{pmatrix}$
|G|=|G^*|=2
$\textrm{Inv}(\pi_1)=3$ , $\textrm{Inv}(\pi_2)=1$ : Burnside $\Longrightarrow\frac{1}{2}(3+1)=2$
$\textrm{Inv}(\pi_1^*)=8$ , $\textrm{Inv}(\pi_2^*)=4$ : Burnside $\Longrightarrow\frac{1}{2}(8+4)=6$
The 6 equivalence classes are:
$\{a\}$ , $\{b,e\}$ , $\{c\}$ , $\{d,g\}$ , $\{f\}$ , $\{h\}$
Note: 4 classes of 1 element, 2 classes of 2 elements

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}$

$G = \left\{ \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \\ \end{pmatrix}, \begin{pm... ...\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \\ \end{pmatrix} \right\}$
|G|=3
$\textrm{Inv}(\pi_1)=3$ , $\textrm{Inv}(\pi_2)=0$ , $\textrm{Inv}(\pi_3)=0$
Burnside lemma: $\frac{1}{3}(3+0+0)=1$ equivalence class
The single equivalence class is $\{1,2,3\}$

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

Three different colored beads (Black, White, Gray) on an equilateral triangle. Allow rotations.

$\begin{picture} (8416,4549)(0,-10) \put(1208,4227){\ellipse{600}{600}} \put(2108... ...2427){$c$} \put(1208,27){$d$} \put(4208,27){$e$} \put(7208,27){$f$}\end{picture}$

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

$G^*=\left\{ \pi_1^*,\pi_2^*,\pi_3^* \right\}$ |G^*|=3
$\pi_1^*= \begin{pmatrix} a & b & c & d & e & f \\ a & b & c & d & e & f \\ \end{pmatrix}\qquad \textrm{Inv}(\pi_1^*)=6$
$\pi_2^*= \begin{pmatrix} a & b & c & d & e & f \\ b & c & a & e & f & d \\ \end{pmatrix}\qquad \textrm{Inv}(\pi_2^*)=0$
$\pi_3^*= \begin{pmatrix} a & b & c & d & e & f \\ c & a & b & f & d & e \\ \end{pmatrix}\qquad \textrm{Inv}(\pi_3^*)=0$
Burnside lemma: $\frac{1}{3}(6+0+0)=2$ equiv classes
The equivalence classes are $\{a,b,c\}$ and $\{d,e,f\}$
Note: If flips are allowed, then one equivalence class
[Need to add $\pi_4=(1\ 3\ 2)$ , $\pi_5=(2\ 1\ 3)$ , $\pi_6=(3\ 2\ 1)$ ]

Special case of Polya's Theorem

$\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)

Assume k beads
$G=\left\{ \pi_1,\pi_2 \right\}$
$\pi_1=(1)(2)(3) \cdots (k)$
$\pi_2= (1 \ k) (2 \ k-1) (3 \ k-2) \cdots$
$\textrm{cyc}(\pi_1)=k$ $\textrm{cyc}(\pi_2)=\begin{cases} \frac{k}{2} & \text{if $k$\space is even} \\ \frac{k+1}{2} & \text{if $k$\space is odd} \\ \end{cases}$
Number of equivalence classes of colorings is
$\begin{displaymath} \begin{cases} \frac{1}{2}\left[ m^k + m^{k/2} \right] & \tex... ...m^{(k+1)/2} \right] & \text{if $k$\space is odd} \\ \end{cases}\end{displaymath}$

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)

Assume m colors
$G=\left\{ \pi_1,\pi_2,\pi_3 \right\}$ |G|=3
$\pi_1=(1)(2)(3)$ $\textrm{cyc}(\pi_1)=3$
$\pi_2=(123)$ $\textrm{cyc}(\pi_2)=1$
$\pi_3=(132)$ $\textrm{cyc}(\pi_3)=1$
Number of equivalence classes of colorings is
$\begin{displaymath} \frac{1}{3}\left[ m^3+2m \right]\end{displaymath}$
For m=3 have 11 colorings
Before: 2 colorings with one B, one W, and one G

Permutation groups: Cycle index

Assume $\pi$ has $\begin{cases} & \text{$b_1$\space cycles of length 1} \\ & \text{$b_2$\space c... ...ngth 2} \\ & \vdots \\ & \text{$b_k$\space cycles of length $k$} \\ \end{cases}$
Encode each $\pi$ by $x_1^{b_1} \ x_2^{b_2} \ \dots \ x_k^{b_k}$
Note: $\sum_i b_i(\pi)=\textrm{cyc}(\pi)$
Cycle index of G is normalized sum of encodings
$\begin{displaymath} P_G(x_1,x_2,\dots,x_k)= \frac{1}{\vert G\vert} \sum_{\pi\in G} x_1^{b_1(\pi)} \ x_2^{b_2(\pi)} \ \cdots \ x_k^{b_k(\pi)}\end{displaymath}$

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)

Assume k beads
$G=\left\{ \pi_1,\pi_2 \right\}$
$\pi_1=(1)(2)(3) \cdots (k)$
$\pi_2= (1 \ k) (2 \ k-1) (3 \ k-2) \cdots$
$b_1(\pi_1)=k$ and $0=b_2(\pi_1)=b_3(\pi_1)=\dots$
If k is even, then $b_2(\pi_2)=\frac{k}{2}$ and $0=b_1(\pi_2)=b_3(\pi_2)=\dots$
If k is odd, then $b_1(\pi_2)=1$ , $b_2(\pi_2)=\frac{k-1}{2}$ and $0=b_3(\pi_2)=b_4(\pi_2)=\dots$

Example: Necklaces with colored beads (V b)

Cycle index is ( $x_i=\sum_{c\in C} w^n(c)$ )
$\begin{displaymath} P_G(x_1,x_2)= \begin{cases} \frac{1}{2}\left[ x_1^k + x_2^{k... ...2^{(k-1)/2} \right] & \text{if $k$\space is odd} \\ \end{cases}\end{displaymath}$
If m=1 color (Black) available: x₁=B, x₂=B²
- For k=2 have $P_G=\frac{1}{2}\left( B^2+\left( B^2 \right)^{1} \right)=B^2$
- For k=3 have $P_G=\frac{1}{2}\left( B^3+B\left( B^2 \right)^{1} \right)=B^3$
- In general: P_G=B^k
- Conclusion: there is a single coloring, and it has all black beads

Example: Necklaces with colored beads (V c)

If m=2 colors (Black, White) available: x₁=(B+W), x₂=(B²+W²)

For k=2 have $P_G= \frac{1}{2}\left( (B+W)^2+\left( B^2+W^2 \right)^{1} \right)=W^2+BW+B^2$

$\begin{picture} (2744,2444)(0,-10) \put(922,2107){\ellipse{600}{600}} \put(1822,... ...,307) \path(1222,307)(1522,307) \path(2122,307)(2422,307)(2722,607)\end{picture}$

There are 3 distinct colorings

Example: Necklaces with colored beads (V d)

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

For k=3: $P_G= \underbrace{W^3 +2B^2W}_{\text{shown below}} +2BW^2+B^3$

$\begin{picture} (3644,2444)(0,-10) \put(922,2107){\ellipse{600}{600}} \put(1822,... ...{\mddefault}{\updefault}$2\times$}}}}} \put(-900,1200){$2\times$} %\end{picture}$

There are 6 distinct colorings
For even $k\ge4$ have: $P_G=W^k + \frac{k}{2} BW^{k-1} + \dots$

Example: Necklaces with colored beads (V e)

If m=3 colors (Black, White, Shade) available: x₁=(B+W+S), x₂=(B²+W²+S²)

For k=2 have 6 distinct colorings:

$\begin{displaymath} \begin{split} P_G&=\frac{1}{2}\left( (B+W+S)^2+(B^2+W^2+S^2) \right)\\ &=(B^2+W^2+S^2)+(BW+BS+SW) \\ \end{split}\end{displaymath}$

For k=3 have 18 distinct colorings:

$\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)

$G=\{\pi_1,\pi_2,\pi_3\}$ , |G|=3
$\pi_1= \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \\ \end{pmatrix}=(1)(2)(3) \qquad b_1(\pi_1)=3$
$\pi_2= \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ \end{pmatrix}=(2\ 3\ 1) \qquad b_3(\pi_2)=1$
$\pi_3= \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \\ \end{pmatrix}=(3\ 1\ 2) \qquad b_3(\pi_3)=1$
Pattern inventory: $P_G=\frac{1}{3}\left( x_1^3+2x_3 \right)$
For m=3 colors have 11 colorings:
$\begin{displaymath} \begin{split} P_G &=\frac{1}{3}\left[ (B+W+S)^3+2\left( B^3+... ...3+S^3 \right) + \dots + \underbar{2BWS} + \dots \\ \end{split}\end{displaymath}$

Conclusion

Many applications of Polya theory:
- bracelets (rotations of an n-gon)
  For n=6 find $P_G=\frac{1}{6}\left[ x_1^6+x_2^3+2x_3^2+2x_6 \right]$
- photomasks for chips
- molecular structures
- non-isomorphic graphs
- seating arrangements
Polya theory is more advanced than shown here
Daniel Zwillinger can help in formulating and solving discrete and continuous mathematical problems (Sudbury 1-1-565, telephone 978-440-1660)

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.

number of states S	2	3	4
naive counting S^2S	16	729	65536
number of actual filters	10	129	2836

state	W	X	Y	Z
probability	(1-p)²	p(1-p)	p(1-p)	p²