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)

0
votes
0answers
21 views

Solutions to the given equation

How many solutions there are to the given equation that satisfy the given condition: $y + 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
20 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
16 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}$?
0
votes
1answer
85 views

Reverse permutation, number of inversions, descents, major index

If $w=a_1a_2...a_n \in S_n $, then let $w^r=a_n....a_2a_1$, the reverse of $w$. Express inv($w^r$), des($w^r$) and maj($w^r$) in terms inv($w$), des($w$), maj($w$), respectively. It from Stanley's ...
1
vote
1answer
12 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 ...
0
votes
1answer
11 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.
1
vote
1answer
32 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
1answer
39 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
0answers
15 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} ...
2
votes
2answers
55 views

Is there a closed form expression for the following sum?

Is there a closed form expression for the following sum? $$\sum_{0\le i_1<i_2<\cdots<i_k\le n}r^{i_1+i_2+\cdots+i_k}$$ I can understand that there are $\binom{n}{k}$ such terms and the ...
0
votes
1answer
23 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, ...
3
votes
1answer
285 views

Positivity of the alternating sum associated to at most five subspaces

Let $V_1 , V_2 , \dots , V_n $ be proper subspaces of $ \mathbb{C}^m$ and let $$\alpha = \sum_{r=1}^n (-1)^{r+1} \sum_{ \ i_1 < i_2 < \cdots < i_r } dim(V_{i_1} \cap \cdots \cap V_{i_r})$$ ...
19
votes
7answers
385 views
+200

Prove that $(mn)!$ is divisible by $(n!)\cdot(m!)^n$

Prove that $$(n!)\cdot(m!)^n|(mn)!$$ I can prove it using Legendre's Formula, but I have to use the lemma that $$ ...
2
votes
1answer
59 views

Coupon Collectors Problem with Packets: Clarifying Wikipedia

The Coupon Collector's Problem (CCP) is very useful in many applications. However, the "default" CCP is relatively simple: suppose you have an urn containing $n$ pairwise different balls. Now you want ...
1
vote
0answers
28 views

alternating binomial sums

So we know that $\sum_{i=0}^t\binom{m}{i}\binom{n-m}{t-i}=\binom{n+m}{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 ...
3
votes
4answers
156 views
+50

Find number of ways to seat $n$ boys and $n$ girls in a row so that every boy has at least one girl sitting beside him.

My attempt: I am getting $2^n(n!)^2$ . First I paired $n$ boys and $n$ girls in $n!$ ways then these pairs can be arranged in $n!$ ways and in each of these pairs boy and girl can arrange themselves ...
0
votes
1answer
16 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
43 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
29 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 ...
3
votes
4answers
48 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 ...
2
votes
3answers
41 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 ...
0
votes
1answer
361 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
2
votes
4answers
85 views

Prove the formula $\sum_{k=1}^n k\binom{n}{k} = n \cdot 2^{n-1}$ for all integers $n > 0$ [duplicate]

I just got to this question and I became a question mark. I wonder if anyone can help me with this one, because I don't even know how to begin to tackle this problem. The question: Prove the ...
1
vote
0answers
59 views

What is so special about Higman's Lemma?

Is there a motivational example 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 example, I was ...
0
votes
0answers
34 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
1answer
45 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
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
25 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
35 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 ...
0
votes
0answers
18 views

Number of ways of selecting a submatrix?

Given a matrix $N \times M$ and a point $(x,y)$ then in how many ways can you select a submatrix such that the point lies inside the submatrix ?
5
votes
5answers
849 views

How to find unique multisets of n naturals of a given domain and their numbers?

Let's say I have numbers each taken in a set $A$ of $n$ consecutive naturals, I ask myself : how can I found what are all the unique multisets, which could be created with $k$ elements of this set ...
1
vote
0answers
23 views

equal unions and intersections

Let $N$ be a $n$-element set and $k\ge n+2$. The sets $P_1,\dots,P_k$ are nonempty and their union equals $N$. Then there exists disjoint sets $I,J\subset\{1,\dots,k\}$ such that $\bigcup_{i\in ...
0
votes
0answers
8 views

Families of 3-element subsets such that no two intersect more than once

Another user asked the following question: "How can I determine the size of the largest collection of $k$-element subsets of an $n$-element set such that each pair of subsets has at most $m$ elements ...
0
votes
2answers
21 views

Permutations with repeated item [on hold]

I have: Orange Apple Orange Guava Pineapple Watermelon Strawberry Note the repeated Orange. Out of these 7, I have to choose 4 fruits. How many permutations are possible?
3
votes
2answers
289 views

How to generalize the Thue-Morse sequence to more than two symbols?

The Thue-Morse sequence is defined as a binary sequence and can be generated like 0, 01, 01 10, 01 10 10 01, 01 10 10 01 10 01 01 10, ... . So the second half of the series is always the binary ...
4
votes
5answers
123 views

Permutation in line and circle with conditions.

A party of $10$ consists of $2$ Americans, $2$ British men, $2$ Chinese & $4$ men of other nationalities (all different). Find the number of ways in which they can stand in a row so that no two ...
3
votes
4answers
78 views

Given that $6$ men and $6$ women are divided into pairs, what is the probability that none of the women will sit with a man?

I've generalized the question I was given here for simplicity: $6$ men and $6$ women are to be paired for a bus trip. If the pairings are done randomly, what's the probability that no women will end ...
0
votes
2answers
56 views

Combination - Distribution of gifts.

Seven different type of gifts are to be distributed among $10$ children. Every kind of gift must be at least given to one child. Then, how many combinations do we have? Note:You have $A, A, A....$ ...
4
votes
3answers
223 views

How many solutions for equation with simple restrictions

I'm working on an assignment in which I have to count the number of solutions for this particular equation: $$x_1+x_2+x_3+x_4=20$$for non negative integers with $x_1<8 $ and $x_2<6$ I'm aware ...
-1
votes
0answers
17 views

Confusing Conditional Probability question 68 [on hold]

The four top tennis players in the world A, B, C, and D are invited to a special tournament where the winner gets one million dollars. In round one, Player A plays player D and player B plays player ...
2
votes
1answer
302 views

Faces of the Permutahedron

We define the Permutahedron as the convex hull of all permutations of the vector $(1,2,\dots,n)\in\mathbb R^n$. I am having trouble seeing why the number of $n-k$ dimensional faces of this polytope is ...
-1
votes
5answers
79 views

Deck of Cards Stats Probability Question [on hold]

Randomly select two cards in sequence from a full deck of 52 cards, what i s the probability that the first one is a King given that the second one is a King. If someone can please help me with this ...
2
votes
1answer
50 views

In how many ways can $8$ appointments be scheduled for a physician visiting a nursing home with $20$ patients? [on hold]

A physician routinely visits a local nursing home on Thursday mornings to examine patients. Suppose the facility has $20$ residents, but the physician only has time to check $8$. The supervisor places ...
3
votes
1answer
27 views

Probability: Finding the Number of Pears Given Two Scenarios

You have a bag containing 20 apples, 10 oranges, and an unknown number of pears. If the probability that you select 2 apples and 2 oranges is equal to the probability that you select 1 apple, 1 ...
3
votes
1answer
61 views

Number of 'walks' which stay above 0.

Consider a set of distinct $n$ numbers where $a_i \in \mathbb{R} $ and $$\sum_{i=1}^{n} a_i = 0$$ A walk is defined to be the sum of the numbers, so that the $k$th position is the partial sum to $k$. ...
0
votes
0answers
4 views

Counting subgraphs of bounded extremal degrees

Let $m\leq n-1$. Is there a closed expression counting the subgraphs of minimum degree $\geq m$ (resp. maximum degree $\geq m$) on $n$ labelled vertices?
2
votes
1answer
21 views

How do you calculate the width of the Poset Lattice of Divisors?

Let $n = 10800 = 2^43^35^2$ I can find a set of eleven divisors of $n$ such that none divides another: $$\begin{array}{ccccc} & & & 2 3^3 & 3^35\\ & & 2^23^2 & ...
0
votes
1answer
40 views

Finding a closed formula for: $1\cdot2\cdot3+2\cdot3\cdot4+…+(n-2)\cdot(n-1)\cdot(n)$ [duplicate]

As I calculated the sum of the serie above doesn't exist(sum doesn't converge). How can I prove it using the double computing(combinatorical method)?
1
vote
1answer
31 views

How many ways to divide $n$ different pieces of chocolate in two non empty groups?

After the example I think that the order of the groups doesn't matter so ${(A),(B,C)}$ and $(B,C),(A)$ counted as $1$. Suppose we split $5$ chocolates into a group of size $1$ and a group of size of ...