Relative symmetric polynomials and money change problem
This article is devoted to the number of non-negative solutions of the linear Diophantine equation a₁t₁ + a₂t₂ + ⋯ + antn = d, where a₁,…,an, and d are positive integers. We obtain a relation between the number of solutions of this equation and characters of the symmetric group, using relative symme...
Збережено в:
| Дата: | 2013 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2013
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/152353 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Relative symmetric polynomials and money change problem / M. Shahryari // Algebra and Discrete Mathematics. — 2013. — Vol. 16, № 2. — С. 287–292. — Бібліогр.: 3 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-152353 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1523532019-06-11T01:24:59Z Relative symmetric polynomials and money change problem Shahryari, M. This article is devoted to the number of non-negative solutions of the linear Diophantine equation a₁t₁ + a₂t₂ + ⋯ + antn = d, where a₁,…,an, and d are positive integers. We obtain a relation between the number of solutions of this equation and characters of the symmetric group, using relative symmetric polynomials. As an application, we give a necessary and sufficient condition for the space of the relative symmetric polynomials to be non-zero. 2013 Article Relative symmetric polynomials and money change problem / M. Shahryari // Algebra and Discrete Mathematics. — 2013. — Vol. 16, № 2. — С. 287–292. — Бібліогр.: 3 назв. — англ. 1726-3255 2010 MSC:Primary 05A17, Secondary 05E05 and 15A69. http://dspace.nbuv.gov.ua/handle/123456789/152353 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
This article is devoted to the number of non-negative solutions of the linear Diophantine equation a₁t₁ + a₂t₂ + ⋯ + antn = d, where a₁,…,an, and d are positive integers. We obtain a relation between the number of solutions of this equation and characters of the symmetric group, using relative symmetric polynomials. As an application, we give a necessary and sufficient condition for the space of the relative symmetric polynomials to be non-zero. |
| format |
Article |
| author |
Shahryari, M. |
| spellingShingle |
Shahryari, M. Relative symmetric polynomials and money change problem Algebra and Discrete Mathematics |
| author_facet |
Shahryari, M. |
| author_sort |
Shahryari, M. |
| title |
Relative symmetric polynomials and money change problem |
| title_short |
Relative symmetric polynomials and money change problem |
| title_full |
Relative symmetric polynomials and money change problem |
| title_fullStr |
Relative symmetric polynomials and money change problem |
| title_full_unstemmed |
Relative symmetric polynomials and money change problem |
| title_sort |
relative symmetric polynomials and money change problem |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2013 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/152353 |
| citation_txt |
Relative symmetric polynomials and money change problem / M. Shahryari // Algebra and Discrete Mathematics. — 2013. — Vol. 16, № 2. — С. 287–292. — Бібліогр.: 3 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT shahryarim relativesymmetricpolynomialsandmoneychangeproblem |
| first_indexed |
2025-07-13T02:53:37Z |
| last_indexed |
2025-07-13T02:53:37Z |
| _version_ |
1837498600642314240 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 16 (2013). Number 2. pp. 287 – 292
c© Journal “Algebra and Discrete Mathematics”
Relative symmetric polynomials
and money change problem
M. Shahryari
Communicated by V. A. Artamonov
Abstract. This article is devoted to the number of non-
negative solutions of the linear Diophantine equation
a1t1 + a2t2 + · · · + antn = d,
where a1, . . . , an, and d are positive integers. We obtain a relation
between the number of solutions of this equation and characters
of the symmetric group, using relative symmetric polynomials. As
an application, we give a necessary and sufficient condition for the
space of the relative symmetric polynomials to be non-zero.
Suppose a1, . . . , an, and d are positive integers, and consider the fol-
lowing linear Diophantine equation:
a1t1 + a2t2 + · · · + antn = d.
Let Qd(a1, . . . , an) be the number of non-negative integer solutions of this
equation. Computing the exact values of the function Qd is the well-known
money change problem. It is easy to see that a generating function for
Qd(a1, . . . , an) is
n∏
i=1
1
1 − tai
.
This article is devoted for an interesting relation between Qd and ir-
reducible complex characters of the symmetric group Sm, where m =
a1 + · · · + an. In fact, we will show that Qd is a permutation character of
2010 MSC: Primary 05A17, Secondary 05E05 and 15A69.
Key words and phrases: Money change problem; Partitions of integers; Relative
symmetric polynomials; Symmetric groups; Complex characters.
288 Money change problem
Sm, and then we will find its irreducible constituents. Our main tool, in
the investigation of Qd, is the notion of relative symmetric polynomials,
which is introduced by the author in [3]. Once, we find the irreducible
constituents of Qd, we can also obtain a necessary and sufficient condition
for vanishing of the space of relative symmetric polynomials. A similar
result was obtained in [2], for vanishing of symmetry classes of tensors,
using the same method.
We need a survey of results about relative symmetric polynomials in
this article. For a detailed exposition, one can see [3].
Let G be a subgroup of the full symmetric group Sm of degree m and
suppose χ is an irreducible complex character of G. Let Hd[x1, . . . , xm]
be the complex space of homogenous polynomials of degree d with the
independent commuting variables x1, . . . , xm. Suppose Γ+
m,d is the set
of all m-tuples of non-negative integers, α = (α1, . . . , αm), such that∑
i αi = d. For any α ∈ Γ+
m,d, define Xα to be the monomial xα1
1 · · ·xαm
m .
So the set {Xα : α ∈ Γ+
m,d} is a basis of Hd[x1, . . . , xm]. We define also
an inner product on Hd[x1, . . . , xm] by
< Xα, Xβ >= δα,β .
The group G acts on Hd[x1, . . . , xm] via
qσ(x1, . . . , xm) = q(xσ−1(1), . . . , xσ−1(m)).
It also acts on Γ+
m,d by
σα = (ασ(1), . . . , ασ(m)).
Let ∆ be a set of representatives of orbits of Γ+
m,d under the action of G.
Now consider the idempotent
T (G,χ) =
χ(1)
|G|
∑
σ∈G
χ(σ)σ
in the group algebra CG. Define the space of relative symmetric polyno-
mials of degree d with respect to G and χ to be
Hd(G,χ) = T (G,χ)(Hd[x1, . . . , xm]).
Let q ∈ Hd[x1, . . . , xm]. Then we set
q∗ = T (G,χ)(q)
M. Shahryari 289
and we call it a symmetrized polynomial with respect to G and χ. Clearly
Hd(G,χ) =< Xα,∗ : α ∈ Γ+
m,d >,
where < set of vectors > denotes the subspace generated by a given
set of vectors.
Recall that the inner product of two characters of an arbitrary group
K is defined as follows,
[φ, ψ]K =
1
|K|
∑
σ∈K
φ(σ)ψ(σ−1).
In the special case where K is a subgroup of G and φ and ψ are characters
of G, the notation [φ, ψ]K will denote the inner product of the restrictions
of φ and ψ to K.
It is proved it [3] that for any α, we have
||Xα,∗||2 = χ(1)
[χ, 1]Gα
[G : Gα]
,
where Gα is the stabilizer subgroup of α under the action of G. Hence,
Xα,∗ 6= 0, if and only if [χ, 1]Gα 6= 0. According to this result, let Ω be
the set of all α ∈ Γ+
m,d, with [χ, 1]Gα 6= 0 and suppose ∆̄ = ∆ ∩ Ω.
We proved in [3], the following formula for the dimension of Hd(G,χ)
dimHd(G,χ) = χ(1)
∑
α∈∆̄
[χ, 1]Gα .
Note that, ∆̄ depends on χ, but ∆ depends only on G. Since, [χ, 1]Gα = 0,
for all α ∈ ∆ − ∆̄, we can re-write the above formula, as
dimHd(G,χ) = χ(1)
∑
α∈∆
[χ, 1]Gα .
There is also another interesting formula for the dimension ofHd(G,χ).
This is the formula which employs the function Qd and so it connects
the money change problem to relative symmetric polynomials. Let σ ∈ G
be any element with the cycle structure [a1, . . . , an], ( i.e. σ is equal to
a product of n disjoint cycles of lengths a1, . . . , an, respectively). Define
Qd(σ) to be the number of non-negative integer solutions of the equation
a1t1 + a2t2 + · · · + antn = d,
290 Money change problem
so, we have Qd(σ) = Qd(a1, . . . , an). If we consider the free vector space
C[Γ+
m,d] as a CG-module, then for all σ ∈ G, we have
Tr σ = Qd(σ),
and hence, Qd is a permutation character of G. It is proved in [3], that
we have also
dimHd(G,χ) =
χ(1)
|G|
∑
σ∈G
χ(σ)Qd(σ).
Note that, we can write this result as dimHd(G,χ) = χ(1)[χ,Qd]G. Now,
comparing two formulae for the dimension of Hd(G,χ) and using the
reciprocity relation for induced characters, we obtain
Qd(a1, . . . , an) =
∑
α∈∆
(1Gα)G(σ),
where σ ∈ Sm is any permutation of the cycle structure [a1, . . . , an], G is
any subgroup of Sm containing σ and m = a1 + · · · + an. It is clear that,
if α and β are in the same orbit of Γ+
m,d, then (1Gα)G = (1Gβ
)G, so we
have also
Qd(a1, . . . , an) =
1
|G|
∑
α∈Γ+
m,d
|Gα|(1Gα)G(σ).
As our main result in this section, we have,
Theorem A.
Qd =
1
|G|
∑
α∈Γ+
m,d
|Gα|(1Gα)G.
For a fixed equation
a1t1 + a2t2 + · · · + antn = d,
suppose σ is a permutation of the cycle structure [a1, . . . , an] and let G be
the cyclic group generated by σ. Clearly this G is the smallest subgroup
of Sm which we can use to obtain the number of non-negative solutions
of the above equation. By Theorem A, the required number is
Qd(σ) =
1
|G|
∑
α∈Γ+
m,d
|Gα|(1Gα)G(σ).
On the other hand, if we want to have a formula for all values of Qd,
we must let G = Sm, which contains any possible cycle structure. So in
the remaining part of this article, we will assume that, G = Sm, then
M. Shahryari 291
using representation theory of symmetric groups, we will find, irreducible
constituents of Qd.
We need some standard notions from representation theory of sym-
metric groups. Ordinary representations of Sm are in one to one corre-
spondence with partitions of m. Let
π = (π1, . . . , πs)
be any partition of m. The irreducible character of Sm, corresponding to
a partition π is denoted by χπ. There is also a subgroup of Sm, associated
to π, which is called the Young subgroup and it is defined as,
Sπ = S{1,...,π1} × S{π1+1,...,π1+π2} × · · · .
Therefore, we have Sπ
∼= Sπ1 × · · · × Sπs .
Let π = (π1, . . . , πs) and µ = (µ1, . . . , µl) be two partitions of m. We
say that µ majorizes π, iff for any 1 ≤ i ≤ min{s, l}, the inequality
π1 + · · · + πi ≤ µ1 + · · · + µi
holds. In this case we write λEµ. This is clearly a partial ordering on the
set of all partitions of m. A generalized µ-tableau of type π is a function
T : {(i, j) : 1 ≤ i ≤ h(µ), 1 ≤ j ≤ µi} → {1, 2, . . . ,m}
such that for any 1 ≤ i ≤ m, we have |t−1(i)| = πi. This generalized
tableau is called semi-standard if for each i, j1 < j2 implies T (i, j1) ≤
T (i, j2) and for any j, i1 < i2 implies T (i1, j) < T (i2, j). In other words, T
is semi-standard, iff every row of T is non-descending and every column of
T is ascending. The number of all such semi-standard tableaux is denoted
by Kµπ and it is called the Kostka number. It is well known that Kµπ 6= 0
iff µ majorizes π, see [1], for example. We have also,
Kµπ = [(1Sπ )Sm , χµ]Sm
= [1, χµ]Sπ .
For any α ∈ Γ+
m,d, the multiplicity partition is denoted by M(α), so, to
obtain M(α), we must arrange the multiplicities of numbers 0, 1, . . . , d
in α in the descending order. It is clear that (Sm)α
∼= SM(α), the Young
subgroup. If M(α) = (k1, . . . , ks), then we have
|(Sm)α| = k1!k2! . . . ks!.
292 Money change problem
In what follows, we use the notation M(α)! for the number k1!k2! . . . ks!.
On the other hand, we have
(1Gα)G = (1SM(α)
)Sm
=
∑
M(α)Eπ
Kπ,M(α)χ
π.
Now, using Theorem A, we obtain,
Theorem B.
Qd =
1
m!
∑
α∈Γ+
m,d
∑
M(α)Eπ
M(α)!Kπ,M(α)χ
π.
As a result, we can compute the dimension of Hd(Sm, χ
π), in a new
fashion. We have,
dimHd(Sm, χ
π) = χπ(1)[χπ, Qd]Sm
=
χπ(1)
m!
∑
α∈Γ+
m,d
,M(α)Eπ
M(α)!Kπ,M(α).
Note that, this generalizes the similar formulae in the final part of the
second section of [3]. Now, as a final result, we have also, a necessary and
sufficient condition for Hd(Sm, χ
π) to be non-zero.
Theorem C. We have Hd(Sm, χ
π) 6= 0, if and only if there exists α ∈
Γ+
m,d, such that M(α) E π.
References
[1] B. Sagan, The Symmetric Group: Representation, Combinatorial Algorithms and
Symmetric Functions, Wadsworth and Brook/ Cole math. series, 1991.
[2] M. Shahryari, M. A. Shahabi, On a permutation character of Sm, Linear and
Multilinear Algebra, 44 (1998), 45 − 52.
[3] M. Shahryari, Relative symmetric polynomials, Linear Algebra and its Applica-
tions, 433 (2010), 1410 − 1421.
Contact information
M. Shahryari Department of Pure Mathematics, Faculty of
Mathematical Sciences, University of Tabriz,
Tabriz, Iran
E-Mail: mshahryari@tabrizu.ac.ir
Received by the editors: 08.04.2012
and in final form 28.04.2012.
|