A330617 Triangle read by rows: T(n,k) is the number of paths from node 0 to k in a directed graph with n+1 vertices labeled 0, 1, ..., n and edges leading from i to i+1 for all i, and from i to i+2 for even i and from i to i-2 for odd i.
1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 4, 1, 3, 2, 4, 4, 4, 1, 3, 2, 4, 4, 4, 8, 1, 4, 2, 6, 4, 8, 8, 8, 1, 4, 2, 6, 4, 8, 8, 8, 16, 1, 5, 2, 8, 4, 12, 8, 16, 16, 16, 1, 5, 2, 8, 4, 12, 8, 16, 16, 16, 32, 1, 6, 2, 10, 4, 16, 8, 24, 16, 32, 32, 32, 1, 6, 2, 10, 4, 16, 8, 24, 16, 32, 32, 32, 64
Offset: 0
Examples
First few rows of the triangle are:
1;
1, 1;
1, 1, 2;
1, 2, 2, 2;
1, 2, 2, 2, 4;
1, 3, 2, 4, 4, 4;
1, 3, 2, 4, 4, 4, 8;
1, 4, 2, 6, 4, 8, 8, 8;
1, 4, 2, 6, 4, 8, 8, 8, 16;
1, 5, 2, 8, 4, 12, 8, 16, 16, 16;
1, 5, 2, 8, 4, 12, 8, 16, 16, 16, 32;
...
For n=6 and k=3, T(6,3)=4 is the number of paths from node 0 to node 3 along the directed network: {0,1,2,3}, {0,2,3}, {0,2,4,5,3}, {0,1,2,4,5,3}.
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
- E. Krom and M. M. Roughan, Path Counting and Eulerian Numbers, Girls' Angle Bulletin, Vol. 13, No. 3 (2020), 8-10.
Crossrefs
Cf. A130128.
Programs
-
Mathematica
Table[If[EvenQ@ k, 2^(k/2), 2^((k - 1)/2)*(Ceiling[n/2] - (k - 1)/2)], {n, 0, 12}, {k, 0, n}] // Flatten (* Michael De Vlieger, Mar 23 2020 *) -
PARI
T(n,k)={if(k%2, 2^(k\2)*((n+1)\2 - k\2), 2^(k/2))} \\ Andrew Howroyd, Mar 17 2020
Formula
For k odd: T(n, k) = 2^((k-1)/2)*(ceiling(n/2) - (k-1)/2).
For k even: T(n, k) = 2^(k/2).
T(2*n-1, 2*k-1) = A130128(n, k).