# Counting number of distinct systems

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$

• 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 :-) – Philippe Morin Feb 15 '14 at 10:37
• I think this is an interesting question. – Marko Riedel Aug 14 '15 at 2:18

## 2 Answers

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]
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);

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

ptickets := subs(subsl, tickets);

cind := cind +
flat*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]
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);

tbl_a := table();
for q in convert(cycs_a, 'multiset') do
tbl_a[op(1, q)] := q;
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, 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);

tbl_b := table();
for q in convert(cycs_b, 'multiset') do
tbl_b[op(1, q)] := q;
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*flat_b;
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$$

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?)

• You appear to have missed the part where the OP says "Two systems are distinct if .." – Marko Riedel Aug 14 '15 at 22:00
• @MarkoRiedel, "are unique up to permutation" is just sets in my book... – vonbrand Aug 14 '15 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 '15 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 '15 at 22:26