login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A244523 Irregular triangle read by rows: T(n,k) is the number of identity trees with n nodes and maximal branching factor k. 10

%I #14 Feb 11 2015 06:05:36

%S 1,0,1,0,1,0,1,1,0,1,2,0,1,5,0,1,10,1,0,1,21,3,0,1,42,9,0,1,87,25,0,1,

%T 178,66,2,0,1,371,170,6,0,1,773,431,21,0,1,1630,1076,63,0,1,3447,2665,

%U 185,1,0,1,7346,6560,512,7,0,1,15712,16067,1403,26,0,1,33790,39219,3750,91,0,1,72922,95476,9928,291

%N Irregular triangle read by rows: T(n,k) is the number of identity trees with n nodes and maximal branching factor k.

%C Row sums give A004111.

%H Joerg Arndt and Alois P. Heinz, <a href="/A244523/b244523.txt">Rows n = 1..285, flattened</a>

%e Triangle starts:

%e 01: 1,

%e 02: 0, 1,

%e 03: 0, 1,

%e 04: 0, 1, 1,

%e 05: 0, 1, 2,

%e 06: 0, 1, 5,

%e 07: 0, 1, 10, 1,

%e 08: 0, 1, 21, 3,

%e 09: 0, 1, 42, 9,

%e 10: 0, 1, 87, 25,

%e 11: 0, 1, 178, 66, 2,

%e 12: 0, 1, 371, 170, 6,

%e 13: 0, 1, 773, 431, 21,

%e 14: 0, 1, 1630, 1076, 63,

%e 15: 0, 1, 3447, 2665, 185, 1,

%e 16: 0, 1, 7346, 6560, 512, 7,

%e 17: 0, 1, 15712, 16067, 1403, 26,

%e 18: 0, 1, 33790, 39219, 3750, 91,

%e 19: 0, 1, 72922, 95476, 9928, 291,

%e 20: 0, 1, 158020, 231970, 25969, 885, 3,

%e 21: 0, 1, 343494, 562736, 67462, 2588, 15,

%e 22: 0, 1, 749101, 1363640, 174039, 7373, 70,

%e 23: 0, 1, 1638102, 3301586, 446884, 20555, 256,

%e 24: 0, 1, 3591723, 7988916, 1142457, 56413, 884,

%e 25: 0, 1, 7893801, 19322585, 2911078, 152812, 2840, 3,

%e ...

%e The A004111(7) = 12 level-sequences and the branching sequences for the identity trees with 7 nodes are (dots for zeros), together with the maximal branching factors, are:

%e 01: [ . 1 2 3 4 5 6 ] [ 1 1 1 1 1 1 . ] 1

%e 02: [ . 1 2 3 4 5 4 ] [ 1 1 1 2 1 . . ] 2

%e 03: [ . 1 2 3 4 5 3 ] [ 1 1 2 1 1 . . ] 2

%e 04: [ . 1 2 3 4 5 2 ] [ 1 2 1 1 1 . . ] 2

%e 05: [ . 1 2 3 4 5 1 ] [ 2 1 1 1 1 . . ] 2

%e 06: [ . 1 2 3 4 3 2 ] [ 1 2 2 1 . . . ] 2

%e 07: [ . 1 2 3 4 3 1 ] [ 2 1 2 1 . . . ] 2

%e 08: [ . 1 2 3 4 2 3 ] [ 1 2 1 1 . 1 . ] 2

%e 09: [ . 1 2 3 4 2 1 ] [ 2 2 1 1 . . . ] 2

%e 10: [ . 1 2 3 4 1 2 ] [ 2 1 1 1 . 1 . ] 2

%e 11: [ . 1 2 3 2 1 2 ] [ 2 2 1 . . 1 . ] 2

%e 12: [ . 1 2 3 1 2 1 ] [ 3 1 1 . 1 . . ] 3

%e This gives row n=7: [0, 1, 10, 1, 0, 0, ... ].

%p b:= proc(n, i, t, k) option remember; `if`(n=0, 1,

%p `if`(i<1, 0, add(binomial(b(i-1$2, k$2), j)*

%p b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))

%p end:

%p g:= proc(n) local k; if n=1 then 0 else

%p for k while T(n, k)>0 do od; k-1 fi

%p end:

%p T:= (n, k)-> b(n-1$2, k$2) -`if`(k=0, 0, b(n-1$2, k-1$2)):

%p seq(seq(T(n, k), k=0..g(n)), n=1..25);

%t b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i<1, 0, Sum[Binomial[b[i-1, i-1, k, k], j]*b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]]]; g[n_] := If[ n == 1 , 0, For[k=1, T[n, k]>0 , k++]; k-1]; T[n_, k_] := b[n-1, n-1, k, k] - If[k == 0, 0, b[n-1, n-1, k-1, k-1]]; Table[Table[T[n, k], {k, 0, g[n]}], {n, 1, 25}] // Flatten (* _Jean-François Alcover_, Feb 11 2015, after Maple *)

%Y Columns k=0-10 give: A000007, A000012 (for n>0), A245747, A245748, A245749, A245750, A245751, A245752, A245753, A245754, A245755.

%Y Cf. A004111 (identity trees), A244372 (unlabeled rooted trees by outdegree).

%K nonn,tabf

%O 1,11

%A _Joerg Arndt_ and _Alois P. Heinz_, Jul 30 2014

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:39 EDT 2024. Contains 371235 sequences. (Running on oeis4.)