This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 (list; graph; refs; listen; history; text; internal format)
 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. LINKS 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: A024794 A195308 A218025 * A091584 A091582 A101977 Adjacent sequences:  A091952 A091953 A091954 * A091956 A091957 A091958 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .