|
%I #14 Aug 08 2015 19:54:04
%S 1,2,3,5,7,11,15,22,30,51,75,119,196,309,472,698,1018,1498,2130,3005,
%T 4262,5909,7884,10579,14543,19884,27182,36278,48440,63730,83712,
%U 109333,141728,180873,231057,294557,377184,491509,627181,803209,1024777,1292487,1623797,2034228,2526480,3120461,3879381,4796155,5896718,7368893,9087883
%N Number of increasing subsequences that can be made from the sequence of successive numbers.
%C Write the numbers from 1 to n in base 10 and concatenate the digits. Then a(n) is the number of sequences of increasing decimal numbers that can be formed by inserting commas anywhere into this string. Leading zeros are permitted but ignored. For example, for n=12 we start with 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2, then 1, 2, 3, 4, 5, 6, 7, 8, 9, 101, 112 and 1, 2, 3, 4, 5, 6, 7, 8, 91, (0)1112 are two examples of increasing subsequences.
%C For n <= 9 this is just A000041(n), the number of partitions of n.
%e For n = 6 we take 123456 and find that the increasing subsequence are 1,2,3,4,5,6; 1,2,3,4,56; 1,2,3,456; 1,2,34,56; 1,2,3456; 1,23,456; 1,23456; 12,34,56; 12,3456; 123,456; 123456; so a(6) = 11.
%e For a(10) we have 51 increasing subsequences: 1,2,3,4,5,6,7,8,9,10; 1,2,3,4,5,6,7,8,910; 1,2,3,4,5,6,7,8910; 1,2,3,4,5,6,78,910; 1,2,3,4,5,6,78910; 1,2,3,4,5,67,8910; 1,2,3,4,5,678,910; 1,2,3,4,5,678910; 1,2,3,4,56,78,910; 1,2,3,4,56,78910; 1,2,3,4,567,8910;
%e 1,2,3,4,5678910; 1,2,3,45,67,8910; 1,2,3,45,678,910; 1,2,3,45,678910; 1,2,3,456,78910; 1,2,3,4567,8910; 1,2,3,45678910; 1,2,34,56,78,910; 1,2,34,56,78910; 1,2,34,567,8910; 1,2,34,5678910;
%e 1,2,345,678,910; 1,2,345,678910; 1,2,3456,78910; 1,2,345678910; 1,23,45,67,8910; 1,23,45,678,910; 1,23,45,678910; 1,23,456,78910; 1,23,4567,8910; 1,23,45678910; 1,234,567,8910;
%e 1,234,5678910; 1,2345,678910; 1,23456,78910; 1,2345678910; 12,34,56,78,910; 12,34,56,78910; 12,34,567,8910; 12,34,5678910; 12,345,678,910; 12,345,678910; 12,3456,78910;
%e 12,345678910; 123,456,78910; 123,4567,8910; 123,45678910; 1234,5678910; 12345,678910; 12345678910
%p A055642 := proc(n) if n = 0 then 1 ; else ilog10(n)+ 1; fi ; end: R := proc(n) local ncpy,resul ; ncpy := n ; resul := [] ; while ncpy > 0 do resul := [ncpy mod 10, op(resul)] ; ncpy := floor(ncpy/10) ; od ; RETURN(resul) ; end: Lcat := proc(L) local resul,i ; resul := op(1,L) ; for i from 2 to nops(L) do resul := resul*10^A055642(op(i,L))+op(i,L) ; od ; RETURN(resul) ; end:
%p A091955 := proc(n) local lbase,i,a,complac,c,t,sul,tstl,fir,las,isincr,s,p ; lbase := [] ; for i from 1 to n do lbase := [op(lbase),op(R(i))] ; od ; a := 0 ; complac := combinat[partition](nops(lbase)) ; for c from 1 to nops(complac) do p := combinat[permute](op(c,complac)) ; for t from 1 to nops(p) do sul := op(t,p) ; tstl := [] ; fir := 1 ; for s from 1 to nops(sul) do las := fir+op(s,sul) ; tstl :=[op(tstl),Lcat(lbase[fir..las-1])] ; fir := fir+op(s,sul) ; od ; isincr := true ; for s from 2 to nops(tstl) do if tstl[s] <= tstl[s-1] then isincr := false ; break ; fi ; od ; if isincr then a := a+1 ; fi ; od ; od ; print(a) ; a ; end:
%p seq(A091955(n),n=1..16) ; # _R. J. Mathar_, Jul 20 2007
%Y Cf. A091956.
%K nonn,base
%O 1,2
%A Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Mar 12 2004
%E More terms from _R. J. Mathar_, Jul 20 2007
%E More terms from _Sean A. Irvine_, Nov 22 2010
|
