Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [combinatorics]

For questions about the study of finite or countable discrete structures, especially 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.

-6
votes
0answers
37 views

Combinations and Permutations. [on hold]

A college has $750$ students and $400$ of them are girls. In how many ways can a delegation of $10$ be selected such that $4$ of them are boys? Using combinations and permutations.
-4
votes
0answers
38 views

In how many ways can the first, second and third prizes be drawn in a raffle? [on hold]

$3,500$ raffle tickets are issued in a charity function. In how many ways can the first, second and third prizes be drawn? Using combinations and permutations
-3
votes
1answer
44 views

${}_nP_r$ versus $n^r$ [on hold]

If I had $n=2$ different symbols, how many $2$-symbol ($r=2$) "words" could I create? If I had $n=5$ different symbols, how many $2$-symbol ($r=2$) "words" could I create? Would I use the ...
1
vote
0answers
46 views

Prove the determinant identity (2)

For any natural $n$ prove that \begin{gather*} {\frac { q \left|\begin {array}{ccc} {q}^{n+2}& \left( {\frac {p}{q}} \right) ^{n+2}& \left( {p}^{-1} \right) ^{n +2}\\ {q}& {\frac {p}{...
2
votes
2answers
104 views

$10$ numbers from $1,2,\dots,37$

$10$ numbers are chosen from $\{1,2, \ldots, 37 \}$. Show that we can choose $4$ of them such that the sum of two of these four is equal to the sum of the other two. My attempt : Almost nothing I ...
3
votes
1answer
48 views

Number of ways to divide dotted square grid in half

Consider a $4\times4$ dotted grid that looks like this: By drawing a series of connected straight lines going from dot to dot, there are many ways to divide the square into two halves (of equal area)...
0
votes
2answers
32 views

Determine the number of ways n distinct marbles can be placed inside five jars.

Determine the number of ways n marbles can be placed inside five distint jars, if the 1st jar must contain 1 marble, 2nd jar must contain 4 marbles, 3rd jar must contain 5 marbles, 4th and 5th marble ...
0
votes
3answers
35 views

Combinatorics proof involving finite series

I am trying to prove the following identity with little success!: $\sum_{k=0}^{p-1} (p-k) = p(p+1)/2$. Any suggestions? Thanks.
0
votes
0answers
24 views

Distribution of randomly ordered clusters

Let $P_{n,S}$ be an unordered random partition on $\{1,\dots,n\}$ whose $S=k$ clusters are randomly ordered by a random permutation $\Pi_S$ such that one gets an ordered partition $\tilde{P}_n$. $$Pr(...
0
votes
1answer
39 views

How to find the number of non-negative/positive integer solutions to $m_1x_1+\cdots+m_rx_r=n$ systematically? (coin-exchange problem)

I have been thinking about this problem for a few days already, out of curiosity. The number of non-negative integer solutions to $m_1x_1+\cdots+m_rx_r=n$ is equal to the $n$-th coefficient of $$f(z)...
2
votes
0answers
28 views

Express a set of number with binomial coefficients in terms of $n$ [duplicate]

Hi I'm working on my scholarship exam practice but I got stuck at my last question, could you please have a look? I'll write every part of question so you know the big picture. I have marked the ...
1
vote
1answer
30 views

Kenneth Rosen-Combinatorics-Exercise for section 5.5

For this question: There are $5$ balls and $3$ boxes. Find the number of ways to distribute the balls in the boxes for the given $4$ cases. 1>box and the balls are labelled: Then we get $3^5$ ...
0
votes
0answers
19 views

$\binom{n+1}{r+1}=\sum_{k=r+1}^{n+1}\binom{k-1}{r}$ whenever $n\geq r\geq 0$ [duplicate]

$\binom{n+1}{r+1}=\sum_{k=r+1}^{n+1}\binom{k-1}{r}\ \text{ whenever }n\geq r\geq 0.$ Anyone can help me with this proof?
-3
votes
3answers
84 views

Show that $a_{n-1}$ divides $a_{kn-1}$ for recurrence relation $a_n = a_{n-1} + a_{n-2}$

Question is posted above will be super thankful for all your help $a_n = a_{n-1} + a_{n-2}$ Show that $a_{n-1}$ divides $a_{kn-1} $for recurrence relation above $a_1 = 1$ $a_2 = 2$ $a_3 = 3$
1
vote
1answer
30 views

Number of five letter words possible using the english alphabet, not including anagrams

I'm studying for an intro to combinatorics midterm by completing past midterms. One of the questions is "How many ways are there to choose $5$-letter 'words' from the $26$-letter English alphabet ...
2
votes
1answer
40 views

Permutations preserving a filtration property

Suppose $\mathcal{A}$ is a non-empty family of sets of natural numbers size $n$ with the property that if $\{k_1<k_2< \dots <k_n\}\in \mathcal{A}$ and $j_i\leq k_i$ for all $1\leq i\leq n$, ...
4
votes
1answer
74 views

How to find the growth rates of $n$ bacteria, knowing the sizes of bacteria from $m$ observations?

Each bacterium grows at a some constant rate, i.e. every minute the size of the bacteria increases by some constant value. Different bacteria can grow at different rate (they can also grow at same ...
0
votes
0answers
47 views

A restaurant has a choice of $12$ main courses and $4$ desserts. How many $2$-course dinner selections are from the menu?

I got this question on combinatorics, but I am very confused about it. Q: A restaurant has a choice of $12$ main courses and $4$ desserts. How many $2$-course dinner selections are from the menu? I ...
0
votes
3answers
33 views

How many circular necklaces can be made with the length of p (a prime number), that can be created by connecting n different types of beads together

Given an unlimited number of beads of n different types, how many circular necklaces are there, with the length of p (a prime number), that can be created by connecting the beads together? Note that ...
0
votes
1answer
32 views

Combinations: summation of combinations equalities

Suppose we have two quantities $$ A = \sum^n_{i=0}C^n_i (X_{n-i}X_{i+1} + X_iX_{n-i+1})\\ B = \sum^{n+1}_{i=0}C^{n+1}_i (X_iX_{n-i+1}), $$ where $C^n_i$ is the combination notation, and $X$ are just ...
1
vote
1answer
39 views

Infinite modular lattices

A finite lattice $L$ is called modular if and only if its elements satisfy the following modular identity: For all $x,y,z\in L$ such that $x\leq z$, we have $x\vee(y\wedge z)=(x\vee y)\wedge z$. How ...
0
votes
1answer
34 views

The sum of the second numbers in the first 100 rows of Pascal's Triangle

What is the sum of the second numbers in the first $100$ rows of Pascal's triangle (excluding the first row, the row containing a single $1$)? The sum should be over the second through the hundredth ...
1
vote
1answer
34 views

A question on “unlabeled Cayley graphs”

Suppose $G$ is a finite group $S \subset G$. Let's define $UCG(G, S)$ (unlabeled Cayley graph) as a finite unordered simple graph $\Gamma(V, E)$, where $V = G$ and $E = \{(x, y) \in G \times G| x \neq ...
0
votes
1answer
37 views

Anagrams with Generating Functions

Consider the letters {a, b, c, d}. How many 5-letter sequences containing an even number of b's and odd d's exist? How to approach this problem using generating functions?
2
votes
1answer
36 views

Minimizing total number of comparisons on a set of numbers

Suppose $S=\{a_1,a_2,\dots,a_{50}\}$ is a set of distinct integers that $1\le a_i\le200$ $(\forall i$ $1\le i\le 50)$ Let $D\subset S^3$ be the subset that doesn't contain any repetitive element in 3-...
0
votes
1answer
16 views

Selection of objects with generating functions

Use generating functions to find the number of ways to choose $r$ objects of $n$ different types, knowing that we must choose at least 1 object of each type. How can we express in the solution that ...
0
votes
1answer
22 views

Degrees of freedom in construction of a symmetric tensor

How many degrees of freedom does a symmetric tensor satisfying $$S^{ij}_{kl} = S^{ji}_{kl} = S^{ij}_{lk} =S^{kl}_{ij}$$ have? The indices range from $1$ to $n$.
-1
votes
0answers
49 views

Lower and Upper bounds of the distance between two Frobenius Numbers [on hold]

I consider two sequences of numbers: $A=\{a_1,...,a_{m-1},n\}$ and $B=\{n-a_{m-1},...,n-a_1,n\}$, where $a_1 < a_2 < ... < a_{m-1} < n$ and $\gcd(A) = \gcd(B) = 1$. I investigate the ...
2
votes
1answer
46 views

The Pigeon Hole Principle for Sequences

Suppose there is a test with $n\geq 2$ questions each of which will receive a score from 0 to $m\geq 1$. Every possible score is obtained by some unique student. Define same$(a,b)$ to be the set of ...
5
votes
1answer
87 views

Minimal Rook Difference Grids

In the below grid all 18 orthogonal differences are distinct, with a difference of 18 missing. Could the highest number be 18? The resulting graph would have valence 4, making it an Eulerian ...
0
votes
1answer
34 views

Number of pair of sequences of length $n$ such that no $2$ elements are equal

My question is this : Given two integers $n$ and $k$, we have to generate $2$ sequences $A$ and $B$ of length $n$ each containing integers from $1$ to $k$. Find the number of sequences we can ...
0
votes
1answer
28 views

Boxes and objects permutation question

What are the total number of ways of distributing $n$ distinct objects in $r$ distinct boxes where arrangement of objects within boxes are also considered and all the boxes are not empty? I know how ...
1
vote
1answer
25 views

Formation of commissions with generating functions

Representatives of three research institutes should form a commission of 9 researchers. How many ways can this committee be formed such that no institute should have an absolute majority in the group? ...
0
votes
1answer
31 views

Combinations With Repetition Intuition

How many ways are there to choose a 5-letter “words” from the 26-letter English alphabet with repeated letters allowed, but words that are anagrams are considered the same? The words need not be ...
7
votes
1answer
55 views

Divide the chessboard

Suppose you have marked all the 64 centers of unitsquares of a chessboard. At least how many lines do you need, such that they divide the plane in a way, such that no two marked points lie in the ...
2
votes
1answer
44 views

Recurrence relation in a Permutation and Combination Problem in Galois Theory by Ian Stewart

The given problem is: Let $P(n)$ be the number of ways to arrange $n$ zeros and ones in a row, given that ones occur in groups of three or more. Show that $$P(n) = 2P(n-1)-P(n-2)+P(n-4)$$ and deduce ...
2
votes
0answers
19 views

Maximum flow in net N where all vertices are subsets of set {1,..k}

Let $N$ be a net whose vertices are all subsets of set $\{1,..,k\}$ and an egde connect only these two subsets that differ in exactly one element. If this element is $x$ then this edge has capacity $2^...
2
votes
2answers
32 views

What's the sum of all 6 digit numbers that can be made with numbers 1, 2, 3, 5, 7, 8?

It's not necessary for the 6 digit numbers to have unique numbers. E.g. 111111 is an acceptable number.
0
votes
1answer
15 views

Specific position / Restricted permutation [I don't exactly know the name of this topic]

In the word ARTICLE find the number of permutation by keeping A in the first place or not keeping E in the last place. How do I solve this. What's the exact category for this type of permutation? ...
0
votes
0answers
38 views

Linear programming over integers mod 2, expressing function as sum of two

Let $h=a+\ell+1$ and define $$ f(a,\ell;u_2,u_1,\tau) = \frac{h^2}2 u_2 +h(a+\frac12)u_1+\frac{a(a+1)}2 \tau+1 $$ where all the variables are integers, and such that $u_1=u_2 \pmod{2}$. Such $f$ is an ...
2
votes
2answers
34 views

Generating Function functional relation

Suppose I have a generating function which I know satisfies the relation $$x = T(x) (1 - x - T(x^2)).$$ Can I say anything about the coefficients? Ideally I would be able to get some kind of closed ...
0
votes
3answers
52 views

Is there any way to simplify $\binom{n}{k}+\binom{n+1}{k}$?

I was wondering if there is any way to express the sum $\binom{n}{k}+\binom{n+1}{k}$ as only one binomial coefficient?
0
votes
1answer
20 views

Combinatorics/Permutations [duplicate]

A village has about 1 million residents. Suppose each resident has a jar with 100 coins in it.Two jars are considered to be “equivalent” if they have the same number of 10c, 20c, 50c, \$1 and \$2 ...
1
vote
0answers
20 views

Assignment of subsets with overlap rule

I want to create $M$ lists of size-$k$ subsets of $\mathbb{Z}_n$, labeled $A_1, \ldots, A_M$ with the following properties: $|A_1| = |A_2| = \ldots = |A_M|$, i.e. every list contains the same number ...
2
votes
2answers
161 views

How to count the number of different sequences possible?

Lets consider all matrices with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$) containing only integers between $0$ and $K−1$ (inclusive). For each such matrix $A$, let'...
1
vote
1answer
49 views

Is it theoretically possible that every person in this village has a different jar of coins?

A village has about $1$ million residents. Suppose each resident has a jar with $100$ coins in it.Two jars are considered to be “equivalent” if they have the same number of 10c, 20c, 50c, $\$$1 and $\$...
0
votes
1answer
39 views

Combinatorics/probability ballot problem

Suppose that there’s an election! Two candidates, Sherlock and Moriarty, are running for office. Suppose that Sherlock receives 8 votes and Moriarty receives 7 votes, and that these votes are being ...
4
votes
3answers
74 views

Combinatorial Proof of $3^n - 2^n = \sum_{i=0}^{n-1}2^i3^{n-1-i}$

$3^n - 2^n = \sum_{i=0}^{n-1}2^i3^{n-1-i}$ Firstly, I'm trying to figure out what both sides count. The left hand side counts the number of $\{0,1,2\}$ strings minus the number of $\{0,1\}$ strings. ...
2
votes
0answers
29 views

A combinatorial argument to prove a general inequality

Recently, I have seen the following argument: $$f(x) < Dx + f\left(\frac{x}{2} \right)$$ $$\Rightarrow f(x) < Dx + f \left( \frac{x}{2} \right ) < Dx + \frac{Dx}{2} + f \left(\frac{x}{4} \...
3
votes
3answers
247 views

In how many ways can a bit string of length $20$ be generated if either all $0$'s or all $1$'s need to be grouped together?

Given a bit string of length $20$, how many ways can such a string be generated if either all 0's or all 1's need to be grouped together in the string? A few examples of strings that would be ...