All the possible tuples from a starting set satisfying specific conditions This should not be a super hard problem, but I have been headbutting against it for two days.
Let's suppose a set $A = [a_1,\dots,a_n]$, an element $a_j \in A$, and a subset of fixed element $A_l \subset A$. I am interested in counting all the possible tuples of $A$ with each element appearing at most once (written as $C(A)$) such that $a_j$ appears before any element in $A_l$.
For example, if I take $A = [x,y,z]$, $A_l = [y]$ and $a_j = x$, then the subsets satisfying the condition are:
$[x]$, $[x,y]$, $[x,z]$, $[z,x]$, $[x,y,z]$, $[z,x,y]$, $[x,z,y]$ and $C(A) = 7$.
Bonus point if I can find the number of satisfactory cases as a function of the cardinality of the tuples (i.e.  $C(A_1) = 1, C(A_2) = 3, C(A_3) = 3$ and $\sum_{i = 1}^{|A|} C(A_i) = C(A)$).
Thanks for the help!
 A: For a tuple with $i$ elements, choose (in addition to $a_j$) $k$ elements from $A_l$ and $i-k-1$ elements not from $A_l$. Let $m=|A_l|$. There are $i!$ ways to order these $i$ elements, and $a_j$ appears before the $k$ elements from $A_l$ in a fraction $\frac1{k+1}$ of these. Thus
\begin{eqnarray}
C(A_i)
&=&
i!\sum_{k=0}^m\frac1{k+1}\binom mk\binom{n-m-1}{i-k-1}
\\
&=&
\frac{i!}{m+1}\sum_{k=0}^m\binom{m+1}{k+1}\binom{n-m-1}{i-k-1}\;.
\end{eqnarray}
Summing this over $i$ yields
$$
C(A)=\frac1{m+1}\sum_{i=0}^ni!\sum_{k=0}^m\binom{m+1}{k+1}\binom{n-m-1}{i-k-1}\;.
$$
Unfortunately Wolfram|Alpha returns a hypergeometric function for both sums, so I doubt this can be simplified.
A: Without loss of generality let $A=(1,\dots,n)$, further let $a_j\in\{1,\dots,n\}$ and $A_l\subseteq\{1,\dots,n\}\setminus\{a_j\}$. For $k\in\{1,\dots,n\}$ a tuple $x=(x_i)_i\in\{1,\dots,n\}^k$ is fine if all $x_i$ are distinct, further if $x_{i^*}=a_j$ for some $i^*$, and that $i>i^*$ for all $i$ with $x_i\in A_l$. Let $\mathcal F$ be the set of all fine tuples. We want to know $|\mathcal F|$, the number of fine tuples.
For this purpose let $r=|A_l|$ and $s=n-r$. First, we decide how many elements appear before $a_j$, which can range from $0$ to $s$ (since no element from $A_l$ can appear before). Then we choose the, say $t$, elements and in which order they appear, respecting that each element can only appear once. Then, we decide how many elements come after $a_j$, which ranges from $0$ to $n-1-t$, since we have to subtract $a_j$ and the $t$ elements we already chose. Then we choose the elements, respecting uniqueness. The result is
\begin{align*}
|\mathcal F|&=\sum_{t=0}^{n-|A_l|}\prod_{h=1}^t(n-|A_l|+1-h)\sum_{u=0}^{n-1-t}\prod_{h=1}^u(n-t-1+1-h)\\
&=\sum_{t=0}^{n-|A_l|}\sum_{u=0}^{n-1-t}(n-|A_l|)_t(n-t-1)_u,
\end{align*}
using the notation for the falling factorial.
Bonus: If you want to consider tuples of a specifc length $\ell=1,\dots,n$, we can also do that. Then you only have to adjust the sums to respect this constraint. So, the number $t$ of elements before $a_j$ reaches from $1$ to $\min(\ell-1,n-|A_l|)$, since we cannot take more than $\ell-1$ to get to $\ell$ in total, and since we can place at most $n-|A_l|$ before. For the second sum, we have to take $\ell-1-t$ elements, and we can by the definition of $b$. This gives
$$\sum_{t=0}^{\min(\ell-1,n-|A_l|)}(n-|A_l|)_t(n-t-1)_{\ell-t-1}.$$
A: Let $q=|A_l|$ and $r=|A\setminus (A_l \cup \{x\})|$, i.e. $r=n-q-1$. We build the allowable tuples as follows: first, we choose and arrange elements from $A_l$, then place $x$ in front of those elements, and then we choose elements from $A\setminus (A_l \cup \{x\})$ and intersperse them.
Let $k$ be the number of elements we choose from $A_l$, where $k$ can range from $0$ to $q$. Those $k$ elements can be chosen and arranged in $_{q}P_{k}$ ways. Adding element $x$ to the arrangement will not change the number as $x$ must be placed in front of all elements from $A_l$, so we still have $_{q}P_{k}$ arrangements for these $k+1$ elements.
Next, we choose $j$ elements from $A\setminus (A_l \cup \{x\})$, where $j$ can range from $0$ to $r$. These $j$ elements can be arranged in $_{r}P_{j}$ ways.
Finally, we intersperse the two arrangements; we can do this in $\binom {j+k+1}{j}$ ways.
So, for fixed $j$ and $k$, we would get
$$_{r}P_{j} \; _{q}P_{k} \; \binom {j+k+1}{k+1}$$
different tuples. To get the total number of tuples we sum over all possible values of $j$ and $k$, so
$$C(A) = \sum_{j=0}^{r} \sum_{k=0}^{q} \; _{r}P_{j} \; _{q}P_{k} \binom {j+k+1}{k+1}$$
For the bonus, to restrict yourself to a fixed cardinality $i$, we want to limit the summation to $j+k+1=i$; then $k$ could now range from $\max(0,i-(n-q))$ to $\min (i-1,q)$, and $j$ would just be $i-k-1$, giving us
$$C(A_i) = \sum_{k=\max (0,i+q-n)}^{\min(i-1,q)} \; _{q}P_{k} \; _{r}P_{i-k-1} \; \binom {i}{k+1}$$
