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)

4
votes
0answers
28 views

How many integer-sided right triangles are there whose sides are combinations?

How many integer-sided right triangles exist whose sides are combinations of the form $\displaystyle \binom{x}{2},\displaystyle \binom{y}{2},\displaystyle \binom{z}{2}$? Attempt: This seems like ...
1
vote
3answers
67 views

How many numbers between $1$ and $9999$ have sum of their digits equal to $8$? $16$?

How many numbers between $1$ and $9999$ have sum of their digits equal to $8$? $16$? Can someone tell me if I got the right answers? I solved both cases and I've got $148$ for $8$ and $633$ for $16$. ...
0
votes
0answers
5 views

“L-normal” finite strings?

Consider finite strings on a finite alphabet of size $b\ (\ge 2)$. Let's call such a finite string "$L$-normal" just if, for each $l\in\{1,2,...,L\}$, all $b^l$ possible length-$l$ substrings occur in ...
0
votes
0answers
15 views

In how many ways can we select $r$ doughnuts from a box of a dozen doughnuts that has $2$ apple fritters, $3$ sprinkled, $3$ jelly and $4$ glazed?”

In how many ways can we select $r$ doughnuts from a box of a dozen doughnuts that has $2$ apple fritters, $3$ sprinkled, $3$ jelly and $4$ glazed?” For this question, I'm supposed to come up with a ...
8
votes
3answers
185 views

How many sewings are there on a soccer ball?

A soccer ball is obtained by sewing $20$ hexagonal pieces of leather and $12$ pieces of leather of pentagonal shape. A sewing joins together the sides of two adjacent pieces. How many sewings ...
0
votes
3answers
38 views

How many ways to write sum as $k$ restricted integers

If we have $3$ positive integers given as \begin{align*} 0 & \leq a \leq 3\\ 0 & \leq b \leq 3\\ 0 & \leq c \leq 2 \end{align*} and given the sum $$ a+b+c = 5$$ how many ways we can ...
0
votes
3answers
43 views

Number of ways to get 17 by rolling dice 4 times (with combinatorial argument)

A dice is rolled four times. How many we can get total of 17? We can solve this by finding coefficient of $x^{17}$ in the ordinary enumerator $(x+x^2+x^3+x^4+x^5+x^6)^4$. But I feel this requires ...
0
votes
2answers
14 views

How many subsets of $S$ exactly of size $3$ must one have in order to know that at least two of our subsets have same weight?

Let $S$ be a set $\{1,2,3,4,5,6,7,8,9,10\}$. How many subsets of $S$ exactly of size $3$ must one have in order to know that at least two of our subsets have same weight? (= sum of the numbers in the ...
1
vote
2answers
28 views

Total number of $4$ digit numbers whose product of digits is $72$

Total number of $4$ digit numbers whose product of digits is $72$ $\bf{My\; Try::}$ Here the possible factor of $72 = 2^{3}\cdot 3^2$ Now here we divide $2^3\cdot 3^3$ into product of $4$ ...
-1
votes
0answers
26 views

Updating array and counting permutations with some criteria

We have an array $A[n]$, and an integer $D$. $P$ is a permutation of numbers $[1, 2, 3 ,.... ,n]$ $P$ is a valid permutation if $$ A[P_1]+D>A[P_2] $$ $$ A[P_2]+D>A[P_3] $$ $$ .... $$ $$ ...
0
votes
3answers
19 views

The probability that the output of the experiment is Y is ___?

Consider the following experiment. Step 1. Flip a fair coin twice. Step 2. If the outcomes are (TAILS, HEADS) then output Y and stop. Step 3. If the outcomes are either (HEADS, HEADS) or (HEADS, ...
6
votes
4answers
304 views

Finding coefficient of polynomial?

The coefficient of $x^{12}$ in $(x^3 + x^4 + x^5 + x^6 + …)^3$ is_______? Somewhere it explain as: The expression can be re-written as: $(x^3 (1+ x + x^2 + x^3 + …))^3=x^9(1+(x+x^2+x^3))^3$ ...
-3
votes
1answer
54 views

Expected Value of a in a randomly chosen Rectangle

There is a N×M grid. Each square in the grid either has or does not have a mango tree. For example, suppose the field looks as follows. We Know That there are K Mango Tree. ...
0
votes
0answers
23 views

Bounding the summation of binomial terms

For $0<\theta<1, \theta'=(1-\epsilon)\theta, \epsilon< \theta, k\in\mathbb{N}$, the problem is to tightly upper bound the following binomial summation: $$\sum_{i=\lceil \theta k \rceil}^k ...
0
votes
1answer
26 views

Possible ways to have $n$ bounded natural numbers with a fixed sum

Is it possible to count in an easy way the solutions of the equations and inequalities $x_1+x_2+\cdots+x_n = S$ and $x_i\leq c_i$ if all $x_i$ and $c_i$ are natural numbers?
1
vote
2answers
30 views

Representing geometric series as sum of binomial coefficients

I was learning generating functions, where faced following: $$(1-x)^{-n}=\sum_{i=0}^\infty\binom{n+i-1}{i}x^i$$ I didn't get how is this arrived. I tried out to prove this to me. But failed. ...
0
votes
0answers
27 views

How many ways to pile up boxes in a direction

Lets assume that there are columns with spesific limits, and there are boxes on these columns. We need to find all the possible ways(positions) from the original layout to the layout that completely ...
0
votes
1answer
22 views

Let $n = p_1^{k_1} + p_2^{k_2} + … + p_m^{k_m}$ how many ways can $n$ be written as a product of two positive integers

Let $n = p_1^{k_1} + p_2^{k_1} + ... + p_m^{k_m}$ where $p_1, p_2,...,p_m$ are distinct prime numbers and $k_1,k_2,...,k_m$ are positive integers. How many ways can $n$ be written as a product of two ...
4
votes
1answer
63 views

Why does the Möbius function take its values so often in $\{0,+1,-1\}$?

The Möbius function of a locally finite poset $P$ is defined on its intervals $[x,y] \subseteq P$ recursively by $$\mu([x,x])=1$$ $$\forall x < y : \mu([x,y])=-\sum_{x \leq z < y} \mu([x,z])$$ ...
0
votes
0answers
14 views

Finding maximal product of numbers of permutations

Let $n\geq 1$ be a total number of objects that must be taken from $m\geq 1$ sets of objects. For all $i \in \{1,\cdots,m\}, \ M_i \in \mathbb{N}^*$ denotes the number of objects present in the set ...
3
votes
2answers
55 views

How many ways we can choose items from different boxes

I searched through the internet but couldn't find my answer, which can either be a very simple or a hard one. Assume there are $3$ boxes, which carry, respectively, $1$, $4$, $2$ items. My question ...
-2
votes
0answers
49 views

Expected Value of a Mangoes [on hold]

There is a $N \times N$ grid. Each square in the grid either has or does not have a mango tree. For example, suppose the field looks as follows: ...
1
vote
1answer
34 views

Selection of subsets

This is an supplementary exercise from Miklos Bona: A walk through combinatorics. We want to select as many subsets of $[n]=\{1,2,3,..,n\}$ without selecting two subsets such that neither one of them ...
1
vote
4answers
56 views

To prove $\sum_{n=0}^\infty \binom{r}{x}\binom{N-r}{n-x}=\binom{N}{n}.$ [duplicate]

To prove $$\sum_{x=0}^n \binom{r}{x}\cdot \binom{N-r}{n-x}=\binom{N}{n}.$$ I tried comparing the coefficients of $(1+x)^{(n+k)} = (1+x)^n(1+x)^k$ but couldn't reach the answer.
0
votes
3answers
50 views

Number of subsets without objects being adjacent

I have a set of $20$ people who have names. 1) How can I count the different subsets of size $3$, where the people of that subset are not allowed to be next to each other in an (alphabetically) ...
2
votes
1answer
44 views

Find a closed formula for $\sum_{n=1}^\infty nx^{n-1}$ [duplicate]

Find a closed formula for $\sum_{n=1}^\infty nx^{n-1}$ I am trying to use the derivative of generalized binomial theorem, $\frac{d}{dx}[(x+1)^r=\sum_{n=0}^\infty \binom{r}{n}x^n] ...
2
votes
0answers
30 views

Decorating a single flower box with $4$ spaces with $4$ differently colored flowers, so that there is no flower box with more than $1$ yellow flower.

What we are actually talking about Available flowers: Pink, Red, Yellow and Blue ($4$ distinct kinds). Available spots in the flower box: $4$. Restriction: Max. $1$ yellow flower in the flower box. ...
7
votes
3answers
61 views

Prove $\binom{3n}{n,n,n}=\frac{(3n)!}{n!n!n!}$ is always divisible by $6$ when $n$ is an integer.

Prove $$\binom{3n}{n,n,n}=\frac{(3n)!}{n!n!n!}$$ is always divisible by $6$ when $n$ is an integer. I have done a similar proof that $\binom{2n}{n}$ is divisible by $2$ by showing that ...
0
votes
0answers
49 views

Number of integral solutions to $y_1 + y_2 + y_3 + y_4 =30$ with $y_i \ge 2$

How many solutions there are to the given equation that satisfy the given condition: $y_1 + y_2 + y_3 + y_4 =30$, each $y_i$ is an integer that is at least $2$. I don't know how to start this ...
0
votes
1answer
28 views

Suppose that after a five-card hand is drawn, the cards in it are put back in the deck and another five-card hand is drawn.

Suppose that after a five-card hand is drawn, the cards in it are put back in the deck and another five-card hand is drawn. a) What is the probability that the two hands have no card in common? b) ...
0
votes
1answer
20 views

Recurrence for the number of n tuples with restrictions

If $a_{n}$ is the number of $n$ tuples $(b_{1}, b_{2},...b_{n})$ with $b_{i} \in[4]$ that have at least one 1 and have no 2 appearing before the first 1. What is the recurrence for $a_{n}$?
1
vote
1answer
34 views

Finding the no of ways to count the letters in an English alphabet

How many strings of six lower case letters from the English alphabet contain a) the letter $a$? b) the letters $a$ and $b$? c) the letters $a$ and $b$ in consecutive positions with $a$ preceding ...
0
votes
0answers
26 views

Restricted integer composition, where every summand belongs to a different set

Could I get any suggestion on how to calculate the number of restricted integer compositions of a number $n$ with $k$ parts, where every summand belongs has its own subset? \begin{equation} ...
0
votes
1answer
41 views

Is there an equation to find out how after $\frac{6!}{6}$ to locate clockwise increase in numbers in sets of 2

So I asked this question last night what is the max possible combinations of 1 2 3 4 5 6 without repeating And as stated I don't know what symbols mean, but I learned what $!$ is and how it works ...
0
votes
1answer
27 views

Number of Unique Ranks of High Card in Three Card Brag

Well the game is called Teen Patti in India. Almost similar to Three Card Brag a British game. There are total $16440$ Unique High Card hands are present. (Considering the suit.) Hand $1 = 5$ Heart, ...
1
vote
1answer
13 views

Express reverse inversion, major index, descents in terms of the forward direction.

Given $w=a_1a_2...a_n \in S_n $, then the reverse of $w$ is $w^r=a_n....a_2a_1$. Express inv($w^r$), des($w^r$) and maj($w^r$) in terms inv($w$), des($w$), maj($w$), respectively. I know the ...
2
votes
0answers
49 views

upper bounding alternating binomial sums

So we know that $\sum_{i=0}^t\binom{m}{i}\binom{n-m}{t-i}=\binom{n}{t}$ by a simple counting argument. Now is there any bound on the quantity $\sum_{i=0}^t(-1)^i\binom{m}{i}\binom{n-m}{t-i}$? Can we ...
0
votes
1answer
40 views

A box with $3$ types of colored balls.

In a box there are $15$ white balls, $8$ black balls, and $12$ red balls. We extract $6$ balls, without putting them back. $(a)$ What is the probability that the first ball is red, the second and ...
0
votes
1answer
18 views

Morse code symbols represented by sequences of seven or fewer dots and dashes

In Morse code, symbols are represented by variable length sequences of dots and dashes. (For example, A = · −, 1 = · − − − −, and ? = · · − − · ·.) How many different symbols can be represented by ...
1
vote
3answers
55 views

An ice-cream shop sells $11$ kinds of ice-cream, including mango and lemon.

An ice-cream shop sells $11$ kinds of ice-cream, including mango and lemon. For a bowl, one chooses at random five kinds (not necessarily different). $(a)$ How many different bowls can be made? ...
0
votes
1answer
16 views

A finite, undirected, connected and simple graph with Eulerian circuit has $3$ vertices with the same degree

Let $G=(V,E)$ a finite, undirected, connected and simple graph, $|V| \ge 3. \space$ Prove: If $G$ has Eulerian circuit then $G$ has $3$ vertices with the same degree.
3
votes
3answers
48 views

If $n_{1}+n_{2}+n_{3}+n_{4}+n_{5} = 20.$ Then number of such distinct arrangements of $(n_{1},n_{2},n_{3},n_{4},n_{5})$

Let $n_{1}<n_{2}<n_{3}<n_{4}<n_{5}$ be the positive integers such that $n_{1}+n_{2}+n_{3}+n_{4}+n_{5} = 20$ Then number of such distinct arrangements of ...
4
votes
4answers
62 views

How many $3$-tuples $(a, b, c) \in M^3$ are there such $a+b+c$ is even?

The task is the following: $M= \left \{ 1,2, ... 99,100 \right \}$ How many $3$-tuples $(a, b, c) \in M^3$ are there such $a+b+c$ is even? I tried to solve it this way: There are only two ...
1
vote
1answer
97 views
+50

What is so special about Higman's Lemma?

Is there a motivational example of an application of Higman's Lemma that brings out the true beauty and importance of Higman's Lemma? What is the thing that made so many people care about it? For an ...
0
votes
1answer
49 views

When is the order important in Combinatorics?

In a shop five different type of chocolates are sold. How many different ways 6 chocolate bars can be chosen in such a way that at least 3 chocolate bars must be of type one and at most one of type ...
0
votes
0answers
35 views

Here is a question on combinatorics [on hold]

here are ten items on sale at a bazaar, each costing less than one dollar. Prove that it is possible for two people to purchase distinct subsets of these objects and pay exactly the same amount. (Not ...
0
votes
0answers
11 views

Bounding entries of random vector

Given a random vector $\mathbf{e} \in \mathbb{R}^n$, is it possible to count (or bound) the number of entries in $\mathbf{e}$ that have $|e_i| \ge 1/ \sqrt{n}$? It is known that entries in ...
1
vote
1answer
109 views

Covering board with pieces

Suppose we have board, of size (16x16) And 31 (1x4) + 33 (2x2) pieces. Is it possible to cover up board with those pieces, if so - how? If not - why? So far I was unable to think of anything ...
6
votes
0answers
27 views

Chromatic Number of Circulant Graph

Consider the Circulant Graph $Ci_{2n}(1,n-1,n)$ as described here: http://mathworld.wolfram.com/MusicalGraph.html Another way to describe $Ci_{2n}(1,n-1,n)$ would be $2n$ vertices with vertex set ...
1
vote
2answers
38 views

$6$ real numbers, sum of any $3$ consecutive is negative, while sum of any $4$ consecutive is positive. Prove false. [on hold]

It's from my combinatorics class, could anyone give me some hints? Thanks Sorry, I shortened the original phrasing of the question, which made it ambiguous here. The question goes: A computer ...