|
| |
|
|
A347187
|
|
Triangle read by rows T(n,k), (n,k>=0), with row/diagonal sums to overpartitions/partitions isomorphic to binomial coefficient sums to 2^n/F(n) (Fibonacci numbers) on Pascal's triangle.
|
|
0
|
|
|
|
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 3, 6, 3, 1, 1, 3, 8, 8, 3, 1, 1, 3, 9, 14, 9, 3, 1, 1, 3, 9, 19, 19, 9, 3, 1, 1, 3, 9, 21, 32, 21, 9, 3, 1, 1, 3, 9, 22, 42, 42, 22, 9, 3, 1, 1, 3, 9, 22, 48, 66, 48, 22, 9, 3, 1, 1, 3, 9, 22, 50, 87, 87, 50, 22, 9, 3, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
The rows sum to overpartitions (A015128). All T(n,k) intersected by the diagonal line drawn on points {T(n,0), T(n-1,1)} sum to unrestricted partitions of n (A000041). The same lines drawn on Pascal's triangle produce the well-known sums to 2^n and to the Fibonacci numbers, resp.
The triangle is found via a generalization of Euler's pentagonal number theorem over 2 positive integer parameters alpha and beta (a,b here) *[1]. Substituting the quadratic f(a,b,k)=((a+b)k^2-(b-a)k)/2 in place of f(k)=(3k^2-k)/2 (the quadratic of the generalized pentagonal numbers (A001318)) produces partition functions, p(a,b,n), and sigma sum of divisors functions, s(a,b,n), restricted to counting/summing only partitions/divisors with parts equivalent to 0, a or b mod (a+b). Only integers 0 < a < b are considered, to avoid duplicates. The base case is given when a=1, b=2, with corresponding Euler recurrences for unrestricted partitions and sum of divisors (A000203) functions. All other b > a cases produce the mod-restricted analogs. The coefficients of the a,b-generalized recurrences, analogous to A010815, are given by directly inverting the sequence of the mod-restricted partitions, i.e., inverting the a,b-partition generating function. The a=b cases are considered separately because the a=b=1 case yields the overpartitions function and a naturally defined "overdivisors" function.
Let the sequences of P(i+1,i+2,j) over j >= 0 be the i-th rows over i >= 0 to produce this table:
1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, ...
1, 0, 1, 1, 1, 2, 2, 3, 4, 4, 7, 6, 10, 11, 13, 18, 19, ...
1, 0, 0, 1, 1, 0, 1, 2, 1, 1, 3, 3, 2, 3, 6, 4, 4, ...
1, 0, 0, 0, 1, 1, 0, 0, 1, 2, 1, 0, 1, 3, 3, 1, 1, ...
1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 2, 1, 0, 0, 1, 3, ...
1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 2, 1, 0, 0, ...
1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 2, 1, ...
1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, ...
1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, ...
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, ...
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, ...
The finite sequences of the T(n,k) rows appear in order on every row of the table, with i zeros between each T(n,0). As j increases, n eventually exceeds i on a given table row and the triangle rows then overlap and sum. Sequence A000041, as the first table row, for example, is constructed by padding every row of the triangle with n zeros and summing them into a single sequence. Using T(n,k) = p(n+1, n+2, 2*binomial(n+1,2)+k) ensures i is sufficiently large to avoid overlaps.
A recursive method of generating the triangle is found by first observing that since the rows sum to overpartitions (let this be O_p(n)), the recursion for O_p(n) may be used, but must operate on whole rows rather than singular values, so must also specify a correct offset for the starting point of each row when added in the recursive sum. Since overpartitions are given when a=b=1, the recurrence for O_p(n) can be derived by substituting into the a,b-generalized Euler recurrence for p(a,b,n), given by p(a,b,n) = p(a,b,n-f(a,b,1)) + p(a,b,n-f(a,b,-1)) - p(a,b,n-f(a,b,2)) - p(a,b,n-f(a,b,-2)) ..., to produce p(1,1,n) = O_p(n) = 2*O_p(n-1) - 2*O_p(n-4) + 2*O_p(n-9) - ... = Sum_{j=1..floor(sqrt(n))} (-1)^(j+1)*2*O_p(n-j^2). The coefficients of this recurrence may also be derived by direct examination of the inverse of the sequence of overpartitions, i.e., the coefficients of the q-series with g.f. Product_{k>=1} (1-q^k)/(1+q^k) *[2][3]. It follows by induction that each 2*O_p(n-j^2) term is composed of 2 copies of a previous row, with different offsets given by binomial(j,2) and binomial(j+1,2). Thus, with O_p(0)=T(0,0)=1 by definition, we obtain: T(n,k) = Sum_{j=1..floor(sqrt(n))} (-1)^(j+1)*(T(n-j^2, k - binomial(j,2)) + T(n-j^2, k - binomial(j+1,2))).
Analogous to the row/diagonal sums, all a,b-generalized partition values, p(a, b, n), may be computed by summing the T(n,k) given on the integral points of the line y = ((a-b)*x + n)/a, where the left edge of the triangle is taken as the y-axis, +y is in the down direction and (y,x) are proxies for (n,k). The generalization's duplicate values, given by the b > a cases, correspond to lines with positive slope, giving the p(b, a, n) as sums of the T(n,k) on integral points on the lines y = ((b-a)*x + n)/b. The lines of the duplicates are the reflections about the triangle's T(2n,n) symmetry axis. Were the symmetry axis to be taken as the y-axis, the slopes of mutually reflected lines would have the same magnitudes with opposite signs. With the Cartesian approach here, the T(n,k) summing to p(a,b,n) appear on lines with rational, negative slopes on the open interval m = (-oo, 0), with unrestricted partitions given on m = -1 lines. Overpartitions are given on m=0 and the T(n,k) summing to the duplicates, p(b,a,n), then appear on positively sloped lines over the open interval m = (0,1), with unrestricted partitions given again on lines with m = 1/2.
The lines containing the T(n,k) summing to p(a,b,n), when mapped to Pascal's triangle, correspond to a,b-generalized Fibonacci numbers, given by F(a, b, 0) = 1, F(a, b, n) = F(a, b, n-a) + F(a, b, n-b). Swapping a and b then produces the reflected duplicates, F(b, a, n), in the same manner that the p(b, a, n) duplicate values are produced.
For fixed k, T(n, k) = T(n, n-k) increase with n to maximum "eventual" values, given by A000716.
[1] H. Leung demonstrates the generalization for the a=1 cases, with applications to Bell Polynomials (see ref.).
[2] R. da Silva and P. Sakai provide another proof of the overpartitions recurrence in their paper (see ref.).
[3] Merca derives the overpartitions recurrence directly from an identity attributed to Gauss (see ref.).
|
|
|
LINKS
|
|
|
|
FORMULA
|
Via a,b mod restricted partition function:
T(n,k) = p(n+1, n+2, 2*binomial(n+1,2)+k), where
p(a,b,n) is the n-th coefficient of the q-series with g.f. Product_{k>=1|k==0,k==a or k==b (mod (a+b))} 1/(1-q^k), or
p(a,b,n) can be computed using its Euler recurrence given by:
p(a,b,n) = Sum_{k>=1|n-f(a,b,k)>=0} (-1)^(k+1)*(p(a,b,n-f(a,b,k)) + p(a,b,n-f(a,b,-k))), where, if n-f(a,b,-k)<0, p(a,b,n-f(a,b,-k))=0 and
f(a,b,k) = ((a+b)*k^2-(b-a)*k)/2.
Via direct recursion:
T(0,0) = 1;
T(n,k) = Sum_{j=1..floor(sqrt(n))} (-1)^(j+1)*(T(n-j^2, k - binomial(j,2)) + T(n-j^2, k - binomial(j+1,2))).
p(a,b,n) (also p(b,a,n)) via sums of T(n,k) on integral lattice points of y(x) = -((b-a)/a)*x + n/a:
p(a, b, n) = Sum_{ x| 0 <= x <= y(x),
y(x)| y(x) = floor(y(x)) } T(y(x), x).
|
|
|
EXAMPLE
|
Triangle begins:
1;
1, 1;
1, 2, 1;
1, 3, 3, 1;
1, 3, 6, 3, 1;
1, 3, 8, 8, 3, 1;
1, 3, 9, 14, 9, 3, 1;
1, 3, 9, 19, 19, 9, 3, 1;
1, 3, 9, 21, 32, 21, 9, 3, 1;
1, 3, 9, 22, 42, 42, 22, 9, 3, 1;
1, 3, 9, 22, 48, 66, 48, 22, 9, 3, 1;
1, 3, 9, 22, 50, 87, 87, 50, 22, 9, 3, 1;
|
|
|
MATHEMATICA
|
(* via a, b mod restricted partition functions *)
lim = 20; P[a_, b_, n_] := P[a, b, n] = (F[k_] := ((a+b)k^2 + (a-b)k)/2;
P[a, b, 0] = 1; If[n == 0, 1, Sum[(-1)^(k+1)
(If[n-F[k] < 0, 0, P[a, b, n-F[k]]] +
If[n-F[-k] < 0, 0, P[a, b, n-F[-k]]]), {k, 1, n}]]);
T[n_, k_] := T[n, k] =
(If[k < 0 || k > n, 0, P[n+1, n+2, 2 Binomial[n+1, 2]+k]]);
MatrixForm[Table[Table[T[n, k], {k, 0, n}], {n, 0, lim}]]
(* via direct recursion *)
lim = 20;
T[n_, k_]:=T[n, k]=(T[0, 0]=1;
If[n==0 && k==0, 1, Sum[(-1)^(j+1)(If[k-Binomial[j, 2] < 0, 0, T[n-j^2, k-Binomial[j, 2]]] + If[k-Binomial[j+1, 2] < 0, 0, T[n-j^2, k-Binomial[j+1, 2]]]), {j, 1, Floor[n^(1/2)]}]]);
MatrixForm[Table[Table[T[n, k], {k, 0, n}], {n, 0, lim}]]
(* via a recursion operating on the triangle row sequences *)
lim=20; S[0]={1};
Table[S[n]=Sum[(-1)^(j+1)(PadRight[PadLeft[S[n-j^2], n+1-Binomial[j, 2]], n+1] + PadRight[PadLeft[S[n-j^2], n+1-Binomial[j+1, 2]], n+1]), {j, 1, Floor[n^(1/2)]}], {n, 1, lim}];
MatrixForm[Table[S[n], {n, 0, lim}]]
(* p(a, b, n) (and p(b, a, n)) via summing select T(n, k) from the triangle held in memory. *)
memlim = 300;
S[0] = {1}; Table[
S[n] = Sum[(-1)^(j + 1) (PadRight[
PadLeft[S[n - j^2], n + 1 - Binomial[j, 2]], n + 1] +
PadRight[PadLeft[S[n - j^2], n + 1 - Binomial[j + 1, 2]],
n + 1]), {j, 1, Floor[n^(1/2)]}], {n, 1, memlim}];
y[a_, b_, x_, n_] := -((b - a)/a) x + n/a;
p[a_, b_, n_] := (x = 0; P = 0;
If[n == 0, P = 1,
While[x <= y[a, b, x, n],
If[y[a, b, x, n] == Floor[y[a, b, x, n]],
P += If[x > y[a, b, x, n], 0, S[y[a, b, x, n]][[x + 1]]]];
x += 1]]; P)
|
|
|
PROG
|
(PARI) T(n, k) = if (!n && !k, 1, sum(j=1, sqrtint(n), (-1)^(j+1)*(T(n-j^2, k - binomial(j, 2)) + T(n-j^2, k - binomial(j+1, 2))))); \\ Michel Marcus, Aug 26 2021
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
