Repository: sagemath/sage
Issue category: Performance Issue

Fast cardinality method for IntegerVectorsModPermutationGroup
### Problem Description

`IntegerVectorsModPermutationGroup` has no implementation of `cardinality`, so it defaults to iterating over the whole set and tallying. This is obviously slow for large sets.

For example, with vectors of length 10, summing to 20, and with the permutation group where the first two elements can be swapped, it takes more than two minutes to compute the cardinality.

### Proposed Solution

The cardinality should be calculated using the cycle index theorem (see e.g. [Peter Cameron's blog post](https://cameroncounts.wordpress.com/2018/03/16/a-counting-problem/) for an explanation).

An example code is here. This should be more or less a ready plug-in for the cardinality method.

```
def fast_cardinality(self):
    G = self._permgroup
    k = G.degree()              # Number of boxes
    d = self._sum               # Number of balls
    m = self._max_part          # Maximum balls in one box, -1 for no limit
    if m == -1:
        m = d
        
    if k==0:
        # Special case, no boxes.
        if d==0:
            return 1
        else:
            return 0

    # Power series with enough precision
    R.<x> = PowerSeriesRing(QQ, default_prec = d+1)

    # The function-counting series, for maximum part size m, is
    # (1-t^(m+1)) / (1-t) = 1+t+...+t^m.
    #
    # For the figure-counting series, we substitute x^cyclen for t.
    
    Z = G.cycle_index()
    funcount = sum(coeff * prod((1-x^((m+1)*cyclen)) / (1-x^cyclen)
                                for cyclen in cyctype)
                   for (cyctype, coeff) in Z)

    # Extract the x^d coefficient.
    dic = funcount.dict()
    if d in dic:
        return Integer(dic[d])  # Convert from Rational to Integer
    else:
        return 0
```


### Alternatives Considered

We could leave it as is, and rely on users to perform the cycle index calculations.

### Additional Information

Here is a speed comparison.

Permutation group acting on 10 elements, and only containing two permutations, the trivial one and the swap `(1,2)`. Count the vectors that sum to 20.

The times are about 0.1 seconds versus 161 seconds.

```
sage: G=PermutationGroup([(1,2)],domain=range(10)); V=IntegerVectorsModPermutationGroup(G,20)                                             
sage: t0=time(); fast_cardinality(V), time()-t0                                                                                           
(5911763, 0.09431600570678711)
sage: t0=time(); V.cardinality(), time()-t0                                                                                               
(5911763, 160.82350969314575)
sage: version()                                                                                                                           
'SageMath version 9.0, Release Date: 2020-01-01'
```


### Is there an existing issue for this?

- [X] I have searched the existing issues for a bug report that matches the one I want to file, without success.
IntegerVectorsModPermutationGroup crashes on empty domain
### Steps To Reproduce

In SageMath version 9.0, Release Date: 2020-01-01, run the following:

```
sage: P=PermutationGroup([],domain=[])                                          
sage: V=IntegerVectorsModPermutationGroup(P, sum=1)                             
sage: V.cardinality()   
```


### Expected Behavior

The cardinality should be zero.

The domain is empty, so we are counting empty integer vectors whose sum is 1. There are no such vectors.


### Actual Behavior

SageMath crashes with the following dump.

```
------------------------------------------------------------------------
/usr/lib/python3/dist-packages/cysignals/signals.cpython-38-x86_64-linux-gnu.so(+0x8154)[0x7ff63a15a154]
/usr/lib/python3/dist-packages/cysignals/signals.cpython-38-x86_64-linux-gnu.so(+0x8329)[0x7ff63a15a329]
/usr/lib/python3/dist-packages/cysignals/signals.cpython-38-x86_64-linux-gnu.so(+0xad5f)[0x7ff63a15cd5f]
/lib/x86_64-linux-gnu/libc.so.6(+0x43090)[0x7ff63d26a090]
/usr/lib/python3/dist-packages/sage/combinat/enumeration_mod_permgroup.cpython-38-x86_64-linux-gnu.so(+0x6ffb)[0x7ff51eb7effb]
/usr/lib/python3/dist-packages/sage/combinat/enumeration_mod_permgroup.cpython-38-x86_64-linux-gnu.so(+0x884b)[0x7ff51eb8084b]
/usr/lib/python3/dist-packages/sage/combinat/enumeration_mod_permgroup.cpython-38-x86_64-linux-gnu.so(+0xcb2d)[0x7ff51eb84b2d]
python3(PyCFunction_Call+0x59)[0x5f6939]
python3(_PyObject_MakeTpCall+0x296)[0x5f7506]
python3(_PyEval_EvalFrameDefault+0x59c7)[0x570787]
python3[0x50b07e]
python3(_PyEval_EvalFrameDefault+0x5796)[0x570556]
python3[0x500e63]
python3(_PyEval_EvalFrameDefault+0xafd)[0x56b8bd]
python3(_PyEval_EvalCodeWithName+0x26a)[0x5697da]
python3[0x50b1f0]
python3(_PyEval_EvalFrameDefault+0x5796)[0x570556]
python3(_PyEval_EvalCodeWithName+0x26a)[0x5697da]
python3(PyEval_EvalCode+0x27)[0x68e547]
python3[0x601624]
python3[0x5c4ef0]
python3(_PyEval_EvalFrameDefault+0x72d)[0x56b4ed]
python3[0x5009c8]
python3(_PyEval_EvalFrameDefault+0x213d)[0x56cefd]
python3[0x5009c8]
python3(_PyEval_EvalFrameDefault+0x213d)[0x56cefd]
python3[0x5009c8]
python3[0x504716]
python3(_PyEval_EvalFrameDefault+0x859)[0x56b619]
python3(_PyFunction_Vectorcall+0x1b6)[0x5f6ce6]
python3(_PyEval_EvalFrameDefault+0x72d)[0x56b4ed]
python3(_PyFunction_Vectorcall+0x1b6)[0x5f6ce6]
python3(_PyEval_EvalFrameDefault+0x859)[0x56b619]
python3(_PyEval_EvalCodeWithName+0x26a)[0x5697da]
python3[0x50b1f0]
python3(_PyEval_EvalFrameDefault+0x1910)[0x56c6d0]
python3(_PyEval_EvalCodeWithName+0x26a)[0x5697da]
python3(_PyFunction_Vectorcall+0x393)[0x5f6ec3]
python3(_PyEval_EvalFrameDefault+0x859)[0x56b619]
python3(_PyEval_EvalCodeWithName+0x26a)[0x5697da]
python3(_PyFunction_Vectorcall+0x393)[0x5f6ec3]
python3(_PyEval_EvalFrameDefault+0x859)[0x56b619]
python3(_PyFunction_Vectorcall+0x1b6)[0x5f6ce6]
python3(_PyEval_EvalFrameDefault+0x859)[0x56b619]
python3(_PyEval_EvalCodeWithName+0x26a)[0x5697da]
python3(PyEval_EvalCode+0x27)[0x68e547]
python3[0x67dbf1]
python3[0x67dc6f]
python3[0x67dd11]
python3(PyRun_SimpleFileExFlags+0x197)[0x67fe37]
python3(Py_RunMain+0x212)[0x6b7c82]
python3(Py_BytesMain+0x2d)[0x6b800d]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf3)[0x7ff63d24b083]
python3(_start+0x2e)[0x5fb85e]
------------------------------------------------------------------------

```

### Additional Information

_No response_

### Environment

```markdown
- **OS**: Ubuntu 20.05
- **Sage Version**: 9.0, Release Date: 2020-01-01

Also tested on Sage 10.0, Release Date: 2023-05-20, with similar results.
```


### Checklist

- [X] I have searched the existing issues for a bug report that matches the one I want to file, without success.
- [X] I have read the documentation and troubleshoot guide


Functions to edit:
src/sage/combinat/integer_vectors_mod_permgroup.py:IntegerVectorsModPermutationGroup.__classcall__
src/sage/combinat/integer_vectors_mod_permgroup.py:IntegerVectorsModPermutationGroup_All.is_canonical
src/sage/combinat/integer_vectors_mod_permgroup.py:IntegerVectorsModPermutationGroup_with_constraints._repr_
src/sage/combinat/integer_vectors_mod_permgroup.py:IntegerVectorsModPermutationGroup_with_constraints.__iter__
src/sage/combinat/integer_vectors_mod_permgroup.py:IntegerVectorsModPermutationGroup_with_constraints.is_canonical
src/sage/combinat/integer_vectors_mod_permgroup.py:IntegerVectorsModPermutationGroup_with_constraints
src/sage/combinat/integer_vectors_mod_permgroup.py:Element.check
Functions added: src/sage/combinat/integer_vectors_mod_permgroup.py:IntegerVectorsModPermutationGroup_with_constraints.cardinality
src/sage/combinat/integer_vectors_mod_permgroup.py:IntegerVectorsModPermutationGroup_with_constraints

Patch:
diff --git a/src/sage/combinat/integer_vectors_mod_permgroup.py b/src/sage/combinat/integer_vectors_mod_permgroup.py
index 996d73a5efa..7877fedee44 100644
--- a/src/sage/combinat/integer_vectors_mod_permgroup.py
+++ b/src/sage/combinat/integer_vectors_mod_permgroup.py
@@ -1,6 +1,11 @@
 # sage.doctest: needs sage.combinat sage.groups
 r"""
 Integer vectors modulo the action of a permutation group
+
+AUTHORS:
+
+* Nicolas Borie (2010-2012) - original module
+* Jukka Kohonen (2023) - fast cardinality method, :issue:`36787`, :issue:`36681`
 """
 # ****************************************************************************
 #    Copyright (C) 2010-12 Nicolas Borie <nicolas.borie at math dot u-psud.fr>
@@ -24,6 +29,12 @@
 
 from sage.combinat.integer_vector import IntegerVectors
 
+from sage.rings.power_series_ring import PowerSeriesRing
+from sage.rings.rational_field import QQ
+from sage.rings.integer import Integer
+from sage.misc.misc_c import prod
+from sage.arith.misc import binomial
+
 
 class IntegerVectorsModPermutationGroup(UniqueRepresentation):
     r"""
@@ -42,39 +53,39 @@ class IntegerVectorsModPermutationGroup(UniqueRepresentation):
         v = \max_{\text{lex order}} \{g \cdot v | g \in G \}
 
     The action of `G` is on position. This means for example that the
-    simple transposition `s_1 = (1, 2)` swaps the first and the second entries
-    of any integer vector `v = [a_1, a_2, a_3, \dots , a_n]`
+    simple transposition `s_1 = (1, 2)` swaps the first and the second
+    entries of any integer vector `v = [a_1, a_2, a_3, \dots , a_n]`
 
     .. MATH::
 
         s_1 \cdot v = [a_2, a_1, a_3, \dots , a_n]
 
-    This functions returns a parent which contains a single integer
-    vector by orbit under the action of the permutation group `G`. The
-    approach chosen here is to keep the maximal integer vector for the
-    lexicographic order in each orbit. Such maximal vector will be
-    called canonical integer vector under the action of the
-    permutation group `G`.
+    This function returns a parent which contains, from each orbit
+    orbit under the action of the permutation group `G`, a single
+    canonical vector.  The canonical vector is the one that is maximal
+    within the orbit according to lexicographic order.
 
     INPUT:
 
     - ``G`` - a permutation group
     - ``sum`` - (default: None) - a nonnegative integer
     - ``max_part`` - (default: None) - a nonnegative integer setting the
-      maximum of entries of elements
+      maximum value for every element
     - ``sgs`` - (default: None) - a strong generating system of the
       group `G`. If you do not provide it, it will be calculated at the
       creation of the parent
 
     OUTPUT:
 
-    - If ``sum`` and ``max_part`` are None, it returns the infinite enumerated
-      set of all integer vectors (list of integers) maximal in their orbit for
-      the lexicographic order.
+    - If ``sum`` and ``max_part`` are None, it returns the infinite
+      enumerated set of all integer vectors (lists of integers) maximal
+      in their orbit for the lexicographic order.  Exceptionally, if
+      the domain of ``G`` is empty, the result is a finite enumerated
+      set that contains one element, namely the empty vector.
 
-    - If ``sum`` is an integer, it returns a finite enumerated set containing
-      all integer vectors maximal in their orbit for the lexicographic order
-      and whose entries sum to ``sum``.
+    - If ``sum`` is an integer, it returns a finite enumerated set
+      containing all integer vectors maximal in their orbit for the
+      lexicographic order and whose entries sum to ``sum``.
 
     EXAMPLES:
 
@@ -105,7 +116,7 @@ class IntegerVectorsModPermutationGroup(UniqueRepresentation):
 
     The method
     :meth:`~sage.combinat.integer_vectors_mod_permgroup.IntegerVectorsModPermutationGroup_All.is_canonical`
-    tests if any integer vector is maximal in its orbit. This method
+    tests if an integer vector is maximal in its orbit. This method
     is also used in the containment test::
 
         sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]))
@@ -124,7 +135,7 @@ class IntegerVectorsModPermutationGroup(UniqueRepresentation):
         sage: I.is_canonical('bla')
         Traceback (most recent call last):
         ...
-        AssertionError: bla should be a list or a integer vector
+        AssertionError: bla should be a list or an integer vector
 
     If you give a value to the extra argument ``sum``, the set returned
     will be a finite set containing only canonical vectors whose entries
@@ -153,10 +164,32 @@ class IntegerVectorsModPermutationGroup(UniqueRepresentation):
         sage: I.orbit([2,2,2])
         {[2, 2, 2]}
 
+    Even without constraints, for an empty domain the result is
+    a singleton set::
+
+        sage: G = PermutationGroup([], domain=[])
+        sage: sgs = tuple(tuple(s) for s in G.strong_generating_system())
+        sage: list(IntegerVectorsModPermutationGroup(G, sgs=sgs))
+        [[]]
+
+
+    .. WARNING::
+
+        Because of :issue:`36527`, permutation groups that have
+        different domains but similar generators can be erroneously
+        treated as the same group.  This will silently produce
+        erroneous results.  To avoid this issue, compute a strong
+        generating system for the group as::
+
+            sgs = tuple(tuple(s) for s in G.strong_generating_system())
+
+        and provide it as the optional ``sgs`` argument to the
+        constructor.
+
     TESTS:
 
     Let us check that canonical integer vectors of the symmetric group
-    are just sorted list of integers::
+    are just nonincreasing lists of integers::
 
         sage: I = IntegerVectorsModPermutationGroup(SymmetricGroup(5))  # long time
         sage: p = iter(I)                                               # long time
@@ -164,9 +197,9 @@ class IntegerVectorsModPermutationGroup(UniqueRepresentation):
         ....:     v = list(next(p))
         ....:     assert sorted(v, reverse=True) == v
 
-    We now check that there is as much of canonical vectors under the
-    symmetric group `S_n` whose entries sum to `d` than partitions of
-    `d` of at most `n` parts::
+    We now check that there are as many canonical vectors under the
+    symmetric group `S_n` whose entries sum to `d` as there are
+    partitions of `d` of at most `n` parts::
 
         sage: I = IntegerVectorsModPermutationGroup(SymmetricGroup(5))  # long time
         sage: for i in range(10):                                       # long time
@@ -185,15 +218,16 @@ class IntegerVectorsModPermutationGroup(UniqueRepresentation):
         18
         23
 
-    We present a last corner case: trivial groups. For the trivial
-    group ``G`` acting on a list of length `n`, all integer vectors of
-    length `n` are canonical::
+    Another corner case is trivial groups. For the trivial group ``G``
+    acting on a list of length `n`, all integer vectors of length `n`
+    are canonical::
 
         sage: # long time
         sage: G = PermutationGroup([[(6,)]])
         sage: G.cardinality()
         1
-        sage: I = IntegerVectorsModPermutationGroup(G)
+        sage: sgs = tuple(tuple(s) for s in G.strong_generating_system())
+        sage: I = IntegerVectorsModPermutationGroup(G, sgs=sgs)
         sage: for i in range(10):
         ....:     d1 = I.subset(i).cardinality()
         ....:     d2 = IntegerVectors(i,6).cardinality()
@@ -209,6 +243,7 @@ class IntegerVectorsModPermutationGroup(UniqueRepresentation):
         792
         1287
         2002
+
     """
     @staticmethod
     def __classcall__(cls, G, sum=None, max_part=None, sgs=None):
@@ -225,13 +260,22 @@ def __classcall__(cls, G, sum=None, max_part=None, sgs=None):
             sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3)]]), 8, max_part=5)
         """
         if sum is None and max_part is None:
-            return IntegerVectorsModPermutationGroup_All(G, sgs=sgs)
+            # No constraints.
+            if G.domain():
+                # Nonempty domain, infinite set.
+                return IntegerVectorsModPermutationGroup_All(G, sgs=sgs)
+            else:
+                # Empty domain, singleton set.
+                return IntegerVectorsModPermutationGroup_with_constraints(
+                    G, 0, max_part=-1, sgs=sgs)
         else:
+            # Some constraints, either sum or max_part or both.
             if sum is not None:
                 assert sum == NN(sum)
             if max_part is not None:
                 assert max_part == NN(max_part)
-            return IntegerVectorsModPermutationGroup_with_constraints(G, sum, max_part, sgs=sgs)
+            return IntegerVectorsModPermutationGroup_with_constraints(
+                G, sum, max_part, sgs=sgs)
 
 
 class IntegerVectorsModPermutationGroup_All(UniqueRepresentation, RecursivelyEnumeratedSet_forest):
@@ -435,7 +479,7 @@ def is_canonical(self, v, check=True):
             False
         """
         if check:
-            assert isinstance(v, (ClonableIntArray, list)), '%s should be a list or a integer vector' % v
+            assert isinstance(v, (ClonableIntArray, list)), '%s should be a list or an integer vector' % v
             assert (self.n == len(v)), '%s should be of length %s' % (v, self.n)
             for p in v:
                 assert (p == NN(p)), 'Elements of %s should be integers' % v
@@ -634,17 +678,27 @@ def _repr_(self):
             sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), 6); S
             Integer vectors of length 4 and of sum 6 enumerated up to the action of Permutation Group with generators [(1,2,3,4)]
             sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), 6, max_part=4); S
-            Vectors of length 4 and of sum 6 whose entries is in {0, ..., 4} enumerated up to the action of Permutation Group with generators [(1,2,3,4)]
+            Vectors of length 4 and of sum 6 whose entries are in {0, ..., 4} enumerated up to the action of Permutation Group with generators [(1,2,3,4)]
             sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), max_part=4); S
-            Integer vectors of length 4 whose entries is in {0, ..., 4} enumerated up to the action of Permutation Group with generators [(1,2,3,4)]
+            Integer vectors of length 4 whose entries are in {0, ..., 4} enumerated up to the action of Permutation Group with generators [(1,2,3,4)]
         """
         if self._sum is not None:
             if self._max_part >= 0:
-                return "Vectors of length %s and of sum %s whose entries is in {0, ..., %s} enumerated up to the action of %s" % (self.n, self._sum, self._max_part, self.permutation_group())
+                return ("Vectors of length %s and of sum %s"
+                        " whose entries are in {0, ..., %s}"
+                        " enumerated up to the action of %s"
+                        % (self.n, self._sum, self._max_part,
+                           self.permutation_group()))
             else:
-                return "Integer vectors of length %s and of sum %s enumerated up to the action of %s" % (self.n, self._sum, self.permutation_group())
+                return ("Integer vectors of length %s"
+                        " and of sum %s"
+                        " enumerated up to the action of %s"
+                        % (self.n, self._sum, self.permutation_group()))
         else:
-            return "Integer vectors of length %s whose entries is in {0, ..., %s} enumerated up to the action of %s" % (self.n, self._max_part, self.permutation_group())
+            return ("Integer vectors of length %s"
+                    " whose entries are in {0, ..., %s}"
+                    " enumerated up to the action of %s"
+                    % (self.n, self._max_part, self.permutation_group()))
 
     def roots(self):
         r"""
@@ -751,6 +805,7 @@ def __iter__(self):
             [2, 0, 2, 0]
             [2, 0, 1, 1]
             [1, 1, 1, 1]
+
             sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), sum=7, max_part=3)
             sage: for i in I: i
             [3, 3, 1, 0]
@@ -763,18 +818,197 @@ def __iter__(self):
             [3, 1, 1, 2]
             [3, 0, 2, 2]
             [2, 2, 2, 1]
+
+        Check that :issue:`36681` is fixed::
+
+            sage: G = PermutationGroup([], domain=[])
+            sage: I = IntegerVectorsModPermutationGroup(G, sum=0)
+            sage: list(iter(I))
+            [[]]
+
+        Check that :issue:`36681` is fixed::
+
+            sage: G = PermutationGroup([], domain=[])
+            sage: I = IntegerVectorsModPermutationGroup(G, sum=3)
+            sage: list(iter(I))
+            []
+
         """
+        # Special cases when domain is empty.
+        if self.n == 0:
+            if self._sum is not None and self._sum > 0:
+                # No empty vector can have positive sum.
+                return iter(())
+            else:
+                # Sum is allowed to be zero.  It does not matter what
+                # the maxpart is, the empty vector is a solution.
+                return iter([self([])])
+
+        # General case, nonempty domain.
         if self._max_part < 0:
             return self.elements_of_depth_iterator(self._sum)
         else:
-            SF = RecursivelyEnumeratedSet_forest((self([0]*(self.n), check=False),),
-                              lambda x : [self(y, check=False) for y in canonical_children(self._sgs, x, self._max_part)],
-                              algorithm='breadth')
+            SF = RecursivelyEnumeratedSet_forest(
+                (self([0]*(self.n), check=False),),
+                lambda x: [self(y, check=False)
+                           for y in canonical_children(
+                                   self._sgs, x, self._max_part)],
+                algorithm='breadth')
             if self._sum is None:
                 return iter(SF)
             else:
                 return SF.elements_of_depth_iterator(self._sum)
 
+    def cardinality(self):
+        r"""
+        Return the number of integer vectors in the set.
+
+        The algorithm utilises :wikipedia:`Cycle Index Theorem <Cycle_index>`, allowing
+        for a faster than a plain enumeration computation.
+
+        EXAMPLES:
+
+        With a trivial group all vectors are canonical::
+
+            sage: G = PermutationGroup([], domain=[1,2,3])
+            sage: IntegerVectorsModPermutationGroup(G, 5).cardinality()
+            21
+            sage: IntegerVectors(5, 3).cardinality()
+            21
+
+        With two interchangeable elements, the smaller one
+        ranges from zero to ``sum//2``::
+
+            sage: G = PermutationGroup([(1,2)])
+            sage: IntegerVectorsModPermutationGroup(G, 1000).cardinality()
+            501
+
+        Binary vectors up to full symmetry are first some ones and
+        then some zeros::
+
+            sage: G = SymmetricGroup(10)
+            sage: I = IntegerVectorsModPermutationGroup(G, max_part=1)
+            sage: I.cardinality()
+            11
+
+        Binary vectors of constant weight, up to PGL(2,17), which
+        is 3-transitive, but not 4-transitive::
+
+            sage: G=PGL(2,17)
+            sage: I = IntegerVectorsModPermutationGroup(G, sum=3, max_part=1)
+            sage: I.cardinality()
+            1
+            sage: I = IntegerVectorsModPermutationGroup(G, sum=4, max_part=1)
+            sage: I.cardinality()
+            3
+
+        TESTS:
+
+        Check that :issue:`36681` is fixed::
+
+            sage: G = PermutationGroup([], domain=[])
+            sage: sgs = tuple(tuple(t) for t in G.strong_generating_system())
+            sage: V = IntegerVectorsModPermutationGroup(G, sum=1, sgs=sgs)
+            sage: V.cardinality()
+            0
+
+        The case when both ``sum`` and ``max_part`` are specified::
+
+            sage: G = PermutationGroup([(1,2,3)])
+            sage: I = IntegerVectorsModPermutationGroup(G, sum=10, max_part=5)
+            sage: I.cardinality()
+            7
+
+        All permutation groups of degree 4::
+
+            sage: for G in SymmetricGroup(4).subgroups():
+            ....:     sgs = tuple(tuple(t) for t in G.strong_generating_system())
+            ....:     I1 = IntegerVectorsModPermutationGroup(G, sum=10, sgs=sgs)
+            ....:     assert I1.cardinality() == len(list(I1))
+            ....:     I2 = IntegerVectorsModPermutationGroup(G, max_part=3, sgs=sgs)
+            ....:     assert I2.cardinality() == len(list(I2))
+            ....:     I3 = IntegerVectorsModPermutationGroup(G, sum=10, max_part=3, sgs=sgs)
+            ....:     assert I3.cardinality() == len(list(I3))
+
+        Symmetric group with sums 0 and 1::
+
+            sage: S10 = SymmetricGroup(10)
+            sage: IntegerVectorsModPermutationGroup(S10, 0).cardinality()
+            1
+            sage: IntegerVectorsModPermutationGroup(S10, 1).cardinality()
+            1
+
+        Trivial group with sums 1 and 100::
+
+            sage: T10 = PermutationGroup([], domain=range(1, 11))
+            sage: IntegerVectorsModPermutationGroup(T10, 1).cardinality()
+            10
+            sage: IntegerVectorsModPermutationGroup(T10, 100).cardinality()
+            4263421511271
+
+        """
+        G = self._permgroup
+        k = G.degree()          # Vector length
+        d = self._sum           # Required sum
+        m = self._max_part      # Max of one entry, -1 for no limit
+        if m == -1:
+            m = d               # Any entry cannot exceed total
+
+        # Some easy special cases.
+        if k == 0:
+            # Empty vectors.  There is only one, and it has zero sum.
+            # Here _max_part does not matter because any _max_part
+            # condition is vacuously true (with no parts).
+            if d == 0 or d is None:
+                return Integer(1)
+            else:
+                return Integer(0)
+        if d == 0 or m == 0:
+            # All-zero vectors.  There is only one of them.
+            return Integer(1)
+        if d == 1:
+            # Vectors with one 1 and all other elements zero.
+            # The 1 can be placed in any orbit, and by symmetry
+            # it will be on the first element of the orbit.
+            return Integer(len(G.orbits()))
+        if d is not None and m >= d and G.is_trivial():
+            # Simple calculation with stars and bars.
+            return Integer(binomial(d + k - 1, k - 1))
+
+        # General case.
+        #
+        # Cardinality is computed using the Cycle Index Theorem.  We
+        # have two cases.  With a fixed sum d we work with power
+        # series and extract the x^d coefficient.  Without a fixed sum
+        # we can do with integer arithmetic.
+        Z = G.cycle_index()
+
+        if d is None:
+            # Case 1.  Without a fixed sum, the sum can be up to k*m.
+            result = sum(coeff * (m+1)**len(cycle_type)
+                         for cycle_type, coeff in Z)
+            # Computed as Rational, but should have an integer value
+            # by now.
+            return Integer(result)
+
+        # Case 2.  Fixed sum d.  Work with power series with enough
+        # precision that x^d is valid.
+        R = PowerSeriesRing(QQ, 'x', default_prec=d+1)
+        x = R.gen()
+
+        # The figure-counting series, for max_part==m, is (1-t**(m+1))
+        # / (1-t) = 1+t+...+t**m.  For the function-counting series,
+        # we substitute x**cycle_length for t.
+        #
+        funcount = sum(
+            coeff * prod((1 - x**((m+1)*cycle_len)) / (1 - x**cycle_len)
+                         for cycle_len in cycle_type)
+            for cycle_type, coeff in Z)
+
+        # Extract the d'th degree coefficient.  Computed as Rational,
+        # but should have an integer value by now.
+        return Integer(funcount[d])
+
     def is_canonical(self, v, check=True):
         r"""
         Return ``True`` if the integer list ``v`` is maximal in its
@@ -798,7 +1032,7 @@ def is_canonical(self, v, check=True):
             True
         """
         if check:
-            assert isinstance(v, (ClonableIntArray, list)), '%s should be a list or a integer vector' % v
+            assert isinstance(v, (ClonableIntArray, list)), '%s should be a list or an integer vector' % v
             assert (self.n == len(v)), '%s should be of length %s' % (v, self.n)
             for p in v:
                 assert (p == NN(p)), 'Elements of %s should be integers' % v
@@ -980,7 +1214,7 @@ class Element(ClonableIntArray):
             sage: v = I.element_class(I, [3,2,0,0])
             Traceback (most recent call last):
             ...
-            AssertionError: [3, 2, 0, 0] should be a integer vector of sum 4
+            AssertionError: [3, 2, 0, 0] should be an integer vector of sum 4
         """
 
         def check(self):
@@ -1000,7 +1234,7 @@ def check(self):
                 AssertionError
             """
             if self.parent()._sum is not None:
-                assert sum(self) == self.parent()._sum, '%s should be a integer vector of sum %s' % (self, self.parent()._sum)
+                assert sum(self) == self.parent()._sum, '%s should be an integer vector of sum %s' % (self, self.parent()._sum)
             if self.parent()._max_part >= 0:
                 assert max(self) <= self.parent()._max_part, 'Entries of %s must be inferior to %s' % (self, self.parent()._max_part)
             assert self.parent().is_canonical(self)
diff --git a/src/sage/groups/group.pyx b/src/sage/groups/group.pyx
index cd2521e3478..0ac243f8364 100644
--- a/src/sage/groups/group.pyx
+++ b/src/sage/groups/group.pyx
@@ -186,6 +186,39 @@ cdef class Group(Parent):
         """
         return self.order() != infinity
 
+    def is_trivial(self):
+        r"""
+        Return ``True`` if this group is the trivial group.
+
+        A group is trivial, if it consists only of the identity
+        element.
+
+        .. WARNING::
+
+            It is in principle undecidable whether a group is
+            trivial, for example, if the group is given by a finite
+            presentation.  Thus, this method may not terminate.
+
+        EXAMPLES::
+
+            sage: groups.presentation.Cyclic(1).is_trivial()
+            True
+
+            sage: G.<a,b> = FreeGroup('a, b')
+            sage: H = G / (a^2, b^3, a*b*~a*~b)
+            sage: H.is_trivial()
+            False
+
+        A non-trivial presentation of the trivial group::
+
+            sage: F.<a,b> = FreeGroup()
+            sage: J = F / ((~a)*b*a*(~b)^2, (~b)*a*b*(~a)^2)
+            sage: J.is_trivial()
+            True
+        """
+        return self.order() == 1
+
+
     def is_multiplicative(self):
         r"""
         Returns True if the group operation is given by \* (rather than
diff --git a/src/sage/groups/matrix_gps/matrix_group.py b/src/sage/groups/matrix_gps/matrix_group.py
index c0c22456320..eeb96fc5445 100644
--- a/src/sage/groups/matrix_gps/matrix_group.py
+++ b/src/sage/groups/matrix_gps/matrix_group.py
@@ -542,3 +542,34 @@ def __richcmp__(self, other, op):
             if lx != rx:
                 return richcmp_not_equal(lx, rx, op)
         return rich_to_bool(op, 0)
+
+    def is_trivial(self):
+        r"""
+        Return ``True`` if this group is the trivial group.
+
+        A group is trivial, if it consists only of the identity
+        element, that is, if all its generators are the identity.
+
+        EXAMPLES::
+
+            sage: MatrixGroup([identity_matrix(3)]).is_trivial()
+            True
+            sage: SL(2, ZZ).is_trivial()
+            False
+            sage: CoxeterGroup(['B',3], implementation="matrix").is_trivial()
+            False
+
+        TESTS::
+
+            sage: CoxeterGroup(['A',0], implementation="matrix").is_trivial()
+            True
+            sage: MatrixGroup([matrix(SR, [[1,x], [0,1]])]).is_trivial()
+            False
+            sage: G = MatrixGroup([identity_matrix(3), identity_matrix(3)])
+            sage: G.ngens()
+            2
+            sage: G.is_trivial()
+            True
+
+        """
+        return all(g.is_one() for g in self.gens())
diff --git a/src/sage/groups/perm_gps/permgroup.py b/src/sage/groups/perm_gps/permgroup.py
index 8e2e6d82c10..12e22246d8c 100644
--- a/src/sage/groups/perm_gps/permgroup.py
+++ b/src/sage/groups/perm_gps/permgroup.py
@@ -1365,6 +1365,38 @@ def ngens(self):
         """
         return len(self.gens())
 
+    def is_trivial(self):
+        r"""
+        Return ``True`` if this group is the trivial group.
+
+        A permutation group is trivial, if it consists only of the
+        identity element, that is, if it has no generators or only
+        trivial generators.
+
+        EXAMPLES::
+
+            sage: G = PermutationGroup([], domain=["a", "b", "c"])
+            sage: G.is_trivial()
+            True
+            sage: SymmetricGroup(0).is_trivial()
+            True
+            sage: SymmetricGroup(1).is_trivial()
+            True
+            sage: SymmetricGroup(2).is_trivial()
+            False
+            sage: DihedralGroup(1).is_trivial()
+            False
+
+        TESTS::
+
+            sage: G = PermutationGroup([[], []], canonicalize=False)
+            sage: G.ngens()
+            2
+            sage: G.is_trivial()
+            True
+        """
+        return all(g.is_one() for g in self._gens)
+
     @cached_method
     def one(self):
         """