Opened 7 years ago

Closed 7 years ago

#18338 closed defect (fixed)

bell_polynomial(n,k) should always return a polynomial

Reported by: Thierry Monteil Owned by:
Priority: major Milestone: sage-6.7
Component: combinatorics Keywords:
Cc: Kevin Dilks Merged in:
Authors: Thierry Monteil Reviewers: Kevin Dilks
Report Upstream: N/A Work issues:
Branch: 6de51b8 (Commits, GitHub, GitLab) Commit: 6de51b865d814879c98e0b3a7c4dbeed963dfb25
Dependencies: Stopgaps:

Status badges

Description

As reported in this ask question, bell_polynomial(n,k) sometimes returns a rational number, while the documents claims that it outputs a polynomial in n-k+1 variables over \QQ.

Change History (17)

comment:1 Changed 7 years ago by Thierry Monteil

Branch: u/tmonteil/bell_polynomial_n_k__should_always_return_a_polynomial

comment:2 Changed 7 years ago by Thierry Monteil

Authors: Thierry Monteil
Commit: d3cc5586e9039da92f1e87bf6a56a5dfae50386a
Status: newneeds_review

Side question : is there a good reason for the variables to start at x_1 and not x_0 ?


New commits:

d3cc558#18338 bell_polynomial(n,k) should always return a polynomial.

comment:3 in reply to:  2 Changed 7 years ago by Vincent Delecroix

Replying to tmonteil:

Side question : is there a good reason for the variables to start at x_1 and not x_0 ?

Indeed, it would be much simpler without this ugly

R = QQ[tuple(['x_'+str(i) for i in range(1, n-k+2)])]

that would just become

R = PolynomialRing(QQ, 'x', n-k+1)

On the other hand, wikipedia starts at 1.

Vincent

comment:4 Changed 7 years ago by Peter Luschny

Vincent, this is indeed the core question and I am happy that you mention it!

The old way to enumerate things here (not only at Wikipedia) is to to start with x_1 and to let the lower triangular matrix of coefficients start at the offset (1,1). Nevertheless the same authors define B_{0,0} = 1 but simply ignore B_{0,k} for k>0. This is a big problem affecting many number triangles on OEIS in particular older versions of the Stirling numbers (see for example the unfortunate (1,1) based definition https://oeis.org/A008275) and of the Lah numbers (https://oeis.org/A008297).

So it depends on how bold the authors of Sage want to be: I am certainly in favor of the definition with x_0, x_1,... which makes thing much cleaner and in agreement with the definition of the Stirling numbers and Lah numbers as they are defined in the recent literature (D. E. Knuth for example, Concrete Mathematics) with an offset (0,0).

Peter

ADDED: For what it's worth I explain my point of view a bit more explicit here:

https://oeis.org/wiki/User:Peter_Luschny/Marginalia

(Link updated.)

Last edited 7 years ago by Peter Luschny (previous) (diff)

comment:5 Changed 7 years ago by git

Commit: d3cc5586e9039da92f1e87bf6a56a5dfae50386a145a97c362ca5faee034430f2a67ce915283fc7e

Branch pushed to git repo; I updated commit sha1. New commits:

145a97c #18338 variables start at x0, not x_1

comment:6 Changed 7 years ago by Thierry Monteil

While we are at it, is there a good reason for the base ring of the polynomials to be QQ and not ZZ ?

comment:7 Changed 7 years ago by git

Commit: 145a97c362ca5faee034430f2a67ce915283fc7ec5281c075bf4e196aea84cafa2c54d119ee6cd7e

Branch pushed to git repo; I updated commit sha1. New commits:

c5281c0#18338 : return a polynomial over ZZ.

comment:8 Changed 7 years ago by Vincent Delecroix

Status: needs_reviewneeds_work

This is ugly

- return result
+ return R(result)

Could you instead make it in such way that the coefficients belong to ZZ. With the current version you are intensively using coercion ZZ[x0,x1,...] -> QQ[x0,x1,...] for no good reasons. i.e. just use // instead of / here

coefficient = factorial(n) / (factorial_product * power_factorial_product)

comment:9 Changed 7 years ago by git

Commit: c5281c075bf4e196aea84cafa2c54d119ee6cd7e55d9a5ef6747d4cac7df581af41c126a676fa280

Branch pushed to git repo; I updated commit sha1. New commits:

55d9a5e#18338 coefficients are integers.

comment:10 Changed 7 years ago by Thierry Monteil

Status: needs_workneeds_review

comment:11 Changed 7 years ago by Kevin Dilks

Docstring giving definition for the Bell Polynomial needs to be changed to reflect the new numbering of x_0,x_1,... as opposed to x_1,x_2,... .

comment:12 Changed 7 years ago by git

Commit: 55d9a5ef6747d4cac7df581af41c126a676fa28012dd9fe9073fef76e81f841466f860c899a5e027

Branch pushed to git repo; I updated commit sha1. New commits:

12dd9fe#18338 : update docstring formula.

comment:13 Changed 7 years ago by git

Commit: 12dd9fe9073fef76e81f841466f860c899a5e0276de51b865d814879c98e0b3a7c4dbeed963dfb25

Branch pushed to git repo; I updated commit sha1. New commits:

6de51b8#18338 reformat formula.

comment:14 Changed 7 years ago by Thierry Monteil

Thanks to notice, i have updated the formula (that was actually missing some braces and was unreadable, see http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/combinat.html#sage.combinat.combinat.bell_polynomial)

comment:15 Changed 7 years ago by Kevin Dilks

Cc: Kevin Dilks added
Reviewers: Kevin Dilks

comment:16 Changed 7 years ago by Kevin Dilks

Status: needs_reviewpositive_review

comment:17 Changed 7 years ago by Volker Braun

Branch: u/tmonteil/bell_polynomial_n_k__should_always_return_a_polynomial6de51b865d814879c98e0b3a7c4dbeed963dfb25
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.