2 added 301 characters in body edited Feb 24 '16 at 22:18 Yuval Filmus 208k1515 gold badges202202 silver badges369369 bronze badges The Whitney rank polynomial, an analog of the well-known Tutte polynomial of graphs, enumerates the number of subsets of a matroid of given size and rank. It can be computed using a deletion-contraction recurrence essentially the same as the recurrence for the Tutte polynomial. You can find the details in Welsh's Matroid Theory, §15.4. From the rank polynomial it is easy to read off the expected rank of $$S_i$$. Granted, this algorithm takes exponential time, which is not necessarily better than direct counting. Computing the coefficients of the rank polynomial is #P-hard, which suggests that computing the expectation might be hard as well. You can estimate it to your heart's content by sampling, though. The Whitney rank polynomial, an analog of the well-known Tutte polynomial of graphs, enumerates the number of subsets of a matroid of given size and rank. It can be computed using a deletion-contraction recurrence essentially the same as the recurrence for the Tutte polynomial. You can find the details in Welsh's Matroid Theory, §15.4. From the rank polynomial it is easy to read off the expected rank of $$S_i$$. The Whitney rank polynomial, an analog of the well-known Tutte polynomial of graphs, enumerates the number of subsets of a matroid of given size and rank. It can be computed using a deletion-contraction recurrence essentially the same as the recurrence for the Tutte polynomial. You can find the details in Welsh's Matroid Theory, §15.4. From the rank polynomial it is easy to read off the expected rank of $$S_i$$. Granted, this algorithm takes exponential time, which is not necessarily better than direct counting. Computing the coefficients of the rank polynomial is #P-hard, which suggests that computing the expectation might be hard as well. You can estimate it to your heart's content by sampling, though. 1 answered Feb 24 '16 at 22:08 Yuval Filmus 208k1515 gold badges202202 silver badges369369 bronze badges The Whitney rank polynomial, an analog of the well-known Tutte polynomial of graphs, enumerates the number of subsets of a matroid of given size and rank. It can be computed using a deletion-contraction recurrence essentially the same as the recurrence for the Tutte polynomial. You can find the details in Welsh's Matroid Theory, §15.4. From the rank polynomial it is easy to read off the expected rank of $$S_i$$.