Ways to multiply n elements with an associative operation
Given a number n, find the number of ways to multiply n elements with an associative operation.
Examples :
Input : 2 Output : 2 For a and b there are two ways to multiply them. 1. (a * b) 2. (b * a) Input : 3 Output : 12
Explanation(Example 2) :
For a, b and c there are 12 ways to multiply them. 1. ((a * b) * c) 2. (a * (b * c)) 3. ((a * c) * b) 4. (a * (c * b)) 5. ((b * a) * c) 6. (b * (a * c)) 7. ((b * c) * a) 8. (b * (c * a)) 9. ((c * a) * b) 10. (c * (a * b)) 11. ((c * b) * a) 12. (c * (b * a))
Approach: First, we try to find out the recurrence relation. From above examples, we can see h(1) = 1, h(2) = 2, h(3) = 12 . Now, for n elements there will be n – 1 multiplications and n – 1 parentheses. And, (a1, a2, …, an ) can be obtained from (a1, a2, …, a(n – 1)) in exactly one of the two ways :
- Take a multiplication (a1, a2, …, a(n – 1))(which has n – 2 multiplications and n – 2 parentheses) and insert the nth element ‘an’ on either side of either factor in one of the n – 2 multiplications. Thus, for each scheme for n – 1 numbers gives 2 * 2 * (n – 2) = 4 * (n – 2) schemes for n numbers in this way.
- Take a multiplication scheme for (a1, a2, .., a(n-1)) and multiply on left or right by (‘an’). Thus, for each scheme for n – 1 numbers gives two schemes for n numbers in this way.
So after adding above two, we get, h(n) = (4 * n – 8 + 2) * h(n – 1), h(n) = (4 * n – 6) * h(n – 1). This recurrence relation with same initial value is satisfied by the pseudo-Catalan number. Hence, h(n) = (2 * n – 2)! / (n – 1)!
C++
// C++ code to find number of ways to multiply n // elements with an associative operation # include <bits/stdc++.h> using namespace std; // Function to find the required factorial int fact( int n) { if (n == 0 || n == 1) return 1 ; int ans = 1; for ( int i = 1 ; i <= n; i++) ans = ans * i ; return ans ; } // Function to find nCr int nCr( int n, int r) { int Nr = n , Dr = 1 , ans = 1; for ( int i = 1 ; i <= r ; i++ ) { ans = ( ans * Nr ) / ( Dr ) ; Nr-- ; Dr++ ; } return ans ; } // function to find the number of ways int solve ( int n ) { int N = 2*n - 2 ; int R = n - 1 ; return nCr (N, R) * fact(n - 1) ; } // Driver code int main() { int n = 6 ; cout << solve (n) ; return 0 ; } |
Java
// Java code to find number of // ways to multiply n elements // with an associative operation import java.io.*; class GFG { // Function to find the // required factorial static int fact( int n) { if (n == 0 || n == 1 ) return 1 ; int ans = 1 ; for ( int i = 1 ; i <= n; i++) ans = ans * i ; return ans ; } // Function to find nCr static int nCr( int n, int r) { int Nr = n , Dr = 1 , ans = 1 ; for ( int i = 1 ; i <= r ; i++ ) { ans = ( ans * Nr ) / ( Dr ) ; Nr-- ; Dr++ ; } return ans ; } // function to find // the number of ways static int solve ( int n ) { int N = 2 * n - 2 ; int R = n - 1 ; return nCr (N, R) * fact(n - 1 ) ; } // Driver Code public static void main (String[] args) { int n = 6 ; System.out.println( solve (n)) ; } } // This code is contributed by anuj_67. |
Python3
# Python3 code to find number # of ways to multiply n # elements with an # associative operation # Function to find the # required factorial def fact(n): if (n = = 0 or n = = 1 ): return 1 ; ans = 1 ; for i in range ( 1 , n + 1 ): ans = ans * i; return ans; # Function to find nCr def nCr(n, r): Nr = n ; Dr = 1 ; ans = 1 ; for i in range ( 1 , r + 1 ): ans = int ((ans * Nr) / (Dr)); Nr = Nr - 1 ; Dr = Dr + 1 ; return ans; # function to find # the number of ways def solve ( n ): N = 2 * n - 2 ; R = n - 1 ; return (nCr (N, R) * fact(n - 1 )); # Driver code n = 6 ; print (solve (n) ); # This code is contributed # by mits |
C#
// C# code to find number of // ways to multiply n elements // with an associative operation using System; class GFG { // Function to find the // required factorial static int fact( int n) { if (n == 0 || n == 1) return 1 ; int ans = 1; for ( int i = 1 ; i <= n; i++) ans = ans * i ; return ans ; } // Function to find nCr static int nCr( int n, int r) { int Nr = n , Dr = 1 , ans = 1; for ( int i = 1 ; i <= r ; i++ ) { ans = ( ans * Nr ) / ( Dr ) ; Nr-- ; Dr++ ; } return ans ; } // function to find // the number of ways static int solve ( int n ) { int N = 2 * n - 2 ; int R = n - 1 ; return nCr (N, R) * fact(n - 1) ; } // Driver Code public static void Main () { int n = 6 ; Console.WriteLine( solve (n)) ; } } // This code is contributed by anuj_67. |
PHP
<?php // PHP code to find number // of ways to multiply n // elements with an // associative operation // Function to find the // required factorial function fact( $n ) { if ( $n == 0 || $n == 1) return 1; $ans = 1; for ( $i = 1 ; $i <= $n ; $i ++) $ans = $ans * $i ; return $ans ; } // Function to find nCr function nCr( $n , $r ) { $Nr = $n ; $Dr = 1 ; $ans = 1; for ( $i = 1 ; $i <= $r ; $i ++ ) { $ans = ( $ans * $Nr ) / ( $Dr ); $Nr --; $Dr ++; } return $ans ; } // function to find // the number of ways function solve ( $n ) { $N = 2* $n - 2 ; $R = $n - 1 ; return nCr ( $N , $R ) * fact( $n - 1) ; } // Driver code $n = 6 ; echo solve ( $n ) ; // This code is contributed // by ajit ?> |
Javascript
<script> // Javascript code to find number of // ways to multiply n elements // with an associative operation // Function to find the // required factorial function fact(n) { if (n == 0 || n == 1) return 1; let ans = 1; for (let i = 1 ; i <= n; i++) ans = ans * i; return ans; } // Function to find nCr function nCr(n, r) { let Nr = n , Dr = 1 , ans = 1; for (let i = 1 ; i <= r ; i++) { ans = parseInt((ans * Nr) / (Dr), 10); Nr--; Dr++; } return ans; } // Function to find // the number of ways function solve(n) { let N = 2 * n - 2; let R = n - 1; return nCr (N, R) * fact(n - 1); } // Driver code let n = 6; document.write(solve(n)); // This code is contributed by decode2207 </script> |
Output :
30240
Time Complexity: O(n).
Auxiliary Space: O(1).
Contact Us