Opened 7 years ago
Closed 6 years ago
#18338 closed defect (fixed)
bell_polynomial(n,k) should always return a polynomial
Reported by:  tmonteil  Owned by:  

Priority:  major  Milestone:  sage6.7 
Component:  combinatorics  Keywords:  
Cc:  kdilks  Merged in:  
Authors:  Thierry Monteil  Reviewers:  Kevin Dilks 
Report Upstream:  N/A  Work issues:  
Branch:  6de51b8 (Commits, GitHub, GitLab)  Commit:  6de51b865d814879c98e0b3a7c4dbeed963dfb25 
Dependencies:  Stopgaps: 
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 nk+1
variables over \QQ
.
Change History (17)
comment:1 Changed 7 years ago by
 Branch set to u/tmonteil/bell_polynomial_n_k__should_always_return_a_polynomial
comment:2 followup: ↓ 3 Changed 7 years ago by
 Commit set to d3cc5586e9039da92f1e87bf6a56a5dfae50386a
 Status changed from new to needs_review
comment:3 in reply to: ↑ 2 Changed 7 years ago by
Replying to tmonteil:
Side question : is there a good reason for the variables to start at
x_1
and notx_0
?
Indeed, it would be much simpler without this ugly
R = QQ[tuple(['x_'+str(i) for i in range(1, nk+2)])]
that would just become
R = PolynomialRing(QQ, 'x', nk+1)
On the other hand, wikipedia starts at 1.
Vincent
comment:4 Changed 7 years ago by
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: http://luschny.de/temp/BellReconsidered.html
comment:5 Changed 7 years ago by
 Commit changed from d3cc5586e9039da92f1e87bf6a56a5dfae50386a to 145a97c362ca5faee034430f2a67ce915283fc7e
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
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
 Commit changed from 145a97c362ca5faee034430f2a67ce915283fc7e to c5281c075bf4e196aea84cafa2c54d119ee6cd7e
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
 Status changed from needs_review to needs_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
 Commit changed from c5281c075bf4e196aea84cafa2c54d119ee6cd7e to 55d9a5ef6747d4cac7df581af41c126a676fa280
Branch pushed to git repo; I updated commit sha1. New commits:
55d9a5e  #18338 coefficients are integers.

comment:10 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:11 Changed 7 years ago by
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
 Commit changed from 55d9a5ef6747d4cac7df581af41c126a676fa280 to 12dd9fe9073fef76e81f841466f860c899a5e027
Branch pushed to git repo; I updated commit sha1. New commits:
12dd9fe  #18338 : update docstring formula.

comment:13 Changed 7 years ago by
 Commit changed from 12dd9fe9073fef76e81f841466f860c899a5e027 to 6de51b865d814879c98e0b3a7c4dbeed963dfb25
Branch pushed to git repo; I updated commit sha1. New commits:
6de51b8  #18338 reformat formula.

comment:14 Changed 7 years ago by
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 6 years ago by
 Cc kdilks added
 Reviewers set to Kevin Dilks
comment:16 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:17 Changed 6 years ago by
 Branch changed from u/tmonteil/bell_polynomial_n_k__should_always_return_a_polynomial to 6de51b865d814879c98e0b3a7c4dbeed963dfb25
 Resolution set to fixed
 Status changed from positive_review to closed
Side question : is there a good reason for the variables to start at
x_1
and notx_0
?New commits:
#18338 bell_polynomial(n,k) should always return a polynomial.