A091955 - OEIS

This site is supported by donations to The OEIS Foundation.

A091955

Number of increasing subsequences that can be made from the sequence of successive numbers.

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: 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`

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

Last modified May 22 13:53 EDT 2013. Contains 225549 sequences.