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
1answer
64 views

Tricky question about binomial expansions. [duplicate]

State the binomial expansion of $(1+x)^n$ So I can do this $$(1+x)^n=\sum_{i=0}^{n} {n\choose i}x^i$$ Then given $n=2k$ is even. Derive an expression for $$\sum_{i=0}^{2k} (-1)^i{2k\choose i}$$ ...
2
votes
1answer
74 views

Trirectangular tetrahedron

Looking at http://mathworld.wolfram.com/TrirectangularTetrahedron.html I wonder what the symmetry group of a trirectangular tetrahedron is?
1
vote
5answers
107 views

There exist a set $X$ such that the number of function $y: x\to \{1,2,3\}$ is $1000$.

There exist a set $X$ such that the number of function $y: x\to \{1,2,3\}$ is $1000.$ My attempt: False, Let set $z = \{1,2,3\}$ then $|z|^{|x|}$ is set of function $y:x\to z.$ $|x| = n$ and $|z| = ...
-4
votes
1answer
28 views

Four letters {A, B, C, D} are arranged in a line. What is the probability that A and B will be next to each other? [on hold]

Four letters $\{A, B, C, D\}$ are arranged, with no repetitions and always using the four. What is the probability that $A$ and $B$ will be next to each other?
1
vote
0answers
23 views

How to find a set of integer vectors (of length L) such that all its subsets with size L are linearly independent?

Given a number $M\geq L$, how to find a set of $M$ vectors in $\mathbb{Z}_{\geq0}^{L}$, say $S=\{\mathbf{a}_1,\cdots,\mathbf{a}_L\}$, such that: 1-All subsets of $S$ with size $L$ are linearly ...
1
vote
2answers
73 views

Probability in a Restaurant

In a revolving restaurant, there are four round tables each with three seats. How many different ways can $12$ people sit in this restaurant? This is what I think the answer is: $$\binom{12}{4} ...
0
votes
1answer
79 views

How to find weight function using generating series?

How to find the weight function and corresponding set given the generating series? Is there a general method for this kind of problems, I am preparing for an olympiad. Consider the below example: ...
1
vote
1answer
42 views

covering subsets

Let $A=\left\{ {1, 2, \ldots, n}\right\}$. Let $B$ be the set of all size $m$ subsets of $A$. $B=\left\{{B_1,B_2, \ldots , B_{\binom{n}{m}} } \right\}$, $ |B_i|=m$ then we want to find $k$ subsets ...
1
vote
0answers
48 views

Lights out - foobar - optimise python implementation beyond binary matrix solver

I'm looking for further details on solving 'Lights out' puzzle, as asked in foobar challenge. Sorry I don't have enough credit to add/comment on existing threads, but I'm interested in a specific ...
3
votes
4answers
42 views

6 people are holding a show, one at a time, such that person $x$ has to go after person $y$ and person $z$. How many ways could the show be held?

Let's say the people are called $a$, $b$, $c$, $x$, $y$, $z$ My initial thinking was to go by fixing "$x$" in a certain position, so: $\underline {} \underline {} \underline {}\underline ...
1
vote
1answer
17 views

How do I get number of combination for pairs of football teams?

Suppose we have 8 football teams playing each other in 4 matches. How do I find the number of combinations that is possible? E.g. Teams A,B,C,D,E,F,G,H can be in the following matches: Match 1: A vs ...
1
vote
2answers
70 views

combinatorics contest problem

Question: Calvin has a bag containing $50$ red balls, $50$ blue balls, and $30$ yellow balls. Given that after pulling out 65 balls at random (without replacement), he has pulled out $5$ more red ...
1
vote
4answers
49 views

Combinatorics: Simplify the generating function $x^0+x^2+x^4+\cdots$

This is probably going to have a simple solution, and I'm going to kick myself when I see it, but I have a bit of mental block on this topic in general that I'm trying to clear before the next year of ...
2
votes
1answer
56 views

How to find the recurrence relation from a given polynomial?

Consider the formal power series: $A(x)=\sum a_nx^n$. and $A(x)= \frac{8+14x-50x^2}{1-7x^2+6x^3}$ I am trying to derive a recurrence relation, Is there a general method for doing it? Please help, ...
2
votes
2answers
37 views

How many possible orders are there?

A tapas bar serves 15 dishes, of which 7 are vegetarian, 4 are fish and 4 are meat. A table of customers decides to order 8 dishes, possibly including repetitions. a) Calculate the number of possible ...
0
votes
0answers
17 views

What's the approximation of such a combination? [duplicate]

Given $k,m, k \leq m$. $N=\binom {m+k}{m}$ What's the approximation of N?
7
votes
0answers
61 views

In how many ways can the integers from $1$ to $n$ be divided into two groups with the same sum?

In how many ways can the integers $1,2,\ldots,n$ be divided into two groups with the same sum? I have tried calculating some of these values for small $n$, but cannot seem to find a pattern. Any ...
2
votes
0answers
23 views

Combinatorics: number of functions/predicates satisfying a sum on their entries

Given integers $n,m$, is there a closed form expression for the cardinality of the following set? $$\left\{ p : \{1,\dots,n\}^2 \rightarrow \{true,false\} \quad \Bigg| \sum_{i,j,k \in \{1,\dots,n\}} ...
0
votes
2answers
91 views

Counting problem: ways of opening stores in non-adjacent blocks?

A coffee company wants to set up stores along the main street of town, which has $n$ blocks. The company won’t open two stores in the same block, or in two adjacent blocks. Q: For this coffee shop, ...
3
votes
0answers
67 views

Combinatorial formula for the number of different words

Does there exist a closed formula for the following: Suppose we have $m$ distinct letters and we are allowed to use each letter at most $d$ times. What is the number of distinct words of length $k?$ ...
1
vote
1answer
33 views

How can I find how many unique strings there are with an equal numbers of elements, given a string length and number of elements to choose from?

The question is all in the title. Here's an example: Elements: A, B; Length: 4: AABB ABAB ABBA BABA BBAA BAAB There are 6 such unique strings for 2 elements and ...
0
votes
0answers
24 views

Maximizing the following function

I need to find values of $k_1$, $k_2$ and $k_3$ that maximize $C^{m_1}_{mm_1} \cdot C^{m_2}_{k_1-mm_1} \cdot C^{n_1}_{nn_1} \cdot C^{n_2}_{k_2-nn_1} \cdot C^{p_1}_{pp_1} \cdot C^{p_2}_{k_3-pp_1}$ ...
2
votes
1answer
23 views

The generating set of Cayley graphs over $Z_n$

Say we have a undirected and connected Cayley graph over $\mathbb{Z}_n$, with generating set $S=\{\pm x_0,\pm x_1,\ldots,\pm x_k\}$. Is it true that we can assume without the loss of generality that ...
6
votes
2answers
137 views

Proof of an identity of $n!$

I came up (numerically) with an identity concerning n! and I was wondering about a proof of it. Here it is: \begin{align} \ n! &= \sum_{r=0}^{n} { \binom{n}{r} (-1)^r(k-r)^n } \quad \forall n ...
1
vote
0answers
14 views

Number of ways to connect sets of k vertices in a perfect n-gon [duplicate]

This is a copy of my post at Mathexchange.com, as my question is still not fully answered and I really wanna find a solution to this. Feel free to refer to there for useful comments and partial ...
0
votes
4answers
46 views

How many three digit numbers with increasing digits can be formed from the set $\{1, 2, 3, 4, 5, 6, 7, 8\}$?

Suppose we pick 3 numbers $x,y,z \in \{1,2,3,4,5,6,7,8\}$ and form a 3 digit number $xyz$ how many possible combinations numbers can we create such that $x < y < z$. For example $357$ ...
0
votes
3answers
43 views

Probability of choosing two numbers so they differ by at least 2

A box has $10$ balls numbered $1,2, \dots, 10.$ A ball is picked at random and then a second ball is picked at random from the remaining nine balls. Find the probability that the numbers on the two ...
2
votes
4answers
76 views

Two dice thrown together.

Each face of a die is marked with a different number from 1 to 6. The number on the faces of the die are marked in such a way that the sum of the numbers on any pair of opposite faces is 7. Two such ...
5
votes
0answers
80 views

Hatcher 2.1.10…

Hatcher asked a question in chapter $2$ (a) Show the quotient space of a finite collection of disjoint $2$-simplices obtained by identifying pairs of edges is always a surface,locally homeomorphic ...
0
votes
0answers
18 views

Number of subset problem [duplicate]

Question: A woman is preparing to go for a party .She need to colour her nails (all her nails considered 10 nails) She want to use either pink nail polish or red nail polish to colour each nails. ...
3
votes
2answers
61 views

Set and subsets link by prime numbers

I have a bit idea to solve this problem for small $n$ by programation but I think for $n>100$ I will need maths to help me. My problem is : Let S be the set of prime numbers less than n. Find ...
5
votes
1answer
60 views

How to prove the maximum possible number of elements of $S$ is $48$?

Let set $S\subseteq \{1,2,3,\cdots,100\}$,for any two different $a,b\in S$,there exist postive integer $k$ and $c,d\in S(c<d)$,($c,d$ can equal to $a$ or $b$),such $$a+b=c^k\cdot d$$ show that ...
-6
votes
2answers
54 views

Chances of this… [closed]

9 people sat in a circle. They wrote their name on a piece of paper, folded it over and placed it in a hat. The hat was shuffled to mix up the pieces of paper. The first person picked out the name ...
1
vote
1answer
16 views

Number of solutions to equation $\sum_{i=1}^{n}x_i = R$ where $x_i>k$ where $k$ is a positive number

I know that the number of solutions to an equation of the form: $$\sum_{i=1}^{n}x_i = R$$ equals $\binom{n+R-1}{R}$. I am aware of the $x_i$ LESS THAN EQUAL TO case where, if say $x_6 \leq 3$, I ...
0
votes
2answers
50 views

In how many ways can we place $n$ indistinguishable balls in $n$ urns so that exactly one urn is empty?

How many ways can we place $n$ indistinguishable balls in $n$ urns so that exactly one urn is empty? So if I do this similar to stars and bars I am looking to put $n$ balls in actually $n-1$ urns, so ...
0
votes
1answer
36 views

Dividing $n$ identical things into $r$ groups

I was reading a course on Combinatorics where I came across following: The number of ways in which $n$ identical things can be divided into $r$ groups so that no group contains less than $m$ items ...
2
votes
3answers
39 views

Number of words which can be formed with INSTITUTION such that vowels and consonants are alternate

Question: How many words which can be formed with INSTITUTION such that vowels and consonants are alternate? My Attempt: There are total 11 letters in word INSTITUTION. The 6 consonants are ...
13
votes
4answers
347 views

Number of ways to connect sets of $k$ dots in a perfect $n$-gon

Let $Q(n,k)$ be the number of ways in which we can connect sets of $k$ vertices (dots), in a given perfect $n$-gon, such that no two lines intersect at the interior of the $n$-gon and no vertice ...
4
votes
1answer
67 views

Knight movement on chess field

I had this task in programming competition: There are two knights, which are $(p_1,q_1)$ and $(p_2, q_2)$. $(p,q)$ knight is figure, with p(q)-length first step, and q(p)-length second step in ...
5
votes
3answers
436 views

How many possible words of this type can be formed?

We are making $10$ letter words using the letters $A,C,G,T$. How many possible words are there of the form $A...AC...CG...GT...T$ This is where all of the $A's$ go before the all of the $C's$ and ...
3
votes
0answers
62 views

Is it 3-D Catalan numbers?

I am studying Catalan numbers recently but I think that how about 3-D Catalan? So that I imagine following situation ; A man travel through the path-way parallel to $ x, y, z $ axis from O ...
2
votes
1answer
42 views

How many $10$ letter anagrams of KOLMOGOROV don't contain the subword GROOV?

How many $10$ letter anagrams of KOLMOGOROV don't contain the subword GROOV? Not sure how to do this one. Obviously there are $\frac{10!}{4!}$ anagrams of KOLMOGOROV but I'm not sure how to account ...
1
vote
0answers
38 views

A Combinational identity using permutations

For a distribution {$p_1,p_2, …,p_m$}, with $p_i>0$ and$\sum_1^m{p_i}=1$ , let $J$ be a subset of size $j$, and $m>j\geq1$. It holds that: $$\int_0^1\prod_{i \in J} (x^{-p_i}-1) dx = ...
2
votes
3answers
46 views

Different ways of giving away 35 coins to 5 people?

The first part of the problem asks how many ways there are to give away 35 identical coins to 5 people, and I've concluded that it's ${35 \choose 5}$ because you're selecting how many ways you can ...
-4
votes
1answer
50 views

Solving $x+2y+3z=100$ in nonnegative integers. [closed]

Solving for number of solution in set of non-negative integer of $$x+2y+3z=100$$ by generating function but finding problem in writing partial fraction of ...
0
votes
1answer
24 views

What's the least number of combinations you need to determine who the most efficient members are?

Not sure if this question fits here, but it's something I was thinking about last night. Maybe someone can throw some light on it. Let's say I have a group of people doing some shared task. Let's ...
2
votes
1answer
48 views

Counting Spanning Trees Needed to cover Edges

This is in the same spirit as this stackexchange post, but I am seeking a more general answer. The goal is, given a graph $G$, give a method of counting the minimum number of spanning trees needed ...
-4
votes
1answer
29 views

Number of different possible armies in Clash of Clans [closed]

Suppose we are given a set of sixteen different units. How many different armies of $200$ units exist ? In other words, how many $16$-uplets $(c_1, \cdots, c_{16})$ exist such that for each $i$, ...
1
vote
1answer
31 views

How many different ways can you choose a group of 4 people?

You have a total of 9 people to choose from. Of these 9 people you are supposed to create a group of 4. How many different ways can the new group look? This is my reasoning: To the new group, the ...
3
votes
1answer
26 views

Generating Constrained Random Distributions

I am trying to help another StackExchange user. We are attempting to fill a 6x6 matrix with 12 A's, 12 B's, and 12 C's subject to the constraint that each row contains 2 A, 2B and 2 C and each column ...