yyGrams logoyyGrams > yyGrams logoworked > chop

zang: (( ))=    

fu: ( )( )=( )

Technique: Reconstructing a Missing Outcomes Column

Counting Combinations

Often a yyGrams™ puzzle gives only one side of the outcomes catalog explicitly, leaving the other side for you to reconstruct. Checking your reconstruction is easier if you know the pattern-counting shortcut.

Combinations and permutations are two quite distinct pattern terms. Permutation doesn't enter into yy-gram analysis technique at all, since zang-fu disappearance doesn't fuss over serial line-up order. The counting shortcut for permutations is less complex than for combinations. We'll present it first to help distinguish these two ideas.

Permutations is the count of ways you can line up—order; serialize—some number of distinct objects.

Combinations is the count of ways you can grab—choose; select—some number of objects from a counted pool of distinct objects. (Without "distinct" in the definitions we couldn't count these "ways.")

Factorial shortcut

The counting shortcuts for permutations and combinations both involve the factorial shortcut.

Factorial: The term "N factorial" is abbreviated N!   The expansion of N! is the product (multiplication) of N factors descending from N to 1. For example,

1! = 1

2! = 2 • 1 = 2

3! = 3 • 2 • 1 = 6

4! = 4 • 3 • 2 • 1 = 24

—and for N greater than 4,

N! = N • (N-1) • (N-2) • ... • 2 • 1

For the special case of N = zero, 0! = 1, defined for consistency in other shortcuts.

Permutations: there are N! ways to order—line up—N distinct objects.

If you can list all combinations of names in the pool you can check off those in the explicit column of the catalog and assign the rest to the other column. Here we'll just do the first, the general part of the problem, not having any particular catalog at hand.

Let's look at a pool of five names, {a,b,c,d,e}.

There is exactly one way of grabbing them all:

{a,b,c,d,e}

—and there are obviously five ways to grab one at a time:

{a}, {b}, {c}, {d}, {e}

The general count of combinations of m objects grabbed n at a time is

C(m,n) = m!/n!(m - n)!

Check the general shortcut against the two obvious counts just above. First, the ways of grabbing all objects from a pool of m:

m!/m!(m-m)!

= m!/m!(0)!

= m!/m!

= 1

which checks with what we obviously expect. Next, the ways of grabbing one at a time from m objects:

m!/1!(m-1)!

= m!/(m-1)!

= m(m-1)(m-2)...(2)(1)

      / (m-1)(m-2)...(2)(1)

= m

Applying the Combo Shortcut

Take the pool of five names now and construct all the combinations. We already have two of the moieties we need: the "all there" there-list,

{a,b,c,d,e}

—and some "one at a time" there-lists,

{a}, {b}, {c}, {d}, {e}

To these we can immediately add the "none there" there-list, { }.

The rest will take a little more work.

Let's begin with the 4-at-a-time grabs, where we eliminate exactly one from the five. How many ways are there to do that?

Counting grabs should turn out to be the same count as for eliminations. We can grab one at a time in
5!/1!(5-1)! ways
=5!/1!•4! ways
= 5
ways,

so we should see the same count of ways to choose one at a time to leave out:
5!/4!(5-4)! ways
= 5!/4!•1! ways
= 5
ways.

{a,b,c,d}
{a,b,c,e}
{a,b,d,e}
{a,c,d,e}
{b,c,d,e}

For 3-at-a-time grabs we should count
  5!/3!(5-3)! ways
= 5!/3!•2! ways
= (5•4)/2 ways
= 10 ways

{c,d,e}
{b,d,e}
{b,c,e}
{b,c,d}
{a,d,e}
{a,c,e}
{a,c,d}
{a,b,e}
{a,b,d}
{a,b,c}



For every way of grabbing three at a time there is a way to leave out three at a time, so the count of 2-at-a-time grabs should likewise be ten:

For 2-at-a-time grabs we should count
  5!/2!(5-2)! ways
= 5!/2!•3! ways
= (5•4)/2 ways
= 10 ways

{a,b}
{a,c}
{a,d}
{a,e}
{b,c}
{b,d}
{b,e}
{c,d}
{c,e}
{d,e}



We have listed all combinations of the pool of names {a,b,c,d,e} . It remains only to strike out the there-lists of the partial (single-column) catalog we received as a puzzle, and put the remaining there-lists in the other outcome column.

Be sure not to forget the "none there" there-list, { }. A complete puzzle must take it into account.

zang: (( ))=    

shortstack disappears

fu: ( )( )=( )

extra Yang disappears



©2012 David Zethmayr
2012.4.12 12gc:10:35J