[seqfan] Re: A279196: a plausible meaning?

[Max Alekseyev]

Hi Luc,

>From your translation of languages, it seems to follow that in the formula
degrade^<n>(P) = P + (x+y-1) * Q_n
the coefficients of Q_n are nonnegative, aren't they?

If so, let's consider n=5 and the polynomial
x^3 + 3xy + y^3 = 1 + (x + y - 1) * (x^2 + y^2 - xy + x + y + 1)
It satisfies the definition of A279196 but cannot be obtained by
degradation.
Do I miss something?

Regards,
Max


On Tue, Jun 27, 2023 at 3:47 PM Luc Rousseau <luc_rousseau at hotmail.com>
wrote:

> Dear SeqFans,
>
>
> In 1971 Richard Guy sent a letter to Neil Sloane outlining some integer
> sequences; one of them is A279196,
> "Number of polynomials P(x,y) with nonnegative integer coefficients such
> that P(x,y)==1 (mod x+y−1) and P(1,1)=n".
>
> 1, 1, 2, 5, 13, 36, 102, 295, 864.
>
> In 2017 in a Winter Fruits talk (https://vimeo.com/201218446), Neil said
> about A279196:
> "I don't even know what the [...] polynomials are for the first few
> values, so it might be interesting to look into this."
>
> = = = =
>
> Unaware of this context, a few days ago, I imagined this:
> let the initial configuration be one token at (0, 0).
> A configuration can be "degraded": to do so, { choose a nonempty pile of
> tokens in it, say that at (i, j); remove one token from that pile; then add
> one token at (i + 1, j) and one token at (i, j + 1) }.
> The process being nondeterministic, define a(n) as the number of distinct
> configurations one can possibly get after (n - 1) "degradations" of the
> initial configuration.
>
> A brute force program that I coded gave:
>
> 1, 1, 2, 5, 13, 36, 102, 295, 864, 2557, 7624, 22868, 68920, 208527,
> 632987, 1926752.
>
> Superseeker then showed me that this sequence was extending A279196's
> known terms. Are the two sequences the same? I discovered the
> above-mentionned context.
>
> It appears I can prove a(n) <= A279196(n) (see below); and I am asking:
> has anyone any insights to prove or disprove the equality?
>
> = = = =
>
> Translating languages, from the piles of tokens to polynomials, is easy:
> C*x^i*y^j means that the height of the pile at (i,j) is C.
> The mod(x+y−1) sounds like a bridge between the two definitions, because
> clearly:
>
> degrade(C*x^i*y^j) = (C−1)*x^i*y^j + x^(i+1)*y^j + x^i*y^(j+1) = C*x^i*y^j
> + (x+y−1)*(x^i*y^j)
>
> Now, write P = Sum_{i,j} C[i,j]*x^i*y^j, and degrade P. We have to choose
> an (i0,j0) to actually degrade; this gives:
>
> degrade(P) = (Sum_{(i,j)!=(i0,j0)} C[i,j]x^i*y^j) + (C[i0,j0]*x^i0*y^j0 +
> (x+y−1)(x^i0*y^j0))
>
> degrade(P) = P + (x+y−1)*(x^i0*y^j0)
>
> Applying "degrade" several times lets the cofactor of (x+y−1) grow
> accordingly; we can write:
>
> degrade^<n>(P) = P + (x+y−1) * Q_n
>
> where Q_n keeps the record of where we took the tokens. The fact we took
> exactly n tokens can be transcripted Q_n(1,1)=n. This implies:
>
> degrade^<n−1>(1)(1,1) = 1+(1+1−1)*(n−1) = n.
>
> Thus the polynomials of the degradation problem satisfy Richard Guy's
> axioms and a(n) <= A279196(n).
> But are there other polynomials that do? Was the degradation problem the
> meaning Richard Guy had in mind, was the definition by polynomials a way to
> make it succinct?
>
>
> Best regards,
> Luc
>
> P.S.: for essentially the same speech in a more comfortable, LaTeX form,
> here is a Math StackExchange thread:
>
> https://math.stackexchange.com/questions/2127914/polynomials-px-y-with-nonnegative-integer-coefficients-such-that-px-y-eq
>
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>