login
Number of regular sequences of length n.
(Formerly M1685)
8

%I M1685 #52 Sep 06 2023 01:12:23

%S 1,2,6,27,192,2280,47097,1735803,115867758,14137353466,3172486137982,

%T 1315460211433262,1011773137731861712,1448486351628212391462,

%U 3872217739919424676743213

%N Number of regular sequences of length n.

%C From _Nathaniel Johnston_, Jun 29 2023: (Start)

%C A sequence x_1, ..., x_n is regular if 1 = x_1 <= x_2 <= ... <= x_n and x_j <= Sum_{i=1..j-1} x_i for all j >= 2. It is immediate from this definition that x_2 = 1 and x_j <= 2^(j-2) for all j >= 2.

%C A sequence x_1, x_2, ..., x_n is regular if and only if (x_2, ..., x_n) is a complete partition of x_2+...+x_n (see A126796 for the definition of a complete partition). As a result, the number of regular sequences with sum equal to n is given by A126796(n-1).

%C (End)

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Marc Davio, <a href="/A003513/a003513.pdf">Unpublished notes, 1975</a>, from a letter to N. J. A. Sloane sent in May 1975.

%H Peter C. Fishburn and Fred S. Roberts, <a href="http://dx.doi.org/10.1007/978-1-4684-6381-1_5">Uniqueness in finite measurement</a>, Applications of combinatorics and graph theory to the biological and social sciences, 103--137, IMA Vol. Math. Appl., 17, Springer, New York, 1989. MR1009374 (90e:92099)

%H Peter C. Fishburn and Fred S. Roberts, <a href="/A005269/a005269.pdf">Uniqueness in finite measurement</a>, in Applications of combinatorics and graph theory to the biological and social sciences, 103--137, IMA Vol. Math. Appl., 17, Springer, New York, 1989. MR1009374 (90e:92099). [Annotated scan of five pages only]

%H Peter C. Fishburn et al., <a href="http://dx.doi.org/10.1016/0166-218X(90)90066-L">Van Lier Sequences</a>, Discrete Appl. Math. 27 (1990), pp. 209-220.

%H Nathaniel Johnston and Sarah Plosker, <a href="https://arxiv.org/abs/2308.15611">Laplacian {-1,0,1}- and {-1,1}-diagonalizable graphs</a>, arXiv:2308.15611 [math.CO], 2023.

%e From _Nathaniel Johnston_, Jun 29 2023: (Start)

%e When n = 4, there are 6 regular sequences:

%e 1,1,1,1

%e 1,1,1,2

%e 1,1,1,3

%e 1,1,2,2

%e 1,1,2,3

%e 1,1,2,4

%e (End)

%p A003513 := proc() local a,b,n ; a := {[1,1]} ; n := 3 ; while true do b := {} ; for s in a do subsa := combinat[choose](s) ; for i in subsa do newa := add(k,k=i) ; if newa >= op(-1,s) then b := b union {[op(s),newa]} ; fi ; od; od; print(n,nops(b) ) ; a := b ; n := n+1 ; od; end: A003513() ; # _R. J. Mathar_, Oct 22 2007

%Y Sequences in the Fishburn-Roberts (1989) article: A005269, A005268, A234595, A005272, A003513, A008926.

%Y Cf. A126796.

%K nonn,nice,more

%O 2,2

%A _N. J. A. Sloane_

%E a(9) from _R. J. Mathar_, Oct 22 2007

%E a(10) from _Sean A. Irvine_, Jun 15 2015

%E a(11)-a(16) from _Bert Dobbelaere_, Dec 28 2020