OFFSET
1,2
COMMENTS
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.
For n <= 9 this is just A000041(n), the number of partitions of n.
EXAMPLE
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.
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;
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;
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;
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;
12,345678910; 123,456,78910; 123,4567,8910; 123,45678910; 1234,5678910; 12345,678910; 12345678910
MAPLE
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:
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:
seq(A091955(n), n=1..16) ; # R. J. Mathar, Jul 20 2007
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Mar 12 2004
EXTENSIONS
More terms from R. J. Mathar, Jul 20 2007
More terms from Sean A. Irvine, Nov 22 2010
STATUS
approved