Swiss Micros DM42: Subfactorial and Numworks Update (16.3)

Swiss Micros DM42: Subfactorial

Happy Labor Day!

This is a request by Marko Draisma and gratitude to Mr. Draisma.

Calculating the Subfactorial

A common,  and perhaps the most straight forward, formula to calculate the subfactorial is:  

!n = n! × Σ((-1)^k ÷ k!, k=0 to n)

Yes, the subfactorial is written with the exclamation point first.  The subfactorial finds all the possible arrangements of a set of objects where none of the objects end up in their original position.

For example, when arranging the set {1, 2, 3, 4} the subfactorial counts sets such as {2, 1, 4, 3} and {3, 4, 1, 2} but not {1, 4, 3, 2}.  For the positive integers:   !n < n!.

I am going to present two programs.  The first will use the formula stated above.

The second uses this formula, which will not require recursion or loops:

!n = floor[ (e + 1/e) × n! ] - floor[ e × n! ]

Note: Since the N! function on the DM42 accepts only positive integers, we can use the IP (integer part) to simulate the floor function.

integer(x) = { floor(x) if x ≥ 0,  ceiling(x) if x < 0

The following programs can be used on Free42, HP 42S, or Swiss Micros DM42.

Swiss Micros DM42 Program:  Subfactorial Version 1

This is a traditional route.  Registers used:

R01:  k,  counter

R02:  sum register 

R03:  n!, later !n

Program labels can start with symbols on the 42S.

01  LBL "!N"

02  STO 01

03  N!

04  STO 03

05  0

06  STO 02

07  RCL 01

08  1E3

09  ÷

10  STO 01

11  LBL 00

12  RCL 01

13  IP

14  ENTER

15  ENTER

16  -1

17  X<>Y 

18  Y↑X

19  X<>Y

20  N!

21  ÷

22  STO+ 02

23  ISG 01

24  GTO 00

25  RCL 02

26  RCL× 03

27  STO 03

28  RTN

Swiss Micros DM42 Program:  Subfactorial Version 2

I only put 2 in the label to distinguish the two programs.  

01  LBL "!N 2"

02  N!

03  ENTER

04  ENTER

05  1

06  E↑X

07  ENTER

08  1/X

09  +

10  ×

11  IP

12  X<>Y

13  1

14  E↑X

15  ×

16  IP

17  -

18  RTN

Examples

!2 = 1

!3 = 2

!4 = 9

!5 = 44

!9 = 133,496

!14 ≈ 3.2071E10

Sources

"Calculus How To:  Subfactorial"   College Help Central, LLC .https://www.calculushowto.com/subfactorial/ Retrieved September 5, 2021. 

Weisstein, Eric W. "Subfactorial." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Subfactorial.html  Retrieved September 5, 2021

Numworks 16.3 Update

Numworks recently updated its firmware to Version 16.3.  Find details of the changes and additions here:

https://my.numworks.com/firmwares

All original content copyright, © 2011-2021.  Edward Shore.   Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited.  This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author. 

Combinations: Arranging Permutations with Three Ascending Consecutive Numbers

Question:  How many ways can a digits of a number be arranged so that at least three digits are in (i) ascending order and (ii) consecutive positions?

The Number 1234 (4 digit numbers)

Question:  How many ways can I arrange the digits of the number 1234 so that each permutation has at least three digits are in (i) ascending order and (ii) consecutive positions?

For example, desired permutations are 1234, 2134, and 4123.

Calculation:

The requirements that three digits are in ascending and consecutive order are be satisfied if the permutation contains any of the following:  123, 124, 134, and 234.

Treat the mentioned permutations as one object and the remaining number as one. Three slots has the group 123, 124, 134, and 234.  The corresponding last digit for each of the group is 4, 3, 2, and 1, respectively.  The number of arrangements so far is 4 * 2 = 8.   We are not done though.  Here are the eight arrangements calculated:

1234
1243
1342
2341
4123
3124
2134
1234

Note that 1234 appears twice.  Let's remove the duplicate.   We are left with 4 * 2 - 1 = 7. A table of all possible arrangements of 1234 (with the desired permutations highlighted). 

 
The Number 12345 (5 Digits)

Let's address the same question, this time with the arranging the digits of 12345.

Calculation:
 
The requirements that three digits are in ascending and consecutive order are be satisfied if the permutation contains any of the following:  123, 124, 125, 134, 135, 145, 234, 235, 245, and 345.  There are 10 three-digit combinations. 

Like before, treat the three digit combinations as "one object" and the two remaining digits separately.  For example, the combo 124 will fill three digits, 3 and 5 will complete the other two digits.  The gross number of permutations are (10 * 3) * 2 * 1 = 60.  Like the last problem, we have to account for duplicates.  In those 60 permutations counted, 12345, 12354, 12453, 13452, 23451, 21345, 51234, 41235, 31245 are counted twice, and 12345 counted thrice.  Removing 10 duplicate permutations, we arrive at our final answer: 60 - 10 = 50.

The complete calculation is:  (10 * 3) * 2 * 1 - 10 = 50.


A table of all possible arrangements of 12345 (with the desired permutations highlighted) is shown below:

I am not 100% sure if there was a formula for answering this question - but here is a way to find such arrangements using brute force.  What inspired me to do pursue this question was this video published by Numberphile:

https://www.youtube.com/watch?v=CwIAfkuXc5A 

In this video, Simon Pampena arranges nine numbered cards and addressed how often those cards are arranged with at least four cards are in ascending or descending order.  However, Pampena does not the requirement that the ordered cards are arranged in consecutive slots.  


BTW, I am back from Seattle in Southern California.  

Have a great weekend - the rest of it - and I'll talk to you next time!

Eddie


 

Permutations: When Objects Repeat

Monday's blog entry (10/22/2012), Factorials and Arrangements of Unique Objects dealt with permutations of arranging a group of objects where all the objects are unique. Today's blog entry looks at three situations where objects can be repeated.

All the Choices are Available all the Time

This is where you make permutations in which all the objects are available for each slot. For example, let's take a five digit zip code. There are five slots and for each slot the 10 digits are available: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.

For the first slot there are 10 choices. For each of the 10 choices, the second slot presents another 10 choices. For each of those 10 choices, the third slot presents another 10 choices. And so on.

The number of arrangements is: 10 × 10 × 10 × 10 × 10 = 100,000. There are 100,000 five-digit zip codes possible, 00000 to 99999.

Remember when calculating permutations, order matters. For our example, 11110, 11101, 11011, 10111, and 01111 are five different arrangements. The general rule is presented below.

---

Permutations where all the choices are available all the time = n^k

where
n = number of objects
k = number of slots

---

Objects Can Repeat, but with Some Restrictions

This is similar to the first situation in the way of calculating the number of permutations (arrangements).

Let's say we are on a very famous game show. One of it's mini games is played for a car valued anywhere from $20,000 to $59,999. We want to know how many possible prices for this game are possible.

Looking at the range from $20,000 to $59,999: we can see the choices for each of the five digits. The first digit must be a 2, 3, 4, or 5. The other four digits can be anything 0 through 9 (10 choices each).

The number of prices possible are 4 × 10 × 10 × 10 × 10 = 40,000.

So using a random guess, the contestant has a 1 in 40,000 choice in getting the price exactly right.

Another mini-game offers cars from $11,111 to $36,666 where the first digit is given to the contestant (1, 2, or 3) and the contestant tries to roll the other four digits using a single die. The die contains the numbers 1, 2, 3, 4, 5, and 6. Our task to find out how many prices are possible.

There are 3 choices for the first digit, and 6 choices for the other four digits.

The number of prices possible are 3 × 6 × 6 × 6 × 6 = 3,888.

This mini-game can be played up to 3,888 times before a price repeats.

---

Permutations where:
1) Different slots can have restrictions
2) Each choice is independent

P = (number of choices for slot 1) × (number of choices for slot 2) × ... × (number of choices for slot k)

---

Rearranging a Group of Objects where some of the Objects Repeat

In this situation we are finding the number of permutations of a group of objects, except some of the objects repeat.

Let's try to find the number of ways to arrange the letters in the word PHYSICS, removing any restriction that the arrangement has to make a sensible word (HYSSICP would count as arrangement).

In the word PHYSICS, there is 1 "P", 1 "H", 1 "Y", 2 "S"s, 1 "I", and 1 "C", for a total of 7 letters. PHYSICS counts as one permutation, regardless which "S" is used in each slot. We still have 7 letters, which can be arranged 7! = 5,040 ways, but have to account for the 2 "S"s.

The true number of ways to arrange the letters in the word PHYSICS is 2,520 ways.

7! / 2! = 5,040/2 = 2,520

Coincidentally, the calculation is really 7! / (1! × 1! × 1! × 2! × 1! × 1!). However, 1! = 1. Hence, 1! × 1! × 1! × 2! × 1! × 1! = 2!.

Let's take another example. Find the number of ways to arrange the letters in the "word" AAABB. In this example, there are 3 "A"s and 2 "B"s for a total of 5 letters.

If all the letters were unique, the number of ways is 5!. But we have to account for the repeats. Divide by 3! for the "A"s and 2! for the "B"s. The result is:

5! / (3! × 2!) = 120 / (6 × 2) = 10

There are only 10 ways to arrange the letters of the "word" AAABB. The ten are:

AAABB
AABAB
AABBA
ABABA
ABBAA

BABAA
BBAAA
ABBAA
AABBA
BAAAB

---

Finding the Number of Arrangements of Objects Where Some Objects Repeat

n! / ( (k_1)! × (k_2)! × ... × (k_m)! )

where:
n = the total number of objects, including repeated objects
m = the number of unique objects
k_1 = number of "k_1" objects
k_2 = number of "k_2" objects
and so on until...
k_m = number of "k_m" objects

The expression above is known as a multinomial coefficient.

---

I hope this day is well for each of you. Thank you for your comments and suggestions. Take care,

Eddie


Source:
Marcus, Daniel A. "Combinatorics: A Problem Orientated Approach" Mathematical Association of America, Washington DC. 1998.


This blog is property of Edward Shore, 2012.

Factorials and Arrangements of Unique Objects

Last weekend my dad asked me about my blog, and the last entry was about factorials of large numbers. Clicking on this link will take you there. On our way to classic car auto shop in Orange, CA; my dad and I talked about the factorials as I tried to come up with a way of finding applications using factorials. Last weekend became the inspiration for my blog entry. Love you, Dad.

Note: This blog entry will cover factorials of non-zero integers, that is n = 0, 1, 2, 3...

---

Factorials

The factorial of a non-negative integer, written with an exclamation mark after the number, is defined as:

n! = n × (n - 1) × (n - 2) × (n - 3) × ... × 3 × 2 × 1

Start by multiplying n by n less 1, then multiplying the product by n less 2, and repeat until you get to 1.

Examples
5! = 5 × 4 × 3 × 2 × 1 = 120
8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320

---

What about 0! ?

By definition, 0! = 1. Dr. James Tanton, Ph. D (www.jamestaton.com) gives an explanation why mathematicians choose to in video: Link to Video

Simply put, 0! = 1 is just defined this way.

---

Arrangements

In this section, we consider three common arrangement problems. The task is to find the number of possible permutations a group of objects can be arranged. A permutation is an arrangement where the order of which the objects are placed is important.

In this section, we are going to arrange all the objects.

Arrangement of Unique Objects

Consider a bookshelf that has room for five books. For simplicity, let's call the books A, B, C, D, and E (and not "Combinatorics", "The Irrationals", "Euclid's Number", "Programming", and "Making Soup for Dummies" like I originally planned.)

The for the first slot there are five choices. The second slot provides four choices. Whatever is available for the second slot depends on what book was put in the first slot. For example, if I choose to put book A in the first slot, the books B, C, D, and E are available for the second slot. Instead, if I choose to put book C in the first slot, then A, B, D, and E are available.

For each choice I make on the first slot, I get four choices for the second. Considering the first two slots alone, this gives me a total of 5 × 4 = 20 arrangements.

Continuing in this way, there are three choices for the third slot, two choices for the fourth slot, and whatever is left over gets the fifth slot.

So, the total number of arrangements of five books is:

5 × 4 × 3 × 2 × 1 = 5! = 120

Yes, 120 different arrangements. Since order is important, the arrangement is considered a permutation.

In general, working with n objects and n slots:
There are n objects for the first slot,
there are n - 1 objects for the second slot,
there are n - 2 objects for the third slot,
and so on,
until we reach 1 slot left for the last object.

Hence, the number of arrangements are:

n × (n - 1) × (n - 2) × ... × 1 = n!

---

Number of Permutations of n Unique Objects = n!

---

Arrangement of Unique Slots, Limited Spaces Available

Let's go back to our problem of arranging five books (A, B, C, D, and E) but this time, we only have three slots available.

For the first slot, I have 5 books available to choose from. Depending on what I choose, I will have 4 books for the second slot. Each of those 4 books present a choice of the 3 books for the last slot. Whatever is left either goes somewhere else in the house or gets donated.

The number of arrangements that are available to me has decreased due to the fact I only have three slots available. Hence, 5 × 4 × 3 = 60.

Observe if we multiply 5 × 4 × 3 by (2 × 1)/(2 × 1) we get:

5 × 4 × 3
= (5 × 4 × 3 × 2 × 1) / (2 × 1)
= 5! / (2 × 1)
= 5! / (5 - 3)!

Basically we are taking all of the ways 5 books can be arranged, and then dividing that number by all the ways the 2 books that are not going to be used can be arranged.

Doing the above in the general case is how we arrive at the formula for permutations:

nPk = n! / (n - k)!

where we have n objects and k slots to fill.

---

Permutations: nPk = n! / (n - k)! where n ≥ k. Order is important.

---

Until next time, have a great day!

Eddie



This blog is property of Edward Shore, 2012.