1,2

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, thne 1, 2, 3, 4, 5, 6, 7, 8, 9, 101, 112 is increasing subsequent 1, 2, 3, 4, 5, 6, 7, 8, 91, (0)1112 aretwo examples of increasing subsequences.

For n <= 9 this is just A000041(n), the number of partitions of n.

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

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 (mathar(AT)strw.leidenuniv.nl), Jul 20 2007

Cf. A091956.

Sequence in context: A000041 A084251 A024794 this_sequence A091584 A091582 A101977

Adjacent sequences: A091952 A091953 A091954 this_sequence A091956 A091957 A091958

more,nonn,base

Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Mar 12 2004

More terms from R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Jul 20 2007