Sunday, August 27, 2023

Casio fx-9750GIII and Swiss Micros DM42: Bijections

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.