Skip to main content

Math Lesson - Combinations and Permutations

Very often I need to deal with combinations and permutations. This is just a recap on high school math which I tend to lose touch on.

A combination doesn't care about the order, e.g. 123 is the same as 312
A permutation does

Imagine there are 5 numbers 1,2,3,4,5. We need to choose 3, n=5, r=3. How many combinations? How many permutations?

Permutation with repetition n^r

Imagine there are 3 slots for the 3 numbers. There's 5 number we can fill the first slot. 5 numbers we can fill the second and 5 number we can fill the third. 5*5*5 permutations.

Permutation without repetition n!/(n-r)!

There's 5 number we can fill the first slot. 4 numbers we can fill the second and 3 number we can fill the third. 5*4*3 permutations.

Combinations without repetition n!/((n-r)!r!)

Imagine permutations without repetition. Now remove the sens of permutations Hence an additional r! in the denominator.

Combinations with repetition (n+r-1)!/r!(n-1)!

This needs an unusual approach to understand, at least for me this worked out as in http://www.statlect.com/subon2/comcom1.htm

We need to order two scoops of ice cream, choosing among four flavours: chocolate, pistachio, strawberry and vanilla. It is possible to order two scoops of the same flavour. How many different combinations can we order? The number of different combinations we can order is equal to the number of possible combinations with repetition of 2 objects from 4. Let us represent an order as a string of crosses (x) and vertical bars (|), where a vertical bar delimits two adjacent flavours and a cross denotes a scoop of a given flavour. For example,

x | | | x      1 chocolate, 1 vanilla
| | x x |      2 strawberry

where the first vertical bar (the leftmost one) delimits chocolate and pistachio, the second one delimits pistachio and strawberry and the third one delimits strawberry and vanilla. Each string contains three vertical bars, one less than the number of flavours, and two crosses, one for each scoop. Therefore, each string contains a total of five symbols. Making an order is equivalent to choosing which two of the five symbols will be a cross (the remaining will be vertical bars). So, to make an order, we need to choose 2 objects from 5. The number of possible ways to choose 2 objects from 5 is equal to the number of possible combinations without repetition of 2 objects from 5, i.e 5! /(5-2)!2!

Comments

Post a Comment

Popular posts from this blog

Detaching a process from terminal - exec(), system(), setsid() and nohup

Linux processes are created by fork() and exec(). The very first process of POSIX systems is init and subsequent processes are derived from the init as parent. These subsequent processes are child processes. During forking the parent process copies itself - with all I/O, address space, stack, everything. The only thing that is different is the process ID. The parent and child will have 2 different process IDs. The system() library function uses fork(2) to create a child process that executes the shell command specified in command using execl(3) as follows: execl("/bin/sh", "sh", "-c", command, (char *) 0); system() returns after the command has been completed. system() executes a command specified in command by calling /bin/sh -c command , and returns after the command has been completed. During execution of the command, SIGCHLD will be blocked, and SIGINT and SIGQUIT will be ignored.  system() calls are often made within programs to execut...
Post a Comment
Read more

sprintf, snprintf, strcpy, strncpy and sizeof operator

"C library functions such as strcpy (), strcat (), sprintf () and vsprintf () operate on null terminated strings and perform no bounds checking." "snprintf is safer than sprintf" What do these statements really mean? int sprintf ( char * str , const char * format , ... )  int snprintf ( char * s, size_t n, const char * format, ... );  char * strcpy ( char * destination, const char * source ); char * strncpy ( char * destination, const char * source, size_t num );   The usage is something like; char* msg1 = new char[10]; strcpy(msg1, "test"); // 1 char buffer[128]; sprintf(buffer, "%s", msg); //2 strcpy : Copies bytes until it finds a 0-byte in the source code. The string literal "test" has 4 characters and a terminating null character at end, therefore needs 5 characters at least on msg1.  Is this dangerous? Yes, because if the source message is not null terminated it will read until a null character ...
Post a Comment
Read more

Vaadin vs GWT

From Chapter 1 of book of Vaadin I quote the following. Vaadin Framework is a Java web application development framework that is designed to make creation and maintenance of high quality web-based user interfaces easy. Vaadin supports two different programming models: server-side and client-side . The server-driven programming model is the more powerful one . It lets you forget the web and program user interfaces much like you would program a desktop application with conventional Java toolkits such as AWT, Swing, or SWT. But easier. While traditional web programming is a fun way to spend your time learning new web technologies, you probably want to be productive and concentrate on the application logic. The server-side Vaadin framework takes care of managing the user interface in the browser and the AJAX communications between the browser and the server . With the Vaadin approach, you do not need to learn and deal directly with browser technologies, such as HTML or JavaScript. ...
3 comments
Read more