Permutations, Combinations, Arrangements, and Strings

Date: 10/22/2007 at 01:00:20
From: David
Subject: permutations vs. multiplication counting principle

Many people define permutation as an ordered arrangement of elements
when elements are selected without repetition.  But suppose you have a
4-question true-false test.  Would the possible arrangement of
answers, say, TFFT, be a permutation?  I think not because the T and 
F are used with repetition.  The number of answer arrangements is
found by using the multiplication counting principle (not the
permutation formula).

This is VERY confusing to students--since order DOES make a difference 
here.  But I do NOT think it is a true permutation.  This is akin to a 
discussion on ordinary combination locks--which, of course do NOT 
involve combinations.  But these are NOT really permutation locks 
either--because the first and third numbers can repeat.  So, I call
them "permutation locks--with a twist."

The same "confusion" occurs with the usual problems about Heads and
Tails.  Is an arrangement such as HHHT on four flips a permutation?
Even in a context where we would like to distinguish HHHT from, say,
HHTH (both have 3 heads and a tail), I would say it's an arrangement, 
but not a permutation.  But, am I too pedantic on this topic?

Date: 10/22/2007 at 13:40:15
From: Doctor Peterson
Subject: Re: permutations vs. multiplication counting principle

Hi, David.

No, you're not too pedantic.  It's important to understand that this 
is not a permutation, because if it were you could use the permutation 
formula to count them, and you can't.

A permutation is, by definition, a selection of k distinct elements 
from a set, in a specific order.  Both distinctness (no repetition) 
and order are important.

Actually, the primary meaning is simply an ordering of (ALL) elements 
of a set; the permutation formula gives the number of permutations of 
SUBSETS of a given size.  (Combinations are subsets of a given size 
without regard to order.)  See the following page:

  Wolfram's Mathworld: Permutation
    http://mathworld.wolfram.com/Permutation.html 

A result in a true/false test, or coin flipping, or a "combination" 
on a lock is neither a permutation nor a combination, but a "string", 
according to this page, which distinguishes four similar concepts:

  Wolfram's Mathworld: Ball Picking
    http://mathworld.wolfram.com/BallPicking.html 

I don't know that I've seen "string" as a general term in this 
context, but it is certainly the same idea; I think of a string as an 
ordered list of "letters" from some "alphabet", which fits all your 
examples.  Again, see

  Wolfram's Mathworld: String
    http://mathworld.wolfram.com/String.html 

The following page defines "arrangement" as either a permutation or 
a combination, the key attribute being distinctness.  So your example 
is not an arrangement in this sense:

  Wolfram's Mathworld: Arrangement
    http://mathworld.wolfram.com/Arrangement.html 

If you have any further questions, feel free to write back.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 10/26/2007 at 21:27:55
From: David
Subject: Thank you (permutations vs. multiplication counting principle)

Dear Doctor Peterson:

Thank you so much for your help with respect to my question about 
permutations / combinations.  You have educated me on a new term-- 
string.  I can tell you that I have been teaching stats courses for
many years at the community college level and never knew exactly how
to refer to this concept.  I am delighted to know that I am not "too
pedantic" on this topic.
 
David