A201730 Triangle T(n,k), read by rows, given by (2,1/2,3/2,0,0,0,0,0,0,0,...) DELTA (0,1/2,-1/2,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938.
1, 2, 0, 5, 1, 0, 14, 6, 0, 0, 41, 26, 1, 0, 0, 122, 100, 10, 0, 0, 0, 365, 363, 63, 1, 0, 0, 0, 1094, 1274, 322, 14, 0, 0, 0, 0, 3281, 4372, 1462, 116, 1, 0, 0, 0, 0, 9842, 14760, 6156, 744, 18, 0, 0, 0, 0, 0
Offset: 0
Examples
Triangle begins: 1 2, 0 5, 1, 0 14, 6, 0, 0 41, 26, 1, 0, 0 122, 100, 10, 0, 0, 0 365, 363, 63, 1, 0, 0, 0
Programs
-
Maple
A201730 := proc(n,k) (1-2*x)/(1-4*x+(3-y)*x^2) ; coeftayl(%,y=0,k) ; coeftayl(%,x=0,n) ; end proc: seq(seq(A201730(n,k),k=0..n),n=0..12) ; # R. J. Mathar, Dec 06 2011
-
Mathematica
m = 13; (* DELTA is defined in A084938 *) DELTA[Join[{2, 1/2, 3/2}, Table[0, {m}]], Join[{0, 1/2, -1/2}, Table[0, {m}]], m] // Flatten (* Jean-François Alcover, Feb 19 2020 *)
Formula
G.f.: (1-2x)/(1-4x+(3-y)*x^2).
Sum_{k, 0<=k<=n} T(n,k)*x^k = A139011(n), A000079(n), A007051(n), A006012(n), A001075(n), A081294(n), A001077(n), A084059(n), A108851(n), A084128(n), A081340(n), A084132(n) for x = -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 respectively.
Sum_{k, k>+0} T(n+k,k) = A081704(n) .
T(n,k) = 3*T(n-1,k)+ Sum_{j>0} T(n-1-j,k-1).
T(n,k) = 4*T(n-1,k)+ T(n-2,k-1) - 3*T(n-2,k) with T(0,0)=1, T(1,0)= 2, T(1,1) = 0 and T(n,k) = 0 if k<0 or if n
A360716 Number of unordered pairs of self-avoiding paths whose sets of nodes are disjoint subsets of a set of n points on a circle; one-node paths are not allowed.
0, 0, 0, 3, 45, 435, 3465, 24794, 165942, 1061730, 6578550, 39796053, 236309931, 1382504669, 7989938775, 45704622660, 259155482652, 1458298435572, 8151155034300, 45290328792695, 250308998693145, 1376766613411959, 7539656755416885, 41126122248463038, 223513887538508850, 1210707873300202550, 6537847299012919890
Offset: 1
Comments
Although each path is self-avoiding, the different paths are allowed to intersect.
Examples
a(5)=30+15=45: the first summand corresponds to the case when one of the paths has three nodes (5*4*3/2=30 variants; division by 2 is due to directional independence) and the second to the case when both paths have two nodes (5!/(2!2!2!)=15 variants).
Links
- Ivaylo Kortezov, Sets of Paths between Vertices of a Polygon, Mathematics Competitions, Vol. 35 (2022), No. 2, ISSN:1031-7503, pp. 35-43.
- Index entries for linear recurrences with constant coefficients, signature (27,-312,2016,-7986,19998,-31472,29880,-15525,3375).
Crossrefs
Formula
a(n) = n*(n-1)*2^(-5)*(5^(n-2) - 2*3^(n-2) + 1).
From Andrew Howroyd, Feb 19 2023: (Start)
Binomial transform of A332426.
a(n) = 27*a(n-1) - 312*a(n-2) + 2016*a(n-3) - 7986*a(n-4) + 19998*a(n-5) - 31472*a(n-6) + 29880*a(n-7) - 15525*a(n-8) + 3375*a(n-9) for n > 9.
G.f.: x^4*(3 - 36*x + 156*x^2 - 288*x^3 + 197*x^4)/((1 - x)*(1 - 3*x)*(1 - 5*x))^3.
E.g.f.: exp(x)*(exp(2*x) - 1)^2*x^2/32.
(End)
A360715 Number of self-avoiding paths with nodes chosen among n given points on a circle; one-node paths are allowed.
1, 3, 9, 30, 105, 369, 1281, 4380, 14769, 49215, 162393, 531450, 1727193, 5580141, 17936145, 57395640, 182948577, 581130747, 1840247337, 5811307350, 18305618121, 57531942633, 180441092769, 564859072980, 1765184603025, 5507375961399, 17157594341241, 53379182394930, 165856745298489, 514727830236645
Offset: 1
Examples
a(4) = A001792(2) + 4*A001792(1) + 6 + 4 = 8 + 4*3 + 6 + 4 = 30 with the four summands corresponding to paths with 4, 3, 2 and 1 nodes, respectively.
Links
- Ivaylo Kortezov, Sets of Paths between Vertices of a Polygon, Mathematics Competitions, Vol. 35 (2022), No. 2, ISSN:1031-7503, pp. 35-43.
- Index entries for linear recurrences with constant coefficients, signature (8,-22,24,-9).
Crossrefs
Formula
a(n) = (n/4)*(3^(n-1)+3).
A361284 Number of unordered triples of self-avoiding paths whose sets of nodes are disjoint subsets of a set of n points on a circle; one-node paths are not allowed.
0, 0, 0, 0, 0, 15, 420, 7140, 95760, 1116990, 11891880, 118776900, 1132182480, 10415938533, 93207174060, 815777235000, 7011723045600, 59364660734172, 496238466573648, 4102968354298200, 33602671702168800, 272909132004479355, 2200084921469527092, 17618774018675345340, 140252152286127750000
Offset: 1
Comments
Although each path is self-avoiding, the different paths are allowed to intersect.
Examples
a(7) = A359404(7) + 7*A359404(6) = 315 + 7*15 = 420 since either all the 7 points are used or one is not.
Links
- Andrew Howroyd, Table of n, a(n) for n = 1..500
- Ivaylo Kortezov, Sets of Paths between Vertices of a Polygon, Mathematics Competitions, Vol. 35 (2022), No. 2, ISSN:1031-7503, pp. 35-43.
Crossrefs
Programs
-
PARI
a(n) = {(n*(n-1)*(n-2)/384) * (7^(n-3) - 3*5^(n-3) + 3^(n-2) - 1)} \\ Andrew Howroyd, Mar 07 2023
Formula
a(n) = (n*(n-1)*(n-2)/384)*(7^(n-3) - 3*5^(n-3) + 3^(n-2) - 1).
E.g.f.: x^3*exp(x)*(exp(2*x) - 1)^3/384. - Andrew Howroyd, Mar 07 2023
A372878 a(n) is the sum of all symmetric valleys in the set of flattened Catalan words of length n.
1, 7, 33, 133, 496, 1770, 6142, 20902, 70107, 232489, 763927, 2491107, 8071234, 26007364, 83402988, 266351548, 847482277, 2687729595, 8499036925, 26804655025, 84336597636, 264777690382, 829636763338, 2594821366338, 8102197327711, 25259791668925, 78638974063827
Offset: 4
Comments
The g.f. listed in Baril et al. has a mistake in the numerator: the factor (1 + 2*x) should be (1 - 2*x).
Links
- Jean-Luc Baril, Pamela E. Harris, and José L. Ramírez, Flattened Catalan Words, arXiv:2405.05357 [math.CO], 2024. See p. 18.
- Index entries for linear recurrences with constant coefficients, signature (9,-30,46,-33,9).
Programs
-
Mathematica
LinearRecurrence[{9,-30,46,-33,9},{1,7,33,133,496},28]
Formula
From Baril et al.: (Start)
G.f.: x^4*(1 - 2*x)/((1 - 3*x)^2*(1 - x)^3).
a(n) = (3^n*(2*n - 5) - 18*n^2 + 54*n - 27)/144. (End)
E.g.f.: (32 + exp(3*x)*(6*x - 5) - 9*exp(x)*(2*x^2 - 4*x + 3))/144.
a(n) - a(n-1) = A261064(n-3).
Comments