For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

17
votes
4answers
2k views

Have I found all the numbers less than 50,000 with exactly 11 divisors?

The math problem I am trying to solve is to find all positive integers that meet these two conditions: have exactly 11 divisors are less than 50,000 My starting point is a number with exactly 11 ...
7
votes
1answer
38 views

The size of sets of positive integers not having distinct subsets with equal size and sum

Let us call a set $S$ of positive integers "good" if there does not exist a pair of distinct subsets $A,B\subseteq S$ who have equal size and an equal sum. Equivalently, a set $S$ is good if the ...
2
votes
1answer
33 views

How to find that a number is a sum of multiple of different numbers?

Suppose a product comes in packs of 3, and 5, and a customer demands 8 quantities of that ...
3
votes
0answers
44 views

example of toric varieties with nontrivial first cohomology group

If I remember correctly, when a toric variety is smooth or simplical (the moment polytope is simplicial rational), then there is no odd dimensional cohomology group and the dimension of the even ...
3
votes
4answers
174 views

How to prove: $\sum_{k=m+1}^{n} (-1)^{k} \binom{n}{k}\binom{k-1}{m}= (-1)^{m+1}$

Show that if $m$ and $n$ are integers with $0\leq m<n$ then $$\sum_{k=m+1}^{n} (-1)^{k} \binom{n}{k}\binom{k-1}{m}= (-1)^{m+1}$$ Attempts: $(-1)^{k}\binom{n}{k}$ is the coefficient of $x^{k}$ in ...
1
vote
2answers
45 views

Probability problem with a die

I've been practicing probability problems lately and I came to this problem A number is formed in the following way. You throw a six-sided die until you get a 6 or until you have thrown it three ...
1
vote
1answer
39 views

How many ways are there to pick k cards in a game of Skat?

In a game of Skat there are 4 suits (spades, hearts, diamonds, clubs) and 8 values (7, 8, 9, 10, jack, queen, king, ace) yielding 32 cards altogether. I'm trying to figure out in how many ways $k \geq ...
0
votes
3answers
53 views

N is a four digit number. If the leftmost digit is removed, the resulting three digit number is 1/9th of N. How many such N are possible? [closed]

N is a four digit number. If the leftmost digit is removed, the resulting three digit number is 1/9th of N. How many such N are possible with solution?
0
votes
2answers
28 views

Probabilities in infinite Bernoulli type of series

While I was trying to solve the 1st problem from here I run into the following problem: find the probability of the events such as $1122213$ or $2122111116$ in infinite series of dice rolls which end ...
3
votes
1answer
67 views

Problem 48 in A First Course in Probability

I have an issue with problem 48 Chapter 2, page 51 in Sheldon Ross' A First Course in Probability (9th edition). The problem is as follows, Given 20 people, what is the probability that among the 12 ...
9
votes
1answer
106 views

Prove that $\dfrac{b^{n-1}a(a+b)(a+2b)\cdots(a+(n-1)b)}{n!}$ is an integer

Let $a$ and $b$ be integers and $n$ a positive integer. Prove that $$\dfrac{b^{n-1}a(a+b)(a+2b)\cdots(a+(n-1)b)}{n!}$$ is an integer. Define $v_p(x)$ such that if $v_p(x) = n$, then $p^n \mid x$ but ...
2
votes
1answer
23 views

Transposal generators like {1, 1, 2, 3, 3, 2}

The sequence {1, 1, 2, 3, 3, 2} generates all the transposals of {1,2,3}. Just cyclically pick positions $n, n+2, n+4$. Is there a sequence like this for 1-4, 1-5, and so on?
0
votes
1answer
35 views

Permutation: Number of ways 4 cars could park

I came across this question in my Algebra textbook: Find the number of ways 4 cars could park right next to each other if the parking slots were: a) in a straight row b) in a circular ...
0
votes
2answers
31 views

How many ways can numbers be split into different groups

If I had the numbers [2,2,2,2,3,3] and I wanted to find the number of ways to split them into two groups, then how would I do it. I know that if I had all different numbers eg.[1,2,3,4,5,6] then I ...
2
votes
2answers
57 views

Number of $k\times n$ matrices of rank $k$

How can I determine the number of $k\times n$ matrices with entries in $\mathbb F_p$ with rank $k$ (of course $k<n$) The formula if $k=n$ is $(p^n-1)(p^n-p)\dots(p^n-p^{n-1})$, now how can I ...
0
votes
2answers
70 views

Four people are rolling a die once. What is the probability of $2$ people getting the same number?

I am doing as following- $1^{st}$ people get a number from any $6$ number in $6$ ways, $2^{nd}$ people get a different number from rest of $5$ in $5$ ways, $3^{rd}$ people get another different ...
2
votes
1answer
53 views

How many different 4 letter words can be selected from the word ADVANCED?

My attempt : $A-2 , D -2 , V - 1, N -1 , C -1 , E -1 $ $XXXX$ words $=0 $ $XXXY$ words $=0 $ $XXYY$ words $= \binom{2}{2}\times \frac{4!}{2!2!} = 6$ $XXYZ$ words $= \binom{2}{1}\times \binom{5}{...
0
votes
1answer
27 views

Unique integer solutions to $\sum\limits_{i=1}^n a_i = A$ when $l \leq a \leq u$ and $a,A,l,u \in \mathbb{N}$

I'm trying to find a analytical way for finding the total amount of unique solutions to equation: $$\sum\limits_{i=1}^n a_i = A, \text{when } l \leq a \leq u,$$ where $a,A,l,u \in \mathbb{N}$. For ...
3
votes
1answer
52 views

Sets of integers with few sums

Let $S$ be a finite set of integers. Denote by $S^{\leq k}$ the set $\{a_1+\dots+a_\ell : \ell\leq k, a_1,\dots,a_\ell\in S\}$ of sums of at most $k$ elements from $S$. What are best/worst cases for ...
4
votes
2answers
84 views

How many integers $\leq N$ are divisible by $2,3$ but not divisible by their powers?

How many integers in the range $\leq N$ are divisible by both $2$ and $3$ but are not divisible by whole powers $>1$ of $2$ and $3$ i.e. not divisible by $2^2,3^2, 2^3,3^3, \ldots ?$ I hope by ...
2
votes
0answers
40 views

Finding only the number of unlabeled graphs on $n$ vertices

I know that it is possible to find the number of unlabelled graphs on $n$ vertices using Polya's theorem, but you get a horrible sum. This also tells you much more: it gives you the number of ...
3
votes
1answer
49 views

Is there symbol to denote a combination and permutation?

For example, let's say I wanted to denote any arbitrary, $2$ number combination of the letters, A, B and C. So you can have AB, AC, and BC. Say you wanted a way to represent any given combination, is ...
1
vote
1answer
56 views

Combinatorial question relating to zero sets of ideals

Let $R$ be a ring and $I$ an ideal of $R[x_1,\ldots,x_n]$. Then define the Zariski closed set $$V=\{x\in R^n:f(x)=0\text{ for all }f\in I\}.$$ I'm interested in the quantity $$p(f)=\frac{|\{x\in V:f(x)...
1
vote
0answers
39 views

Maximal chains in posets under homomorphisms

Suppose that $P$ and $Q$ are two posets and $f:P\to Q$ is a homomorphism (a.k.a., $f(x)\le f(y)$ whenever $x\le y$). Given a chain $C\subset P$, the image $f(C)$ automatically is a chain as well. ...
0
votes
0answers
24 views

Plaid in generic position. Counting faces.

I write $\pi_n$ to denote a group of $n$ parallel lines. Consider a family of $(\pi_1,\pi_2,\ldots,\pi_s)$ parallel groups each with $(n_1,n_2,\ldots,n_s)$ parallel lines. Arrange the family of ...
0
votes
1answer
47 views

Method of integration [duplicate]

We have to find the integration of the following function I tried but got stuck can anybody help me how to proceed . Is there anyother method to solve this
1
vote
0answers
39 views

Optimization Algorithm for Combining Nodes on a Graph

Graph before and after clustering nodes $R_1$ and $R_2$ In the picture linked above, I have a graph with nodes $R_1$ through $R_5$ and vertices linking them. All the vertices are weighted 10 in this ...
0
votes
1answer
26 views

Counting solutions by estimating Fourier coefficients

In W. T. Gower's essay The Two Cultures of Mathematics, he mentions the following as an example of a 'general principle' in combinatorics: "If one is counting solutions, inside a given set, to a ...
4
votes
2answers
63 views

How many distinct ways are there to $2$-color the $8$ vertices of a cube?

How many distinct ways are there to $2$-color the $8$ vertices of a cube, with colorings only considered distinct up to rotation?
2
votes
0answers
51 views

lower bound for sum of distinct n-th roots of unity

Given a positive integer $n$, define $\zeta = e^{2\pi i/n}$ and define $s: \mathbb Z^n \to \mathbb C$$$s(\vec x) = \sum_{k=0}^{n-1} x_k \zeta^k$$ Let us consider the set $S = \{ |s(\vec x)| : \vec x \...
1
vote
4answers
84 views

Closed form of recurrence relation $F(n) = 2 + F(n-1) + F(n-2)$

I was figuring out an answer to the question, How many Boolean arrays of length $n$ could be formed if there are to be no two falses in a row? I could see that it boils down to a Fibonacci ...
0
votes
0answers
31 views

Applications of tensor product of graphs (modelling of Internet Graphs)

I was going through the book Handbook of Product Graphs, by Richard Hammack, Wilfried Imrich, Sandi Klavžar. Somewhere in book, they mentioned the following lines : One of the applications of tensor ...
0
votes
1answer
22 views

Can any simple graph be “super edge labeled”?

Let $X=(V(X),E(X))$ be a simple graph with $|V(X)|=n$ and $|E(X)|=m$. Let $$f:V(X) \bigcup E(X)\rightarrow \{1,2,3,\ldots ,n+m\}$$ be a bijection, such that for all $x,y \in V(X)$ and $\{x,y\} \in E(X)...
-3
votes
1answer
22 views

How many possible combinations can be made of two characters from $62$ characters?

I want to make combinations to create an encryption system. Can you please tell me how to calculate how many possible combinations can be made of two characters from $62$ characters. Characters are A-...
2
votes
0answers
34 views

Minimum least common multiplier for variable combinations

I looking to find the minimum possible value of the LCM of a variable set of integers. My hypotheses are the following: I have a set $N$ of $n$ integers, all different. My integers are bounded by $...
-1
votes
2answers
52 views

find the number of permutations of the letters of the word ANTENNA taken 4 at a time? [closed]

I understand how to get the permutation of the word itself, but what does the "taken 4 at a time" mean?
0
votes
1answer
26 views

determine the number of poker hands that are better than 2 Aces, 2 Eights, and a 5?

I am not very familiar with the game of poker so I have no clue where to begin answering this question. it is along the lines of using combinations to solve though.
0
votes
1answer
23 views

excecutives from 25 student clubs, one male and one female…

excecutives from 25 student clubs, one male and one female from each are attending a workshop on student violence. how many ways can a commitee be set up of 5 men and 7 women if only one male or ...
2
votes
2answers
87 views

Probability with biased coin problem

Jules César gives Astérix a biased coin which produces heads 70% of the time, and asks him to play one of the following games: Game A : Toss the biased coin 99 times. If there are more than 49 heads, ...
0
votes
1answer
27 views

In how many ways can 10 different things be distributed to 4 persons if 2 are to receive 2 things and the others are to receive 3 things?

I have no idea how to answer this question, I did a lot of research on trying to figure it out but every answer is so different. I would prefer something along the lines of using combinations and ...
3
votes
0answers
64 views

Counting number of bases in a set of vectors with spanning constraint

I am interested in a good bound for the following problem: Suppose $S = \{ v_1, \dots, v_n \}$ is a set of vectors where $v_i \in \mathbb{R}^r$ for $i = 1, \dots, n$. Suppose further that any ...
2
votes
2answers
67 views

What is the rank of COCHIN

Is there any shortcut method for finding the rank of the word COCHIN? I mean is there any shortcut method for finding the rank of a word having repeated letters. For example there is a shortcut method ...
2
votes
2answers
68 views

every tree $T$ has at most one perfect matching, alternative proof

I have two questions: I need to know if the following approach (by induction) is correct. The ones I saw use induction on the components of $T$ with a leaf removed, I did something a little different....
3
votes
3answers
140 views

Coefficient of $x^{41}$ in $(x^5 + x^6 + x^7 + x^8 + x^9)^5$

What is the coefficient of coefficient of $x^{41}$ in $(x^5 + x^6 + x^7 + x^8 + x^9)^5$? Using summation of G.P., this is equivalent to finding the coefficient of $x^{41}$ in $$\left(x^5 \left(\...
0
votes
1answer
11 views

achievability of average

Out of a textbook. Informally, the goal is to show that if from a given set of values ($2^n$ many values) in the range of $[0,m]$ (for fixed $m,k$), more than half are less than $m\cdot (1-\frac{1}{2^...
6
votes
2answers
169 views

Fun with combinatorics and 80 business customers

In business with 80 workers, 7 of them are angry. If the business leader visits and picks 12 randomly, what is the probability of picking 12 where exactly 1 is angry? (7/80)(73/79)(72/78)(71/77)(70/...
4
votes
1answer
34 views

A simple question about the Hamming weight of a square

Let we define the Hamming weight $H(n)$ of $n\in\mathbb{N}^*$ as the number of $1$s in the binary representation of $n$. Two questions: Is it possible that $H(n^2)<H(n)$ ? If so, is there ...
1
vote
2answers
27 views

Number of routes

Suppose there is an ant on the point $(0,0)$ that can move one step right ($(x,y)\mapsto(x+1, y)$), one step up ($(x,y)\mapsto(x, y+1)$) or one step diagnolly ($(x,y)\mapsto(x+1, y+1)$). How many ways ...
1
vote
2answers
47 views

Number of ways to choose 4 groups of 4 people from a set of 16 people

How many ways are there to choose 4 groups of 4 people each from a set of 16 people (the groups are distinct) ? I can't quite decide if the answer should be ${16 \choose 4} + {12 \choose 4} + {8 \...
2
votes
0answers
35 views

Singular Locus of a Schubert variety

I am trying to compute the singular locus of the schubert variety $X_w$ in $G_{2,7}$ where $w=(4,7) \in I_{2,7}$. Following the notation in the book "The Grassmannian Variety: Geometric and ...