login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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

Table of n, a(n) for n=1..51.

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

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 | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 30 06:59 EDT 2020. Contains 333119 sequences. (Running on oeis4.)