A005270 -id:A005270 - cp's OEIS frontend

A125051 The sub-Fibonacci tree; a rooted tree in which every node with label k and parent node with label g has g child nodes that are assigned labels beginning with k+1 through k+g; the tree starts at generation n=0 with a root node labeled '1' and a child node labeled '2'.

1, 2, 3, 4, 5, 5, 6, 7, 6, 7, 8, 6, 7, 8, 9, 7, 8, 9, 10, 8, 9, 10, 11, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 9, 10, 11, 12, 13, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 9, 10, 11, 12, 13, 10, 11, 12, 13, 14, 8, 9, 10, 11, 12, 13, 9, 10, 11, 12, 13, 14, 10, 11, 12, 13, 14, 15, 11, 12, 13, 14, 15, 16, 9

Offset: 0

Paul D. Hanna, Nov 19 2006

The maximum label for nodes in generation n is Fibonacci(n+2) for n>=0. The total number of nodes in generation n equals A005270(n+2) for n>=0. The sum of the labels for nodes in generation n equals A125052(n).

			The initial nodes of the tree for generations 0..5 are:
gen.0: [1];
gen.1: [2];
gen.2: [3];
gen.3: [4,5];
gen.4: (4)->[5,6,7],(5)->[6,7,8];
gen.5: (5)->[6,7,8,9],(6)->[7,8,9,10],(7)->[8,9,10,11],
(6)->[7,8,9,10,11],(7)->[8,9,10,11,12],(8)->[9,10,11,12,13].
By definition, there are 2 child nodes for node [3] of gen.2 since the parent of node [3] has label 2;
likewise, there are 3 child nodes for nodes [4] and [5] of gen.3 since the parent of both nodes has label 3.
The number of nodes in generation n begins:
1, 1, 1, 2, 6, 27, 177, 1680, 23009, 455368, 13067353, ...
The sum of the labels for nodes in generation n begins:
1, 2, 3, 9, 39, 252, 2361, 32077, 631058, 18035534, ...

Alois P. Heinz, Table of n, a(n) for n = 0..24903 (generations 0..8)
Peter C. Fishburn and Fred S. Roberts, Elementary sequences, sub-Fibonacci sequences, Discrete Appl. Math. 44 (1993), no. 1-3, 261-281.

Cf. A005270, A125052.

g:= proc(n) option remember; `if`(n=0, [[1, 1]],
      map(x-> seq([x[2], x[2]+i], i=1..x[1]), g(n-1)))
    end:
T:= n-> map(x-> x[2], g(n)):
a:= proc() local i, l; i, l:= -1, []; proc(n) while
      nops(l)<=n do i:=i+1; l:=[l[], T(i)[]] od; l[n+1] end
    end():
seq(a(n), n=0..200);  # Alois P. Heinz, Feb 08 2013

A125052 Sum of labels for nodes in generation n of the sub-Fibonacci tree (A125051).

Original entry on oeis.org

1, 2, 3, 9, 39, 252, 2361, 32077, 631058, 18035534, 751936149, 45973362492, 4144777181393, 554100538432001, 110435083963283354, 32981178674724868365

Offset: 0

Paul D. Hanna, Nov 19 2006

nonn

The sub-Fibonacci tree is a rooted tree in which every node with label k and parent node with label g has g child nodes that are assigned labels beginning with k+1 through k+g; the tree starts at generation n=0 with a root node labeled '1' and a child node labeled '2'. The number of nodes in generation n of the sub-Fibonacci tree is A005270(n+2); the maximum label in generation n is Fibonacci(n+2).

			The initial nodes of the sub-Fibonacci tree for generations 0..5 are:
gen.0: [1];
gen.1: [2];
gen.2: [3];
gen.3: [4,5];
gen.4: (4)->[5,6,7],(5)->[6,7,8];
gen.5: (5)->[6,7,8,9],(6)->[7,8,9,10],(7)->[8,9,10,11],
(6)->[7,8,9,10,11],(7)->[8,9,10,11,12],(8)->[9,10,11,12,13].
The sum of the labels for nodes in generation n+1 >= 2 is equal to:
a(n+1) = sum (parent label)*(label) over all nodes in generation n + sum (parent label)*[label*(label+1)/2] over all nodes in gen. n-1.
For example:
a(2) = 3 = 1*2 + 1*( 1*2/2 );
a(3) = 9 = 2*3 + 1*( 2*3/2 );
a(4) = 39 = 3*(4+5) + 2*( 3*4/2 );
a(5) = 252 = 4*(5+6+7) + 5*(6+7+8) + 3*( 4*5/2 + 5*6/2 );
a(6) = 2361 = 5*(6+7+8+9) + 6*(7+8+9+10) + 7*(8+9+10+11) +
6*(7+8+9+10+11) + 7*(8+9+10+11+12) + 8*(9+10+11+12+13) +
4*( 5*6/2 + 6*7/2 + 7*8/2 ) + 5*( 6*7/2 + 7*8/2 + 8*9/2 ).

Peter C. Fishburn and Fred S. Roberts, Elementary sequences, sub-Fibonacci sequences, Discrete Appl. Math. 44 (1993), no. 1-3, 261-281.

Cf. A125051, A005270.

a(10)-a(15) from Alois P. Heinz, May 03 2015

A355129 a(n) is the number of integer sequences b(0..n) of length n+1, with 0 <= b(k) <= k! and monotonic b(k) <= b(k+1).

Original entry on oeis.org

2, 3, 7, 40, 856, 91821, 60080136, 279276911843, 10503211888973754, 3585680755683196123365, 12323227994417456429490342865, 468378989392773003347310901356953089, 214565221409985003242070442557341938941878313, 1282499669290042152350268651085002913530161723080398635

Offset: 0

Thomas Scheuerle, Aug 04 2022

nonn

List of the possible cases regarding the patterns of the numbers in the sequence b:
Length:  1    2    3    4    5    6
Pos 0:   1    1    1    1    1    1
Pos 1:   1    2    3    4    5    6
Pos 2:   0    0    3    7   12   18
Pos 3:   0    0    0    7   19   37
Pos 4:   0    0    0    7   26   63
Pos 5:   0    0    0    7   33   96
Pos 6:   0    0    0    7   40  136
Pos 7:   0    0    0    0   40  176
Pos 8:   0    0    0    0   40  216
   ...  ...  ...  ...  ... ...  ...
    Sum: 2    3    7   40  856 91821
Each row counts the number of possible distributions of numbers, row "Pos 0" is the number of possible distributions with only the number zero. The row "Pos 1" counts the distributions of zeros and ones. The row "Pos 2" the possible distributions of {0,1,2} and so forth.
From top to down: If a number in the column length = k has reached the value of the sum of the column length = k-1, this number will be k!-(k-1)!+1 times repeated. Before this limit is reached each number is the sum of the neighbor one step above and the neighbor one step to the left.

			For a(0) we get two possible sequences:
  {0}, {1}.
For a(1) we get three possible sequences:
  {0, 0}, {0, 1}, {1, 1}.
For a(2) = 7 we get:
  {0, 0, 0}, {0, 0, 1}, {0, 0, 2}, {0, 1, 1},
  {0, 1, 2}, {1, 1, 1}, {1, 1, 2}.

Cf. A000108 (if we change the definition into 0 <= b(k) <= k).

Cf. A005269, A005270, A008934, A016121, A128094, A242105.

a(n) = binomial((n-1)! + n-1, n-1) + binomial((n-1)! + n-2, n-1) + sum(r = 1, n-2, sum(k = 0, r-1 ,binomial((n-1)! - r! - k+n - 2, n-1)*binomial(r-1,k)*a(r)*(-1)^(k+1)))

a(n) = binomial((n-1)! + n-1, n-1) + binomial((n-1)! + n-2, n-1) + Sum_{r = 1..n-2} Sum_{k = 0..r-1} binomial((n-1)! - r! - k+n - 2, n-1)*binomial(r-1,k)*a(r)*(-1)^(k+1).

cp's OEIS Frontend

A125051 The sub-Fibonacci tree; a rooted tree in which every node with label k and parent node with label g has g child nodes that are assigned labels beginning with k+1 through k+g; the tree starts at generation n=0 with a root node labeled '1' and a child node labeled '2'.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A125052 Sum of labels for nodes in generation n of the sub-Fibonacci tree (A125051).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A355129 a(n) is the number of integer sequences b(0..n) of length n+1, with 0 <= b(k) <= k! and monotonic b(k) <= b(k+1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula