cp's OEIS Frontend

A268485 Number of sequences with n copies each of 1,2,...,n and longest increasing subsequence of length n.

%I A268485 #23 Jun 18 2018 05:26:48
%S A268485 1,1,5,1306,46922017,449363984934526,1878320344216429026862153,
%T A268485 5078529731893937404909347067888886466,
%U A268485 12324197596430667064913735085330208112438377122058241,35544813569338447788721757701614208334438136486811525386710064098254294
%N A268485 Number of sequences with n copies each of 1,2,...,n and longest increasing subsequence of length n.
%H A268485 Alois P. Heinz, <a href="/A268485/b268485.txt">Table of n, a(n) for n = 0..27</a>
%H A268485 J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. <a href="http://www.ams.org/mathscinet-getitem?mr=681905">MR 681905</a>
%e A268485 a(2) = 5: 1122, 1212, 1221, 2112, 2121.
%e A268485 a(3) = 1306: 111222333, 111223233, 111223323, ..., 332212113, 332212131, 332212311.
%p A268485 g:= proc(l) option remember; (n-> f(l[1..nops(l)-1])*
%p A268485       binomial(n-1, l[-1]-1)+ add(f(sort(subsop(j=l[j]
%p A268485       -1, l))), j=1..nops(l)-1))(add(i, i=l))
%p A268485     end:
%p A268485 f:= l-> (n-> `if`(n<2 or l[-1]=1, 1, `if`(l[1]=0, 0, `if`(
%p A268485          n=2, binomial(l[1]+l[2], l[1])-1, g(l)))))(nops(l)):
%p A268485 a:= n-> f([n$n]):
%p A268485 seq(a(n), n=0..8);
%p A268485 # second Maple program:
%p A268485 b:= proc(k, p, j, l, t) option remember;
%p A268485       `if`(k=0, (-1)^t/l!, `if`(p<0, 0, add(b(k-i, p-1,
%p A268485        j+1, l+i*j, irem(t+i*j, 2))/(i!*p!^i), i=0..k)))
%p A268485     end:
%p A268485 a:= n-> n!*(n^2)!*b(n, n-1, 1, 0, irem(n, 2)):
%p A268485 seq(a(n), n=0..10);  # _Alois P. Heinz_, Mar 03 2016
%t A268485 b[k_, p_, j_, l_, t_] := b[k, p, j, l, t] = If[k==0, (-1)^t/l!, If[p<0, 0, Sum[b[k-i, p-1, j+1, l+i*j, Mod[t + i*j, 2]]/(i!*p!^i), {i, 0, k}]]];
%t A268485 a[n_] := n!*(n^2)!*b[n, n - 1, 1, 0, Mod[n, 2]];
%t A268485 Table[a[n], {n, 0, 10}] (* _Jean-François Alcover_, Jun 18 2018, translated from 2nd Maple program *)
%Y A268485 Main diagonal of A047909.
%Y A268485 Cf. A268667, A268751.
%K A268485 nonn
%O A268485 0,3
%A A268485 _Alois P. Heinz_, Feb 05 2016