Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is an enumeration problem in conjonction with some lottery problems.

Given an integer $N \ge 5$. Let a ticket be a set of 5 distinct integers between $1$ and $N$. Given an integer $T$ between $1$ and ${{N}\choose{5}}$. Let a system of size $T$ be a set of $T$ distinct tickets.

Given $N \ge 5$, I want to count how many distinct systems of size $T$ exist.

Two systems $S1$ and $S2$ are distinct if we can not find a permutation of $\{1,..,N\}$ so that the image of $S1$ under permutation is $S2$.

I tried some computations for small values of $N$ and $T$.

$N=7$

$T= 1, 2, 3, 4, 5, 6, 7, 8, 9$

number of distinct systems = $1, 2, 5, 10, 21, 41, 65, 97, 131, 148$

(It seems that this sequence of numbers is known as A008406 at oeis.org)

$N=8$

$T= 1, 2, 3, 4, 5, 6, 7, 8, 9$

number of distinct systems = $1, 3, 11, 52, 252, 1413, 7812, 41868, 207277$

$N=9$

$T= 1, 2, 3, 4, 5, 6, 7 $

number of distinct systems = $1, 4, 20, 155, 1596, 20528, 282246$

Is there a method to "guess" those numbers and find bigger values ?

I wonder if Polya enumeration can be used there. I currently do not know how.

Updated : Taking a look at http://ac.cs.princeton.edu/home/

Let s(T,N) be the number of distincts systems of size T ($1 \le T \le{{N}\choose{5}}$), given N.

$\forall N \ge 5, s(1,N) = 1$

$\forall N \ge 10, s(2,N) = 5$

$\forall N \ge 15, s(3,N) = 44$

share|improve this question
    
A question without answer on the Web is either too stupid or too complicated. I still have not found how much stupid is this one , but trying :-) –  tqbfjotld Feb 15 at 10:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.