Opened 4 years ago

Closed 4 years ago

#18338 closed defect (fixed)

bell_polynomial(n,k) should always return a polynomial

Reported by: tmonteil Owned by:
Priority: major Milestone: sage-6.7
Component: combinatorics Keywords:
Cc: kdilks Merged in:
Authors: Thierry Monteil Reviewers: Kevin Dilks
Report Upstream: N/A Work issues:
Branch: 6de51b8 (Commits) 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 n-k+1 variables over \QQ.

Change History (17)

comment:1 Changed 4 years ago by tmonteil

  • Branch set to u/tmonteil/bell_polynomial_n_k__should_always_return_a_polynomial

comment:2 follow-up: Changed 4 years ago by tmonteil

  • Authors set to Thierry Monteil
  • Commit set to d3cc5586e9039da92f1e87bf6a56a5dfae50386a
  • Status changed from new to needs_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 4 years ago by vdelecroix

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 4 years ago by pluschny

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 4 years ago by pluschny (previous) (diff)

comment:5 Changed 4 years ago by git

  • 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 4 years ago by tmonteil

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 4 years ago by git

  • 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 4 years ago by vdelecroix

  • 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 4 years ago by git

  • 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 4 years ago by tmonteil

  • Status changed from needs_work to needs_review

comment:11 Changed 4 years ago by kdilks

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 4 years ago by git

  • 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 4 years ago by git

  • Commit changed from 12dd9fe9073fef76e81f841466f860c899a5e027 to 6de51b865d814879c98e0b3a7c4dbeed963dfb25

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

6de51b8#18338 reformat formula.

comment:14 Changed 4 years ago by tmonteil

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 4 years ago by kdilks

  • Cc kdilks added
  • Reviewers set to Kevin Dilks

comment:16 Changed 4 years ago by kdilks

  • Status changed from needs_review to positive_review

comment:17 Changed 4 years ago by vbraun

  • 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
Note: See TracTickets for help on using tickets.