Here is a possible title matchings in hypergraphs This is just a restatement but it might help with finding references. For $T=2$ one has the usual graphs and there are good algorithms for finding maximum size matchings. For larger $T$ finding matchings is (in general) NP-complete even for $T=3$. It may be that there are special features of your problem that bring things into reach.

For $T=2$ make a simple undirected graph with vertices $1,\cdots,N$ and edges all pairs $(i,j)$ which are allowed ($i \in S_1 \text{ and } j \in S_2$ or vice versa). A matching is a set of vertex disjoint edges (also called an independent edge set). If $KT=N$ then you are asking for a perfect matching.

If $T>2$ one can consider a hypergraph whose hyper-edges are all legal $T$-tuples and look for a matching.

Of course it is more compact to list your sets $S_i$ than to list every possible $T$-tuple. Your example above is the complete graph $K_6$ missing only the edges $(1,5)$ and $(3,6).$ The full graph $K_6$ has $15$ perfect matchings, $3$ using each edge. Of these, $10$ work for your problem.

Here is a slightly more promising idea: Make a bipartite graph with $N+T$ vertices labelled $1,\cdots,N$ on one side and $S_1,\cdots,S_T$ on the other. Draw an edge for $j$ to $S_t$ when $j \in S_t$. Then a maximum size matching of this graph would have at best $T$ edges. So you could look for $k$ disjoint $T$-matchings. This has the added structure that each tuple is essentially ordered.

Here is a possible title matchings in hypergraphs This is just a restatement but it might help with finding references. For $T=2$ one has the usual graphs and there are good algorithms for finding maximum size matchings. For larger $T$ finding matchings is (in general) NP-complete even for $T=3$. It may be that there are special features of your problem that bring things into reach.

For $T=2$ make a simple undirected graph with vertices $1,\cdots,N$ and edges all pairs $(i,j)$ which are allowed ($i \in S_1 \text{ and } j \in S_2$ or vice versa). A matching is a set of vertex disjoint edges (also called an independent edge set). If $KT=N$ then you are asking for a perfect matching.

If $T>2$ one can consider a hypergraph whose hyper-edges are all legal $T$-tuples and look for a matching.

Of course it is more compact to list your sets $S_i$ than to list every possible $T$-tuple. Your example above is the complete graph $K_6$ missing only the edges $(1,5)$ and $(3,6).$ The full graph $K_6$ has $15$ perfect matchings, $3$ using each edge. Of these, $10$ work for your problem.

Here is a slightly more promising idea: Make a bipartite graph with $N+T$ vertices labelled $1,\cdots,N$ on one side and $S_1,\cdots,S_T$ on the other. Draw an edge for $j$ to $S_t$ when $j \in S_t$. Then a maximum size matching of this graph would have at best $T$ edges. So you could look for $k$ disjoint $T$-matchings. This has the added structure that each tuple is essentially ordered.

Later thoughts: You've changed the problem to clarify that the tuples are ordered.

An answer might depend on $k$ and $T$. For $T=2$ you could use the first idea of matchings with unordered pairs in a possibly non-bipartite graph. For each solution find out how many of the pairs have both members in $S_1 \cap S_2$. If the number is $j$ then this gives $2^j$ ordered solutions.

If $T$ is large Then you might look to choose $k$ elements from each set so as to get $kT$ elements. Each such choice would describe $(k!)^{T-1}$ solutions. So now your example has 12 solutions because for the two solutions (24)(13)(56) and (24)(16)(53) can each replace (24) with (42). This number is also $\mathbf{2}*3!$ since from $S_1$ you must choose $1,5$ and from $S_2$ $3,6$. This leaves $\mathbf{2}$ choices for $2,4$.

Here is a possible title matchings in hypergraphs This is just a restatement but it might help with finding references. For $T=2$ one has the usual graphs and there are good algorithms for finding maximum size matchings. For larger $T$ finding matchings is (in general) NP-complete even for $T=3$. It may be that there are special features of your problem that bring things into reach.

For $T=2$ make a simple undirected graph with vertices $1,\cdots,N$ and edges all pairs $(i,j)$ which are allowed ($i \in S_1 \text{ and } j \in S_2$ or vice versa). A matching is a set of vertex disjoint edges (also called an independent edge set). If $KT=N$ then you are asking for a perfect matching.

If $T>2$ one can consider a hypergraph whose hyper-edges are all legal $T$-tuples and look for a matching.

Of course it is more compact to list your sets $S_i$ than to list every possible $T$-tuple. Your example above is the complete graph $K_6$ missing only the edges $(1,5)$ and $(3,6).$ The full graph $K_6$ has $15$ perfect matchings, $3$ using each edge. Of these, $10$ work for your problem.

Here is a possible title matchings in hypergraphs This is just a restatement but it might help with finding references. For $T=2$ one has the usual graphs and there are good algorithms for finding maximum size matchings. For larger $T$ finding matchings is (in general) NP-complete even for $T=3$. It may be that there are special features of your problem that bring things into reach.

For $T=2$ make a simple undirected graph with vertices $1,\cdots,N$ and edges all pairs $(i,j)$ which are allowed ($i \in S_1 \text{ and } j \in S_2$ or vice versa). A matching is a set of vertex disjoint edges (also called an independent edge set). If $KT=N$ then you are asking for a perfect matching.

If $T>2$ one can consider a hypergraph whose hyper-edges are all legal $T$-tuples and look for a matching.

Of course it is more compact to list your sets $S_i$ than to list every possible $T$-tuple. Your example above is the complete graph $K_6$ missing only the edges $(1,5)$ and $(3,6).$ The full graph $K_6$ has $15$ perfect matchings, $3$ using each edge. Of these, $10$ work for your problem.

Here is a slightly more promising idea: Make a bipartite graph with $N+T$ vertices labelled $1,\cdots,N$ on one side and $S_1,\cdots,S_T$ on the other. Draw an edge for $j$ to $S_t$ when $j \in S_t$. Then a maximum size matching of this graph would have at best $T$ edges. So you could look for $k$ disjoint $T$-matchings. This has the added structure that each tuple is essentially ordered.