001    /*
002     * $Id: Combinatoric.java 3295 2010-08-26 17:01:10Z kredel $
003     */
004    
005    package edu.jas.arith;
006    
007    
008    /**
009     * Combinatoric algorithms. Similar to ALDES/SAC2 SACCOMB module.
010     * @author Heinz Kredel
011     */
012    public class Combinatoric {
013    
014    
015        /**
016         * Integer binomial coefficient induction. n and k are beta-integers with 0
017         * less than or equal to k less than or equal to n. A is the binomial
018         * coefficient n over k. B is the binomial coefficient n over k+1.
019         * @param A previous induction result.
020         * @param n long.
021         * @param k long.
022         * @return the binomial coefficient n over k+1.
023         */
024        public static BigInteger binCoeffInduction(BigInteger A, long n, long k) {
025            BigInteger kp, np;
026            np = new BigInteger(n - k);
027            kp = new BigInteger(k + 1);
028            BigInteger B = A.multiply(np).divide(kp);
029            return B;
030        }
031    
032    
033        /**
034         * Integer binomial coefficient. n and k are beta-integers with 0 less than
035         * or equal to k less than or equal to n. A is the binomial coefficient n
036         * over k.
037         * @param n long.
038         * @param k long.
039         * @return the binomial coefficient n over k+1.
040         */
041        public static BigInteger binCoeff(int n, int k) {
042            BigInteger A = BigInteger.ONE;
043            int kp = (k < n - k ? k : n - k);
044            for (int j = 0; j < kp; j++) {
045                A = binCoeffInduction(A, n, j);
046            }
047            return A;
048        }
049    
050    
051        /**
052         * Integer binomial coefficient partial sum. n and k are integers, 0 le k le
053         * n. A is the sum on i, from 0 to k, of the binomial coefficient n over i.
054         * @param n long.
055         * @param k long.
056         * @return the binomial coefficient partial sum n over i.
057         */
058        public static BigInteger binCoeffSum(int n, int k) {
059            BigInteger B, S;
060            S = BigInteger.ONE;
061            B = BigInteger.ONE;
062            for (int j = 0; j < k; j++) {
063                B = binCoeffInduction(B, n, j);
064                S = S.sum(B);
065            }
066            return S;
067        }
068    
069    }