login
A091955
Number of increasing subsequences that can be made from the sequence of successive numbers.
2
1, 2, 3, 5, 7, 11, 15, 22, 30, 51, 75, 119, 196, 309, 472, 698, 1018, 1498, 2130, 3005, 4262, 5909, 7884, 10579, 14543, 19884, 27182, 36278, 48440, 63730, 83712, 109333, 141728, 180873, 231057, 294557, 377184, 491509, 627181, 803209, 1024777, 1292487, 1623797, 2034228, 2526480, 3120461, 3879381, 4796155, 5896718, 7368893, 9087883
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
Cf. A091956.
Sequence in context: A326292 A195308 A218025 * A091584 A091582 A241727
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