I found a lot of things distribing a number of paths across a grid, but not quite what my question is. I'm looking for the total number of distinguishable paths through X number of points. For example, let's say i have 5 points A - E as seen below
A B C D E
For example a few of my paths could be as follows:
ABCDE (Don't skip any)
ACDE (Skip B)
ABDE (Skip B)
ABD (Skip C and E)
... etc
I'd like to find the total paths for two cases. 1) I can only go in increasing order (ABCDE would be valid, but not ACBDE). 2) where I can go in any order. In either case a point cannot be repeated (can't go ABACDE for example)
For case 1, i can see this as occupation problem where i have r = 5 balls and n = 5 cells, and then need to find all the distributions with at least 1 empty cell, but no more than 3 empty cells. if i know that, then i can just add 1 to it for the case there no cells are empty. The problem with that is, i might have a case where 2 balls are in cell A and 3 in C, and another with 3 balls in A and 2 in C. For my case, these are the exact same path. I'm just not sure how to do the math.... is it simple 2^5 (2^x for the general case)?
For Case 2, I pretty lost on how to think about that one. If anyone could at least point me in the right direction, I would appreciate it. Thanks!!
I would have said for the first $2^5=32$ as you suggest, and in general $2^n$.
For the second, I would say $1 + 5\times(1 + 4\times( 1+ 3\times(1+ 2\times(1+1)))) = 326$. The general value would be $\displaystyle \sum_{k=0}^n \frac{n!}{k!}$.
But from your comments it seems that your paths apparently need to start a a particular point and finish at a different point, so the $1$ path with no points and the $5$ paths with just one point would need to be subtracted, leaving $26$ paths for the first question and $320$ for the second. In general you need to subtract $n+1$.