Discrete Math Question

[quest726]

Let S be an n-element set and let k be a fixed positive number. How many sequences (T[sub:ix9ou5od]1[/sub:ix9ou5od], T[sub:ix9ou5od]2[/sub:ix9ou5od], ...T[sub:ix9ou5od]k[/sub:ix9ou5od]) are there of subsets T[sub:ix9ou5od]i[/sub:ix9ou5od] of S such that T[sub:ix9ou5od]i[/sub:ix9ou5od] is always a subset of T[sub:ix9ou5od]i+1[/sub:ix9ou5od]?

Let me know if you have any guesses on starting points.

 

[daon]

This potentially a very, very big number, even for small n,k. Just to get an idea, all constant sequences are contained, so 2^n.

Suppose T_(2)=S. Then there are 2^n undetermined subsets which T1 can be.

But T_(2) could be any subset of S. Suppose T_2 contains m elements. Then there are 2^m choices for T1.

Continue in this fashion. The result will contain a few summations.