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)

1
vote
2answers
48 views

Unique combinations of 7 items (repetition allowed, order doesn't matter)

I am trying to calculate the number of unique combinations for a 7 element set with repetition allowed where order doesn't matter. For example: ...
0
votes
2answers
32 views

Unique combinations from 7 items where repetition is allowed, and order doesn't matter

I am trying to calculate the number of unique combinations from a 7-element set where repetition is allowed and order doesn't matter. For example: Suppose $S = \{a, b, c, d, e, f, g\}$, and I want 3 ...
3
votes
1answer
56 views

finding the partial bell polynomial of $e^x$

$$ \left(e^{x+z} - e^x\right) = \sum_{n=1}^\infty \frac{z^n}{n!} \frac{d^n}{dx^n}[e^x] $$ $$ \left(e^{x+z}-e^x\right)^k = \sum_{n \geq k} Y^{\Delta}_{e^x}(n,k,x)z^n $$ Where: $$ Y^{\Delta}(n,k,x) = ...
3
votes
3answers
73 views

Arrangements of Chairs in a Circle

Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs. Hints only please! This is a confusing worded-problem. We ...
2
votes
1answer
52 views

Formula to find possible number of combinations

A committee of 5 is to be selected from a group of 6 men and 9 women. If the selection is made randomly, what is the probability that the committee consists of 3 men and 2 women. We can solve ...
-2
votes
4answers
64 views

How many arrangements exist (a + b + c = 4) [duplicate]

For example, $a + b + c = 4$ Solving this using stars and bars You have $4$ stars and $2$ bars: $$ x | x | xx$$ For example. Then what does $\binom{6}{2}$ mean? The number of arrangements ...
0
votes
1answer
27 views

Calculating the number of all possible connected regions on a discrete grid

Given an $N \times M$ grid. How would one calculate the number of possible connected regions of that grid? A connected region is a set of cells in this grid such that there is a path from any cell ...
3
votes
1answer
36 views

Permutations of n objects taken r at a time ( r=1 to r=n ) where objects may be groups of same entities and it's sum

Given n objects where n1 objects are the same ,along with another group of n2 objects of same element etc.. such that Σni = n (i=1 to k). Assuming there are k groups of similar objects eg: in ...
4
votes
2answers
47 views

Prove that $x\ge n(n-1)(n-3)/8$, where $x$ is the number of $C_4$ cycles in a graph.

If there are no $C_4$ cycles in a graph the edges in $G$, ie, $e(G)\le\frac n4(\sqrt{4n-3}+1)$, but if $e(G)\ge\frac12 {n \choose 2}$, we have to show that $x$ (number of $c_4$ cycles) $\ge ...
4
votes
1answer
40 views

How many matches are played?

A tennis club has $10$ couples as members. They meet to organize a mixed double match. If each wife refuses to partner as well as oppose her husband in the match, then in how many different ways ...
0
votes
0answers
33 views

A complicated summation of binomial coefficients

I am trying to evaluate this sum. I think closed form of this sum is not possible, but there might be some bound or approximate result. So far I was unable to find any approximation. Any help will be ...
0
votes
2answers
53 views

Proof Question regarding product sum and series

The question is let $\{m_1, m_2, m_3, \dots \}$ be a sequence of numbers where $m_k\geq 0$ for every $k \geq 1$. Let $$M_n = \sum_{k=1}^n m_k $$ when $n \geq 1$ is an integer. Show that if ...
4
votes
6answers
91 views

Show that if n+1 integers are choosen from set $\{1,2,3,…,2n\}$ ,then there are always two which differ by 1

Considering n=5 i have $\{1,2,3,...,10\}$ .Making pairs such as $\{1,2\}$ ,$\{2,3\}$ ... total of $9$ pairs which are my holes and $6$ numbers are to be choosen which are pigeons .So one hole must ...
2
votes
3answers
42 views

Permutations without repetitions (exclude repeated permutations) [duplicate]

The formula to calculate all permutations without repetitions of the set {1,2,3} is $\dfrac{n!}{(n-r)!}$ But how to calculate it if the set (or rather array in programming terms) includes repeated ...
2
votes
1answer
26 views

Number of subsets of $[n]$ with $k$ runs

This is an exercise from Douglas West's course on combinatorics. Given a set $S \subseteq [n] = \{1, 2, \ldots, n\}$, a run in $S$ is a maximal subset of $S$ that contains only consecutive integers. ...
4
votes
1answer
75 views

Does Euler's $\phi$ function have the same value in arbitrarily large subsets of $\mathbb{N}$?

As my most recent question still does not have any answers and it appears to be a difficult problem, I propose the following problem (that seems easier), but which I still could not manage to solve: ...
1
vote
1answer
38 views

Are there different combinatorial species with the same symmetry type?

First off: for my purposes, let $\sf B$ be the category of finite sets with bijections, and ${\sf B}_n$ the subcategory of sets with cardinality $n$, and define a combinatorial species to be a functor ...
0
votes
1answer
41 views

“quasi-increasing” permutation of a number

Call a permutation $a_1,a_2,\ldots,a_n$ quasi-increasing if $a_k\le a_{k+1}+2$ for each $1\le k\le n-1$. For example, $54321$ and $14253$ are quasi-increasing permutations of the integers ...
1
vote
2answers
24 views

how many ways to arrange 10 players between 3 positions with at least two players in each position?

my thought is that you would do 10 choose 6 to decide the 6 players to split between the 3 groups, then 6 choose 2 times 4 choose 2 times 2 choose 2 divided by 3! to determine how to arrange the 6 and ...
1
vote
1answer
21 views

characterize convergent sequences

Suppose that there is a strictly decreasing sequence $\{a_i\}$ such that $\sum_i a_i=1$. Given a rational number $r$ with $0<r<1$, is it possible to characterize for which subsets $A\subseteq ...
0
votes
2answers
22 views

Max 2-sat and clause size

I've seen that Max 2-Sat is NP-complete, are there instances in which every clause has exactly $2$ variables which are $NP$-complete? Or do all such instance need to contain a clause of exactly 1 ...
3
votes
3answers
65 views

Probability that no two consecutive heads occur?

A fair coin is tossed $10$ times. What is the probability that no two consecutive tosses are heads? Possibilities are (dont mind the number of terms): $H TTTTTTH$, $HTHTHTHTHTHTHT$. But ...
1
vote
2answers
34 views

Comparison of two collections of 4-tuples using combinatorics - more complicated version

My problem is to show that 2 collections of unordered 4-tuples - $\mathbf{A}$ and $\mathbf{B}$ - are the same. I define a collection of objects as a set, in which multiple entries of the same object ...
0
votes
1answer
92 views

Combinatoric meaning of $\binom{n}{k}$

$$\binom{n}{k}$$ Means how many ways there are to choose $k$ objects out of $n$ objects (order of picking doesnt matter). But does $\binom{n}{k}$ also mean how many ways there are to arrange ...
0
votes
1answer
17 views

Number of permutations with balanced middle element

Let $v$ be a permutation of $\{1,2,\cdots,2n+1\}$ where $n$ is odd, such that the middle element $v_{n+1}$ satisfies the following: the number of elements to the right of $v_{n+1}$ that are less than ...
1
vote
3answers
62 views

Why is the probability multiplied by $\binom{n}{k}$

A while ago I asked a question about probability here Why is binomial probability used here? I get that you can find how many ways of choosing the $6$ correct out of $10$ questions. But why do we ...
4
votes
1answer
122 views

A summation involving multinomial coefficient

We need to find out $$\sum {\binom{N}{a_1,a_2,a_3...a_B} a_1^{\alpha}a_2^{\alpha}...a_C^{\alpha} }$$ $$a_1+a_2...a_B=N, \alpha>0 ,0\lt C \le B$$ All are nonnegative integers. We need to sum ...
0
votes
1answer
39 views

What is the number of ways to express $\mathbb{Z_n}$, the ring of integers modulo $n$, as a direct sum of its ideals?

$\mathbb{Z}_n$ is a ring, ($\{0,1,2,...,n-1\}, \mod n$ addition and multiplication). I think that the ideals of $\mathbb{Z}_n$ are precisely the rings generated by its divisors. For example, the set ...
0
votes
1answer
29 views

Arranging $2n$ objects in specific ways

There are $n$ objects $a_1, a_2, ... , a_n$ and another $n$ objects $b_1, b_2, ... , b_n$. We have to choose all the $2n$ objects such that $a_i$ is chosen before $a_{i+1}$ and $b_i$ is chosen before ...
10
votes
0answers
200 views

Finding real money on an even stranger weighing device

You have $n$ coins which each weigh either $20$ grams or $10$ grams. Each is labelled from $0$ to $n-1$ so you can tell the coins apart. You have one weighing device as well. At the first turn you ...
1
vote
0answers
23 views

Polyhedral surface with infinitely many triangulations with same combinatorics

Is there an example of a polyhedral surface that has infinitely many triangulations with the same combinatorics?
10
votes
2answers
148 views

Find $\sum_{i\in\mathbb{N}}(n-2i)^k\binom{n}{2i+1}$

Find $$\sum_{i\in\mathbb{N}}(n-2i)^k\binom{n}{2i+1},$$ where both $n$ and $k$ are natural numbers. I know the following identity: $$ ...
2
votes
2answers
88 views

Combinatorial Game

Suppose you have $m+n+1$ consecutive squares, and place $m$ white counters in the first $m$ squares and $n$ black counters in the last $n$ squares, leaving a counter-free box in between. White ...
1
vote
3answers
44 views

Question involving chess master (combinatorics)

I am having hard time with this question .I have not understood what is point and why is sequence $a_1 + 21$ , $a_2 + 21 $... has been taken in second picture .Please help me understand the question ...
0
votes
1answer
72 views

Counting the number of nonnegative integer solutions

The constraints are $x_1+x_2+x_3=5,\qquad (1)$ $y_1+y_2+y_3=7,\qquad \; (2)$ $x_1 \geq 3,\qquad \qquad \qquad \;\; (3)$ $0 \leq y_2 \leq 2,\qquad \qquad \;\;\;(4)$ $x_2+y_2 \geq 1,\qquad \qquad ...
2
votes
1answer
63 views

How many patterns there are in a sequence of dice throws?

I have the set of all possible results from throwin $n$ dices. Like 1 1 1 ... 1 ... 6 6 6 ... 6 Then I have been given a list $T$ of sequences of throws: ...
3
votes
1answer
51 views

Dependency of submatrix used in a combinatorial strategy .

This is a verification post , Please inform if anything is undefined or unclear or miss-tagged. Also if you vote up/down it would be helpfull if you leave a comment. Introduction: Given a matrix A ...
1
vote
0answers
24 views

how to count unique combination of elements taken from different sets, and with fixed combination length

i have n sets of numbers each containing xn repeated number, for instance i can have the following sets : {1,1,1}, {3,3}, {8} where n =3, and x1 = 3, x2 = 2, x3 = 1. and i would like to find ...
0
votes
2answers
42 views

Probability a string has $2$ digits, $4$ consonants, and $1$ vowel, given a length of $7$ w/o repetition

My thinking behind this problem would be to pick $2$ digits out of 10 total $\binom{10}{2}$, $4$ consonants out of $21$, vowels not included $\binom{21}{4}$, and the $5$ vowels, multiplied by $7!$. ...
1
vote
1answer
33 views

Number of ways of choosing at least $k$ objects out of $n$

Suppose you have three distinct items $a$, $b$, $c$. You want to find how many unique sets you can get by choosing at least one item. For example, $\{a\}$ would form a unique set, and $\{a, b\}$ would ...
0
votes
2answers
75 views

Multinomial Coefficients Definition in expansion of $(1+x+x^2+\cdots+x^l)^n$

The literature defines multinomial coefficients (or extended bnomial coefficients) as $$ \binom{n}{r_1,r_2,\cdots,r_l} = \frac{n!}{r_1!r_2!\cdots r_l!}$$ where $$ r_1+r_2+\cdots+r_l = n$$ Which is ...
2
votes
1answer
49 views

Urn problem and combinatorics

You have $5$ red and $4$ black balls. How many ways there are to distribute all to $3$ different bottles? If I had $9$ red balls, then it would be $\binom{n+k-1}{k}$ = $\binom{3+9-1}{9}$, but I have ...
0
votes
1answer
23 views

Calculating combinations without duplicate values

I have 128 chairs, and 256 people. How many different combinations of the 256 people can be sitting in the 128 chairs? Order doesn't matter, and obviously the same person can't be sitting in more ...
0
votes
3answers
98 views

Why is Binomial Probability used here?

A test consists of 10 multiple choice questions with five choices for each question. As an experiment, you GUESS on each and every answer without even reading the questions. What is the ...
-1
votes
0answers
52 views

how to evaluate permutations of rubik's cube?

how to calculate total number of permutations of a rubik's cube , say, one face of the cube , specifically saying it is the blue face which is fixed , now what are the total number of permutations of ...
1
vote
1answer
27 views

Ways to stack 65 different disks in 3 piles with constraints.

How many ways are there to stack 65 different disks in 3 piles if pile 1 but have at least 15 disks and pile 3 must be non-empty. Attempt: 1) Ways to arrange all the disks in a horizontal line: ...
4
votes
2answers
325 views

Count the number of integer solutions of a linear equation

What kind of approach can be used to solve this specific problem? An easy one if possible. I thought about the Inclusion-Exclusion Principle; I think using generating functions will be more ...
2
votes
2answers
46 views

How many solutions exists for this equation? [duplicate]

$$x_1 + x_2 + x_3 + x_4 = 28$$ I tried to solve it with generating functions. Is it correct to get to the form of $${(1 + x + {x^2} + {x^3} + ....)^4}$$ and this equals to: $${(1 - x)^{ - 4}}$$ ...
0
votes
0answers
28 views

Confused between cyclic sum and symmetric sums.

four variables $a, b, c, d$ are given, what is the symmetric and cyclic sum? I thought: $$\sum_{cyc} ab = ab + ac + ad + bc + bd + cd$$ And $$\sum_{sym} ab = 2(ab + ac + ad + bc + bc + ...
3
votes
2answers
64 views

Number of ways to choose numbers from a list.

While studying, I came upon this question in my book: "How many ways are there to take 7 numbers from 1 to 12 such that none of the chosen numbers is twice the other?" The solution is shown as 47, but ...