Casio fx-9750GIII and Swiss Micros DM42: Bijections
Bijection - Three Problems
I have a subscription to Brilliant (brillant.org, this is not a paid ad), where I am taking courses of probability, quantitative finance, and quantum mechanics.
Today's blog is dealing with bijections, a technique to solve a class of counting problems. A counting problem calculates the number of ways an event, such as distributing pieces of candy among a group of people, can happen.
Here, I am working with three types of problems:
Problem 1: How many positive integer solutions are possible of the equation:
A + B + C + ... = M
M = sum of the integers A, B, C, etc.
M > A, M > B, M > C.
Problem 2: How many positive integer solutions are possible of the equation:
A + B + C + ... ≤ M
M = sum of the integers A, B, C, etc.
M > A, M > B, M > C.
Problem 3: How many ways can distribute a set amount of balls into a set of urns? Assume that the urns do not have to have an equal amount of balls.
Similar problem would be:
How many ways to distribute candy among a population of people?
How many ways to give a deck of cards from a deck to a table full of players, given that each card is randomly distributed? Assume that the players do not have equal amount of cards.
The programs on this blog uses two different approaches. The program for the fx-9750GIII uses a prompt approach while the program for the DM42 uses a direct approach.
Casio fx-9750GIII Program: BIJECT
Code:
"EWS 2023-06-12"
0 → S
ClrText
Menu "BIJECTIONS","A+B+C+...=M",1,"A+B+C+...≤M",2,"BALLS IN URNS",3
Lbl 2
1 → S
Lbl 1
"# OF VARIABLES"? → B
V + S - 1 → V
"SUM (POS. INTEGER)"? → M
Goto 4
Lbl 3
"# OF URNS"? → V
V - 1 → V
"# OF BALLS"? → M
Lbl 4
(M + V) nCr V → S
"# SOLUTIONS = "
S
Notes:
The character # is from the character map (CHAR) of the default program menu in program editing mode (Mode B).
The combination function is displayed as a bold C. I have nCr in the code listing for clarity.
Swiss Micros DM42 Program: BIJECT
Code also works for HP 42S, Plus42, Free42
Code:
00 {14-Byte Prgm}
01 LBL "BIJECT"
02 +
03 LAST x
04 COMB
05 END
Stack Set Up:
Y: number of dividers
X: number of balls
Set up the stack for the three types of problems.
Problem 1:
Y: number of variables - 1
X: sum
Problem 2:
Y: number of variables
X: sum
Problem 3:
Y: number of urns - 1
X: number of balls
Examples
Problem 1: How many positive integer solutions are possible of the equation:
A + B + C = 20
Number of variables: 3
Sum: 20
Number of dividers: 2 (the number of plus signs in the equation)
Number of solutions: nCr(20 + 2, 20) = 231
Problem 2: How many positive integer solutions are possible of the equation:
A + B + C ≤ 20
Number of variables: 3
Sum: 20
Number of dividers: 3
Since we are allowing for A, B, and C to add up to less than 20, add a slack variable, S, to "catch" any deficit to make the sum 20. Therefore, we are really solving:
A + B + C + S = 20
In listing the solutions, S is ignored.
Number of solutions: nCr(20 + 3, 20) = 1,771
Problem 3: How many ways can distribute 40 balls in to 6 urns?
Set the urns in a line, and imagine a divider in between each urn.
urn 1 | urn 2 | urn 3 | urn 4 | urn 5 | urn 6
Number of dividers: 5
Number of balls: 40
Number of distributions: nCr(40 + 5, 40) = 1,221,759
Try listing all possible distributions.
Eddie
All original content copyright, © 2011-2023. 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.