How to efficiently calculate a row in pascal’s triangle?

by 
>>> def pascal(n):
...   line = [1]
...   for k in range(n):
...     line.append(line[k] * (n-k) / (k+1))
...   return line
... 
>>> pascal(9)
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]

This uses the following identity:

C(n,k+1) = C(n,k) * (n-k) / (k+1)

So you can start with C(n,0) = 1 and then calculate the rest of the line using this identity, each time multiplying the previous element by (n-k) / (k+1).

More Related Contents:

  1. Algorithm to return all combinations of k elements from n
  2. Finding all possible combinations of numbers to reach a given sum
  3. Generate all binary strings of length n with k bits set
  4. Compute rank of a combination?
  5. Best way of calculating n choose k?
  6. The intersection of all combinations of n sets
  7. Algorithm to list all unique permutations of numbers contain duplicates
  8. Calculate the sum with minimum usage of numbers
  9. Sum a number with divisors to get another number
  10. Priority scoring algorithm [closed]
  11. What is the optimal algorithm for the game 2048?
  12. Reverse the ordering of words in a string
  13. Converting a Uniform Distribution to a Normal Distribution
  14. Can hash tables really be O(1)?
  15. What is Sliding Window Algorithm? Examples?
  16. Diff Algorithm? [closed]
  17. Choosing n numbers with fixed sum
  18. Fast way to calculate n! mod m where m is prime?
  19. Store the largest 5000 numbers from a stream of numbers
  20. Sum-subset with a fixed subset size
  21. Algorithm for “nice” grid line intervals on a graph
  22. How to calculate the entropy of a file?
  23. Travelling Salesman with multiple salesmen?
  24. Test if a number is fibonacci
  25. A Cache Efficient Matrix Transpose Program?
  26. Faster version of find for sorted vectors (MATLAB)
  27. Number of paths between two nodes in a DAG
  28. Word comparison algorithm
  29. What are the pitfalls in implementing binary search? [closed]
  30. Optimized low-accuracy approximation to `rootn(x, n)`

Leave a Comment