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 conjunction 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 $S_1$ and $S_2$ are distinct if we can not find a permutation of $\{1,..,N\}$ so that the image of $S_1$ under permutation is $S_2$.

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.

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

Let $s(T,N)$ be the number of distinct 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 '14 at 10:37
    
I think this is an interesting question. –  Marko Riedel Aug 14 at 2:18

2 Answers 2

This appears to be an interesting problem that can be attacked using Power Group Enumeration on sets as described in quite some detail at the following MSE link.

That link discusses the number of different subsets of a standard $52$ card deck under suit permutation. Here we have the group permuting the slots into which we distribute the cards is the symmetric group and the group permuting cards is the cardinality twenty-four induced action on the cards of all permutations of the four suits.

The lottery ticket problem proposed here follows exactly the same model, only now we are distributing tickets into the slots being permuted by the symmetric group and the group acting on the tickets is the induced action of the symmetric group $S_N.$ The number of terms in the cycle indices $Z(S_N)$ and $Z(S_T)$ is given by the partition function and we get an algorithm that is of asymptotically lower order than the naive $N!\times T!.$

The only non-trivial issue that is not already featured in the solution to the distributions of cards is how to compute the cycle index of the induced action of $S_N$ on the ${N\choose Q}$ tickets of $Q$ elements. This can be done quite effectively by computing a representative of the permutation shape from the cycle index of the symmetric group, letting it act on the tickets, and factoring the result into cycles for a contribution to the desired cycle index.

Setting $Q=5$ as in the question we obtain for $N=7$ the sequence $$1, 2, 5, 10, 21, 41, 65, 97, 131, 148, 148, 131,\ldots$$ for $N=8$ the sequence $$1, 3, 11, 52, 252, 1413, 7812, 41868, 207277, 936130, 3826031,\\ 14162479,\ldots$$ for $N=9$ the sequence $$1, 4, 20, 155, 1596, 20528, 282246, 3791710, 47414089, 542507784,\\ 5659823776,53953771138,\ldots$$ and finally for $N=10$ the sequence $$1, 5, 28, 324, 5750, 142148, 3937487, 108469019, 2804300907,\\ 66692193996,1452745413957, 29041307854703,\ldots.$$

To illustrate the good complexity of this algorithm here is the sequence for $N=13:$ $$1, 5, 42, 813, 34871, 2777978, 304948971, 37734074019,\\ 4719535940546, 566299855228261, 63733180893169422,\\ 6674324951638852138,\ldots$$

Finally we obtain for $N$ variable with $Q=5$ and $T=3$ the sequence $$0, 0, 0, 0, 0, 1, 5, 11, 20, 28, 35, 39, 42, 43,\\ 44, 44, 44, 44,\ldots$$

The Maple code to compute these was as follows:

with(combinat);
with(numtheory);

pet_flatten_term :=
proc(varp)
local terml, d, cf, v;

    terml := [];

    cf := varp;
    for v in indets(varp) do
        d := degree(varp, v);
        terml := [op(terml), seq(v, k=1..d)];
        cf := cf/v^d;
    od;

    [cf, terml];
end;

pet_autom2cycles :=
proc(src, aut)
local numa, numsubs;
local marks, pos, cycs, cpos, clen;

    numsubs := [seq(src[k]=k, k=1..nops(src))];
    numa := subs(numsubs, aut);

    marks := Array([seq(true, pos=1..nops(aut))]);

    cycs := []; pos := 1;

    while pos <= nops(aut) do
        if marks[pos] then
            clen := 0; cpos := pos;

            while marks[cpos] do
                marks[cpos] := false;
                cpos := numa[cpos];
                clen := clen+1;
            od;

            cycs := [op(cycs), clen];
        fi;

        pos := pos+1;
    od;

    return mul(a[cycs[k]], k=1..nops(cycs));
end;

pet_cycleind_symm :=
proc(n)
local p, s;
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_flat2rep :=
proc(f)
local p, q, res, t, len;

    q := 1; res := [];

    for t in f do
        len := op(1, t);
        res := [op(res), seq(p, p=q+1..q+len-1), q];
        q := q+len;
    od;

    res;
end;

pet_cycleind_tickets :=
proc(N, Q)
    option remember;
    local cind, tickets, q, term, rep, subsl, ptickets,
    idx, flat;

    if N=1 then
       idx := [a[1]]
    else
       idx := pet_cycleind_symm(N);
    fi;

    cind := 0;

    tickets := convert(choose({seq(q, q=1..N)}, Q), `list`);

    for term in idx do
        flat := pet_flatten_term(term);
        rep := pet_flat2rep(flat[2]);

        subsl := [seq(q=rep[q], q=1..N)];

        ptickets := subs(subsl, tickets);

        cind := cind +
        flat[1]*pet_autom2cycles(tickets, ptickets);
    od;

    cind;
end;


X :=
proc(N, Q, T)
    option remember;
    local idx_slots, res, a, b,
    flat_a, flat_b, cycs_a, cycs_b, q,
    tbl_a, tbl_b, f1, f2, f3;

    if T=1 then
       idx_slots := [a[1]]
    else
       idx_slots := pet_cycleind_symm(T);
    fi;

    res := 0;

    for a in idx_slots do
        flat_a := pet_flatten_term(a);
        cycs_a := sort(flat_a[2]);

        tbl_a := table();
        for q in convert(cycs_a, 'multiset') do
            tbl_a[op(1, q[1])] := q[2];
        od;

        f1 := map(q -> op(1, q), cycs_a);
        f1 := mul(f1[q], q=1..nops(cycs_a));

        f2 := convert(map(q -> op(1, q), cycs_a), 'multiset');
        f2 := map(q -> q[2], f2);
        f2 := mul(f2[q]!, q=1..nops(f2));

        for b in pet_cycleind_tickets(N, Q) do
            flat_b := pet_flatten_term(b);
            cycs_b := sort(flat_b[2]);


            tbl_b := table();
            for q in convert(cycs_b, 'multiset') do
                tbl_b[op(1, q[1])] := q[2];
            od;

            f3 := 1;
            for q in [indices(tbl_a, 'nolist')] do
                if type(tbl_b[q], integer) then
                    f3 := f3*binomial(tbl_b[q], tbl_a[q]);
                else
                    f3 := 0;
                fi;
            od;

            res := res + f3*f2*f1*flat_a[1]*flat_b[1];
        od;
    od;

    res;
end;

Addendum Fri Aug 14 2015. The sequence for $Q=5$ and $N=20$ is $$1, 5, 44, 966, 53484, 7023375, 1756229468, 710218125299, \\ 411620592905173, 308212635851733551, 271743509344779773214,\ldots$$

Addendum Sat Aug 15 2015. The sequence for $Q=5$ and $N=22$ is $$1, 5, 44, 966, 53529, 7041834, 1773511264, 734330857318, \\ 452455270344141, 383969184978128899, 416614280701828877344, \\ 536531456518633409220043, 766723127226754935510254929,\ldots$$

Addendum Wed Aug 19 2015. The sequence for $Q=5$ and $N=24$ is $$1, 5, 44, 966, 53534, 7043732, 1775444689, 737776095236, \\ 460462767067281, 405308264117856150, 477303563740811267063, \\ 712445246443357547546003, 1271053814158420923816386794,\ldots$$

share|improve this answer

There are $\binom{N}{5}$ possible tickets, you are asking how many $T$-subsets of those there are, i.e., the number of systems is:

$$ \binom{\binom{N}{5}}{T} $$

(somehow I'm feeling I'm just being stupid here... can't be that easy?)

share|improve this answer
    
You appear to have missed the part where the OP says "Two systems are distinct if .." –  Marko Riedel Aug 14 at 22:00
    
@MarkoRiedel, "are unique up to permutation" is just sets in my book... –  vonbrand Aug 14 at 22:06
    
These lottery tickets are indeed sets. The permutation however acts on the $N$ values from which they are drawn. E.g. the ticket $\{1,2,3,4,5\}$ drawn from $N=10$ could be transformed into the ticket $\{6,7,8,9,10\}$ by a permutation of the $N$ values that exchanges the upper and lower five values (permutation not unique). –  Marko Riedel Aug 14 at 22:11
    
The permutation acts simultaneously on all tickets in a system of size $T,$ which is indeed a set of tickets. –  Marko Riedel Aug 14 at 22:26

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.