finding general formula

[mpsn]

Hi, for my assignment, I need to figure out how many possible paths through a bubblesort,

 

Let n be the size of the array

 

so my results are:

if n = 0, 2^0 paths

if n = 1, 2^1 paths

if n = 2, 2^3 paths

if n = 3, 2^6 paths

if n = 4, 2^10 paths

 

so I need to figure out a summation/product notation formula for the exponent, for a given size n so I mean 2^(some formula involving summation or multiplication notation)

 

Any help appreciated

[silkfire]

The formula for adding series starting from 1 to n is:  n(n+1)/2.

 

So for 4 it will be 4 * (4 + 1) / 2 = 20 / 2 = 10.

 

Did that answer your question?

[mpsn]

Thanks, appreciate it

[mpsn]

Wait, actually I need to have a summation and/or product notation used, b/c yours is simply:

 

2^[n(n+1)/2], but I need 2^(summation from start to n for some formula) for instance.

[Alex]

  Quote

Wait, actually I need to have a summation and/or product notation used, b/c yours is simply:

 

2^[n(n+1)/2], but I need 2^(summation from start to n for some formula) for instance.

 

The n(n+1)/2 is the value for the sum of numbers from 1 to n, so you're just looking for: