Q: What's a sub-factorial?
David Buck
posed a math puzzle which I'll summarize below. Part of the puzzle
mentioned factorials which I understand, and subfactorials which I've
never heard of. Can anybody enlighten me as to the meaning of a
subfactorial?
According to the show, the subfactorial of 4 is written !4 and
evaluates to 9.
Here's the puzzle: Can you create all numbers from 1 to 16 using only
three 4's and the following symbols: + - * / sqrt decimal point
(as in .4) and repeating decimal point (i.e., .4...). To go higher
than 16, you can use factorials and subfactorials. How high can you
go with these operations? The math professor who presented the puzzle
claims that he can get all numbers up to 90 but doesn't know how to
get 91.
Thanks in advance
David Buck
db...@magi.com
Kurt Foster
: I was watching the Canadian Discovery Channel the other night and they
: posed a math puzzle which I'll summarize below. Part of the puzzle
: mentioned factorials which I understand, and subfactorials which I've
: never heard of. Can anybody enlighten me as to the meaning of a
: subfactorial?
This may be in the FAQ, which see. Here's a thumbnail sketch.
Subfactorial n is the number of "derangements" of n objects, i.e. the
number of permutations of the integers 1 through n in which the k-th
position is occupied by an integer OTHER THAN k, for every k from 1 to n.
One has the formula
!n = n![1 - 1/1! + 1/2! - 1/3! + ... (+/-)1/n!}
so
!4 = 24[1 - 1 + 1/2 - 1/6 + 1/24] = 24 - 24 + 12 - 4 + 1 = 9
One can easily obtain the formula from the "inclusion-exclusion"
principle. An alternate notation is n followed by an upside-down
exclamation mark. See, e.g. Chrystal's "Textbook of Algebra".
Tony Lezard
Kurt Foster <kfo...@rainbow.rmii.com> wrote:
> Subfactorial n is the number of "derangements" of n objects, i.e. the
>number of permutations of the integers 1 through n in which the k-th
>position is occupied by an integer OTHER THAN k, for every k from 1 to n.
> One has the formula
>
>!n = n![1 - 1/1! + 1/2! - 1/3! + ... (+/-)1/n!}
...which for positive n is the closest integer to n!/e.
Something I've wondered in the past about subfactorials: has anyone come
up with an elegant generalization of these things outside the positive
integers ala the Gamma function for factorials?
--
== Tony Lezard == | PGP public key 0xBF172045 available from keyservers
to...@mantis.co.uk | or from my home page, http://www.mantis.co.uk/~tony/
pe...@solution.maths.unsw.edu.au
In article <4814qb$6...@news0.accent.net>, db...@magi.com (David Buck) writes:
|> I was watching the Canadian Discovery Channel the other night and they
|> posed a math puzzle which I'll summarize below. Part of the puzzle
|> mentioned factorials which I understand, and subfactorials which I've
|> never heard of. Can anybody enlighten me as to the meaning of a
|> subfactorial?
|>
|> evaluates to 9.
|>
|> Here's the puzzle: Can you create all numbers from 1 to 16 using only
|> three 4's and the following symbols: + - * / sqrt decimal point
|> (as in .4) and repeating decimal point (i.e., .4...). To go higher
|> than 16, you can use factorials and subfactorials. How high can you
|> go with these operations? The math professor who presented the puzzle
|> claims that he can get all numbers up to 90 but doesn't know how to
|> get 91.
|>
|> Thanks in advance
|> David Buck
|> db...@magi.com
|>
|>
n objects. ie. the number of ways to permute the numbers 1,2,....n such that
no number remains in the same position. The answer is given by
n!(1-1/1!+1/2!-1/3!+.....+(-1)^n/n!), so !4 = 4!(1/2 - 1/6 + 1/24)=9
I have not seen the notation !n before, the standard notation is
n followed by an upside down ! sign, or ||n with n underlined. (See Chrystal's
algebra Bk2 p.25).
Cheers
Peter Brown
Uni of NSW
Aust.
Packrat
pe...@solution.maths.unsw.edu.au says...
>
> I have not seen the notation !n before, the standard notation is
>n followed by an upside down ! sign
Yeah, but you try typing that! It's like @ for partial derivative.
ASCIIspeak.
>, or ||n with n underlined.
_Underlined_? Not only a double bar but _underlined_ as well? Don't you
sometimes feel that notations sometimes get carried away at times? I
remeber coming across von Neumann's Onion: Phi((((x)))). I never did
quite work out what the iterated parentheses meant - or why he bothered
to put them in.
Morgan L. Owens (himself)
.sig in subcommittee